174664626SKris Kennaway /* crypto/bn/bn_add.c */ 274664626SKris Kennaway /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 374664626SKris Kennaway * All rights reserved. 474664626SKris Kennaway * 574664626SKris Kennaway * This package is an SSL implementation written 674664626SKris Kennaway * by Eric Young (eay@cryptsoft.com). 774664626SKris Kennaway * The implementation was written so as to conform with Netscapes SSL. 874664626SKris Kennaway * 974664626SKris Kennaway * This library is free for commercial and non-commercial use as long as 1074664626SKris Kennaway * the following conditions are aheared to. The following conditions 1174664626SKris Kennaway * apply to all code found in this distribution, be it the RC4, RSA, 1274664626SKris Kennaway * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1374664626SKris Kennaway * included with this distribution is covered by the same copyright terms 1474664626SKris Kennaway * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1574664626SKris Kennaway * 1674664626SKris Kennaway * Copyright remains Eric Young's, and as such any Copyright notices in 1774664626SKris Kennaway * the code are not to be removed. 1874664626SKris Kennaway * If this package is used in a product, Eric Young should be given attribution 1974664626SKris Kennaway * as the author of the parts of the library used. 2074664626SKris Kennaway * This can be in the form of a textual message at program startup or 2174664626SKris Kennaway * in documentation (online or textual) provided with the package. 2274664626SKris Kennaway * 2374664626SKris Kennaway * Redistribution and use in source and binary forms, with or without 2474664626SKris Kennaway * modification, are permitted provided that the following conditions 2574664626SKris Kennaway * are met: 2674664626SKris Kennaway * 1. Redistributions of source code must retain the copyright 2774664626SKris Kennaway * notice, this list of conditions and the following disclaimer. 2874664626SKris Kennaway * 2. Redistributions in binary form must reproduce the above copyright 2974664626SKris Kennaway * notice, this list of conditions and the following disclaimer in the 3074664626SKris Kennaway * documentation and/or other materials provided with the distribution. 3174664626SKris Kennaway * 3. All advertising materials mentioning features or use of this software 3274664626SKris Kennaway * must display the following acknowledgement: 3374664626SKris Kennaway * "This product includes cryptographic software written by 3474664626SKris Kennaway * Eric Young (eay@cryptsoft.com)" 3574664626SKris Kennaway * The word 'cryptographic' can be left out if the rouines from the library 3674664626SKris Kennaway * being used are not cryptographic related :-). 3774664626SKris Kennaway * 4. If you include any Windows specific code (or a derivative thereof) from 3874664626SKris Kennaway * the apps directory (application code) you must include an acknowledgement: 3974664626SKris Kennaway * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4074664626SKris Kennaway * 4174664626SKris Kennaway * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4274664626SKris Kennaway * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4374664626SKris Kennaway * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4474664626SKris Kennaway * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4574664626SKris Kennaway * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4674664626SKris Kennaway * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4774664626SKris Kennaway * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4874664626SKris Kennaway * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4974664626SKris Kennaway * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5074664626SKris Kennaway * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5174664626SKris Kennaway * SUCH DAMAGE. 5274664626SKris Kennaway * 5374664626SKris Kennaway * The licence and distribution terms for any publically available version or 5474664626SKris Kennaway * derivative of this code cannot be changed. i.e. this code cannot simply be 5574664626SKris Kennaway * copied and put under another distribution licence 5674664626SKris Kennaway * [including the GNU Public Licence.] 5774664626SKris Kennaway */ 5874664626SKris Kennaway 5974664626SKris Kennaway #include <stdio.h> 6074664626SKris Kennaway #include "cryptlib.h" 6174664626SKris Kennaway #include "bn_lcl.h" 6274664626SKris Kennaway 6374664626SKris Kennaway /* r can == a or b */ 6474664626SKris Kennaway int BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b) 6574664626SKris Kennaway { 6674664626SKris Kennaway BIGNUM *tmp; 6774664626SKris Kennaway 6874664626SKris Kennaway bn_check_top(a); 6974664626SKris Kennaway bn_check_top(b); 7074664626SKris Kennaway 7174664626SKris Kennaway /* a + b a+b 7274664626SKris Kennaway * a + -b a-b 7374664626SKris Kennaway * -a + b b-a 7474664626SKris Kennaway * -a + -b -(a+b) 7574664626SKris Kennaway */ 7674664626SKris Kennaway if (a->neg ^ b->neg) 7774664626SKris Kennaway { 7874664626SKris Kennaway /* only one is negative */ 7974664626SKris Kennaway if (a->neg) 8074664626SKris Kennaway { tmp=a; a=b; b=tmp; } 8174664626SKris Kennaway 8274664626SKris Kennaway /* we are now a - b */ 8374664626SKris Kennaway 8474664626SKris Kennaway if (BN_ucmp(a,b) < 0) 8574664626SKris Kennaway { 8674664626SKris Kennaway if (!BN_usub(r,b,a)) return(0); 8774664626SKris Kennaway r->neg=1; 8874664626SKris Kennaway } 8974664626SKris Kennaway else 9074664626SKris Kennaway { 9174664626SKris Kennaway if (!BN_usub(r,a,b)) return(0); 9274664626SKris Kennaway r->neg=0; 9374664626SKris Kennaway } 9474664626SKris Kennaway return(1); 9574664626SKris Kennaway } 9674664626SKris Kennaway 9774664626SKris Kennaway if (a->neg) /* both are neg */ 9874664626SKris Kennaway r->neg=1; 9974664626SKris Kennaway else 10074664626SKris Kennaway r->neg=0; 10174664626SKris Kennaway 10274664626SKris Kennaway if (!BN_uadd(r,a,b)) return(0); 10374664626SKris Kennaway return(1); 10474664626SKris Kennaway } 10574664626SKris Kennaway 10674664626SKris Kennaway /* unsigned add of b to a, r must be large enough */ 10774664626SKris Kennaway int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 10874664626SKris Kennaway { 10974664626SKris Kennaway register int i; 11074664626SKris Kennaway int max,min; 11174664626SKris Kennaway BN_ULONG *ap,*bp,*rp,carry,t1; 11274664626SKris Kennaway const BIGNUM *tmp; 11374664626SKris Kennaway 11474664626SKris Kennaway bn_check_top(a); 11574664626SKris Kennaway bn_check_top(b); 11674664626SKris Kennaway 11774664626SKris Kennaway if (a->top < b->top) 11874664626SKris Kennaway { tmp=a; a=b; b=tmp; } 11974664626SKris Kennaway max=a->top; 12074664626SKris Kennaway min=b->top; 12174664626SKris Kennaway 12274664626SKris Kennaway if (bn_wexpand(r,max+1) == NULL) 12374664626SKris Kennaway return(0); 12474664626SKris Kennaway 12574664626SKris Kennaway r->top=max; 12674664626SKris Kennaway 12774664626SKris Kennaway 12874664626SKris Kennaway ap=a->d; 12974664626SKris Kennaway bp=b->d; 13074664626SKris Kennaway rp=r->d; 13174664626SKris Kennaway carry=0; 13274664626SKris Kennaway 13374664626SKris Kennaway carry=bn_add_words(rp,ap,bp,min); 13474664626SKris Kennaway rp+=min; 13574664626SKris Kennaway ap+=min; 13674664626SKris Kennaway bp+=min; 13774664626SKris Kennaway i=min; 13874664626SKris Kennaway 13974664626SKris Kennaway if (carry) 14074664626SKris Kennaway { 14174664626SKris Kennaway while (i < max) 14274664626SKris Kennaway { 14374664626SKris Kennaway i++; 14474664626SKris Kennaway t1= *(ap++); 14574664626SKris Kennaway if ((*(rp++)=(t1+1)&BN_MASK2) >= t1) 14674664626SKris Kennaway { 14774664626SKris Kennaway carry=0; 14874664626SKris Kennaway break; 14974664626SKris Kennaway } 15074664626SKris Kennaway } 15174664626SKris Kennaway if ((i >= max) && carry) 15274664626SKris Kennaway { 15374664626SKris Kennaway *(rp++)=1; 15474664626SKris Kennaway r->top++; 15574664626SKris Kennaway } 15674664626SKris Kennaway } 15774664626SKris Kennaway if (rp != ap) 15874664626SKris Kennaway { 15974664626SKris Kennaway for (; i<max; i++) 16074664626SKris Kennaway *(rp++)= *(ap++); 16174664626SKris Kennaway } 16274664626SKris Kennaway /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/ 16374664626SKris Kennaway return(1); 16474664626SKris Kennaway } 16574664626SKris Kennaway 16674664626SKris Kennaway /* unsigned subtraction of b from a, a must be larger than b. */ 16774664626SKris Kennaway int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 16874664626SKris Kennaway { 16974664626SKris Kennaway int max,min; 17074664626SKris Kennaway register BN_ULONG t1,t2,*ap,*bp,*rp; 17174664626SKris Kennaway int i,carry; 17274664626SKris Kennaway #if defined(IRIX_CC_BUG) && !defined(LINT) 17374664626SKris Kennaway int dummy; 17474664626SKris Kennaway #endif 17574664626SKris Kennaway 17674664626SKris Kennaway bn_check_top(a); 17774664626SKris Kennaway bn_check_top(b); 17874664626SKris Kennaway 17974664626SKris Kennaway if (a->top < b->top) /* hmm... should not be happening */ 18074664626SKris Kennaway { 18174664626SKris Kennaway BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3); 18274664626SKris Kennaway return(0); 18374664626SKris Kennaway } 18474664626SKris Kennaway 18574664626SKris Kennaway max=a->top; 18674664626SKris Kennaway min=b->top; 18774664626SKris Kennaway if (bn_wexpand(r,max) == NULL) return(0); 18874664626SKris Kennaway 18974664626SKris Kennaway ap=a->d; 19074664626SKris Kennaway bp=b->d; 19174664626SKris Kennaway rp=r->d; 19274664626SKris Kennaway 19374664626SKris Kennaway #if 1 19474664626SKris Kennaway carry=0; 19574664626SKris Kennaway for (i=0; i<min; i++) 19674664626SKris Kennaway { 19774664626SKris Kennaway t1= *(ap++); 19874664626SKris Kennaway t2= *(bp++); 19974664626SKris Kennaway if (carry) 20074664626SKris Kennaway { 20174664626SKris Kennaway carry=(t1 <= t2); 20274664626SKris Kennaway t1=(t1-t2-1)&BN_MASK2; 20374664626SKris Kennaway } 20474664626SKris Kennaway else 20574664626SKris Kennaway { 20674664626SKris Kennaway carry=(t1 < t2); 20774664626SKris Kennaway t1=(t1-t2)&BN_MASK2; 20874664626SKris Kennaway } 20974664626SKris Kennaway #if defined(IRIX_CC_BUG) && !defined(LINT) 21074664626SKris Kennaway dummy=t1; 21174664626SKris Kennaway #endif 21274664626SKris Kennaway *(rp++)=t1&BN_MASK2; 21374664626SKris Kennaway } 21474664626SKris Kennaway #else 21574664626SKris Kennaway carry=bn_sub_words(rp,ap,bp,min); 21674664626SKris Kennaway ap+=min; 21774664626SKris Kennaway bp+=min; 21874664626SKris Kennaway rp+=min; 21974664626SKris Kennaway i=min; 22074664626SKris Kennaway #endif 22174664626SKris Kennaway if (carry) /* subtracted */ 22274664626SKris Kennaway { 22374664626SKris Kennaway while (i < max) 22474664626SKris Kennaway { 22574664626SKris Kennaway i++; 22674664626SKris Kennaway t1= *(ap++); 22774664626SKris Kennaway t2=(t1-1)&BN_MASK2; 22874664626SKris Kennaway *(rp++)=t2; 22974664626SKris Kennaway if (t1 > t2) break; 23074664626SKris Kennaway } 23174664626SKris Kennaway } 23274664626SKris Kennaway #if 0 23374664626SKris Kennaway memcpy(rp,ap,sizeof(*rp)*(max-i)); 23474664626SKris Kennaway #else 23574664626SKris Kennaway if (rp != ap) 23674664626SKris Kennaway { 23774664626SKris Kennaway for (;;) 23874664626SKris Kennaway { 23974664626SKris Kennaway if (i++ >= max) break; 24074664626SKris Kennaway rp[0]=ap[0]; 24174664626SKris Kennaway if (i++ >= max) break; 24274664626SKris Kennaway rp[1]=ap[1]; 24374664626SKris Kennaway if (i++ >= max) break; 24474664626SKris Kennaway rp[2]=ap[2]; 24574664626SKris Kennaway if (i++ >= max) break; 24674664626SKris Kennaway rp[3]=ap[3]; 24774664626SKris Kennaway rp+=4; 24874664626SKris Kennaway ap+=4; 24974664626SKris Kennaway } 25074664626SKris Kennaway } 25174664626SKris Kennaway #endif 25274664626SKris Kennaway 25374664626SKris Kennaway r->top=max; 25474664626SKris Kennaway bn_fix_top(r); 25574664626SKris Kennaway return(1); 25674664626SKris Kennaway } 25774664626SKris Kennaway 25874664626SKris Kennaway int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 25974664626SKris Kennaway { 26074664626SKris Kennaway int max; 26174664626SKris Kennaway int add=0,neg=0; 26274664626SKris Kennaway const BIGNUM *tmp; 26374664626SKris Kennaway 26474664626SKris Kennaway bn_check_top(a); 26574664626SKris Kennaway bn_check_top(b); 26674664626SKris Kennaway 26774664626SKris Kennaway /* a - b a-b 26874664626SKris Kennaway * a - -b a+b 26974664626SKris Kennaway * -a - b -(a+b) 27074664626SKris Kennaway * -a - -b b-a 27174664626SKris Kennaway */ 27274664626SKris Kennaway if (a->neg) 27374664626SKris Kennaway { 27474664626SKris Kennaway if (b->neg) 27574664626SKris Kennaway { tmp=a; a=b; b=tmp; } 27674664626SKris Kennaway else 27774664626SKris Kennaway { add=1; neg=1; } 27874664626SKris Kennaway } 27974664626SKris Kennaway else 28074664626SKris Kennaway { 28174664626SKris Kennaway if (b->neg) { add=1; neg=0; } 28274664626SKris Kennaway } 28374664626SKris Kennaway 28474664626SKris Kennaway if (add) 28574664626SKris Kennaway { 28674664626SKris Kennaway if (!BN_uadd(r,a,b)) return(0); 28774664626SKris Kennaway r->neg=neg; 28874664626SKris Kennaway return(1); 28974664626SKris Kennaway } 29074664626SKris Kennaway 29174664626SKris Kennaway /* We are actually doing a - b :-) */ 29274664626SKris Kennaway 29374664626SKris Kennaway max=(a->top > b->top)?a->top:b->top; 29474664626SKris Kennaway if (bn_wexpand(r,max) == NULL) return(0); 29574664626SKris Kennaway if (BN_ucmp(a,b) < 0) 29674664626SKris Kennaway { 29774664626SKris Kennaway if (!BN_usub(r,b,a)) return(0); 29874664626SKris Kennaway r->neg=1; 29974664626SKris Kennaway } 30074664626SKris Kennaway else 30174664626SKris Kennaway { 30274664626SKris Kennaway if (!BN_usub(r,a,b)) return(0); 30374664626SKris Kennaway r->neg=0; 30474664626SKris Kennaway } 30574664626SKris Kennaway return(1); 30674664626SKris Kennaway } 30774664626SKris Kennaway 308