src/rt/bigint/bigint.h

   1 /* bigint.h - include file for bigint package
   2 **
   3 ** This library lets you do math on arbitrarily large integers.  It's
   4 ** pretty fast - compared with the multi-precision routines in the "bc"
   5 ** calculator program, these routines are between two and twelve times faster,
   6 ** except for division which is maybe half as fast.
   7 **
   8 ** The calling convention is a little unusual.  There's a basic problem
   9 ** with writing a math library in a language that doesn't do automatic
  10 ** garbage collection - what do you do about intermediate results?
  11 ** You'd like to be able to write code like this:
  12 **
  13 **     d = bi_sqrt( bi_add( bi_multiply( x, x ), bi_multiply( y, y ) ) );
  14 **
  15 ** That works fine when the numbers being passed back and forth are
  16 ** actual values - ints, floats, or even fixed-size structs.  However,
  17 ** when the numbers can be any size, as in this package, then you have
  18 ** to pass them around as pointers to dynamically-allocated objects.
  19 ** Those objects have to get de-allocated after you are done with them.
  20 ** But how do you de-allocate the intermediate results in a complicated
  21 ** multiple-call expression like the above?
  22 **
  23 ** There are two common solutions to this problem.  One, switch all your
  24 ** code to a language that provides automatic garbage collection, for
  25 ** example Java.  This is a fine idea and I recommend you do it wherever
  26 ** it's feasible.  Two, change your routines to use a calling convention
  27 ** that prevents people from writing multiple-call expressions like that.
  28 ** The resulting code will be somewhat clumsy-looking, but it will work
  29 ** just fine.
  30 **
  31 ** This package uses a third method, which I haven't seen used anywhere
  32 ** before.  It's simple: each number can be used precisely once, after
  33 ** which it is automatically de-allocated.  This handles the anonymous
  34 ** intermediate values perfectly.  Named values still need to be copied
  35 ** and freed explicitly.  Here's the above example using this convention:
  36 **
  37 **     d = bi_sqrt( bi_add(
  38 **             bi_multiply( bi_copy( x ), bi_copy( x ) ),
  39 **             bi_multiply( bi_copy( y ), bi_copy( y ) ) ) );
  40 **     bi_free( x );
  41 **     bi_free( y );
  42 **
  43 ** Or, since the package contains a square routine, you could just write:
  44 **
  45 **     d = bi_sqrt( bi_add( bi_square( x ), bi_square( y ) ) );
  46 **
  47 ** This time the named values are only being used once, so you don't
  48 ** have to copy and free them.
  49 **
  50 ** This really works, however you do have to be very careful when writing
  51 ** your code.  If you leave out a bi_copy() and use a value more than once,
  52 ** you'll get a runtime error about "zero refs" and a SIGFPE.  Run your
  53 ** code in a debugger, get a backtrace to see where the call was, and then
  54 ** eyeball the code there to see where you need to add the bi_copy().
  55 **
  56 **
  57 ** Copyright © 2000 by Jef Poskanzer <jef@mail.acme.com>.
  58 ** All rights reserved.
  59 **
  60 ** Redistribution and use in source and binary forms, with or without
  61 ** modification, are permitted provided that the following conditions
  62 ** are met:
  63 ** 1. Redistributions of source code must retain the above copyright
  64 **    notice, this list of conditions and the following disclaimer.
  65 ** 2. Redistributions in binary form must reproduce the above copyright
  66 **    notice, this list of conditions and the following disclaimer in the
  67 **    documentation and/or other materials provided with the distribution.
  68 **
  69 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  70 ** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  71 ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  72 ** ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  73 ** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  74 ** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  75 ** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  76 ** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  77 ** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  78 ** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  79 ** SUCH DAMAGE.
  80 */
  81
  82
  83 /* Type definition for bigints - it's an opaque type, the real definition
  84 ** is in bigint.c.
  85 */
  86 typedef void* bigint;
  87
  88
  89 /* Some convenient pre-initialized numbers.  These are all permanent,
  90 ** so you can use them as many times as you want without calling bi_copy().
  91 */
  92 extern bigint bi_0, bi_1, bi_2, bi_10, bi_m1, bi_maxint, bi_minint;
  93
  94
  95 /* Initialize the bigint package.  You must call this when your program
  96 ** starts up.
  97 */
  98 void bi_initialize( void );
  99
 100 /* Shut down the bigint package.  You should call this when your program
 101 ** exits.  It's not actually required, but it does do some consistency
 102 ** checks which help keep your program bug-free, so you really ought
 103 ** to call it.
 104 */
 105 void bi_terminate( void );
 106
 107 /* Run in unsafe mode, skipping most runtime checks.  Slightly faster.
 108 ** Once your code is debugged you can add this call after bi_initialize().
 109 */
 110 void bi_no_check( void );
 111
 112 /* Make a copy of a bigint.  You must call this if you want to use a
 113 ** bigint more than once.  (Or you can make the bigint permanent.)
 114 ** Note that this routine is very cheap - all it actually does is
 115 ** increment a reference counter.
 116 */
 117 bigint bi_copy( bigint bi );
 118
 119 /* Make a bigint permanent, so it doesn't get automatically freed when
 120 ** used as an operand.
 121 */
 122 void bi_permanent( bigint bi );
 123
 124 /* Undo bi_permanent().  The next use will free the bigint. */
 125 void bi_depermanent( bigint bi );
 126
 127 /* Explicitly free a bigint.  Normally bigints get freed automatically
 128 ** when they are used as an operand.  This routine lets you free one
 129 ** without using it.  If the bigint is permanent, this doesn't do
 130 ** anything, you have to depermanent it first.
 131 */
 132 void bi_free( bigint bi );
 133
 134 /* Compare two bigints.  Returns -1, 0, or 1. */
 135 int bi_compare( bigint bia, bigint bib );
 136
 137 /* Convert an int to a bigint. */
 138 bigint int_to_bi( int i );
 139
 140 /* Convert a string to a bigint. */
 141 bigint str_to_bi( char* str );
 142
 143 /* Convert a bigint to an int.  SIGFPE on overflow. */
 144 int bi_to_int( bigint bi );
 145
 146 /* Write a bigint to a file. */
 147 void bi_print( FILE* f, bigint bi );
 148
 149 /* Read a bigint from a file. */
 150 bigint bi_scan( FILE* f );
 151
 152
 153 /* Operations on a bigint and a regular int. */
 154
 155 /* Add an int to a bigint. */
 156 bigint bi_int_add( bigint bi, int i );
 157
 158 /* Subtract an int from a bigint. */
 159 bigint bi_int_subtract( bigint bi, int i );
 160
 161 /* Multiply a bigint by an int. */
 162 bigint bi_int_multiply( bigint bi, int i );
 163
 164 /* Divide a bigint by an int.  SIGFPE on divide-by-zero. */
 165 bigint bi_int_divide( bigint binumer, int denom );
 166
 167 /* Take the remainder of a bigint by an int, with an int result.
 168 ** SIGFPE if m is zero.
 169 */
 170 int bi_int_rem( bigint bi, int m );
 171
 172 /* Take the modulus of a bigint by an int, with an int result.
 173 ** Note that mod is not rem: mod is always within [0..m), while
 174 ** rem can be negative.  SIGFPE if m is zero or negative.
 175 */
 176 int bi_int_mod( bigint bi, int m );
 177
 178
 179 /* Basic operations on two bigints. */
 180
 181 /* Add two bigints. */
 182 bigint bi_add( bigint bia, bigint bib );
 183
 184 /* Subtract bib from bia. */
 185 bigint bi_subtract( bigint bia, bigint bib );
 186
 187 /* Multiply two bigints. */
 188 bigint bi_multiply( bigint bia, bigint bib );
 189
 190 /* Divide one bigint by another.  SIGFPE on divide-by-zero. */
 191 bigint bi_divide( bigint binumer, bigint bidenom );
 192
 193 /* Binary division of one bigint by another.  SIGFPE on divide-by-zero.
 194 ** This is here just for testing.  It's about five times slower than
 195 ** regular division.
 196 */
 197 bigint bi_binary_divide( bigint binumer, bigint bidenom );
 198
 199 /* Take the remainder of one bigint by another.  SIGFPE if bim is zero. */
 200 bigint bi_rem( bigint bia, bigint bim );
 201
 202 /* Take the modulus of one bigint by another.  Note that mod is not rem:
 203 ** mod is always within [0..bim), while rem can be negative.  SIGFPE if
 204 ** bim is zero or negative.
 205 */
 206 bigint bi_mod( bigint bia, bigint bim );
 207
 208
 209 /* Some less common operations. */
 210
 211 /* Negate a bigint. */
 212 bigint bi_negate( bigint bi );
 213
 214 /* Absolute value of a bigint. */
 215 bigint bi_abs( bigint bi );
 216
 217 /* Divide a bigint in half. */
 218 bigint bi_half( bigint bi );
 219
 220 /* Multiply a bigint by two. */
 221 bigint bi_double( bigint bi );
 222
 223 /* Square a bigint. */
 224 bigint bi_square( bigint bi );
 225
 226 /* Raise bi to the power of biexp.  SIGFPE if biexp is negative. */
 227 bigint bi_power( bigint bi, bigint biexp );
 228
 229 /* Integer square root. */
 230 bigint bi_sqrt( bigint bi );
 231
 232 /* Factorial. */
 233 bigint bi_factorial( bigint bi );
 234
 235
 236 /* Some predicates. */
 237
 238 /* 1 if the bigint is odd, 0 if it's even. */
 239 int bi_is_odd( bigint bi );
 240
 241 /* 1 if the bigint is even, 0 if it's odd. */
 242 int bi_is_even( bigint bi );
 243
 244 /* 1 if the bigint equals zero, 0 if it's nonzero. */
 245 int bi_is_zero( bigint bi );
 246
 247 /* 1 if the bigint equals one, 0 otherwise. */
 248 int bi_is_one( bigint bi );
 249
 250 /* 1 if the bigint is less than zero, 0 if it's zero or greater. */
 251 int bi_is_negative( bigint bi );
 252
 253
 254 /* Now we get into the esoteric number-theory stuff used for cryptography. */
 255
 256 /* Modular exponentiation.  Much faster than bi_mod(bi_power(bi,biexp),bim).
 257 ** Also, biexp can be negative.
 258 */
 259 bigint bi_mod_power( bigint bi, bigint biexp, bigint bim );
 260
 261 /* Modular inverse.  mod( bi * modinv(bi), bim ) == 1.  SIGFPE if bi is not
 262 ** relatively prime to bim.
 263 */
 264 bigint bi_mod_inverse( bigint bi, bigint bim );
 265
 266 /* Produce a random number in the half-open interval [0..bi).  You need
 267 ** to have called srandom() before using this.
 268 */
 269 bigint bi_random( bigint bi );
 270
 271 /* Greatest common divisor of two bigints.  Euclid's algorithm. */
 272 bigint bi_gcd( bigint bim, bigint bin );
 273
 274 /* Greatest common divisor of two bigints, plus the corresponding multipliers.
 275 ** Extended Euclid's algorithm.
 276 */
 277 bigint bi_egcd( bigint bim, bigint bin, bigint* bim_mul, bigint* bin_mul );
 278
 279 /* Least common multiple of two bigints. */
 280 bigint bi_lcm( bigint bia, bigint bib );
 281
 282 /* The Jacobi symbol.  SIGFPE if bib is even. */
 283 bigint bi_jacobi( bigint bia, bigint bib );
 284
 285 /* Probabalistic prime checking.  A non-zero return means the probability
 286 ** that bi is prime is at least 1 - 1/2 ^ certainty.
 287 */
 288 int bi_is_probable_prime( bigint bi, int certainty );
 289
 290 /* Random probabilistic prime with the specified number of bits. */
 291 bigint bi_generate_prime( int bits, int certainty );
 292
 293 /* Number of bits in the number.  The log base 2, approximately. */
 294 int bi_bits( bigint bi );