bn_add.c 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313
  1. /* crypto/bn/bn_add.c */
  2. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  3. * All rights reserved.
  4. *
  5. * This package is an SSL implementation written
  6. * by Eric Young (eay@cryptsoft.com).
  7. * The implementation was written so as to conform with Netscapes SSL.
  8. *
  9. * This library is free for commercial and non-commercial use as long as
  10. * the following conditions are aheared to. The following conditions
  11. * apply to all code found in this distribution, be it the RC4, RSA,
  12. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  13. * included with this distribution is covered by the same copyright terms
  14. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15. *
  16. * Copyright remains Eric Young's, and as such any Copyright notices in
  17. * the code are not to be removed.
  18. * If this package is used in a product, Eric Young should be given attribution
  19. * as the author of the parts of the library used.
  20. * This can be in the form of a textual message at program startup or
  21. * in documentation (online or textual) provided with the package.
  22. *
  23. * Redistribution and use in source and binary forms, with or without
  24. * modification, are permitted provided that the following conditions
  25. * are met:
  26. * 1. Redistributions of source code must retain the copyright
  27. * notice, this list of conditions and the following disclaimer.
  28. * 2. Redistributions in binary form must reproduce the above copyright
  29. * notice, this list of conditions and the following disclaimer in the
  30. * documentation and/or other materials provided with the distribution.
  31. * 3. All advertising materials mentioning features or use of this software
  32. * must display the following acknowledgement:
  33. * "This product includes cryptographic software written by
  34. * Eric Young (eay@cryptsoft.com)"
  35. * The word 'cryptographic' can be left out if the rouines from the library
  36. * being used are not cryptographic related :-).
  37. * 4. If you include any Windows specific code (or a derivative thereof) from
  38. * the apps directory (application code) you must include an acknowledgement:
  39. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40. *
  41. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51. * SUCH DAMAGE.
  52. *
  53. * The licence and distribution terms for any publically available version or
  54. * derivative of this code cannot be changed. i.e. this code cannot simply be
  55. * copied and put under another distribution licence
  56. * [including the GNU Public Licence.]
  57. */
  58. #include <stdio.h>
  59. #include "cryptlib.h"
  60. #include "bn_lcl.h"
  61. /* r can == a or b */
  62. int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  63. {
  64. const BIGNUM *tmp;
  65. int a_neg = a->neg, ret;
  66. bn_check_top(a);
  67. bn_check_top(b);
  68. /*-
  69. * a + b a+b
  70. * a + -b a-b
  71. * -a + b b-a
  72. * -a + -b -(a+b)
  73. */
  74. if (a_neg ^ b->neg) {
  75. /* only one is negative */
  76. if (a_neg) {
  77. tmp = a;
  78. a = b;
  79. b = tmp;
  80. }
  81. /* we are now a - b */
  82. if (BN_ucmp(a, b) < 0) {
  83. if (!BN_usub(r, b, a))
  84. return (0);
  85. r->neg = 1;
  86. } else {
  87. if (!BN_usub(r, a, b))
  88. return (0);
  89. r->neg = 0;
  90. }
  91. return (1);
  92. }
  93. ret = BN_uadd(r, a, b);
  94. r->neg = a_neg;
  95. bn_check_top(r);
  96. return ret;
  97. }
  98. /* unsigned add of b to a */
  99. int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  100. {
  101. int max, min, dif;
  102. BN_ULONG *ap, *bp, *rp, carry, t1, t2;
  103. const BIGNUM *tmp;
  104. bn_check_top(a);
  105. bn_check_top(b);
  106. if (a->top < b->top) {
  107. tmp = a;
  108. a = b;
  109. b = tmp;
  110. }
  111. max = a->top;
  112. min = b->top;
  113. dif = max - min;
  114. if (bn_wexpand(r, max + 1) == NULL)
  115. return 0;
  116. r->top = max;
  117. ap = a->d;
  118. bp = b->d;
  119. rp = r->d;
  120. carry = bn_add_words(rp, ap, bp, min);
  121. rp += min;
  122. ap += min;
  123. bp += min;
  124. if (carry) {
  125. while (dif) {
  126. dif--;
  127. t1 = *(ap++);
  128. t2 = (t1 + 1) & BN_MASK2;
  129. *(rp++) = t2;
  130. if (t2) {
  131. carry = 0;
  132. break;
  133. }
  134. }
  135. if (carry) {
  136. /* carry != 0 => dif == 0 */
  137. *rp = 1;
  138. r->top++;
  139. }
  140. }
  141. if (dif && rp != ap)
  142. while (dif--)
  143. /* copy remaining words if ap != rp */
  144. *(rp++) = *(ap++);
  145. r->neg = 0;
  146. bn_check_top(r);
  147. return 1;
  148. }
  149. /* unsigned subtraction of b from a, a must be larger than b. */
  150. int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  151. {
  152. int max, min, dif;
  153. register BN_ULONG t1, t2, *ap, *bp, *rp;
  154. int i, carry;
  155. #if defined(IRIX_CC_BUG) && !defined(LINT)
  156. int dummy;
  157. #endif
  158. bn_check_top(a);
  159. bn_check_top(b);
  160. max = a->top;
  161. min = b->top;
  162. dif = max - min;
  163. if (dif < 0) { /* hmm... should not be happening */
  164. BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);
  165. return (0);
  166. }
  167. if (bn_wexpand(r, max) == NULL)
  168. return (0);
  169. ap = a->d;
  170. bp = b->d;
  171. rp = r->d;
  172. #if 1
  173. carry = 0;
  174. for (i = min; i != 0; i--) {
  175. t1 = *(ap++);
  176. t2 = *(bp++);
  177. if (carry) {
  178. carry = (t1 <= t2);
  179. t1 = (t1 - t2 - 1) & BN_MASK2;
  180. } else {
  181. carry = (t1 < t2);
  182. t1 = (t1 - t2) & BN_MASK2;
  183. }
  184. # if defined(IRIX_CC_BUG) && !defined(LINT)
  185. dummy = t1;
  186. # endif
  187. *(rp++) = t1 & BN_MASK2;
  188. }
  189. #else
  190. carry = bn_sub_words(rp, ap, bp, min);
  191. ap += min;
  192. bp += min;
  193. rp += min;
  194. #endif
  195. if (carry) { /* subtracted */
  196. if (!dif)
  197. /* error: a < b */
  198. return 0;
  199. while (dif) {
  200. dif--;
  201. t1 = *(ap++);
  202. t2 = (t1 - 1) & BN_MASK2;
  203. *(rp++) = t2;
  204. if (t1)
  205. break;
  206. }
  207. }
  208. #if 0
  209. memcpy(rp, ap, sizeof(*rp) * (max - i));
  210. #else
  211. if (rp != ap) {
  212. for (;;) {
  213. if (!dif--)
  214. break;
  215. rp[0] = ap[0];
  216. if (!dif--)
  217. break;
  218. rp[1] = ap[1];
  219. if (!dif--)
  220. break;
  221. rp[2] = ap[2];
  222. if (!dif--)
  223. break;
  224. rp[3] = ap[3];
  225. rp += 4;
  226. ap += 4;
  227. }
  228. }
  229. #endif
  230. r->top = max;
  231. r->neg = 0;
  232. bn_correct_top(r);
  233. return (1);
  234. }
  235. int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  236. {
  237. int max;
  238. int add = 0, neg = 0;
  239. const BIGNUM *tmp;
  240. bn_check_top(a);
  241. bn_check_top(b);
  242. /*-
  243. * a - b a-b
  244. * a - -b a+b
  245. * -a - b -(a+b)
  246. * -a - -b b-a
  247. */
  248. if (a->neg) {
  249. if (b->neg) {
  250. tmp = a;
  251. a = b;
  252. b = tmp;
  253. } else {
  254. add = 1;
  255. neg = 1;
  256. }
  257. } else {
  258. if (b->neg) {
  259. add = 1;
  260. neg = 0;
  261. }
  262. }
  263. if (add) {
  264. if (!BN_uadd(r, a, b))
  265. return (0);
  266. r->neg = neg;
  267. return (1);
  268. }
  269. /* We are actually doing a - b :-) */
  270. max = (a->top > b->top) ? a->top : b->top;
  271. if (bn_wexpand(r, max) == NULL)
  272. return (0);
  273. if (BN_ucmp(a, b) < 0) {
  274. if (!BN_usub(r, b, a))
  275. return (0);
  276. r->neg = 1;
  277. } else {
  278. if (!BN_usub(r, a, b))
  279. return (0);
  280. r->neg = 0;
  281. }
  282. bn_check_top(r);
  283. return (1);
  284. }