bn_add.c revision 1.24
1/* $OpenBSD: bn_add.c,v 1.24 2023/02/22 05:46:37 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 <limits.h> 61#include <stdio.h> 62 63#include <openssl/err.h> 64 65#include "bn_arch.h" 66#include "bn_local.h" 67#include "bn_internal.h" 68 69/* 70 * bn_add_words() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b 71 * are both arrays of words. Any carry resulting from the addition is returned. 72 */ 73#ifndef HAVE_BN_ADD_WORDS 74BN_ULONG 75bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 76{ 77 BN_ULONG carry = 0; 78 79 assert(n >= 0); 80 if (n <= 0) 81 return 0; 82 83#ifndef OPENSSL_SMALL_FOOTPRINT 84 while (n & ~3) { 85 bn_addw_addw(a[0], b[0], carry, &carry, &r[0]); 86 bn_addw_addw(a[1], b[1], carry, &carry, &r[1]); 87 bn_addw_addw(a[2], b[2], carry, &carry, &r[2]); 88 bn_addw_addw(a[3], b[3], carry, &carry, &r[3]); 89 a += 4; 90 b += 4; 91 r += 4; 92 n -= 4; 93 } 94#endif 95 while (n) { 96 bn_addw_addw(a[0], b[0], carry, &carry, &r[0]); 97 a++; 98 b++; 99 r++; 100 n--; 101 } 102 return carry; 103} 104#endif 105 106/* 107 * bn_add() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b are both 108 * arrays of words (r may be the same as a or b). The length of a and b may 109 * differ, while r must be at least max(a_len, b_len) in length. Any carry 110 * resulting from the addition is returned. 111 */ 112#ifndef HAVE_BN_ADD 113BN_ULONG 114bn_add(BN_ULONG *r, int r_len, const BN_ULONG *a, int a_len, const BN_ULONG *b, 115 int b_len) 116{ 117 int min_len, diff_len; 118 BN_ULONG carry = 0; 119 120 if ((min_len = a_len) > b_len) 121 min_len = b_len; 122 123 diff_len = a_len - b_len; 124 125 carry = bn_add_words(r, a, b, min_len); 126 127 a += min_len; 128 b += min_len; 129 r += min_len; 130 131 /* XXX - consider doing four at a time to match bn_add_words(). */ 132 while (diff_len < 0) { 133 /* Compute r[0] = 0 + b[0] + carry. */ 134 bn_addw(b[0], carry, &carry, &r[0]); 135 diff_len++; 136 b++; 137 r++; 138 } 139 140 /* XXX - consider doing four at a time to match bn_add_words(). */ 141 while (diff_len > 0) { 142 /* Compute r[0] = a[0] + 0 + carry. */ 143 bn_addw(a[0], carry, &carry, &r[0]); 144 diff_len--; 145 a++; 146 r++; 147 } 148 149 return carry; 150} 151#endif 152 153/* 154 * bn_sub_words() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b 155 * are both arrays of words. Any borrow resulting from the subtraction is 156 * returned. 157 */ 158#ifndef HAVE_BN_SUB_WORDS 159BN_ULONG 160bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) 161{ 162 BN_ULONG borrow = 0; 163 164 assert(n >= 0); 165 if (n <= 0) 166 return 0; 167 168#ifndef OPENSSL_SMALL_FOOTPRINT 169 while (n & ~3) { 170 bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]); 171 bn_subw_subw(a[1], b[1], borrow, &borrow, &r[1]); 172 bn_subw_subw(a[2], b[2], borrow, &borrow, &r[2]); 173 bn_subw_subw(a[3], b[3], borrow, &borrow, &r[3]); 174 a += 4; 175 b += 4; 176 r += 4; 177 n -= 4; 178 } 179#endif 180 while (n) { 181 bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]); 182 a++; 183 b++; 184 r++; 185 n--; 186 } 187 return borrow; 188} 189#endif 190 191/* 192 * bn_sub() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b are both 193 * arrays of words (r may be the same as a or b). The length of a and b may 194 * differ, while r must be at least max(a_len, b_len) in length. Any borrow 195 * resulting from the subtraction is returned. 196 */ 197#ifndef HAVE_BN_SUB 198BN_ULONG 199bn_sub(BN_ULONG *r, int r_len, const BN_ULONG *a, int a_len, const BN_ULONG *b, 200 int b_len) 201{ 202 int min_len, diff_len; 203 BN_ULONG borrow = 0; 204 205 if ((min_len = a_len) > b_len) 206 min_len = b_len; 207 208 diff_len = a_len - b_len; 209 210 borrow = bn_sub_words(r, a, b, min_len); 211 212 a += min_len; 213 b += min_len; 214 r += min_len; 215 216 /* XXX - consider doing four at a time to match bn_sub_words. */ 217 while (diff_len < 0) { 218 /* Compute r[0] = 0 - b[0] - borrow. */ 219 bn_subw(0 - b[0], borrow, &borrow, &r[0]); 220 diff_len++; 221 b++; 222 r++; 223 } 224 225 /* XXX - consider doing four at a time to match bn_sub_words. */ 226 while (diff_len > 0) { 227 /* Compute r[0] = a[0] - 0 - borrow. */ 228 bn_subw(a[0], borrow, &borrow, &r[0]); 229 diff_len--; 230 a++; 231 r++; 232 } 233 234 return borrow; 235} 236#endif 237 238int 239BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 240{ 241 BN_ULONG carry; 242 int rn; 243 244 if ((rn = a->top) < b->top) 245 rn = b->top; 246 if (rn == INT_MAX) 247 return 0; 248 if (!bn_wexpand(r, rn + 1)) 249 return 0; 250 251 carry = bn_add(r->d, rn, a->d, a->top, b->d, b->top); 252 r->d[rn] = carry; 253 254 r->top = rn + (carry & 1); 255 r->neg = 0; 256 257 return 1; 258} 259 260int 261BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 262{ 263 BN_ULONG borrow; 264 int rn; 265 266 if (a->top < b->top) { 267 BNerror(BN_R_ARG2_LT_ARG3); 268 return 0; 269 } 270 rn = a->top; 271 272 if (!bn_wexpand(r, rn)) 273 return 0; 274 275 borrow = bn_sub(r->d, rn, a->d, a->top, b->d, b->top); 276 if (borrow > 0) { 277 BNerror(BN_R_ARG2_LT_ARG3); 278 return 0; 279 } 280 281 r->top = rn; 282 r->neg = 0; 283 284 bn_correct_top(r); 285 286 return 1; 287} 288 289int 290BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 291{ 292 int ret, r_neg; 293 294 if (a->neg == b->neg) { 295 r_neg = a->neg; 296 ret = BN_uadd(r, a, b); 297 } else { 298 int cmp = BN_ucmp(a, b); 299 300 if (cmp > 0) { 301 r_neg = a->neg; 302 ret = BN_usub(r, a, b); 303 } else if (cmp < 0) { 304 r_neg = b->neg; 305 ret = BN_usub(r, b, a); 306 } else { 307 r_neg = 0; 308 BN_zero(r); 309 ret = 1; 310 } 311 } 312 313 BN_set_negative(r, r_neg); 314 315 return ret; 316} 317 318int 319BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 320{ 321 int ret, r_neg; 322 323 if (a->neg != b->neg) { 324 r_neg = a->neg; 325 ret = BN_uadd(r, a, b); 326 } else { 327 int cmp = BN_ucmp(a, b); 328 329 if (cmp > 0) { 330 r_neg = a->neg; 331 ret = BN_usub(r, a, b); 332 } else if (cmp < 0) { 333 r_neg = !b->neg; 334 ret = BN_usub(r, b, a); 335 } else { 336 r_neg = 0; 337 BN_zero(r); 338 ret = 1; 339 } 340 } 341 342 BN_set_negative(r, r_neg); 343 344 return ret; 345} 346