5

I want to perform 64-bit addition and subtraction:

v1v0(HiLo) = a1a0 + a3a2 using MIPS assembly language (a1a0(HiLo) is the first 64-bit number consists of two 32-bit numbers, and a3a2(HiLo) is the second)

and I have:

$a0 = 0xffffffff
$a1 = 0x0
$a2 = 0x1
$a3 = 0x0

I'm a beginner in MIPS, and I'm not sure how to handle carries. Could someone provide a solution with explanation?

Thanks in advance! This is the instruction set that I'm using:

http://www.cs.uregina.ca/Links/class-info/201/SPIM-IO/MIPSrefCard.pdf

phuclv
  • 37,963
  • 15
  • 156
  • 475
Meteorite
  • 344
  • 1
  • 5
  • 17

4 Answers4

6

To subtrate a number, i.e. v = a - b is the same as doing an add with a negative number, i.e., v = a + (-b). But, in integer aritmetic, a negative number is coded as a 2-compliment, that is the same as 1-compliment + 1 and 1-compliment is a bitwise negation.

In this way, we can write that:

v1v0 = a1a0 - b1b0
v1v0 = a1a0 + ~b1~b0 + 1

so, we can write this in assembly as (assuming b1 = a3 and b0 = a2):

add64: addu  $v0, $a0, $a2    # add least significant word
       nor   $t0, $a2, $zero  # ~a2
       sltu  $t0, $a0, $t0    # set carry-in bit (capturing overflow)
       addu  $v1, $t0, $a1    # add in first most significant word
       addu  $v1, $v1, $a3    # add in second most significant word
       jr $ra
#PS: To capture the carry bit in a unsigned sum is equivalent to test if the sum
# can not be contained in a 32 bit register. I.e. if a0 + a2 > 2^32 - 1

sub64: nor $a3, $a3, $zero    # ~b1
       nor $a2, $a2, $zero    # ~b0
       jal add64    # v1v0 = a1a0 + ~b1~b0
         # adding 1 to v1v0
       ori $a0, $v0, 0
       ori $a1, $v1, 0
       ori $a2, $zero, 1
       ori $a3, $zero, 0
       jal add64
       jr $ra

using your ideas, which, I think you would answer your own question:

