code Transfigure data with bit-level operations.

You must use a CS 240 computing environment for CS 240 assignments.

CS 240 is a low-level systems course where the low-level system details matter. Some provided tools will not run elsewhere. Some solutions that work on other compilers may fail with ours (and vice versa). Do not waste time trying to use a different environment (Mac/Windows). Use a CS 240 computing environment.

Also, now is the right time to learn your tools: If you did not learn how to use Emacs or complete the Mercurial solo workflow tutorial during lab, do so before starting work on this assignment.

Contents

Overview

This assignment requires you to solve a series of programming puzzles to become familiar with data representation at the bit level. Some puzzles may seem far removed from your previous programming experience, but bit manipulations like these are crucial for efficiency in essential applications such as cryptography, data compression, or encoding and decoding pictures, audio, video, and more. These puzzles will push you to think in new ways and internalize how computers deal with bit representations. Mind-twisters, enlightenment, and fun await!

Read the Instructions and Advice carefully and skim this entire document before starting to work.

Advice

Start early. This assignment will take considerably longer than the paper exercises we have done so far. Even if you are already comfortable with the bitwise operators, these puzzles are not easy. Allow plenty of time do some work, get stuck, sleep on it, and come back. Any CS 240 alumna from fall 2014 and later will confirm that we are serious about this!

Plan before you code. Try some pencil-and-paper or whiteboard hacking to design your solution before you start typing C.

Learn the tools. Before starting to write code for this assignment, get familiar with the CS 240 tools if you did not get a chance during lab. You will use these tools repeatedly during this assignment and the rest of the course. If you are Python programmer with no knowledge of Java or C, check out C for Python programmers.

Commit often. Each time you get a new function working (or even just closer to working), hg commit your work with Mercurial. Also push your commits to your Bitbucket repository reasonably often. Then if things go wrong later you can always recover your work.

The short Integer Arithmancy exercises will help familiarize you with number representations for this assignment, but many puzzles can be solved without knowing number representation.

Starter Code

Starter code for this assignment is available in the wellesleycs240 / cs240-bits repository. You will make a fork (your own private copy) of this repository on Bitbucket to store and submit your solutions. You will then clone your repository to your local computer account to work on it. As you make changes, you will save and submit them by committing and pushing back to your Bitbucket repository.

To begin, follow the fork-share-clone process described here, as we did in the first lab meeting, but replace the cs240-lab1 repository with cs240-bits.

Your working copy will contain several tools and supporting files, described later, and a bits.c file where you will write solutions.

Instructions

Your task is to solve the given bit puzzles and explain your solutions. The bits.c file contains rules, specifications, and function templates for the programming puzzles. For each puzzle, you must:

  • Implement the function according to the specification and coding rules.
  • Explain in one or more comments why your solution works.

Implementation

All functions must obey the restrictive coding rules at the top of bits.c. Read the rules carefully before starting – they are essential. The rules restrict you to performing only bit-level operations on data. The purpose of these restrictions is to force you to think about the data as bits. Due to the restrictions, your solutions may not be the simplest or most efficient way to accomplish the function’s goal, but the process of working out the solution should make the notion of data as bits completely clear.

For each individual function, a comment in bits.c gives:

  • a specification of the function’s behavior
  • the set of operators allowed
  • the maximum number of operations allowed
  • a difficulty rating, from low (1) to high (4)

Tests in test.c include a reference implementation of the function that can also help understand expected behavior. The reference implementations completely ignore restrictions on allowed operations.

Tables below summarize the difficulty rating and description of each function.

The Testing section below describes how to evaluate compliance and correctness in your solutions.

Explanation

For each function, one or more comments must explain how and why your solution works.

Translating the series of operations into English comments does not suffice. Re-explaining the high-level specification of what the function computes does not suffice. Both of those explain what. Your comment must demonstrate clearly that you understand the link between these. How/why do the effects of the individual operations combine to implement the specification?

In some cases your comments may be shorter than your code. In some cases they may be longer.

Grading

Your grade will be derived as follows:

Correct solutions that match or beat the operator count from the intructor’s solutions may result in prizes!

Submitting Your Work

Submit your work by committing and pushing your final revisions to your Bitbucket repository, where your instructor will retrieve your work for grading. Do not submit a paper copy. Detailed instructions are here.

