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