In this segment we'll look more closely at how bits behave during binary addition and subtraction, and at how the CPU tests for various arithmetic conditions based on that behavior.
Earlier lectures introduced the cmp instruction, followed by tests based on the result of the "comparison" perform by cmp. This instruction pair, for instance, assigns r2 into r1 only if r2 is greater than r3:
cmp r2, r3 movge r1, r2
Now that we've got more knowledge of binary arithmetic, let's look more closely at just what cmp does, and how the results of its comparison are recorded by the CPU.
Cmp performs a subtraction. It's like a sub, but without saving the result. What it does save, however, is whether the result was a zero or not, and whether the result was negative or not. These two true/false values are stored in the program status register or PSR . Earlier lectures promised more registers than r0 - r15, and the PSR is the next one. The PSR doesn't store a single number like the other registers. Instead, each of its 32 bits has a specific purpose. Two of those 32 bits, termed the Z and N flags, represent whether the most recent cmp result was 0 (the Z flag), or negative (the N flag).
An assembly instruction that is conditioned on the results of an earlier cmp checks the PSR bits, and executes, or doesn't, based on their state. ARM assembly uses a pair letters after the assembly opcode to indicate this, so movge is a mov, conditioned on a greater than or equal outcome. Many other two-letter conditions are allowed. moveq for instance, would do a move only if the compared values were equal.
Given that cmp performs a "test subtraction" on its arguments, what combination of N and Z flag values would make a subsequent moveq instruction execute?
Answer 1
There are two more PSR flags that result from arithmetic operations. Both deal with overflow conditions during addition and subtraction. Overflow occurs when addition or subtraction produces a result that is beyond the range of the integer in question, either too high a value or too low a value. A too-low value doesn't sound like an "over" flow, but it's still called that.
It's useful to consider how overflow happens, and is detected, in both signed and unsigned cases. Let's do that, sticking with the easy-to-discuss 8-bit case. In practice integer operations are almost always at least 16-bit or higher, but the 8-bit example extends easily to larger ints.
Let's start with overflow for unsigned 8-bit ints. Recall the allowed range for such ints, from 0 (00000000) to 255 (11111111).
Question 2 Recall the earlier discussion on modular arithmetic. In 8-bit arithmetic, 256 "wraps back" to 0. So, what value do we get if we add two unsigned 8-bit ints with values 220 and 50?
Answer 2
Overflow in unsigned ints happens when the value wraps back like that. If this happens, the CPU sets a PSR bit called the carry flag.
To understand why it's called that, consider the decimal car odometer example from earlier lecture. [SPM: why not just say 9+1 means a 1 is carried into the tens place, and the carry bit is set for the specific case of the MSB carrying? The odometer example, in my opinion, really just says what happens to it, not why its called the carry bit] What would happen if we added 600,000 and 500,000 on that odometer? The addition of 6 and 5 in the leftmost place would result in a carry into the one-millions place. But the odometer lacks that place, so the carry is simply lost. In fact, this is how the wrap-around occurs on the odometer -- by dropping anything carried into the nonexistent millions-place.
We haven't discussed binary addition in this class; it's more of a hardware topic. But the process of adding place values and carrying the excess into the next place happens during binary addition in much the same way as in decimal addition. The carry just happens when the sum of bits exceeds 1, instead of when the sum of digits exceeds 9. And, when a carry occurs when adding the MSBs, that indicates a wraparound, just as in the car odometer. The carry flag is set when a carry occurs from adding the MSBs, thus its name.
There is, however, another case to consider: subtraction. If we subtract a larger unsigned value from a smaller one, that also involves a wrap around zero, but in the downward direction. How does the CPU detect this?
Back to the odometer. What value would we get from subtracting 2000 from 1000 on the odometer? And what would the borrowing look like in such a subtraction? Would anything be "borrowed" from the millions-place? Try it by hand, subtracting 002000 from 001000, using the usual gradeschool procedure.
Answer 3
In the odometer, subtractive overflow is indicated by borrowing in the leftmost digits. And in the binary case, subtractive overflow is indicated by a borrow when subracting the MSBs. The carry bit is also set when this happens, and it thus covers both types of overflow. It should probably have been called the "carry/borrow" bit.
OK, so the carry bit covers any case of unsigned overflow. What about overflow for signed values?
Question 4 Considering how two's complement works, is wrapping around zero necessarily a problem when adding signed values? If not, in what case is it OK?
Answer 4
Question 5
So if wrapping around zero is OK in two's complement operations, what is not OK? Assuming
Answer 5
For instance, adding 100+50 in signed values results in what would be unsigned 150, but is signed -106, because that 127/-128 boundary was crossed.
But, how do we know whether the operation crossed it?
Can overflow occur if we add a positive and a negative?
Answer 6
So, to get overflow, we need to add two positives, or two negatives. Putting that differently, the MSBs of the two operands must be the same for an overflow to be possible.
So, what kind of result do we get from signed overflow when adding same-sign operands? Say we add two 8-bit positive values like 120 and 110. They'd sum to 230 in unsigned form, but what is that in signed form? Answer the same question for adding -120 and -110.
Answer 7
Even adding -128 and -128 results in 0, not a negative value. And adding 127 and 127 results in -2, not a nonnegative value.
So, the "acid test" of signed overflow is that the two added values have the same sign, both negative or both positive, but the result has the opposite sign.
This condition is what the PSR V flag detects. (V is for oVerflow.)
OK, so we have both the C flag for going across the zero boundary, and the V flag for going across the 127/-128 boundary. (Or, actually whatever the two's complement boundary is for the values being added. 32-bit addition sets the V flag if the result crosses the 2,147,483,647/-2,147,483,648 boundary, for instance.)
How does the CPU know whether we're doing signed or unsigned math? There aren't different assembly instructions for the two forms. It's all the same hardware doing the same operations; remember the distinction between signed and unsigned is just a viewpoint. So, the CPU sets both C and V flags, and it's up to us to choose which one to test if we want to know whether there was an overflow.
Such tests are sometimes done at the assembly level, but most compiler-generated assembly leaves it up to the programmer to be sure no overflow occurs, since the overhead of testing every operation would slow down the program. That's one reason for knowing the symptoms of overflow. If you add two unsigned values and get a smaller unsigned value, or if you subtract unsigned values, and get a larger unsigned value, that's arithmetic overflow. Likewise if you do add operations on two positive signed values and get a negative value, or vice versa, that's overflow.