bn_add.c 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309
  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;
  66. bn_check_top(a);
  67. bn_check_top(b);
  68. /* a + b a+b
  69. * a + -b a-b
  70. * -a + b b-a
  71. * -a + -b -(a+b)
  72. */
  73. if (a_neg ^ b->neg)
  74. {
  75. /* only one is negative */
  76. if (a_neg)
  77. { tmp=a; a=b; b=tmp; }
  78. /* we are now a - b */
  79. if (BN_ucmp(a,b) < 0)
  80. {
  81. if (!BN_usub(r,b,a)) return(0);
  82. r->neg=1;
  83. }
  84. else
  85. {
  86. if (!BN_usub(r,a,b)) return(0);
  87. r->neg=0;
  88. }
  89. return(1);
  90. }
  91. if (!BN_uadd(r,a,b)) return(0);
  92. if (a_neg) /* both are neg */
  93. r->neg=1;
  94. else
  95. r->neg=0;
  96. return(1);
  97. }
  98. /* unsigned add of b to a, r must be large enough */
  99. int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  100. {
  101. register int i;
  102. int max,min;
  103. BN_ULONG *ap,*bp,*rp,carry,t1;
  104. const BIGNUM *tmp;
  105. bn_check_top(a);
  106. bn_check_top(b);
  107. if (a->top < b->top)
  108. { tmp=a; a=b; b=tmp; }
  109. max=a->top;
  110. min=b->top;
  111. if (bn_wexpand(r,max+1) == NULL)
  112. return(0);
  113. r->top=max;
  114. ap=a->d;
  115. bp=b->d;
  116. rp=r->d;
  117. carry=0;
  118. carry=bn_add_words(rp,ap,bp,min);
  119. rp+=min;
  120. ap+=min;
  121. bp+=min;
  122. i=min;
  123. if (carry)
  124. {
  125. while (i < max)
  126. {
  127. i++;
  128. t1= *(ap++);
  129. if ((*(rp++)=(t1+1)&BN_MASK2) >= t1)
  130. {
  131. carry=0;
  132. break;
  133. }
  134. }
  135. if ((i >= max) && carry)
  136. {
  137. *(rp++)=1;
  138. r->top++;
  139. }
  140. }
  141. if (rp != ap)
  142. {
  143. for (; i<max; i++)
  144. *(rp++)= *(ap++);
  145. }
  146. /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/
  147. r->neg = 0;
  148. return(1);
  149. }
  150. /* unsigned subtraction of b from a, a must be larger than b. */
  151. int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  152. {
  153. int max,min;
  154. register BN_ULONG t1,t2,*ap,*bp,*rp;
  155. int i,carry;
  156. #if defined(IRIX_CC_BUG) && !defined(LINT)
  157. int dummy;
  158. #endif
  159. bn_check_top(a);
  160. bn_check_top(b);
  161. if (a->top < b->top) /* hmm... should not be happening */
  162. {
  163. BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3);
  164. return(0);
  165. }
  166. max=a->top;
  167. min=b->top;
  168. if (bn_wexpand(r,max) == NULL) return(0);
  169. ap=a->d;
  170. bp=b->d;
  171. rp=r->d;
  172. #if 1
  173. carry=0;
  174. for (i=0; i<min; i++)
  175. {
  176. t1= *(ap++);
  177. t2= *(bp++);
  178. if (carry)
  179. {
  180. carry=(t1 <= t2);
  181. t1=(t1-t2-1)&BN_MASK2;
  182. }
  183. else
  184. {
  185. carry=(t1 < t2);
  186. t1=(t1-t2)&BN_MASK2;
  187. }
  188. #if defined(IRIX_CC_BUG) && !defined(LINT)
  189. dummy=t1;
  190. #endif
  191. *(rp++)=t1&BN_MASK2;
  192. }
  193. #else
  194. carry=bn_sub_words(rp,ap,bp,min);
  195. ap+=min;
  196. bp+=min;
  197. rp+=min;
  198. i=min;
  199. #endif
  200. if (carry) /* subtracted */
  201. {
  202. while (i < max)
  203. {
  204. i++;
  205. t1= *(ap++);
  206. t2=(t1-1)&BN_MASK2;
  207. *(rp++)=t2;
  208. if (t1 > t2) break;
  209. }
  210. }
  211. #if 0
  212. memcpy(rp,ap,sizeof(*rp)*(max-i));
  213. #else
  214. if (rp != ap)
  215. {
  216. for (;;)
  217. {
  218. if (i++ >= max) break;
  219. rp[0]=ap[0];
  220. if (i++ >= max) break;
  221. rp[1]=ap[1];
  222. if (i++ >= max) break;
  223. rp[2]=ap[2];
  224. if (i++ >= max) break;
  225. rp[3]=ap[3];
  226. rp+=4;
  227. ap+=4;
  228. }
  229. }
  230. #endif
  231. r->top=max;
  232. r->neg=0;
  233. bn_fix_top(r);
  234. return(1);
  235. }
  236. int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  237. {
  238. int max;
  239. int add=0,neg=0;
  240. const BIGNUM *tmp;
  241. bn_check_top(a);
  242. bn_check_top(b);
  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. {
  250. if (b->neg)
  251. { tmp=a; a=b; b=tmp; }
  252. else
  253. { add=1; neg=1; }
  254. }
  255. else
  256. {
  257. if (b->neg) { add=1; neg=0; }
  258. }
  259. if (add)
  260. {
  261. if (!BN_uadd(r,a,b)) return(0);
  262. r->neg=neg;
  263. return(1);
  264. }
  265. /* We are actually doing a - b :-) */
  266. max=(a->top > b->top)?a->top:b->top;
  267. if (bn_wexpand(r,max) == NULL) return(0);
  268. if (BN_ucmp(a,b) < 0)
  269. {
  270. if (!BN_usub(r,b,a)) return(0);
  271. r->neg=1;
  272. }
  273. else
  274. {
  275. if (!BN_usub(r,a,b)) return(0);
  276. r->neg=0;
  277. }
  278. return(1);
  279. }