3 mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpfactorial, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
18 void mpsetminbits(int n)
21 void mpbits(mpint *b, int n)
27 mpint* mpcopy(mpint *b)
30 void mpassign(mpint *old, mpint *new)
33 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
36 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
39 char* mptoa(mpint *b, int base, char *buf, int blen)
45 mpint* betomp(uchar *buf, uint blen, mpint *b)
48 int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
51 mpint* letomp(uchar *buf, uint blen, mpint *b)
54 int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
60 mpint* uitomp(uint, mpint*)
66 mpint* itomp(int, mpint*)
69 mpint* vtomp(vlong, mpint*)
75 mpint* uvtomp(uvlong, mpint*)
81 void mpadd(mpint *b1, mpint *b2, mpint *sum)
84 void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
87 void mpsub(mpint *b1, mpint *b2, mpint *diff)
90 void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
93 void mpleft(mpint *b, int shift, mpint *res)
96 void mpright(mpint *b, int shift, mpint *res)
99 void mpmul(mpint *b1, mpint *b2, mpint *prod)
102 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
105 void mpmod(mpint *b, mpint *m, mpint *remainder)
108 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder)
111 mpint* mpfactorial(ulong n)
114 int mpcmp(mpint *b1, mpint *b2)
117 int mpmagcmp(mpint *b1, mpint *b2)
120 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
123 void mpinvert(mpint *b, mpint *m, mpint *res)
126 int mpsignif(mpint *b)
129 int mplowbits0(mpint *b)
132 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
135 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
138 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
141 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
144 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
147 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
150 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
153 CRTpre* crtpre(int nfactors, mpint **factors)
156 CRTres* crtin(CRTpre *crt, mpint *x)
159 void crtout(CRTpre *crt, CRTres *r, mpint *x)
162 void crtprefree(CRTpre *cre)
165 void crtresfree(CRTres *res)
168 mpint *mpzero, *mpone, *mptwo
171 These routines perform extended precision integer arithmetic.
174 which points to an array of
176 stored in little-endian order:
179 typedef struct mpint mpint;
182 int sign; /* +1 or -1 */
183 int size; /* allocated digits */
184 int top; /* significant digits */
194 is architecture-dependent and defined in
195 .BR /$cputype/include/u.h .
197 are dynamically allocated and must be explicitly freed. Operations
198 grow the array of digits as needed.
200 In general, the result parameters are last in the
203 Routines that return an
207 if the result parameter is
215 These functions, in addition to
221 if the allocation fails.
223 Input and result parameters may point to the same
225 The routines check and copy where necessary.
230 with an initial allocation of
235 is zero, the allocation will be whatever was specified in the
238 or to the initial value, 1056.
243 grows the allocation of
251 bits it increases it to do so.
252 Unless you are writing new basic operations, you
253 can restrict yourself to
259 normalizes the representation by trimming any high order zero
260 digits. All routines except
262 return normalized results.
267 with the same value as
279 bit random number using the generator
282 takes a pointer to a string of uchar's and the number
292 representations using the base indicated.
293 Only the bases 10, 16, 32, and 64 are
294 supported. Anything else defaults to 16.
296 skips any leading spaces or tabs.
298 scan stops when encountering a digit not valid in the
303 is set to point to the character immediately after the
305 If the parse pterminates before any digits are found,
310 returns a pointer to the filled buffer.
315 the buffer is allocated.
321 to print hexadecimal representations of
329 to a byte array. The former creates a big endian representation,
330 the latter a little endian one.
335 it specifies the buffer of length
337 for the result. If the representation
340 bytes, the rest of the buffer is zero filled.
345 then a buffer is allocated and a pointer to it is
346 deposited in the location pointed to by
348 Sign is ignored in these conversions, i.e., the byte
349 array version is always positive.
354 convert from a big or little endian byte array at
364 it refers to a preallocated
371 a new integer is allocated and returned as the result.
373 The integer conversions are:
377 .BR mpint -> "unsigned int"
380 .BR "unsigned int" -> mpint
389 .BR mpint -> "unsigned vlong"
392 .BR "unsigned vlong" -> mpint
401 When converting to the base integer types, if the integer is too large,
402 the largest integer of the appropriate sign
403 and size is returned.
405 The mathematical functions are:
409 .BR "sum = b1 + b2" .
412 .BR "sum = abs(b1) + abs(b2)" .
415 .BR "diff = b1 - b2" .
418 .BR "diff = abs(b1) - abs(b2)" .
421 .BR "res = b<<shift" .
424 .BR "res = b>>shift" .
435 .BR "res = b**e mod m" .
438 .BR "remainder = b % m" .
441 .BR "quotient = dividend/divisor" .
442 .BR "remainder = dividend % divisor" .
449 returns -1, 0, or +1 as
451 is less than, equal to, or greater than
457 but ignores the sign and just compares magnitudes.
461 computes the greatest common denominator,
472 .BR "a*x + b*y = d" .
477 are required to be positive.
478 If called with negative arguments, it will
482 computes the multiplicative inverse of
488 returns the bit offset of the left most 1 bit in
491 returns the bit offset of the right most 1 bit.
492 For example, for 0x14,
498 The remaining routines all work on arrays of
502 They are the basis of all the other routines. They are separated out
503 to allow them to be rewritten in assembler for each architecture. There
504 is also a portable C version for each one.
508 .BR "quotient = dividend[0:1] / divisor" .
511 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
512 We assume alen >= blen and that sum has room for alen+1 digits.
515 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
516 We assume that alen >= blen and that diff has room for alen digits.
519 .BR "p[0:n] += m * b[0:n-1]" .
520 This multiplies a an array of digits times a scalar and adds it to another array.
521 We assume p has room for n+1 digits.
524 .BR "p[0:n] -= m * b[0:n-1]" .
525 This multiplies a an array of digits times a scalar and subtracts it fromo another array.
526 We assume p has room for n+1 digits. It returns +1 is the result is positive and
530 .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
531 We assume that p has room for alen*blen+1 digits.
534 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
541 are the constants 2, 1 and 0. These cannot be freed.
542 .SS "Chinese remainder theorem
544 When computing in a non-prime modulus,
546 it is possible to perform the computations on the residues modulo the prime
549 instead. Since these numbers are smaller, multiplication and exponentiation
553 computes the residues of
555 and returns them in a newly allocated structure:
557 typedef struct CRTres CRTres;
559 int n; // number of residues
560 mpint *r[n]; // residues
565 takes a residue representation of a number and converts it back into
566 the number. It also frees the residue structure.
569 saves a copy of the factors and precomputes the constants necessary
570 for converting the residue form back into a number modulo
571 the product of the factors. It returns a newly allocated structure
581 structures respectively.
