Bit Transfiguration

code Transfigure data with bit-level operations.

• Checkpoint: complete 4-5 puzzles by 11:00pm Monday, 8 February
• Due: 11:00pm Thursday, 11 February
• Starter Code: fork wellesleycs240 / cs240-bits (just once!) and add bpw as admin. (Need help?)
• Submit:
  • Commit and push your final revision and double-check that you submitted the up-to-date version. (Need help?)
  • Do not submit a paper copy.
• Relevant Reference:
  • data as bits
  • integer representation
  • K&R 2.7, 2.9
• Collaboration: individual code assignment policy, as defined by the syllabus.

Contents

• Overview
• Instructions
• Puzzles
• Testing
• More Tools

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 artificial, 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 already feel 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), commit your work. 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:

• 50% correctness
• 20% performance (number of operations)
• 30% succint, clear comments explaining why your implementations work

Partial credit may be awarded for partially working solutions or comments describing an intended approach that you did not finish implementing.

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).

Two’s Complement Functions

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

Testing

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

dlc: Compliance

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.

btest: Testing

btest is a program that checks the functional correctness of the code in bits.c. To build (compile) btest, 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.

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. Notice that you must rebuild btest after modifying your bits.c file if you want to test the current version. (Just run make again.)

$ 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.

driver.pl: Combined Testing and Conciseness

The driver.pl tool will both run btest and count the number of operations your solutions, displaying an automatically generated score for each. The scores do not convert directly to grades, but they let you check correctness and performance succintly. Here is (part of) the output on our sample solution:

$ ./driver.pl
[ ... status messages omitted here ... ]
Correctness Results     Perf Resultsogic
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       14  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] (76 total operators)

The “performance” score is based on the number of operations used. Fewer operations = higher score, in a range of 0-2 for each puzzle, but getting the absolute minimum number of operations is not necessary to get the full score.

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 */
}

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

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