0

I'm asked to implement subtraction for 64 bit numbers in Mips, whereby the numbers are given in 2's complement, and the lower/upper 32 bits are stored in different registers. My thoughts: We first subtract the lower parts and then the upper ones. A "problematic" situation occurs if the lower part number of the first number is smaller than that of the second number, i.e. considering a small example where we only have 4 bit registers

 0110 0011 
-0010 1000

so first the lower part

 0000 0011    0000 0011
-0000 1000 = +1111 1000 = 1111 1011

and then the upper part

 0110 0000    0110 0000
-0010 0000 = +1110 0000 = 0100 0000

and then adding the two parts together

 0100 0000
+1111 1011 = 0011 1011

My Mips implementation would then look something like this (registers 1-8 for simplicity):

// A-B
lw  $1, 0($8) // upper part of A
lw  $2, 4($8) // lower part of A
lw  $3, 8($8) // upper part of B
lw  $4, 12($8) // lower part of B

subu $5, $2, $4
stlu $6, $2, $4 // if lower part of A < lower part of B we need to add 1111 0000 i.e. 
                // subtract 1 from upper part result
subu $7, $1, $3
subu $7, $7, $6

// Now the upper part of the result is stored in $7$ and the lower part in $5

Does my idea seem correct?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Kaisan
  • 109
  • 1
  • 8

1 Answers1

1

Compare what GCC and clang do for subtracting uint64_t on 32-bit MIPS: https://godbolt.org/z/eGY3aWoKq.

Yes, an sltu to generate the borrow output from the low half, plus 3x subu is the right mix of instructions. Do the low half subtraction, and subtract the high half and the borrow.

Manually transforming it into addition would be slower, so it's probably easiest to think about this in terms of just subtracting the borrow from the high half, and otherwise doing the high and low half subtractions separately.

On an ISA with a carry/borrow flag (like x86 or ARM https://godbolt.org/z/sfG5PzsPW), you'd do

     subs    r0, r0, r2      # sub low half and set flags
     sbc     r1, r1, r3      # sub-with-carry does high half including borrow

ARM and x86 set their carry flag opposite from each other for subtraction (!borrow or borrow), but both are designed to chain from low to high in carry-propagation order so it's just 2 instructions.

# clang -O3 -m32 -mregparm=3   first uint64_t passed in EDX:EAX, second in mem
     sub     eax, dword ptr [esp + 4]
     sbb     edx, dword ptr [esp + 8]    # x86 sub-with-borrow

Since MIPS doesn't have FLAGS, you have to manually handle carry / borrow propagation, but that's all you're doing.

It gets more inconvenient for wider integers when you need to handle borrow in and out, because emulating sbb including the carry output requires checking for wraparound after subtracting the borrow and after subtracting the integer operands. Just like for emulating adc

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • Is my explanation with the 4bit register example correct? I was struggling a bit understanding the meaning of borrow here. – Kaisan Jul 21 '21 at 10:23
  • @HerkulesOl: When binary subtraction does `0 - 1`, it produces a borrow that propagates to the next more significant bit. Across the boundary between registers, that's the borrow output of the 32-bit `sub` operation. Exactly like how addition produces a carry-out from a full-adder (https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder). Without a FLAGS output from the ALU, you do `carry = (a+b) < a` unsigned compare for addition, but for subtraction the borrow output from `a-b` is just `borrow = a – Peter Cordes Jul 21 '21 at 17:03
  • @HerkulesOl: So your way is certainly over-complicated: as I said, you don't need to transform it into an addition. And moreover, most ways of doing that don't correctly preserve the carry/borrow output of sub for every possible input (or for MIPS don't correctly reproduce the `sltu` result). [Arithmetic identities and EFLAGS](https://stackoverflow.com/q/62218921) discusses trying to emulate the borrow output of an actual x86 `sub` instruction, equivalent to emulating the MIPS `sltu` result. – Peter Cordes Jul 21 '21 at 17:04
  • but isn't subtraction of 2's complement numbers just converted to addition? – Kaisan Jul 22 '21 at 10:39
  • and can you recommend any resource where I can read more about the "borrow" thing when performing subtraction? – Kaisan Jul 22 '21 at 10:40
  • @HerkulesOl: However a hardware ALU implements subtraction internally, it has to produce a correct output in the carry flag. (Unless it's an ISA like MIPS without a flags register.) But note that doing `x - y` as `x + (~x + 1)` involves two addition operations. Adding a constant 1 can still carry through all the bits, although I guess you could simplify from full adders to just xor gates for carry propagation. I'm not certain how subtraction is normally done in modern ALUs, but I think it usually doesn't involve a separate step of actually generating `-y` first. – Peter Cordes Jul 22 '21 at 17:38
  • @HerkulesOl: Re: borrowing. It works the same in binary as what you learned in elementary school for decimal, e.g. https://www.smartick.com/blog/math/learning-resources/subtract-borrowing/. Obviously in base 2, the borrow is either 0 or 1 from any given bit-position. – Peter Cordes Jul 22 '21 at 17:40