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