CODEWITHSUNDEEP
assemblymipssubtractionbigint
Kaisan
Kaisan

Reputation: 109

Mips subtraction of 64 bit numbers

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?

Upvotes: 0

Views: 1027

Answers (1)

Peter Cordes
Peter Cordes

Reputation: 363999

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

Upvotes: 1

Related Questions