• Assign: Monday, 11 February
• Due: 11:59pm Wednesday, 20 February
• Policy: Individual graded synthesis assignment
• Code: cs240 start bits --solo
• Submit: git commit, cs240 sign, and git push your completed code.
• Reference:
  • data as bits
  • integer representation
  • K&R 2.7, 2.9
  • C for Python programmers

Contents

• Overview
  • Goals
  • Advice
  • Time Reports
• Setup
  • Learn the Tools
  • Get the Code
• Tasks
• Preparatory Exercises
• Puzzle Specifications
  • Raw Bitwise Functions
  • Two’s Complement Functions
• Compiling and Testing
  • Compiling: make
  • Correctness: btest
  • Coding Rules: dlc
  • Summary: driver.pl
  • Common Issues
• Submission
• Grading

Overview¹

This assignment requires you to solve a series of programming puzzles using only bitwise operations. 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. The puzzles will push you to think in new ways and internalize how computers deal with bit representations. Mind-twisters, enlightenment, and fun await!

Goals

• To understand the representation and manipulation of data as bits.
• To communicate how low-level bitwise operations relate to high-level data operations through representation.
• To master unsigned and two’s complement number representation.
• To become comfortable with basics of the C programming language.
• To practice using command-line tools for programming.
• To have at least one mind-blowing realization about two’s complement.

Advice

This is your first 240 code assignment. It is more challenging (and fun!) than the paper exercises that precede it. Here is some advice:

• Start early. This assignment takes considerably longer than the earlier paper exercises. Allow time to work, get stuck, sleep on it, and come back repeatedly. Any recent CS 240 alum will confirm that we are serious about starting early!

• Learn the tools early. It will pay off all semester (and beyond).

• 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 and push often. Each time you get a new function working (or even just closer to working), git add and git commit your work. Also git push your commits reasonably often. If things go wrong later you can always recover your work.

Time Reports

In Fall 2018, this assignment required solving one (difficult) puzzle which the Spring 2019 assignment does not require. According to self-reported times from Fall 2018:

• 25% of students spent <= 7 hours.
• 50% of students spent <= 9 hours.
• 75% of students spent <= 12 hours.

Compared to other CS 240 code assignments, this assignment has a higher reported median work time per available time ratio: 9 hours / 8 days using Fall 2018 self-reported time information and the Spring 2019 assignment schedule. Most code assignments have a similar median reported work time, but longer available time from release to deadline.

Setup

Learn the Tools

For this assignment, you need a set of programming tools that you will use repeatedly throughout CS 240. You are not expected to know these coming into CS 240. We introduce tools in lab activities, but practice on your own time is necessary and beneficial. If you did not finish during lab activities:

1. Complete the lab tutorials on the command line, the Emacs, and C, referring to additional documentation as needed.
   • If you are not familiar with Java (or C), but you know some Python, check out C for Python programmers.
2. Set up your CS lab account (and optionally the csenv appliance) for CS 240.
3. Read to understand the purpose of version control for CS 240 assignments.
4. Complete the Git and CodeTub setup and Solo Basics tutorial.

Get the Code

Each student is provided with a true repository hosted on the CS 240 repository server. This repository contains starter code and is where you will submit your work for the assignment.

To start, run cs240 start bits --solo to create your hosted repository and clone it to your local computer account.

• As you make changes, record them with git add and git commit and submit them (or make backups) with git push.
• The assignment manifest at the top of every assignment gives steps necessary to obtain starter code.
• The Solo Workflow summary or the full Git and CodeTub tutorial describe this process in more detail.

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 additional support for testing

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 how and why your solution works.

  Translating the operations into English or re-explaining the high-level specification do not suffice. You must demonstrate that you understand the link between the high-level behavior and its low-level implementation. How/why do the effects of the individual operations combine to implement the specification?

Grading considers correctness and compliance of your implementations as well as effectiveness of your explanations.

The remainder of this document describes:

1. Preparatory exercises to help you review and start the assignment.
2. Specifications and rules for the puzzle functions you must implement.
3. Documentation of how to compile and test your implementation.
4. Grading criteria.

Preparatory Exercises

CS 240 code assignments include preparatory exercises. Preparatory exercises are required, but not graded (unless otherwise noted).

A. Learn your tools.

Complete the setup steps above to learn software tools and acquire assignment code.

B. Practice bitwise thinking.

