double precision integer subtraction with 32-bit registers(MIPS)

Question

I am learning computer arithmetic. The book I use(Patterson and Hennessey) lists the below question.

Write mips code to conduct double precision integer subtraction for 64-bit data. Assume the first operand to be in registers $t4(hi) and $t5(lo), second in $t6(hi) and $t7(lo).

My solution to the answer is

sub  $t3, $t5, $t7   # Subtract lo parts of operands. t3 = t5 - t7
sltu $t2, $t5, $t7   # If the lo part of the 1st operand is less than the 2nd,
                     #   it means a borrow must be made from the hi part
add  $t6, $t6, $t2   # Simulate the borrow of the msb-of-low from lsb-of-high
sub  $t2, $t4, $t6   # Subtract the hi's. t2 = t4 - t6

However the author given solutions for this problem are as below

For signed double precision integers,

subu $t3, $t5, $t7   
sltu $t2, $t5, $t7  
add  $t6, $t6, $t2
sub  $t2, $t4, $t6

For unsigned double precision integers,

subu $t3, $t5, $t7   
sltu $t2, $t5, $t7  
addu $t6, $t6, $t2
subu $t2, $t4, $t6

My understanding of the difference in operation of sub/add and subu/addu is that overflow-exception is generated in sub/add and not in subu/addu. Both sub/add and subu/addu subtract/add the bits of the operands and the interpretation of the operands being signed or unsigned makes no difference to the result unlike in slt and sltu instructions.

Question 1
I am inferring from the author given solutions that overflow detection is being handled whereas I did not think of the same in my solution. Am I right? Is there any other thing I am missing?

Question 2
Assuming that my above inference is right, why is overflow detection switched off for the author provided solutions in the case of subtraction of unsigned double precision by the use of addu and subu?

Answer 1

For addition and subtraction, there is no difference between signed and unsigned operands, except for the notion of overflow. An overflow is what happens when the numerical value of the result does not match the interpretation of the sequence of bits that you obtain.

For instance, consider 8-bit sequences (MIPS has 32-bit registers, but 8 bits are easier for my examples). Let us assume unsigned interpretation: an 8-bit sequence represents a numerical value between 0 and 255 (inclusive). If I add 10010011 (numerical value 147) to 01110110 (numerical value 118) then I get 00001001 (numerical value 9). 9 is not equal to 147+118. I get that result because the mathematical value is 265, which cannot fit in 8 bits. The addition result would have required 9 bits, but the upper ninth bit has been dropped.

Now, imagine the same example with the signed interpretation. 10010011 now has numerical value -109. 01110110 still has numerical value 118, and the obtained result (00001001) has value 9. The mathematical sum of -109 and 118 is 9, so there is no overflow.

This means that the notion of overflow depends on how you interpret the values. The addition mechanics are the same for both signed and unsigned interpretations (for the same input sequences of bits, you get the same output bit sequence -- this is the whole point of using two's complement for negative signed values) but overflow handling differs.

The MIPS architecture provides means for triggering exceptions on overflow. Conceptually, there are three possible addition operations on 32-bit words:

• an addition which silently ignores overflows (result is truncated)
• an addition which raises an exception when a signed overflow occurs (there is an overflow if the input and output sequences are interpreted as signed numbers)
• an addition which raises an exception when an unsigned overflow occurs (there is an overflow if the intput and output sequences are interpreted as unsigned numbers)

The MIPS implements the first two kinds of additions, with, respectively, the addu and add opcodes. In the MIPS documentations, they are called, respectively, unsigned and signed arithmetics. There is no opcode for raising exceptions on unsigned overflows. In practice, C compilers use only addu, but they could use add for signed types (this is allowed by the C standard, but would break an awful lot of existing code). Ada compilers use add because Ada makes overflow checking mandatory.

That being said...

Patterson and Hennessey want to implement signed and unsigned arithmetics on 64-bit integers. For unsigned arithmetics, they want no exception whatsoever, hence they use addu and subu. For signed arithmetics, they want an exception to occur when the mathematical result would not fit on a 64-bit sequence with signed interpretation. They do not want to raise an exception because of some spurious overflow-like condition when processing the low 32-bit halves. This is why they use a subu for the low parts.

Your solution is wrong because it may raise an exception where it should not. Suppose that you want to subtract 2000000000 (two billions) from -2000000000 (minus two billions). The mathematical result is 4000000000 (four billions). The two operands and the result certainly fit in 64 bits (the representable range is -9223372036854775808 to 9223372036854775807). Hence, for 64-bit signed arithmetics, there is no overflow: there should be no exception. However, in that situation, your first sub will report an overflow. That sub works with 32-bit values and signed 32-bit arithmetics. Its operands will be 01110111001101011001010000000000 and 10001000110010100110110000000000. Notice that these values both fit in 32 bits: the 32-bit signed interpretation of these values are, respectively, plus and minus two billions. The subtraction result, however, is four billions, and it does not fit in 32 bits (as a signed number). Thus, your sub raises an exception.

As a rule of thumb, overflow detection is about doing things which depend on signedness interpretation, which impacts handling of the most significant bit. For big integer arithmetics, all words except the most significant shall be treated as unsigned, hence addu/subu everywhere. As a first step, things are easier to understand if you first concentrate on unsigned arithmetics, with no exception (then you just use addu and subu, and never add or sub).