How to properly add/subtract a 128-bit number (as two uint64_t)?

Question

I'm working in C and need to add and subtract a 64-bit number and a 128-bit number. The result will be held in the 128-bit number. I am using an integer array to store the upper and lower halves of the 128-bit number (i.e. uint64_t bigNum[2], where bigNum[0] is the least significant).

Can anybody help with an addition and subtraction function that can take in bigNum and add/subtract a uint64_t to it?

I have seen many incorrect examples on the web, so consider this:

bigNum[0] = 0;  
bigNum[1] = 1;  
subtract(&bigNum, 1);

At this point bigNum[0] should have all bits set, while bigNum[1] should have no bits set.

Answer 1

In many architectures it's very easy to add/subtract any arbitrarily-long integers because there's a carry flag and add/sub-with-flag instruction. For example on x86 rdx:rax += r8:r9 can be done like this

add rax, r9    # add the low parts and store the carry
adc rdx, r8    # add the high parts with carry

In C there's no way to access this carry flag so you must calculate the flag on your own. The easiest way is to check if the unsigned sum is less than either of the operand like this. For example to do a += b we'll do

aL += bL;
aH += bH + (aL < bL);

This is exactly how multi-word add is done in architectures that don't have a flag register. For example in MIPS it's done like this

    # alow = blow + clow
addu    alow, blow, clow
    # set tmp = 1 if alow < clow, else 0
sltu    tmp, alow, clow
addu    ahigh, bhigh, chigh
addu    ahigh, ahigh, tmp

Here's some example assembly output

Answer 2

In grade 1 or 2, you should have learn't how to break down the addition of 1 and 10 into parts, by splitting it into multiple separate additions of tens and units. When dealing with big numbers, the same principals can be applied to compute arithmetic operations on arbitrarily large numbers, by realizing your units are now units of 2^bits, your "tens" are 2^bits larger and so on.

Answer 3

This should work for the subtraction:

typedef u_int64_t bigNum[2];

void subtract(bigNum *a, u_int64_t b)
{
  const u_int64_t borrow = b > a[1];

  a[1] -= b;
  a[0] -= borrow;
}

Addition is very similar. The above could of course be expressed with an explicit test, too, but I find it cleaner to always do the borrowing. Optimization left as an exercise.

For a bigNum equal to { 0, 1 }, subtracting two would make it equal { ~0UL, ~0UL }, which is the proper bit pattern to represent -1. Here, UL is assumed to promote an integer to 64 bits, which is compiler-dependent of course.

Answer 4

For the case the value that your are subtracting is less or equal to bignum[0] you don't have to touch bignum[1].

If it isn't, you subtract it from bignum[0], anyhow. This operation will wrap around, but this is the behavior you need here. In addition you'd then have to substact 1 from bignum[1].

Answer 5

Most compilers support a __int128 type intrinsically.

Try it and you might be lucky.