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