subu $v0, $a0, $a2 # $v0 = $a0 - $a2 
sltu $v1, $a0, $a2 # $v1 = ($a0 < $a2)? 1:0(subtract 1 if there's a borrow for Lo words) 
subu $a1, $a1, $v1 # $a1 = $a1 - $v1 
subu $v1, $a1, $a3 # $v1 = $a1 - $a3
Amadeus
  • 10,199
  • 3
  • 25
  • 31
  • For addition, I did the same thing. But for subtraction, I think `sub64: subu $v0, $a0, $a2 # $v0 = $a0 - $a2 sltu $v1, $v0, $a2 # $v1 = ($v0 < $a2)? 1:0(subtract 1 if there's a borrow for Lo words) addu $a3, $a3, $v1 # $a3 = $a3 + $v1 subu $v1, $a1, $a3 # $v1 = $a1 - $a3 jr $ra` should work. What do you think? – Meteorite Oct 14 '14 at 04:06
  • Try the following values and see if it works: `$a1 = 0, $a0 = 0x8000 0001, $a3 = 0, $a2 = 0x8000 0000` – Amadeus Oct 14 '14 at 04:20
  • Sorry there was a typo. I actually used this one: `# your code here subu $v0, $a0, $a2 # $v0 = $a0 - $a2 sltu $v1, $a0, $a2 # $v1 = ($a0 < $a2)? 1:0(subtract 1 if there's a borrow for Lo words) addu $a3, $a3, $v1 # $a3 = $a3 + $v1 subu $v1, $a1, $a3 # $v1 = $a1 - $a3` – Meteorite Oct 14 '14 at 04:23
  • Again, you can try with the following values: `$a1 = 0, $a0 = 0, $a3 = 0, $a2 = 1` – Amadeus Oct 14 '14 at 04:28
  • 2
    @Amadeus I could be wrong, but to me it looks like the second line of add64 should read `sltu $t0, $v0, $a2` because it appears that you're setting `$t0` arbitrarily based on weather the upper halves of the parameters are greater/less than one another. – tuckerchapin Oct 23 '15 at 06:23
  • @tuckerchapin I did not remember the logic that I've followed, but it seems incorrect by now, so I have updated my answer to accomplish what I think is correct. In regard with your proposed solution, I guess it would not solve the problem once if a2 = a0 = 0x8000 0000, `sltu $t0, $v0, $a2` would not capture the carry bit – Amadeus Oct 23 '15 at 17:26
  • How do the second and third line capture the carry bit? – Gustavo Alejandro Castellanos Mar 03 '20 at 06:53
  • @tuckerchapin is correct; the usual idiom is `sum = a+b`; `carry = sum < a;` or `sum < b` (either one is equally valid because addition is commutative). That's what GCC does (https://godbolt.org/z/ca9zT5cjM), using just `sltu` as tucker suggested instead of wasting an instruction on NOR. I'm not sure whether your answer works or not; it seems to be doing `a_low < (-b_low - 1)` which makes no sense to me, and isn't commutative so it seems incorrect unless I'm missing something. It's certainly inefficient. – Peter Cordes Feb 14 '22 at 00:52
  • Turns out this is almost correct, just inefficient. (The operands to `sltu` are backwards: should be `sltu $t0, $t0, $a0` as shown in El Rico's answer). The asymmetry of `<` is balanced out by NOTing one of the operands. Tested with uint8_t so we can check all all possible inputs: https://godbolt.org/z/9KeWdo3sM : `(~b) < a;` is correct, unlike the asm here doing `a < (~b)`. – Peter Cordes Feb 14 '22 at 01:28
1

The algorithm add64 should be:

   addu  $v0, $a0, $a2    # add least significant word
   nor   $t0, $a2, $zero  # ~a2
   sltu  $t0, $t0, $a0    # **~a2 < a0 to check carry generation**
   addu  $v1, $t0, $a1    # add in first most significant word
   addu  $v1, $v1, $a3    # add in second most significant word
   jr $ra

We may check the carry with a0 + a2 > 2^32 - 1, but remember that in binary:

2^n - 1 = a2 + ~a2 (ex: a2 = 0110, ~a2 = 1001, a2 + ~a2 = 1111 = 2^4 - 1, n=4)

Thus, a0 + a2 > a2 + ~a2 => a0 > ~a2

El Rico
  • 11
  • 1
  • This is correct but less efficient than `sum = a+b;` `carry = sum < a;`. See [Adding two 64 bit numbers in Assembly](https://stackoverflow.com/q/1281806) – Peter Cordes Feb 14 '22 at 01:31
0

In general you need to do exactly what you learned in like second grade when adding multi-digit numbers. Add each "column".

 12    89
+34   +33
---   ---
 46   122

The first one is easy because no "carrying" happens. In the second case you had to actually add 3 numbers in the tens column: 8 + 3 + 1 (carry from ones column). Then the second column also carried to make 100.

You need to do the same thing but you will be adding 32-bits in each "column". Fortunately since you are in binary, you can only carry one bit from the first column to the second.

Dwayne Towell
  • 8,154
  • 4
  • 36
  • 49
0

The MIPS architecture does not provide a carry flag (nor any other flags!). According to this page, an overflow requiring a carry occurs when adding two positive numbers gives a negative number (or vice versa).

Something like bool carry = (a1[31] == a3[31]) && (v1[31] != a1[31]) translated into MIPS assembly should work.

markgz
  • 6,054
  • 1
  • 19
  • 41
  • Thank you @markgz ! I figured I need something like that, and I'm trying to implement the logic using `sltu`. – Meteorite Oct 14 '14 at 03:29
  • That expression gives you signed overflow, not unsigned carry-out. e.g. `0xFFFFFFFF` x 2 produces carry-out, but in terms of signed operations it's just `-1 + -1 = -2` without overflow. One `sltu` after an `addu` can produce the carry-out: [use slt to check unsigned integer addition carry flag mips](https://stackoverflow.com/q/33503676) – Peter Cordes Jun 29 '21 at 02:13