1 /* $OpenBSD: bn_div.c,v 1.22 2014/07/11 08:44:47 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 <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) 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 int 120 BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 121 BN_CTX *ctx) 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 BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED); 135 return 0; 136 } 137 138 bn_check_top(num); 139 140 if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) || 141 (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) { 142 no_branch = 1; 143 } 144 145 bn_check_top(dv); 146 bn_check_top(rm); 147 /* bn_check_top(num); */ /* 'num' has been checked already */ 148 bn_check_top(divisor); 149 150 if (BN_is_zero(divisor)) { 151 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); 152 return (0); 153 } 154 155 if (!no_branch && BN_ucmp(num, divisor) < 0) { 156 if (rm != NULL) { 157 if (BN_copy(rm, num) == NULL) 158 return (0); 159 } 160 if (dv != NULL) 161 BN_zero(dv); 162 return (1); 163 } 164 165 BN_CTX_start(ctx); 166 tmp = BN_CTX_get(ctx); 167 snum = BN_CTX_get(ctx); 168 sdiv = BN_CTX_get(ctx); 169 if (dv == NULL) 170 res = BN_CTX_get(ctx); 171 else 172 res = dv; 173 if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL) 174 goto err; 175 176 /* First we normalise the numbers */ 177 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); 178 if (!(BN_lshift(sdiv, divisor, norm_shift))) 179 goto err; 180 sdiv->neg = 0; 181 norm_shift += BN_BITS2; 182 if (!(BN_lshift(snum, num, norm_shift))) 183 goto err; 184 snum->neg = 0; 185 186 if (no_branch) { 187 /* Since we don't know whether snum is larger than sdiv, 188 * we pad snum with enough zeroes without changing its 189 * value. 190 */ 191 if (snum->top <= sdiv->top + 1) { 192 if (bn_wexpand(snum, sdiv->top + 2) == NULL) 193 goto err; 194 for (i = snum->top; i < sdiv->top + 2; i++) 195 snum->d[i] = 0; 196 snum->top = sdiv->top + 2; 197 } else { 198 if (bn_wexpand(snum, snum->top + 1) == NULL) 199 goto err; 200 snum->d[snum->top] = 0; 201 snum->top ++; 202 } 203 } 204 205 div_n = sdiv->top; 206 num_n = snum->top; 207 loop = num_n - div_n; 208 /* Lets setup a 'window' into snum 209 * This is the part that corresponds to the current 210 * 'area' being divided */ 211 wnum.neg = 0; 212 wnum.d = &(snum->d[loop]); 213 wnum.top = div_n; 214 /* only needed when BN_ucmp messes up the values between top and max */ 215 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ 216 wnum.flags = snum->flags | BN_FLG_STATIC_DATA; 217 218 /* Get the top 2 words of sdiv */ 219 /* div_n=sdiv->top; */ 220 d0 = sdiv->d[div_n - 1]; 221 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 222 223 /* pointer to the 'top' of snum */ 224 wnump = &(snum->d[num_n - 1]); 225 226 /* Setup to 'res' */ 227 res->neg = (num->neg ^ divisor->neg); 228 if (!bn_wexpand(res, (loop + 1))) 229 goto err; 230 res->top = loop - no_branch; 231 resp = &(res->d[loop - 1]); 232 233 /* space for temp */ 234 if (!bn_wexpand(tmp, (div_n + 1))) 235 goto err; 236 237 if (!no_branch) { 238 if (BN_ucmp(&wnum, sdiv) >= 0) { 239 /* If BN_DEBUG_RAND is defined BN_ucmp changes (via 240 * bn_pollute) the const bignum arguments => 241 * clean the values between top and max again */ 242 bn_clear_top2max(&wnum); 243 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); 244 *resp = 1; 245 } else 246 res->top--; 247 } 248 249 /* if res->top == 0 then clear the neg value otherwise decrease 250 * the resp pointer */ 251 if (res->top == 0) 252 res->neg = 0; 253 else 254 resp--; 255 256 for (i = 0; i < loop - 1; i++, wnump--, resp--) { 257 BN_ULONG q, l0; 258 /* the first part of the loop uses the top two words of 259 * snum and sdiv to calculate a BN_ULONG q such that 260 * | wnum - sdiv * q | < sdiv */ 261 #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) 262 BN_ULONG bn_div_3_words(BN_ULONG*, BN_ULONG, BN_ULONG); 263 q = bn_div_3_words(wnump, d1, d0); 264 #else 265 BN_ULONG n0, n1, rem = 0; 266 267 n0 = wnump[0]; 268 n1 = wnump[-1]; 269 if (n0 == d0) 270 q = BN_MASK2; 271 else /* n0 < d0 */ 272 { 273 #ifdef BN_LLONG 274 BN_ULLONG t2; 275 276 #if defined(BN_DIV2W) && !defined(bn_div_words) 277 q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2)|n1)/d0); 278 #else 279 q = bn_div_words(n0, n1, d0); 280 #endif 281 282 #ifndef REMAINDER_IS_ALREADY_CALCULATED 283 /* 284 * rem doesn't have to be BN_ULLONG. The least we 285 * know it's less that d0, isn't it? 286 */ 287 rem = (n1 - q * d0) & BN_MASK2; 288 #endif 289 t2 = (BN_ULLONG)d1*q; 290 291 for (;;) { 292 if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | 293 wnump[-2])) 294 break; 295 q--; 296 rem += d0; 297 if (rem < d0) break; /* don't let rem overflow */ 298 t2 -= d1; 299 } 300 #else /* !BN_LLONG */ 301 BN_ULONG t2l, t2h; 302 303 q = bn_div_words(n0, n1, d0); 304 #ifndef REMAINDER_IS_ALREADY_CALCULATED 305 rem = (n1 - q*d0)&BN_MASK2; 306 #endif 307 308 #if defined(BN_UMULT_LOHI) 309 BN_UMULT_LOHI(t2l, t2h, d1, q); 310 #elif defined(BN_UMULT_HIGH) 311 t2l = d1 * q; 312 t2h = BN_UMULT_HIGH(d1, q); 313 #else 314 { 315 BN_ULONG ql, qh; 316 t2l = LBITS(d1); 317 t2h = HBITS(d1); 318 ql = LBITS(q); 319 qh = HBITS(q); 320 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ 321 } 322 #endif 323 324 for (;;) { 325 if ((t2h < rem) || 326 ((t2h == rem) && (t2l <= wnump[-2]))) 327 break; 328 q--; 329 rem += d0; 330 if (rem < d0) 331 break; /* don't let rem overflow */ 332 if (t2l < d1) 333 t2h--; 334 t2l -= d1; 335 } 336 #endif /* !BN_LLONG */ 337 } 338 #endif /* !BN_DIV3W */ 339 340 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 341 tmp->d[div_n] = l0; 342 wnum.d--; 343 /* ingore top values of the bignums just sub the two 344 * BN_ULONG arrays with bn_sub_words */ 345 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 346 /* Note: As we have considered only the leading 347 * two BN_ULONGs in the calculation of q, sdiv * q 348 * might be greater than wnum (but then (q-1) * sdiv 349 * is less or equal than wnum) 350 */ 351 q--; 352 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) 353 /* we can't have an overflow here (assuming 354 * that q != 0, but if q == 0 then tmp is 355 * zero anyway) */ 356 (*wnump)++; 357 } 358 /* store part of the result */ 359 *resp = q; 360 } 361 bn_correct_top(snum); 362 if (rm != NULL) { 363 /* Keep a copy of the neg flag in num because if rm==num 364 * BN_rshift() will overwrite it. 365 */ 366 int neg = num->neg; 367 BN_rshift(rm, snum, norm_shift); 368 if (!BN_is_zero(rm)) 369 rm->neg = neg; 370 bn_check_top(rm); 371 } 372 if (no_branch) 373 bn_correct_top(res); 374 BN_CTX_end(ctx); 375 return (1); 376 377 err: 378 bn_check_top(rm); 379 BN_CTX_end(ctx); 380 return (0); 381 } 382