开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 加密解密 > CA认证 > 查看源码
bn16.c
资源名称：certlib.tar.gz　[点击查看]
上传用户：zbbssh
上传日期：2007-01-08
资源大小：196k
文件大小：19k
源码类别：

CA认证

开发平台：

C/C++

bn16.c：源码内容
  1. /*
  2.  * bn16.c - the high-level bignum interface
  3.  *
  4.  * Like lbn16.c, this reserves the string "16" 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.  */
  12. #if HAVE_CONFIG_H
  13. #include "config.h"
  14. #endif
  16. #if !NO_ASSERT_H
  17. #include <assert.h>
  18. #else
  19. #define assert(x) (void)0
  20. #endif
  22. #if !NO_STRING_H
  23. #include <string.h> /* for memmove() in bnMakeOdd */
  24. #elif HAVE_STRINGS_H
  25. #include <strings.h>
  26. #endif
  28. /*
  29.  * This was useful during debugging, so it's left in here.
  30.  * You can ignore it.  DBMALLOC is generally undefined.
  31.  */
  32. #if DBMALLOC
  33. #include "../dbmalloc/malloc.h"
  34. #define MALLOCDB malloc_chain_check(1)
  35. #else
  36. #define MALLOCDB (void)0
  37. #endif
  39. #include "lbn.h"
  40. #include "lbn16.h"
  41. #include "lbnmem.h"
  42. #include "bn16.h"
  43. #include "bn.h"
  45. #include "kludge.h" /* For memmove() */
  47. /* Functions */
  48. void
  49. bnInit_16(void)
  50. {
  51. bnEnd = bnEnd_16;
  52. bnPrealloc = bnPrealloc_16;
  53. bnCopy = bnCopy_16;
  54. bnNorm = bnNorm_16;
  55. bnExtractBigBytes = bnExtractBigBytes_16;
  56. bnInsertBigBytes = bnInsertBigBytes_16;
  57. bnExtractLittleBytes = bnExtractLittleBytes_16;
  58. bnInsertLittleBytes = bnInsertLittleBytes_16;
  59. bnLSWord = bnLSWord_16;
  60. bnBits = bnBits_16;
  61. bnAdd = bnAdd_16;
  62. bnSub = bnSub_16;
  63. bnSetQ = bnSetQ_16;
  64. bnAddQ = bnAddQ_16;
  65. bnSubQ = bnSubQ_16;
  66. bnCmp = bnCmp_16;
  67. bnSquare = bnSquare_16;
  68. bnMul = bnMul_16;
  69. bnMulQ = bnMulQ_16;
  70. bnDivMod = bnDivMod_16;
  71. bnMod = bnMod_16;
  72. bnModQ = bnModQ_16;
  73. bnExpMod = bnExpMod_16;
  74. bnDoubleExpMod = bnDoubleExpMod_16;
  75. bnTwoExpMod = bnTwoExpMod_16;
  76. bnGcd = bnGcd_16;
  77. bnInv = bnInv_16;
  78. bnLShift = bnLShift_16;
  79. bnRShift = bnRShift_16;
  80. bnMakeOdd = bnMakeOdd_16;
  81. }
  83. void
  84. bnEnd_16(struct BigNum *bn)
  85. {
  86. if (bn->ptr) {
  87. LBNFREE((BNWORD16 *)bn->ptr, bn->allocated);
  88. bn->ptr = 0;
  89. }
  90. bn->size = 0;
  91. bn->allocated = 0;
  93. MALLOCDB;
  94. }
  96. /* Internal function.  It operates in words. */
  97. static int
  98. bnResize_16(struct BigNum *bn, unsigned len)
  99. {
  100. void *p;
  102. /* Round size up: most mallocs impose 8-byte granularity anyway */
  103. len = (len + (8/sizeof(BNWORD16) - 1)) & ~(8/sizeof(BNWORD16) - 1);
  104. p = LBNREALLOC((BNWORD16 *)bn->ptr, bn->allocated, len);
  105. if (!p)
  106. return -1;
  107. bn->ptr = p;
  108. bn->allocated = len;
  110. MALLOCDB;
  112. return 0;
  113. }
  115. #define bnSizeCheck(bn, size) 
  116. if (bn->allocated < size && bnResize_16(bn, size) < 0) 
  117. return -1
  119. int
  120. bnPrealloc_16(struct BigNum *bn, unsigned bits)
  121. {
  122. bits = (bits + 16-1)/16;
  123. bnSizeCheck(bn, bits);
  124. MALLOCDB;
  125. return 0;
  126. }
  128. int
  129. bnCopy_16(struct BigNum *dest, struct BigNum const *src)
  130. {
  131. bnSizeCheck(dest, src->size);
  132. dest->size = src->size;
  133. lbnCopy_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, src->size);
  134. MALLOCDB;
  135. return 0;
  136. }
  138. void
  139. bnNorm_16(struct BigNum *bn)
  140. {
  141. bn->size = lbnNorm_16((BNWORD16 *)bn->ptr, bn->size);
  142. }
  144. /*
  145.  * Convert a bignum to big-endian bytes.  Returns, in big-endian form, a
  146.  * substring of the bignum starting from lsbyte and "len" bytes long.
  147.  * Unused high-order (leading) bytes are filled with 0.
  148.  */
  149. void
  150. bnExtractBigBytes_16(struct BigNum const *bn, unsigned char *dest,
  151.                   unsigned lsbyte, unsigned len)
  152. {
  153. unsigned s = bn->size * (16 / 8);
  155. /* Fill unused leading bytes with 0 */
  156. while (s < lsbyte+len) {
  157. *dest++ = 0;
  158. len--;
  159. }
  161. if (len)
  162. lbnExtractBigBytes_16((BNWORD16 *)bn->ptr, dest, lsbyte, len);
  163. MALLOCDB;
  164. }
  166. int
  167. bnInsertBigBytes_16(struct BigNum *bn, unsigned char const *src,
  168.                  unsigned lsbyte, unsigned len)
  169. {
  170. unsigned s = bn->size;
  171. unsigned words = (len+lsbyte+sizeof(BNWORD16)-1) / sizeof(BNWORD16);
  173. /* Pad with zeros as required */
  174. bnSizeCheck(bn, words);
  176. if (s < words) {
  177. lbnZero_16((BNWORD16 *)bn->ptr BIGLITTLE(-s,+s), words-s);
  178. s = words;
  179. }
  181. lbnInsertBigBytes_16((BNWORD16 *)bn->ptr, src, lsbyte, len);
  183. bn->size = lbnNorm_16((BNWORD16 *)bn->ptr, s);
  185. MALLOCDB;
  186. return 0;
  187. }
  190. /*
  191.  * Convert a bignum to little-endian bytes.  Returns, in little-endian form, a
  192.  * substring of the bignum starting from lsbyte and "len" bytes long.
  193.  * Unused high-order (trailing) bytes are filled with 0.
  194.  */
  195. void
  196. bnExtractLittleBytes_16(struct BigNum const *bn, unsigned char *dest,
  197.                   unsigned lsbyte, unsigned len)
  198. {
  199. unsigned s = bn->size * (16 / 8);
  201. /* Fill unused leading bytes with 0 */
  202. while (s < lsbyte+len)
  203. dest[--len] = 0;
  205. if (len)
  206. lbnExtractLittleBytes_16((BNWORD16 *)bn->ptr, dest,
  207.                          lsbyte, len);
  208. MALLOCDB;
  209. }
  211. int
  212. bnInsertLittleBytes_16(struct BigNum *bn, unsigned char const *src,
  213.                        unsigned lsbyte, unsigned len)
  214. {
  215. unsigned s = bn->size;
  216. unsigned words = (len+lsbyte+sizeof(BNWORD16)-1) / sizeof(BNWORD16);
  218. /* Pad with zeros as required */
  219. bnSizeCheck(bn, words);
  221. if (s < words) {
  222. lbnZero_16((BNWORD16 *)bn->ptr BIGLITTLE(-s,+s), words-s);
  223. s = words;
  224. }
  226. lbnInsertLittleBytes_16((BNWORD16 *)bn->ptr, src, lsbyte, len);
  228. bn->size = lbnNorm_16((BNWORD16 *)bn->ptr, s);
  230. MALLOCDB;
  231. return 0;
  232. }
  234. /* Return the least-significant word of the input. */
  235. unsigned
  236. bnLSWord_16(struct BigNum const *src)
  237. {
  238. return src->size ? (unsigned)((BNWORD16 *)src->ptr)[BIGLITTLE(-1,0)]: 0;
  239. }
  241. unsigned
  242. bnBits_16(struct BigNum const *src)
  243. {
  244. return lbnBits_16((BNWORD16 *)src->ptr, src->size);
  245. }
  247. int
  248. bnAdd_16(struct BigNum *dest, struct BigNum const *src)
  249. {
  250. unsigned s = src->size, d = dest->size;
  251. BNWORD16 t;
  253. if (!s)
  254. return 0;
  256. bnSizeCheck(dest, s);
  258. if (d < s) {
  259. lbnZero_16((BNWORD16 *)dest->ptr BIGLITTLE(-d,+d), s-d);
  260. dest->size = d = s;
  261. MALLOCDB;
  262. }
  263. t = lbnAddN_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, s);
  264. MALLOCDB;
  265. if (t) {
  266. if (d > s) {
  267. t = lbnAdd1_16((BNWORD16 *)dest->ptr BIGLITTLE(-s,+s),
  268.                d-s, t);
  269. MALLOCDB;
  270. }
  271. if (t) {
  272. bnSizeCheck(dest, d+1);
  273. ((BNWORD16 *)dest->ptr)[BIGLITTLE(-1-d,d)] = t;
  274. dest->size = d+1;
  275. }
  276. }
  277. return 0;
  278. }
  280. /*
  281.  * dest -= src.
  282.  * If dest goes negative, this produces the absolute value of
  283.  * the difference (the negative of the true value) and returns 1.
  284.  * Otherwise, it returls 0.
  285.  */
  286. int
  287. bnSub_16(struct BigNum *dest, struct BigNum const *src)
  288. {
  289. unsigned s = src->size, d = dest->size;
  290. BNWORD16 t;
  292. if (d < s  &&  d < (s = lbnNorm_16((BNWORD16 *)src->ptr, s))) {
  293. bnSizeCheck(dest, s);
  294. lbnZero_16((BNWORD16 *)dest->ptr BIGLITTLE(-d,+d), s-d);
  295. dest->size = d = s;
  296. MALLOCDB;
  297. }
  298. if (!s)
  299. return 0;
  300. t = lbnSubN_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, s);
  301. MALLOCDB;
  302. if (t) {
  303. if (d > s) {
  304. t = lbnSub1_16((BNWORD16 *)dest->ptr BIGLITTLE(-s,+s),
  305.                d-s, t);
  306. MALLOCDB;
  307. }
  308. if (t) {
  309. lbnNeg_16((BNWORD16 *)dest->ptr, d);
  310. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr,
  311.                         dest->size);
  312. MALLOCDB;
  313. return 1;
  314. }
  315. }
  316. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, dest->size);
  317. return 0;
  318. }
  320. int
  321. bnSetQ_16(struct BigNum *dest, unsigned src)
  322. {
  323. if (src) {
  324. bnSizeCheck(dest, 1);
  326. ((BNWORD16 *)dest->ptr)[BIGLITTLE(-1,0)] = (BNWORD16)src;
  327. dest->size = 1;
  328. } else {
  329. dest->size = 0;
  330. }
  331. return 0;
  332. }
  334. int
  335. bnAddQ_16(struct BigNum *dest, unsigned src)
  336. {
  337. BNWORD16 t;
  339. if (!dest->size)
  340. return bnSetQ(dest, src);
  342. t = lbnAdd1_16((BNWORD16 *)dest->ptr, dest->size, (BNWORD16)src);
  343. MALLOCDB;
  344. if (t) {
  345. src = dest->size;
  346. bnSizeCheck(dest, src+1);
  347. ((BNWORD16 *)dest->ptr)[BIGLITTLE(-1-src,src)] = t;
  348. dest->size = src+1;
  349. }
  350. return 0;
  351. }
  353. /*
  354.  * Return value as for bnSub: 1 if subtract underflowed, in which
  355.  * case the return is the negative of the computed value.
  356.  */
  357. int
  358. bnSubQ_16(struct BigNum *dest, unsigned src)
  359. {
  360. BNWORD16 t;
  362. if (!dest->size)
  363. return bnSetQ(dest, src) < 0 ? -1 : (src != 0);
  365. t = lbnSub1_16((BNWORD16 *)dest->ptr, dest->size, src);
  366. MALLOCDB;
  367. if (t) {
  368. /* Underflow. <= 1 word, so do it simply. */
  369. lbnNeg_16((BNWORD16 *)dest->ptr, 1);
  370. dest->size = 1;
  371. return 1;
  372. }
  373. /* Try to normalize?  Needing this is going to be pretty damn rare. */
  374. /* dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, dest->size); */
  375. return 0;
  376. }
  378. /*
  379.  * Compare two BigNums.  Returns -1. 0 or 1 if a<b, a == b or a>b.
  380.  * a <=> b --> bnCmp(a,b) <=> 0
  381.  */
  382. int
  383. bnCmp_16(struct BigNum const *a, struct BigNum const *b)
  384. {
  385. unsigned s, t;
  387. s = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
  388. t = lbnNorm_16((BNWORD16 *)b->ptr, b->size);
  390. if (s != t)
  391. return s > t ? 1 : -1;
  392. return lbnCmp_16((BNWORD16 *)a->ptr, (BNWORD16 *)b->ptr, s);
  393. }
  395. int
  396. bnSquare_16(struct BigNum *dest, struct BigNum const *src)
  397. {
  398. unsigned s;
  399. BNWORD16 *srcbuf;
  401. s = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
  402. if (!s) {
  403. dest->size = 0;
  404. return 0;
  405. }
  406. bnSizeCheck(dest, 2*s);
  408. if (src == dest) {
  409. LBNALLOC(srcbuf, s);
  410. if (!srcbuf)
  411. return -1;
  412. lbnCopy_16(srcbuf, (BNWORD16 *)src->ptr, s);
  413. lbnSquare_16((BNWORD16 *)dest->ptr, (BNWORD16 *)srcbuf, s);
  414. LBNFREE(srcbuf, s);
  415. } else {
  416. lbnSquare_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, s);
  417. }
  419. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, 2*s);
  420. MALLOCDB;
  421. return 0;
  422. }
  424. int
  425. bnMul_16(struct BigNum *dest, struct BigNum const *a, struct BigNum const *b)
  426. {
  427. unsigned s, t;
  428. BNWORD16 *srcbuf;
  430. s = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
  431. t = lbnNorm_16((BNWORD16 *)b->ptr, b->size);
  433. if (!s || !t) {
  434. dest->size = 0;
  435. return 0;
  436. }
  438. if (a == b)
  439. return bnSquare_16(dest, a);
  441. bnSizeCheck(dest, s+t);
  443. if (dest == a) {
  444. LBNALLOC(srcbuf, s);
  445. if (!srcbuf)
  446. return -1;
  447. lbnCopy_16(srcbuf, (BNWORD16 *)a->ptr, s);
  448. lbnMul_16((BNWORD16 *)dest->ptr, srcbuf, s,
  449.                                  (BNWORD16 *)b->ptr, t);
  450. LBNFREE(srcbuf, s);
  451. } else if (dest == b) {
  452. LBNALLOC(srcbuf, t);
  453. if (!srcbuf)
  454. return -1;
  455. lbnCopy_16(srcbuf, (BNWORD16 *)b->ptr, t);
  456. lbnMul_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s,
  457.                                  srcbuf, t);
  458. LBNFREE(srcbuf, t);
  459. } else {
  460. lbnMul_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s,
  461.                                  (BNWORD16 *)b->ptr, t);
  462. }
  463. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, s+t);
  464. MALLOCDB;
  465. return 0;
  466. }
  468. int
  469. bnMulQ_16(struct BigNum *dest, struct BigNum const *a, unsigned b)
  470. {
  471. unsigned s;
  473. s = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
  474. if (!s || !b) {
  475. dest->size = 0;
  476. return 0;
  477. }
  478. if (b == 1)
  479. return bnCopy_16(dest, a);
  480. bnSizeCheck(dest, s+1);
  481. lbnMulN1_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s, b);
  482. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, s+1);
  483. MALLOCDB;
  484. return 0;
  485. }
  487. int
  488. bnDivMod_16(struct BigNum *q, struct BigNum *r, struct BigNum const *n,
  489.             struct BigNum const *d)
  490. {
  491. unsigned dsize, nsize;
  492. BNWORD16 qhigh;
  494. dsize = lbnNorm_16((BNWORD16 *)d->ptr, d->size);
  495. nsize = lbnNorm_16((BNWORD16 *)n->ptr, n->size);
  497. if (nsize < dsize) {
  498. q->size = 0; /* No quotient */
  499. r->size = nsize;
  500. return 0; /* Success */
  501. }
  503. bnSizeCheck(q, nsize-dsize);
  505. if (r != n) { /* You are allowed to reduce in place */
  506. bnSizeCheck(r, nsize);
  507. lbnCopy_16((BNWORD16 *)r->ptr, (BNWORD16 *)n->ptr, nsize);
  508. }
  510. qhigh = lbnDiv_16((BNWORD16 *)q->ptr, (BNWORD16 *)r->ptr, nsize,
  511.                   (BNWORD16 *)d->ptr, dsize);
  512. nsize -= dsize;
  513. if (qhigh) {
  514. bnSizeCheck(q, nsize+1);
  515. *((BNWORD16 *)q->ptr BIGLITTLE(-nsize-1,+nsize)) = qhigh;
  516. q->size = nsize+1;
  517. } else {
  518. q->size = lbnNorm_16((BNWORD16 *)q->ptr, nsize);
  519. }
  520. r->size = lbnNorm_16((BNWORD16 *)r->ptr, dsize);
  521. MALLOCDB;
  522. return 0;
  523. }
  525. int
  526. bnMod_16(struct BigNum *dest, struct BigNum const *src, struct BigNum const *d)
  527. {
  528. unsigned dsize, nsize;
  530. nsize = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
  531. dsize = lbnNorm_16((BNWORD16 *)d->ptr, d->size);
  534. if (dest != src) {
  535. bnSizeCheck(dest, nsize);
  536. lbnCopy_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, nsize);
  537. }
  539. if (nsize < dsize) {
  540. dest->size = nsize; /* No quotient */
  541. return 0;
  542. }
  544. (void)lbnDiv_16((BNWORD16 *)dest->ptr BIGLITTLE(-dsize,+dsize),
  545.                 (BNWORD16 *)dest->ptr, nsize,
  546.                 (BNWORD16 *)d->ptr, dsize);
  547. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, dsize);
  548. MALLOCDB;
  549. return 0;
  550. }
  552. unsigned
  553. bnModQ_16(struct BigNum const *src, unsigned d)
  554. {
  555. unsigned s;
  557. s = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
  558. if (!s)
  559. return 0;
  561. return lbnModQ_16((BNWORD16 *)src->ptr, s, d);
  562. }
  564. int
  565. bnExpMod_16(struct BigNum *dest, struct BigNum const *n,
  566. struct BigNum const *exp, struct BigNum const *mod)
  567. {
  568. unsigned nsize, esize, msize;
  570. nsize = lbnNorm_16((BNWORD16 *)n->ptr, n->size);
  571. esize = lbnNorm_16((BNWORD16 *)exp->ptr, exp->size);
  572. msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);
  574. if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  575. return -1; /* Illegal modulus! */
  577. bnSizeCheck(dest, msize);
  579. /* Special-case base of 2 */
  580. if (nsize == 1 && ((BNWORD16 *)n->ptr)[BIGLITTLE(-1,0)] == 2) {
  581. if (lbnTwoExpMod_16((BNWORD16 *)dest->ptr,
  582.     (BNWORD16 *)exp->ptr, esize,
  583.     (BNWORD16 *)mod->ptr, msize) < 0)
  584. return -1;
  585. } else {
  586. if (lbnExpMod_16((BNWORD16 *)dest->ptr,
  587.                  (BNWORD16 *)n->ptr, nsize,
  588.  (BNWORD16 *)exp->ptr, esize,
  589.  (BNWORD16 *)mod->ptr, msize) < 0)
  590. return -1;
  591. }
  593. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, msize);
  594. MALLOCDB;
  595. return 0;
  596. }
  598. int
  599. bnDoubleExpMod_16(struct BigNum *dest,
  600. struct BigNum const *n1, struct BigNum const *e1,
  601. struct BigNum const *n2, struct BigNum const *e2,
  602. struct BigNum const *mod)
  603. {
  604. unsigned n1size, e1size, n2size, e2size, msize;
  606. n1size = lbnNorm_16((BNWORD16 *)n1->ptr, n1->size);
  607. e1size = lbnNorm_16((BNWORD16 *)e1->ptr, e1->size);
  608. n2size = lbnNorm_16((BNWORD16 *)n2->ptr, n2->size);
  609. e2size = lbnNorm_16((BNWORD16 *)e2->ptr, e2->size);
  610. msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);
  612. if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  613. return -1; /* Illegal modulus! */
  615. bnSizeCheck(dest, msize);
  617. if (lbnDoubleExpMod_16((BNWORD16 *)dest->ptr,
  618. (BNWORD16 *)n1->ptr, n1size, (BNWORD16 *)e1->ptr, e1size,
  619. (BNWORD16 *)n2->ptr, n1size, (BNWORD16 *)e2->ptr, e2size,
  620. (BNWORD16 *)mod->ptr, msize) < 0)
  621. return -1;
  623. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, msize);
  624. MALLOCDB;
  625. return 0;
  626. }
  628. int
  629. bnTwoExpMod_16(struct BigNum *n, struct BigNum const *exp,
  630. struct BigNum const *mod)
  631. {
  632. unsigned esize, msize;
  634. esize = lbnNorm_16((BNWORD16 *)exp->ptr, exp->size);
  635. msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);
  637. if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
  638. return -1; /* Illegal modulus! */
  640. bnSizeCheck(n, msize);
  642. if (lbnTwoExpMod_16((BNWORD16 *)n->ptr, (BNWORD16 *)exp->ptr, esize,
  643.                     (BNWORD16 *)mod->ptr, msize) < 0)
  644. return -1;
  646. n->size = lbnNorm_16((BNWORD16 *)n->ptr, msize);
  647. MALLOCDB;
  648. return 0;
  649. }
  651. int
  652. bnGcd_16(struct BigNum *dest, struct BigNum const *a, struct BigNum const *b)
  653. {
  654. BNWORD16 *tmp;
  655. unsigned asize, bsize;
  656. int i;
  658. /* Kind of silly, but we might as well permit it... */
  659. if (a == b)
  660. return dest == a ? 0 : bnCopy(dest, a);
  662. /* Ensure a is not the same as "dest" */
  663. if (a == dest) {
  664. a = b;
  665. b = dest;
  666. }
  668. asize = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
  669. bsize = lbnNorm_16((BNWORD16 *)b->ptr, b->size);
  671. bnSizeCheck(dest, bsize+1);
  673. /* Copy a to tmp */
  674. LBNALLOC(tmp, asize+1);
  675. if (!tmp)
  676. return -1;
  677. lbnCopy_16(tmp, (BNWORD16 *)a->ptr, asize);
  679. /* Copy b to dest,if necessary */
  680. if (dest != b)
  681. lbnCopy_16((BNWORD16 *)dest->ptr,
  682.    (BNWORD16 *)b->ptr, bsize);
  683. if (bsize > asize || (bsize == asize &&
  684.         lbnCmp_16((BNWORD16 *)b->ptr, (BNWORD16 *)a->ptr, asize) > 0))
  685. {
  686. i = lbnGcd_16((BNWORD16 *)dest->ptr, bsize, tmp, asize);
  687. if (i >= 0) {
  688. dest->size = (unsigned)i;
  689. } else {
  690. lbnCopy_16((BNWORD16 *)dest->ptr, tmp,
  691.    (unsigned)-i);
  692. dest->size = (unsigned)-i;
  693. }
  694. } else {
  695. i = lbnGcd_16(tmp, asize, (BNWORD16 *)dest->ptr, bsize);
  696. if (i <= 0) {
  697. dest->size = (unsigned)-i;
  698. } else {
  699. lbnCopy_16((BNWORD16 *)dest->ptr, tmp,
  700.    (unsigned)i);
  701. dest->size = (unsigned)i;
  702. }
  703. }
  704. LBNFREE(tmp, asize+1);
  705. MALLOCDB;
  706. return 0;
  707. }
  709. int
  710. bnInv_16(struct BigNum *dest, struct BigNum const *src,
  711.          struct BigNum const *mod)
  712. {
  713. unsigned s, m;
  714. int i;
  716. s = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
  717. m = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);
  719. /* lbnInv_16 requires that the input be less than the modulus */
  720. if (m < s ||
  721.     (m==s && lbnCmp_16((BNWORD16 *)src->ptr, (BNWORD16 *)mod->ptr, s)))
  722. {
  723. bnSizeCheck(dest, s + (m==s));
  724. if (dest != src)
  725. lbnCopy_16((BNWORD16 *)dest->ptr,
  726.            (BNWORD16 *)src->ptr, s);
  727. /* Pre-reduce modulo the modulus */
  728. (void)lbnDiv_16((BNWORD16 *)dest->ptr BIGLITTLE(-m,+m),
  729.         (BNWORD16 *)dest->ptr, s,
  730.                 (BNWORD16 *)mod->ptr, m);
  731. s = lbnNorm_16((BNWORD16 *)dest->ptr, m);
  732. MALLOCDB;
  733. } else {
  734. bnSizeCheck(dest, m+1);
  735. if (dest != src)
  736. lbnCopy_16((BNWORD16 *)dest->ptr,
  737.            (BNWORD16 *)src->ptr, s);
  738. }
  740. i = lbnInv_16((BNWORD16 *)dest->ptr, s, (BNWORD16 *)mod->ptr, m);
  741. if (i == 0)
  742. dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, m);
  744. MALLOCDB;
  745. return i;
  746. }
  748. /*
  749.  * Shift a bignum left the appropriate number of bits,
  750.  * multiplying by 2^amt.
  751.  */
  752. int 
  753. bnLShift_16(struct BigNum *dest, unsigned amt)
  754. {
  755. unsigned s = dest->size;
  756. BNWORD16 carry;
  758. if (amt % 16) {
  759. carry = lbnLshift_16(dest->ptr, s, amt % 16);
  760. if (carry) {
  761. s++;
  762. bnSizeCheck(dest, s);
  763. ((BNWORD16 *)dest->ptr)[BIGLITTLE(-s,s-1)] = carry;
  764. }
  765. }
  767. amt /= 16;
  768. if (amt) {
  769. bnSizeCheck(dest, s+amt);
  770. memmove((BNWORD16 *)dest->ptr BIGLITTLE(-s-amt, +amt),
  771.         (BNWORD16 *)dest->ptr BIG(-s),
  772. s * sizeof(BNWORD16));
  773. lbnZero_16((BNWORD16 *)dest->ptr, amt);
  774. s += amt;
  775. }
  776. dest->size = s;
  777. MALLOCDB;
  778. return 0;
  779. }
  781. /*
  782.  * Shift a bignum right the appropriate number of bits,
  783.  * dividing by 2^amt.
  784.  */
  785. void bnRShift_16(struct BigNum *dest, unsigned amt)
  786. {
  787. unsigned s = dest->size;
  789. if (amt >= 16) {
  790. memmove(
  791.         (BNWORD16 *)dest->ptr BIG(-s+amt/16),
  792. (BNWORD16 *)dest->ptr BIGLITTLE(-s, +amt/16),
  793. s-amt/16 * sizeof(BNWORD16));
  794. s -= amt/16;
  795. amt %= 16;
  796. }
  798. if (amt)
  799. (void)lbnRshift_16(dest->ptr, s, amt);
  801. dest->size = lbnNorm_16(dest->ptr, s);
  802. MALLOCDB;
  803. }
  805. /*
  806.  * Shift a bignum right until it is odd, and return the number of
  807.  * bits shifted.  n = d * 2^s.  Replaces n with d and returns s.
  808.  * Returns 0 when given 0.  (Another valid answer is infinity.)
  809.  */
  810. unsigned
  811. bnMakeOdd_16(struct BigNum *n)
  812. {
  813. unsigned size;
  814. unsigned s; /* shift amount */
  815. BNWORD16 *p;
  816. BNWORD16 t;
  818. p = (BNWORD16 *)n->ptr;
  819. size = lbnNorm_16(p, n->size);
  820. if (!size)
  821. return 0;
  823. t = BIGLITTLE(p[-1],p[0]);
  824. s = 0;
  826. /* See how many words we have to shift */
  827. if (!t) {
  828. /* Shift by words */
  829. do {
  831. s++;
  832. BIGLITTLE(--p,p++);
  833. } while ((t = BIGLITTLE(p[-1],p[0])) == 0);
  834. size -= s;
  835. s *= 16;
  836. memmove((BNWORD16 *)n->ptr BIG(-size), p BIG(-size),
  837. size * sizeof(BNWORD16));
  838. p = (BNWORD16 *)n->ptr;
  839. MALLOCDB;
  840. }
  842. assert(t);
  844. /* Now count the bits */
  845. while ((t & 1) == 0) {
  846. t >>= 1;
  847. s++;
  848. }
  850. /* Shift the bits */
  851. if (s & (16-1)) {
  852. lbnRshift_16(p, size, s & (16-1));
  853. /* Renormalize */
  854. if (BIGLITTLE(*(p-size),*(p+(size-1))) == 0)
  855. --size;
  856. }
  857. n->size = size;
  859. MALLOCDB;
  860. return s;
  861. }