libskarnet

skalibs

Software

www.skarnet.org

`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.

- Use
`#include <skalibs/biguint.h>`

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

- 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.

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.

uint32_t *x ; unsigned int n ; bu_zero(x, n) ;

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

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.

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`.

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`.

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.

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.

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.

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.

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.

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.

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.

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.

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)`.

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.