The purpose of this assignment is for you to become more familiar with bit-level representations of integers and floating point numbers and how to manipulate them using bit-level operations. Youll do this by solving a series of programming puzzles. Many of these puzzles are quite artificial, but youll find yourself thinking much more about bit level representations and manipulations in working your way through them. Some of them are relatively easy. Some of them are really hard. 2 Logistics This is an individual project. Like everything else this term all submissions are electronic. Clarifications and corrections will be posted on the course web pages if needed. You dont really do anything to submit your solution other than copying it the a properly named file. In order to submit your work you should copy your bits.c file to a file named your-login-id-bits.c substituting your actual login id for your-login-id. Also put a C style comment at the top of your file with your name just to be doubly sure your file is distinguishable as yours. A command such as the following will do the trick cp bits.c whoami-bits.c Note that the 1 character is on your keyboard on the top row left-most key to the left of the 1 key. The Unix incantation whoami means run the whoami command and take the output of that command and stick those characters here like I typed them in. The result is to take your login id and attach it to the front of the character string -bits.c to build up the file name you want for the destination of the copy command. In UNIX we often use the output of commands to build up parts of the text of the actual command we want for us. The more modern way to accomplish this in the bash shell is to use the form cp bits.c $(whoami)-bits.c where putting something inside the parentheses after the dollar sign means run the command inside the parentheses and put the text of its output here. Regardless of how you choose to do it, remember to copy the bits.c file to one with your login id at the beginning of the file name so that it will be picked up by the script that runs on scofield to collect everyones work at the deadline. To make things as simple as possible I have provided a script you can run on scofield that will place your work into a properly named file. The script command is named handinp1. Here is the contents of the handinp1 script file. #!/bin/bash cp /home/$(whoami)/projects/1/bits.c /home/$(whoami)/projects/1/$(whoami)-bits.c Very Important READ THIS You must perform all your work on your bits.c file. The handinp1 script will make a copy of that file with the properly constructed name. While working though the puzzles ALWAYS WORK ON YOUR bits.c file NEVER directly on the your-login-id-bits.c file used to submit your work. This is because you should only copy it over to the your-login-id-bits.c file once you have determined it has passed all the tests using the dlc, btest, and driver.pl tools described below. Work on a puzzle in bits.c and when you have something new solved and it passes all the tests then copy it over to the your-login-id-bits.c file. After every new thing you solve go ahead and copy it over to the your-login-id-bits.c file so that it will always have everything you have accomplished up to that point, however, NEVER copy a broken bits.c that wont compile with dlc without errors. If the reaper script that collects all the files when the project is due picks up your your-login-id-bits.c and it wont compile with dlc without errors you wont get credit for anything. 3 Instructions Since we are doing all our work on scofield where I have root permission available I am able to put together a shell script to simply place all the files you will need for your projects into your home directory on scofield for you. In other words, there is nothing you need to download to work on your projects, everything will just appear in the projects/1 directory under your home directory for you all ready to work on it. My script that distributes your first project places all the files you will need in your projects/1 directory on scofield. This is where you must perform all your work on the project. How to get no credit for your work 2 Fail to copy your bits.c file to your-login-id-bits.c. The reaper script isnt clairvoyant, it looks for a file with a specific name in a specific place. Put something in your-login-id-bits.c that wont compile with the dlc compiler without errors. The auto-grader cant run tests against you code to see what you got right and wrong if it cant even build an executable to test because your program wont even compile. Put something in your-login-id-bits.c that doesnt pass the btest check program. Put your your-login-id-bits.c somewhere other than the /projects/1. If you dont put the file where the reaper script is looking to find it you havent submitted anything. Your bits.c file The bits.c file provided for you contains a skeleton function for each of the programming puzzles you will be solving. Your assignment is to complete each function skeleton using only straightline code for the integer puzzles (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators: ! & | + << >> Some of the functions in bits.c further restrict this list so pay attention to the comments in each individual function indicating which operators are allowed to solve that puzzle. Also, you are NOT allowed to use any constants longer than 8 bits. In other words, no decimal constants bigger than 255. See the comments at the beginning of the bits.c file for detailed rules and a discussion of the desired coding style. 4 The Puzzles This section describes the puzzles that you will be solving in bits.c. 4.1 Bit Manipulations The following table describes the functions that you are to implement. 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. See the comments in bits.c for details on the desired behavior of each functions. The comments describe what the function is to accomplish using the restricted set of operations allowed. The IEEE standard does not specify a single specific value for NaNs, 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 the exact bit representation 0x7FC00000. In the command examples below unix> represents the prompt that the shell prints and is not part of the command you enter. I have provided a program on scofield fshow that helps you understand the structure of floating point numbers. It is already on your PATH and you can run it by just typing fshow. You can use fshow to see what an arbitrary pattern represents as a floating-point number: 3 Name Rating Max Ops w2301 2 2 w2302 4 5 w2303 3 14 w2304 3 14 w2305 2 2 w2306 3 9 w2307 1 4 w2308 2 4 w2309 4 16 w2310 4 48 w2311 2 3 w2312 2 6 w2313 4 16 w2314 2 8 w2315 2 6 w2316 3 13 w2317 3 3 Table 1: Puzzle Functions. unix> ./fshow 2080374784 Floating point value 2.658455992e+36 Bit Representation 0x7c000000, sign = 0, exponent = f8, fraction = 000000 Normalized. 1.0000000000 X 2(121) You can also give fshow hexadecimal and floating point values, and it will decipher their bit structure. 5 Evaluation Your score will be computed out of a maximum of 80 points based on the following distribution: 46 Correctness points. 34 Performance points. Correctness points. The puzzles you must solve have been given a difficulty rating between 1 and 4, such that their weighted sum totals to 46. I will evaluate your functions using the btest program, which is described in the next section. You will get full correctness points credit for a puzzle if it passes all of the tests performed by btest, and no credit otherwise. Performance points. Our main concern at this point in the course is that you can get the right answer. However, we want to instill in you a sense of keeping things as short and simple as you can. Furthermore, some of the puzzles can be solved by brute force, but we want you to be more clever. Thus, for each function 4 weve established a maximum number of operators that you are allowed to use for each function. This limit is very generous and is designed only to catch egregiously inefficient solutions. You will receive two points for each correct function that satisfies the operator limit. Autograding your work I have included some auto-grading tools in your projects/1 directory btest, dlc, and driver.pl to help you check the correctness of your work. 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 with the make command each time you modify your bits.c file. Youll 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 functionName You can feed it specific function arguments using the option flags -1, -2, and -3: This is useful to manually test some parameter edge case values where bugs often hide. unix> ./btest -f FunctionName -1 7 -2 0xf Check the file README file for documentation on running the btest program. Note that when you run the make to rebuild the btest program you will get a warning message from the compiler as follows: gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c btest.c: In function test_function: btest.c:332:23: warning: arg_test_range[1] may be used uninitialized in this332 | if (arg_test_range[1] < 1) | Just ignore this warning. dlc: This is a specially modified version of an ANSI C compiler using tools from the MIT CILK group I have set up in such a way that you can use it to check for compliance with the coding rules for each puzzle. This compiler has been created specifically for use in this assignment so that it knows how to enforce the coding rules for each function you are working on. The typical usage is: 5 unix> ./dlc bits.c The program runs silently unless it detects a problem, such as an illegal operator, too many operators, or non-straight-line code in the integer puzzles. Running with the -e switch: unix> ./dlc -e bits.c causes dlc to print counts of the number of operators used by each function. Type ./dlc -help for a list of command line options. The dlc program is a specially modified C compiler that knows about the names of the functions you are implementing and knows what operators are allowed to be used in each of them and how many total operators can be used in these functions. In other words, this is a special C compiler that has been generated to check that your solutions conform to the coding rules for the assignment. You can, if you wish, develop your work using the gcc compiler but to test that your solutions conforms to the coding conventions you should run the dlc compiler. When your work is graded we will run dlc. If your work doesnt pass dlc you get no points. So always run dlc to make sure you have not violated the coding restrictions before using handinp1 to move your work to the file that will be graded. Never put a broken bits.c file into the your-login-id-bits.c file. driver.pl: This is a driver program written in the Perl programming language that uses btest and dlc to compute the correctness and performance points for your solution. It takes no arguments: unix> ./driver.pl I will use a version of driver.pl similar to the one I gave you to evaluate your solutions and generate your scores. 6 Instructions for Submitting You Work At the specified due date and time a job will execute on scofield to copy your solutions from your projects/1 directory and save it to my file space so I can run a grading program against all the solutions for the class. In order to hand in your solutions the only thing you need to do is copy the bits.c file to your-login-name-bits.c in your projects/1 directory. You can copy your bits.c file to your-login-id-bits.c as often as you want to save your current solutions but when the due date and time arrive whatever you have in the file your-login-id-bits.c in your project1 directory is what is going to be graded. You can also use the handinp1 command to copy your bits.c file to a file with the properly formed name for handing in. Always perform your work on your bits.c file and only copy it to the handin file if it will pass the dlc checks. Never work directly in the handin file. 7 Advice In normal C programming we teach you to always include the header file if you want to use the printf function. For our purposes in this assignment since we are using a specially modified 6 C compiler to check your compliance with the coding restrictions for each puzzle you should NOT include the header file in your bits.c file, as it confuses dlc and results in some nonintuitive error messages. You will still be able to use printf in your bits.c file for debugging without including the header, although gcc will print a warning that you can simply ignore. READ THIS! Another difference from normal C programming is that the dlc compiler enforces a stricter form of C declarations than is the case for C or C++ or that is enforced by gcc. In particular, any declaration must appear in a block (what you enclose in curly braces) BEFORE any statement that is not a declaration. This is similar to the rules in the language Pascal. All declarations must precede any executable statement. 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 */ } This should have been coded as follows putting all the declarations BEFORE any executable statements. int foo(int x) { int a; int b; a = x; a *= 3; b = a; }