code Transfigure data with bit-level operations.

You must use a CS 240 computing environment for CS 240 code 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.

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!

Advice

This assignment is your first 240 code assignment. It is signficantly more challenging (and fun!) than the assignments that precede it.

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

Start early. Start this assignment soon after you submit the preceding assignment. 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 recent CS 240 alum will confirm that we are serious about this!

Prepare and plan before you code. Complete the preparatory exercises. Try some pencil-and-paper or whiteboard hacking to design your solution before you start typing C.

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.

Learn CS 240 Software Tools

For this assignment, you will learn to use a handful of programming tools that we will use repeatedly throughout the semester. You are not expected to know these already, but you are expected to learn them. Please do not hesitate to ask questions as you do. In some semesters we get more or less time to cover these during lab. Some learning and practice with these tools on your own time is necessary and beneficial in all semesters.

  1. Create a Bitbucket account using these steps if you have not yet.
  2. Complete the lab tutorials on the command line, the Emacs, and C.
  3. Connect your Bitbucket account to your local account using these steps. Do this once on any CS Linux lab machine and once on your wx appliance if you have decided to use it.
  4. Read to understand the purpose of Mercurial and Bitbucket.
  5. Complete the Mercurial Solo Basics Tutorial.

Setup

Each student is provided with a Mercurial repository hosted on Bitbucket. Your repository for this assignment is called cs240-bits-owner, where owner is replaced with your Bitbucket username. This repository contains starter code and is where you will submit your work for the assignment.

To start, hg clone your Bitbucket repository to your local computer account.

  • As you make changes, you will record them with hg commit and submit them (or make backups) to your Bitbucket repository with hg push. The instructors will collect your work there.
  • If you are already comfortable with the Mercurial workflow from lab, note that the assignment manifest at the top of every assignment gives steps necessary to obtain starter code. (We purposelfully omit full instructions right here so you get used to finding them there.)
  • The Solo Workflow summarized here or the full Mercural Tutorial will walk you through in more detail if you are not yet comfortable.

Your Beginner’s Bit Transfiguration Kit contains the following files, explained in later sections of this document:

  • bits.c: you will edit this file
  • btest.c, dlc, driver.pl: testing code and tools
  • Makefile: recipes to compile testing code with the make command
  • README: documentation of testing tools
  • remaining files are adiitional support for testing

Preparatory Exercises

CS 240 code assignments include preparatory exercises. You do not need to submit answers to these exercises for grading, but you must complete them before starting the main assignment.

Preparation is your ticket for assistance.
  • You may ask questions on preparatory exercises at any time.
  • You must complete the preparatory exercises (and show evidence) before asking code/debugging questions about the main assignment.

A. Learn your Tools

Learn your tools first.

B. Bitwise Warmup

Examine the code below:

unsigned puzzle(unsigned x, unsigned y) {
    unsigned result = 0;
    for (unsigned i = 0; i < 32; i++){
        if (y & (1 << i)) {
            result = result + (x << i);
        }
    }
    return result;
}
  1. Simulate this code on the (x, y) pairs (2,3), (3,9), and (5,2).
  2. Can you think of a better name for this function, describing what it computes from x and y (now how)?

C. Read the Instructions

Skim the rest of this document, as well as as the coding rules given in bits.c. To help with this tour, here are a few questions to answer.

  1. What command should you run to compile your code?
  2. What command should you run to test both correctness and compliance of your solutions?
  3. Are loops allowed?
  4. How many arguments does the thirdBits function take? What operators are allowed in thirdBits?

Tasks

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 rough difficulty rating, from low (1) to high (4)1

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.

Puzzles

The puzzles are summarized here and documented more precisely in bits.c.

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.

[Update Feb 16] If you experience errors like this:

bpw@finch: ~/240/starters/cs240-bits$ make
gcc -O -Wall -g -pedantic -Werror -lm -o btest bits.c btest.c decl.c tests.c
bits.c:1:1: error: C++ style comments are not allowed in ISO C90
bits.c:1:1: error: (this will be reported only once per input file)
...

Edit the file Makefile in your repository. Replace the line:

CFLAGS = -O -Wall -g -pedantic -Werror

with

CFLAGS = -O -Wall -g -Werror

by removing -pedantic.

The -pedantic option helps detect errors earlier, but the lab machines currently have an old version of the C compiler that is a little too -pedantic. Until we can update it, please follow the above steps if you encounter the problem.

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.

[Updated Feb 13] You may receive one warning from dlc which you can safely ignore:

/usr/include/stdc-predef.h:1: Warning: Non-includable file <command-line> included from includable file /usr/include/stdc-predef.h.

Pay attention to other warnings and errors.

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.

Grading

Submit your work by committing and pushing your latest work to your Bitbucket repository, as indicated in the assignment manifest.

Submit "quiet" code.

Before submitting, disable any diagnostic printing you added in bits.c.

Your grade will be derived as follows:

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

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 may use decimal number notation (normal syntax, e.g., 87) or hexadecimal notation (0x57). dlc will NOT accept binary notation (0b01010111).

  1. Different people have different opinions about which puzzles are more difficult. ↩