mp.h 5.1 KB

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