From 3534b428629be185e096be99e3bd5fdfe32d5544 Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Thu, 18 Sep 2014 18:55:44 +0000 Subject: initial commit with rc for skalibs-2.0.0.0 --- doc/libbiguint/index.html | 391 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 391 insertions(+) create mode 100644 doc/libbiguint/index.html (limited to 'doc/libbiguint/index.html') diff --git a/doc/libbiguint/index.html b/doc/libbiguint/index.html new file mode 100644 index 0000000..30de27e --- /dev/null +++ b/doc/libbiguint/index.html @@ -0,0 +1,391 @@ + + + + + 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

+ + + +

Programming

+ +

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

+ +

+Definitions

+ + + +

+Basic operations

+ +

Creating a biguint

+ +

+ Just declare uint32 x[n] ; - n being the length of the +biguint. You could also allocate x in the heap, possibly using a +uint32 genalloc. In the following, +a biguint is always referred to as a uint32 * 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 *x ;
+unsigned int n ;
+
+ bu_zero(x, n) ;
+
+ +

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

+ +

Copying a biguint

+ +
+uint32 const *x ;
+unsigned int xn ;
+uint32 *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 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 const *a ;
+unsigned int an ;
+uint32 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 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 *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 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 *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 const *a ;
+unsigned int an ;
+uint32 const *b ;
+unsigned int bn ;
+uint32 *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 const *a ;
+unsigned int an ;
+uint32 const *b ;
+unsigned int bn ;
+uint32 *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 const *a ;
+unsigned int an ;
+uint32 const *b ;
+unsigned int bn ;
+uint32 *q ;
+unsigned int qn ;
+uint32 *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 *r ;
+unsigned int rn ;
+uint32 const *a ;
+unsigned int an ;
+uint32 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 *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 const *a ;
+unsigned int an ;
+uint32 const *b ;
+unsigned int bn ;
+uint32 *c ;
+unsigned int cn ;
+uint32 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 algorithm for modular division and inversion is due to +Sheueling +Chang Shantz. +

+ + + -- cgit v1.3.1