Due: Mon Jan 21 11:59 pm
Ontime bonus 5%. Grace period for late submissions until Wed Jan 23 11:59 pm
Assignment by Julie Zelenski, with modifications by Nick Troccoli
This assignment delves into those topics covered in the first week of lecture and the first lab. You will be building your skills with:
- editing, compiling, testing, and debugging C programs under Unix
- writing code that manipulates bits and integers using the C bitwise and arithmetic operators
- working within/around the limits of integer representation
This assignment asks you to complete three programs, each of which explores a particular aspect of bitwise or numeric manipulation. The code you will write is short, but these small passages are mighty! Digging into this code will solidify your understanding of bits, integer representation, and computer arithmetic.
Take a look at the working on assignments page linked to from the assignments page as you are working on this assignment; it outlines everything you need to know about working through a CS107 assignment, from getting the starter code to testing to submitting.
Note: To remind you of the collaboration policy as it applies to the assignments: you are to do your own independent thinking, design, coding, and debugging. The assignments are for you to solidify your own understanding and develop your individual skills. If you are having trouble completing the assignment on your own, please reach out to the course staff; we are here to help!
To get started on the assignment, clone the starter project using the command
git clone /afs/ir/class/cs107/repos/assign1/$USER assign1
The starter project contains the following:
Makefile: three partially-written programs that you will modify, and their Makefile for compiling
custom_tests: the file where you will add custom tests for your programs
samples: a symbolic link to the shared directory for this assignment. It contains:
prototypes.h: files to configure and run Sanity Check. You can ignore these.
utf8_soln: executable solutions for the programs you will modify.
tools: contains symbolic links to the
submitprograms for testing and submitting your work.
Review and Comment
When you inherit code as a starting point, your first task should be to carefully review it. You want to know how the given code operates and what it does and doesn't handle so you can plan how the code you write will fit into the program. You are given about 25 lines for each program and will add about a dozen lines of your own per program, so there is more starter code to review than new code to add.
To get you started, our provided code for each program processes the command-line arguments and handles user error in how the program is invoked, and has a few important details, particularly in converting string arguments to numbers. The
triangle program from
assign0 used the
atoi function, which is simpler to use but has no capability to detect malformed inputs. For these programs, we are using the more robust, but complex,
strtol. Read the function documentation at
man strtol and review how the function is used in
Some questions you might consider as a self-test:
- How do the sample programs respond if invoked with missing arguments? excess arguments?
- How is the
errorfunction used here?
- When converting the user's string argument to a number, what base is passed to
strtol? In which bases does this allow the argument to be specified? How does the user's argument indicate which base to use?
- What does
strtoldo if it encounters an invalid character in the string to convert?
- How is the second argument to
strtolused for error-detection? Why is it ok that the
endvariable is used without being initialized? If you did not want that error-detection, what do you pass as the second argument instead?
- What does
strtoldo if asked to convert a string whose value would be too large to be represented in a
- Do you see anything unexpected or erroneous? We intend for our code to be bug-free; if you find otherwise, please let us know!
After reviewing the code, try experimenting with it! Build and run the programs, invoking them with different arguments to see how each is treated. Run the program under the debugger and step through code, printing intermediate values as you go. Observing the code in action is an excellent way to better understand it. Confirm your answers to the self-test questions above to verify your understanding.
We intentionally left off all the comments on the starter code, so you should add in documentation. Add an appropriate overview comment for the entire program, document each of the functions, and add inline comments where necessary to highlight any particularly tricky details.
1. Saturating Arithmetic
sat program performs a synthetic saturating addition operation. Saturating addition clamps the result into the representable range. Instead of overflowing with wraparound as ordinary two's-complement addition does, a saturating addition returns the type's maximum value when there would be positive overflow, and minimum when there would be negative overflow. Saturating arithmetic is a common feature in 3D graphics and digital signal processing applications.
Here are two sample runs of the
$ ./sat 8 8-bit signed integer range min: -128 0xffffffffffffff80 max: 127 0x000000000000007f $ ./sat 8 126 5 126 + 5 = 127
The program reports that an 8-bit signed value has a range of -128 to 127 and if you attempt to add 126 to 5, the result overflows and sticks at the maximum value of 127.
Your task is to implement the functions below to support saturating addition for the
long signed_min(int bitwidth); long signed_max(int bitwidth); long sat_add(long operand1, long operand2, int bitwidth);
bitwidth argument is a number between 4 and 64. A two's-complement signed value with
bitwidth total bits is limited to a fixed range. The
signed_max functions return the smallest and largest values of that range. The
sat_add function implements a saturating addition operation which returns the sum of its operands if the sum is within range, or the appropriate min/max value when the result overflows. The type of the two operands is
long but you can assume the value of the operands will always be within the representable range for a
bitwidth-sized signed value. That being said, this means there may be more bits than you need for a
bitwidth-sized value, and these extra bits should be set appropriately to ensure the value is correctly interpreted when it is inside a
There are three important restrictions on the code you write for this problem (these restrictions apply only to this program, and not others):
- No relational operators or
math.hfunctions. You are prohibited from making any use of the relational operators. This means no use of
< > <= >=. You may use
!= ==. You also should not call any function from the floating point
math.hlibrary (e.g no
exp2). These restrictions are intended to guide you to implement the operation via bitwise manipulation. All other operators (arithmetic, logical, bitwise, ...) are fine.
- No special cases based on bitwidth. Whether the value of bitwidth is 4, 64, or something in between, your functions must use one unified code path to handle any/all values of bitwidth without special-case handling. You should not use
if switch ?:to divide the code into different cases based on the value of bitwidth. This doesn't mean that you can't use conditional logic (such as to separately handle overflow or non-overflow cases), but conditionals that dispatch based on the value of bitwidth or make a special case out of one or more bitwidths are disallowed.
- No loops. No loops at all. (In particular, no loop increment by one and stop at max.)
A solution that violates any of these restrictions will receive zero credit, so please verify your approach is in compliance!
2. Cellular Automata
Many of you implemented Conway's delightful Life simulation as a CS106B/X assignment. For this assignment, we consider a simpler form of this "cellular automata" simulation implemented using bit operators.
This simulation models the life cycle of cells, where each cell can be either live or empty. For this assignment, we will represent a colony of cells as a 64-bit unsigned long, with one bit for each cell in a 1D world. A
1 indicates the cell is live, and
0 indicates the cell is empty. Over time, the game simulates the birth and death of future generations of cells using a provided set of rules that tell us, based on the state of a cell and its neighbors in the current generation, whether that cell is live or empty in the next generation. Using this bit vector representation, reading and updating a single cell is implemented as a bitwise operation.
Daniel Shiffman's neat book The Nature of Code contains an excellent explanation of how the simulation works. Rather than repeat it here, please read Sections 7.1 and 7.2 for essential background information. (Note that Section 7.3 of the above link goes on to develop an automata program, but it employs a more heavyweight array/OO design that we eschew in favor of a streamlined approach using bits.) Note that we'll be using larger colonies than those examples, but the idea is the same. Once you've read these sections, continue on below to confirm your understanding of the simulation.
Let's review how one generation advances to the next. As mentioned in the book sections, a cell and its two neighbors form a "neighborhood". A neighborhood is effectively a 3-bit number, a value from 0 to 7. Consider a live cell with a live left neighbor and an empty right neighbor. The cell's neighborhood in binary is
110, which is the 3-bit number 6. The ruleset dictates whether a cell with neighborhood 6 will be live or empty in the next generation. A ruleset is represented as an 8-bit number, one bit for each of the 8 possible neighborhood configurations. Let's say the ruleset is 77. The number 77 expressed in binary is
01001101. Because the bit at position 6 (note: position 0 refers to the least significant bit) of the ruleset is 1, this cell will be live in the next generation.
automata program animates an elementary cellular automaton starting from the initial generation and applying a specified ruleset through a number of iterations. It stops early if the generations do not change. In the output, each line represents one generation, going from the first generation at the top to the last generation at the bottom. Below shows a sample run of the program for ruleset 77:
$ ./automata 77 + ++++++++++++++++++++++++++++++ + +++++++++++++++++++++++++++++++ + + + + + + ++++++++++++++++++++++++++ + + + +++++++++++++++++++++++++++ + + + + + + + + + + + + ++++++++++++++++++++++ + + + + + +++++++++++++++++++++++ + + + + + + + + + + + + + + + + + + ++++++++++++++++++ + + + + + + + +++++++++++++++++++ + + + + + + + + + + + + + + + + + + + + + + + + ++++++++++++++ + + + + + + + + + +++++++++++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ++++++++++ + + + + + + + + + + + +++++++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ++++++ + + + + + + + + + + + + + +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ++ + + + + + + + + + + + + + + + +++ + + + + + + + + + + + + + + ++ + + + + + + + + + + + + + + + + + + + + + + + +
Pretty cool, huh? Since a ruleset is an 8-bit number, this means there are 256 different possible rulesets to dictate how cell generations evolve. There are some really cool outcomes you get depending on the ruleset. We'll let you explore these!
You are to implement these functions for the
void draw_generation(unsigned long gen); unsigned long advance(unsigned long gen, unsigned char ruleset);
draw_generation function outputs a row of 64 characters, one for each cell. A live cell is shown as an inverted box (a provided constant), and an empty cell is shown as a blank space. The generation is ordered such that the cell corresponding to the most significant bit is in the leftmost column and the least significant bit is in the rightmost column. We recommend you implement this first. If you then run the program, it should print out one line for the first generation, another blank line for a generation of 0 (since that is what the
advance function below initially returns), and then it will stop because the generation does not change.
advance function advances the generation forward one iteration. For each cell, it examines its neighborhood and uses the ruleset to determine the cell's state in the next generation. The two cells at the outside edges require a small special case due to having only one neighbor; their non-existent neighbor should be treated as though permanently off.
When testing your program, try playing with different values for the rulesets. Can you find a ruleset that produces Sierpinski's triangle? What about an inverted Sierpinski? Which ruleset produces your favorite output?
Rather than trying to manually eyeball the output for correctness, we recommend using SanityCheck to compare your output to that of the sample. Sanitycheck converts the output to show live cells as
# and empty as
.. This makes the output less aesthetically pleasing, but easier for visual discrimination.
A C char is a one-byte data type, capable of storing 28 different bit patterns. The ASCII standard (
man ascii) establishes a mapping for those patterns, but is limited to 256 options, so only ordinary letters, digits, and punctuation are included. Unicode is ASCII's more cosmopolitan cousin, defining a universal character set that supports glyphs from a wide variety of world languages, both modern and ancient (Egyptian hieroglyphics, the original emoji?).
A Unicode character is identified by a number called its code point, and the Unicode codespace encompasses over a million different code points. The notation U+NNNN refers to the code point whose value is hex 0xNNNN. The
utf8 program takes one or more code points and displays the UTF-8 hex encoding and corresponding character glyph for each code point. Here is a sample run:
$ utf8 0x41 0xfc 0x3c0 0x4751 U+0041 Hex: 41 Character: A U+00FC Hex: c3 bc Character: ü U+03C0 Hex: cf 80 Character: π U+4751 Hex: e4 9d 91 Character: 䝑
UTF-8 is an encoding used for Unicode - a way to store code points. It represents a code point as a sequence of bytes; the length of the sequence is determined by the number of significant bits in the code point's binary representation. The following table shows the structure for one, two and three-byte UTF-8 encodings. If the number of significant bits in the code point is no more than 7, it fits into the one-byte sequence; if the number of significant bits is between 8 and 11, it requires a two-byte sequence, and if the number is between 12 and 16 bits, it requires a three-byte sequence. (There is also a four-byte encoding, but we will ignore it).
|Code point range||Num sigbits||UTF-8 encoded bytes (in binary)|
|U+0000 to U+007F||7||
|U+0080 to U+07FF||11||
|U+0800 to U+FFFF||16||
1 bits shown in the UTF-8 bytes above are fixed for all code points. The
xxx bits store the binary representation of the code point. The one-byte sequence stores 7 bits, the two-byte sequence stores 11 bits (5 bits in first byte and 6 in the other), and the three-byte stores 16 bits (divided 4, 6, and 6).
In a single-byte sequence, the high-order bit is always
0, and the other 7 bits are the value of the code point itself. (The first 128 Unicode code points deliberately use the same single byte representation as the corresponding ASCII character, for backwards-compatibility with older systems that only know about ASCII -- neat!)
For the multi-byte sequences, the first byte is called the leading byte, and the subsequent byte(s) are continuation bytes. The high-order bits of the leading byte indicate the number of bytes in the sequence through the number of 1s. The high-order bits of a continuation byte are always
10. The bit representation of the code point is then divided across the low-order bits of the leading and continuation bytes.
Example (paraphrased from Wikipedia UTF-8 page)
Consider encoding the Euro sign, €.
- The Unicode code point for € is U+20AC.
- The code point is within the range U+0800 to U+FFFF and will require a three-byte sequence. There are 14 significant bits in the binary representation of 0x20AC.
- Hex code point 20AC is binary
00100000 10101100. Two leading zero bits of padding are used to fill to 16 bits. These 16 bits will be divided across the three-byte sequence.
- Let's calculate the leading byte. High-order bits are fixed: three 1s followed by a 0 indicate the three-byte sequence. The low-order bits store the 4 highest bits of the code point. This byte is
11100010. The code point has 12 bits remaining to be encoded.
- Next, let's calculate the first continuation byte. High-order bits are fixed
10, low-order bits store the next 6 bits of the code point. This byte is
10000010. The code point has 6 bits remaining to be encoded.
- Finally, let's calculate the last continuation byte. High-order bits are fixed
10, low-order bits store the last 6 bits of the code point. This byte is
- The three-byte sequence this results in is
10101100, which can be more concisely written in hexadecimal, as
e2 82 ac. The underscores indicate where the bits of the code point were distributed across the encoded bytes.
You are to write the
to_utf8 function that takes a Unicode code point and constructs its sequence of UTF-8 encoded bytes.
int to_utf8(unsigned short code_point, unsigned char seq)
to_utf8 function has two parameters; an unsigned short
code_point and a byte array
seq. The function constructs the UTF-8 representation for the given code point and writes the sequence of encoded bytes into the array
seq. The first byte (e.g. leading byte) should go at index 0, and the remaining bytes (if any, e.g. continuation bytes) should follow at index 1, etc. The
seq array is provided by the client and is guaranteed to be large enough to hold a full 3 bytes, although only 1 or 2 may be needed. The function returns the number of bytes written to the array (either 1, 2, or 3).
This task is excellent practice with constructing bitmasks and applying bitwise ops and standard techniques to extract/rearrange/pack bits.
In addition to the above programs, as part of this assignment you should also add at least 3 to 5 additional tests of your own per program (total of 10) in the
custom_tests file that show thoughtful effort to develop comprehensive test coverage. When you add a test, also document your work by including comments in the file that remind you why you included each test and how the tests relate to one another. The tests supplied with the default SanityCheck are a start that you should build on, with the goal of finding and fixing any bugs before submitting, just like how a professional developer is responsible for vetting any code through comprehensive testing before adding it to a team repository. As a reminder, you can visit the working on assignments linked to from the Assignments page for information about SanityCheck and how to use it with custom tests. We recommend you run SanityCheck early and often (and remember, it even makes a snapshot of your code to guard against editing mishaps!).
How do you brainstorm what additional tests to consider? First review the cases supplied with default sanitycheck to see what is already covered. Then consider the full range of inputs/possibilities beyond those simple cases. If the variety of inputs is sufficiently small, you may be able to enumerate a test case for each possibility. In other situations, exhaustive coverage is not feasible, so you instead identify representative samples to validate the operation on specific cases. You should target ordinary cases as well as edge conditions and unusual inputs.
For example, consider testing
sat. Your tests should cover a variety of different bitwidths, including extreme values, and on sums within range as well as those that overflow. For
automata, look carefully at where you have special cases in advancing the generation, and set up test cases that explicitly poke at those issues. There are some 65,000 possible code points you could feed to
utf8, but given that they all flow through just a few distinct paths, having a test case targeted to hit each of those paths, with a little extra attention at the boundaries, should be sufficient to give you confidence about the rest.
Once you are finished working and have saved all your changes, check out the guide to working on assignments for how to submit your work. We recommend you do a trial submit in advance of the deadline to familiarize yourself with the process and allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work.
Below is the tentative grading rubric. We use a combination of automated tests and human review to evaluate your submission. More details are given in our page linked to from the Assignments page explaining How assignments are graded.
Code Functionality (80 points)
- Sanity cases. (30 points) The default sanity check tests are used for sanity grading.
- Comprehensive cases. (45 points) We will thoroughly test on a variety of an additional inputs ranging from simple to complex, including edge conditions where appropriate.
- Custom sanitycheck tests (5 points) Your
custom_testsfile should include at least 10 tests of your own, 3-5 per program, that show thoughtful effort to develop comprehensive testing coverage. Please include comments that explain your choices. We will run your custom tests against your submission as well as review the cases to assess the strength of your testing efforts.
- Clean compile. (2 points) We expect your code to compile cleanly without warnings.
Code Quality (buckets weighted to contribute ~10 points)
The grader's code review is scored into buckets to emphasize the qualitative features of the review over the quantitative.
- Bitwise manipulation. We expect you to show proficiency in bitwise manipulation through clean construction and use of masks and proper application of the bitwise operations.
- Algorithms. Your chosen approach should demonstrate that you understand how to leverage bit patterns and numeric representation to directly and efficiently accomplish the task. Avoid unnecessary divergence and special-case code; unify into one general-purpose path wherever possible.
- Style and readability. We expect your code to be clean and readable. We will look for descriptive names, defined constants (not magic numbers!), and consistent layout. Be sure to use the most clear and direct C syntax and constructs available to you.
- Documentation. You should document both the code you wrote and what we provided. We expect program overview and per-function comments that explain the overall design along with sparing use of inline comments to draw attention to noteworthy details or shed light on a dense or obscure passage. The audience for the comments is your C-savvy peer.
On-time Bonus (+5%) The on-time bonus for this assignment is 5%. Submissions received by the due date earn the on-time bonus. Submissions received by the due date receive the on-time bonus. If you miss the due date, late work may be submitted during the grace period without penalty. No submissions will be accepted after the grace period ends, please plan accordingly! The bonus is calculated as a percentage of the point score earned by the submission. See the General Information handout for more information about the late policy.
How did the assignment go for you? We encourage you to take a moment to reflect on how far you've come and what new knowledge and skills you have to take forward. Once you finish this assignment, you will have completed your first C programs! This assignment may definitely have a bit of a learning curve getting used to the write/compile/debug process in C and the command line. Celebrate this important milestone; the skills you develop now will pay off throughout the quarter!
To help you gauge your progress, for each assignment/lab, we identify some of its takeaways and offer a few thought questions you can use as a self-check on your post-task understanding. If you find the responses don't come easily, it may be a sign a little extra review is warranted. These questions are not to be handed in or graded. You're encouraged to freely discuss these with your peers and course staff to solidify any gaps in you understanding before moving on from a task. They could also be useful as review before the exams.
- Consider all negative
ints whose absolute value is an exact power of two (-8, -32 and so on). What do their bit patterns have in common?
- How can you determine if an integer bit pattern has a pair of consecutive 'on' bits? (Straightforward to do using a loop, but there is also a clever single expression...)
- A treasure trove of bit wizardry curated by Sean Anderson, Stanford CS PhD.
We would also appreciate if you filled out this homework survey to tell us what you think. We appreciate your feedback!
To help approach this assignment, we've compiled some tips that may help with the various problems, as well as bit manipulation in general.
Embrace hexadecimal. The base-16 system very conveniently translates to and from binary -- each byte is expressed in two hex digits, one hex digit for the 4 high-order bits, the other for the 4 low bits. Masks in hex or expressed via their construction are more evocative of the binary representation and help you avoid mistakes. For example, a mask to extract the sign bit from a 32-bit value can be cleanly expressed as
1 << 31 or
0x80000000 and both are quite readable. The mask also happens to be decimal
2147483648U, but who can tell? Would you notice if you had accidentally mistyped
2147486348U? Say no to decimal, hex is your pal!
Learn your bitwise operators. It is wasteful to invoke the (expensive, floating-point)
pow function to compute integer powers of two:
1 << 10 does a perfect job of computing
pow(2, 10) and requires way fewer compute cycles. The bitwise operations are also the right tools to rearrange/isolate/change bits as opposed to the more indirect use of integer multiply/divide/mod with powers of two.
Aim for directness. There may be more direct ways to write certain bit manipulations. Here are a few:
No left-shift right-shift. In the code below, the first version right-shifts then immediately left-shifts back. This seems to just cycle the bits back to where they were originally, but in fact the right-shift will discard the lsb and the left-shift will then zero-fill. This is roundabout way to wipe the lsb, but the better approach is to just directly mask it off as in second version:
result = (val >> 1) << 1; // original version // Better version: result = val & ~1; // better: directly turn off lsb
No redundant/unnecessary ops. Imagine your goal is to extract the 4 high-order bits of a byte and shift them down to the lower half-byte. You could do it with two steps (mask and shift), but in fact, the shift will already discard the low-order bits, so there's no need to mask them off first!
result = (val & 0xf0) >> 4; // mask off lower 4, then shift down result = val >> 4; // better: directly shift, low-order bits gone!
Know your identities/relationships. When putting together a bitwise construction, stop and consider whether there is a more direct way to accomplish the same thing, e.g.
b = a | 0 // this is no op! b = a ^ -1 // more clearly written as b = ~a b = ~a + 1 // more clearly written as b = -a b = (1U << 31) - 1 // INT_MAX from <limits.h> b = INT_MIN >> 31 // This is -1!
At first you may find yourself using a longer expression than needed, but reviewing in a later pass, you can spot these issues and make them more concise. The goal is eventually to go straight to the most direct expressions from the beginning.
Frequently Asked Questions
How do I display values in binary?
p/t prints in the binary format. The
/t format also works for the gdb
display commands. The C
printf function does not have a binary format, but
%x will print in hex, which is the next best thing.
Are there any differences in the bitwise operations when applied to signed versus unsigned values?
The bitwise operations
& | ^ ~ << operate identically on signed versus unsigned types. The right shift operator
>> comes in two flavors: logical and arithmetic. Check out the lecture materials from Monday 1/14 for more information!
I'm getting the error
warning: left shift count >= width of type. What does this mean?
Code such as this will produce that warning:
long val = 1 << 32;
An integer constant defaults to type
int, so shifting a 32-bit int by 32 positions would effectively shift off all the bits, and thus the compiler warns about it. Assigning the result to a variable of type
long (64 bits) doesn't help; you have to start with a 64-bit value if you intend to compute a 64-bit result. Read the next question!
What bitwidth and signedness does a numeric integer constant have?
An integer literal is a signed int by default. Suffixes can be added to the constant to dictate its type. A suffix of
L indicates the type is long and
U (either by itself or with
L) indicates it is unsigned. E.g.
1UL means a literal 1 that is an unsigned long.
What are the rules for integer promotion in C?
When assigning from narrower bitwidth (e.g. char, short) to a wider one, the source bytes are copied to the low-order bytes of the destination, and the upper bytes are assigned based on the promotion rules. If the source type was unsigned, the upper bytes of destination are zero-filled. If the source type was signed, its sign bit (the msb) is replicated across the upper bytes of destination (this is called sign extension). It may help to trace through this and confirm for yourself how/why this is value-preserving. If an operation is performed on two operands of mixed type, integer promotion is implicitly applied to the narrower first. It also the case (and a bit surprising, too) that integer promotion is also applied to types narrower than int when an operation is performed on them, even if no other wider type is involved. For example, the bitshift and invert operations promote the operand to an int, so bit-shifting a char will promote to an int before shifting, bit-inverting of a char similarly promotes, and the default result type of these expressions will be int. If the bitwidth of the operand was larger than int, the bitwidth will be unchanged by these promotion rules.
My Unicode characters are not printing or appear garbled. How can I fix this?
If the characters output by the UTF-8 program do not appear correctly on your terminal, but the encoded hex bytes are correct, you may need to set your terminal to expect UTF-8. Changing the configuration is OS/terminal-specific, but within 5 minutes of Googling we found utf8 advice for Putty, MobaXterm and Xterm. The default Mac OS X Terminal.app works by default. Note that sanity check should still pass even if your terminal is showing the wrong character.