| Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_div.c |
| Source code | Switch to Preprocessed file |
| Line | Source | Count | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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) | - | ||||||||||||||||||||||||
| 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) {
| 0-458458 | ||||||||||||||||||||||||
| 134 | BNerror(BN_R_NOT_INITIALIZED); | - | ||||||||||||||||||||||||
| 135 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
| 136 | } | - | ||||||||||||||||||||||||
| 137 | - | |||||||||||||||||||||||||
| 138 | bn_check_top(num); | - | ||||||||||||||||||||||||
| 139 | - | |||||||||||||||||||||||||
| 140 | if (ct)
| 1421-457664 | ||||||||||||||||||||||||
| 141 | no_branch = 1; executed 457664 times by 14 tests: no_branch = 1;Executed by:
| 457664 | ||||||||||||||||||||||||
| 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)) {
| 6-459079 | ||||||||||||||||||||||||
| 149 | BNerror(BN_R_DIV_BY_ZERO); | - | ||||||||||||||||||||||||
| 150 | return (0); executed 6 times by 1 test: return (0);Executed by:
| 6 | ||||||||||||||||||||||||
| 151 | } | - | ||||||||||||||||||||||||
| 152 | - | |||||||||||||||||||||||||
| 153 | if (!no_branch && BN_ucmp(num, divisor) < 0) {
| 281-457659 | ||||||||||||||||||||||||
| 154 | if (rm != NULL) {
| 0-281 | ||||||||||||||||||||||||
| 155 | if (BN_copy(rm, num) == NULL)
| 0-281 | ||||||||||||||||||||||||
| 156 | return (0); never executed: return (0); | 0 | ||||||||||||||||||||||||
| 157 | } executed 281 times by 2 tests: end of blockExecuted by:
| 281 | ||||||||||||||||||||||||
| 158 | if (dv != NULL)
| 51-230 | ||||||||||||||||||||||||
| 159 | BN_zero(dv); executed 51 times by 1 test: (BN_set_word((dv),0));Executed by:
| 51 | ||||||||||||||||||||||||
| 160 | return (1); executed 281 times by 2 tests: return (1);Executed by:
| 281 | ||||||||||||||||||||||||
| 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)
| 119825-338973 | ||||||||||||||||||||||||
| 168 | res = BN_CTX_get(ctx); executed 119825 times by 14 tests: res = BN_CTX_get(ctx);Executed by:
| 119825 | ||||||||||||||||||||||||
| 169 | else | - | ||||||||||||||||||||||||
| 170 | res = dv; executed 338973 times by 14 tests: res = dv;Executed by:
| 338973 | ||||||||||||||||||||||||
| 171 | if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL)
| 0-458798 | ||||||||||||||||||||||||
| 172 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 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)))
| 0-458798 | ||||||||||||||||||||||||
| 177 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 178 | sdiv->neg = 0; | - | ||||||||||||||||||||||||
| 179 | norm_shift += BN_BITS2; | - | ||||||||||||||||||||||||
| 180 | if (!(BN_lshift(snum, num, norm_shift)))
| 0-458798 | ||||||||||||||||||||||||
| 181 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 182 | snum->neg = 0; | - | ||||||||||||||||||||||||
| 183 | - | |||||||||||||||||||||||||
| 184 | if (no_branch) {
| 1139-457659 | ||||||||||||||||||||||||
| 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) {
| 79263-378396 | ||||||||||||||||||||||||
| 190 | if (bn_wexpand(snum, sdiv->top + 2) == NULL)
| 0-79263 | ||||||||||||||||||||||||
| 191 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 192 | for (i = snum->top; i < sdiv->top + 2; i++)
| 79263-89981 | ||||||||||||||||||||||||
| 193 | snum->d[i] = 0; executed 89981 times by 14 tests: snum->d[i] = 0;Executed by:
| 89981 | ||||||||||||||||||||||||
| 194 | snum->top = sdiv->top + 2; | - | ||||||||||||||||||||||||
| 195 | } else { executed 79263 times by 14 tests: end of blockExecuted by:
| 79263 | ||||||||||||||||||||||||
| 196 | if (bn_wexpand(snum, snum->top + 1) == NULL)
| 0-378396 | ||||||||||||||||||||||||
| 197 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 198 | snum->d[snum->top] = 0; | - | ||||||||||||||||||||||||
| 199 | snum->top ++; | - | ||||||||||||||||||||||||
| 200 | } executed 378396 times by 14 tests: end of blockExecuted by:
| 378396 | ||||||||||||||||||||||||
| 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];
| 130955-327843 | ||||||||||||||||||||||||
| 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)))
| 0-458798 | ||||||||||||||||||||||||
| 227 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 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)))
| 0-458798 | ||||||||||||||||||||||||
| 233 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
| 234 | - | |||||||||||||||||||||||||
| 235 | if (!no_branch) {
| 1139-457659 | ||||||||||||||||||||||||
| 236 | if (BN_ucmp(&wnum, sdiv) >= 0) {
| 23-1116 | ||||||||||||||||||||||||
| 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 executed 23 times by 2 tests: end of blockExecuted by:
| 23 | ||||||||||||||||||||||||
| 244 | res->top--; executed 1116 times by 2 tests: res->top--;Executed by:
| 1116 | ||||||||||||||||||||||||
| 245 | } | - | ||||||||||||||||||||||||
| 246 | - | |||||||||||||||||||||||||
| 247 | /* if res->top == 0 then clear the neg value otherwise decrease | - | ||||||||||||||||||||||||
| 248 | * the resp pointer */ | - | ||||||||||||||||||||||||
| 249 | if (res->top == 0)
| 0-458798 | ||||||||||||||||||||||||
| 250 | res->neg = 0; never executed: res->neg = 0; | 0 | ||||||||||||||||||||||||
| 251 | else | - | ||||||||||||||||||||||||
| 252 | resp--; executed 458798 times by 14 tests: resp--;Executed by:
| 458798 | ||||||||||||||||||||||||
| 253 | - | |||||||||||||||||||||||||
| 254 | for (i = 0; i < loop - 1; i++, wnump--, resp--) {
| 458798-1385068 | ||||||||||||||||||||||||
| 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)
| 110-1384958 | ||||||||||||||||||||||||
| 268 | q = BN_MASK2; executed 110 times by 4 tests: q = (0xffffffffffffffffL);Executed by:
| 110 | ||||||||||||||||||||||||
| 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) ||
| 187633-1307965 | ||||||||||||||||||||||||
| 324 | ((t2h == rem) && (t2l <= wnump[-2])))
| 83-178122 | ||||||||||||||||||||||||
| 325 | break; executed 1317393 times by 14 tests: break;Executed by:
| 1317393 | ||||||||||||||||||||||||
| 326 | q--; | - | ||||||||||||||||||||||||
| 327 | rem += d0; | - | ||||||||||||||||||||||||
| 328 | if (rem < d0)
| 67565-110640 | ||||||||||||||||||||||||
| 329 | break; /* don't let rem overflow */ executed 67565 times by 12 tests: break;Executed by:
| 67565 | ||||||||||||||||||||||||
| 330 | if (t2l < d1)
| 45740-64900 | ||||||||||||||||||||||||
| 331 | t2h--; executed 64900 times by 12 tests: t2h--;Executed by:
| 64900 | ||||||||||||||||||||||||
| 332 | t2l -= d1; | - | ||||||||||||||||||||||||
| 333 | } executed 110640 times by 12 tests: end of blockExecuted by:
| 110640 | ||||||||||||||||||||||||
| 334 | #endif /* !BN_LLONG */ | - | ||||||||||||||||||||||||
| 335 | } executed 1384958 times by 14 tests: end of blockExecuted by:
| 1384958 | ||||||||||||||||||||||||
| 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)) {
| 413-1384655 | ||||||||||||||||||||||||
| 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))
| 0-413 | ||||||||||||||||||||||||
| 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)++; executed 413 times by 6 tests: (*wnump)++;Executed by:
| 413 | ||||||||||||||||||||||||
| 355 | } executed 413 times by 6 tests: end of blockExecuted by:
| 413 | ||||||||||||||||||||||||
| 356 | /* store part of the result */ | - | ||||||||||||||||||||||||
| 357 | *resp = q; | - | ||||||||||||||||||||||||
| 358 | } executed 1385068 times by 14 tests: end of blockExecuted by:
| 1385068 | ||||||||||||||||||||||||
| 359 | bn_correct_top(snum); executed 450459 times by 14 tests: break;Executed by:
executed 458798 times by 14 tests: end of blockExecuted by:
| 0-1869162 | ||||||||||||||||||||||||
| 360 | if (rm != NULL) {
| 3331-455467 | ||||||||||||||||||||||||
| 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))
| 5458-450009 | ||||||||||||||||||||||||
| 367 | rm->neg = neg; executed 450009 times by 14 tests: rm->neg = neg;Executed by:
| 450009 | ||||||||||||||||||||||||
| 368 | bn_check_top(rm); | - | ||||||||||||||||||||||||
| 369 | } executed 455467 times by 14 tests: end of blockExecuted by:
| 455467 | ||||||||||||||||||||||||
| 370 | if (no_branch)
| 1139-457659 | ||||||||||||||||||||||||
| 371 | bn_correct_top(res); executed 454359 times by 14 tests: break;Executed by:
executed 457659 times by 14 tests: end of blockExecuted by:
executed 457659 times by 14 tests: end of blockExecuted by:
| 0-835683 | ||||||||||||||||||||||||
| 372 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
| 373 | return (1); executed 458798 times by 14 tests: return (1);Executed by:
| 458798 | ||||||||||||||||||||||||
| 374 | - | |||||||||||||||||||||||||
| 375 | err: | - | ||||||||||||||||||||||||
| 376 | bn_check_top(rm); | - | ||||||||||||||||||||||||
| 377 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
| 378 | return (0); never executed: return (0); | 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) ||
| 0-1421 | ||||||||||||||||||||||||
| 386 | (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0));
| 0-1421 | ||||||||||||||||||||||||
| 387 | - | |||||||||||||||||||||||||
| 388 | return BN_div_internal(dv, rm, num, divisor, ctx, ct); executed 1421 times by 2 tests: return BN_div_internal(dv, rm, num, divisor, ctx, ct);Executed by:
| 1421 | ||||||||||||||||||||||||
| 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); never executed: return BN_div_internal(dv, rm, num, divisor, ctx, 0); | 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); executed 457664 times by 14 tests: return BN_div_internal(dv, rm, num, divisor, ctx, 1);Executed by:
| 457664 | ||||||||||||||||||||||||
| 403 | } | - | ||||||||||||||||||||||||
| Source code | Switch to Preprocessed file |