I am just trying to implement multi-precision arithmetic on native MIPS. Assume that
one 64-bit integer is in register $12 and $13 and another is in registers $14 and $15.
The sum is to be placed in registers $10 and $11. The most significant word of the 64-bit integer is found in the even-numbered registers, and the least significant word is found in the odd-numbered registers. On the internet, it said, this is the shortest possible implementation.
addu $11, $13, $15 # add least significant word
sltu $10, $11, $15 # set carry-in bit
addu $10, $10, $12 # add in first most significant word
addu $10, $10, $14 # add in second most significant word
I just wanna double check that I understand correctly. The sltu checks if
the sum of the two least significant words is smaller or equal than one of
the operands. If this is the case, than did a carry occur, is this right?
To check if there occured a carry when adding the two most significant
words and store the result in $9 I have to do:
sltu $9, $10, $12 # set carry-in bit
Does this make any sense?
The sltu checks if the sum of the two least significant words is smaller or equal than one of the operands.
Not quite: it sets $10 to 1 if the sum of the two least significant words is strictly less than one of the operands (considered as 32-bit unsigned values); and 0 if the sum is equal to, or greater than, that operand.
If this is the case, than did a carry occur, is this right?
Yes.
Consider what can happen when adding various possible values of b to some particular value a (where everything is an unsigned 32-bit value):
- If overflow has not occurred, we must have a <= sum <= 0xFFFFFFFF, so 0 <= b <= (0xFFFFFFFF - a).
- The remaining cases for b cause an overflow; the actual sum in these cases must be 0x100000000 <= sum <= a + 0xFFFFFFFF, which when truncated to 32 bits gives 0 <= sum <= a - 1.
To check if there occured a carry when adding the two most significant words and store the result in $9
I have to do:
sltu $9, $10, $12 # set carry-in bit
Not quite.
The problem here is that you're adding two 32-bit values and possibly a carry from the sum of the least significant words. For example, consider the case where there is a carry and both most significant words are 0xFFFFFFFF: the sum will be 1+ 0xFFFFFFFF + 0xFFFFFFFF = 0xFFFFFFFF, and so the carry will not be set (but it should be).
One way to deal with this would be to check for carry after adding $12 to $10, and check again after adding $11 to that sum. Only one of those sums can produce a carry ($12 + $10 only overflows when $12 is 0xFFFFFFFF, because $10 is either 0 or 1; and in that case the sum is 0, so the second sum can't overflow as well).
So this might (disclaimer: it's late, and this is untested) do the trick:
addu $11, $13, $15
sltu $10, $11, $15 # carry from low word
addu $10, $10, $12
sltu $9, $10, $12 # possible carry from high word (1)
addu $10, $10, $14
sltu $8, $10, $14 # possible carry from high word (2)
or $9, $8, $9 # carry in result if either (1) or (2) were true (can't both be true at once)
