Big Integer Subtraction

Subtracting B from A on the Power architecture is easy when both A and B fit in a single machine word: subf[c] rt, B, A. Much more interesting is the case where they do not fit, as is often the case in big number libraries and cryptographic code. In order to make this fast, this needs to be implemented directly in assembly for the target architecture. This exercise, and the code in it, arose from optimizing hot spots in the Go math/big library as it is used by the crypto packages.

Big integers are (in our case) stored as an array of words and a sign. The function being implemented, subVV (subtract-vector-vector) has several conditions to the API in order to call it: the arguments all have the same length, (This is a fine assumption - to do subtraction of numbers that don't have the same number of words, truncate them to length of the shorter array and handle the case of needing to borrow once more at the end; this is handled at the call site) and function must return 1 if there was a borrow and 0 otherwise. Thus, the subtraction algorithm can be outlined in psuedocode (or actual code):

var c = 0
for i from 0 to length:
    result[i] = A[i] - B[i] - c
    c = 1 if that borrowed, 0 if it didn't
return c

The ideal instruction to implement this will handle both of these steps. To understand how this ideal instruction should work, it pays off to examine what the subtraction instruction does.

According to the Power ISA manual (version 2.07, p. 68), subtraction performs "the sum ¬B + A + 1" and places it in rt. This works due to the nature of two's complement numbers: namely, that addition of numbers represented in two's complement form works identically to addition of unsigned numbers. This allows performing A + (-B). -B, in two's complement, is ¬B+1.

The desired instruction takes a possible borrow into account, and so would look like ¬B + A + 1 - c, where c is 1 if there was a borrow and 0 otherwise.

The difference between subf and subfc on POWER is that the subfc version sets the carry bit, CA, in the processor. When will subtraction carry? This is easiest to examine on a single bit:

The CA bit is set to 1 when a ≥ b, and 0 when a < b: CA serves as a not-borrow flag. This allows rewriting the expression ¬B + A + 1 - c in terms of CA by noting that CA = 1 - c *(Proof left as an exercise to the reader), giving ¬B + A + CA.

A quick browse of the ISA, and we find the instruction we're looking for: Subtract From Extended, subfe. Like subfc, subfe sets the CA bit. Exactly as required, "the sum ¬B + A + CA" is placed in rt.

This can be explored by considering an example of 9-bit subtraction on a 3-bit computer.

  368      101 110 000
- 123    - 001 111 011
-----    -------------
  245      011 110 101

Beginning with the least significant words, 000-011:

000 - 011 = 000 + ¬011 + CA = 000 + 100 + 1 = 101

For the first subtraction, there was no previous borrow and so CA must be 1. This does not overflow, and so CA is 0 for the next word:

110 - 111 - c = 110 + ¬111 + 1 - c = 110 + 000 + CA = 110

This leads to our final word of the subtraction, again with CA = 0:

101 - 001 - c = 101 + ¬001 + 1 - c = 101 + 110 + CA = 011

This just leaves a couple loose ends. First, to use subfe for the loop, CA needs to have an initial value. As this is a normal subtraction without a borrow, that initial value must be 1. Additionally, this implementation is being written targeting the Go assembler which uses its own assembly syntax.

// func subVV(r, a, b []Word) c Word
TEXT ·subVV, NOSPLIT, $0
    MOVD res_len+8(FP), R7 // length of result
    MOVD a+24(FP), R8      // address of subtrahend
    MOVD b+48(FP), R9      // address of minuend
    MOVD r+0(FP), R10      // address of result

    MOVD $0, R5  // i = 0
    MOVD $8, R28 // unaware of mulli equivalent in go asm
    SUBC R0, R0  // R0 always contains 0, so this sets CA
    JMP END

LOOP:
    MULLD R5, R28, R6   // offset in bytes by i
    MOVD  (R8)(R6), R11 // a[i]
    MOVD  (R9)(R6), R12 // b[b]

    SUBE R12, R11, R15  // same as subfe r15, r12, r11
    MOVD R15, (R10)(R6) // store result in r[i]

    ADD $1, R5 // i++

END:
    CMP R5, R7 // if i < len(r):
    BLT LOOP   //   goto LOOP

    MOVD  $0, R4
    ADDZE R4     // R4 += CA
    XOR   $1, R4 // return value is !CA
    MOVD  R4, r+72(FP) // Go passes return values on the stack
    RET

How much faster is this assembly than the generic implementation? The benchmark for addVV is easily modified to benchmark subVV, giving the following results:

benchmark                 old ns/op     new ns/op     delta
BenchmarkSubVV/1          16.1          6.76          -58.01%
BenchmarkSubVV/2          18.2          9.59          -47.31%
BenchmarkSubVV/3          20.5          9.32          -54.54%
BenchmarkSubVV/4          22.9          11.3          -50.66%
BenchmarkSubVV/5          25.5          13.3          -47.84%
BenchmarkSubVV/10         42.6          27.1          -36.38%
BenchmarkSubVV/100        259           198           -23.55%
BenchmarkSubVV/1000       2408          1910          -20.68%
BenchmarkSubVV/10000      23853         19037         -20.19%
BenchmarkSubVV/100000     244542        190399        -22.14%

benchmark                 old MB/s     new MB/s     speedup
BenchmarkSubVV/1          3968.14      9460.99      2.38x
BenchmarkSubVV/2          7045.22      13347.39     1.89x
BenchmarkSubVV/3          9357.28      20609.20     2.20x
BenchmarkSubVV/4          11156.85     22688.51     2.03x
BenchmarkSubVV/5          12556.21     24002.40     1.91x
BenchmarkSubVV/10         15007.22     23583.03     1.57x
BenchmarkSubVV/100        24693.65     32217.26     1.30x
BenchmarkSubVV/1000       26575.40     33492.23     1.26x
BenchmarkSubVV/10000      26830.29     33617.69     1.25x
BenchmarkSubVV/100000     26171.33     33613.55     1.28x