CS233 Lab 2 Handout
“Beware of bugs in the above code; I have only proved it correct, not tried it.” – Donald E. Knuth
Learning Objectives
1. Combinational logic design.
2. Using bitwise logical and shifting operations in a high-level language like C++.
Work that needs to be handed in
These files need to be submitted by the first deadline:
1. keypad.v: Modify as described in the Keypad section. We’ve provided an exhaustive test
suite in keypad_tb.v.
These files need to be submitted by the second deadline:
1. extractMessage.cpp: Modify as described in the Encryption section.
2. countOnes.cpp: Modify as described in the Count Ones section.
Compiling, Running and Testing
If you’re on EWS, you’ll need to get your PATH set up to be able to easily access various tools
throughout the semester. Run the following command to do so; once again, this is only necessary
on EWS. Google “shell PATH” and take a look at the source of the script if you’re interested in
what’s happening under the hood.
source /class/cs233/setup
We have included a Makefile in your Lab2 directory that facilitates compilation. The following
examples illustrate its use:
make keypad – compiles the keypad circuit and runs its test bench
make extractMessage – compiles the extractMessage program
make countOnes – compiles the countOnes program
make clean – removes all compiled files
To test message extraction, run the following command, which calls your extractMessage function
on the default test message. A correct implementation should print out
Knock knock.
Race Condition.
Who’s there?
./extractMessage
1
CS233 Lab 2 Handout
To test Problem 2, run the command ./countOnes
correct implementation should print out the number of bits that are 1 in that number. You can use
0b to prefix binary constants and 0x to prefix hexadecimal constants. A few examples:
./countOnes 55 – should print out 5
./countOnes 0xbaadf00d – should print out 17
./countOnes 0b10110100 – should print out 4
2
CS233 Lab 2 Handout
Keypad
Consider the telephone style key pad shown below. This key pad supports numerical buttons 0-9
and has 7 output signals a-g. When no buttons are being pressed all of these signals output a 0.
When a button is pressed a 1 is output on both the row and the column of the button pressed (e.g.,
if 6 was pressed c and e would be 1 and all of the other signals would be zero).
1 2 3
4 5 6
7 8 9
0
a b c
d
e
f
g
Your job is to design a circuit that indicates numerically which button is being pressed (assuming a
single button is pressed at a time). Your circuit will take the 7 signals (a-g) as inputs and produce
two outputs: the 1-bit signal valid indicating that a numbered button was pressed, and the 4-bit
signal number specifying which number button was pressed (encoded as a binary number).
Write boolean expressions for these signals:
valid =
number[3] =
number[2] =
number[1] =
number[0] =
3
CS233 Lab 2 Handout
Encryption
Encryption1 is the process of encoding messages or information in such a way that only authorized
parties can read it. Here, we will look at a simple method of “encrypting” a text message as an
encoded string. Your task is to write a C++ function to decode these encoded messages. (Note:
your function will also serve as an encoders, as the encode and decode process are identical.)
Messages are encoded/decoded according to the following scheme:
(a) First, each character in the message is encoded in 1 byte (8 bits) according to its ASCII code2.
For encoding/decoding purposes, the length of the message must be a multiple of 8 bytes. The
length of the message must be provided to the encoder/decoder along with the message itself.
(b) Each group of 8 bytes is encoded/decoded independently.
(c) Within each group of 8 bytes, we’re going to “reflect” the bits, so that the bits of the ith byte of
the input becomes the ith bit of each of the 8 bytes of the output, with the LSB of the ith byte
becoming the ith bit of the 0th byte of the group. (Alternatively, you could view this as least
significant bits (LSbs) of each group of 8 input bytes containing the bits of the first character of
the group of 8 output bytes, the second LSbs containing the bits of the second character, …,
the most significant bits (MSbs) of the 8 characters containing the bits of the 8th character.)
As an example, say we’re given the message:
Hello World! If we represent this as a set of bits in ASCII, pad it with the null character, and
perform the scheme above, the transformation will look like this:
H 0 1 0 0 1 0 0 0
e 0 1 1 0 0 1 0 1
l 0 1 1 0 1 1 0 0
l 0 1 1 0 1 1 0 0
o 0 1 1 0 1 1 1 1
0 0 1 0 0 0 0 0
W 0 1 0 1 0 1 1 1
o 0 1 1 0 1 1 1 1
r 0 1 1 1 0 0 1 0
l 0 1 1 0 1 1 0 0
d 0 1 1 0 0 1 0 0
! 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
→
o W o l l e H
210 1 1 0 1 0 0 1 0
208 1 1 0 1 0 0 0 0
222 1 1 0 1 1 1 1 0
157 1 0 0 1 1 1 0 1
64 0 1 0 0 0 0 0 0
190 1 0 1 1 1 1 1 0
223 1 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0
! d l r
8 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 1
6 0 0 0 0 0 1 1 0
2 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1
15 0 0 0 0 1 1 1 1
7 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0
1Encryption: https://en.wikipedia.org/wiki/Encryption
2ASCII codes: http://www.asciitable.com
4
CS233 Lab 2 Handout
The transformation is a transposition of the matrix of each character’s bits along their secondary
axis.
The extractMessage_main.c contains the following message encoded according to the above
scheme:
Knock knock.
Race Condition.
Who’s there?
What you need to do
The C++ function extractMessage in the file extractMessage.cpp accepts two parameters, a
pointer to a character array and the length of that character array; Complete it so that it extracts
the encoded message according to the scheme just described into the provided character array
and returns a pointer to it. To do this, your code must use bitwise logical and shifting
operations in C++.
5
CS233 Lab 2 Handout
Count Ones
In this problem, you will write an efficient C++ function to count the number of bits that are equal
to one in an unsigned integer. Here is a simple (but inefficient) way to solve the problem:
unsigned countOnesDumb(unsigned input) {
int i, count;
count = 0;
for (i = 0; i < 8 * sizeof(unsigned); i++) {
if ((input & 1) != 0) {
count++;
}
input = input >> 1;
}
return count;
}
This is inefficient, because it takes O(n) operations3 on n-bit numbers to count the number of ones
in an n-bit integer. We want you to write a function that performs only O(log2 n) operations on
n-bit numbers for this task.
Here is a description of an efficient algorithm for this problem (you can assume that integers are 32
bits long):
(a) Treat each integer as 32 1-bit counters. Pair adjacent counters off, and add each pair. The
result will be 16 2-bit counters.
(b) Take these 16 2-bit counters and pair adjacent counters off. Add the pairs of counters to produce
8 4-bit counters.
(c) Keep pairing and adding in this fashion until you get a single 32-bit counter, which will contain
the result.
Is this really efficient? Think about step 1 of this algorithm. For each pair of bits, we need to
perform one addition operation – this means n/2 additions for an n-bit number. For step 2, we need
to perform one addition operation for each of the 16 2-bit counters – this means n/4 additions are
required for this step. We can continue this trend until we are left with a single 32-bit counter.
After all steps are complete, we are left with an algorithm that requires O(n) operations!
The trick to achieve O(log2 n) is to do all these additions together (in parallel). In what follows,
we’ll show you how to do this with an example. To keep things simple, we’ll work with 8-bit integers.
3Recall from CS 125/173/225: O(n) means (roughly) at most c · n, for some constant c > 0
6
CS233 Lab 2 Handout
What you need to do
The C++ function countOnes in the file countOnes.cpp accepts an unsigned integer as the input;
complete it so that it efficiently counts and returns the number of occurences of 1 in the binary
representation of the input 32-bit integer using the algorithm described below, and without
using loops or conditionals.
Doing things efficiently
Suppose the input integer is 10110110. We treat this as eight 1-bit counters. First, let’s isolate
every alternate counter in this integer. We can do this by AND-ing the number with the bit-pattern
01010101 (i.e. 0x55)
1 0 1 1 0 1 1 0 (Our starting number)
AND 0 1 0 1 0 1 0 1 (The appropriate mask for the odd 1-bit counters)
——————–
0 0 0 1 0 1 0 0 odd counters
Next we get the other counters, this time by AND-ing with the bit-pattern 10101010 (i.e. 0xAA)
1 0 1 1 0 1 1 0 (Our starting number)
AND 1 0 1 0 1 0 1 0 (The appropriate mask for the even 1-bit counters)
——————–
1 0 1 0 0 0 1 0 even counters
Now we need to pair-up adjacent counters and add them. We can do this by first RIGHT-SHIFTING
the even counters by 1 to align them with the odd counters, and then simply adding the two numbers:
0 1 0 1 0 0 0 1 even counters RIGHT-SHIFTED by 1
+ 0 0 0 1 0 1 0 0 odd counters
——————–
0 1 1 0 0 1 0 1
This completes step 1 of the algorithm. It takes 4 operations (two ANDs, one RIGHT-SHIFT and
one + operation) in the case of 8-bit integers, and will similarly take 4 operations in the case of
32-bit integers.
Moving on to step 2, we need to treat the number 01100101 as four two-bit counters as follows:
0 1 1 0 0 1 0 1
\ / \ / \ / \ /
= 1 2 1 1
We will need appropriate bit-patterns to obtain alternate counters like before. However, because
our counters are now two-bits each, the patterns also need to represent that change.
7
CS233 Lab 2 Handout
Firstly, isolate the odd counters
0 1 1 0 0 1 0 1 (The output of adding both 1-bit counters)
AND 0 0 1 1 0 0 1 1 (The appropriate mask for the two-bit odd counters)
——————–
0 0 1 0 0 0 0 1 odd counters
Likewise, we repeat this step for the even counters:
0 1 1 0 0 1 0 1 (The output of adding both 1-bit counters)
AND 1 1 0 0 1 1 0 0 (The appropriate mask for the two-bit even counters)
——————–
0 1 0 0 0 1 0 0 even counters
Again, we align the counters (this time by right-shifting the even counters by 2) and add them:
0 0 0 1 0 0 0 1 even counters RIGHT-SHIFTED by 2
+ 0 0 1 0 0 0 0 1 odd counters
——————–
0 0 1 1 0 0 1 0
= \ / \ /
3 2
Finally, we treat 00110010 as two 4-bit counters (as shown above) and add them to get the final
answer: 5.
8