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