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" {
8 2277c5d7 2004-03-21 devnull #pragma src "/sys/src/libmp"
9 2277c5d7 2004-03-21 devnull #pragma lib "libmp.a"
12 2277c5d7 2004-03-21 devnull #define _MPINT 1
14 2277c5d7 2004-03-21 devnull typedef long mpdigit;
16 2277c5d7 2004-03-21 devnull // the code assumes mpdigit to be at least an int
17 2277c5d7 2004-03-21 devnull // mpdigit must be an atomic type. mpdigit is defined
18 2277c5d7 2004-03-21 devnull // in the architecture specific u.h
20 2277c5d7 2004-03-21 devnull typedef struct mpint mpint;
22 2277c5d7 2004-03-21 devnull struct mpint
24 2277c5d7 2004-03-21 devnull int sign; // +1 or -1
25 2277c5d7 2004-03-21 devnull int size; // allocated digits
26 2277c5d7 2004-03-21 devnull int top; // significant digits
27 2277c5d7 2004-03-21 devnull mpdigit *p;
28 2277c5d7 2004-03-21 devnull char flags;
33 2277c5d7 2004-03-21 devnull MPstatic= 0x01,
34 2277c5d7 2004-03-21 devnull Dbytes= sizeof(mpdigit), // bytes per digit
35 2277c5d7 2004-03-21 devnull Dbits= Dbytes*8 // bits per digit
38 2277c5d7 2004-03-21 devnull // allocation
39 2277c5d7 2004-03-21 devnull void mpsetminbits(int n); // newly created mpint's get at least n bits
40 2277c5d7 2004-03-21 devnull mpint* mpnew(int n); // create a new mpint with at least n bits
41 2277c5d7 2004-03-21 devnull void mpfree(mpint *b);
42 2277c5d7 2004-03-21 devnull void mpbits(mpint *b, int n); // ensure that b has at least n bits
43 2277c5d7 2004-03-21 devnull void mpnorm(mpint *b); // dump leading zeros
44 2277c5d7 2004-03-21 devnull mpint* mpcopy(mpint *b);
45 2277c5d7 2004-03-21 devnull void mpassign(mpint *old, mpint *new);
47 2277c5d7 2004-03-21 devnull // random bits
48 2277c5d7 2004-03-21 devnull mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
50 2277c5d7 2004-03-21 devnull // conversion
51 2277c5d7 2004-03-21 devnull mpint* strtomp(char*, char**, int, mpint*); // ascii
52 2277c5d7 2004-03-21 devnull int mpfmt(Fmt*);
53 2277c5d7 2004-03-21 devnull char* mptoa(mpint*, int, char*, int);
54 2277c5d7 2004-03-21 devnull mpint* letomp(uchar*, uint, mpint*); // byte array, little-endian
55 2277c5d7 2004-03-21 devnull int mptole(mpint*, uchar*, uint, uchar**);
56 2277c5d7 2004-03-21 devnull mpint* betomp(uchar*, uint, mpint*); // byte array, little-endian
57 2277c5d7 2004-03-21 devnull int mptobe(mpint*, uchar*, uint, uchar**);
58 2277c5d7 2004-03-21 devnull uint mptoui(mpint*); // unsigned int
59 2277c5d7 2004-03-21 devnull mpint* uitomp(uint, mpint*);
60 2277c5d7 2004-03-21 devnull int mptoi(mpint*); // int
61 2277c5d7 2004-03-21 devnull mpint* itomp(int, mpint*);
62 2277c5d7 2004-03-21 devnull uvlong mptouv(mpint*); // unsigned vlong
63 2277c5d7 2004-03-21 devnull mpint* uvtomp(uvlong, mpint*);
64 2277c5d7 2004-03-21 devnull vlong mptov(mpint*); // vlong
65 2277c5d7 2004-03-21 devnull mpint* vtomp(vlong, mpint*);
67 2277c5d7 2004-03-21 devnull // divide 2 digits by one
68 2277c5d7 2004-03-21 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
70 2277c5d7 2004-03-21 devnull // in the following, the result mpint may be
71 2277c5d7 2004-03-21 devnull // the same as one of the inputs.
72 2277c5d7 2004-03-21 devnull void mpadd(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2
73 2277c5d7 2004-03-21 devnull void mpsub(mpint *b1, mpint *b2, mpint *diff); // diff = b1-b2
74 2277c5d7 2004-03-21 devnull void mpleft(mpint *b, int shift, mpint *res); // res = b<<shift
75 2277c5d7 2004-03-21 devnull void mpright(mpint *b, int shift, mpint *res); // res = b>>shift
76 2277c5d7 2004-03-21 devnull void mpmul(mpint *b1, mpint *b2, mpint *prod); // prod = b1*b2
77 2277c5d7 2004-03-21 devnull void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); // res = b**e mod m
78 2277c5d7 2004-03-21 devnull void mpmod(mpint *b, mpint *m, mpint *remainder); // remainder = b mod m
80 2277c5d7 2004-03-21 devnull // quotient = dividend/divisor, remainder = dividend % divisor
81 2277c5d7 2004-03-21 devnull void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
83 2277c5d7 2004-03-21 devnull // return neg, 0, pos as b1-b2 is neg, 0, pos
84 2277c5d7 2004-03-21 devnull int mpcmp(mpint *b1, mpint *b2);
86 2277c5d7 2004-03-21 devnull // extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d
87 2277c5d7 2004-03-21 devnull void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
89 2277c5d7 2004-03-21 devnull // res = b**-1 mod m
90 2277c5d7 2004-03-21 devnull void mpinvert(mpint *b, mpint *m, mpint *res);
92 2277c5d7 2004-03-21 devnull // bit counting
93 2277c5d7 2004-03-21 devnull int mpsignif(mpint*); // number of sigificant bits in mantissa
94 2277c5d7 2004-03-21 devnull int mplowbits0(mpint*); // k, where n = 2**k * q for odd q
96 2277c5d7 2004-03-21 devnull // well known constants
97 2277c5d7 2004-03-21 devnull extern mpint *mpzero, *mpone, *mptwo;
99 2277c5d7 2004-03-21 devnull // sum[0:alen] = a[0:alen-1] + b[0:blen-1]
100 2277c5d7 2004-03-21 devnull // prereq: alen >= blen, sum has room for alen+1 digits
101 2277c5d7 2004-03-21 devnull void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
103 2277c5d7 2004-03-21 devnull // diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]
104 2277c5d7 2004-03-21 devnull // prereq: alen >= blen, diff has room for alen digits
105 2277c5d7 2004-03-21 devnull void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
107 2277c5d7 2004-03-21 devnull // p[0:n] += m * b[0:n-1]
108 2277c5d7 2004-03-21 devnull // prereq: p has room for n+1 digits
109 2277c5d7 2004-03-21 devnull void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
111 2277c5d7 2004-03-21 devnull // p[0:n] -= m * b[0:n-1]
112 2277c5d7 2004-03-21 devnull // prereq: p has room for n+1 digits
113 2277c5d7 2004-03-21 devnull int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
115 2277c5d7 2004-03-21 devnull // p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1]
116 2277c5d7 2004-03-21 devnull // prereq: alen >= blen, p has room for m*n digits
117 2277c5d7 2004-03-21 devnull void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
119 2277c5d7 2004-03-21 devnull // sign of a - b or zero if the same
120 2277c5d7 2004-03-21 devnull int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
122 2277c5d7 2004-03-21 devnull // divide the 2 digit dividend by the one digit divisor and stick in quotient
123 2277c5d7 2004-03-21 devnull // we assume that the result is one digit - overflow is all 1's
124 2277c5d7 2004-03-21 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
126 2277c5d7 2004-03-21 devnull // playing with magnitudes
127 2277c5d7 2004-03-21 devnull int mpmagcmp(mpint *b1, mpint *b2);
128 2277c5d7 2004-03-21 devnull void mpmagadd(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2
129 2277c5d7 2004-03-21 devnull void mpmagsub(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2
131 2277c5d7 2004-03-21 devnull // chinese remainder theorem
132 2277c5d7 2004-03-21 devnull typedef struct CRTpre CRTpre; // precomputed values for converting
133 2277c5d7 2004-03-21 devnull // twixt residues and mpint
134 2277c5d7 2004-03-21 devnull typedef struct CRTres CRTres; // residue form of an mpint
136 2277c5d7 2004-03-21 devnull struct CRTres
138 2277c5d7 2004-03-21 devnull int n; // number of residues
139 2277c5d7 2004-03-21 devnull mpint *r[1]; // residues
142 2277c5d7 2004-03-21 devnull CRTpre* crtpre(int, mpint**); // precompute conversion values
143 2277c5d7 2004-03-21 devnull CRTres* crtin(CRTpre*, mpint*); // convert mpint to residues
144 2277c5d7 2004-03-21 devnull void crtout(CRTpre*, CRTres*, mpint*); // convert residues to mpint
145 2277c5d7 2004-03-21 devnull void crtprefree(CRTpre*);
146 2277c5d7 2004-03-21 devnull void crtresfree(CRTres*);
149 2277c5d7 2004-03-21 devnull /* #pragma varargck type "B" mpint* */
150 2277c5d7 2004-03-21 devnull #ifdef __cplusplus
