mp.h 5.3 KB

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