mp.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148
  1. /*
  2. * This file is part of the UCB release of Plan 9. It is subject to the license
  3. * terms in the LICENSE file found in the top-level directory of this
  4. * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
  5. * part of the UCB release of Plan 9, including this file, may be copied,
  6. * modified, propagated, or distributed except according to the terms contained
  7. * in the LICENSE file.
  8. */
  9. #define _MPINT 1
  10. /*
  11. * the code assumes mpdigit to be at least an int
  12. * mpdigit must be an atomic type. mpdigit is defined
  13. * in the architecture specific u.h
  14. */
  15. typedef struct mpint mpint;
  16. struct mpint
  17. {
  18. int sign; /* +1 or -1 */
  19. int size; /* allocated digits */
  20. int top; /* significant digits */
  21. mpdigit *p;
  22. char flags;
  23. };
  24. enum
  25. {
  26. MPstatic= 0x01,
  27. Dbytes= sizeof(mpdigit), /* bytes per digit */
  28. Dbits= Dbytes*8 /* bits per digit */
  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. /* random bits */
  39. mpint* mprand(int bits, void (*gen)(uint8_t*, int), mpint *b);
  40. /* conversion */
  41. mpint* strtomp(char*, char**, int, mpint*); /* ascii */
  42. int mpfmt(Fmt*);
  43. char* mptoa(mpint*, int, char*, int);
  44. mpint* letomp(uint8_t*, uint, mpint*); /* byte array, little-endian */
  45. int mptole(mpint*, uint8_t*, uint, uint8_t**);
  46. mpint* betomp(uint8_t*, uint, mpint*); /* byte array, little-endian */
  47. int mptobe(mpint*, uint8_t*, uint, uint8_t**);
  48. uint mptoui(mpint*); /* unsigned int */
  49. mpint* uitomp(uint, mpint*);
  50. int mptoi(mpint*); /* int */
  51. mpint* itomp(int, mpint*);
  52. uint64_t mptouv(mpint*); /* unsigned vlong */
  53. mpint* uvtomp(uint64_t, mpint*);
  54. int64_t mptov(mpint*); /* vlong */
  55. mpint* vtomp(int64_t, mpint*);
  56. /* divide 2 digits by one */
  57. void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
  58. /* in the following, the result mpint may be */
  59. /* the same as one of the inputs. */
  60. void mpadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
  61. void mpsub(mpint *b1, mpint *b2, mpint *diff); /* diff = b1-b2 */
  62. void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
  63. void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
  64. void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
  65. void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
  66. void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
  67. /* quotient = dividend/divisor, remainder = dividend % divisor */
  68. void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
  69. /* return neg, 0, pos as b1-b2 is neg, 0, pos */
  70. int mpcmp(mpint *b1, mpint *b2);
  71. /* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
  72. void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
  73. /* res = b**-1 mod m */
  74. void mpinvert(mpint *b, mpint *m, mpint *res);
  75. /* bit counting */
  76. int mpsignif(mpint*); /* number of sigificant bits in mantissa */
  77. int mplowbits0(mpint*); /* k, where n = 2**k * q for odd q */
  78. /* well known constants */
  79. extern mpint *mpzero, *mpone, *mptwo;
  80. /* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
  81. /* prereq: alen >= blen, sum has room for alen+1 digits */
  82. void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
  83. /* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
  84. /* prereq: alen >= blen, diff has room for alen digits */
  85. void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
  86. /* p[0:n] += m * b[0:n-1] */
  87. /* prereq: p has room for n+1 digits */
  88. void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
  89. /* p[0:n] -= m * b[0:n-1] */
  90. /* prereq: p has room for n+1 digits */
  91. int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
  92. /* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
  93. /* prereq: alen >= blen, p has room for m*n digits */
  94. void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
  95. /* sign of a - b or zero if the same */
  96. int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
  97. /* divide the 2 digit dividend by the one digit divisor and stick in quotient */
  98. /* we assume that the result is one digit - overflow is all 1's */
  99. void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
  100. /* playing with magnitudes */
  101. int mpmagcmp(mpint *b1, mpint *b2);
  102. void mpmagadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
  103. void mpmagsub(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
  104. /* chinese remainder theorem */
  105. typedef struct CRTpre CRTpre; /* precomputed values for converting */
  106. /* twixt residues and mpint */
  107. typedef struct CRTres CRTres; /* residue form of an mpint */
  108. struct CRTres
  109. {
  110. int n; /* number of residues */
  111. mpint *r[1]; /* residues */
  112. };
  113. CRTpre* crtpre(int, mpint**); /* precompute conversion values */
  114. CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
  115. void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
  116. void crtprefree(CRTpre*);
  117. void crtresfree(CRTres*);