libskarnet
skalibs
Software
www.skarnet.org

The `biguint` library interface

biguint is set of simple primitives performing arithmetical operations on (unsigned) integers of arbitrary length. It is nowhere near as powerful or efficient as specialized, assembly language-optimized libraries such as GMP, but it has the advantages of smallness and simplicity.

Compiling

Use #include <skalibs/biguint.h>

Programming

You should refer to the skalibs/biguint.h header for the exact function prototypes.

Definitions

A biguint x is a pointer to an array u of uint32_t, together with an unsigned integer n called its length.
x = (2^32)^0 * u[0] + (2^32)^1 * u[1] + ... + (2^32)^(n-1) * u[n-1].
Every u[i] is called a limb.
The greatest integer i lesser than n for which u[i] is non-zero is called the order of x. The order of zero is 0.

Basic operations

Creating a biguint

Just declare uint32_t x[n] ; - n being the length of the biguint. You could also allocate x in the heap, possibly using a uint32_t genalloc. In the following, a biguint is always referred to as a uint32_t * with its unsigned int length ; it must always be pre-allocated.

If an operation fails because a biguint's length n is too small to accommodate the result, the function will write the first (i.e. least significant) n limbs of the result, truncating it, then return 0 with errno set to EOVERFLOW.

Setting it to zero

uint32_t *x ;
unsigned int n ;

 bu_zero(x, n) ;

bu_zero() sets the first n limbs of x to zero.

Copying a biguint

uint32_t const *x ;
unsigned int xn ;
uint32_t *y ;
unsigned int yn ;

  bu_copy(y, yn, x, xn) ;

bu_copy() copies x to y, setting higher limbs of y to zero if needed. It then returns 1. If y is too small to contain x, the function returns 0 EOVERFLOW.

Calculating the order

uint32_t const *x ;
unsigned int n ;
unsigned int r ;

  r = bu_len(x, n) ;

bu_len() outputs the order of x of length n. 0 <= r <= n.

Comparing two biguints

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
int r ;

  r = bu_cmp(a, an, b, bn) ;

bu_cmp() returns -1 if a < b, 1 if a > b, and 0 if a = b.

I/O operations

Writing a biguint as an array of bytes

char *s ;
uint32_t const *x ;
unsigned int n ;

  bu_pack(s, x, n) ;
  bu_pack_big(s, x, n) ;

bu_pack() writes 4*n bytes to s. The bytes are a little-endian representation of x.
bu_pack_big() is the same, with a big-endian representation.

Reading a biguint from an array of bytes

char const *s ;
uint32_t *x ;
unsigned int n ;

  bu_unpack(s, x, n) ;
  bu_unpack_big(s, x, n) ;

bu_unpack() reads 4*n little-endian bytes from s and writes them into the corresponding biguint x.
bu_unpack_big() is the same, but the bytes are interpreted as big-endian.

Formatting a biguint for readable output

char *s ;
uint32_t const *x ;
unsigned int n ;

  bu_fmt(s, x, n) ;

bu_fmt() writes x in s as a standard big-endian hexadecimal number. x is considered of length n, so 8*n bytes will be written to s, even if it x starts with zeros. bu_fmt returns the number of bytes written.

Reading a biguint from readable format

char const *s ;
uint32_t *x ;
unsigned int xn ;
unsigned int z ;
unsigned int len ;

  len = bu_scanlen(s, &z) ;
  bu_scan(s, len, x, xn, z) ;

bu_scanlen() scans s for a biguint written as a hexadecimal number and returns the number of bytes read. The reading stops at the first byte encountered that is not in the 0-9, A-F or a-f range. The z integer then contains the number of bytes excluding leading zeros.

If x has not been allocated yet, you can use xn = bitarray_div8(z) (if you have included the bitarray.h header) and allocate x with length xn.

bu_scan() then reads len bytes from s, assuming there are z significant bytes (i.e. not leading zeros); it writes the resulting biguint into x of length xn. It returns 1, except if xn is too small, in which case it returns 0 EOVERFLOW.

Arithmetic operations

Addition

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
unsigned char carrybefore ;
unsigned char carryafter ;

  bu_add(c, cn, a, an, b, bn) ;
  bu_sub(c, cn, a, an, b, bn) ;

bu_add() adds a and b, and puts the result into c. It returns 1 unless it has to truncate it.

bu_sub() substracts b from a, and puts the result into c. If the result should be negative, then it is written as (2^32)^cn - c and the function returns 0 EOVERFLOW.

Multiplication

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;

 bu_mul(c, cn, a, an, b, bn) ;

bu_mul() computes c=a*b. Make sure that cn ≥ bu_len(a, an) + bu_len(b, bn). If it is not the case, the result will be truncated and bu_mul will return 0 EOVERFLOW.

Division

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *q ;
unsigned int qn ;
uint32_t *r ;
unsigned int rn ;

 bu_div(a, an, b, bn, q, qn, r, rn) ;
 bu_mod(r, rn, b, bn) ;

bu_div() computes q, the quotient, and r, the remainder, of a divided by b. If b is zero, it returns 0 EDOM. If qn or rn is to small to store the quotient or the remainder, it returns 0 EOVERFLOW. bu_mod() computes only the remainder, and stores it in-place.

GCD

uint32_t *r ;
unsigned int rn ;
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;

 bu_gcd(r, rn, a, an, b, bn) ;

bu_gcd() computes the greatest common divisor between a and b, and stores it into r. It returns 1 if all went well.

Note that this function iterates on divisions, so it might use a non totally negligible amount of CPU time.

Left-shifts and right-shifts

uint32_t *x ;
unsigned int xn ;
unsigned char carryafter ;
unsigned char carrybefore ;

 carryafter = bu_slbc(x, xn, carrybefore) ;
 carryafter = bu_srbc(x, xn, carrybefore) ;

bu_slbc() computes x <<= 1. The least significant bit of x is then set to carrybefore. bu_slbc() returns the previous value of x's most significant bit.
bu_srbc() computes x >>= 1. The most significant bit of x is then set to carrybefore. bu_slbc() returns the previous value of x's least significant bit.
bu_slb(x, n) and bu_srb(x, n) are macros for respectively bu_slbc(x, n, 0) and bu_srbc(x, n, 0).

Modular operations

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
uint32_t const *m ;
unsigned int mn ;

 bu_addmod(c, cn, a, an, b, bn, m, mn) ;
 bu_submod(c, cn, a, an, b, bn, m, mn) ;
 bu_mulmod(c, cn, a, an, b, bn, m, mn) ;
 bu_divmod(c, cn, a, an, b, bn, m, mn) ;
 bu_invmod(c, cn, m, mn) ;

bu_addmod() computes c = (a+b) mod m.
bu_submod() computes c = (a-b) mod m.
bu_mulmod() computes c = (a*b) mod m.
a and b must already be numbers modulo m.
The functions return 1 if all went well.

bu_divmod() computes a divided by b modulo m and stores it into c.
bu_invmod() computes the inverse of c modulo m and stores it into c.
The divisor and m must be relatively prime, else those functions return 0 EDOM.

The biguint library interface