15 213 18 243 Fall 2010 Lab Assignment L1 Manipulating Bits Assigned Aug 24 Due Tuesday Sept 7 11 59PM Last Possible Time to Turn in Friday Sept 10 11 59PM Important There is a lot of information in this handout Be sure to study it carefully and to reread it when you have questions before asking for help from one of the course staff Please contact the 15 213 staff list 15 213 staff cs cmu edu for questions about assignment 1 Introduction The purpose of this assignment is to become more familiar with bit level representations of common patterns integers and floating point numbers You ll do this by solving a series of programming puzzles Many of these puzzles are quite artificial but you ll find yourself thinking much more about bits in working your way through them 1 1 Logistics This is an individual project All handins are electronic Clarifications and corrections will be posted on the Autolab message board 1 2 Logging in to Autolab All 15 213 labs are being offered this term through a Web service developed by Hunter Pitelka and Prof David O Hallaron called Autolab Before you can download your lab materials you will need to update your Autolab account Point your browser at the Autolab front page http autolab cs cmu edu You will be asked to authenticate via WebISO After you authenticate this first time Autolab will prompt you to update your account information with a nickname Your nickname is the external name that identifies you on the public scoreboards that Autolab maintains for each assignment so pick something interesting 1 You can change your nickname as often as you like Once you have updated your account information click on Edit and then select the Home link to proceed to the main Autolab page If you added the class late you might not be included in Autolab s list of valid students In this case you won t see the 15 213 18 243 course listed on your Autolab home page If this happens just send email to the staff mailing list 15 213 staff cs cmu edu requesting an Autolab account and we will add you to the list 1 3 Obtaining your Lab Materials Your lab materials are contained in a Unix tar file called datalab handout tar which you can download from Autolab After logging in to Autolab at http autolab cs cmu edu you can retrieve the datalab handout tar file by selecting Datalab Download Lab Materials and then hitting the Save File button Start by copying datalab handout tar to a directory in which you plan to do your work Then give the command tar xvf datalab handout tar This will create a directory called datalab handout that contains a number of files The only file you will be modifying and handing in is bits c WARNING Do not let the Windows WinZip program open up your tar file many Web browsers are set to do this automatically Instead save the file to your AFS directory and use the Linux tar program to extract the files In general for this class you should NEVER use any platform other than Linux to modify your files doing so can cause loss of data and important work The file btest c contains code that performs a simple non exhaustive check of the functional correctness of your code The file README contains additional documentation about BTEST Use the command make to generate the test code and run it with the command btest The included program DLC can be used to check your solutions for compliance with the coding rules The included programs ISHOW and FSHOW can be used to help examine the bit representations of integer and floating point numbers The files in the subdirectory bddcheck implement the BDD checker a tool that formally verifies your code The file driver pl is the main driver program that uses DLC and the BDD checker to check your bits c for correctness grades your submission and optionally streams the results to the Autolab server for inclusion on the Autolab scoreboard You can run the driver as often as like you to check your work The remaining files are used to build the program BTEST 1 4 Your Assignment The bits c file contains a skeleton for each of the 13 programming puzzles Your assignment is to complete each function skeleton according to a strict set of programming rules intended to help you understand how values are represented at the bit level and how to manipulate bit patterns using standard C operations 2 2 Evaluation Your code will be compiled with GCC and exhaustively tested with the BDD checker Your score will be computed out of a maximum of 66 points based on the following distribution 35 Correctness of code 26 Performance of code based on number of operators used in each function 5 Style points based on your instructor s subjective evaluation of the quality of your solutions and your comments The 13 puzzles you must solve have been given a difficulty rating between 1 and 4 such that their weighted sum totals to 35 The code in BTEST simply tests your functions for a number of different cases For most functions the number of possible argument combinations far exceeds what could be tested exhaustively To provide complete coverage we have created an experimental formal verification program CBIT that in effect tests your functions for all possible combinations of arguments It does this by viewing each bit of the function result as a Boolean function of the bits comprising the function arguments It uses a data structure known as Binary Decision Diagrams BDDs R E Bryant IEEE Transactions on Computers August 1986 to represent these Boolean functions in a way such that the program can efficiently compare the results of your functions with those of a set of reference solutions If the bit level functions match then the two C functions compute identical results Otherwise CBIT can generate a counterexample i e a set of function arguments where your function will produce a different result than the reference solution You do not invoke it Execute CBIT directly Instead there is a series of Perl scripts that set up and evaluate the calls to unix bddcheck check pl f fun to check function fun Execute unix bddcheck check pl to check all of your functions Note The Perl scripts are a bit picky about the formatting of your code They expect the function to open with a line of the form int fun or unsigned fun 3 and to end with a single right brace in the leftmost column That should be the only right brace in the leftmost column of your function You will get full credit for a puzzle if the BDD checker determines that your solution is correct and no credit otherwise The
View Full Document
Unlocking...