summaryrefslogtreecommitdiff
path: root/doc/libbiguint
diff options
context:
space:
mode:
authorLaurent Bercot <ska-skaware@skarnet.org>2014-09-18 18:55:44 +0000
committerLaurent Bercot <ska-skaware@skarnet.org>2014-09-18 18:55:44 +0000
commit3534b428629be185e096be99e3bd5fdfe32d5544 (patch)
tree210ef3198ed66bc7f7b7bf6a85e4579f455e5a36 /doc/libbiguint
downloadskalibs-3534b428629be185e096be99e3bd5fdfe32d5544.tar.xz
initial commit with rc for skalibs-2.0.0.0
Diffstat (limited to 'doc/libbiguint')
-rw-r--r--doc/libbiguint/index.html391
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 &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, 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&nbsp;&lt;=&nbsp;r&nbsp;&lt;=&nbsp;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&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 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, &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 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> &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 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&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 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&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. <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>