sys/include/mp.h

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