Assignment 1: DataLab (due on Tue, Sep 17, 2024 by 11:59pm)

Introduction

The purpose of this assignment is to become familiar with the bit-level representation of integer and floating-point numbers (and their operations). You’ll achieve 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 while working your way through them.

You can assume 32-bit 2’s complement integers (int in C on x86-64) and 32-bit IEEE 754 floating-point variables (float in C). Floating point variables are passed to your functions as unsigned int (on which you operate using bitwise and other integer operations).

Notably, problems on the manipulation of floating point variables allow you to use a larger set of operations, including loops (for, while, do while), conditional statements (if), all operators (including -, >, <) and 4-byte constants.

To solve the problems, you must know:

  • 2’s complement and integer operations (negation, addition, subtraction, bitwise operations).
  • Overflow conditions for addition and subtraction of signed integers.
  • The bit-level format of float (1 bit for sign, 8 bits for exponent in excess-127 format, 23 bits for fraction).
  • How to extract (and combine) sign/exponent/fraction fields using bitwise operations.
  • The bit-level encoding of special values (positive/negative zero and infinity, NaN) and their behavior with respect to floating-point operations.

Logistics

This is an individual project. All handins are electronic. Clarifications and corrections will be posted on the course Piazza page.

Remember that:

  • You are not allowed to search for help online!
  • Any time you receive help from a TA/CP, you should acknowledge that in your code with a comment starting with the string “assistance from”.
  • You are not allowed to ask other students for detailed help, show them your code, or discuss the specifics of the solution.
  • Reconsideration requests must be made within one week of our release of grades for the assignment.

Be aware that you may be asked to explain your code to a member of our course staff using only what you have submitted: your comments in the code should be such that you can determine what your code does and why a few weeks later, if needed.

Handout Instructions

Similarly to the previous assignment, we will create a private GitHub repository for this assignment and share it with you. Be sure to clone the GitHub repository on the programming server.

The only file you will be modifying and turning in is bits.c, although other files will help you, such as to find out what your grade will be. The bits.c file contains a skeleton for each of the programming puzzles. Your assignment is to complete each function skeleton using only straight-line 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:

!  ~ & ^ | + << >>

A few of the puzzles/functions may further restrict this list so read the comments of each puzzle/function carefully. Also, you are not allowed to use any constants longer than 8 bits. See the comments in README.md for detailed rules and a discussion of the desired coding style.

In contrast, floating-point puzzles allow you to use 4-byte constants, loops and conditionals (with any comparison operator).

The Puzzles

Integer Puzzles

  • int tmin() (1 point, 1 op allowed): return the minimum 2’s complement integer.
  • int bitAnd(int x, int y) (1 point, 4 ops allowed): x&y using only ~ and |.
  • int negate(int x) (1 point, 2 ops allowed): duplicate the effect of -x.
  • int isEqual(int x, int y) (2 points, 2 ops allowed): return 1 if x == y, and 0 otherwise.
  • int addOK(int x, int y) (3 points, 14 ops allowed): return 1 if x + y does not cause overflow, and 0 otherwise.
  • int signMag2TwosComp(int x) (4 points, 10 ops allowed): convert from sign-magnitude to two’s complement.
  • int satAdd(int x, int y) (4 points, 25 ops allowed): add x and y, saturating to the minimum or maximum 2’s complement integer in case of overflow.
  • int dividePower2(int x, int n) (3 points, 8 ops allowed): compute x/(2^n) for 0 <= n <= 30, rounding toward 0.
  • int replaceByte(int x, int n, int c) (3 points, 10 ops allowed): replace the $n$th byte of x with c (between 0 and 255).

Floating-Point Puzzles

  • unsigned floatAbsVal(unsigned uf) (2 points, 5 ops allowed): compute (f > 0.0)?(f):(-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.
  • int floatIsEqual(unsigned uf, unsigned ug) (3 points, 19 ops allowed): compute f == g for floating point arguments f and g. Both the arguments are passed as unsigned int’s, but they are to be interpreted as the bit-level representations of single-precision floating point values. If either argument is NaN, return 0; +0 and -0 are considered equal.

Evaluation

Your score will be computed out of a maximum of 49 points including 27 correctness points and 22 performance points.

  • Correctness points. The puzzles have been given a number of correctness points between 1 and 4, such that their weighted sum totals to 30. We will evaluate your functions using the btest program (described in the next section) to check for correctness. You will get correctness points for a puzzle if it passes all the tests performed by btest.

  • Performance points. Our main concern at this point in the course is that you can get the right answer; but you should also try to keep things as short and simple as you can. Furthermore, some puzzles can be solved by brute force, but we want you to be more clever. Thus, for each function we’ve established a maximum number of operators that you are allowed to use. You will receive 2 additional performance points for each correct function that satisfies the operator limit. You can use the dlc program (described in the next section) to check if your program satisfies these limits.

Note that we will be running the grade program to do the grading (correctness and performance points).

Autograding your work

We have included the following grading tools in the handout.

  • btest checks the functional correctness of the functions in bits.c. Every time you modify bits.c, you should recompile it with make btest and run it as ./btest to see how many correctness points you would receive. You can run ./btest -f funcName to test only a specific function, or ./btest -f funcName -1 123 -2 456 to test funcName(123, 456). You can ignore any warnings about btest.c:528:9: warning: variable errors set but not used.

  • dlc is a modified version of an ANSI C compiler from the MIT CILK group that you can use to check for compliance with the coding rules for each puzzle (allowed operators and maximum number of operations). You can run it as ./dlc bits.c: the program runs silently unless it detects a problem, such as an illegal operator, too many operators, or non-straightline code in the integer puzzles. Run as ./dlc -e bits.c to also print the number of operations used by each function. You can ignore any warnings about /usr/include/stdc-predef.h:1: Warning: Non-includable file <command-line> included from includable file.

  • grade uses btest and dlc to compute correctness/performance points and produce your final score (the instructors will use this program to evaluate your solution). Run it as ./grade.

Hand-In Instructions

You must commit and push your solution to GitHub. Assignment collection will be automatic: right after the assignment deadline, our grading system will fetch the most recent commit on the master branch of your repository.

Be sure to run ./grade and verify that your program passes not only the functional tests, but also the performance tests. The grade you see from ./grade will be the grade you get.

If you want to use late days, make a push after the deadline: we will use the push date (not the commit date) to determine your late days.

Advice

  • Do not 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.
  • The dlc program enforces a stricter form of C declarations than is the case for C++, or that is enforced by gcc. In particular, any variable declaration must appear in a block 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 */
}
  • Run the grade program! We’ll be running the same program to determine your grade. You want to make sure it will work when we run it.

Acknowledgements. This lab was developed by the authors of the course textbook and their staff. It has been customized for use by this course.