1 /* $OpenBSD: bn_div.c,v 1.25 2017/01/29 17:49:22 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 <stdio.h> 60 61 #include <openssl/opensslconf.h> 62 63 #include <openssl/bn.h> 64 #include <openssl/err.h> 65 66 #include "bn_lcl.h" 67 68 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ 69 && !defined(BN_DIV3W) 70 # if defined(__GNUC__) && __GNUC__>=2 71 # if defined(__i386) || defined (__i386__) 72 /* 73 * There were two reasons for implementing this template: 74 * - GNU C generates a call to a function (__udivdi3 to be exact) 75 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to 76 * understand why...); 77 * - divl doesn't only calculate quotient, but also leaves 78 * remainder in %edx which we can definitely use here:-) 79 * 80 * <appro@fy.chalmers.se> 81 */ 82 #undef bn_div_words 83 # define bn_div_words(n0,n1,d0) \ 84 ({ asm volatile ( \ 85 "divl %4" \ 86 : "=a"(q), "=d"(rem) \ 87 : "a"(n1), "d"(n0), "g"(d0) \ 88 : "cc"); \ 89 q; \ 90 }) 91 # define REMAINDER_IS_ALREADY_CALCULATED 92 # elif defined(__x86_64) && defined(_LP64) 93 /* 94 * Same story here, but it's 128-bit by 64-bit division. Wow! 95 * <appro@fy.chalmers.se> 96 */ 97 # undef bn_div_words 98 # define bn_div_words(n0,n1,d0) \ 99 ({ asm volatile ( \ 100 "divq %4" \ 101 : "=a"(q), "=d"(rem) \ 102 : "a"(n1), "d"(n0), "g"(d0) \ 103 : "cc"); \ 104 q; \ 105 }) 106 # define REMAINDER_IS_ALREADY_CALCULATED 107 # endif /* __<cpu> */ 108 # endif /* __GNUC__ */ 109 #endif /* OPENSSL_NO_ASM */ 110 111 112 /* BN_div computes dv := num / divisor, rounding towards 113 * zero, and sets up rm such that dv*divisor + rm = num holds. 114 * Thus: 115 * dv->neg == num->neg ^ divisor->neg (unless the result is zero) 116 * rm->neg == num->neg (unless the remainder is zero) 117 * If 'dv' or 'rm' is NULL, the respective value is not returned. 118 */ 119 static int 120 BN_div_internal(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 121 BN_CTX *ctx, int ct) 122 { 123 int norm_shift, i, loop; 124 BIGNUM *tmp, wnum, *snum, *sdiv, *res; 125 BN_ULONG *resp, *wnump; 126 BN_ULONG d0, d1; 127 int num_n, div_n; 128 int no_branch = 0; 129 130 /* Invalid zero-padding would have particularly bad consequences 131 * in the case of 'num', so don't just rely on bn_check_top() for this one 132 * (bn_check_top() works only for BN_DEBUG builds) */ 133 if (num->top > 0 && num->d[num->top - 1] == 0) { 134 BNerror(BN_R_NOT_INITIALIZED); 135 return 0; 136 } 137 138 bn_check_top(num); 139 140 if (ct) 141 no_branch = 1; 142 143 bn_check_top(dv); 144 bn_check_top(rm); 145 /* bn_check_top(num); */ /* 'num' has been checked already */ 146 bn_check_top(divisor); 147 148 if (BN_is_zero(divisor)) { 149 BNerror(BN_R_DIV_BY_ZERO); 150 return (0); 151 } 152 153 if (!no_branch && BN_ucmp(num, divisor) < 0) { 154 if (rm != NULL) { 155 if (BN_copy(rm, num) == NULL) 156 return (0); 157 } 158 if (dv != NULL) 159 BN_zero(dv); 160 return (1); 161 } 162 163 BN_CTX_start(ctx); 164 tmp = BN_CTX_get(ctx); 165 snum = BN_CTX_get(ctx); 166 sdiv = BN_CTX_get(ctx); 167 if (dv == NULL) 168 res = BN_CTX_get(ctx); 169 else 170 res = dv; 171 if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL) 172 goto err; 173 174 /* First we normalise the numbers */ 175 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); 176 if (!(BN_lshift(sdiv, divisor, norm_shift))) 177 goto err; 178 sdiv->neg = 0; 179 norm_shift += BN_BITS2; 180 if (!(BN_lshift(snum, num, norm_shift))) 181 goto err; 182 snum->neg = 0; 183 184 if (no_branch) { 185 /* Since we don't know whether snum is larger than sdiv, 186 * we pad snum with enough zeroes without changing its 187 * value. 188 */ 189 if (snum->top <= sdiv->top + 1) { 190 if (bn_wexpand(snum, sdiv->top + 2) == NULL) 191 goto err; 192 for (i = snum->top; i < sdiv->top + 2; i++) 193 snum->d[i] = 0; 194 snum->top = sdiv->top + 2; 195 } else { 196 if (bn_wexpand(snum, snum->top + 1) == NULL) 197 goto err; 198 snum->d[snum->top] = 0; 199 snum->top ++; 200 } 201 } 202 203 div_n = sdiv->top; 204 num_n = snum->top; 205 loop = num_n - div_n; 206 /* Lets setup a 'window' into snum 207 * This is the part that corresponds to the current 208 * 'area' being divided */ 209 wnum.neg = 0; 210 wnum.d = &(snum->d[loop]); 211 wnum.top = div_n; 212 /* only needed when BN_ucmp messes up the values between top and max */ 213 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ 214 wnum.flags = snum->flags | BN_FLG_STATIC_DATA; 215 216 /* Get the top 2 words of sdiv */ 217 /* div_n=sdiv->top; */ 218 d0 = sdiv->d[div_n - 1]; 219 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 220 221 /* pointer to the 'top' of snum */ 222 wnump = &(snum->d[num_n - 1]); 223 224 /* Setup to 'res' */ 225 res->neg = (num->neg ^ divisor->neg); 226 if (!bn_wexpand(res, (loop + 1))) 227 goto err; 228 res->top = loop - no_branch; 229 resp = &(res->d[loop - 1]); 230 231 /* space for temp */ 232 if (!bn_wexpand(tmp, (div_n + 1))) 233 goto err; 234 235 if (!no_branch) { 236 if (BN_ucmp(&wnum, sdiv) >= 0) { 237 /* If BN_DEBUG_RAND is defined BN_ucmp changes (via 238 * bn_pollute) the const bignum arguments => 239 * clean the values between top and max again */ 240 bn_clear_top2max(&wnum); 241 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); 242 *resp = 1; 243 } else 244 res->top--; 245 } 246 247 /* if res->top == 0 then clear the neg value otherwise decrease 248 * the resp pointer */ 249 if (res->top == 0) 250 res->neg = 0; 251 else 252 resp--; 253 254 for (i = 0; i < loop - 1; i++, wnump--, resp--) { 255 BN_ULONG q, l0; 256 /* the first part of the loop uses the top two words of 257 * snum and sdiv to calculate a BN_ULONG q such that 258 * | wnum - sdiv * q | < sdiv */ 259 #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) 260 BN_ULONG bn_div_3_words(BN_ULONG*, BN_ULONG, BN_ULONG); 261 q = bn_div_3_words(wnump, d1, d0); 262 #else 263 BN_ULONG n0, n1, rem = 0; 264 265 n0 = wnump[0]; 266 n1 = wnump[-1]; 267 if (n0 == d0) 268 q = BN_MASK2; 269 else /* n0 < d0 */ 270 { 271 #ifdef BN_LLONG 272 BN_ULLONG t2; 273 274 #if defined(BN_DIV2W) && !defined(bn_div_words) 275 q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2)|n1)/d0); 276 #else 277 q = bn_div_words(n0, n1, d0); 278 #endif 279 280 #ifndef REMAINDER_IS_ALREADY_CALCULATED 281 /* 282 * rem doesn't have to be BN_ULLONG. The least we 283 * know it's less that d0, isn't it? 284 */ 285 rem = (n1 - q * d0) & BN_MASK2; 286 #endif 287 t2 = (BN_ULLONG)d1*q; 288 289 for (;;) { 290 if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | 291 wnump[-2])) 292 break; 293 q--; 294 rem += d0; 295 if (rem < d0) break; /* don't let rem overflow */ 296 t2 -= d1; 297 } 298 #else /* !BN_LLONG */ 299 BN_ULONG t2l, t2h; 300 301 q = bn_div_words(n0, n1, d0); 302 #ifndef REMAINDER_IS_ALREADY_CALCULATED 303 rem = (n1 - q*d0)&BN_MASK2; 304 #endif 305 306 #if defined(BN_UMULT_LOHI) 307 BN_UMULT_LOHI(t2l, t2h, d1, q); 308 #elif defined(BN_UMULT_HIGH) 309 t2l = d1 * q; 310 t2h = BN_UMULT_HIGH(d1, q); 311 #else 312 { 313 BN_ULONG ql, qh; 314 t2l = LBITS(d1); 315 t2h = HBITS(d1); 316 ql = LBITS(q); 317 qh = HBITS(q); 318 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ 319 } 320 #endif 321 322 for (;;) { 323 if ((t2h < rem) || 324 ((t2h == rem) && (t2l <= wnump[-2]))) 325 break; 326 q--; 327 rem += d0; 328 if (rem < d0) 329 break; /* don't let rem overflow */ 330 if (t2l < d1) 331 t2h--; 332 t2l -= d1; 333 } 334 #endif /* !BN_LLONG */ 335 } 336 #endif /* !BN_DIV3W */ 337 338 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 339 tmp->d[div_n] = l0; 340 wnum.d--; 341 /* ingore top values of the bignums just sub the two 342 * BN_ULONG arrays with bn_sub_words */ 343 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 344 /* Note: As we have considered only the leading 345 * two BN_ULONGs in the calculation of q, sdiv * q 346 * might be greater than wnum (but then (q-1) * sdiv 347 * is less or equal than wnum) 348 */ 349 q--; 350 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) 351 /* we can't have an overflow here (assuming 352 * that q != 0, but if q == 0 then tmp is 353 * zero anyway) */ 354 (*wnump)++; 355 } 356 /* store part of the result */ 357 *resp = q; 358 } 359 bn_correct_top(snum); 360 if (rm != NULL) { 361 /* Keep a copy of the neg flag in num because if rm==num 362 * BN_rshift() will overwrite it. 363 */ 364 int neg = num->neg; 365 BN_rshift(rm, snum, norm_shift); 366 if (!BN_is_zero(rm)) 367 rm->neg = neg; 368 bn_check_top(rm); 369 } 370 if (no_branch) 371 bn_correct_top(res); 372 BN_CTX_end(ctx); 373 return (1); 374 375 err: 376 bn_check_top(rm); 377 BN_CTX_end(ctx); 378 return (0); 379 } 380 381 int 382 BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 383 BN_CTX *ctx) 384 { 385 int ct = ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) || 386 (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)); 387 388 return BN_div_internal(dv, rm, num, divisor, ctx, ct); 389 } 390 391 int 392 BN_div_nonct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 393 BN_CTX *ctx) 394 { 395 return BN_div_internal(dv, rm, num, divisor, ctx, 0); 396 } 397 398 int 399 BN_div_ct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 400 BN_CTX *ctx) 401 { 402 return BN_div_internal(dv, rm, num, divisor, ctx, 1); 403 } 404