bn_add.c revision 1.19
146686Sbrian/* $OpenBSD: bn_add.c,v 1.19 2023/01/23 10:34:21 jsing Exp $ */ 246686Sbrian/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 346686Sbrian * All rights reserved. 446686Sbrian * 546686Sbrian * This package is an SSL implementation written 646686Sbrian * by Eric Young (eay@cryptsoft.com). 746686Sbrian * The implementation was written so as to conform with Netscapes SSL. 846686Sbrian * 946686Sbrian * This library is free for commercial and non-commercial use as long as 1046686Sbrian * the following conditions are aheared to. The following conditions 1146686Sbrian * apply to all code found in this distribution, be it the RC4, RSA, 1246686Sbrian * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1346686Sbrian * included with this distribution is covered by the same copyright terms 1446686Sbrian * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1546686Sbrian * 1646686Sbrian * Copyright remains Eric Young's, and as such any Copyright notices in 1746686Sbrian * the code are not to be removed. 1846686Sbrian * If this package is used in a product, Eric Young should be given attribution 1946686Sbrian * as the author of the parts of the library used. 2046686Sbrian * This can be in the form of a textual message at program startup or 2146686Sbrian * in documentation (online or textual) provided with the package. 2246686Sbrian * 2346686Sbrian * Redistribution and use in source and binary forms, with or without 2446686Sbrian * modification, are permitted provided that the following conditions 2546686Sbrian * are met: 2647461Sbrian * 1. Redistributions of source code must retain the copyright 2746686Sbrian * notice, this list of conditions and the following disclaimer. 2846686Sbrian * 2. Redistributions in binary form must reproduce the above copyright 2946686Sbrian * notice, this list of conditions and the following disclaimer in the 3046686Sbrian * documentation and/or other materials provided with the distribution. 3146686Sbrian * 3. All advertising materials mentioning features or use of this software 3246686Sbrian * must display the following acknowledgement: 3346686Sbrian * "This product includes cryptographic software written by 3446686Sbrian * Eric Young (eay@cryptsoft.com)" 3546686Sbrian * The word 'cryptographic' can be left out if the rouines from the library 3646686Sbrian * being used are not cryptographic related :-). 3746686Sbrian * 4. If you include any Windows specific code (or a derivative thereof) from 3846686Sbrian * the apps directory (application code) you must include an acknowledgement: 3946686Sbrian * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4046686Sbrian * 4146686Sbrian * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4246686Sbrian * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4346686Sbrian * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4446686Sbrian * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4546686Sbrian * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4646686Sbrian * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4746686Sbrian * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4846686Sbrian * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4946686Sbrian * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5046686Sbrian * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5146686Sbrian * SUCH DAMAGE. 5246686Sbrian * 5346686Sbrian * The licence and distribution terms for any publically available version or 5446686Sbrian * derivative of this code cannot be changed. i.e. this code cannot simply be 5546686Sbrian * copied and put under another distribution licence 5646686Sbrian * [including the GNU Public Licence.] 5746686Sbrian */ 5846686Sbrian 5946686Sbrian#include <assert.h> 6046686Sbrian#include <stdio.h> 6146686Sbrian 6246686Sbrian#include <openssl/err.h> 6346686Sbrian 6446686Sbrian#include "bn_arch.h" 6546686Sbrian#include "bn_local.h" 6646686Sbrian 6746686Sbrian#ifndef HAVE_BN_ADD_WORDS 6846686Sbrian#ifdef BN_LLONG 6946686SbrianBN_ULONG 7046686Sbrianbn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 7146686Sbrian{ 7246686Sbrian BN_ULLONG ll = 0; 7346686Sbrian 7446686Sbrian assert(n >= 0); 7546686Sbrian if (n <= 0) 7646686Sbrian return ((BN_ULONG)0); 7746686Sbrian 7846686Sbrian#ifndef OPENSSL_SMALL_FOOTPRINT 7946686Sbrian while (n & ~3) { 8046686Sbrian ll += (BN_ULLONG)a[0] + b[0]; 8147061Sbrian r[0] = (BN_ULONG)ll & BN_MASK2; 8247061Sbrian ll >>= BN_BITS2; 8347061Sbrian ll += (BN_ULLONG)a[1] + b[1]; 8447061Sbrian r[1] = (BN_ULONG)ll & BN_MASK2; 8547061Sbrian ll >>= BN_BITS2; 8647061Sbrian ll += (BN_ULLONG)a[2] + b[2]; 8747061Sbrian r[2] = (BN_ULONG)ll & BN_MASK2; 8847061Sbrian ll >>= BN_BITS2; 8947061Sbrian ll += (BN_ULLONG)a[3] + b[3]; 9047061Sbrian r[3] = (BN_ULONG)ll & BN_MASK2; 9147061Sbrian ll >>= BN_BITS2; 9247061Sbrian a += 4; 9347061Sbrian b += 4; 9447061Sbrian r += 4; 9547061Sbrian n -= 4; 9647061Sbrian } 9747061Sbrian#endif 9847061Sbrian while (n) { 9946686Sbrian ll += (BN_ULLONG)a[0] + b[0]; 10047461Sbrian r[0] = (BN_ULONG)ll & BN_MASK2; 10147461Sbrian ll >>= BN_BITS2; 10247061Sbrian a++; 10347461Sbrian b++; 10447061Sbrian r++; 10547061Sbrian n--; 10647061Sbrian } 10747061Sbrian return ((BN_ULONG)ll); 10847061Sbrian} 10947061Sbrian#else /* !BN_LLONG */ 11047061SbrianBN_ULONG 11147061Sbrianbn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 11246686Sbrian{ 11346686Sbrian BN_ULONG c, l, t; 11446686Sbrian 11546686Sbrian assert(n >= 0); 11646686Sbrian if (n <= 0) 11746686Sbrian return ((BN_ULONG)0); 11846686Sbrian 11946686Sbrian c = 0; 12046686Sbrian#ifndef OPENSSL_SMALL_FOOTPRINT 12146686Sbrian while (n & ~3) { 12246686Sbrian t = a[0]; 12346686Sbrian t = (t + c) & BN_MASK2; 12446686Sbrian c = (t < c); 12546686Sbrian l = (t + b[0]) & BN_MASK2; 12646686Sbrian c += (l < t); 12746686Sbrian r[0] = l; 12846686Sbrian t = a[1]; 12946686Sbrian t = (t + c) & BN_MASK2; 13046686Sbrian c = (t < c); 13146686Sbrian l = (t + b[1]) & BN_MASK2; 13246686Sbrian c += (l < t); 13346686Sbrian r[1] = l; 13446686Sbrian t = a[2]; 13546686Sbrian t = (t + c) & BN_MASK2; 13646686Sbrian c = (t < c); 13746686Sbrian l = (t + b[2]) & BN_MASK2; 13846686Sbrian c += (l < t); 13946686Sbrian r[2] = l; 14046686Sbrian t = a[3]; 14146686Sbrian t = (t + c) & BN_MASK2; 14246686Sbrian c = (t < c); 14346686Sbrian l = (t + b[3]) & BN_MASK2; 14446686Sbrian c += (l < t); 14546686Sbrian r[3] = l; 14646686Sbrian a += 4; 14746686Sbrian b += 4; 14846686Sbrian r += 4; 14946686Sbrian n -= 4; 15046686Sbrian } 15146686Sbrian#endif 15246686Sbrian while (n) { 15346686Sbrian t = a[0]; 15446686Sbrian t = (t + c) & BN_MASK2; 15546686Sbrian c = (t < c); 15646686Sbrian l = (t + b[0]) & BN_MASK2; 15746686Sbrian c += (l < t); 15846686Sbrian r[0] = l; 15946686Sbrian a++; 16046686Sbrian b++; 16146686Sbrian r++; 16246686Sbrian n--; 16346686Sbrian } 16446686Sbrian return ((BN_ULONG)c); 16546686Sbrian} 16646686Sbrian#endif /* !BN_LLONG */ 16747461Sbrian#endif 16847061Sbrian 16946686Sbrian#ifndef HAVE_BN_SUB_WORDS 17046686SbrianBN_ULONG 17146686Sbrianbn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 17246686Sbrian{ 17347061Sbrian BN_ULONG t1, t2; 17446686Sbrian 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 ap += min; 295 rp += min; 296 297 while (dif) { 298 dif--; 299 t1 = *(ap++); 300 t2 = (t1 - borrow) & BN_MASK2; 301 *(rp++) = t2; 302 borrow &= (t1 == 0); 303 } 304 305 while (max > 0 && *--rp == 0) 306 max--; 307 308 r->top = max; 309 r->neg = 0; 310 bn_correct_top(r); 311 return 1; 312} 313 314int 315BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 316{ 317 int ret, r_neg; 318 319 320 if (a->neg == b->neg) { 321 r_neg = a->neg; 322 ret = BN_uadd(r, a, b); 323 } else { 324 int cmp = BN_ucmp(a, b); 325 326 if (cmp > 0) { 327 r_neg = a->neg; 328 ret = BN_usub(r, a, b); 329 } else if (cmp < 0) { 330 r_neg = b->neg; 331 ret = BN_usub(r, b, a); 332 } else { 333 r_neg = 0; 334 BN_zero(r); 335 ret = 1; 336 } 337 } 338 339 r->neg = r_neg; 340 return ret; 341} 342 343int 344BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 345{ 346 int ret, r_neg; 347 348 349 if (a->neg != b->neg) { 350 r_neg = a->neg; 351 ret = BN_uadd(r, a, b); 352 } else { 353 int cmp = BN_ucmp(a, b); 354 355 if (cmp > 0) { 356 r_neg = a->neg; 357 ret = BN_usub(r, a, b); 358 } else if (cmp < 0) { 359 r_neg = !b->neg; 360 ret = BN_usub(r, b, a); 361 } else { 362 r_neg = 0; 363 BN_zero(r); 364 ret = 1; 365 } 366 } 367 368 r->neg = r_neg; 369 return ret; 370} 371