home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / BN64.C < prev    next >
Text File  |  1996-09-22  |  22KB  |  924 lines
  1. /*
  2.  * bn64.c - the high-level bignum interface
  3.  *
  4.  * Like lbn64.c, this reserves the string "64" for textual replacement.
  5.  * The string must not appear anywhere unless it is intended to be replaced
  6.  * to generate other bignum interface functions.
  7.  *
  8.  * Copyright (c) 1995  Colin Plumb.  All rights reserved.
  9.  * For licensing and other legal details, see the file legal.c.
  10.  */
  11.  
  12. #ifndef HAVE_CONFIG_H
  13. #define HAVE_CONFIG_H 0
  14. #endif
  15. #if HAVE_CONFIG_H
  16. #if defined( INC_ALL ) || defined( INC_CHILD )
  17.   #include "config.h"
  18. #else
  19.   #include "bnlib/config.h"
  20. #endif /* Compiler-specific includes */
  21. #endif
  22.  
  23. /*
  24.  * Some compilers complain about #if FOO if FOO isn't defined,
  25.  * so do the ANSI-mandated thing explicitly...
  26.  */
  27. #ifndef NO_ASSERT_H
  28. #define NO_ASSERT_H 0
  29. #endif
  30. #ifndef NO_STRING_H
  31. #define NO_STRING_H 0
  32. #endif
  33. #ifndef HAVE_STRINGS_H
  34. #define HAVE_STRINGS_H 0
  35. #endif
  36. #ifndef NEED_MEMORY_H
  37. #define NEED_MEMORY_H 0
  38. #endif
  39.  
  40. #if !NO_ASSERT_H
  41. #include <assert.h>
  42. #else
  43. #define assert(x) (void)0
  44. #endif
  45.  
  46. #if !NO_STRING_H
  47. #include <string.h>    /* for memmove() in bnMakeOdd */
  48. #elif HAVE_STRINGS_H
  49. #include <strings.h>
  50. #endif
  51. #if NEED_MEMORY_H
  52. #include <memory.h>
  53. #endif
  54.  
  55. /*
  56.  * This was useful during debugging, so it's left in here.
  57.  * You can ignore it.  DBMALLOC is generally undefined.
  58.  */
  59. #ifndef DBMALLOC
  60. #define DBAMLLOC 0
  61. #endif
  62. #if DBMALLOC
  63. #include "../dbmalloc/malloc.h"
  64. #define MALLOCDB malloc_chain_check(1)
  65. #else
  66. #define MALLOCDB (void)0
  67. #endif
  68.  
  69. #if defined( INC_ALL ) || defined( INC_CHILD )
  70.   #include "lbn.h"
  71.   #include "lbn64.h"
  72.   #include "lbnmem.h"
  73.   #include "bn64.h"
  74.   #include "bn.h"
  75.  
  76.   /* Work-arounds for some particularly broken systems */
  77.   #include "kludge.h"    /* For memmove() */
  78. #else
  79.   #include "bnlib/lbn.h"
  80.   #include "bnlib/lbn64.h"
  81.   #include "bnlib/lbnmem.h"
  82.   #include "bnlib/bn64.h"
  83.   #include "bnlib/bn.h"
  84.  
  85.   /* Work-arounds for some particularly broken systems */
  86.   #include "bnlib/kludge.h"    /* For memmove() */
  87. #endif /* Compiler-specific includes */
  88.  
  89. /* Functions */
  90. void
  91. bnInit_64(void)
  92. {
  93.     bnEnd = bnEnd_64;
  94.     bnPrealloc = bnPrealloc_64;
  95.     bnCopy = bnCopy_64;
  96.     bnNorm = bnNorm_64;
  97.     bnExtractBigBytes = bnExtractBigBytes_64;
  98.     bnInsertBigBytes = bnInsertBigBytes_64;
  99.     bnExtractLittleBytes = bnExtractLittleBytes_64;
  100.     bnInsertLittleBytes = bnInsertLittleBytes_64;
  101.     bnLSWord = bnLSWord_64;
  102.     bnBits = bnBits_64;
  103.     bnAdd = bnAdd_64;
  104.     bnSub = bnSub_64;
  105.     bnCmpQ = bnCmpQ_64;
  106.     bnSetQ = bnSetQ_64;
  107.     bnAddQ = bnAddQ_64;
  108.     bnSubQ = bnSubQ_64;
  109.     bnCmp = bnCmp_64;
  110.     bnSquare = bnSquare_64;
  111.     bnMul = bnMul_64;
  112.     bnMulQ = bnMulQ_64;
  113.     bnDivMod = bnDivMod_64;
  114.     bnMod = bnMod_64;
  115.     bnModQ = bnModQ_64;
  116.     bnExpMod = bnExpMod_64;
  117.     bnDoubleExpMod = bnDoubleExpMod_64;
  118.     bnTwoExpMod = bnTwoExpMod_64;
  119.     bnGcd = bnGcd_64;
  120.     bnInv = bnInv_64;
  121.     bnLShift = bnLShift_64;
  122.     bnRShift = bnRShift_64;
  123.     bnMakeOdd = bnMakeOdd_64;
  124. }
  125.  
  126. void
  127. bnEnd_64(struct BigNum *bn)
  128. {
  129.     if (bn->ptr) {
  130.         LBNFREE((BNWORD64 *)bn->ptr, bn->allocated);
  131.         bn->ptr = 0;
  132.     }
  133.     bn->size = 0;
  134.     bn->allocated = 0;
  135.  
  136.     MALLOCDB;
  137. }
  138.  
  139. /* Internal function.  It operates in words. */
  140. static int
  141. bnResize_64(struct BigNum *bn, unsigned len)
  142. {
  143.     void *p;
  144.  
  145.     /* Round size up: most mallocs impose 8-byte granularity anyway */
  146.     len = (len + (8/sizeof(BNWORD64) - 1)) & ~(8/sizeof(BNWORD64) - 1);
  147.     p = LBNREALLOC((BNWORD64 *)bn->ptr, bn->allocated, len);
  148.     if (!p)
  149.         return -1;
  150.     bn->ptr = p;
  151.     bn->allocated = len;
  152.  
  153.     MALLOCDB;
  154.  
  155.     return 0;
  156. }
  157.  
  158. #define bnSizeCheck(bn, size) \
  159.     if (bn->allocated < size && bnResize_64(bn, size) < 0) \
  160.         return -1
  161.  
  162. int
  163. bnPrealloc_64(struct BigNum *bn, unsigned bits)
  164. {
  165.     bits = (bits + 64-1)/64;
  166.     bnSizeCheck(bn, bits);
  167.     MALLOCDB;
  168.     return 0;
  169. }
  170.  
  171. int
  172. bnCopy_64(struct BigNum *dest, struct BigNum const *src)
  173. {
  174.     bnSizeCheck(dest, src->size);
  175.     dest->size = src->size;
  176.     lbnCopy_64((BNWORD64 *)dest->ptr, (BNWORD64 *)src->ptr, src->size);
  177.     MALLOCDB;
  178.     return 0;
  179. }
  180.  
  181. void
  182. bnNorm_64(struct BigNum *bn)
  183. {
  184.     bn->size = lbnNorm_64((BNWORD64 *)bn->ptr, bn->size);
  185. }
  186.  
  187. /*
  188.  * Convert a bignum to big-endian bytes.  Returns, in big-endian form, a
  189.  * substring of the bignum starting from lsbyte and "len" bytes long.
  190.  * Unused high-order (leading) bytes are filled with 0.
  191.  */
  192. void
  193. bnExtractBigBytes_64(struct BigNum const *bn, unsigned char *dest,
  194.                   unsigned lsbyte, unsigned len)
  195. {
  196.     unsigned s = bn->size * (64 / 8);
  197.  
  198.     /* Fill unused leading bytes with 0 */
  199.     while (s < lsbyte+len) {
  200.         *dest++ = 0;
  201.         len--;
  202.     }
  203.  
  204.     if (len)
  205.         lbnExtractBigBytes_64((BNWORD64 *)bn->ptr, dest, lsbyte, len);
  206.     MALLOCDB;
  207. }
  208.  
  209. int
  210. bnInsertBigBytes_64(struct BigNum *bn, unsigned char const *src,
  211.                  unsigned lsbyte, unsigned len)
  212. {
  213.     unsigned s = bn->size;
  214.     unsigned words = (len+lsbyte+sizeof(BNWORD64)-1) / sizeof(BNWORD64);
  215.  
  216.     /* Pad with zeros as required */
  217.     bnSizeCheck(bn, words);
  218.  
  219.     if (s < words) {
  220.         lbnZero_64((BNWORD64 *)bn->ptr BIGLITTLE(-s,+s), words-s);
  221.         s = words;
  222.     }
  223.  
  224.     lbnInsertBigBytes_64((BNWORD64 *)bn->ptr, src, lsbyte, len);
  225.  
  226.     bn->size = lbnNorm_64((BNWORD64 *)bn->ptr, s);
  227.  
  228.     MALLOCDB;
  229.     return 0;
  230. }
  231.  
  232.  
  233. /*
  234.  * Convert a bignum to little-endian bytes.  Returns, in little-endian form, a
  235.  * substring of the bignum starting from lsbyte and "len" bytes long.
  236.  * Unused high-order (trailing) bytes are filled with 0.
  237.  */
  238. void
  239. bnExtractLittleBytes_64(struct BigNum const *bn, unsigned char *dest,
  240.                   unsigned lsbyte, unsigned len)
  241. {
  242.     unsigned s = bn->size * (64 / 8);
  243.  
  244.     /* Fill unused leading bytes with 0 */
  245.     while (s < lsbyte+len)
  246.         dest[--len] = 0;
  247.  
  248.     if (len)
  249.         lbnExtractLittleBytes_64((BNWORD64 *)bn->ptr, dest,
  250.                                  lsbyte, len);
  251.     MALLOCDB;
  252. }
  253.  
  254. int
  255. bnInsertLittleBytes_64(struct BigNum *bn, unsigned char const *src,
  256.                        unsigned lsbyte, unsigned len)
  257. {
  258.     unsigned s = bn->size;
  259.     unsigned words = (len+lsbyte+sizeof(BNWORD64)-1) / sizeof(BNWORD64);
  260.  
  261.     /* Pad with zeros as required */
  262.     bnSizeCheck(bn, words);
  263.  
  264.     if (s < words) {
  265.         lbnZero_64((BNWORD64 *)bn->ptr BIGLITTLE(-s,+s), words-s);
  266.         s = words;
  267.     }
  268.  
  269.     lbnInsertLittleBytes_64((BNWORD64 *)bn->ptr, src, lsbyte, len);
  270.  
  271.     bn->size = lbnNorm_64((BNWORD64 *)bn->ptr, s);
  272.  
  273.     MALLOCDB;
  274.     return 0;
  275. }
  276.  
  277. /* Return the least-significant word of the input. */
  278. unsigned
  279. bnLSWord_64(struct BigNum const *src)
  280. {
  281.     return src->size ? (unsigned)((BNWORD64 *)src->ptr)[BIGLITTLE(-1,0)]: 0;
  282. }
  283.  
  284. unsigned
  285. bnBits_64(struct BigNum const *src)
  286. {
  287.     return lbnBits_64((BNWORD64 *)src->ptr, src->size);
  288. }
  289.  
  290. int
  291. bnAdd_64(struct BigNum *dest, struct BigNum const *src)
  292. {
  293.     unsigned s = src->size, d = dest->size;
  294.     BNWORD64 t;
  295.  
  296.     if (!s)
  297.         return 0;
  298.  
  299.     bnSizeCheck(dest, s);
  300.  
  301.     if (d < s) {
  302.         lbnZero_64((BNWORD64 *)dest->ptr BIGLITTLE(-d,+d), s-d);
  303.         dest->size = d = s;
  304.         MALLOCDB;
  305.     }
  306.     t = lbnAddN_64((BNWORD64 *)dest->ptr, (BNWORD64 *)src->ptr, s);
  307.     MALLOCDB;
  308.     if (t) {
  309.         if (d > s) {
  310.             t = lbnAdd1_64((BNWORD64 *)dest->ptr BIGLITTLE(-s,+s),
  311.                            d-s, t);
  312.             MALLOCDB;
  313.         }
  314.         if (t) {
  315.             bnSizeCheck(dest, d+1);
  316.             ((BNWORD64 *)dest->ptr)[BIGLITTLE(-1-d,d)] = t;
  317.             dest->size = d+1;
  318.         }
  319.     }
  320.     return 0;
  321. }
  322.  
  323. /*
  324.  * dest -= src.
  325.  * If dest goes negative, this produces the absolute value of
  326.  * the difference (the negative of the true value) and returns 1.
  327.  * Otherwise, it returls 0.
  328.  */
  329. int
  330. bnSub_64(struct BigNum *dest, struct BigNum const *src)
  331. {
  332.     unsigned s = src->size, d = dest->size;
  333.     BNWORD64 t;
  334.  
  335.     if (d < s  &&  d < (s = lbnNorm_64((BNWORD64 *)src->ptr, s))) {
  336.         bnSizeCheck(dest, s);
  337.         lbnZero_64((BNWORD64 *)dest->ptr BIGLITTLE(-d,+d), s-d);
  338.         dest->size = d = s;
  339.         MALLOCDB;
  340.     }
  341.     if (!s)
  342.         return 0;
  343.     t = lbnSubN_64((BNWORD64 *)dest->ptr, (BNWORD64 *)src->ptr, s);
  344.     MALLOCDB;
  345.     if (t) {
  346.         if (d > s) {
  347.             t = lbnSub1_64((BNWORD64 *)dest->ptr BIGLITTLE(-s,+s),
  348.                            d-s, t);
  349.             MALLOCDB;
  350.         }
  351.         if (t) {
  352.             lbnNeg_64((BNWORD64 *)dest->ptr, d);
  353.             dest->size = lbnNorm_64((BNWORD64 *)dest->ptr,
  354.                                     dest->size);
  355.             MALLOCDB;
  356.             return 1;
  357.         }
  358.     }
  359.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, dest->size);
  360.     return 0;
  361. }
  362.  
  363. /*
  364.  * Compare the BigNum to the given value, which must be < 65536.
  365.  * Returns -1. 0 or 1 if a<b, a == b or a>b.
  366.  * a <=> b --> bnCmpQ(a,b) <=> 0
  367.  */
  368. int
  369. bnCmpQ_64(struct BigNum const *a, unsigned b)
  370. {
  371.     unsigned t;
  372.     BNWORD64 v;
  373.  
  374.     t = lbnNorm_64((BNWORD64 *)a->ptr, a->size);
  375.     /* If a is more than one word long or zero, it's easy... */
  376.     if (t != 1)
  377.         return (t > 1) ? 1 : (b ? -1 : 0);
  378.     v = (unsigned)((BNWORD64 *)a->ptr)[BIGLITTLE(-1,0)];
  379.     return (v > b) ? 1 : ((v < b) ? -1 : 0);
  380. }
  381.  
  382. int
  383. bnSetQ_64(struct BigNum *dest, unsigned src)
  384. {
  385.     if (src) {
  386.         bnSizeCheck(dest, 1);
  387.  
  388.         ((BNWORD64 *)dest->ptr)[BIGLITTLE(-1,0)] = (BNWORD64)src;
  389.         dest->size = 1;
  390.     } else {
  391.         dest->size = 0;
  392.     }
  393.     return 0;
  394. }
  395.  
  396. int
  397. bnAddQ_64(struct BigNum *dest, unsigned src)
  398. {
  399.     BNWORD64 t;
  400.  
  401.     if (!dest->size)
  402.         return bnSetQ(dest, src);
  403.     
  404.     t = lbnAdd1_64((BNWORD64 *)dest->ptr, dest->size, (BNWORD64)src);
  405.     MALLOCDB;
  406.     if (t) {
  407.         src = dest->size;
  408.         bnSizeCheck(dest, src+1);
  409.         ((BNWORD64 *)dest->ptr)[BIGLITTLE(-1-src,src)] = t;
  410.         dest->size = src+1;
  411.     }
  412.     return 0;
  413. }
  414.  
  415. /*
  416.  * Return value as for bnSub: 1 if subtract underflowed, in which
  417.  * case the return is the negative of the computed value.
  418.  */
  419. int
  420. bnSubQ_64(struct BigNum *dest, unsigned src)
  421. {
  422.     BNWORD64 t;
  423.  
  424.     if (!dest->size)
  425.         return bnSetQ(dest, src) < 0 ? -1 : (src != 0);
  426.  
  427.     t = lbnSub1_64((BNWORD64 *)dest->ptr, dest->size, src);
  428.     MALLOCDB;
  429.     if (t) {
  430.         /* Underflow. <= 1 word, so do it simply. */
  431.         lbnNeg_64((BNWORD64 *)dest->ptr, 1);
  432.         dest->size = 1;
  433.         return 1;
  434.     }
  435. /* Try to normalize?  Needing this is going to be pretty damn rare. */
  436. /*        dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, dest->size); */
  437.     return 0;
  438. }
  439.  
  440. /*
  441.  * Compare two BigNums.  Returns -1. 0 or 1 if a<b, a == b or a>b.
  442.  * a <=> b --> bnCmp(a,b) <=> 0
  443.  */
  444. int
  445. bnCmp_64(struct BigNum const *a, struct BigNum const *b)
  446. {
  447.     unsigned s, t;
  448.  
  449.     s = lbnNorm_64((BNWORD64 *)a->ptr, a->size);
  450.     t = lbnNorm_64((BNWORD64 *)b->ptr, b->size);
  451.     
  452.     if (s != t)
  453.         return s > t ? 1 : -1;
  454.     return lbnCmp_64((BNWORD64 *)a->ptr, (BNWORD64 *)b->ptr, s);
  455. }
  456.  
  457. int
  458. bnSquare_64(struct BigNum *dest, struct BigNum const *src)
  459. {
  460.     unsigned s;
  461.     BNWORD64 *srcbuf;
  462.  
  463.     s = lbnNorm_64((BNWORD64 *)src->ptr, src->size);
  464.     if (!s) {
  465.         dest->size = 0;
  466.         return 0;
  467.     }
  468.     bnSizeCheck(dest, 2*s);
  469.  
  470.     if (src == dest) {
  471.         LBNALLOC(srcbuf, s);
  472.         if (!srcbuf)
  473.             return -1;
  474.         lbnCopy_64(srcbuf, (BNWORD64 *)src->ptr, s);
  475.         lbnSquare_64((BNWORD64 *)dest->ptr, (BNWORD64 *)srcbuf, s);
  476.         LBNFREE(srcbuf, s);
  477.     } else {
  478.         lbnSquare_64((BNWORD64 *)dest->ptr, (BNWORD64 *)src->ptr, s);
  479.     }
  480.  
  481.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, 2*s);
  482.     MALLOCDB;
  483.     return 0;
  484. }
  485.  
  486. int
  487. bnMul_64(struct BigNum *dest, struct BigNum const *a, struct BigNum const *b)
  488. {
  489.     unsigned s, t;
  490.     BNWORD64 *srcbuf;
  491.  
  492.     s = lbnNorm_64((BNWORD64 *)a->ptr, a->size);
  493.     t = lbnNorm_64((BNWORD64 *)b->ptr, b->size);
  494.  
  495.     if (!s || !t) {
  496.         dest->size = 0;
  497.         return 0;
  498.     }
  499.  
  500.     if (a == b)
  501.         return bnSquare_64(dest, a);
  502.  
  503.     bnSizeCheck(dest, s+t);
  504.  
  505.     if (dest == a) {
  506.         LBNALLOC(srcbuf, s);
  507.         if (!srcbuf)
  508.             return -1;
  509.         lbnCopy_64(srcbuf, (BNWORD64 *)a->ptr, s);
  510.         lbnMul_64((BNWORD64 *)dest->ptr, srcbuf, s,
  511.                                          (BNWORD64 *)b->ptr, t);
  512.         LBNFREE(srcbuf, s);
  513.     } else if (dest == b) {
  514.         LBNALLOC(srcbuf, t);
  515.         if (!srcbuf)
  516.             return -1;
  517.         lbnCopy_64(srcbuf, (BNWORD64 *)b->ptr, t);
  518.         lbnMul_64((BNWORD64 *)dest->ptr, (BNWORD64 *)a->ptr, s,
  519.                                          srcbuf, t);
  520.         LBNFREE(srcbuf, t);
  521.     } else {
  522.         lbnMul_64((BNWORD64 *)dest->ptr, (BNWORD64 *)a->ptr, s,
  523.                                          (BNWORD64 *)b->ptr, t);
  524.     }
  525.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, s+t);
  526.     MALLOCDB;
  527.     return 0;
  528. }
  529.  
  530. int
  531. bnMulQ_64(struct BigNum *dest, struct BigNum const *a, unsigned b)
  532. {
  533.     unsigned s;
  534.  
  535.     s = lbnNorm_64((BNWORD64 *)a->ptr, a->size);
  536.     if (!s || !b) {
  537.         dest->size = 0;
  538.         return 0;
  539.     }
  540.     if (b == 1)
  541.         return bnCopy_64(dest, a);
  542.     bnSizeCheck(dest, s+1);
  543.     lbnMulN1_64((BNWORD64 *)dest->ptr, (BNWORD64 *)a->ptr, s, b);
  544.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, s+1);
  545.     MALLOCDB;
  546.     return 0;
  547. }
  548.  
  549. int
  550. bnDivMod_64(struct BigNum *q, struct BigNum *r, struct BigNum const *n,
  551.             struct BigNum const *d)
  552. {
  553.     unsigned dsize, nsize;
  554.     BNWORD64 qhigh;
  555.  
  556.     dsize = lbnNorm_64((BNWORD64 *)d->ptr, d->size);
  557.     nsize = lbnNorm_64((BNWORD64 *)n->ptr, n->size);
  558.  
  559.     if (nsize < dsize) {
  560.         q->size = 0;    /* No quotient */
  561.         r->size = nsize;
  562.         return 0;    /* Success */
  563.     }
  564.  
  565.     bnSizeCheck(q, nsize-dsize);
  566.  
  567.     if (r != n) {    /* You are allowed to reduce in place */
  568.         bnSizeCheck(r, nsize);
  569.         lbnCopy_64((BNWORD64 *)r->ptr, (BNWORD64 *)n->ptr, nsize);
  570.     }
  571.         
  572.     qhigh = lbnDiv_64((BNWORD64 *)q->ptr, (BNWORD64 *)r->ptr, nsize,
  573.                       (BNWORD64 *)d->ptr, dsize);
  574.     nsize -= dsize;
  575.     if (qhigh) {
  576.         bnSizeCheck(q, nsize+1);
  577.         *((BNWORD64 *)q->ptr BIGLITTLE(-nsize-1,+nsize)) = qhigh;
  578.         q->size = nsize+1;
  579.     } else {
  580.         q->size = lbnNorm_64((BNWORD64 *)q->ptr, nsize);
  581.     }
  582.     r->size = lbnNorm_64((BNWORD64 *)r->ptr, dsize);
  583.     MALLOCDB;
  584.     return 0;
  585. }
  586.  
  587. int
  588. bnMod_64(struct BigNum *dest, struct BigNum const *src, struct BigNum const *d)
  589. {
  590.     unsigned dsize, nsize;
  591.  
  592.     nsize = lbnNorm_64((BNWORD64 *)src->ptr, src->size);
  593.     dsize = lbnNorm_64((BNWORD64 *)d->ptr, d->size);
  594.  
  595.  
  596.     if (dest != src) {
  597.         bnSizeCheck(dest, nsize);
  598.         lbnCopy_64((BNWORD64 *)dest->ptr, (BNWORD64 *)src->ptr, nsize);
  599.     }
  600.  
  601.     if (nsize < dsize) {
  602.         dest->size = nsize;    /* No quotient */
  603.         return 0;
  604.     }
  605.  
  606.     (void)lbnDiv_64((BNWORD64 *)dest->ptr BIGLITTLE(-dsize,+dsize),
  607.                     (BNWORD64 *)dest->ptr, nsize,
  608.                     (BNWORD64 *)d->ptr, dsize);
  609.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, dsize);
  610.     MALLOCDB;
  611.     return 0;
  612. }
  613.  
  614. unsigned
  615. bnModQ_64(struct BigNum const *src, unsigned d)
  616. {
  617.     unsigned s;
  618.  
  619.     s = lbnNorm_64((BNWORD64 *)src->ptr, src->size);
  620.     if (!s)
  621.         return 0;
  622.     
  623.     return lbnModQ_64((BNWORD64 *)src->ptr, s, d);
  624. }
  625.  
  626. int
  627. bnExpMod_64(struct BigNum *dest, struct BigNum const *n,
  628.     struct BigNum const *exp, struct BigNum const *mod)
  629. {
  630.     unsigned nsize, esize, msize;
  631.  
  632.     nsize = lbnNorm_64((BNWORD64 *)n->ptr, n->size);
  633.     esize = lbnNorm_64((BNWORD64 *)exp->ptr, exp->size);
  634.     msize = lbnNorm_64((BNWORD64 *)mod->ptr, mod->size);
  635.  
  636.     if (!msize || (((BNWORD64 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  637.         return -1;    /* Illegal modulus! */
  638.  
  639.     bnSizeCheck(dest, msize);
  640.  
  641.     /* Special-case base of 2 */
  642.     if (nsize == 1 && ((BNWORD64 *)n->ptr)[BIGLITTLE(-1,0)] == 2) {
  643.         if (lbnTwoExpMod_64((BNWORD64 *)dest->ptr,
  644.                     (BNWORD64 *)exp->ptr, esize,
  645.                     (BNWORD64 *)mod->ptr, msize) < 0)
  646.             return -1;
  647.     } else {
  648.         if (lbnExpMod_64((BNWORD64 *)dest->ptr,
  649.                          (BNWORD64 *)n->ptr, nsize,
  650.                  (BNWORD64 *)exp->ptr, esize,
  651.                  (BNWORD64 *)mod->ptr, msize) < 0)
  652.         return -1;
  653.     }
  654.  
  655.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, msize);
  656.     MALLOCDB;
  657.     return 0;
  658. }
  659.  
  660. int
  661. bnDoubleExpMod_64(struct BigNum *dest,
  662.     struct BigNum const *n1, struct BigNum const *e1,
  663.     struct BigNum const *n2, struct BigNum const *e2,
  664.     struct BigNum const *mod)
  665. {
  666.     unsigned n1size, e1size, n2size, e2size, msize;
  667.  
  668.     n1size = lbnNorm_64((BNWORD64 *)n1->ptr, n1->size);
  669.     e1size = lbnNorm_64((BNWORD64 *)e1->ptr, e1->size);
  670.     n2size = lbnNorm_64((BNWORD64 *)n2->ptr, n2->size);
  671.     e2size = lbnNorm_64((BNWORD64 *)e2->ptr, e2->size);
  672.     msize = lbnNorm_64((BNWORD64 *)mod->ptr, mod->size);
  673.  
  674.     if (!msize || (((BNWORD64 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  675.         return -1;    /* Illegal modulus! */
  676.  
  677.     bnSizeCheck(dest, msize);
  678.  
  679.     if (lbnDoubleExpMod_64((BNWORD64 *)dest->ptr,
  680.         (BNWORD64 *)n1->ptr, n1size, (BNWORD64 *)e1->ptr, e1size,
  681.         (BNWORD64 *)n2->ptr, n2size, (BNWORD64 *)e2->ptr, e2size,
  682.         (BNWORD64 *)mod->ptr, msize) < 0)
  683.         return -1;
  684.  
  685.     dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, msize);
  686.     MALLOCDB;
  687.     return 0;
  688. }
  689.  
  690. int
  691. bnTwoExpMod_64(struct BigNum *n, struct BigNum const *exp,
  692.     struct BigNum const *mod)
  693. {
  694.     unsigned esize, msize;
  695.  
  696.     esize = lbnNorm_64((BNWORD64 *)exp->ptr, exp->size);
  697.     msize = lbnNorm_64((BNWORD64 *)mod->ptr, mod->size);
  698.  
  699.     if (!msize || (((BNWORD64 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  700.         return -1;    /* Illegal modulus! */
  701.  
  702.     bnSizeCheck(n, msize);
  703.  
  704.     if (lbnTwoExpMod_64((BNWORD64 *)n->ptr, (BNWORD64 *)exp->ptr, esize,
  705.                         (BNWORD64 *)mod->ptr, msize) < 0)
  706.         return -1;
  707.  
  708.     n->size = lbnNorm_64((BNWORD64 *)n->ptr, msize);
  709.     MALLOCDB;
  710.     return 0;
  711. }
  712.  
  713. int
  714. bnGcd_64(struct BigNum *dest, struct BigNum const *a, struct BigNum const *b)
  715. {
  716.     BNWORD64 *tmp;
  717.     unsigned asize, bsize;
  718.     int i;
  719.  
  720.     /* Kind of silly, but we might as well permit it... */
  721.     if (a == b)
  722.         return dest == a ? 0 : bnCopy(dest, a);
  723.  
  724.     /* Ensure a is not the same as "dest" */
  725.     if (a == dest) {
  726.         a = b;
  727.         b = dest;
  728.     }
  729.  
  730.     asize = lbnNorm_64((BNWORD64 *)a->ptr, a->size);
  731.     bsize = lbnNorm_64((BNWORD64 *)b->ptr, b->size);
  732.  
  733.     bnSizeCheck(dest, bsize+1);
  734.  
  735.     /* Copy a to tmp */
  736.     LBNALLOC(tmp, asize+1);
  737.     if (!tmp)
  738.         return -1;
  739.     lbnCopy_64(tmp, (BNWORD64 *)a->ptr, asize);
  740.  
  741.     /* Copy b to dest,if necessary */
  742.     if (dest != b)
  743.         lbnCopy_64((BNWORD64 *)dest->ptr,
  744.                (BNWORD64 *)b->ptr, bsize);
  745.     if (bsize > asize || (bsize == asize &&
  746.             lbnCmp_64((BNWORD64 *)b->ptr, (BNWORD64 *)a->ptr, asize) > 0))
  747.     {
  748.         i = lbnGcd_64((BNWORD64 *)dest->ptr, bsize, tmp, asize);
  749.         if (i >= 0) {
  750.             dest->size = (unsigned)i;
  751.         } else {
  752.             lbnCopy_64((BNWORD64 *)dest->ptr, tmp,
  753.                    (unsigned)-i);
  754.             dest->size = (unsigned)-i;
  755.         }
  756.     } else {
  757.         i = lbnGcd_64(tmp, asize, (BNWORD64 *)dest->ptr, bsize);
  758.         if (i <= 0) {
  759.             dest->size = (unsigned)-i;
  760.         } else {
  761.             lbnCopy_64((BNWORD64 *)dest->ptr, tmp,
  762.                    (unsigned)i);
  763.             dest->size = (unsigned)i;
  764.         }
  765.     }
  766.     LBNFREE(tmp, asize+1);
  767.     MALLOCDB;
  768.     return 0;
  769. }
  770.  
  771. int
  772. bnInv_64(struct BigNum *dest, struct BigNum const *src,
  773.          struct BigNum const *mod)
  774. {
  775.     unsigned s, m;
  776.     int i;
  777.  
  778.     s = lbnNorm_64((BNWORD64 *)src->ptr, src->size);
  779.     m = lbnNorm_64((BNWORD64 *)mod->ptr, mod->size);
  780.  
  781.     /* lbnInv_64 requires that the input be less than the modulus */
  782.     if (m < s ||
  783.         (m==s && lbnCmp_64((BNWORD64 *)src->ptr, (BNWORD64 *)mod->ptr, s)))
  784.     {
  785.         bnSizeCheck(dest, s + (m==s));
  786.         if (dest != src)
  787.             lbnCopy_64((BNWORD64 *)dest->ptr,
  788.                        (BNWORD64 *)src->ptr, s);
  789.         /* Pre-reduce modulo the modulus */
  790.         (void)lbnDiv_64((BNWORD64 *)dest->ptr BIGLITTLE(-m,+m),
  791.                     (BNWORD64 *)dest->ptr, s,
  792.                         (BNWORD64 *)mod->ptr, m);
  793.         s = lbnNorm_64((BNWORD64 *)dest->ptr, m);
  794.         MALLOCDB;
  795.     } else {
  796.         bnSizeCheck(dest, m+1);
  797.         if (dest != src)
  798.             lbnCopy_64((BNWORD64 *)dest->ptr,
  799.                        (BNWORD64 *)src->ptr, s);
  800.     }
  801.  
  802.     i = lbnInv_64((BNWORD64 *)dest->ptr, s, (BNWORD64 *)mod->ptr, m);
  803.     if (i == 0)
  804.         dest->size = lbnNorm_64((BNWORD64 *)dest->ptr, m);
  805.  
  806.     MALLOCDB;
  807.     return i;
  808. }
  809.  
  810. /*
  811.  * Shift a bignum left the appropriate number of bits,
  812.  * multiplying by 2^amt.
  813.  */
  814. int 
  815. bnLShift_64(struct BigNum *dest, unsigned amt)
  816. {
  817.     unsigned s = dest->size;
  818.     BNWORD64 carry;
  819.  
  820.     if (amt % 64) {
  821.         carry = lbnLshift_64(dest->ptr, s, amt % 64);
  822.         if (carry) {
  823.             s++;
  824.             bnSizeCheck(dest, s);
  825.             ((BNWORD64 *)dest->ptr)[BIGLITTLE(-s,s-1)] = carry;
  826.         }
  827.     }
  828.  
  829.     amt /= 64;
  830.     if (amt) {
  831.         bnSizeCheck(dest, s+amt);
  832.         memmove((BNWORD64 *)dest->ptr BIGLITTLE(-s-amt, +amt),
  833.                 (BNWORD64 *)dest->ptr BIG(-s),
  834.             s * sizeof(BNWORD64));
  835.         lbnZero_64((BNWORD64 *)dest->ptr, amt);
  836.         s += amt;
  837.     }
  838.     dest->size = s;
  839.     MALLOCDB;
  840.     return 0;
  841. }
  842.  
  843. /*
  844.  * Shift a bignum right the appropriate number of bits,
  845.  * dividing by 2^amt.
  846.  */
  847. void bnRShift_64(struct BigNum *dest, unsigned amt)
  848. {
  849.     unsigned s = dest->size;
  850.  
  851.     if (amt >= 64) {
  852.         memmove(
  853.                 (BNWORD64 *)dest->ptr BIG(-s+amt/64),
  854.             (BNWORD64 *)dest->ptr BIGLITTLE(-s, +amt/64),
  855.             s-amt/64 * sizeof(BNWORD64));
  856.         s -= amt/64;
  857.         amt %= 64;
  858.     }
  859.  
  860.     if (amt)
  861.         (void)lbnRshift_64(dest->ptr, s, amt);
  862.  
  863.     dest->size = lbnNorm_64(dest->ptr, s);
  864.     MALLOCDB;
  865. }
  866.  
  867. /*
  868.  * Shift a bignum right until it is odd, and return the number of
  869.  * bits shifted.  n = d * 2^s.  Replaces n with d and returns s.
  870.  * Returns 0 when given 0.  (Another valid answer is infinity.)
  871.  */
  872. unsigned
  873. bnMakeOdd_64(struct BigNum *n)
  874. {
  875.     unsigned size;
  876.     unsigned s;    /* shift amount */
  877.     BNWORD64 *p;
  878.     BNWORD64 t;
  879.  
  880.     p = (BNWORD64 *)n->ptr;
  881.     size = lbnNorm_64(p, n->size);
  882.     if (!size)
  883.         return 0;
  884.  
  885.     t = BIGLITTLE(p[-1],p[0]);
  886.     s = 0;
  887.  
  888.     /* See how many words we have to shift */
  889.     if (!t) {
  890.         /* Shift by words */
  891.         do {
  892.             
  893.             s++;
  894.             BIGLITTLE(--p,p++);
  895.         } while ((t = BIGLITTLE(p[-1],p[0])) == 0);
  896.         size -= s;
  897.         s *= 64;
  898.         memmove((BNWORD64 *)n->ptr BIG(-size), p BIG(-size),
  899.             size * sizeof(BNWORD64));
  900.         p = (BNWORD64 *)n->ptr;
  901.         MALLOCDB;
  902.     }
  903.  
  904.     assert(t);
  905.  
  906.     /* Now count the bits */
  907.     while ((t & 1) == 0) {
  908.         t >>= 1;
  909.         s++;
  910.     }
  911.  
  912.     /* Shift the bits */
  913.     if (s & (64-1)) {
  914.         lbnRshift_64(p, size, s & (64-1));
  915.         /* Renormalize */
  916.         if (BIGLITTLE(*(p-size),*(p+(size-1))) == 0)
  917.             --size;
  918.     }
  919.     n->size = size;
  920.  
  921.     MALLOCDB;
  922.     return s;
  923. }
  924.