Numbers bigger than 8 bytes in C

Question

I am writing some code to deal with numbers in C which are bigger than 8 bytes in size (don't fit into unsigned long). In this example I will use 16 bytes (128 bits) as the width. The numbers are unsigned and integers (no decimal places). They are stored as an array of unsigned chars eg:

unsigned char n[16];

I have managed to get addition to work (it works like an unsigned number in C so if you had a number which was 0xffffffffffffffffffffffffffffffff (2**128) and you were to add 1 you would get 0. I have managed to get addition to work, but I cannot get subtraction to work. I would assume it would be similar code to addition, but I don't seem to be able to get it to work.

Addition code:

//a and b are numbers
unsigned char *add(unsigned char *a, unsigned char *b){
    unsigned char *c = malloc(NUM_SIZE);
    //d is the carry and c is the output number
    unsigned short d = 0;

    if(!c){
        return NULL;
    }
    for(int i = 0; i < NUM_SIZE; i++){
        c[i] = 0;
    }
    for(int i = NUM_SIZE * 2 - 1; i >= 0; i--){
        d += a[i % NUM_SIZE] + b[i % NUM_SIZE];
        c[i % NUM_SIZE] = d % 256;
        d >>= 8;
    }
    return c;
}

NUM_SIZE is defined as 16 (the width of the number in bytes)

What I have tried:

//changing the signs to minuses
d -= a[i % NUM_SIZE] - b[i % NUM_SIZE];

//changing the some signs to minuses
d -= a[i % NUM_SIZE] + b[i % NUM_SIZE];
//or
d += a[i % NUM_SIZE] - b[i % NUM_SIZE];

//looping through the number backwards
for(int i = 0; i < NUM_SIZE * 2; i++)

Answer 1

You may want to use arbitrary-precision arithmetic, a.k.a. as bigint or bignum. You should use a library for that (because bignum algorithms are very clever and use some assembler code). I recommend GMPlib. See also this.

Answer 2

Just an idea (not compiled):

void not( unsigned char* a, unsigned int n )
{
  for ( unsigned int i = 0; i < n; ++i )
    a[i] = ~a[i];
}

void inc( unsigned char* a, unsigned int n )
{
  for ( unsigned int i = 0; i < n; ++i )
    if ( ++a[i] )
      return;
}

void add( unsigned char* c, unsigned char* a, unsigned char* b, unsigned int n )
{
  for ( unsigned int i = 0, r = 0; i < n; ++i )
    c[i] = r = a[i] + b[i] + ( r >> 8 );
}

void sub( unsigned char* c, unsigned char* a, unsigned char* b, unsigned int n )
{
  not( b, n );
  add( c, a, b, n );
  not( b, n ); // revert
  inc( c, n );
}

Answer 3

NUM_SIZE * 2 does not make sense with malloc(NUM_SIZE); ... for(int i = NUM_SIZE * 2 - 1. Only a loop of NUM_SIZE iterations is needed.

Repaired code

#define NUM_SIZE 8
//a - b
unsigned char *sub(const unsigned char *a, const unsigned char *b) {
  unsigned char *c = malloc(NUM_SIZE);
  if (!c) {
    return NULL;
  }

  // zeroing `c[]` not needed.  Retain that code if desired

  int d = 0;  // Use signed accumulator to save the "borrow"

  // drop *2
  for (int i = NUM_SIZE - 1; i >= 0; i--) {
    d += a[i] - b[i];                // Perform the subtraction
    c[i] = d;                        // Save the 8 least significant bits in c[]
    d = (d - c[i]) / (UCHAR_MAX+1);  // Form the "borrow" for the next loop
  }
  // If d<0 at this point, b was greater than a
  return c;
}

Various performance improvements can be made, but important to get functionality correct first.

Answer 4

There may be some __int128_t. But if your compiler does not support it you define a struct with hi and lo with the biggest type you have. In c++ you can also add operators similar to the operators you know from the other int_t-s.

typedef struct uint128 {
    uint64_t lo, hi; // lo comes first if you want to use little-endian else hi comes first
} uint128_t;

If you want to double the size, you use uint128_t in a similar struct.

Edit: A simple function to increase the int128:

int128_t& int128_increase(int128_t& value) {
    // increase the low part, it is 0 if it was overflown
    // so increase hi
    if (!(++value.lo)) {
        ++value.hi;
    };
    return value;
};

Edit: A runtime scaled version of ints, I use words, because it is faster in accessing memory:

typedef struct uint_dynamic {
    // the length as a multiple of the wordsize
    size_t length;
    size_t* words;
} uint_dynamic_t;

uint_dynamic_t& uint_dynamic_increase(uint_dynamic_t& value) {
    size_t* ptr = value.words; size_t i = value.length;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

Or if you want some constant size, put it clearly into a struct.

#define uint_fixed_SIZE (16 / sizeof(size_t))
typedef struct uint_fixed {
    size_t words[uint_fixed_SIZE];
} uint_fixed_t;

uint_fixed_t& uint_fixed_increase(uint_fixed_t& value) {
    size_t* ptr = value.words; size_t i = uint_fixed_SIZE;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

This can be rewritten as a #define-macro, where you replace the specific values by a parameter. Which has similar functionality, by defining specific values and including a file:

File fixed_int.h

// note that here is no #ifndef FILE_H or #pragma once
// to reuse the file

#define _concat1(a, b) a ## b
#define _concat(a, b) _concat1(a, b)
#define _size (-((-fixed_int_size) / sizeof(size_t) / 8))
#ifndef fixed_int_name
    #define _name concat(uint_, fixed_int_size)
#else
    #define _name fixed_int_name
#endif
#define _name_(member) _concat(_concat(_name, _), member)

typedef struct _name {
    size_t words[_size];
} _name_(t);

_name_(t)& _name_(increase)(_name_(t)& value) {
    size_t* ptr = value.words; size_t i = _size;
    while(i && !(++*ptr)) { ++ptr; --i; };
    return value;
};

// undef all defines!
#undef _concat1
#undef _concat
#undef _size
#undef _name
#undef _name_

File my_ints.h

//...

// the following lines define the type uint128_t and the function uint_128_t& uint128_increase(uint128_t&)
#define fixed_int_name uint128 // is optional
#define fixed_int_size 128
#include"fixed_int.h"
#undef fixed_int_size
#undef fixed_int_name

//...

Answer 5

Numbers have a "base" that determines the range of each digit (e.g. "base 10" is decimal).

One uint8_t is a single digit in "base 256". One uint16_t is a single digit in "base 65536". One uint32_t is a single digit in "base 4294967296".

For mathematical operations, performance is heavily effected by the number of digits. By using a larger base you need fewer digits for the same number, which improves performance (until you exceed the CPU's native word size).

For subtraction of unsigned numbers:

#define DIGITS 4

int subtract(uint32_t *result, uint32_t *src1, uint32_t *src2) {
    int carry = 0;
    int oldCarry;
    int i;

    for(i = 0; i < DIGITS; i++) {
        oldCarry = carry;
        if(src2[i] < src1[i]) {
            carry = 1;
        } else if( (src2[i] == src1[i]) && (oldCarry != 0) ) {
            carry = 1;
        } else {
            carry = 0;
        }
        result[i] = src1[i] - src2[i] - oldCarry;
    }
    return carry;
}