diff options
Diffstat (limited to 'doc/libbiguint/index.html')
| -rw-r--r-- | doc/libbiguint/index.html | 388 |
1 files changed, 0 insertions, 388 deletions
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 @@ -<html> - <head> - <meta name="viewport" content="width=device-width, initial-scale=1.0" /> - <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="//skarnet.org/default.css" /> --> - </head> -<body> - -<p> -<a href="../libskarnet.html">libskarnet</a><br /> -<a href="../index.html">skalibs</a><br /> -<a href="//skarnet.org/software/">Software</a><br /> -<a href="//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="https://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_t, 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_t 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_t <a href="../libstddjb/genalloc.html">genalloc</a>. In the following, -a biguint is always referred to as a <tt>uint32_t *</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_t *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_t const *x ; -unsigned int xn ; -uint32_t *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_t 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_t const *a ; -unsigned int an ; -uint32_t 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_t 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_t *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_t 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_t *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_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) ; -</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_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) ; -</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_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) ; -</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_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) ; -</pre> - -<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_t *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_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) ; -</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. -</p> - -</body> -</html> |