X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_div.c;h=4c844902487e9a1203645715b8dd413818afd565;hp=6801eccdd1ce2cf6d4511155c37e11df8f82cc06;hb=a7e8ab41fd6d53abba3f63cb34c9bcccb31efda7;hpb=208fb891e36f16d20262710c70ef0ff3df0e885c diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index 6801eccdd1..4c84490248 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -1,5 +1,5 @@ /* - * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -24,13 +24,13 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, bn_check_top(d); if (BN_is_zero(d)) { BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); - return (0); + return 0; } if (BN_ucmp(m, d) < 0) { if (rem != NULL) { if (BN_copy(rem, m) == NULL) - return (0); + return 0; } if (dv != NULL) BN_zero(dv); @@ -81,11 +81,62 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, ret = 1; end: BN_CTX_end(ctx); - return (ret); + return ret; } #else +# if defined(BN_DIV3W) +BN_ULONG bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0); +# elif 0 +/* + * This is #if-ed away, because it's a reference for assembly implementations, + * where it can and should be made constant-time. But if you want to test it, + * just replace 0 with 1. + */ +# if BN_BITS2 == 64 && defined(__SIZEOF_INT128__) && __SIZEOF_INT128__==16 +# undef BN_ULLONG +# define BN_ULLONG __uint128_t +# define BN_LLONG +# endif + +# ifdef BN_LLONG +# define BN_DIV3W +/* + * Interface is somewhat quirky, |m| is pointer to most significant limb, + * and less significant limb is referred at |m[-1]|. This means that caller + * is responsible for ensuring that |m[-1]| is valid. Second condition that + * has to be met is that |d0|'s most significant bit has to be set. Or in + * other words divisor has to be "bit-aligned to the left." bn_div_fixed_top + * does all this. The subroutine considers four limbs, two of which are + * "overlapping," hence the name... + */ +static BN_ULONG bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0) +{ + BN_ULLONG R = ((BN_ULLONG)m[0] << BN_BITS2) | m[-1]; + BN_ULLONG D = ((BN_ULLONG)d0 << BN_BITS2) | d1; + BN_ULONG Q = 0, mask; + int i; + + for (i = 0; i < BN_BITS2; i++) { + Q <<= 1; + if (R >= D) { + Q |= 1; + R -= D; + } + D >>= 1; + } + + mask = 0 - (Q >> (BN_BITS2 - 1)); /* does it overflow? */ + + Q <<= 1; + Q |= (R >= D); + + return (Q | mask) & BN_MASK2; +} +# endif +# endif + # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ && !defined(PEDANTIC) && !defined(BN_DIV3W) # if defined(__GNUC__) && __GNUC__>=2 @@ -97,8 +148,6 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, * understand why...); * - divl doesn't only calculate quotient, but also leaves * remainder in %edx which we can definitely use here:-) - * - * */ # undef bn_div_words # define bn_div_words(n0,n1,d0) \ @@ -113,7 +162,6 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) /* * Same story here, but it's 128-bit by 64-bit division. Wow! - * */ # undef bn_div_words # define bn_div_words(n0,n1,d0) \ @@ -140,7 +188,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { - int norm_shift, i, loop; + int norm_shift, i, j, loop; BIGNUM *tmp, wnum, *snum, *sdiv, *res; BN_ULONG *resp, *wnump; BN_ULONG d0, d1; @@ -177,13 +225,13 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, if (BN_is_zero(divisor)) { BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); - return (0); + return 0; } if (!no_branch && BN_ucmp(num, divisor) < 0) { if (rm != NULL) { if (BN_copy(rm, num) == NULL) - return (0); + return 0; } if (dv != NULL) BN_zero(dv); @@ -237,6 +285,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, wnum.neg = 0; wnum.d = &(snum->d[loop]); wnum.top = div_n; + wnum.flags = BN_FLG_STATIC_DATA; /* * only needed when BN_ucmp messes up the values between top and max */ @@ -293,8 +342,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, * the first part of the loop uses the top two words of snum and sdiv * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv */ -# if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) - BN_ULONG bn_div_3_words(BN_ULONG *, BN_ULONG, BN_ULONG); +# if defined(BN_DIV3W) q = bn_div_3_words(wnump, d1, d0); # else BN_ULONG n0, n1, rem = 0; @@ -378,20 +426,22 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, * ingore top values of the bignums just sub the two BN_ULONG arrays * with bn_sub_words */ - if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { - /* - * Note: As we have considered only the leading two BN_ULONGs in - * the calculation of q, sdiv * q might be greater than wnum (but - * then (q-1) * sdiv is less or equal than wnum) - */ - q--; - if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) - /* - * we can't have an overflow here (assuming that q != 0, but - * if q == 0 then tmp is zero anyway) - */ - (*wnump)++; - } + l0 = bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1); + q -= l0; + /* + * Note: As we have considered only the leading two BN_ULONGs in + * the calculation of q, sdiv * q might be greater than wnum (but + * then (q-1) * sdiv is less or equal than wnum) + */ + for (l0 = 0 - l0, j = 0; j < div_n; j++) + tmp->d[j] = sdiv->d[j] & l0; + l0 = bn_add_words(wnum.d, wnum.d, tmp->d, div_n); + /* + * we can't have an overflow here (assuming that q != 0, but + * if q == 0 then tmp is zero anyway) + */ + (*wnump) += l0; + /* store part of the result */ resp--; *resp = q; @@ -415,6 +465,6 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, err: bn_check_top(rm); BN_CTX_end(ctx); - return (0); + return 0; } #endif