2

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?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Rob
  • 21
  • 2
  • I'd recommend creating more ILP by adding the high halves before SLTU and then adding the carry-in later, so a superscalar MIPS could run that in parallel with the low-half `addu` or the `sltu` to generate carry-out from the low half. Your version has one dependency chain running through all 4 instructions so latency can't be any better than 4 cycles; mine would shorten that to 3 cycles. – Peter Cordes Aug 07 '19 at 22:44

1 Answers1

1

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)
Matthew Slattery
  • 45,290
  • 8
  • 103
  • 119