Puzzles

Raw Bitwise Functions

These functions do checks and manipulations on 32-bit values treated as bit vectors (i.e., they do not interpret the values as numbers).

Rating Function Name Description
1 bitAnd x & y using only ~ and |
1 bitXor x ^ y using only ~ and &
1 thirdBits return word with every third bit (starting from the LSB) set to 1
2 getByte Extract byte n from word x
3 logicalShift logical shift x to the right by n
4 bang Compute !x without using !
3 conditional x ? y : z

Two’s Complement Functions

These functions do checks and manipulations of 32-bit 2’s-complement integer values.

Rating Function Name Description
2 fitsBits returns 1 if x can be represented as an n-bit, two's complement integer
2 sign return 1 if positive, 0 if zero, and -1 if negative
3 addOK Determine if x+y can be computed without overflow
4 isPower2 returns 1 if x is a power of 2, and 0 otherwise

Compiling and Testing

We have included a few tools to help you check your work.

To build (compile) your solutions and provided testing code, type the command make. The make command looks for a file called Makefile that gives a recipe for how to compile a given executable so that you can avoid retyping long compilation commands each time you need to compile a new version. The Makefile we provide (take a look) compiles your code with testing code and produces an executable file called btest.

Correctness: btest

btest is a program that checks the functional correctness of the code in bits.c.

To run tests of your solutions, type the command ./btest. This runs the executable file btest, which tests the version of bits.c that has been compiled. Every time you update bits.c and want to run btest, you must first run make to compile btest using the latest version of your code.

$ make
$ ./btest

You can use the -f flag to instruct btest to test only a single function. For example, to test only bitXor, run:

$ ./btest -f bitXor

You can feed it specific function arguments using the option flags -1, -2, and -3. For example, to test bitXor(1,0xf), run:

$ ./btest -f bitXor -1 7 -2 0xf

Check the README file for documentation on running the btest program.

We may test your solution on inputs that btest does not check by default and we will check to see if your solutions follow the coding rules.

Coding Rules: dlc

dlc is a modified C compiler that you can use to check for compliance with the coding rules for each puzzle. The typical usage is:

$ ./dlc bits.c

The program runs silently unless it detects a problem, such as an illegal operator, too many operations, or non-straightline code in the integer puzzles. Running with the -e switch:

$ ./dlc -e bits.c

causes dlc to print counts of the number of operations used by each function. Type ./dlc -help for a list of command line options.

Autograde: driver.pl

The driver.pl tool will automatically grade your solutions on correctness and performance using the dlc and btest tools.

Points are awarded only for working solutions. The difficulty rating determines the number of correctness points available for each puzzle. Each puzzle may receive up to 2 performance points, based on the number of operations used.

Run the autograder like this (part of the output on our sample solution is shown):

$ ./driver.pl
[ ... status messages omitted here ... ]
Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops Puzzle
1       1       0       2       4   bitAnd
1       1       0       2       7   bitXor
1       1       0       2       4   thirdBits
2       2       0       2       7   fitsBits
2       2       0       2       4   sign
2       2       0       2       3   getByte
3       3       0       2       6   logicalShift
3       3       0       2       9   addOK
4       4       0       2       6   bang
3       3       0       2       7   conditional
4       4       0       2       11  isPower2
Score = 48/48 [26/26 Corr + 22/22 Perf] (68 total operators)

Issues with undeclared variables? See Variable Declarations.

More Tools

Number Conversion

The ishow tool lets you display integer representations and conversions. It takes hex or decimal input.

$ ./ishow 0x27
Hex = 0x00000027,	Signed = 39,	Unsigned = 39

Debugging

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.

Variable Declarations

The dlc program enforces a stricter form of C declarations than gcc enforces. In particular, in a block (what you enclose in curly braces) all your variable declarations must appear before any statement that is not a declaration. For example, dlc 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 */
    return b+2;
}

Instead, you must declare all your variables first, like this:

int foo(int x) {
    int a = x;
    int b;
    a *= 3;
    b = a;
    return b+2
}

Number Notation

You are may use decimal number notation (normal syntax, e.g., 87) or hexadecimal notation (0x57). dlc will NOT accept binary notation (0b01010111).