bn_add.c revision 1.20
1/* $OpenBSD: bn_add.c,v 1.20 2023/01/31 05:16:52 jsing Exp $ */ 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 59#include <assert.h> 60#include <stdio.h> 61 62#include <openssl/err.h> 63 64#include "bn_arch.h" 65#include "bn_local.h" 66 67#ifndef HAVE_BN_ADD_WORDS 68#ifdef BN_LLONG 69BN_ULONG 70bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 71{ 72 BN_ULLONG ll = 0; 73 74 assert(n >= 0); 75 if (n <= 0) 76 return ((BN_ULONG)0); 77 78#ifndef OPENSSL_SMALL_FOOTPRINT 79 while (n & ~3) { 80 ll += (BN_ULLONG)a[0] + b[0]; 81 r[0] = (BN_ULONG)ll & BN_MASK2; 82 ll >>= BN_BITS2; 83 ll += (BN_ULLONG)a[1] + b[1]; 84 r[1] = (BN_ULONG)ll & BN_MASK2; 85 ll >>= BN_BITS2; 86 ll += (BN_ULLONG)a[2] + b[2]; 87 r[2] = (BN_ULONG)ll & BN_MASK2; 88 ll >>= BN_BITS2; 89 ll += (BN_ULLONG)a[3] + b[3]; 90 r[3] = (BN_ULONG)ll & BN_MASK2; 91 ll >>= BN_BITS2; 92 a += 4; 93 b += 4; 94 r += 4; 95 n -= 4; 96 } 97#endif 98 while (n) { 99 ll += (BN_ULLONG)a[0] + b[0]; 100 r[0] = (BN_ULONG)ll & BN_MASK2; 101 ll >>= BN_BITS2; 102 a++; 103 b++; 104 r++; 105 n--; 106 } 107 return ((BN_ULONG)ll); 108} 109#else /* !BN_LLONG */ 110BN_ULONG 111bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 112{ 113 BN_ULONG c, l, t; 114 115 assert(n >= 0); 116 if (n <= 0) 117 return ((BN_ULONG)0); 118 119 c = 0; 120#ifndef OPENSSL_SMALL_FOOTPRINT 121 while (n & ~3) { 122 t = a[0]; 123 t = (t + c) & BN_MASK2; 124 c = (t < c); 125 l = (t + b[0]) & BN_MASK2; 126 c += (l < t); 127 r[0] = l; 128 t = a[1]; 129 t = (t + c) & BN_MASK2; 130 c = (t < c); 131 l = (t + b[1]) & BN_MASK2; 132 c += (l < t); 133 r[1] = l; 134 t = a[2]; 135 t = (t + c) & BN_MASK2; 136 c = (t < c); 137 l = (t + b[2]) & BN_MASK2; 138 c += (l < t); 139 r[2] = l; 140 t = a[3]; 141 t = (t + c) & BN_MASK2; 142 c = (t < c); 143 l = (t + b[3]) & BN_MASK2; 144 c += (l < t); 145 r[3] = l; 146 a += 4; 147 b += 4; 148 r += 4; 149 n -= 4; 150 } 151#endif 152 while (n) { 153 t = a[0]; 154 t = (t + c) & BN_MASK2; 155 c = (t < c); 156 l = (t + b[0]) & BN_MASK2; 157 c += (l < t); 158 r[0] = l; 159 a++; 160 b++; 161 r++; 162 n--; 163 } 164 return ((BN_ULONG)c); 165} 166#endif /* !BN_LLONG */ 167#endif 168 169#ifndef HAVE_BN_SUB_WORDS 170BN_ULONG 171bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 172{ 173 BN_ULONG t1, t2; 174 int c = 0; 175 176 assert(n >= 0); 177 if (n <= 0) 178 return ((BN_ULONG)0); 179 180#ifndef OPENSSL_SMALL_FOOTPRINT 181 while (n&~3) { 182 t1 = a[0]; 183 t2 = b[0]; 184 r[0] = (t1 - t2 - c) & BN_MASK2; 185 if (t1 != t2) 186 c = (t1 < t2); 187 t1 = a[1]; 188 t2 = b[1]; 189 r[1] = (t1 - t2 - c) & BN_MASK2; 190 if (t1 != t2) 191 c = (t1 < t2); 192 t1 = a[2]; 193 t2 = b[2]; 194 r[2] = (t1 - t2 - c) & BN_MASK2; 195 if (t1 != t2) 196 c = (t1 < t2); 197 t1 = a[3]; 198 t2 = b[3]; 199 r[3] = (t1 - t2 - c) & BN_MASK2; 200 if (t1 != t2) 201 c = (t1 < t2); 202 a += 4; 203 b += 4; 204 r += 4; 205 n -= 4; 206 } 207#endif 208 while (n) { 209 t1 = a[0]; 210 t2 = b[0]; 211 r[0] = (t1 - t2 - c) & BN_MASK2; 212 if (t1 != t2) 213 c = (t1 < t2); 214 a++; 215 b++; 216 r++; 217 n--; 218 } 219 return (c); 220} 221#endif 222 223int 224BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 225{ 226 int max, min, dif; 227 const BN_ULONG *ap, *bp; 228 BN_ULONG *rp, carry, t1, t2; 229 230 231 if (a->top < b->top) { 232 const BIGNUM *tmp; 233 234 tmp = a; 235 a = b; 236 b = tmp; 237 } 238 max = a->top; 239 min = b->top; 240 dif = max - min; 241 242 if (!bn_wexpand(r, max + 1)) 243 return 0; 244 245 r->top = max; 246 247 ap = a->d; 248 bp = b->d; 249 rp = r->d; 250 251 carry = bn_add_words(rp, ap, bp, min); 252 rp += min; 253 ap += min; 254 255 while (dif) { 256 dif--; 257 t1 = *(ap++); 258 t2 = (t1 + carry) & BN_MASK2; 259 *(rp++) = t2; 260 carry &= (t2 == 0); 261 } 262 *rp = carry; 263 r->top += carry; 264 265 r->neg = 0; 266 return 1; 267} 268 269int 270BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 271{ 272 int max, min, dif; 273 const BN_ULONG *ap, *bp; 274 BN_ULONG t1, t2, borrow, *rp; 275 276 277 max = a->top; 278 min = b->top; 279 dif = max - min; 280 281 if (dif < 0) { 282 BNerror(BN_R_ARG2_LT_ARG3); 283 return 0; 284 } 285 286 if (!bn_wexpand(r, max)) 287 return 0; 288 289 ap = a->d; 290 bp = b->d; 291 rp = r->d; 292 293 borrow = bn_sub_words(rp, ap, bp, min); 294 if (dif == 0 && borrow > 0) { 295 BNerror(BN_R_ARG2_LT_ARG3); 296 return 0; 297 } 298 ap += min; 299 rp += min; 300 301 while (dif) { 302 dif--; 303 t1 = *(ap++); 304 t2 = (t1 - borrow) & BN_MASK2; 305 *(rp++) = t2; 306 borrow &= (t1 == 0); 307 } 308 309 while (max > 0 && *--rp == 0) 310 max--; 311 312 r->top = max; 313 r->neg = 0; 314 bn_correct_top(r); 315 return 1; 316} 317 318int 319BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 320{ 321 int ret, r_neg; 322 323 324 if (a->neg == b->neg) { 325 r_neg = a->neg; 326 ret = BN_uadd(r, a, b); 327 } else { 328 int cmp = BN_ucmp(a, b); 329 330 if (cmp > 0) { 331 r_neg = a->neg; 332 ret = BN_usub(r, a, b); 333 } else if (cmp < 0) { 334 r_neg = b->neg; 335 ret = BN_usub(r, b, a); 336 } else { 337 r_neg = 0; 338 BN_zero(r); 339 ret = 1; 340 } 341 } 342 343 r->neg = r_neg; 344 return ret; 345} 346 347int 348BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 349{ 350 int ret, r_neg; 351 352 353 if (a->neg != b->neg) { 354 r_neg = a->neg; 355 ret = BN_uadd(r, a, b); 356 } else { 357 int cmp = BN_ucmp(a, b); 358 359 if (cmp > 0) { 360 r_neg = a->neg; 361 ret = BN_usub(r, a, b); 362 } else if (cmp < 0) { 363 r_neg = !b->neg; 364 ret = BN_usub(r, b, a); 365 } else { 366 r_neg = 0; 367 BN_zero(r); 368 ret = 1; 369 } 370 } 371 372 r->neg = r_neg; 373 return ret; 374} 375