aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:20:53 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:20:53 -0700
commitc95004199f9aa7dfebdab980abb42d1147790906 (patch)
tree87c1251f8bd8dc57ed537ea6f3f3d6ee6bacefef
downloadcsci2400-c95004199f9aa7dfebdab980abb42d1147790906.tar.gz
csci2400-c95004199f9aa7dfebdab980abb42d1147790906.zip
Lab 1 - Data Lab
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--lab1_datalab/Driverhdrs.pm12
-rw-r--r--lab1_datalab/Driverlib.pm138
-rw-r--r--lab1_datalab/Makefile59
-rw-r--r--lab1_datalab/README-longer.md127
-rw-r--r--lab1_datalab/README.md90
-rw-r--r--lab1_datalab/bddcheck/all-functions.txt76
-rwxr-xr-xlab1_datalab/bddcheck/cbit/cbitbin0 -> 403376 bytes
-rwxr-xr-xlab1_datalab/bddcheck/check.pl136
-rwxr-xr-xlab1_datalab/bddcheck/checkprogs.pl368
-rw-r--r--lab1_datalab/bddcheck/satparse.pl121
-rw-r--r--lab1_datalab/bits.c500
-rw-r--r--lab1_datalab/bits.h66
-rw-r--r--lab1_datalab/btest.c583
-rw-r--r--lab1_datalab/btest.h32
-rw-r--r--lab1_datalab/decl.c90
-rwxr-xr-xlab1_datalab/dlcbin0 -> 1277888 bytes
-rwxr-xr-xlab1_datalab/driver.pl526
-rw-r--r--lab1_datalab/fshow.c151
-rw-r--r--lab1_datalab/ishow.c75
-rw-r--r--lab1_datalab/tests.c153
20 files changed, 3303 insertions, 0 deletions
diff --git a/lab1_datalab/Driverhdrs.pm b/lab1_datalab/Driverhdrs.pm
new file mode 100644
index 0000000..b2c3ca5
--- /dev/null
+++ b/lab1_datalab/Driverhdrs.pm
@@ -0,0 +1,12 @@
+#
+# This file contains configuration variables for drivers.
+# It was generated by genhdrs.pl. Do not modify it.
+#
+package Driverhdrs;
+
+$LAB = "datalab";
+$SERVER_NAME = "cs2400.cs.colorado.edu";
+$SERVER_PORT = 8081;
+$COURSE_NAME = "csapp";
+$AUTOGRADE_TIMEOUT = 0;
+1;
diff --git a/lab1_datalab/Driverlib.pm b/lab1_datalab/Driverlib.pm
new file mode 100644
index 0000000..d7f7da1
--- /dev/null
+++ b/lab1_datalab/Driverlib.pm
@@ -0,0 +1,138 @@
+###############################################################
+# Driverlib.pm - A package of helper functions for Perl drivers
+#
+# Copyright (c) 2005 David R. O'Hallaron, All rights reserved.
+###############################################################
+
+package Driverlib;
+
+use Socket;
+
+# Autogenerated header file with lab-specific constants
+use lib ".";
+use Driverhdrs;
+
+require Exporter;
+@ISA = qw(Exporter);
+@EXPORT = qw(
+ driver_post
+ );
+
+use strict;
+
+#####
+# Public functions
+#
+
+#
+# driver_post - This is the routine that a driver calls when
+# it needs to transmit an autoresult string to the result server.
+#
+sub driver_post ($$) {
+ my $userid = shift; # User id for this submission
+ my $result = shift; # Autoresult string
+ my $autograded = shift; # Set if called by an autograder
+
+ # Echo the autoresult string to stdout if the driver was called
+ # by an autograder
+ if ($autograded) {
+ print "\n";
+ print "AUTORESULT_STRING=$result\n";
+ return;
+ }
+
+ # If the driver was called with a specific userid, then submit
+ # the autoresult string to the result server over the Internet.
+ if ($userid) {
+ my $status = submitr($Driverhdrs::SERVER_NAME,
+ $Driverhdrs::SERVER_PORT,
+ $Driverhdrs::COURSE_NAME,
+ $userid,
+ $Driverhdrs::LAB,
+ $result);
+
+ # Print the status of the transfer
+ if (!($status =~ /OK/)) {
+ print "$status\n";
+ print "Did not send autoresult string to the result server.\n";
+ exit(1);
+ }
+ print "Success: Sent autoresult string for $userid to the result server.\n";
+ }
+}
+
+
+#####
+# Private functions
+#
+
+#
+# submitr - Sends an autoresult string to the result server
+#
+sub submitr ($$$$$$) {
+ my $hostname = shift;
+ my $port = shift;
+ my $course = shift;
+ my $userid = shift;
+ my $lab = shift;
+ my $result = shift;
+
+ my $internet_addr;
+ my $enc_result;
+ my $paddr;
+ my $line;
+ my $http_version;
+ my $errcode;
+ my $errmsg;
+
+ # Establish the connection to the server
+ socket(SERVER, PF_INET, SOCK_STREAM, getprotobyname('tcp'));
+ $internet_addr = inet_aton($hostname)
+ or die "Could not convert $hostname to an internet address: $!\n";
+ $paddr = sockaddr_in($port, $internet_addr);
+ connect(SERVER, $paddr)
+ or die "Could not connect to $hostname:$port:$!\n";
+
+ select((select(SERVER), $| = 1)[0]); # enable command buffering
+
+ # Send HTTP request to server
+ $enc_result = url_encode($result);
+ print SERVER "GET /$course/submitr.pl/?userid=$userid&lab=$lab&result=$enc_result&submit=submit HTTP/1.0\r\n\r\n";
+
+ # Get first HTTP response line
+ $line = <SERVER>;
+ chomp($line);
+ ($http_version, $errcode, $errmsg) = split(/\s+/, $line);
+ if ($errcode != 200) {
+ return "Error: HTTP request failed with error $errcode: $errmsg";
+ }
+
+ # Read the remaining HTTP response header lines
+ while ($line = <SERVER>) {
+ if ($line =~ /^\r\n/) {
+ last;
+ }
+ }
+
+ # Read and return the response from the result server
+ $line = <SERVER>;
+ chomp($line);
+
+ close SERVER;
+ return $line;
+
+}
+
+#
+# url_encode - Encode text string so it can be included in URI of GET request
+#
+sub url_encode ($) {
+ my $value = shift;
+
+ $value =~s/([^a-zA-Z0-9_\-.])/uc sprintf("%%%02x",ord($1))/eg;
+ return $value;
+}
+
+# Always end a module with a 1 so that it returns TRUE
+1;
+
diff --git a/lab1_datalab/Makefile b/lab1_datalab/Makefile
new file mode 100644
index 0000000..2b571b4
--- /dev/null
+++ b/lab1_datalab/Makefile
@@ -0,0 +1,59 @@
+#
+# Makefile that builds btest and other helper programs for the CS:APP data lab
+#
+CC = clang
+# The -fwrapv flat instructs the compiler optimizer than overflows
+# wrap around using 2's complement addition. This disables
+# optimizations that can make specific problems hard to solve.
+#
+CFLAGS = -O -g -fwrapv -fsanitize=undefined -Wall
+LIBS = -lm
+
+default: btest
+ @echo "Run one of make [ test-coding | test-correctness | test-ops | test-score | test-count ]"
+ @echo "Or, run make grade to run all steps and get overall grade"
+
+test-coding: btest
+ @echo "This will report coding rules violations"
+ ./dlc -z bits.c
+ -rm bits.p.c
+
+test-correctness: btest
+ @echo "This will check if your functions are correct"
+ ./bddcheck/check.pl -g bits.c
+
+test-ops: btest
+ @echo "This will show illegal operations in your code"
+ ./dlc -Z bits.c
+ -rm bits.p.c
+
+test-score: btest
+ @echo "This will report per-function scores, but 'make grade' shows overall grade"
+ ./bddcheck/check.pl -g -r 2
+
+test-count: btest
+ @echo "This reports the number of operations per function"
+ ./dlc -W1 -il -e bits.c
+ -rm bits.p.c
+
+grade: btest fshow ishow
+ @echo Running tests..
+ ./driver.pl
+
+btest: btest.c bits.c decl.c tests.c btest.h bits.h
+ $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c
+
+fshow: fshow.c
+ $(CC) $(CFLAGS) -o fshow fshow.c
+
+ishow: ishow.c
+ $(CC) $(CFLAGS) -o ishow ishow.c
+
+# Forces a recompile. Used by the driver program.
+btestexplicit:
+ $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c
+
+clean:
+ rm -f *.o btest fshow ishow *~
+
+
diff --git a/lab1_datalab/README-longer.md b/lab1_datalab/README-longer.md
new file mode 100644
index 0000000..e99055f
--- /dev/null
+++ b/lab1_datalab/README-longer.md
@@ -0,0 +1,127 @@
+# CSCI 2400 - Computer Systems - Data Lab: Manipulating Bits
+
+## Details
+
+This README provides more details about the assignment and details on how to develop, debug and grade your work.
+
+## Developing & Debugging Your Puzzle Solutions
+
+There are five steps you need to go through. Each of those steps has a rule in the `Makefile` to lets you focus on that step:
+ * Write valid puzzles (`make test-coding`)
+ * Write correct puzzles (`make test-correctness`)
+ * Only use allowed operations (`make test-ops`)
+ * Figure out your score (`make test-score`)
+ * Don't use too many operations (`make test-count`)
+
+You can run all of these steps using `make grade` but the step-by-step methods are useful to sort out *why* your solution is having problems.
+
+#### The `dlc` Compiler
+`dlc` is a modified version of an ANSI C89 compiler from that you can use to check for compliance with the coding rules for each puzzle. The `dlc` program only understands the C89 standard and thus enforces a stricter form of C declarations than is the case for C++ or that is enforced by `gcc`. Any declaration must appear in a block (what you enclose in curly braces) before any statement that is not a declaration. For example, it will complain about the following code:
+
+```
+ int foo(int x)
+ {
+ int a = x;
+ a *= 3; /* Statement that is not a declaration */
+ int b = a; /* ERROR: Declaration not allowed here */
+ b *= a; // ERROR -- this comment style causes error
+```
+
+The program runs silently unless it detects a problem, such as an illegal operator, too many operators, or forbidden code (`if`, `while`, *etc*) code in the integer puzzles.
+
+Don't include the `<stdio.h>` header file in your `bits.c` file, as it confuses `dlc` and results in some non-intuitive error messages. You will still be able to use `printf` in your `bits.c` file for debugging without including the `<stdio.h>` header, although `gcc` will print a warning that you can ignore.
+
+## Grading
+
+The autograding script produces a report about 'points' -- this doesn't align with what we've described above (which is what holds). This happens in part because of the presence of the extra problems.
+
+#### `btest`
+This program checks the functional correctness of the functions in `bits.c`. To build and use it, type the following two commands:
+
+```
+ unix> make
+ unix> ./btest
+```
+
+Notice that you must rebuild `btest` each time you modify your `bits.c` file.
+
+You'll find it helpful to work through the functions one at a time, testing each one as you go. You can use the `-f` flag to instruct `btest` to test only a single function:
+```
+ unix> ./btest -f bitOr
+```
+You can feed it specific function arguments using the option flags `-1`, `-2`, and `-3`. For example, the following specifies the first argument is `7` and the second is `0xf`.
+```
+ unix> ./btest -f bitOr -1 7 -2 0xf
+```
+
+Here are the command line options for btest:
+```
+ unix> ./btest -h
+ Usage: ./btest [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>]
+ -1 <val> Specify first function argument
+ -2 <val> Specify second function argument
+ -3 <val> Specify third function argument
+ -f <name> Test only the named function
+ -g Format output for autograding with no error messages
+ -h Print this message
+ -r <n> Give uniform weight of n for all problems
+ -T <lim> Set timeout limit to lim
+```
+Examples:
+```
+ Test all functions for correctness and print out error messages:
+ unix> ./btest
+
+ Test all functions in a compact form with no error messages:
+ unix> ./btest -g
+
+ Test function foo for correctness:
+ unix> ./btest -f foo
+
+ Test function foo for correctness with specific arguments:
+ unix> ./btest -f foo -1 27 -2 0xf
+```
+Btest does not check your code for compliance with the coding
+guidelines. Use `dlc` to do that.
+
+#### `driver.pl`
+This is a driver program that uses `btest` and `dlc` to compute the correctness and performance points for your solution. It takes no arguments:
+
+```
+ unix> ./driver.pl
+```
+
+Your instructors will use `driver.pl` to evaluate your solution.
+
+## Helper program: ishow and fshow
+
+We have included the ishow and fshow programs to help you decipher
+integer and floating point representations respectively. Each takes a
+single decimal or hex number as an argument.
+
+To build them type:
+```
+ unix> make ishow fshow
+```
+The included program `fshow` helps you understand the structure of floating point numbers. You can use `fshow` to see what an arbitrary pattern represents as a floating-point number:
+```
+ unix> ./fshow 15213243
+ Floating point value 2.131829405e-38
+ Bit Representation 0x00e822bb, sign = 0, exponent = 0x01, fraction = 0x6822bb
+ Normalized. +1.8135598898 X 2^(-126)
+
+ unix> ./fshow 0x15213243
+ Floating point value 3.255334057e-26
+ Bit Representation 0x15213243, sign = 0, exponent = 0x2a, fraction = 0x213243
+ Normalized. +1.2593463659 X 2^(-85)
+```
+The `ishow` program behaves in a similar way for integer operations.
+
+Example usages:
+```
+ unix> ./ishow 0x27
+ Hex = 0x00000027, Signed = 39, Unsigned = 39
+
+ unix> ./ishow 27
+ Hex = 0x0000001b, Signed = 27, Unsigned = 27
+`` \ No newline at end of file
diff --git a/lab1_datalab/README.md b/lab1_datalab/README.md
new file mode 100644
index 0000000..5b4e395
--- /dev/null
+++ b/lab1_datalab/README.md
@@ -0,0 +1,90 @@
+[![Open in Codespaces](https://classroom.github.com/assets/launch-codespace-f4981d0f882b2a3f0472912d15f9806d57e124e0fc890972558857b51b24a6f9.svg)](https://classroom.github.com/open-in-codespaces?assignment_repo_id=9768280)
+# CSCI 2400 - Computer Systems - Data Lab: Manipulating Bits
+
+## Introduction
+
+The purpose of this assignment is to become more familiar with bit-level representations of integers (and floating point) numbers. You'll do this by solving a series of programming ``puzzles.'' Some of these puzzles are quite artificial, but you'll find yourself thinking much more about bits in working your way through them.
+
+## Logistics
+
+All handins are electronic via Github Classroom. Clarifications and corrections will be posted on the course page. Grading will be done through interviews.
+
+## Handout Instructions
+
+You will be provided a link to download a Github repository containing the template code.
+
+This will cause a number of files to be unpacked in the directory. The only file you will be modifying and turning in is `bits.c`.
+
+The `bits.c` file contains a skeleton for each of the programming puzzles. Your assignment is to complete each function skeleton. You should should not use loops or conditionals and you can only use a limited number of C arithmetic and logical operators as specified in each problem. Specifically, you are **only** allowed to use the following eight operators:
+```
+ ! ~ & ^ | + << >>
+```
+A few of the functions further restrict this list. Also, you are not allowed to use any constants longer than 8 bits, but you can construct larger constants using 8 bit constants and operators. See the comments in `bits.c` for detailed rules and a discussion of the desired coding style.
+
+## The Puzzles
+
+This section describes the puzzles that you will be solving in [bits.c](bits.c). Each problem has a **Difficulty Rating** and **maximum number of operations**. The **Rating** field gives the difficulty rating (the number of points) for the puzzle, and the **Max ops** field gives the maximum number of operators you are allowed to use to implement each function. The following report from `make grade` would score 100% and also score extra credit.
+
+```
+Points Rating Errors Points Ops Puzzle
+1 1 0 2 4 bitAnd
+1 1 0 2 4 evenBits
+1 1 0 2 5 isTmin
+2 2 0 2 7 allEvenBits
+2 2 0 2 3 getByte
+2 2 0 2 2 isNegative
+3 3 0 2 7 conditional
+3 3 0 2 6 ezThreeFourths
+3 3 0 2 3 isNonNegative
+4 4 0 2 5 isNonZero
+4 4 0 2 30 leftBitCount
+4 4 0 2 12 trueThreeFourths
+2 2 0 2 4 float_abs
+4 4 0 2 27 float_i2f
+
+General Points = 54/54 [30/30 Corr + 24/24 Perf]
+Extra Points = 10/10 [6/6 Corr + 4/4 Perf]
+
+Conversion to 40% of DataLab grading (the remaining 60% will come from interview grading)
+Execution Grade = 40
+Execution Extra = 4
+```
+Two of these problems (`float_half` and `float_i2f`) are optional extra credit problems; thus a perfect score on the required problems is a score of `32/32 Corr + 26/26 Perf`.
+
+See the comments in [bits.c](bits.c) for more details on the desired behavior of the functions. You may also refer to the test functions in [tests.c](tests.c). These are used as reference functions to express the correct behavior of your functions, although they don't satisfy the coding rules for your functions.
+
+### Floating-Point Puzzles
+
+For Extra Credit, you can implement some common single-precision floating-point operations.
+For these, you are allowed to use standard control structures (conditionals, loops), and you may use both `int` and `unsigned` data types, including arbitrary unsigned and integer constants. You may not use any unions, structs, or arrays. You may not use any floating point data types, operations, or constants. Instead, any floating-point operand will be passed to the function as having type `unsigned`, and any returned floating-point value will be of type `unsigned`. Your code should perform the bit manipulations that implement the specified floating point operations.
+
+Functions must handle the full range of possible argument values, including not-a-number (NaN) and infinity. The IEEE standard does not specify precisely how to handle NaN's, and the IA32 behavior is a bit obscure. We will follow a convention that for any function returning a NaN value, it will return the one with bit representation `0x7FC00000`. See [the longer README](README-longer.md) for details on using `fshow` to develop your solutions.
+
+## Evaluation
+
+The assignment is scored in two parts - you will receive 40 percent of the overall score for having correctly functioning functions handed in on time and 60 percent for being able to correctly explain how your functions work in your interview grading section and how to generalize those solutions.
+
+Running [make grade](README-longer.md) will grade your solution; it combines the scores for the Integer and extra-credit Floating Point puzzles. The [ longer README](README-longer.md) has information on how to test your puzzles.
+
+## Extra Credit
+You can receive up to 10% extra credit (for the whole assignment) by completing all of the floating point problems. You will have to read ahead to learn about floating point, because we're going to cover it later; however, you're going to have to learn it someday...
+
+
+## Submitting Your Assignment
+
+You should submit your assignment using `git`. The normal commands you would execute commit **a**ll the files with a **m**essage and then push them to Github.
+```
+git commit -a -m"some useful about your commit"
+git push
+```
+
+## The ``Beat the Prof'' Contest
+
+For fun, we're offering an optional ``Beat the Prof'' contest that allows you to compete with other students and the instructor to develop the most efficient puzzles. The goal is to solve each Data Lab puzzle using the fewest number of operators. Students who match or beat the instructor's operator count for each puzzle are winners!
+
+To submit your entry to the contest, type:
+```
+ unix> ./driver.pl -u ``Your Nickname''
+```
+Nicknames are limited to 35 characters and can contain alphanumerics, apostrophes, commas, periods, dashes, underscores, and ampersands. You can submit as often as you like. Your most recent submission will appear on a real-time scoreboard, identified only by your nickname. You can view the scoreboard by pointing your browser at
+[http://cs2400.cs.colorado.edu:8080](http://cs2400.cs.colorado.edu:8080).
diff --git a/lab1_datalab/bddcheck/all-functions.txt b/lab1_datalab/bddcheck/all-functions.txt
new file mode 100644
index 0000000..50e13fa
--- /dev/null
+++ b/lab1_datalab/bddcheck/all-functions.txt
@@ -0,0 +1,76 @@
+#Complete set of functions [droh fall 2010]
+#Function Rating Args
+absVal 4 [-2147483647,2147483647]
+addOK 3 all
+allEvenBits 2 all
+allOddBits 2 all
+anyEvenBit 2 all
+anyOddBit 2 all
+bang 4 all
+bitAnd 1 all
+bitCount 4 all
+bitMask 3 u5:u5
+bitNor 1 all
+bitOr 1 all
+bitParity 4 all
+bitXor 1 all
+byteSwap 2 :[0,3]:[0,3]
+conditional 3 all
+copyLSB 2 all
+divpwr2 2 :[0,30]
+evenBits 1 all
+ezThreeFourths 3 all
+fitsBits 2 :[1,32]
+fitsShort 1 all
+float_abs 2 all
+float_f2i 4 all
+float_half 4 all
+float_i2f 4 all
+float_neg 2 all
+float_twice 4 all
+getByte 2 :u2
+greatestBitPos 4 all
+howManyBits 4 all
+reverseBits 4 all
+ilog2 4 [1,2147483647]
+implication 2 [0,1]:[0,1]
+isAsciiDigit 3 all
+isEqual 2 all
+isGreater 3 all
+isLess 3 all
+isLessOrEqual 3 all
+isNegative 2 all
+isNonNegative 3 all
+isNonZero 4 all
+isNotEqual 2 all
+isPositive 3 all
+isPower2 4 all
+isTmin 1 all
+isTmax 1 all
+isZero 1 all
+leastBitPos 2 all
+leftBitCount 4 all
+logicalNeg 4 all
+logicalShift 3 :[0,31]
+minusOne 1 all
+multFiveEighths 3 all
+negate 2 all
+oddBits 2 all
+rempwr2 3 :[0,30]
+replaceByte 3 :[0,3]:[0,255]
+reverseBytes 3 all
+rotateLeft 3 :[0,31]
+rotateRight 3 :[0,31]
+satAdd 4 all
+satMul2 3 all
+satMul3 3 all
+sign 2 all
+sm2tc 4 all
+subOK 3 all
+tc2sm 4 [-2147483647,2147483647]
+thirdBits 1 all
+tmax 1 all
+tmin 1 all
+trueFiveEighths 4 all
+trueThreeFourths 4 all
+upperBits 1 [0,32]
diff --git a/lab1_datalab/bddcheck/cbit/cbit b/lab1_datalab/bddcheck/cbit/cbit
new file mode 100755
index 0000000..f708385
--- /dev/null
+++ b/lab1_datalab/bddcheck/cbit/cbit
Binary files differ
diff --git a/lab1_datalab/bddcheck/check.pl b/lab1_datalab/bddcheck/check.pl
new file mode 100755
index 0000000..b86bd2b
--- /dev/null
+++ b/lab1_datalab/bddcheck/check.pl
@@ -0,0 +1,136 @@
+#!/usr/bin/perl
+
+use Getopt::Std;
+
+$progdir = "./bddcheck";
+$Fsolve = "bits.c";
+$Fref = "tests.c";
+$Finfo = "$progdir/all-functions.txt";
+$FLAGS = "-t";
+$PROG = "$progdir/checkprogs.pl";
+
+getopts('hgtvkf:r:');
+
+if ($opt_h) {
+ print STDOUT "Usage $0 [-hgkv] [-f fun]\n";
+ print STDOUT " -h Print this message\n";
+ print STDOUT " -g Generate grading information\n";
+ print STDOUT " -k Keep intermediate files\n";
+ print STDOUT " -v Verbose mode\n";
+ print STDOUT " -f fun Test only function fun\n";
+ print STDOUT " -r rating Set rating of all functions\n";
+ exit(0);
+}
+
+if ($opt_g) {
+ printf "Score\tRating\tErrors\tFunction\n";
+ $FLAGS = "";
+}
+
+if ($opt_k) {
+ $FLAGS = "$FLAGS -k";
+}
+
+if ($opt_v) {
+ $FLAGS = "$FLAGS -v";
+ $verbose = 1;
+} else {
+ $verbose = 0;
+}
+
+# Set time limit
+$FLAGS = $FLAGS . " -T 10";
+
+
+$totalscore = 0;
+$maxscore = 0;
+$passed = 0;
+$attempted = 0;
+
+if ($opt_f) {
+ if ($verbose) {
+ print "Looking for function '$opt_f' in $Finfo\n";
+ }
+ $entry = `grep \"$opt_f \" $Finfo` || die "Couldn't find entry for function '$opt_f'\n";
+ chomp $entry;
+ ($fun,$rating,$pat) = split(/[ \t]+/, $entry);
+ if ($opt_r) {
+ $rating = $opt_r;
+ }
+ $patarg = "";
+ if (!($pat eq "all")) {
+ $patarg = " -a " . $pat;
+ }
+ if ($verbose) {
+ print "Executing $PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun\n";
+ }
+ $result = `$PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun` ||
+ die "Executing '$PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun gives ERROR\n$result";
+ if (!$opt_g) {
+ print $result;
+ }
+ $attempted++;
+ $maxscore += $rating;
+ $ok = !($result =~ /\.\. Mismatch/ || $result =~ /Error/);
+ $errors = 1-$ok;
+ $passed += $ok;
+ $score = ($ok*$rating);
+ $totalscore += $score;
+ if ($opt_g) {
+ print " $score\t$rating\t$errors\t$fun\n";
+ } else {
+ print "Check $fun score: $score/$rating\n";
+ }
+} else {
+ # Try out all functions in file
+ open TESTFILE, $Fref || die "Couldn't open reference file $Fref\n";
+ while (<TESTFILE>) {
+ $line = $_;
+ if ($line =~ /[\s]*(unsigned|int)[\s]+test_([a-zA-Z0-9_]+)[\s]*\(/) {
+ $funname = $2;
+ if ($verbose) {
+ print "Testing function '$funname'\n";
+ print "Looking for function '$funname' in $Finfo\n";
+ }
+ $entry = `grep \"$funname \" $Finfo` || die "Couldn't find entry for function '$funname'\n";
+ chomp $entry;
+ ($fun,$rating,$pat) = split(/[ \t]+/, $entry);
+ if ($opt_r) {
+ $rating = $opt_r;
+ }
+ $patarg = "";
+ if (!($pat eq "all")) {
+ $patarg = " -a " . $pat;
+ }
+ if ($verbose) {
+ print "Executing $PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun\n";
+ }
+ $result = `$PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun` ||
+ "Executing '$PROG $FLAGS $patarg -f $Fsolve -p $fun -F $Fref -P test_$fun' gives Error\n";
+ if (!$opt_g) {
+ print $result;
+ }
+ $attempted++;
+ $maxscore += $rating;
+ $ok = !($result =~ /\.\. Mismatch/ || $result =~ /Error/);
+ $errors = 1-$ok;
+ $passed += $ok;
+ $score = ($ok*$rating);
+ $totalscore += $score;
+ if ($opt_g) {
+ print " $score\t$rating\t$errors\t$fun\n";
+ } else {
+ print "Check $fun score: $score/$rating\n";
+ }
+ }
+ }
+}
+
+if (!$opt_g) {
+ print "Overall correctness score: $totalscore/$maxscore\n";
+ if ($passed == $attempted) {
+ print "All tests passed\n";
+ }
+} else {
+ print "Total points: $totalscore/$maxscore\n";
+}
diff --git a/lab1_datalab/bddcheck/checkprogs.pl b/lab1_datalab/bddcheck/checkprogs.pl
new file mode 100755
index 0000000..5571e66
--- /dev/null
+++ b/lab1_datalab/bddcheck/checkprogs.pl
@@ -0,0 +1,368 @@
+#!/usr/bin/env perl
+#!/usr/bin/env perl -w
+use Getopt::Std;
+$progdir = "./bddcheck";
+$cbit = "$progdir/cbit/cbit";
+
+# Extract named function(s) from file(s), and check for equivalence.
+
+getopts('hkvsdtbBCf:p:F:P:a:T:');
+
+if ($opt_h || !$opt_f || !$opt_p) {
+ print STDOUT "Usage $0 [-hkvsdtbB] -f file1.c -p proc1 [-F file2.c] [-P proc2]\n";
+ print STDOUT " -h Print this message\n";
+ print STDOUT " -k Keep intermediate files\n";
+ print STDOUT " -v Verbose\n";
+ print STDOUT " -s Solve using SAT solver\n";
+ print STDOUT " -d Just check for define/use errors\n";
+ print STDOUT " -C Check for casting by first function\n";
+ print STDOUT " -t Generate counterexample test code\n";
+ print STDOUT " -f file1.c First code file\n";
+ print STDOUT " -p proc1 Name of (first) function\n";
+ print STDOUT " -b First function ends with first '}'\n";
+ print STDOUT " -F file2.c Second code file\n";
+ print STDOUT " -P proc2 Name of second function\n";
+ print STDOUT " -B Second function ends with first '}'\n";
+ print STDOUT " -a argpattern Specify argument types\n";
+ print STDOUT " -T timelim Set time limit\n";
+}
+
+$file1 = $opt_f;
+$proc1 = $opt_p;
+
+$file_cnt = 1;
+if ($opt_P || $opt_F) {
+ $file_cnt = 2;
+ $file2 = $file1;
+ $proc2 = $proc1;
+ if ($opt_P) {
+ $proc2 = $opt_P;
+ }
+ if ($opt_F) {
+ $file2 = $opt_F;
+ }
+}
+
+if ($opt_C) {
+ $cbit = $cbit . " -C";
+}
+
+if ($opt_a) {
+ $cbit = $cbit . " -a " . $opt_a;
+}
+
+if ($opt_T) {
+ $cbit = $cbit . " -t " . $opt_T;
+}
+
+if ($opt_v) {
+ print "Looking for $proc1 in $file1\n";
+}
+
+# Extract first function and put into file
+$newfile1 = "$proc1-1.c";
+open(INFILE, $file1) || die("Couldn't open input file $file1\n");
+open(CODEFILE, ">$newfile1") || die("Couldn't open temporary file $newfile1\n");
+$code1 = "";
+
+$found = 0;
+$expecting_header = 1;
+$done = 0;
+while (<INFILE>)
+{
+ if ($done) {
+ break;
+ }
+ $line = $_;
+ if (!$found && $line =~ /[\s]*(int|unsigned)[\s]+$proc1[\s]*\(/) {
+ # found the line
+ $found = 1;
+ }
+ if ($found && !$done) {
+ if (!($line =~ /^#line/)) {
+ print CODEFILE $line;
+ }
+ $code1 = $code1 . $line;
+ if ($line =~ /^}/) {
+ $done = 1;
+ }
+ if ($opt_b && $line =~ /^[\s]*}/) {
+ $done = 1;
+ }
+ }
+ }
+
+if (!$found) {
+ die "Function $proc1 not found in file $file1\n";
+}
+
+close INFILE;
+close CODEFILE;
+
+if ($file_cnt > 1) {
+ if ($opt_v) {
+ print "Looking for $proc2 in $file2\n";
+ }
+
+ $newfile2 = "$proc2-2.c";
+ $code2 = "";
+ open(INFILE, $file2) || die("Couldn't open input file $file2\n");
+ open(CODEFILE, ">$newfile2") || die("Couldn't open temporary file $newfile2\n");
+
+ $found = 0;
+ $done = 0;
+ while (<INFILE>)
+ {
+ if ($done) {
+ break;
+ }
+ $line = $_;
+ if (!$found && $line =~ /[\s]*(int|unsigned)[\s]+$proc2[\s]*\(/) {
+ # found the line
+ $found = 1;
+ }
+ if ($found && !$done) {
+ print CODEFILE $line;
+ $code2 = $code2 . $line;
+ if ($line =~ /^}/) {
+ $done = 1;
+ }
+ if ($opt_B && $line =~ /^[\s]*}/) {
+ $done = 1;
+ }
+ }
+ }
+ if (!$found) {
+ die "Function $proc2 not found in file $file2\n";
+ }
+ close INFILE;
+ close CODEFILE;
+} else {
+ $newfile2 = "";
+}
+
+$root = "comp";
+$cnffile = "$root.cnf";
+$satfile = "$root.sout";
+
+
+if ($opt_d) {
+ if ($file_cnt > 1) {
+ print "Checking define/use in $file1:$proc1 and $file2:$proc2\n";
+ } else {
+ print "Checking define/use in $file1:$proc1\n";
+ }
+
+ if ($opt_v) {
+ print "$cbit -d $newfile1 -o $cnffile\n";
+ }
+ $result = `$cbit -d $newfile1 -o $cnffile` ||
+ die "ERROR: $result\nCouldn't generate CNF file $cnffile\n";
+
+ if ($opt_v) {
+ print "$zchaff $cnffile > $satfile\n";
+ }
+
+ system "$zchaff $cnffile > $satfile" || die "Couldn't run zchaff on $cnffile\n";
+
+ if ($opt_v) {
+ print "$satparse $root\n";
+ }
+
+ $satresult = `$satparse $root` || die "Couldn't analyze SAT file $satfile\n";
+ if ($satresult =~ /\sSAT\s/ || $satresult =~ Tautology) {
+ print "Define/Use violation detected in file $newfile1\n";
+ } else {
+ print "No Define/Use violations occur in file $newfile1\n";
+ }
+
+ if ($file_cnt > 1) {
+ if ($opt_v) {
+ print "$cbit -d $newfile2 -o $cnffile\n";
+ }
+ $result = `$cbit -d $newfile2 -o $cnffile` ||
+ die "ERROR: $result\nCouldn't generate CNF file $cnffile\n";
+
+ if ($opt_v) {
+ print "$zchaff $cnffile > $satfile\n";
+ }
+
+ system "$zchaff $cnffile > $satfile" || die "Couldn't run zchaff on $cnffile\n";
+
+ if ($opt_v) {
+ print "$satparse $root\n";
+ }
+
+ $satresult = `$satparse $root` || die "Couldn't analyze SAT file $satfile\n";
+ if ($satresult =~ /\sSAT\s/ || $satresult =~ /Tautology/) {
+ print "Define/Use violation detected in file $newfile2\n";
+ } else {
+ print "No Define/Use violations occur in file $newfile2\n";
+ }
+ exit(0);
+ }
+} else { # Full check
+
+ if (!$opt_s) { # Use BDDs
+ if ($opt_v) {
+ print "$cbit $newfile1 $newfile2 \n";
+ }
+
+ $satresult = `$cbit $newfile1 $newfile2` ||
+ "Error: Couldn't process file(s) $newfile1 $newfile2 with BDDs\n";
+
+ if ($opt_v) {
+ print $satresult;
+ }
+ } else { # Use SAT solver
+ if ($opt_v) {
+ print "$cbit -s $newfile1 $newfile2 -o $cnffile\n";
+ }
+
+ $result = `$cbit -s $newfile1 $newfile2 -o $cnffile` ||
+ die "ERROR: $result\nCouldn't generate CNF file $cnffile\n";
+
+ if ($opt_v) {
+ print "$zchaff $cnffile > $satfile\n";
+ }
+
+ system "$zchaff $cnffile > $satfile" || die "Couldn't run zchaff on $cnffile\n";
+
+ if ($opt_v) {
+ print "$satparse $root\n";
+ }
+
+ $satresult = `$satparse $root` || die "Couldn't analyze SAT file $satfile\n";
+
+ if ($opt_v) {
+ print $satresult;
+ }
+ }
+}
+
+$bad = ($satresult =~ /Error/ || $satresult =~ /Timeout/ || $satresult =~ /Runtime error/ ||
+ $satresult =~ /Disallowed/);
+
+if (!$bad && ($satresult =~ /\sSAT\s/ || $satresult =~ /Tautology/ || $satresult =~ /Satisfiable/)) {
+ $error = 1;
+}
+
+if ($file_cnt > 1) {
+ print "Comparing $file1:$proc1 to $file2:$proc2 .. ";
+} else {
+ print "Testing predicate $file1:$proc1 .. ";
+}
+
+
+if ($error) {
+ print "Mismatch\n";
+} else {
+ if ($bad) {
+ print "Error\n$satresult";
+ } else {
+ print "OK\n";
+ }
+}
+
+$testfile = "";
+
+$testfile = "";
+$testofile = "";
+$testexefile = "";
+
+if ($opt_t && $error) {
+ # Generate testing code
+ $testfile = "checktest.c";
+ $testofile = "checktest";
+ $testexefile = "checktest.exe";
+ $argstring = "";
+ $firstarg = 1;
+ if ($proc1 eq $proc2) {
+ # Need to rename function to avoid name collision
+ $nproc1 = $proc1 . "_1";
+ $nproc2 = $proc1 . "_2";
+ $code1 =~ s/$proc1/$nproc1/;
+ $code2 =~ s/$proc2/$nproc2/;
+ $proc1 = $nproc1;
+ $proc2 = $nproc2;
+ }
+ open(TESTFILE, ">$testfile") || die("Couldn't open test file $testfile\n");
+ @arglines = split(/\n/, $satresult);
+ foreach $sline (@arglines) {
+ chomp $sline;
+ if ($sline =~ /arg-([a-zA-Z_0-9]+):([-]*[0-9]+)/) {
+ $val = $2;
+ if ($val eq "-2147483648") {
+ $val = "1<<31";
+ }
+ if ($firstarg) {
+ $argstring = $val;
+ } else {
+ $argstring = $argstring . ", " . $val;
+ }
+ $firstarg = 0;
+ }
+ }
+ print TESTFILE <<HERE;
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+/* Convert from bit level representation to floating point number */
+float u2f(unsigned u) {
+ union {
+ unsigned u;
+ float f;
+ } a;
+ a.u = u;
+ return a.f;
+}
+
+/* Convert from floating point number to bit-level representation */
+unsigned f2u(float f) {
+ union {
+ unsigned u;
+ float f;
+ } a;
+ a.f = f;
+ return a.u;
+}
+
+/* Fix any NaN to be NaN value 0x7FC00000 */
+float fix_nan(float f)
+{
+ if (isnanf(f))
+ return u2f(0x7FC0000);
+ else
+ return f;
+}
+
+$code1
+
+$code2
+
+int main()
+{
+ int val1 = $proc1($argstring);
+ int val2 = $proc2($argstring);
+ printf("$proc1($argstring) --> %d [0x%x]\\n", val1, val1);
+ printf("$proc2($argstring) --> %d [0x%x]\\n", val2, val2);
+ if (val1 == val2) {
+ printf(".. False negative\\n");
+ } else
+ printf(".. A genuine counterexample\\n");
+}
+HERE
+ system "gcc -o $testofile $testfile" || die "Couldn't compile $testfile\n";
+system "./$testofile" || die "Couldn't run test file $testofile\n";
+}
+
+if (!$opt_k) {
+ system "rm -f $newfile1 $newfile2 $cnffile $satfile" ||
+ die "Couldn't remove files $newfile1 $newfile2 $cnffile $satfile\n";
+ if ($opt_t && $error) {
+ system "rm -f $testfile $testofile $testexefile" ||
+ die "Couldn't remove files $newfile1 $newfile2 $cnffile $satfile\n";
+ }
+}
+
diff --git a/lab1_datalab/bddcheck/satparse.pl b/lab1_datalab/bddcheck/satparse.pl
new file mode 100644
index 0000000..e39202f
--- /dev/null
+++ b/lab1_datalab/bddcheck/satparse.pl
@@ -0,0 +1,121 @@
+#!/usr/local/bin/perl
+#!/usr/local/bin/perl -w
+
+# Parse SAT values from .cnf file comments & SAT output .sout to generate
+# satisfying solution
+
+# Usage: satparse.pl rootname
+if (@ARGV != 1) {
+ die "Usage: $0 rootname\n";
+}
+
+$rootname = $ARGV[0];
+
+# Build up array of PI names
+open(CNFFILE, "$rootname.cnf") || die "Couldn't open CNF file $rootname.cnf\n";
+
+@input = ();
+@asst = ();
+@show = ();
+
+$iname = ();
+@ivec = ();
+$num = 0;
+$inum = 0;
+
+while (<CNFFILE>) {
+ $line = $_;
+ chomp($line);
+ if ($line =~ "tautology") {
+ print "Tautology\n";
+ exit;
+ }
+ if ($line =~ "c BPI") {
+ ($j1,$j2,$num,$name) = split(/ /, $line);
+ $input[$num] = $name;
+ $show[$num] = 1;
+ $asst[$num] = 0;
+ $num++;
+ }
+ if ($line =~ "c IPI") {
+ ($j1,$j2,$name,$ids) = split(/ /, $line);
+ $iname[$inum] = $name;
+ $ivec[$inum] = $ids;
+ $inum++;
+ foreach $id (split(/:/, $ids)) {
+ if ($id > 0 && $id < $num) {
+ $show[$id] = 0;
+ }
+ }
+ }
+ if ($line =~ "p cnf") {
+ break;
+ }
+}
+close CNFFILE;
+
+$acount = @input;
+
+open(SATFILE, "$rootname.sout")
+ || die "Couldn't open SAT output file $rootname.sout\n";
+
+$ready = 0;
+while (<SATFILE>) {
+ $line = $_;
+ chomp($line);
+ if ($line =~ /Total Run Time[\s]*([0-9]+\.[0-9]*)/) {
+ $time = $1;
+ print "Time: $time secs\n";
+ }
+ if ($line =~ /Total Run Time[\s]*([0-9]+)/) {
+ $time = $1;
+ print "Time: $time.0 secs\n";
+ }
+ if ($line =~ "unsatisfiable" || $line =~ "Unsatisfiable" || $line =~ "RESULT: UNSAT") {
+ print "Unsatisfiable\n";
+ } elsif ($line =~ "satisfiable" || $line =~ "Satisfiable" || $line =~ "RESULT: SAT") {
+ print "Satisfiable\n";
+ $ready = 1;
+ } elsif ($line =~ /TIME OUT/) {
+ print "Timeout";
+ } elsif ($ready) {
+ # This is the real line
+ @vals = split(/ /, $line);
+ foreach $v (@vals) {
+ $var = $v;
+ $val = 1;
+ if ($var < 0) {
+ $var = -$var;
+ $val = 0;
+ }
+ if ($var > 0 && $var < $acount) {
+ $asst[$var] = $val;
+ }
+ }
+
+ }
+}
+
+for ($i = 0; $i < $acount; $i++) {
+ if ($input[$i] && $show[$i]) {
+ print "$input[$i]:$asst[$i]\n";
+ }
+}
+
+$icount = @iname;
+
+for ($i = 0; $i < $icount; $i++) {
+ @ids = split(/:/, $ivec[$i]);
+ $vlen = @ids;
+ $val = 0;
+ $p2 = 1;
+ for ($j = 0; $j < $vlen; $j++) {
+ $sign = 1;
+ if ($j == $vlen -1 && $j >= 31) {
+ $sign = -1;
+ }
+ $val = $val + $p2*$asst[$ids[$j]] * $sign;
+ $p2 *= 2;
+ }
+ print "$iname[$i]:$val\n";
+}
diff --git a/lab1_datalab/bits.c b/lab1_datalab/bits.c
new file mode 100644
index 0000000..5773007
--- /dev/null
+++ b/lab1_datalab/bits.c
@@ -0,0 +1,500 @@
+/*
+ * CS:APP Data Lab
+ *
+ * Jack Sangdahl (@waffle87 [github])
+ *
+ * bits.c - Source file with your solutions to the Lab.
+ * This is the file you will hand in to your instructor.
+ *
+ * WARNING: Do not include the <stdio.h> header; it confuses the dlc
+ * compiler. You can still use printf for debugging without including
+ * <stdio.h>, although you might get a compiler warning. In general,
+ * it's not good practice to ignore compiler warnings, but in this
+ * case it's OK.
+ */
+
+#if 0
+/*
+ * Instructions to Students:
+ *
+ * STEP 1: Read the following instructions carefully.
+ */
+
+You will provide your solution to the Data Lab by
+editing the collection of functions in this source file.
+
+INTEGER CODING RULES:
+
+ Replace the "return" statement in each function with one
+ or more lines of C code that implements the function. Your code
+ must conform to the following style:
+
+ int Funct(arg1, arg2, ...) {
+ /* brief description of how your implementation works */
+ int var1 = Expr1;
+ ...
+ int varM = ExprM;
+
+ varJ = ExprJ;
+ ...
+ varN = ExprN;
+ return ExprR;
+ }
+
+ Each "Expr" is an expression using ONLY the following:
+ 1. Integer constants 0 through 255 (0xFF), inclusive. You are
+ not allowed to use big constants such as 0xffffffff.
+ 2. Function arguments and local variables (no global variables).
+ 3. Unary integer operations ! ~
+ 4. Binary integer operations & ^ | + << >>
+
+ Some of the problems restrict the set of allowed operators even further.
+ Each "Expr" may consist of multiple operators. You are not restricted to
+ one operator per line.
+
+ You are expressly forbidden to:
+ 1. Use any control constructs such as if, do, while, for, switch, etc.
+ 2. Define or use any macros.
+ 3. Define any additional functions in this file.
+ 4. Call any functions.
+ 5. Use any other operations, such as &&, ||, -, or ?:
+ 6. Use any form of casting.
+ 7. Use any data type other than int. This implies that you
+ cannot use arrays, structs, or unions.
+
+
+ You may assume that your machine:
+ 1. Uses 2s complement, 32-bit representations of integers.
+ 2. Performs right shifts arithmetically and a negative shift value results in zero.
+ 3. Has unpredictable behavior when shifting an integer by more
+ than the word size.
+
+EXAMPLES OF ACCEPTABLE CODING STYLE:
+ /*
+ * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
+ */
+ int pow2plus1(int x) {
+ /* exploit ability of shifts to compute powers of 2 */
+ return (1 << x) + 1;
+ }
+
+ /*
+ * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
+ */
+ int pow2plus4(int x) {
+ /* exploit ability of shifts to compute powers of 2 */
+ int result = (1 << x);
+ result += 4;
+ return result;
+ }
+
+FLOATING POINT CODING RULES
+
+For the problems that require you to implent floating-point operations,
+the coding rules are less strict. You are allowed to use looping and
+conditional control. You are allowed to use both ints and unsigneds.
+You can use arbitrary integer and unsigned constants.
+
+You are expressly forbidden to:
+ 1. Define or use any macros.
+ 2. Define any additional functions in this file.
+ 3. Call any functions.
+ 4. Use any form of casting.
+ 5. Use any data type other than int or unsigned. This means that you
+ cannot use arrays, structs, or unions.
+ 6. Use any floating point data types, operations, or constants.
+
+
+ * STEP 2: Modify the following functions according the coding rules.
+ *
+ * IMPORTANT. TO AVOID GRADING SURPRISES, FOLLOW THE DIRECTIONS in README.md
+ */
+
+
+#endif
+/* Copyright (C) 1991-2022 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <https://www.gnu.org/licenses/>. */
+/* This header is separate from features.h so that the compiler can
+ include it implicitly at the start of every compilation. It must
+ not itself include <features.h> or any other header that includes
+ <features.h> because the implicit include comes before any feature
+ test macros that may be defined in a source file before it first
+ explicitly includes a system header. GCC knows the name of this
+ header in order to preinclude it. */
+/* glibc's intent is to support the IEC 559 math functionality, real
+ and complex. If the GCC (4.9 and later) predefined macros
+ specifying compiler intent are available, use them to determine
+ whether the overall intent is to support these features; otherwise,
+ presume an older compiler has intent to support these features and
+ define these macros by default. */
+/* wchar_t uses Unicode 10.0.0. Version 10.0 of the Unicode Standard is
+ synchronized with ISO/IEC 10646:2017, fifth edition, plus
+ the following additions from Amendment 1 to the fifth edition:
+ - 56 emoji characters
+ - 285 hentaigana
+ - 3 additional Zanabazar Square characters */
+/*
+ * bitAnd - x&y using only ~ and |
+ * Example: bitAnd(6, 5) = 4
+ * Legal ops: ~ |
+ * Max ops: 8
+ * Rating: 1
+ */
+int bitAnd(int x, int y) {
+ /*
+ * use's de morgan's law of intersection:
+ * x & y == ~~(x & y) == ~(~x | ~y)
+ *
+ * eg. (6 & 5)
+ * 110
+ * & 101
+ * 100 (4)
+ *
+ * ~110 = 001
+ * ~101 = 010
+ *
+ * 001
+ * | 010
+ * 011
+ *
+ * ~011 = 100 (4)
+ */
+ return ~(~x | ~y);
+}
+/*
+ * evenBits - return word with all even-numbered bits set to 1
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 8
+ * Rating: 1
+ */
+int evenBits(void) {
+ //essentially turning 8-bit number into 32-bit number.
+ int word = 85; //0b01010101
+ /*
+ * begin with 85 as it is the largest 8-bit number following [01] pattern.
+ * shift all values left by one byte (0b0101010100000000) to make lower 8 bits 0
+ * and use 'or' operator to flip bits compared to original state of'word', then
+ * repeat with two bytes. (we can only do shifts of 8 and 16 bits at a time b/c
+ * that's the size of the word we're or'ing it to)
+ */
+ word |= word << 8; //0b101010101010101
+ word |= word << 16; //0b1010101010101010101010101010101
+ return word;
+}
+/*
+ * isTmin - returns 1 if x is the minimum two's complement number, and 0 otherwise
+ * Legal ops: ! ~ & ^ | +
+ * Max ops: 10
+ * Rating: 1
+ */
+int isTmin(int x) {
+ /*
+ * Tmin = 0x80000000 (0b10000000000000000000000000000000) aka INT_MIN for signed integers
+ * first use '!x' to verify 'x' isn't zero
+ * then add 'x' to test for overflow: (if 'x' != Tmin, there won't be any)
+ * x = -2147483648
+ * + 2147483648
+ * = 0
+ * !0 = 1
+ * !x = 0
+ * | = 1 (tmin!!!)
+ */
+ return !x ^ !(x + x);
+}
+/*
+ * allEvenBits - return 1 if all even-numbered bits in word set to 1
+ * Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 12
+ * Rating: 2
+ */
+int allEvenBits(int x) {
+ /* all even bits:
+ * ("even numbered bits" refers to bit position eg:
+ * 0 2 4 6 8 etc.)
+ * 0xFFFFFFFE (0b11111111111111111111111111111110) -> returns 0
+ * 0x55555555 (0b01010101010101010101010101010101) -> returns 1
+ * essentially need to check MSB & 1, so
+ * shift 'x' right (arithmetically b/c signed value) sequentially
+ * to put MSB in LSB, then compare it with 1, where '1' is the LSB
+ */
+ x &= x >> 16;
+ x &= x >> 8;
+ x &= x >> 4;
+ x &= x >> 2;
+ return x & 1;
+}
+/*
+ * getByte - Extract byte n from word x
+ * Bytes numbered from 0 (LSB) to 3 (MSB)
+ * Examples: getByte(0x12345678,1) = 0x56
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 6
+ * Rating: 2
+ */
+int getByte(int x, int n) {
+ /*
+ * n = 3 2 1 0
+ * 0x[12][34][56][78]
+ *
+ * n == 0 -> no shift and return 'x & 0xFF'
+ * n > 0 -> shift 'x' (8 * n) to right and return 'x & 0xFF'
+ *
+ * eg. n = 1
+ * first shift 'x' left by '8 * n' bits:
+ * 0b0001 << 3 = 0b1000 (0x08)
+ * 0x12345678 >> 0x08 = 0x123456 (getting rid of last 'n' byte(s))
+ * then use '& 0xFF' to get last bit of hexadecimal number:
+ * 0x123456 & 0xFF = 0x56
+ */
+ return (x >> (n << 3)) & 0xFF;
+}
+/*
+ * isNegative - return 1 if x < 0, return 0 otherwise
+ * Example: isNegative(-1) = 1.
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 6
+ * Rating: 2
+ */
+int isNegative(int x) {
+ /*
+ * if x < 0, MSB == 1
+ * if x >= 0, MSB == 0
+ * so we can simply check the MSB by shifting 'x'
+ * right by 31 bits to put MSB in LSB position,
+ * essentially making it 'x's value 0x01 or or 0x00
+ * then use double not to either return 0 or 1
+ * eg. MSB = 1 (negative):
+ * !1 = 0, !0 = 1
+ *
+ * MSB = 0 (positive):
+ * !0 = 1, !1 = 0
+ */
+ x >>= 31;
+ return !!x;
+}
+/*
+ * conditional - same as x ? y : z
+ * Example: conditional(2,4,5) = 4
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 16
+ * Rating: 3
+ */
+int conditional(int x, int y, int z) {
+ /*
+ * if (x != 0)
+ * return y
+ * else
+ * return z
+ *
+ * create a mask based on 'x's value:
+ * eg. x = 8 x = 0
+ * !x = 0 !x = 1
+ * ~0 = -1 ~0 = -1
+ * + -1 + 0
+ * return 'y' or 'z' based on 'x's value
+ */
+ int mask = (!x + ~0);
+ return (y & mask) | (z & ~mask);
+}
+/*
+ * ezThreeFourths - multiplies by 3/4 rounding toward 0,
+ * Should exactly duplicate effect of C expression (x*3/4),
+ * including overflow behavior.
+ * Examples: ezThreeFourths(11) = 8
+ * ezThreeFourths(-9) = -6
+ * ezThreeFourths(1073741824) = -268435456 (overflow)
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 12
+ * Rating: 3
+ */
+int ezThreeFourths(int x) {
+ /*
+ * '(x * 3/4)' can be expressed as '(x + x + x) >> 2'
+ * broken down:
+ * x * 3 == x + x + x
+ * / 4 == >> 2
+ *
+ * however negative values require additional steps ('z' variable):
+ * first check if number is positive or negative by arithmetically
+ * shifting 'y' right by 31 bits (all 1's = -1 (negative)):
+ * positive: z = 0
+ * negative: z = -1
+ * if 'z' is negative, add a bias of 3 to 'y'
+ * finally shift 'y' right 2
+ */
+ //x = -9
+ int y = x + x + x; //0b11100101 (-27)
+ int z = y >> 31; //0b11111111 (-1)
+ z &= 3; //0b00000011 (3)
+ y += z; //0b11101000 (-24)
+ y >>= 2; //0b11111010 (-6)
+ return y;
+}
+/*
+ * isNonNegative - return 1 if x >= 0, return 0 otherwise
+ * Example: isNonNegative(-1) = 0. isNonNegative(0) = 1.
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 6
+ * Rating: 3
+ */
+int isNonNegative(int x) {
+ //identical to isNegative, just return single !x, instead of !!x
+ x >>= 31;
+ return !x;
+}
+/*
+ * isNonZero - Check whether x is nonzero using
+ * the legal operators except !
+ * Examples: isNonZero(3) = 1, isNonZero(0) = 0
+ * Legal ops: ~ & ^ | + << >>
+ * Max ops: 10
+ * Rating: 4
+ */
+int isNonZero(int x) {
+ /*
+ * use 2's complement
+ * if x == 0: '~x + 1 = 0'
+ * ~0 = -1
+ * + 1
+ * 0
+ * otherwise, '~x + 1 != 0'
+ * ~3 = -4
+ * + 1
+ * -3
+ *
+ * then shift this value right by 31 to place MSB in LSB
+ * then check if 'x' is zero or not with x | x:
+ * 3 | -1 = -1
+ * or
+ * 0 | 0 = 0
+ *
+ * use x & 1 to return either 0 or 1:
+ * 0b0000
+ * & 0b0000
+ * 0
+ * or
+ * 0b1111
+ * & 0b0001
+ * 1
+ */
+ return ((x | (~x + 1)) >> 31) & 1;
+}
+/*
+ * leftBitCount - returns count of number of consective 1's in
+ * left-hand (most significant) end of word.
+ * Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 50
+ * Rating: 4
+ */
+int leftBitCount(int x) {
+ /*
+ * think of binary search (divide and conquer)
+ * p1 p2
+ * eg. 0b[1111111111110000][1111000011110000] (0xFFF0F0F0)
+ * p3 p4 p5 p6
+ * [11111111][11110000][11110000][11110000]
+ * first check if p1 is all 1's,
+ * if yes, repeat process in p3
+ * if not, repeat process in p5
+ */
+ int y = !~x, res, shift;
+ //check first 16 bits and append to 'res' if they exist
+ //otherwise shift 'x' over by 16 so they're 0
+ res = !(~x >> 16) << 4;
+ x <<= res;
+ //check last 8 bits (24-32)
+ shift = !(~x >> 24) << 3;
+ x <<= shift;
+ res |= shift;
+ //check last 4 bits
+ shift = !(~x >> 28) << 2;
+ x <<= shift;
+ res |= shift;
+ //check last 2 bits
+ shift = !(~x >> 30) << 1;
+ x <<= shift;
+ res |= shift;
+ //check last bit
+ res ^= 1 & x >> 31;
+ //return final count + 'y' to make it into 32 bit number
+ return res + y;
+}
+/*
+ * trueThreeFourths - multiplies by 3/4 rounding toward 0,
+ * avoiding errors due to overflow
+ * Examples: trueThreeFourths(11) = 8
+ * trueThreeFourths(-9) = -6
+ * trueThreeFourths(1073741824) = 805306368 (no overflow)
+ * Legal ops: ! ~ & ^ | + << >>
+ * Max ops: 20
+ * Rating: 4
+ */
+int trueThreeFourths(int x) {
+ /* eg. x = -9
+ * first check if 'x' is negative by shifting right 31 bits to access MSB:
+ * -9 >> 31 = -1 (sign)
+ * x & 3 can be used to calculate remainder of 'x / 4':
+ * -9 & 3 = 3 (rem)
+ * calculate 'x / 4' next to avoid overflow:
+ * -9 >> 2 = -3 (x)
+ * calculate 'x * 3' by shifting left one bit and adding to existing value of 'x':
+ * -3 << 1 = -6 + -3 = -9 (x)
+ * inverse of 'x' to "prepare" for subtraction
+ * 3 << 1 = 6 + 3 = 9 (rem)
+ * -1 & 3 = 3 + 9 = 12 (rem)
+ * add 'rem' and 'x'
+ * 12 >> 2 = 3 + -9 = 6 (x)
+ */
+ int sign = x >> 31;
+ int rem = x & 3;
+ x >>= 2;
+ x += x << 1;
+ rem += rem << 1;
+ rem += sign & 3;
+ return x += rem >> 2;
+}
+/*
+ * Extra credit
+ */
+/*
+ * float_abs - Return bit-level equivalent of absolute value of f for
+ * floating point argument f.
+ * Both the argument and result are passed as unsigned int's, but
+ * they are to be interpreted as the bit-level representations of
+ * single-precision floating point values.
+ * When argument is NaN, return argument..
+ * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
+ * Max ops: 10
+ * Rating: 2
+ */
+unsigned float_abs(unsigned uf) {
+ return 2;
+}
+/*
+ * float_i2f - Return bit-level equivalent of expression (float) x
+ * Result is returned as unsigned int, but
+ * it is to be interpreted as the bit-level representation of a
+ * single-precision floating point values.
+ * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
+ * Max ops: 30
+ * Rating: 4
+ */
+unsigned float_i2f(int x) {
+ return 2;
+}
diff --git a/lab1_datalab/bits.h b/lab1_datalab/bits.h
new file mode 100644
index 0000000..2b4becc
--- /dev/null
+++ b/lab1_datalab/bits.h
@@ -0,0 +1,66 @@
+/* Copyright (C) 1991-2022 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <https://www.gnu.org/licenses/>. */
+/* This header is separate from features.h so that the compiler can
+ include it implicitly at the start of every compilation. It must
+ not itself include <features.h> or any other header that includes
+ <features.h> because the implicit include comes before any feature
+ test macros that may be defined in a source file before it first
+ explicitly includes a system header. GCC knows the name of this
+ header in order to preinclude it. */
+/* glibc's intent is to support the IEC 559 math functionality, real
+ and complex. If the GCC (4.9 and later) predefined macros
+ specifying compiler intent are available, use them to determine
+ whether the overall intent is to support these features; otherwise,
+ presume an older compiler has intent to support these features and
+ define these macros by default. */
+/* wchar_t uses Unicode 10.0.0. Version 10.0 of the Unicode Standard is
+ synchronized with ISO/IEC 10646:2017, fifth edition, plus
+ the following additions from Amendment 1 to the fifth edition:
+ - 56 emoji characters
+ - 285 hentaigana
+ - 3 additional Zanabazar Square characters */
+int bitAnd(int, int);
+int test_bitAnd(int, int);
+int evenBits();
+int test_evenBits();
+int isTmin(int);
+int test_isTmin(int);
+int allEvenBits();
+int test_allEvenBits();
+int getByte(int, int);
+int test_getByte(int, int);
+int isNegative(int);
+int test_isNegative(int);
+int conditional(int, int, int);
+int test_conditional(int, int, int);
+int ezThreeFourths(int);
+int test_ezThreeFourths(int);
+int isNonNegative(int);
+int test_isNonNegative(int);
+int isNonZero(int);
+int test_isNonZero(int);
+int leftBitCount(int);
+int test_leftBitCount(int);
+int trueThreeFourths(int);
+int test_trueThreeFourths(int);
+/*
+ * Extra credit
+ */
+unsigned float_abs(unsigned);
+unsigned test_float_abs(unsigned);
+unsigned float_i2f(int);
+unsigned test_float_i2f(int);
diff --git a/lab1_datalab/btest.c b/lab1_datalab/btest.c
new file mode 100644
index 0000000..0382126
--- /dev/null
+++ b/lab1_datalab/btest.c
@@ -0,0 +1,583 @@
+/*
+ * CS:APP Data Lab
+ *
+ * btest.c - A test harness that checks a student's solution in bits.c
+ * for correctness.
+ *
+ * Copyright (c) 2001-2011, R. Bryant and D. O'Hallaron, All rights
+ * reserved. May not be used, modified, or copied without permission.
+ *
+ * This is an improved version of btest that tests large windows
+ * around zero and tmin and tmax for integer puzzles, and zero, norm,
+ * and denorm boundaries for floating point puzzles.
+ *
+ * Note: not 64-bit safe. Always compile with gcc -m32 option.
+ */
+#include <stdio.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <signal.h>
+#include <setjmp.h>
+#include <math.h>
+#include "btest.h"
+
+/* Not declared in some stdlib.h files, so define here */
+float strtof(const char *nptr, char **endptr);
+
+/*************************
+ * Configuration Constants
+ *************************/
+
+/* Handle infinite loops by setting upper limit on execution time, in
+ seconds */
+#define TIMEOUT_LIMIT 10
+
+/* For functions with a single argument, generate TEST_RANGE values
+ above and below the min and max test values, and above and below
+ zero. Functions with two or three args will use square and cube
+ roots of this value, respectively, to avoid combinatorial
+ explosion */
+#define TEST_RANGE 500000
+
+/* This defines the maximum size of any test value array. The
+ gen_vals() routine creates k test values for each value of
+ TEST_RANGE, thus MAX_TEST_VALS must be at least k*TEST_RANGE */
+#define MAX_TEST_VALS 13*TEST_RANGE
+
+/**********************************
+ * Globals defined in other modules
+ **********************************/
+/* This characterizes the set of puzzles to test.
+ Defined in decl.c and generated from templates in ./puzzles dir */
+extern test_rec test_set[];
+
+/************************************************
+ * Write-once globals defined by command line args
+ ************************************************/
+
+/* Emit results in a format for autograding, without showing
+ and counter-examples */
+static int grade = 0;
+
+/* Time out after this number of seconds */
+static int timeout_limit = TIMEOUT_LIMIT; /* -T */
+
+/* If non-NULL, test only one function (-f) */
+static char* test_fname = NULL;
+
+/* Special case when only use fixed argument(s) (-1, -2, or -3) */
+static int has_arg[3] = {0,0,0};
+static unsigned argval[3] = {0,0,0};
+
+/* Use fixed weight for rating, and if so, what should it be? (-r) */
+static int global_rating = 0;
+
+/******************
+ * Helper functions
+ ******************/
+
+/*
+ * Signal - installs a signal handler
+ */
+typedef void handler_t(int);
+
+handler_t *Signal(int signum, handler_t *handler)
+{
+ struct sigaction action, old_action;
+
+ action.sa_handler = handler;
+ sigemptyset(&action.sa_mask); /* block sigs of type being handled */
+ action.sa_flags = SA_RESTART; /* restart syscalls if possible */
+
+ if (sigaction(signum, &action, &old_action) < 0)
+ perror("Signal error");
+ return (old_action.sa_handler);
+}
+
+/*
+ * timeout_handler - SIGALARM hander
+ */
+sigjmp_buf envbuf;
+void timeout_handler(int sig) {
+ siglongjmp(envbuf, 1);
+}
+
+/*
+ * random_val - Return random integer value between min and max
+ */
+static int random_val(int min, int max)
+{
+ double weight = rand()/(double) RAND_MAX;
+ int result = min * (1-weight) + max * weight;
+ return result;
+}
+
+/*
+ * gen_vals - Generate the integer values we'll use to test a function
+ */
+static int gen_vals(int test_vals[], int min, int max, int test_range, int arg)
+{
+ int i;
+ int test_count = 0;
+
+ /* Special case: If the user has specified a specific function
+ argument using the -1, -2, or -3 flags, then simply use this
+ argument and return */
+ if (has_arg[arg]) {
+ test_vals[0] = argval[arg];
+ return 1;
+ }
+
+ /*
+ * Special case: Generate test vals for floating point functions
+ * where the input argument is an unsigned bit-level
+ * representation of a float. For this case we want to test the
+ * regions around zero, the smallest normalized and largest
+ * denormalized numbers, one, and the largest normalized number,
+ * as well as inf and nan.
+ */
+ if ((min == 1 && max == 1)) {
+ unsigned smallest_norm = 0x00800000;
+ unsigned one = 0x3f800000;
+ unsigned largest_norm = 0x7f000000;
+
+ unsigned inf = 0x7f800000;
+ unsigned nan = 0x7fc00000;
+ unsigned sign = 0x80000000;
+
+ /* Test range should be at most 1/2 the range of one exponent
+ value */
+ if (test_range > (1 << 23)) {
+ test_range = 1 << 23;
+ }
+
+ /* Functions where the input argument is an unsigned bit-level
+ representation of a float. The number of tests generated
+ inside this loop body is the value k referenced in the
+ comment for the global variable MAX_TEST_VALS. */
+
+ for (i = 0; i < test_range; i++) {
+ /* Denorms around zero */
+ test_vals[test_count++] = i;
+ test_vals[test_count++] = sign | i;
+
+ /* Region around norm to denorm transition */
+ test_vals[test_count++] = smallest_norm + i;
+ test_vals[test_count++] = smallest_norm - i;
+ test_vals[test_count++] = sign | (smallest_norm + i);
+ test_vals[test_count++] = sign | (smallest_norm - i);
+
+ /* Region around one */
+ test_vals[test_count++] = one + i;
+ test_vals[test_count++] = one - i;
+ test_vals[test_count++] = sign | (one + i);
+ test_vals[test_count++] = sign | (one - i);
+
+ /* Region below largest norm */
+ test_vals[test_count++] = largest_norm - i;
+ test_vals[test_count++] = sign | (largest_norm - i);
+ }
+
+ /* special vals */
+ test_vals[test_count++] = inf; /* inf */
+ test_vals[test_count++] = sign | inf; /* -inf */
+ test_vals[test_count++] = nan; /* nan */
+ test_vals[test_count++] = sign | nan; /* -nan */
+
+ return test_count;
+ }
+
+
+ /*
+ * Normal case: Generate test vals for integer functions
+ */
+
+ /* If the range is small enough, then do exhaustively */
+ if (max - MAX_TEST_VALS <= min) {
+ for (i = min; i <= max; i++)
+ test_vals[test_count++] = i;
+ return test_count;
+ }
+
+ /* Otherwise, need to sample. Do so near the boundaries, around
+ zero, and for some random cases. */
+ for (i = 0; i < test_range; i++) {
+
+ /* Test around the boundaries */
+ test_vals[test_count++] = min + i;
+ test_vals[test_count++] = max - i;
+
+ /* If zero falls between min and max, then also test around zero */
+ if (i >= min && i <= max)
+ test_vals[test_count++] = i;
+ if (-i >= min && -i <= max)
+ test_vals[test_count++] = -i;
+
+ /* Random case between min and max */
+ test_vals[test_count++] = random_val(min, max);
+
+ }
+ return test_count;
+}
+
+/*
+ * test_0_arg - Test a function with zero arguments
+ */
+static int test_0_arg(funct_t f, funct_t ft, char *name)
+{
+ int r = f();
+ int rt = ft();
+ int error = (r != rt);
+
+ if (error && !grade)
+ printf("ERROR: Test %s() failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, r, r, rt, rt);
+
+ return error;
+}
+
+/*
+ * test_1_arg - Test a function with one argument
+ */
+static int test_1_arg(funct_t f, funct_t ft, int arg1, char *name)
+{
+ funct1_t f1 = (funct1_t) f;
+ funct1_t f1t = (funct1_t) ft;
+ int r, rt, error;
+
+ r = f1(arg1);
+ rt = f1t(arg1);
+ error = (r != rt);
+ if (error && !grade)
+ printf("ERROR: Test %s(%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, r, r, rt, rt);
+
+ return error;
+}
+
+/*
+ * test_2_arg - Test a function with two arguments
+ */
+static int test_2_arg(funct_t f, funct_t ft, int arg1, int arg2, char *name)
+{
+ funct2_t f2 = (funct2_t) f;
+ funct2_t f2t = (funct2_t) ft;
+ int r = f2(arg1, arg2);
+ int rt = f2t(arg1, arg2);
+ int error = (r != rt);
+
+ if (error && !grade)
+ printf("ERROR: Test %s(%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, r, r, rt, rt);
+
+ return error;
+}
+
+/*
+ * test_3_arg - Test a function with three arguments
+ */
+static int test_3_arg(funct_t f, funct_t ft,
+ int arg1, int arg2, int arg3, char *name)
+{
+ funct3_t f3 = (funct3_t) f;
+ funct3_t f3t = (funct3_t) ft;
+ int r = f3(arg1, arg2, arg3);
+ int rt = f3t(arg1, arg2, arg3);
+ int error = (r != rt);
+
+ if (error && !grade)
+ printf("ERROR: Test %s(%d[0x%x],%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, arg3, arg3, r, r, rt, rt);
+
+ return error;
+}
+
+/*
+ * test_function - Test a function. Return number of errors
+ */
+static int test_function(test_ptr t) {
+ int test_counts[3]; /* number of test values for each arg */
+ int args = t->args; /* number of function arguments */
+ int arg_test_range[3] = {0}; /* test range for each argument */
+ int i, a1, a2, a3;
+ int errors = 0;
+
+ /* These are the test values for each arg. Declared with the
+ static attribute so that the array will be allocated in bss
+ rather than the stack */
+ static int arg_test_vals[3][MAX_TEST_VALS];
+
+ /* Sanity check on the number of args */
+ if (args < 0 || args > 3) {
+ printf("Configuration error: invalid number of args (%d) for function %s\n", args, t->name);
+ exit(1);
+ }
+
+ /* Assign range of argument test vals so as to conserve the total
+ number of tests, independent of the number of arguments */
+ if (args == 1) {
+ arg_test_range[0] = TEST_RANGE;
+ }
+ else if (args == 2) {
+ arg_test_range[0] = pow((double)TEST_RANGE, 0.5); /* sqrt */
+ arg_test_range[1] = arg_test_range[0];
+ }
+ else {
+ arg_test_range[0] = pow((double)TEST_RANGE, 0.333); /* cbrt */
+ arg_test_range[1] = arg_test_range[0];
+ arg_test_range[2] = arg_test_range[0];
+ }
+
+ /* Sanity check on the ranges */
+ if (arg_test_range[0] < 1)
+ arg_test_range[0] = 1;
+ if (arg_test_range[1] < 1)
+ arg_test_range[1] = 1;
+ if (arg_test_range[2] < 1)
+ arg_test_range[2] = 1;
+
+ /* Create a test set for each argument */
+ for (i = 0; i < args; i++) {
+ test_counts[i] = gen_vals(arg_test_vals[i],
+ t->arg_ranges[i][0], /* min */
+ t->arg_ranges[i][1], /* max */
+ arg_test_range[i],
+ i);
+
+ }
+
+ /* Handle timeouts in the test code */
+ if (timeout_limit > 0) {
+ int rc;
+ rc = sigsetjmp(envbuf, 1);
+ if (rc) {
+ /* control will reach here if there is a timeout */
+ errors = 1;
+ printf("ERROR: Test %s failed.\n Timed out after %d secs (probably infinite loop)\n", t->name, timeout_limit);
+ return errors;
+ }
+ alarm(timeout_limit);
+ }
+
+
+ /* Test function has no arguments */
+ if (args == 0) {
+ errors += test_0_arg(t->solution_funct, t->test_funct, t->name);
+ return errors;
+ }
+
+ /*
+ * Test function has at least one argument
+ */
+
+ /* Iterate over the values for first argument */
+
+ for (a1 = 0; a1 < test_counts[0]; a1++) {
+ if (args == 1) {
+ errors += test_1_arg(t->solution_funct,
+ t->test_funct,
+ arg_test_vals[0][a1],
+ t->name);
+
+ /* Stop testing if there is an error */
+ if (errors)
+ return errors;
+ }
+ else {
+ /* if necessary, iterate over values for second argument */
+ for (a2 = 0; a2 < test_counts[1]; a2++) {
+ if (args == 2) {
+ errors += test_2_arg(t->solution_funct,
+ t->test_funct,
+ arg_test_vals[0][a1],
+ arg_test_vals[1][a2],
+ t->name);
+
+ /* Stop testing if there is an error */
+ if (errors)
+ return errors;
+ }
+ else {
+ /* if necessary, iterate over vals for third arg */
+ for (a3 = 0; a3 < test_counts[2]; a3++) {
+ errors += test_3_arg(t->solution_funct,
+ t->test_funct,
+ arg_test_vals[0][a1],
+ arg_test_vals[1][a2],
+ arg_test_vals[2][a3],
+ t->name);
+
+ /* Stop testing if there is an error */
+ if (errors)
+ return errors;
+ } /* a3 */
+ }
+ } /* a2 */
+ }
+ } /* a1 */
+
+
+ return errors;
+}
+
+/*
+ * run_tests - Run series of tests. Return number of errors
+ */
+static int run_tests()
+{
+ int i;
+ int errors = 0;
+ double points = 0.0;
+ double max_points = 0.0;
+
+ printf("Score\tRating\tErrors\tFunction\n");
+
+ for (i = 0; test_set[i].solution_funct; i++) {
+ int terrors;
+ double tscore;
+ double tpoints;
+ if (!test_fname || strcmp(test_set[i].name,test_fname) == 0) {
+ int rating = global_rating ? global_rating : test_set[i].rating;
+ terrors = test_function(&test_set[i]);
+ errors += terrors;
+ tscore = terrors == 0 ? 1.0 : 0.0;
+ tpoints = rating * tscore;
+ points += tpoints;
+ max_points += rating;
+
+ if (grade || terrors < 1)
+ printf(" %.0f\t%d\t%d\t%s\n",
+ tpoints, rating, terrors, test_set[i].name);
+
+ }
+ }
+
+ printf("Total points: %.0f/%.0f\n", points, max_points);
+ return errors;
+}
+
+/*
+ * get_num_val - Extract hex/decimal/or float value from string
+ */
+static int get_num_val(char *sval, unsigned *valp) {
+ char *endp;
+
+ /* See if it's an integer or floating point */
+ int ishex = 0;
+ int isfloat = 0;
+ int i;
+ for (i = 0; sval[i]; i++) {
+ switch (sval[i]) {
+ case 'x':
+ case 'X':
+ ishex = 1;
+ break;
+ case 'e':
+ case 'E':
+ if (!ishex)
+ isfloat = 1;
+ break;
+ case '.':
+ isfloat = 1;
+ break;
+ default:
+ break;
+ }
+ }
+ if (isfloat) {
+ float fval = strtof(sval, &endp);
+ if (!*endp) {
+ *valp = *(unsigned *) &fval;
+ return 1;
+ }
+ return 0;
+ } else {
+ long long int llval = strtoll(sval, &endp, 0);
+ long long int upperbits = llval >> 31;
+ /* will give -1 for negative, 0 or 1 for positive */
+ if (!*valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) {
+ *valp = (unsigned) llval;
+ return 1;
+ }
+ return 0;
+ }
+}
+
+
+/*
+ * usage - Display usage info
+ */
+static void usage(char *cmd) {
+ printf("Usage: %s [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>]\n", cmd);
+ printf(" -1 <val> Specify first function argument\n");
+ printf(" -2 <val> Specify second function argument\n");
+ printf(" -3 <val> Specify third function argument\n");
+ printf(" -f <name> Test only the named function\n");
+ printf(" -g Compact output for grading (with no error msgs)\n");
+ printf(" -h Print this message\n");
+ printf(" -r <n> Give uniform weight of n for all problems\n");
+ printf(" -T <lim> Set timeout limit to lim\n");
+ exit(1);
+}
+
+
+/**************
+ * Main routine
+ **************/
+
+int main(int argc, char *argv[])
+{
+ char c;
+
+ /* parse command line args */
+ while ((c = getopt(argc, argv, "hgf:r:T:1:2:3:")) != -1)
+ switch (c) {
+ case 'h': /* help */
+ usage(argv[0]);
+ break;
+ case 'g': /* grading option for autograder */
+ grade = 1;
+ break;
+ case 'f': /* test only one function */
+ test_fname = strdup(optarg);
+ break;
+ case 'r': /* set global rating for each problem */
+ global_rating = atoi(optarg);
+ if (global_rating < 0)
+ usage(argv[0]);
+ break;
+ case '1': /* Get first argument */
+ has_arg[0] = get_num_val(optarg, &argval[0]);
+ if (!has_arg[0]) {
+ printf("Bad argument '%s'\n", optarg);
+ exit(0);
+ }
+ break;
+ case '2': /* Get first argument */
+ has_arg[1] = get_num_val(optarg, &argval[1]);
+ if (!has_arg[1]) {
+ printf("Bad argument '%s'\n", optarg);
+ exit(0);
+ }
+ break;
+ case '3': /* Get first argument */
+ has_arg[2] = get_num_val(optarg, &argval[2]);
+ if (!has_arg[2]) {
+ printf("Bad argument '%s'\n", optarg);
+ exit(0);
+ }
+ break;
+ case 'T': /* Set timeout limit */
+ timeout_limit = atoi(optarg);
+ break;
+ default:
+ usage(argv[0]);
+ }
+
+ if (timeout_limit > 0) {
+ Signal(SIGALRM, timeout_handler);
+ }
+
+ /* test each function */
+ run_tests();
+
+ return 0;
+}
diff --git a/lab1_datalab/btest.h b/lab1_datalab/btest.h
new file mode 100644
index 0000000..a011bc1
--- /dev/null
+++ b/lab1_datalab/btest.h
@@ -0,0 +1,32 @@
+/*
+ * CS:APP Data Lab
+ */
+
+/* Declare different function types */
+typedef int (*funct_t) (void);
+typedef int (*funct1_t)(int);
+typedef int (*funct2_t)(int, int);
+typedef int (*funct3_t)(int, int, int);
+
+/* Combine all the information about a function and its tests as structure */
+typedef struct {
+ char *name; /* String name */
+ funct_t solution_funct; /* Function */
+ funct_t test_funct; /* Test function */
+ int args; /* Number of function arguments */
+ char *ops; /* List of legal operators. Special case: "$" for floating point */
+ int op_limit; /* Max number of ops allowed in solution */
+ int rating; /* Problem rating (1 -- 4) */
+ int arg_ranges[3][2]; /* Argument ranges. Always defined for 3 args, even if */
+ /* the function takes fewer. Special case: First arg */
+ /* must be set to {1,1} for f.p. puzzles */
+} test_rec, *test_ptr;
+
+extern test_rec test_set[];
+
+
+
+
+
+
+
diff --git a/lab1_datalab/decl.c b/lab1_datalab/decl.c
new file mode 100644
index 0000000..b5c7d96
--- /dev/null
+++ b/lab1_datalab/decl.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+#define TMin INT_MIN
+#define TMax INT_MAX
+
+#include "btest.h"
+#include "bits.h"
+
+test_rec test_set[] = {
+/* Copyright (C) 1991-2022 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <https://www.gnu.org/licenses/>. */
+/* This header is separate from features.h so that the compiler can
+ include it implicitly at the start of every compilation. It must
+ not itself include <features.h> or any other header that includes
+ <features.h> because the implicit include comes before any feature
+ test macros that may be defined in a source file before it first
+ explicitly includes a system header. GCC knows the name of this
+ header in order to preinclude it. */
+/* glibc's intent is to support the IEC 559 math functionality, real
+ and complex. If the GCC (4.9 and later) predefined macros
+ specifying compiler intent are available, use them to determine
+ whether the overall intent is to support these features; otherwise,
+ presume an older compiler has intent to support these features and
+ define these macros by default. */
+/* wchar_t uses Unicode 10.0.0. Version 10.0 of the Unicode Standard is
+ synchronized with ISO/IEC 10646:2017, fifth edition, plus
+ the following additions from Amendment 1 to the fifth edition:
+ - 56 emoji characters
+ - 285 hentaigana
+ - 3 additional Zanabazar Square characters */
+ {"bitAnd", (funct_t) bitAnd, (funct_t) test_bitAnd, 2, "| ~", 8, 1,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"evenBits", (funct_t) evenBits, (funct_t) test_evenBits, 0,
+ "! ~ & ^ | + << >>", 8, 1,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"isTmin", (funct_t) isTmin, (funct_t) test_isTmin, 1, "! ~ & ^ | +", 10, 1,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"allEvenBits", (funct_t) allEvenBits, (funct_t) test_allEvenBits, 1,
+ "! ~ & ^ | + << >>", 12, 2,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"getByte", (funct_t) getByte, (funct_t) test_getByte, 2,
+ "! ~ & ^ | + << >>", 6, 2,
+ {{TMin, TMax},{0,3},{TMin,TMax}}},
+ {"isNegative", (funct_t) isNegative, (funct_t) test_isNegative, 1,
+ "! ~ & ^ | + << >>", 6, 2,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"conditional", (funct_t) conditional, (funct_t) test_conditional, 3, "! ~ & ^ | << >>", 16, 3,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"ezThreeFourths", (funct_t) ezThreeFourths, (funct_t) test_ezThreeFourths, 1,
+ "! ~ & ^ | + << >>", 12, 3,
+ {{TMin,TMax},{TMin,TMax},{TMin,TMax}}},
+ {"isNonNegative", (funct_t) isNonNegative, (funct_t) test_isNonNegative, 1,
+ "! ~ & ^ | + << >>", 6, 3,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"isNonZero", (funct_t) isNonZero, (funct_t) test_isNonZero, 1,
+ "~ & ^ | + << >>", 10, 4,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"leftBitCount", (funct_t) leftBitCount, (funct_t) test_leftBitCount, 1, "! ~ & ^ | + << >>", 40, 4,
+ {{TMin, TMax},{TMin,TMax},{TMin,TMax}}},
+ {"trueThreeFourths", (funct_t) trueThreeFourths, (funct_t) test_trueThreeFourths, 1,
+ "! ~ & ^ | + << >>", 20, 4,
+ {{TMin,TMax},{TMin,TMax},{TMin,TMax}}},
+/*
+ * Extra credit
+ */
+ {"float_abs", (funct_t) float_abs, (funct_t) test_float_abs, 1,
+ "$", 10, 2,
+ {{1, 1},{1,1},{1,1}}},
+ {"float_i2f", (funct_t) float_i2f, (funct_t) test_float_i2f, 1,
+ "$", 30, 4,
+ {{1, 1},{1,1},{1,1}}},
+ {"", NULL, NULL, 0, "", 0, 0,
+ {{0, 0},{0,0},{0,0}}}
+};
diff --git a/lab1_datalab/dlc b/lab1_datalab/dlc
new file mode 100755
index 0000000..1a5662b
--- /dev/null
+++ b/lab1_datalab/dlc
Binary files differ
diff --git a/lab1_datalab/driver.pl b/lab1_datalab/driver.pl
new file mode 100755
index 0000000..6c30d58
--- /dev/null
+++ b/lab1_datalab/driver.pl
@@ -0,0 +1,526 @@
+#!/usr/bin/perl
+#######################################################################
+# driver.pl - CS:APP Data Lab driver
+#
+# Copyright (c) 2004-2011, R. Bryant and D. O'Hallaron, All rights
+# reserved. May not be used, modified, or copied without permission.
+#
+# Note: The driver can use either btest or the BDD checker to check
+# puzzles for correctness. This version of the lab uses btest, which
+# has been extended to do better testing of both integer and
+# floating-point puzzles.
+#
+#######################################################################
+
+use strict 'vars';
+use Getopt::Std;
+
+use lib ".";
+use Driverlib;
+
+# Set to 1 to use btest, 0 to use the BDD checker.
+my $USE_BTEST = 0;
+
+# The number of problems to grade for "success"
+my $GRADE_HOWMANY = -1;
+
+my $DEBUG=0;
+sub System {
+ if ($DEBUG) {
+ print @_, "\n";
+ }
+ return system(@_);
+}
+
+# Generic settings
+$| = 1; # Flush stdout each time
+umask(0077); # Files created by the user in tmp readable only by that user
+$ENV{PATH} = "/usr/local/bin:/usr/bin:/bin";
+
+#
+# usage - print help message and terminate
+#
+sub usage {
+ printf STDERR "$_[0]\n";
+ printf STDERR "Usage: $0 [-h] [-u \"nickname\"]\n";
+ printf STDERR "Options:\n";
+ printf STDERR " -h Print this message.\n";
+ printf STDERR " -u \"nickname\" Send autoresult to server, using nickname on scoreboard)\n";
+ printf STDERR " -g N Script returns true / false if all problems up to #N are correct\n";
+ die "\n";
+}
+
+##############
+# Main routine
+##############
+my $login = getlogin() || (getpwuid($<))[0] || "unknown";
+my $tmpdir = "/var/tmp/datalab.$login.$$";
+my $diemsg = "The files are in $tmpdir.";
+
+my $driverfiles;
+my $infile;
+my $autograded;
+
+my $status;
+my $inpuzzles;
+my $puzzlecnt;
+my $line;
+my $blank;
+my $name;
+my $c_points;
+my $c_rating;
+my $c_errors;
+my $p_points;
+my $p_rating;
+my $p_errors;
+my $total_c_points;
+my $total_c_rating;
+my $total_p_points;
+my $total_p_rating;
+my $total_c_extra_points;
+my $total_c_extra_rating;
+my $total_p_extra_points;
+my $total_p_extra_rating;
+my $tops;
+my $tpoints;
+my $trating;
+my $tExtraPoints;
+my $tExtraRating;
+my $ExecutionGrade;
+my $ExecutionExtra;
+my $foo;
+my $name;
+my $msg;
+my $nickname;
+my $autoresult;
+
+my %puzzle_c_points;
+my %puzzle_c_rating;
+my %puzzle_c_errors;
+my %puzzle_p_points;
+my %puzzle_p_ops;
+my %puzzle_p_maxops;
+my %puzzle_number;
+
+
+# Parse the command line arguments
+no strict;
+getopts('hu:f:A:b:g:');
+if ($opt_h) {
+ usage();
+}
+if ($opt_b) {
+ print STDERR "Using complete BDD checker\n";
+ $USE_BTEST = 0;
+}
+
+# The default input file is bits.c (change with -f)
+$infile = "bits.c";
+$nickname = "";
+
+#####
+# These are command line args that every driver must support
+#
+
+# Causes the driver to send an autoresult to the server on behalf of user
+if ($opt_u) {
+ $nickname = $opt_u;
+ check_nickname($nickname);
+}
+
+# Hidden flag that indicates that the driver was invoked by an autograder
+if ($opt_A) {
+ $autograded = $opt_A;
+}
+
+#####
+# Drivers can also define an arbitary number of other command line args
+#
+# Optional hidden flag used by the autograder
+if ($opt_f) {
+ $infile = $opt_f;
+}
+
+if ($opt_g) {
+ $GRADE_HOWMANY = int($opt_g);
+ print("Grading $GRADE_HOWMANY\n");
+}
+
+use strict 'vars';
+
+################################################
+# Compute the correctness and performance scores
+################################################
+
+# Make sure that an executable dlc (data lab compiler) exists
+(-e "./dlc" and -x "./dlc")
+ or die "$0: ERROR: No executable dlc binary.\n";
+
+
+# If using the bdd checker, then make sure it exists
+if (!$USE_BTEST) {
+ (-e "./bddcheck/cbit/cbit" and -x "./bddcheck/cbit/cbit")
+ or die "$0: ERROR: No executable cbit binary.\n";
+}
+
+#
+# Set up the contents of the scratch directory
+#
+System("mkdir $tmpdir") == 0
+ or die "$0: Could not make scratch directory $tmpdir.\n";
+
+# Copy the student's work to the scratch directory
+unless (System("cp $infile $tmpdir/bits.c") == 0) {
+ clean($tmpdir);
+ die "$0: Could not copy file $infile to scratch directory $tmpdir.\n";
+}
+
+# Copy the student's work to the scratch directory
+unless (System("cp bits.h $tmpdir/bits.h") == 0) {
+ clean($tmpdir);
+ die "$0: Could not copy file bits.h to scratch directory $tmpdir.\n";
+}
+
+# Copy the various autograding files to the scratch directory
+if ($USE_BTEST) {
+ $driverfiles = "Makefile dlc btest.c decl.c tests.c btest.h bits.h";
+ unless (System("cp -r $driverfiles $tmpdir") == 0) {
+ clean($tmpdir);
+ die "$0: Could not copy autogradingfiles to $tmpdir.\n";
+ }
+}
+else {
+ $driverfiles = "dlc tests.c bits.h bddcheck";
+ unless (System("cp -r $driverfiles $tmpdir") == 0) {
+ clean($tmpdir);
+ die "$0: Could not copy support files to $tmpdir.\n";
+ }
+}
+
+# Change the current working directory to the scratch directory
+unless (chdir($tmpdir)) {
+ clean($tmpdir);
+ die "$0: Could not change directory to $tmpdir.\n";
+}
+
+#
+# Generate a zapped (for coding rules) version of bits.c. In this
+# zapped version of bits.c, any functions with illegal operators are
+# transformed to have empty function bodies.
+#
+print "1. Running './dlc -z' to identify coding rules violations.\n";
+System("cp bits.c save-bits.c") == 0
+ or die "$0: ERROR: Could not create backup copy of bits.c. $diemsg\n";
+System("cat bits.h save-bits.c > bits.c") == 0
+ or die "$0: ERROR: could not append function prototypes\n";
+System("./dlc -Zerror -il -z -o zap-bits.c bits.c") == 0
+ or die "$0: ERROR: zapped bits.c did not compile. $diemsg\n";
+System("cp save-bits.c bits.c") == 0
+ or die "$0: ERROR: could not recopy bits.c\n";
+System("./dlc -Zerror -il -z -o zap-bits.c bits.c") == 0
+ or die "$0: ERROR: zapped bits.c did not compile. $diemsg\n";
+
+
+#
+# Run btest or BDD checker to determine correctness score
+#
+if ($USE_BTEST) {
+ print "\n2. Compiling and running './btest -g' to determine correctness score.\n";
+ System("cp zap-bits.c bits.c");
+
+ # Compile btest
+ System("make btestexplicit") == 0
+ or die "$0: Could not make btest in $tmpdir. $diemsg\n";
+
+ # Run btest
+ $status = System("./btest -g > btest-zapped.out 2>&1");
+ if ($status != 0) {
+ die "$0: ERROR: btest check failed. $diemsg\n";
+ }
+}
+else {
+ print "\n2. Running './bddcheck/check.pl -g' to determine correctness score.\n";
+ System("cp zap-bits.c bits.c");
+ $status = System("./bddcheck/check.pl -g > btest-zapped.out 2>&1");
+ if ($status != 0) {
+ die "$0: ERROR: BDD check failed. $diemsg\n";
+ }
+}
+
+#
+# Run dlc to identify operator count violations.
+#
+print "\n3. Running './dlc -Z' to identify operator count violations.\n";
+System("./dlc -il -Z -o Zap-bits.c save-bits.c") == 0
+ or die "$0: ERROR: dlc unable to generated Zapped bits.c file.\n";
+
+#
+# Run btest or the bdd checker to compute performance score
+#
+if ($USE_BTEST) {
+ print "\n4. Compiling and running './btest -g -r 2' to determine performance score.\n";
+ System("cp Zap-bits.c bits.c");
+
+ # Compile btest
+ System("make btestexplicit") == 0
+ or die "$0: Could not make btest in $tmpdir. $diemsg\n";
+ print "\n";
+
+ # Run btest
+ $status = System("./btest -g -r 2 > btest-Zapped.out 2>&1");
+ if ($status != 0) {
+ die "$0: ERROR: Zapped btest failed. $diemsg\n";
+ }
+}
+else {
+ print "\n4. Running './bddcheck/check.pl -g -r 2' to determine performance score.\n";
+ System("cp Zap-bits.c bits.c");
+ $status = System("./bddcheck/check.pl -g -r 2 > btest-Zapped.out 2>&1");
+ if ($status != 0) {
+ die "$0: ERROR: Zapped bdd checker failed. $diemsg\n";
+ }
+}
+
+#
+# Run dlc to get the operator counts on the zapped input file
+#
+print "\n5. Running './dlc -e' to get operator count of each function.\n";
+$status = System("./dlc -W1 -il -e zap-bits.c > dlc-opcount.out 2>&1");
+if ($status != 0) {
+ die "$0: ERROR: bits.c did not compile. $diemsg\n";
+}
+
+#################################################################
+# Collect the correctness and performance results for each puzzle
+#################################################################
+
+#
+# Collect the correctness results
+#
+%puzzle_c_points = (); # Correctness score computed by btest
+%puzzle_c_errors = (); # Correctness error discovered by btest
+%puzzle_c_rating = (); # Correctness puzzle rating (max points)
+
+$inpuzzles = 0; # Becomes true when we start reading puzzle results
+$puzzlecnt = 0; # Each puzzle gets a unique number
+$total_c_points = 0;
+$total_c_rating = 0;
+$total_c_extra_points = 0;
+$total_c_extra_rating = 0;
+
+open(INFILE, "$tmpdir/btest-zapped.out")
+ or die "$0: ERROR: could not open input file $tmpdir/btest-zapped.out\n";
+
+while ($line = <INFILE>) {
+ chomp($line);
+
+ # Notice that we're ready to read the puzzle scores
+ if ($line =~ /^Score/) {
+ $inpuzzles = 1;
+ next;
+ }
+
+ # Notice that we're through reading the puzzle scores
+ if ($line =~ /^Total/) {
+ $inpuzzles = 0;
+ next;
+ }
+
+ # Read and record a puzzle's name and score
+ if ($inpuzzles) {
+ ($blank, $c_points, $c_rating, $c_errors, $name) = split(/\s+/, $line);
+ $puzzle_c_points{$name} = $c_points;
+ $puzzle_c_errors{$name} = $c_errors;
+ $puzzle_c_rating{$name} = $c_rating;
+ $puzzle_number{$name} = $puzzlecnt++;
+ if ($name =~ m/float.*/ ) {
+ $total_c_extra_points += $c_points;
+ $total_c_extra_rating += $c_rating;
+ }
+ else {
+ $total_c_points += $c_points;
+ $total_c_rating += $c_rating;
+ }
+ }
+
+}
+close(INFILE);
+
+#
+# Collect the performance results
+#
+%puzzle_p_points = (); # Performance points
+
+$inpuzzles = 0; # Becomes true when we start reading puzzle results
+$total_p_points = 0;
+$total_p_rating = 0;
+$total_p_extra_points = 0;
+$total_p_extra_rating = 0;
+
+open(INFILE, "$tmpdir/btest-Zapped.out")
+ or die "$0: ERROR: could not open input file $tmpdir/btest-Zapped.out\n";
+
+while ($line = <INFILE>) {
+ chomp($line);
+
+ # Notice that we're ready to read the puzzle scores
+ if ($line =~ /^Score/) {
+ $inpuzzles = 1;
+ next;
+ }
+
+ # Notice that we're through reading the puzzle scores
+ if ($line =~ /^Total/) {
+ $inpuzzles = 0;
+ next;
+ }
+
+ # Read and record a puzzle's name and score
+ if ($inpuzzles) {
+ ($blank, $p_points, $p_rating, $p_errors, $name) = split(/\s+/, $line);
+ $puzzle_p_points{$name} = $p_points;
+ if ($name =~ m/float.*/ ) {
+ $total_p_extra_points += $p_points;
+ $total_p_extra_rating += $p_rating;
+ }
+ else {
+ $total_p_points += $p_points;
+ $total_p_rating += $p_rating;
+ }
+ }
+}
+close(INFILE);
+
+#
+# Collect the operator counts generated by dlc
+#
+open(INFILE, "$tmpdir/dlc-opcount.out")
+ or die "$0: ERROR: could not open input file $tmpdir/dlc-opcount.out\n";
+
+$tops = 0;
+while ($line = <INFILE>) {
+ chomp($line);
+
+ if ($line =~ /(\d+) operators/) {
+ ($foo, $foo, $foo, $name, $msg) = split(/:/, $line);
+ $puzzle_p_ops{$name} = $1;
+ $tops += $1;
+ }
+}
+close(INFILE);
+
+#
+# Print a table of results sorted by puzzle number
+#
+print "\n";
+printf("%s\t%s\n", "Correctness Results", "Perf Results");
+printf("%s\t%s\t%s\t%s\t%s\t%s\n", "Points", "Rating", "Errors",
+ "Points", "Ops", "Puzzle");
+
+foreach $name (sort {$puzzle_number{$a} <=> $puzzle_number{$b}}
+ keys %puzzle_number) {
+ printf("%d\t%d\t%d\t%d\t%d\t\%s\n",
+ $puzzle_c_points{$name},
+ $puzzle_c_rating{$name},
+ $puzzle_c_errors{$name},
+ $puzzle_p_points{$name},
+ $puzzle_p_ops{$name},
+ $name);
+}
+
+$tpoints = $total_c_points + $total_p_points;
+$trating = $total_c_rating + $total_p_rating;
+$ExecutionGrade = 40 * $tpoints / $trating;
+
+$tExtraPoints = $total_c_extra_points + $total_p_extra_points;
+$tExtraRating = $total_c_extra_rating + $total_p_extra_rating;
+$ExecutionExtra = 4 * $tExtraPoints / $tExtraRating;
+
+print "\nGeneral Points = $tpoints/$trating [$total_c_points/$total_c_rating Corr + $total_p_points/$total_p_rating Perf]\n";
+print "Extra Points = $tExtraPoints/$tExtraRating [$total_c_extra_points/$total_c_extra_rating Corr + $total_p_extra_points/$total_p_extra_rating Perf]\n";
+
+print "\nConversion to 40% of DataLab grading (the remaining 60% will come from interview grading)\n";
+print "Execution Grade = $ExecutionGrade\n";
+print "Execution Extra = $ExecutionExtra\n";
+
+#
+# Check if we have grades all of the problems
+#
+if ( $GRADE_HOWMANY > 0 ) {
+ my $graded = 0;
+ my $got = 0;
+ my $possible = 0;
+ foreach $name (sort {$puzzle_number{$a} <=> $puzzle_number{$b}}
+ keys %puzzle_number) {
+ $got += $puzzle_c_points{$name};
+ $possible += $puzzle_c_rating{$name};
+ $graded++;
+ if ( $graded >= $GRADE_HOWMANY ) {
+ exit( $got < $possible );
+ }
+ }
+}
+
+#
+# Optionally send the autoresult to the contest server if the driver
+# was called with the -u command line flag.
+#
+if ($nickname) {
+ # Generate the autoresult
+ $autoresult = "$tpoints|$total_c_points|$total_p_points|$tops";
+ foreach $name (sort {$puzzle_number{$a} <=> $puzzle_number{$b}}
+ keys %puzzle_number) {
+ $autoresult .= " |$name:$puzzle_c_points{$name}:$puzzle_c_rating{$name}:$puzzle_p_points{$name}:$puzzle_p_ops{$name}";
+ }
+
+ # Post the autoresult to the server. The Linux login id is
+ # concatenated with the user-supplied nickname for some (very) loose
+ # authentication of submissions.
+ &Driverlib::driver_post("$login:$nickname", $autoresult, $autograded);
+}
+
+# Clean up and exit
+clean ($tmpdir);
+exit;
+
+##################
+# Helper functions
+#
+
+#
+# check_nickname - Check a nickname for legality
+#
+sub check_nickname {
+ my $nickname = shift;
+
+ # Nicknames can't be empty
+ if (length($nickname) < 1) {
+ die "$0: Error: Empty nickname.\n";
+ }
+
+ # Nicknames can't be too long
+ if (length($nickname) > 35) {
+ die "$0: Error: Nickname exceeds 35 characters.\n";
+ }
+
+ # Nicknames can have restricted set of metacharacters (e.g., no #
+ # HTML tags)
+ if (!($nickname =~ /^[_-\w.,'@ ]+$/)) {
+ die "$0: Error: Illegal character in nickname. Only alphanumerics, apostrophes, commas, periods, dashes, underscores, and ampersands are allowed.\n";
+ }
+
+ # Nicknames can't be all whitespace
+ if ($nickname =~ /^\s*$/) {
+ die "$0: Error: Nickname is all whitespace.\n";
+ }
+
+}
+
+#
+# clean - remove the scratch directory
+#
+sub clean {
+ my $tmpdir = shift;
+ System("rm -rf $tmpdir");
+}
+
diff --git a/lab1_datalab/fshow.c b/lab1_datalab/fshow.c
new file mode 100644
index 0000000..fc918f6
--- /dev/null
+++ b/lab1_datalab/fshow.c
@@ -0,0 +1,151 @@
+/* Display structure of floating-point numbers */
+
+#include <stdio.h>
+#include <stdlib.h>
+float strtof(const char *nptr, char **endptr);
+
+#define FLOAT_SIZE 32
+#define FRAC_SIZE 23
+#define EXP_SIZE 8
+#define BIAS ((1<<(EXP_SIZE-1))-1)
+#define FRAC_MASK ((1<<FRAC_SIZE)-1)
+#define EXP_MASK ((1<<EXP_SIZE)-1)
+
+/* Floating point helpers */
+unsigned f2u(float f)
+{
+ union {
+ unsigned u;
+ float f;
+ } v;
+ v.u = 0;
+ v.f = f;
+ return v.u;
+}
+
+static float u2f(unsigned u)
+{
+ union {
+ unsigned u;
+ float f;
+ } v;
+ v.u = u;
+ return v.f;
+}
+
+/* Get exponent */
+unsigned get_exp(unsigned uf)
+{
+ return (uf>>FRAC_SIZE) & EXP_MASK;
+}
+
+/* Get fraction */
+unsigned get_frac(unsigned uf)
+{
+ return uf & FRAC_MASK;
+}
+
+/* Get sign */
+unsigned get_sign(unsigned uf)
+{
+ return (uf>>(FLOAT_SIZE-1)) & 0x1;
+}
+
+void show_float(unsigned uf)
+{
+ float f = u2f(uf);
+ unsigned exp = get_exp(uf);
+ unsigned frac = get_frac(uf);
+ unsigned sign = get_sign(uf);
+
+ printf("\nFloating point value %.10g\n", f);
+ printf("Bit Representation 0x%.8x, sign = %x, exponent = 0x%.2x, fraction = 0x%.6x\n",
+ uf, sign, exp, frac);
+ if (exp == EXP_MASK) {
+ if (frac == 0) {
+ printf("%cInfinity\n", sign ? '-' : '+');
+ } else
+ printf("Not-A-Number\n");
+ } else {
+ int denorm = (exp == 0);
+ int uexp = denorm ? 1-BIAS : exp - BIAS;
+ int mantissa = denorm ? frac : frac + (1<<FRAC_SIZE);
+ float fman = (float) mantissa / (float) (1<<FRAC_SIZE);
+ printf("%s. %c%.10f X 2^(%d)\n",
+ denorm ? "Denormalized" : "Normalized",
+ sign ? '-' : '+',
+ fman, uexp);
+ }
+}
+
+/* Extract hex/decimal/or float value from string */
+static int get_num_val(char *sval, unsigned *valp) {
+ char *endp;
+ /* See if it's an integer or floating point */
+ int ishex = 0;
+ int isfloat = 0;
+ int i;
+ for (i = 0; sval[i]; i++) {
+ switch (sval[i]) {
+ case 'x':
+ case 'X':
+ ishex = 1;
+ break;
+ case 'e':
+ case 'E':
+ if (!ishex)
+ isfloat = 1;
+ break;
+ case '.':
+ isfloat = 1;
+ break;
+ default:
+ break;
+ }
+ }
+ if (isfloat) {
+ float fval = strtof(sval, &endp);
+ if (!*endp) {
+ *valp = *(unsigned *) &fval;
+ return 1;
+ }
+ return 0;
+ } else {
+ long long int llval = strtoll(sval, &endp, 0);
+ long long int upperbits = llval >> 31;
+ /* will give -1 for negative, 0 or 1 for positive */
+ if (valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) {
+ *valp = (unsigned) llval;
+ return 1;
+ }
+ return 0;
+ }
+}
+
+
+void usage(char *fname) {
+ printf("Usage: %s val1 val2 ...\n", fname);
+ printf("Values may be given as hex patterns or as floating point numbers\n");
+ exit(0);
+}
+
+
+int main(int argc, char *argv[])
+{
+ int i;
+ unsigned uf;
+ if (argc < 2)
+ usage(argv[0]);
+ for (i = 1; i < argc; i++) {
+ char *sval = argv[i];
+ if (get_num_val(sval, &uf)) {
+ show_float(uf);
+ } else {
+ printf("Invalid 32-bit number: '%s'\n", sval);
+ usage(argv[0]);
+ }
+ }
+ return 0;
+}
+
+
diff --git a/lab1_datalab/ishow.c b/lab1_datalab/ishow.c
new file mode 100644
index 0000000..ffb1df7
--- /dev/null
+++ b/lab1_datalab/ishow.c
@@ -0,0 +1,75 @@
+/* Display value of fixed point numbers */
+#include <stdlib.h>
+#include <stdio.h>
+
+/* Extract hex/decimal/or float value from string */
+static int get_num_val(char *sval, unsigned *valp) {
+ char *endp;
+ /* See if it's an integer or floating point */
+ int ishex = 0;
+ int isfloat = 0;
+ int i;
+ for (i = 0; sval[i]; i++) {
+ switch (sval[i]) {
+ case 'x':
+ case 'X':
+ ishex = 1;
+ break;
+ case 'e':
+ case 'E':
+ if (!ishex)
+ isfloat = 1;
+ break;
+ case '.':
+ isfloat = 1;
+ break;
+ default:
+ break;
+ }
+ }
+ if (isfloat) {
+ return 0; /* Not supposed to have a float here */
+ } else {
+ long long int llval = strtoll(sval, &endp, 0);
+ long long int upperbits = llval >> 31;
+ /* will give -1 for negative, 0 or 1 for positive */
+ if (valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) {
+ *valp = (unsigned) llval;
+ return 1;
+ }
+ return 0;
+ }
+}
+
+void show_int(unsigned uf)
+{
+ printf("Hex = 0x%.8x,\tSigned = %d,\tUnsigned = %u\n",
+ uf, (int) uf, uf);
+}
+
+
+void usage(char *fname) {
+ printf("Usage: %s val1 val2 ...\n", fname);
+ printf("Values may be given in hex or decimal\n");
+ exit(0);
+}
+
+int main(int argc, char *argv[])
+{
+ int i;
+ unsigned uf;
+ if (argc < 2)
+ usage(argv[0]);
+ for (i = 1; i < argc; i++) {
+ char *sval = argv[i];
+ if (get_num_val(sval, &uf)) {
+ show_int(uf);
+ } else {
+ printf("Cannot convert '%s' to 32-bit number\n", sval);
+ }
+ }
+ return 0;
+}
+
+
+
diff --git a/lab1_datalab/tests.c b/lab1_datalab/tests.c
new file mode 100644
index 0000000..93e95d6
--- /dev/null
+++ b/lab1_datalab/tests.c
@@ -0,0 +1,153 @@
+/* Testing Code */
+
+#include <limits.h>
+#include <math.h>
+
+/* Routines used by floation point test code */
+
+/* Convert from bit level representation to floating point number */
+float u2f(unsigned u) {
+ union {
+ unsigned u;
+ float f;
+ } a;
+ a.u = u;
+ return a.f;
+}
+
+/* Convert from floating point number to bit-level representation */
+unsigned f2u(float f) {
+ union {
+ unsigned u;
+ float f;
+ } a;
+ a.f = f;
+ return a.u;
+}
+
+/* Copyright (C) 1991-2022 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <https://www.gnu.org/licenses/>. */
+/* This header is separate from features.h so that the compiler can
+ include it implicitly at the start of every compilation. It must
+ not itself include <features.h> or any other header that includes
+ <features.h> because the implicit include comes before any feature
+ test macros that may be defined in a source file before it first
+ explicitly includes a system header. GCC knows the name of this
+ header in order to preinclude it. */
+/* glibc's intent is to support the IEC 559 math functionality, real
+ and complex. If the GCC (4.9 and later) predefined macros
+ specifying compiler intent are available, use them to determine
+ whether the overall intent is to support these features; otherwise,
+ presume an older compiler has intent to support these features and
+ define these macros by default. */
+/* wchar_t uses Unicode 10.0.0. Version 10.0 of the Unicode Standard is
+ synchronized with ISO/IEC 10646:2017, fifth edition, plus
+ the following additions from Amendment 1 to the fifth edition:
+ - 56 emoji characters
+ - 285 hentaigana
+ - 3 additional Zanabazar Square characters */
+int test_bitAnd(int x, int y)
+{
+ return x&y;
+}
+int test_evenBits(void) {
+ int result = 0;
+ int i;
+ for (i = 0; i < 32; i+=2)
+ result |= 1<<i;
+ return result;
+}
+int test_isTmin(int x) {
+ return x == 0x80000000;
+}
+int test_allEvenBits(int x) {
+ int i;
+ for (i = 0; i < 32; i+=2)
+ if ((x & (1<<i)) == 0)
+ return 0;
+ return 1;
+}
+int test_getByte(int x, int n)
+{
+ unsigned char byte;
+ switch(n) {
+ case 0:
+ byte = x;
+ break;
+ case 1:
+ byte = x >> 8;
+ break;
+ case 2:
+ byte = x >> 16;
+ break;
+ default:
+ byte = x >> 24;
+ break;
+ }
+ return (int) (unsigned) byte;
+}
+int test_isNegative(int x) {
+ return x < 0;
+}
+int test_conditional(int x, int y, int z)
+{
+ return x?y:z;
+}
+int test_ezThreeFourths(int x)
+{
+ return (x*3)/4;
+}
+int test_isNonNegative(int x) {
+ return x >= 0;
+}
+int test_isNonZero(int x)
+{
+ return x!=0;
+}
+int test_leftBitCount(int x) {
+ int result = 0;
+ int i;
+ for (i = 31; i >= 0; i--) {
+ int bit = (x >> i) & 0x1;
+ if (!bit)
+ break;
+ result ++;
+ }
+ return result;
+}
+int test_trueThreeFourths(int x)
+{
+ return (int) (((long long int) x * 3)/4);
+}
+/*
+ * Extra credit
+ */
+unsigned test_float_abs(unsigned uf) {
+ float f = u2f(uf);
+ unsigned unf = f2u(-f);
+ if (isnan(f))
+ return uf;
+ /* An unfortunate hack to get around a limitation of the BDD Checker */
+ if ((int) uf < 0)
+ return unf;
+ else
+ return uf;
+}
+unsigned test_float_i2f(int x) {
+ float f = (float) x;
+ return f2u(f);
+}