In this topic, we'll do several lecture segments to analyze the assembly code generated from program Primes.c. This is a larger program than any we've analyzed, and it makes heavy use of bitwise operations -- assembly instructions that operate on register contents as patterns of bits, not binary numbers.
Primes.c examines the numbers from 0 to 319 to determine which are prime. It records prime/nonprime status for each of those 320 different numbers using an array primeSet of just 10 32-bit ints. How it does so is the main point of the program.
Primes.c uses one bit per number, setting the bit to 0 if the number is nonprime and 1 if the number is prime. Each 32-bit int in primeSet thus stores primeness information for 32 values. primeSet[0]'s bits indicate primeness for the values 0-31, with the LSB indicating primeness for 0, and the MSB indicating primeness for 31. Since 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31 are prime, this means primeSet[0] will look like this when the program is done:
10100000100010100010100010101100
Be sure you see how that bit pattern corresponds with the list of prime values in the range 0-31.
There are a total of 320 bits in the entire array primeSet, and remaining elements store primeness for the values 31 through 319.
Which index of primeSet has the bit for the value 119? How in general do we compute which index of primeSet to use, given a value V? (Check your rule against 319, which should yield index 9, and 31, which should yield index 0.)
Answer 1
Now, how do we choose which bit within that element represents a given value?
Let's start by numbering the bits in each element from 0 (LSB) to 31 (MSB). This right-to-left numbering, from least to most significant instead of the reverse, may seem a little odd. But it turns out to be convenient to number bits this way within an int. For instance, note that each bit is numbered according to the power of 2 that is its place value. The LSB has place value 2^0, and the MSB has place value 2^31.
Given this numbering system, we see that values 0-31 are represented by bits 0-31 in primeSet[0]. Values 32-63 are represented by bits 0-31 is primeSet[1], etc.
What simple computation will give us the right bit number within the array element, given a value V? Check your rule against 0 (which should be bit 0) and 319 (which should be bit 31).
Answer 2
The setBit function at the end of Primes.c uses the two equations just discussed to pick out an individual bit in primeSet and set it to 1. It takes several steps to do this, and it's important to understand them before we look at their assembly translation.
Parameter prime gives the number of the bit to set, from 0 to 319. setBit picks the right index of primeSet, and uses bitwise operations to set just one bit in that element to 1 without changing the others.
The right index, per discussion above, is prime/bitsPerInt. (bitsPerInt is a constant 32.) And the right bit number is prime % bitsPerInt.
This C expression:
1 << prime % bitsPerInt
performs a left shift, an operation we discussed in a prior lecture. It shifts the bits of the first operand (1) to the left by as many positions as indicated by the second operand (prime % bitsPerInt). Any pair of integer operands is allowed. The 32-bit pattern for 1 is:
00000000000000000000000000000001
If prime % bitsPerInt is, say, 21, then the result is that bit-pattern shifted left by 21 positions, or:
00000000001000000000000000000000
C has a >> rightshift operator as well, and we'll use it later in the discussion. It performs either an arithmetic right shift or a logical right shift (recall the distinction from prior lecture) depending on whether the integer operands are declared signed or unsigned.
That left-shifted 1 is the second operand in an expression using |:
primeSet[prime/bitsPerInt] | (1 << prime % bitsPerInt)
The C | operator does a bitwise or operation. It takes two integer operands, treats both of them not as numbers, but as bit patterns, and does a logical "or" operation on each pair of bits, one from each operand. Here's an 8-bit example:
01101100 A 10100110 B 11101110 A | B
The A | B operation creates an integer with a bit pattern in which each bit is the "or" of the corresponding bits in the two operands A and B. If either or both bits are 1, the result is a 1 bit. Only if both bits are 0 is the result bit 0.
The | operator is good for setting individual bits in a value without changing any other bits, and setBit uses it to turn on the correct bit for value prime. Say, for instance, that prime is 53. Then we'd be dealing with bit number 21 in primeSet[1]. Let's assume primeSet[1] already has 1-bits for primes 37, 41, 43, and 47. The two operands would then be as shown below. And the result of the | operation is as shown, with each pair of corresponding bits "or-ed" together to produce one bit of the result. The | operation keeps the existing 1's in primeSet[primes/bitsPerInt] even though they are matched by 0's, and also sets the 1-bit we want. Function setBit copies this result back into primeSet[prime/bitsPerInt], completing the task.
00000000000000001000101000100000 primeSet[primes / bitsPerInt] 00000000001000000000000000000000 1 << prime % bitsPerInt --------------------------------- 00000000001000001000101000100000 primeSet[primes / bitsPerInt] | 1 << prime % bitsPerInt
There is also a C & operator, which works exactly like | except that it does an "and" on each bit pair. The resulting bit is 1 only if both corresponding bits in the operands are 1; otherwise it's a 0. We'll use the '&' operation in the main function.
CheckNum checks parameter toTest to see if it is prime, by looping through all possible divisors to see if any divide evenly into toTest. If the loop passes through all divisors without finding an even division, then checkNum adds toTest to primeSet by calling setBit. CheckNum returns true if this happens, false otherwise.
There is one new concept in checkNum that will show up in the assembly. The condition
divisor < toTest && toTest % divisor != 0
is short-circuited. C ensures that if the first operand (e.g. divisor < toTest) of an && clause is false, then the second half isn't even run. There's no point in doing so since a false first operand ensures the && is false regardless of the second operand's truth or falsity. We'll find that the assembly code jumps over the second operand of the && clause in this case.
Take a moment to be sure you understand the rest of the code in checkNum. It's fairly straightforward, with the loop ending either upon finding an even divisor, or reaching the toTest limit, and then the if-statement and return value using divisor == toTest to in effect say "no even divisors were found".
The main function declares relevant variables, sets all values of primeSet to 0 so all bits are initially 0, and then runs through the values from 2 to 319, passing each to checkNum to set the proper bit in primeSet if the number is prime. Variable totalPrimes counts the number of primes.
By the end of the second for-loop, primeSet will have 1-bits for each prime value less than 320.
The final for-loop runs through all the elements of primeSet and prints the relevant prime number for each 1-bit in primeSet. The if-test it uses needs some analysis:
primeSet[toTest/bitsPerInt] >> (toTest % bitsPerInt) & 0x1
What bit from will be in the LSB position in the bit pattern resulting from the shift operation? Will it be a 1-bit or 0-bit? Why? (Recall that >> represents a right shift.)
primeSet[toTest/bitsPerInt] >> (toTest % bitsPerInt)
Answer 3
toTest. It'll be a 1-bit if toTest is prime.
The expression picks the primeSet element containing toTest's bit, and then shifts that element to the right by the bit number for toTest, leaving toTest's bit in the LSB spot.
Here's an example, assuming toTest is 53, so we're shifting primeSet[1], which contains 1-bits for the primes from 32 to 63, including one for 53 partway up, which we'll call the "53-bit". The 53-bit moves down to the LSB after the shift.
00101010001000001000101000100000 primeSet[toTest / bitsPerInt] 00000000000000000000000101010001 primeSet[toTest / bitsPerInt] >> (toTest % bitsPerInt)
We need to test to see if the 53-bit is 1. Since integers are true/false values in C, it's tempting to just use that shifted result as the needed test. Why can't we?
Answer 4
So, we need to "knock out" all the other bits aside from the LSB. We can do this via an & operation with the value 1, which has 0s in all bit positions but the LSB. All bit pairs but the LSB will be 0 after the &, and the LSB will be 1 only if the 53-bit is 1.
00000000000000000000000101010001 primeSet[toTest / bitsPerInt] >> (toTest % bitsPerInt) 00000000000000000000000000000001 1 --------------------------------- 00000000000000000000000000000001 primeSet[primes / bitsPerInt] >> (toTest % bitsPerInt) & 1
This is the test we need, and main uses it to decide whether to print toTest.
That concludes our look at the C code. In the next segments, we'll look at the assembly translations of setBit, checkNum, and main.