Bits

Assignment: Bits

• Assign: Wednesday, 17 Feb
• Due: 4:00pm Friday, 26 Feb
• Policy: Individual graded synthesis assignment
• Code: cs240 start bits --solo
• Submit: git commit and git push your completed code.
• Reference:
  • Data as Bits
  • Integer Representation

Contents

• Assignment: Bits
• Overview
  • Goals
  • Advice
  • Time Reports
• Setup
  • 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:

• Complete Assignment Zero before starting. Knowing your way around the tools will pay off now, all semester, and beyond.

• 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!

• 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 a past semester, according to self-reported times for a similar version of this assignment:

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

Setup

Complete Assignment Zero to learn the standard CS 240 tools before starting this assignment.

Get the Code

Each student is provided with a bits 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 CS 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 repository initially contains many files. The only file that you need to inspect or edit is:

• bits.c: file where you will implement bit puzzle solutions

The other files support for testing. You do not need to inspect them, though you are free to do so. You will be compiling or running them along with your code in bits.c. The most important ones are:

• btest.c, dlc, driver.pl: testing code and tools
• Makefile: recipes to compile testing code with the make command

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. Get the code (and know your tools).

Complete the setup steps above to refresh your memory of the course software tools and acquire assignment code.

B. Practice bitwise thinking.

1. Review the zero.c functions from Zero.

2. Review the Integers Practice exercises from the Integer Representation topic in class.

3. Consider the following code:

   unsigned puzzle(unsigned x, unsigned y) {
       unsigned result = 0;
       for (unsigned i = 0; i < 32; i++){
           if (y & (1 << i)) { // remember, the zero number is false, any nonzero number is true
               result = result + (x << i);
           }
       }
       return result;
   }

   Complete the following exercises with the puzzle function defined above.

   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

C. Read the instructions.

As you read this document and the coding rules given in bits.c, complete these exercises to familiarize yourself with the 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?

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.

Raw Bitwise Functions

These functions do checks and manipulations on 32-bit int 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 int 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 Bits 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
}

This restriction is specific to older standards for the C language, such as that used by the dlc checker. In future assignments, it will best practice and good style to declare variables at the innermost scope that is reasonable.

Avoid Binary Notation

Remember that unprefixed integer literals in C use decimal notation. The expression 10110010 in a C program means “the int value ten million, one-hundred ten thousand, and ten.”

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

Instead, make good use of hexadecimal in this assignment: 0xF0. Or, for small numbers, decimal notation may work just fine.

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. To submit your work:

1. Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.

2. Make sure you have committed your latest changes. (Replace FILES with the files you changed and MESSAGE with your commit message.)

   $ git add FILES
   $ git commit -m "MESSAGE"

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

   $ cs240 sign

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

   $ git push

Confirm: 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!