summaryrefslogtreecommitdiff
path: root/doc/libbiguint
diff options
context:
space:
mode:
Diffstat (limited to 'doc/libbiguint')
-rw-r--r--doc/libbiguint/index.html388
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 &lt;skalibs/biguint.h&gt;</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&nbsp;&lt;=&nbsp;r&nbsp;&lt;=&nbsp;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&nbsp;&lt;&nbsp;b</tt>, 1 if
-<tt>a&nbsp;&gt;&nbsp;b</tt>, and 0 if <tt>a&nbsp;=&nbsp;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, &amp;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> &ge; <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&nbsp;&lt;&lt;=&nbsp;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&nbsp;&gt;&gt;=&nbsp;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&nbsp;=&nbsp;(a+b)&nbsp;mod&nbsp;m</tt>.<br />
-<tt>bu_submod()</tt> computes <tt>c&nbsp;=&nbsp;(a-b)&nbsp;mod&nbsp;m</tt>.<br />
-<tt>bu_mulmod()</tt> computes <tt>c&nbsp;=&nbsp;(a*b)&nbsp;mod&nbsp;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>