How can I add and subtract 128 bit integers in C or C++ if my compiler does not support them?

Question

I'm writing a compressor for a long stream of 128 bit numbers. I would like to store the numbers as differences -- storing only the difference between the numbers rather than the numbers themselves because I can pack the differences in fewer bytes because they are smaller.

However, for compression then I need to subtract these 128 bit values, and for decompression I need to add these values. Maximum integer size for my compiler is 64 bits wide.

Anyone have any ideas for doing this efficiently?

Answer 1

If all you need is addition and subtraction, and you already have your 128-bit values in binary form, a library might be handy but isn't strictly necessary. This math is trivial to do yourself.

I don't know what your compiler uses for 64-bit types, so I'll use INT64 and UINT64 for signed and unsigned 64-bit integer quantities.

class Int128 { public:     ...     Int128 operator+(const Int128 & rhs)     {         Int128 sum;         sum.high = high + rhs.high;         sum.low = low + rhs.low;         // check for overflow of low 64 bits, add carry to high         if (sum.low < low)             ++sum.high;         return sum;     }     Int128 operator-(const Int128 & rhs)     {         Int128 difference;         difference.high = high - rhs.high;         difference.low = low - rhs.low;         // check for underflow of low 64 bits, subtract carry to high         if (difference.low > low)             --difference.high;         return difference;     }  private:     INT64  high;     UINT64 low; }; 

Answer 2

Take a look at GMP.

#include <stdio.h> #include <gmp.h>  int main (int argc, char** argv) {     mpz_t x, y, z;     char *xs, *ys, *zs;     int i;     int base[4] = {2, 8, 10, 16};      /* setting the value of x in base 10 */     mpz_init_set_str(x, "100000000000000000000000000000000", 10);      /* setting the value of y in base 16 */     mpz_init_set_str(y, "FF", 16);      /* just initalizing the result variable */     mpz_init(z);      mpz_sub(z, x, y);      for (i = 0; i < 4; i++) {         xs = mpz_get_str(NULL, base[i], x);         ys = mpz_get_str(NULL, base[i], y);         zs = mpz_get_str(NULL, base[i], z);          /* print all three in base 10 */         printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);          free(xs);         free(ys);         free(zs);     }      return 0; } 

The output is

x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000 y = 11111111 z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001  x = 235613266501267026547370040000000000 y = 377 z = 235613266501267026547370037777777401  x = 100000000000000000000000000000000 y = 255 z = 99999999999999999999999999999745  x = 4ee2d6d415b85acef8100000000 y = ff z = 4ee2d6d415b85acef80ffffff01