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