CSC373 Lab Assignment 1: Manipulating Bits

Contact your instructor, Glenn Lancaster (glancast@cs.depaul.edu), for questions/advice for this assignment.

Also check the Piazza discussion forum.

Introduction

The purpose of this assignment is to become more familiar with bit-level representations and manipulations. 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.

Logistics

You may work in a group of up to two people in solving the problems for this assignment. The only "hand-in" will be electronic. Any clarifications and revisions to the assignment will be posted on the course Web page.

Hand Out Instructions

Start by copying datalab-handout.tar to a (protected) directory in which you plan to do your work. (Create a subdirectory of your login directory for lab1.)

On the CDM Linux machine, to copy the datalab-handout.tar file to your directory, change to that directory (using the cd command) and type 

	cp ~glancast/373class/datalab-handout.tar .

Important: Don't forget to type the space and last "." to indicate the target directory where the file will be copied. The name "." is an alias for your current directory, whatever that happens to be at any given time.

Or on your own Linux machine, open a terminal window, change to a directory where you want the tar file and copy the datalab-handout.tar file from the class web site using wget: 


	wget http://condor.depaul.edu/~glancast/373class/docs/datalab-handout.tar

Then give the command: 

	tar xvf datalab-handout.tar

This will cause a number of files (listed below) to be unpacked in the directory. The only file you will be modifying and turning in is bits.c. 

        File       Size 
        ----       ----
        bits.c     7594 
        bits.h      698 
        btest.c    9712 
        btest.h     936 
        decl.c     2197 
        dlc      759594 
        Makefile    342 
        README     2246 
        tests.c    1414

The file btest.c allows you to evaluate the functional correctness of your code. The file README contains additional documentation about btest. Use the command

	make btest

or just

        make

to compile the test code initially and each time you modify the bits.c file.

You can run btest to test one or all the 15 functions. For example, if you have written the code for the bitAnd function, you can test it by:

	btest -f bitAnd

The btest function will call bitAnd multiple times and check the results each time. For each call that gives incorrect values, btest notes an error. By default btest will print each error giving the parameters the expected value and the (incorrect) value your function calculated. You can limit the maximum number of such errors that are printed with an -e option. For example, to limit the number of errors printed to be 5: 

	btest -f bitAnd -e 5

The file dlc is a compiler binary that you can use to check your solutions for compliance with the coding rules. The remaining files are used to build btest.

Looking at the file bits.c you'll notice a C structure team into which you should insert the requested identifying information about the one or two individuals comprising your programming team. Do this right away so you don't forget. For example, if Tristram Shandy and Ralph Roysterdoyster are a team with login id's tshandy and rroyster, the team struct in bits.c should be filled in like this: 

team_struct team =
{
   /* Team name: Replace with either:
      Your login ID if working as a one person team
      or, ID1+ID2 where ID1 is the login ID of the first team member
      and ID2 is the login ID of the second team member */
    "tshandy+rroyster", 
   /* Student name 1: Replace with the full name of first team member */
   "Tristram Shandy",
   /* Login ID 1: Replace with the login ID of first team member */
   "tshandy",

   /* The following should only be changed if there are two team members */
   /* Student name 2: Full name of the second team member */
   "Ralph Roysterdoyster",
   /* Login ID 2: Login ID of the second team member */
   "rroyster"
};

