From dd6bb6c6b8298ebeff2d1882becb36580b969d6f Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Fri, 23 Jul 2021 16:43:57 +0000 Subject: New 2.11.0.0 branch with several modifications - libbiguint removed - cdb_make changed to cdbmake (because different ui) - cdb redesigned Signed-off-by: Laurent Bercot --- doc/libbiguint/index.html | 388 ---------------------------------------------- 1 file changed, 388 deletions(-) delete mode 100644 doc/libbiguint/index.html (limited to 'doc/libbiguint/index.html') diff --git a/doc/libbiguint/index.html b/doc/libbiguint/index.html deleted file mode 100644 index f0378dd..0000000 --- a/doc/libbiguint/index.html +++ /dev/null @@ -1,388 +0,0 @@ - - - - - - skalibs: the biguint library interface - - - - - - -

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

- - - -- cgit v1.2.3

The biguint library interface