-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. -
- -- You should refer to the skalibs/biguint.h header for the exact function -prototypes. -
- -- 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.
-
-libstddjb
-libskarnet
-skalibs
-Software
-skarnet.org
-
- TODO: write this documentation page. (Sorry!) -
- -