1 2277c5d7 2004-03-21 devnull #ifndef __MP_H__
2 2277c5d7 2004-03-21 devnull #define __MP_H__ 1
3 2277c5d7 2004-03-21 devnull #ifdef __cplusplus
4 2277c5d7 2004-03-21 devnull extern "C" {
7 1a0954ab 2005-01-04 devnull AUTOLIB(mp)
10 2277c5d7 2004-03-21 devnull #pragma src "/sys/src/libmp"
11 2277c5d7 2004-03-21 devnull #pragma lib "libmp.a"
14 2277c5d7 2004-03-21 devnull #define _MPINT 1
16 e290e875 2007-01-15 devnull typedef uint mpdigit;
18 cbeb0b26 2006-04-01 devnull /* the code assumes mpdigit to be at least an int */
19 cbeb0b26 2006-04-01 devnull /* mpdigit must be an atomic type. mpdigit is defined */
20 cbeb0b26 2006-04-01 devnull /* in the architecture specific u.h */
22 2277c5d7 2004-03-21 devnull typedef struct mpint mpint;
24 2277c5d7 2004-03-21 devnull struct mpint
26 cbeb0b26 2006-04-01 devnull int sign; /* +1 or -1 */
27 cbeb0b26 2006-04-01 devnull int size; /* allocated digits */
28 cbeb0b26 2006-04-01 devnull int top; /* significant digits */
29 2277c5d7 2004-03-21 devnull mpdigit *p;
30 2277c5d7 2004-03-21 devnull char flags;
35 2277c5d7 2004-03-21 devnull MPstatic= 0x01,
36 cbeb0b26 2006-04-01 devnull Dbytes= sizeof(mpdigit), /* bytes per digit */
37 cbeb0b26 2006-04-01 devnull Dbits= Dbytes*8 /* bits per digit */
40 cbeb0b26 2006-04-01 devnull /* allocation */
41 cbeb0b26 2006-04-01 devnull void mpsetminbits(int n); /* newly created mpint's get at least n bits */
42 cbeb0b26 2006-04-01 devnull mpint* mpnew(int n); /* create a new mpint with at least n bits */
43 2277c5d7 2004-03-21 devnull void mpfree(mpint *b);
44 cbeb0b26 2006-04-01 devnull void mpbits(mpint *b, int n); /* ensure that b has at least n bits */
45 cbeb0b26 2006-04-01 devnull void mpnorm(mpint *b); /* dump leading zeros */
46 2277c5d7 2004-03-21 devnull mpint* mpcopy(mpint *b);
47 2277c5d7 2004-03-21 devnull void mpassign(mpint *old, mpint *new);
49 cbeb0b26 2006-04-01 devnull /* random bits */
50 2277c5d7 2004-03-21 devnull mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
52 cbeb0b26 2006-04-01 devnull /* conversion */
53 cbeb0b26 2006-04-01 devnull mpint* strtomp(char*, char**, int, mpint*); /* ascii */
54 2277c5d7 2004-03-21 devnull int mpfmt(Fmt*);
55 2277c5d7 2004-03-21 devnull char* mptoa(mpint*, int, char*, int);
56 cbeb0b26 2006-04-01 devnull mpint* letomp(uchar*, uint, mpint*); /* byte array, little-endian */
57 2277c5d7 2004-03-21 devnull int mptole(mpint*, uchar*, uint, uchar**);
58 cbeb0b26 2006-04-01 devnull mpint* betomp(uchar*, uint, mpint*); /* byte array, little-endian */
59 2277c5d7 2004-03-21 devnull int mptobe(mpint*, uchar*, uint, uchar**);
60 cbeb0b26 2006-04-01 devnull uint mptoui(mpint*); /* unsigned int */
61 2277c5d7 2004-03-21 devnull mpint* uitomp(uint, mpint*);
62 cbeb0b26 2006-04-01 devnull int mptoi(mpint*); /* int */
63 2277c5d7 2004-03-21 devnull mpint* itomp(int, mpint*);
64 cbeb0b26 2006-04-01 devnull uvlong mptouv(mpint*); /* unsigned vlong */
65 2277c5d7 2004-03-21 devnull mpint* uvtomp(uvlong, mpint*);
66 cbeb0b26 2006-04-01 devnull vlong mptov(mpint*); /* vlong */
67 2277c5d7 2004-03-21 devnull mpint* vtomp(vlong, mpint*);
69 cbeb0b26 2006-04-01 devnull /* divide 2 digits by one */
70 2277c5d7 2004-03-21 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
72 cbeb0b26 2006-04-01 devnull /* in the following, the result mpint may be */
73 cbeb0b26 2006-04-01 devnull /* the same as one of the inputs. */
74 cbeb0b26 2006-04-01 devnull void mpadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
75 cbeb0b26 2006-04-01 devnull void mpsub(mpint *b1, mpint *b2, mpint *diff); /* diff = b1-b2 */
76 cbeb0b26 2006-04-01 devnull void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
77 cbeb0b26 2006-04-01 devnull void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
78 cbeb0b26 2006-04-01 devnull void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
79 cbeb0b26 2006-04-01 devnull void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
80 cbeb0b26 2006-04-01 devnull void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
82 cbeb0b26 2006-04-01 devnull /* quotient = dividend/divisor, remainder = dividend % divisor */
83 2277c5d7 2004-03-21 devnull void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
85 cbeb0b26 2006-04-01 devnull /* return neg, 0, pos as b1-b2 is neg, 0, pos */
86 2277c5d7 2004-03-21 devnull int mpcmp(mpint *b1, mpint *b2);
88 cbeb0b26 2006-04-01 devnull /* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
89 2277c5d7 2004-03-21 devnull void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
91 cbeb0b26 2006-04-01 devnull /* res = b**-1 mod m */
92 2277c5d7 2004-03-21 devnull void mpinvert(mpint *b, mpint *m, mpint *res);
94 cbeb0b26 2006-04-01 devnull /* bit counting */
95 cbeb0b26 2006-04-01 devnull int mpsignif(mpint*); /* number of sigificant bits in mantissa */
96 cbeb0b26 2006-04-01 devnull int mplowbits0(mpint*); /* k, where n = 2**k * q for odd q */
98 cbeb0b26 2006-04-01 devnull /* well known constants */
99 2277c5d7 2004-03-21 devnull extern mpint *mpzero, *mpone, *mptwo;
101 cbeb0b26 2006-04-01 devnull /* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
102 cbeb0b26 2006-04-01 devnull /* prereq: alen >= blen, sum has room for alen+1 digits */
103 2277c5d7 2004-03-21 devnull void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
105 cbeb0b26 2006-04-01 devnull /* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
106 cbeb0b26 2006-04-01 devnull /* prereq: alen >= blen, diff has room for alen digits */
107 2277c5d7 2004-03-21 devnull void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
109 cbeb0b26 2006-04-01 devnull /* p[0:n] += m * b[0:n-1] */
110 cbeb0b26 2006-04-01 devnull /* prereq: p has room for n+1 digits */
111 2277c5d7 2004-03-21 devnull void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
113 cbeb0b26 2006-04-01 devnull /* p[0:n] -= m * b[0:n-1] */
114 cbeb0b26 2006-04-01 devnull /* prereq: p has room for n+1 digits */
115 2277c5d7 2004-03-21 devnull int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
117 cbeb0b26 2006-04-01 devnull /* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
118 cbeb0b26 2006-04-01 devnull /* prereq: alen >= blen, p has room for m*n digits */
119 2277c5d7 2004-03-21 devnull void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
121 cbeb0b26 2006-04-01 devnull /* sign of a - b or zero if the same */
122 2277c5d7 2004-03-21 devnull int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
124 cbeb0b26 2006-04-01 devnull /* divide the 2 digit dividend by the one digit divisor and stick in quotient */
125 cbeb0b26 2006-04-01 devnull /* we assume that the result is one digit - overflow is all 1's */
126 2277c5d7 2004-03-21 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
128 cbeb0b26 2006-04-01 devnull /* playing with magnitudes */
129 2277c5d7 2004-03-21 devnull int mpmagcmp(mpint *b1, mpint *b2);
130 cbeb0b26 2006-04-01 devnull void mpmagadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
131 cbeb0b26 2006-04-01 devnull void mpmagsub(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
133 cbeb0b26 2006-04-01 devnull /* chinese remainder theorem */
134 cbeb0b26 2006-04-01 devnull typedef struct CRTpre CRTpre; /* precomputed values for converting */
135 cbeb0b26 2006-04-01 devnull /* twixt residues and mpint */
136 cbeb0b26 2006-04-01 devnull typedef struct CRTres CRTres; /* residue form of an mpint */
138 2277c5d7 2004-03-21 devnull struct CRTres
140 cbeb0b26 2006-04-01 devnull int n; /* number of residues */
141 cbeb0b26 2006-04-01 devnull mpint *r[1]; /* residues */
144 cbeb0b26 2006-04-01 devnull CRTpre* crtpre(int, mpint**); /* precompute conversion values */
145 cbeb0b26 2006-04-01 devnull CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
146 cbeb0b26 2006-04-01 devnull void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
147 2277c5d7 2004-03-21 devnull void crtprefree(CRTpre*);
148 2277c5d7 2004-03-21 devnull void crtresfree(CRTres*);
151 2277c5d7 2004-03-21 devnull /* #pragma varargck type "B" mpint* */
152 2277c5d7 2004-03-21 devnull #ifdef __cplusplus
