Assignment 4 advice
Written by Julie Zelenski
Before you dive in, it might help to work through some thought exercises to bring our your inner bitwise ninja. Answering these questions is not required, nor to be submitted. You are encouraged to freely discuss these warmup questions and answers with your peers (in person, on forum) to help everyone reach a solid foundation on the basic concepts before starting.
- How do you construct the mask for a single bit in the nth position? What about a mask with the lowest n bits on and rest zeros?
- How do the bits change when moving from an integer to its successor (i.e. adding one)? Is there a difference in effect depending on whether the integer is negative or positive? What about moving to the predecessor? Does anything interesting result from combining a number and its successor/predecessor with the bitwise operators?
- Left-shift and right-shift on positive values compute multiplication and division by 2. Does this also work for negative values?
- Can the same test on the underlying bits be used to determine the sign of an int as the sign of a float? Why or why not?
- What mask will extract the exponent from a float? What is the value of the bias for the exponent as stored in the float bits?
You also may find it helpful to review the bits/int/float exercises from labs 3 and 4, especially if you left tasks unfinished or feel you still have gaps in your understanding.
General advice on working with bits
- Learn hexadecimal! The base-16 system maps directly to the underlying binary patterns and is very convenient to work with -- each byte is expressed in two hex digits, one hex digit for the high-order 4 bits, the other for the low bits. A little upfront practice to get comfortable reading/expressing values in hex will pay off in spades any time you are working with bits.
- Build expressions from your understanding of bits/binary. This means embracing hex values and bit-shifted constants instead of their decimal equivalents. 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 unsigned decimal value
2147483648, but who can tell? Don't make yourself (or the reader) have to translate between binary and decimal to follow along.
- In a similar vein, it is foolish to invoke the (expensive) pow function to compute values that can be directly expressed using simple bit shifts. For example, calculating
pow(2, 31) is equivalent to 1 << 31, but costs orders of magnitude more compute cycles. Similarly using integer multiply, divide, and mod by powers of two to move/isolate/change bits is wasteful when the bitwise operations can do these tasks directly and efficiently.
- It is typically most appropriate to qualify types as explicitly
unsigned that you intend to manipulate bitwise. By declaring as unsigned, you will avoid any special treatment of the most significant bit as a sign bit. Whereas the bitwise operations & | ^ ~ and << don't give any special status to the MSB, you have to take care with the right shift operator >> . A logical right shift always shifts zeros in to fill the vacated bits on the left, an arithmetic right shift copies the previously leftmost bit to fill the vacated bits (thus replicating the sign bit). Right shifting a unsigned value always performs a logical shift. Right shifting a signed value performs an arithmetic shift using our gcc compiler. (However, the C standard leaves this choice up to the implementation, so you could run into a different behavior on another compiler).
Students who aren't yet comfortable with bits often end up expressing operations in roundabout/convoluted ways. For example, compare the two approaches below for testing the third bit of a value:
shifted = val >> 3; // shift target bit over to lsb
if ((shifted & 1) != 0) ... // then test if lsb is on
// Better version:
if ((val & (1 << 3)) != 0) ... // test target bit in-place with mask
The first version right-shifts the bits over to get the target bit in the 0th position and uses a mask to test the LSB, where as the second tests the target bit in place using a targeted mask. The second is preferred--- it is more idiomatic and the mask can be optimized into a compile-time constant and moved to a #define constant for readability.
Here's another example: you need 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 no need to mask them off first:
masked = val & 0xf0; // hex f0 is 1111 0000 in binary
result = masked >> 4;
// Better version:
result = val >> 4; // instead just directly shift, low-order bits gone!
And lastly, look at this bit of code below that right-shifts then immediately left-shifts back. At first glance, this seems like it would just cycle the bits back to where they were originally -- what's the point? Trace carefully, the right-shift will discard the LSB and then zero-fill it when left-shifting. This is roundabout way to wipe the LSB, but the better approach is to just directly mask it off as the second version below does:
result = (val >> 1) << 1;
// Better version:
result = val & ~1; // turn off LSB if on
At first you may find yourself using the more long-winded expressions as you think it through, but reviewing in a later pass, you can spot these issues and clean them up. Eventually you want to become facile enough with bit manipulations that you go straight for the streamlined, direct expression from the beginning.
Remember gdb can print/examine in binary using the
t format (e.g. using
/1wt ). That will come in handy when working with bits.
- The sign bit (most significant) is not treated specially, it contributes to the count just like all other bits.
- One approach is to write a helper to counts the "on" bits in an integer, call the helper to get the two counts, and return their difference. A simple approach to bit-counting is a tight loop to individually mask out each bit and increment a counter. This strategy is perfectly acceptable.
- There are alternative approaches for
cmp_bits that don't rely on counting, but instead take advantage of the bitwise properties. For example, it is possible to quickly eliminate the bits in common since they don't change the comparison result. You can also streamline by processing both integers in a single loop and stopping as soon as you can determine the result. If you go this route, we encourage you to play around with how you can streamline, as this exploration will strengthen your understanding of bitwise manipulation, but we will accept any simple, reasonably efficient implementation (such as the dual bit-count and subtract).
- One entirely off-limits function is the gcc
builtin_popcount. You might find it a useful testing tool to compare against your own counter, but will receive no credit for using it to implement bit counting.
- Optional extracurricular diversion: Algorithms for fast bit-counting are a perennial interview question and there are many fancy solutions. A Google search will turn up many discussions explaining various approaches and arguing their merits. These algorithms are also O(N), but reduce the constant on the linear term. These clever ideas make interesting reading and we encourage your exploration but only after you've finished your own implementation, otherwise, is easy to be overly lead by the work of others and compromise the opportunity to do your own thinking and coding. The CS107 policy is that code you submit should be something you wrote yourself, not copied or adapted from the code/pseudocode of others.
- It may help to work out how the bitwise combinators
^ can be thought of as operations on two sets. What is the effect of bitwise
& as a set operation? What about
- Depending on your approach, the crux of
is_single may come down to being able to efficiently determine if only a single bit is on. A simple tactic is to count "on" bits and compare the count to 1, but this is one of the inefficient/looping approaches that we mention can work but isn't the most direct. Instead think about which bit patterns have a single "on" bit. What do they represent numerically? Is there anything interesting about those numbers and their relationship to other nearby numbers that could help you identify whether you have one of those numbers or not?
- Your first task will be to identify the bit-count of the incoming Unicode code point. One simple way involves scanning from most significant bit to least significant to find the first on bit. This task has a lot in common with
cmp_bits. As an alternative, you can consider what is the relationship between a value and its bit-count. What values have bit-count 2? What values have bit-count 7 or 8?
- Once you have the bit-count sorted out, you will likely use three separate cases to handle single byte, 2-byte and 3-bye code points. For each case, you have to extract the bits from the code point and rearrange them into the proper form for the UTF-8 encoding, and attaching the proper leading bits in place as necessary. This is great practice with bit masking and shifting!
- If you find that the characters being output by the UTF-8 test do not appear correctly on your terminal, but the hex values seem right, 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 unchanged. Note that sanity check should still pass even if your terminal is showing the wrong character.
- Start by thinking through what makes sum not be representable. You can choose to either detect the problem by foreseeing that over/underflow will occur if you were to add the operands or by computing the sum using the regular (unsaturating) addition and observing that over/underflow did occur.
- Once you can correctly identify saturating inputs, construct the appropriate pegged result to return, i.e. the minimum or maximum value for the given type. It may help to work out the bit patterns for the minimum/maximum, and use that understanding to construct the value in a bitwise fashion. (If you need help understanding the range for given type, the limits.h header file #defines
UINT_MAX and so on for char/short/etc. These constants can't be directly used in your saturating operations as they are bitwidth-specific, but you can examine the values to discern their patterns).
- You are free to use any of the integer arithmetic and relational operators and/or the bitwise ops in your solution.
- You can assume the utype/stype pair will be typedef'ed to the same bitwidth. The unsigned operation won't care about stype, but the utype may have a role to play in implementing the signed operation, depending on how you implement it.
- Some (but not all) approaches make use of an integer literal. It may be helpful to know that an integer literal is of type
int by default. You can add a suffix to the constant to dictate its type. For example, a suffix of L indicates the type should be long, LL is for long long. You can also use U (either by itself or before L or LL) to indicate you want the constant to be unsigned.
- Another important C detail concerns implicit promotion within the integer family types. The binary arithmetic and bitwise operators applied to operands of integer type with smaller bitwidth than int will implicitly promote the narrower type to the wider (i.e, adding a char to a int will first promote the char to an int, then add the two ints; similarly for bitwise
& applied to a char and an int). The bitwise shift 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.
- You'll likely find the portability across all bitwidths the trickiest part of the task. A good approach is to concentrate on correctness for single fixed bitwidth and only then generalize to any bitwidth. A good understanding of the integer family promotion/truncation rules is essential. If you've feeling all-powerful, you can come up with a solution that won't even use the
- The bitwidth of
stype/utype is controlled by the
SAT_CHOICE #define at the top of
bits.h. The starter Makefile includes additional targets (char, short, int, long and longlong) that configure the #define and rebuild bitstest. This is a more convenient way to try different bitwidths that repeatedly editing the bits.h file (although the latter does work as well).
- If the sequence you have in mind consists of just a handful of values, a static initializer is a handy way to define a short fixed sequence. However, if you are using a longer sequence as the trigger for a certain kind of pattern, it will be more convenient to fill in the sequence using a loop or other C code. No matter how you fill in your sequence, be sure to add INFINITY after the final value to properly terminate the sequence.
- Be sure the values in your sequence are not being rounded on assignment. By starting with values that are exactly representable, you will limit the rounding issues to only what occurs during the computation of average, making it easier for you to reason about and judge what is the correct result. Our provided
echo_sequence function will echo back the values assigned into your sequence. Look carefully to spot values that were rounded on assignment and adjust them as necessary.
- You will probably want to put off working on sequence #4 (the input that is incorrect on all) until after you have worked through the first three sequences. After you are better acquainted with the strengths and weaknesses of each version, you can mash together a sequence that simultaneously hits all their vulnerabilities.
- You can play around and rework the various average functions to better understand how they operate, but in grading we will be using the original versions of average/A/B/C, so be sure that your sequences will correctly demonstrate the required outcomes on the unmodified original code.
- Optional extracurricular diversion: A different strategy for reducing the error in a sequence of floating point addition operations is "compensated summation". This a simple yet powerful technique is due to Kahan, the genius behind the design of the IEEE 754 standard. The Wikipedia page on Kahan summation is good place to learn more. It's quite a clever algorithm— check it out! How do you estimate a version of average that uses Kahan summation would fare?
- Your job consists of two related tasks: calculating what the epsilon value is for a given float and then manually constructing its bit pattern.
- We recommend you start by first working out an intuitive understanding of what epsilon represents and its relationship to a given float value. How does the epsilon change as you move along the floating point number line? Where on the number line does it change? What must be true about two float values for them to have the same epsilon?
float.h header defines a constant
FLT_EPSILON. The name suggests it could be the resolution between any pair of neighboring float values (impossible!) or perhaps some minimum magnitude float, but it's much less exciting than that.
FLT_EPSILON is defined as the distance from the float value 1.0 to its next higher neighbor.
- Be sure to consider whether/how a denormalized input might require different handling than a normalized value.
- Your solution can use any of the integer and bitwise operations, but code that makes any use of floats (types, constants, variables, operations, etc) will receive no credit. No floats means also no floating point functions (log, pow, floor, round, fabs, etc.) Be absolutely sure you are in compliance!
- To test, you can manually create a raw instruction by assigning the desired bytes in an array of unsigned char and passing that array to
disassemble. It will be helpful to ask gdb to disassemble the same bytes as a comparison for testing. The
x/i command in gdb will examine a memory address and prints its contents disassembled into instructions.
- To further explain the anomaly mentioned in the writeup: there is an ambiguity if the second opcode byte is 01110100. This bit pattern matches both the opcode for the scaled-index subtype and indirect-with-displacement on register
%esp. Which is it? The explanation is that
%esp is disallowed as the base in an push indirect-with-displacement because its register code is overloaded to use as the marker for the push scaled-index subtype. The ISA designers had to sacrifice one register to do this and chose the register they deemed least likely to be used. This means
%esp as base for indirect-with-displacement has to be encoded using the longer scaled-index form. There is a somewhat similar overlay on the push indirect with
%ebp as base. This choice by the designers avoids consuming another bit of encoding for most cases, while making one special case longer. (oh, the joys of CISC architectures...) For the purposes of the assignment, just ignore the possibility of the base being
%ebp for indirect or indirect-with-displacement. This avoids the ambiguity and you won't need to make a special case out of anything.
Advice on testing
- Your testing effort on this set of diverse problems will benefit a mix of approaches, including creating your own test inputs, writing test code, and a mix of black-box and white-box strategies.
- To achieve targeted coverage of the corner cases, you want to specifically identify the oddballs -- values that are different that the others, who represent the extreme edge of the range and the like. Wherever you have special cases in the code will likely dictate the need for special case inputs for testing. Be thorough!
- To get widespread coverage, you might this a good time to experiment with fuzz testing. For this, you generate a large number of inputs which with to bombard your function. If the input space is relatively constrained and easily iterated, you can simply test every single value. If the population is much larger, you can randomly sample from it.
A note on gdb and float/doubles
You can invoke function calls at the gdb prompt and it will make a valiant effort to invoke the function and print its result. This is pretty handy for working more interactively/experimentally. But be warned that the mechanism can be a little squirrely. For example, if the called function takes or returns variables of float/double type, you may get garbled results. The issue has to do with gdb not having access to the complete type information and doing a bit of guessing. You can add a typecast on the function being called (to its proper type, of course) to force the right interpretation. For example:
(gdb) p fabs(-3.5)
$1 = 1 // huh ??? why is result from fabs so wrong?
(gdb) p ((double (*)(double))fabs)(-3.5) // tell gdb fabs takes double, returns double
$2 = 3.5
Consider this the one exception to the rule that you should never ever cast a function pointer. :-)
- Code size. Our bits.c has 87 lines. Submissions have ranged from 50 to 250 lines. This are counts of programming statement lines (not including blank lines, comments, #include).
- Number of mercurial commits. The count of Mercurial commits averaged was 11, the high over 40.
- Points earned. The median assignment score has been around 85% of the total points.
A little bit
Little bit of beet.
Because he liked the taste of it.
But when he bit
A wee bit more,
It was more bitter than before.
"This beet is bitter!"
"I feel a bit unwell inside!"
But when he bit
Another bite, that bit of beet
Seemed quite all right.
When all is said and done,
Better bitter beet
-- Mary Ann Hoberman