diff options
| author | Laurent Bercot <ska-skaware@skarnet.org> | 2014-09-18 18:55:44 +0000 |
|---|---|---|
| committer | Laurent Bercot <ska-skaware@skarnet.org> | 2014-09-18 18:55:44 +0000 |
| commit | 3534b428629be185e096be99e3bd5fdfe32d5544 (patch) | |
| tree | 210ef3198ed66bc7f7b7bf6a85e4579f455e5a36 /doc/libbiguint | |
| download | skalibs-3534b428629be185e096be99e3bd5fdfe32d5544.tar.xz | |
initial commit with rc for skalibs-2.0.0.0
Diffstat (limited to 'doc/libbiguint')
| -rw-r--r-- | doc/libbiguint/index.html | 391 |
1 files changed, 391 insertions, 0 deletions
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 @@ +<html> + <head> + <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> + <meta http-equiv="Content-Language" content="en" /> + <title>skalibs: the biguint library interface</title> + <meta name="Description" content="skalibs: the biguint library interface" /> + <meta name="Keywords" content="skalibs biguint libbiguint library interface" /> + <!-- <link rel="stylesheet" type="text/css" href="http://skarnet.org/default.css" /> --> + </head> +<body> + +<p> +<a href="../libskarnet.html">libskarnet</a><br /> +<a href="../index.html">skalibs</a><br /> +<a href="http://www.skarnet.org/software/">Software</a><br /> +<a href="http://www.skarnet.org/">www.skarnet.org</a> +</p> + +<h1> The <tt>biguint</tt> library interface </h1> + +<p> +<tt>biguint</tt> 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 +<a href="http://gmplib.org/">GMP</a>, but it has the advantages +of smallness and simplicity. +</p> + +<h2> Compiling </h2> + +<ul> + <li> Use <tt>#include <skalibs/biguint.h></tt> </li> +</ul> + +<h2> Programming </h2> + +<p> + You should refer to the <tt>skalibs/biguint.h</tt> header for the exact function +prototypes. +</p> + +<h3> <a name="defs" /> +Definitions </h3> + +<ul> + <li> A <em>biguint</em> <tt>x</tt> is a pointer to an array <tt>u</tt> +of uint32, together with an unsigned integer <tt>n</tt> called its <em>length</em>. +<br><tt>x = (2^32)^0 * u[0] + (2^32)^1 * u[1] + ... + (2^32)^(n-1) * u[n-1]</tt>. </li> + <li> Every <tt>u[i]</tt> is called a <em>limb</em>. </li> + <li> The greatest integer <tt>i</tt> lesser than <tt>n</tt> for which +<tt>u[i]</tt> is non-zero is called the <em>order</em> of <tt>x</tt>. The +order of zero is 0. </li> +</ul> + +<h3> <a name="basic" /> +Basic operations </h3> + +<h4> Creating a biguint </h4> + +<p> + Just declare <tt>uint32 x[n] ;</tt> - <em>n</em> being the length of the +biguint. You could also allocate <em>x</em> in the heap, possibly using a +uint32 <a href="../libstddjb/genalloc.html">genalloc</a>. In the following, +a biguint is always referred to as a <tt>uint32 *</tt> with its +<tt>unsigned int</tt> length ; it must always be pre-allocated. +</p> + +<p> + If an operation fails because a biguint's length <tt>n</tt> is too small to +accommodate the result, the function will write the first (i.e. least significant) +<tt>n</tt> limbs of the result, truncating it, then return 0 with errno set to +EOVERFLOW. +</p> + +<h4> Setting it to zero </h4> + +<pre> +uint32 *x ; +unsigned int n ; + + bu_zero(x, n) ; +</pre> + +<p> +<tt>bu_zero()</tt> sets the first <tt>n</tt> limbs of <tt>x</tt> to zero. +</p> + +<h4> Copying a biguint </h4> + +<pre> +uint32 const *x ; +unsigned int xn ; +uint32 *y ; +unsigned int yn ; + + bu_copy(y, yn, x, xn) ; +</pre> + +<p> +<tt>bu_copy()</tt> copies <tt>x</tt> to <tt>y</tt>, setting higher limbs of <tt>y</tt> +to zero if needed. It then returns 1. If <tt>y</tt> is too small to contain <tt>x</tt>, +the function returns 0 EOVERFLOW. +</p> + +<h4> Calculating the order </h4> + +<pre> +uint32 const *x ; +unsigned int n ; +unsigned int r ; + + r = bu_len(x, n) ; +</pre> + +<p> +<tt>bu_len()</tt> outputs the order of <tt>x</tt> of length <tt>n</tt>. +<tt>0 <= r <= n</tt>. +</p> + +<h4> Comparing two biguints </h4> + +<pre> +uint32 const *a ; +unsigned int an ; +uint32 const *b ; +unsigned int bn ; +int r ; + + r = bu_cmp(a, an, b, bn) ; +</pre> + +<p> +<tt>bu_cmp()</tt> returns -1 if <tt>a < b</tt>, 1 if +<tt>a > b</tt>, and 0 if <tt>a = b</tt>. +</p> + +<h3> <a name="io" /> +I/O operations </h3> + +<h4> Writing a biguint as an array of bytes </h4> + +<pre> +char *s ; +uint32 const *x ; +unsigned int n ; + + bu_pack(s, x, n) ; + bu_pack_big(s, x, n) ; +</pre> + +<p> +<tt>bu_pack()</tt> writes <tt>4*n</tt> bytes to <tt>s</tt>. The bytes +are a little-endian representation of <tt>x</tt>.<br /> +<tt>bu_pack_big()</tt> is the same, with a big-endian representation. +</p> + +<h4> Reading a biguint from an array of bytes </h4> + +<pre> +char const *s ; +uint32 *x ; +unsigned int n ; + + bu_unpack(s, x, n) ; + bu_unpack_big(s, x, n) ; +</pre> + +<p> +<tt>bu_unpack()</tt> reads <tt>4*n</tt> little-endian bytes from <tt>s</tt> +and writes them into the corresponding biguint <tt>x</tt>. <br /> +<tt>bu_unpack_big()</tt> is the same, but the bytes are interpreted as +big-endian. +</p> + +<h4> Formatting a biguint for readable output </h4> + +<pre> +char *s ; +uint32 const *x ; +unsigned int n ; + + bu_fmt(s, x, n) ; +</pre> + +<p> +<tt>bu_fmt()</tt> writes <tt>x</tt> in <tt>s</tt> as a standard big-endian +hexadecimal number. <tt>x</tt> is considered of length <tt>n</tt>, so +<tt>8*n</tt> bytes will be written to <tt>s</tt>, even if it <tt>x</tt> +starts with zeros. <tt>bu_fmt</tt> returns the number of bytes written. +</p> + +<h4> Reading a biguint from readable format </h4> + +<pre> +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) ; +</pre> + +<p> + bu_scanlen() scans <tt>s</tt> 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 <tt>z</tt> integer then contains the +number of bytes excluding leading zeros. +</p> + +<p> + If x has not been allocated yet, you can use <tt>xn = bitarray_div8(z)</tt> +(if you have included the <tt>bitarray.h</tt> header) +and allocate <tt>x</tt> with length <tt>xn</tt>. +</p> + +<p> +<tt>bu_scan()</tt> then reads <tt>len</tt> bytes from <tt>s</tt>, assuming +there are <tt>z</tt> significant bytes (i.e. not leading zeros); it writes +the resulting biguint into <tt>x</tt> of length <tt>xn</tt>. It returns 1, +except if <tt>xn</tt> is too small, in which case it returns 0 EOVERFLOW. +</p> + +<h3> <a name="arith" /> +Arithmetic operations </h3> + +<h4> Addition </h4> + +<pre> +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) ; +</pre> + +<p> +<tt>bu_add()</tt> adds <tt>a</tt> and <tt>b</tt>, and puts the result +into <tt>c</tt>. It returns 1 unless it has to truncate it. +</p> + +<p> +<tt>bu_sub()</tt> substracts <tt>b</tt> from <tt>a</tt>, and puts the +result into <tt>c</tt>. If the result should be negative, then it is +written as <tt>(2^32)^cn - c</tt> and the function returns 0 EOVERFLOW. +</p> + +<h4> Multiplication </h4> + +<pre> +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) ; +</pre> + +<p> +<tt>bu_mul()</tt> computes <tt>c=a*b</tt>. +Make sure that <tt>cn</tt> ≥ <tt>bu_len(a, an) + bu_len(b, bn)</tt>. +If it is not the case, the result will be truncated and bu_mul will return +0 EOVERFLOW. +</p> + +<h4> Division </h4> + +<pre> +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) ; +</pre> + +<p> +<tt>bu_div()</tt> computes <tt>q</tt>, the quotient, and <tt>r</tt>, the +remainder, of <tt>a</tt> divided by <tt>b</tt>. If <tt>b</tt> is zero, it +returns 0 EDOM. If <tt>qn</tt> or <tt>rn</tt> is to small to store the +quotient or the remainder, it returns 0 EOVERFLOW. +<tt>bu_mod()</tt> computes only the remainder, and stores it in-place. +</p> + +<h4> GCD </h4> + +<pre> +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) ; +</pre> + +<p> +</p> +<tt>bu_gcd()</tt> computes the greatest common divisor between <tt>a</tt> +and <tt>b</tt>, and stores it into <tt>r</tt>. It returns 1 if all went well. +</p> + +<p> + Note that this function iterates on divisions, so it might use a non totally +negligible amount of CPU time. +</p> + + +<h4> Left-shifts and right-shifts </h4> + +<pre> +uint32 *x ; +unsigned int xn ; +unsigned char carryafter ; +unsigned char carrybefore ; + + carryafter = bu_slbc(x, xn, carrybefore) ; + carryafter = bu_srbc(x, xn, carrybefore) ; +</pre> + +<p> +<tt>bu_slbc()</tt> computes <tt>x <<= 1</tt>. +The least significant bit of <tt>x</tt> is then set to +<tt>carrybefore</tt>. <tt>bu_slbc()</tt> returns the +previous value of <tt>x</tt>'s most significant bit. <br /> +<tt>bu_srbc()</tt> computes <tt>x >>= 1</tt>. +The most significant bit of <tt>x</tt> is then set to +<tt>carrybefore</tt>. <tt>bu_slbc()</tt> returns the +previous value of <tt>x</tt>'s least significant bit.<br /> +<tt>bu_slb(x, n)</tt> and <tt>bu_srb(x, n)</tt> are macros for +respectively <tt>bu_slbc(x, n, 0)</tt> and <tt>bu_srbc(x, n, 0)</tt>. +</p> + +<h4> Modular operations </h4> + +<pre> +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) ; +</pre> + +<p> +<tt>bu_addmod()</tt> computes <tt>c = (a+b) mod m</tt>.<br /> +<tt>bu_submod()</tt> computes <tt>c = (a-b) mod m</tt>.<br /> +<tt>bu_mulmod()</tt> computes <tt>c = (a*b) mod m</tt>.<br /> +<tt>a</tt> and <tt>b</tt> must already be numbers modulo <tt>m</tt>.<br /> +The functions return 1 if all went well. +</p> + +<p> +<tt>bu_divmod()</tt> computes <tt>a</tt> divided by <tt>b</tt> modulo +<tt>m</tt> and stores it into <tt>c</tt>. <br /> +<tt>bu_invmod()</tt> computes the inverse of <tt>c</tt> modulo <tt>m</tt> +and stores it into <tt>c</tt>. <br /> +The divisor and <tt>m</tt> must be relatively prime, else +those functions return 0 EDOM. <br /> + The algorithm for modular division and inversion is due to +<a href="http://research.sun.com/techrep/2001/abstract-95.html">Sheueling +Chang Shantz</a>. +</p> + +</body> +</html> |