Examine the code below. You have seen it in class.

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?
3. Why does this code work to implement the operation you named?
4. Recommended: Try some practice problems from CSAPP: 2.8, 2.9, 2.14, 2.16
5. Review exercises from the Integer Arithmancy assignment.

C. Read the instructions.

As you read this document and the coding rules given in bits.c, complete these exercises to familiarize you coding restrictions, the compilation process, and puzzle functions.

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. Where are loops allowed?
4. How many arguments does the thirdBits function take? What operators are allowed in thirdBits?

D. Review your lab notes.

You should see the solutions to 1 or 2 of the puzzle functions in lab. Check your notes to save some time!

Puzzle Specifications

General Restrictions

All puzzle function implementations 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.

Individual Specifications

For each individual function:

• A function header comment in bits.c gives:
  • a specification of the function’s behavior
  • the set of operators allowed (a specific subset of the operators ~ & | ^ + << >> !)
  • the maximum number of operations allowed
  • a rough difficulty rating, from low (1) to high (4)²
• A testing harness in test.c gives alternative documentation of expected behavior:
  • test cases (arguments and corresponding expected return values)
  • an unrestricted reference implementation of the function

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

Problems marked [Independent] must be completed without assistance from tutors or instructors.

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.

Compiling and Testing

There are 4 key steps for checking your work:

1. Use make to compile your code and generate the btest executable.
2. Use btest to check your solution’s functional correctness.
3. Use dlc to check your solution’s compliance with the coding rules.
4. Use driver.pl to autograde your solution.

The dlc and driver.pl tools enforce strict coding rules and will raise error messages if you have use prohibited or unsupported code. See Common Issues if you are confused by error messages in these steps.

Compiling: make

To build (compile) your solutions and provided testing code, type the command make.

$ 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. In this case, the Makefile we provide (take a look!) uses gcc to compile 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.

Run tests of all puzzle functions with the command ./btest, which runs the executable file btest that was generated last time you compiled bits.c.

$ ./btest

Don’t forget to (re-)compile a fresh version of the btest executable each time you update bits.c.

... edit and save bits.c ...
$ make
$ ./btest

To test an individual puzzle function, e.g., bitXor, pass the function name to btest with its -f flag:

$ ./btest -f bitXor

Optionally, test an individual function with specific arguments using the flags -1, -2, and -3 to pass the 1st, 2nd, and 3rd arguments. For example, to test bitXor(7, 0xf), run:

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

Coding Rules: dlc

dlc is a modified C compiler that can check your solution against the coding rules.

$ ./dlc bits.c

A lack of output means your solution follows the coding rules. Error messages will appear if your solution violates the coding rules.

The -e switch supports counting operations in a function.

$ ./dlc -e bits.c

Summary: 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)

Common Issues

The dlc checker enforces a stricter and older form of C declarations than gcc enforces. This section describes how to avoid common issues with dlc for the Bit Transfiguration assignment only. Do not adopt these as style conventions in later assignments.

Benign Warning in std-predef.h

You may receive one warning from dlc that 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.

Declare Variables at the Start of the Function

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
}

Avoid Binary Notation

The dlc checker does not accept the 0b prefix for numbers in binary notation (e.g., 0b11110000). Do not use it.

Use decimal (e.g., 240) or hexadecimal (0xf0) notation only.

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

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

Avoid #include

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.

Submission

Submit: The course staff will collect your work directly from your hosted repository as of the deadline. To submit your work:

1. Make sure you have committed your latest changes.

   $ git add ...
   $ git commit ...

2. Run the command cs240 sign to sign your work and respond to any assignment survey questions.

   $ cs240 sign

3. Push your signature and your latest local commits to the hosted repository.

   $ git push

Confirm: After pushing, all local changes have been submitted if the output of git status shows both:

• Your branch is up to date with 'origin/master', meaning all local commits have been pushed
• nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.

Grading

Your grade will be derived as follows:

• Correctness and performance (72 points = 1.5 × autograder score):
  • Grading considers correctness and performance of all puzzle solutions.
  • Tests may include new inputs that btest does not check by default.
  • Solutions must comply with the coding rules as checked by dlc.
  • No credit is awarded unless the driver.pl autograder can compile and run your code.
• Succinct comments explaining why each puzzle solution works (28 points):
  • Grading may consider explanations for a random subset of puzzles.
  • Good comments describing incomplete or non-working solutions may receive credit in this part.

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