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