The bits.c file also contains a skeleton for each of the 15 programming puzzles. Your assignment is to complete each function skeleton using only straightline code (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 further restrict this list. Also, you are not allowed to use any constants longer than 8 bits. See the comments in bits.c for detailed rules and a discussion of the desired coding style.

Evaluation

Your code will be compiled with the gcc compiler, run and tested in Linux (on the class Linux machine). Each of the 15 functions is worth a maximum 7 points for a total of 105 points.

To earn the 7 points, your function must evaluate correctly on all the test parameters passed by btest. In addition, you must follow the coding rules (straight line code, no constants bigger than 1 byte in your code, etc.)

The 15 puzzles you must solve have been given a difficulty rating between 1 and 4. This is somewhat subjective, but should give you an idea of which ones might be easier or harder to solve. Note that the difficulty rating doesn't affect the score you earn. All functions are worth 7 points. You can check your total score by:

	btest -r 7 -g

Assuming I have only worked on two of the functions (bang and abs, this might generate the following output:

  Team: glancast
  Member 1:       Glenn Lancaster glancast

  Score   Errors  Function
   0.0    382     bitAnd
   0.0    1       tmax
   0.0    390     bitXor
   0.0    20      copyLSB
   0.0    640     fitsBits
   0.0    78      getByte
   0.0    400     isNotEqual
   0.0    19      negate
   0.0    400     addOK
   0.0    614     logicalShift
   0.0    20      isNonNegative
   0.0    20      isPositive
   0.0    20      reverseBytes
   7.0    0       bang
   7.0    0       abs
  Total points: 14.00/105.00

You will get full credit for a puzzle if it passes all of the tests performed by btest.c, half credit if it fails one test, and no credit otherwise.

Regarding performance, the main concern at this point in the course is that you can get the right answer. However, this assignment challenges you to develop a sense of keeping things as short and simple as you can. Furthermore, some of the puzzles can be solved by brute force, but you are encouraged to be more clever. Thus, for each function we've 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 one additional point for each function that satisfies the operator limit.

The dlc program will check your bits.c file and report the number of operators used for each function if that number exceeds the maximum allowed. If none of your functions exceed the maximum, dlc runs silently with no report.

Run the dlc program to check your bits.c file like this:


	dlc bits.c

Bit manipulations

Unless otherwise restricted further, each function is only allowed to use assignment and these 8 operators:


	! ~ & ^ | + << >>
Name Description Rating Max Ops
bitAnd(int x, int y) x & y using only ~ and | 1 8
tmax() return maximum two's complement integer 1 4
bitXor(int x, int y) x^y using only ~ and & 2 14
copyLSB(int x) set all bits of result to least significant bit of x 2 5
fitsBits(int x, int n) return 1 if x can be represented as an n-bit, two's complement integer. 2 15
getByte(int x, int n) Extract byte n from word x (n = 0, 1, 2, or 3) 2 6
isNotEqual(int x, int y) return 0 if x == y, and 1 otherwise 2 6
negate(int x) return -x 2 5
addOK(int x, int y) Determine if can compute x+y without overflow 3 20
logicalShift(int x, int n) shift x to the right by n, using a logical shift 3 16
isNonNegative(int x) return 1 if x >= 0, return 0 otherwise 3 6
isPositive(int x) return 1 if x > 0, return 0 otherwise 3 8
reverseBytes(int x) reverse the bytes of x 3 25
bang(int x) !x without using ! 4 12
abs(int x) absolute value of x (except returns TMin for TMin) 4 10

Function bitAnd(x,y) computes the And function. That is, when applied to arguments x and y, it returns the same value as (x & y). However, you may only use the operators | and ~.

Function bitXor(x,y) should duplicate the behavior of the bit operation x ^ y, using only the operations & and ~.

Function isNotEqual(x,y) compares x to y for inequality. As with all predicate operations, it should return 1 if the tested condition holds and 0 otherwise. Note that you cannot use the relational operators != or ==.

Function getByte(x) extracts a byte from a word x. The bytes within a word are ordered from 0 (least significant) to 3 (most significant).

Function copyLSB(x) returns a result with all 32 bits equal to the least significant bit of x.

Function logicalShift performs logical right shifts. You may assume the shift amount n satisfies

	1 <= n <= 31.

Function tmax() returns the largest integer.

Function isNonNegative(x) returns true (i.e., 1) if x is greater than or equal to 0.

Function isPositive(x) returns true (i.e. 1) if x is greater than 0.

Function abs is equivalent to the expression 

	(x < 0) ? -x : x

giving the absolute value of x for all values other than TMin. abs(TMin) should return TMin

Function addOK(x, y) returns 1 if its two arguments can be added together without overflow.

Advice

  1. For quick testing, type

    	    make help

    in the directory containing the datalab handout files.

  2. A suggested order of writing the functions is:

    Group I
    1. bitAnd
    Group II
    1. bitXor
    2. getByte
    3. reverseBytes
    4. tmax
    5. isNotEqual
    6. copyLSB
    7. logicalShift
    Group III
    1. negate
    2. isNonNegative
    3. isPositive
    4. fitsBits
    5. addOk
    6. bang
    7. abs

    There will be 3 submission due dates, one for each group.

    So the first submission due is for Group I, consisting of only one function, bitAnd.

  3. The btest and dlc functions provide a bit more assistance for debugging than the simple make commands:

    Type dlc -help for a list of command line options. The README file is also helpful. Some notes on dlc:

    • The dlc program runs silently unless it detects a problem.
    • Don't include \verb:: in your bits.c file, as it confuses dlc and results in some non-intuitive error messages.

    Check the file README for documentation on running the btest program. 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, e.g., 

    	btest -f isPositive

Hand In Instructions

On CDM Linux servers, change to the directory with your bits.c file and submit it typing: 

	make handin

If you are using your own Linux machine, submit your bits.c file to the Course Online site for assignment 'datalab'.

Make sure you test your files locally. If you test your files on the CDM machines, the grade you get from btest is representative of the grade you will receive when you submit your solution except for extra credit points. The dlc program will let you determine if you will also earn an extra credit point for each function for which you are within the maximum operator limit.