mp.h 4.7 KB

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