mp.h (4964B)
1 #ifndef __MP_H__ 2 #define __MP_H__ 1 3 #ifdef __cplusplus 4 extern "C" { 5 #endif 6 7 AUTOLIB(mp) 8 9 /* 10 #pragma src "/sys/src/libmp" 11 #pragma lib "libmp.a" 12 */ 13 14 #define _MPINT 1 15 16 typedef uint mpdigit; 17 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 */ 21 22 typedef struct mpint mpint; 23 24 struct mpint 25 { 26 int sign; /* +1 or -1 */ 27 int size; /* allocated digits */ 28 int top; /* significant digits */ 29 mpdigit *p; 30 char flags; 31 }; 32 33 enum 34 { 35 MPstatic= 0x01, 36 Dbytes= sizeof(mpdigit), /* bytes per digit */ 37 Dbits= Dbytes*8 /* bits per digit */ 38 }; 39 40 /* allocation */ 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); 48 49 /* random bits */ 50 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b); 51 52 /* conversion */ 53 mpint* strtomp(char*, char**, int, mpint*); /* ascii */ 54 int mpfmt(Fmt*); 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*); 68 69 /* divide 2 digits by one */ 70 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient); 71 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 */ 81 82 /* quotient = dividend/divisor, remainder = dividend % divisor */ 83 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder); 84 85 /* return neg, 0, pos as b1-b2 is neg, 0, pos */ 86 int mpcmp(mpint *b1, mpint *b2); 87 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); 90 91 /* res = b**-1 mod m */ 92 void mpinvert(mpint *b, mpint *m, mpint *res); 93 94 /* bit counting */ 95 int mpsignif(mpint*); /* number of sigificant bits in mantissa */ 96 int mplowbits0(mpint*); /* k, where n = 2**k * q for odd q */ 97 98 /* well known constants */ 99 extern mpint *mpzero, *mpone, *mptwo; 100 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); 104 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); 108 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); 112 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); 116 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); 120 121 /* sign of a - b or zero if the same */ 122 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen); 123 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); 127 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 */ 132 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 */ 137 138 struct CRTres 139 { 140 int n; /* number of residues */ 141 mpint *r[1]; /* residues */ 142 }; 143 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*); 149 150 151 /* #pragma varargck type "B" mpint* */ 152 #ifdef __cplusplus 153 } 154 #endif 155 #endif