diff options
Diffstat (limited to 'libtommath/bn_mp_reduce.c')
| -rw-r--r-- | libtommath/bn_mp_reduce.c | 125 |
1 files changed, 61 insertions, 64 deletions
diff --git a/libtommath/bn_mp_reduce.c b/libtommath/bn_mp_reduce.c index 367383f..9cb9d2a 100644 --- a/libtommath/bn_mp_reduce.c +++ b/libtommath/bn_mp_reduce.c @@ -1,4 +1,4 @@ -#include <tommath_private.h> +#include "tommath_private.h" #ifdef BN_MP_REDUCE_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * @@ -9,92 +9,89 @@ * Michael Fromberger but has been written from scratch with * additional optimizations in place. * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tstdenis82@gmail.com, http://libtom.org + * SPDX-License-Identifier: Unlicense */ /* reduces x mod m, assumes 0 < x < m**2, mu is * precomputed via mp_reduce_setup. * From HAC pp.604 Algorithm 14.42 */ -int mp_reduce (mp_int * x, mp_int * m, mp_int * mu) +int mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu) { - mp_int q; - int res, um = m->used; + mp_int q; + int res, um = m->used; - /* q = x */ - if ((res = mp_init_copy (&q, x)) != MP_OKAY) { - return res; - } + /* q = x */ + if ((res = mp_init_copy(&q, x)) != MP_OKAY) { + return res; + } - /* q1 = x / b**(k-1) */ - mp_rshd (&q, um - 1); + /* q1 = x / b**(k-1) */ + mp_rshd(&q, um - 1); - /* according to HAC this optimization is ok */ - if (((mp_digit) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) { - if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) { - goto CLEANUP; - } - } else { + /* according to HAC this optimization is ok */ + if ((mp_digit)um > ((mp_digit)1 << (DIGIT_BIT - 1))) { + if ((res = mp_mul(&q, mu, &q)) != MP_OKAY) { + goto CLEANUP; + } + } else { #ifdef BN_S_MP_MUL_HIGH_DIGS_C - if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { - goto CLEANUP; - } + if ((res = s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { + goto CLEANUP; + } #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C) - if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { - goto CLEANUP; - } + if ((res = fast_s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { + goto CLEANUP; + } #else - { - res = MP_VAL; - goto CLEANUP; - } + { + res = MP_VAL; + goto CLEANUP; + } #endif - } - - /* q3 = q2 / b**(k+1) */ - mp_rshd (&q, um + 1); + } - /* x = x mod b**(k+1), quick (no division) */ - if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { - goto CLEANUP; - } + /* q3 = q2 / b**(k+1) */ + mp_rshd(&q, um + 1); - /* q = q * m mod b**(k+1), quick (no division) */ - if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) { - goto CLEANUP; - } - - /* x = x - q */ - if ((res = mp_sub (x, &q, x)) != MP_OKAY) { - goto CLEANUP; - } - - /* If x < 0, add b**(k+1) to it */ - if (mp_cmp_d (x, 0) == MP_LT) { - mp_set (&q, 1); - if ((res = mp_lshd (&q, um + 1)) != MP_OKAY) + /* x = x mod b**(k+1), quick (no division) */ + if ((res = mp_mod_2d(x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { goto CLEANUP; - if ((res = mp_add (x, &q, x)) != MP_OKAY) + } + + /* q = q * m mod b**(k+1), quick (no division) */ + if ((res = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) { goto CLEANUP; - } + } - /* Back off if it's too big */ - while (mp_cmp (x, m) != MP_LT) { - if ((res = s_mp_sub (x, m, x)) != MP_OKAY) { + /* x = x - q */ + if ((res = mp_sub(x, &q, x)) != MP_OKAY) { goto CLEANUP; - } - } + } + + /* If x < 0, add b**(k+1) to it */ + if (mp_cmp_d(x, 0uL) == MP_LT) { + mp_set(&q, 1uL); + if ((res = mp_lshd(&q, um + 1)) != MP_OKAY) + goto CLEANUP; + if ((res = mp_add(x, &q, x)) != MP_OKAY) + goto CLEANUP; + } + + /* Back off if it's too big */ + while (mp_cmp(x, m) != MP_LT) { + if ((res = s_mp_sub(x, m, x)) != MP_OKAY) { + goto CLEANUP; + } + } CLEANUP: - mp_clear (&q); + mp_clear(&q); - return res; + return res; } #endif -/* ref: $Format:%D$ */ -/* git commit: $Format:%H$ */ -/* commit time: $Format:%ai$ */ +/* ref: HEAD -> master, tag: v1.1.0 */ +/* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ +/* commit time: 2019-01-28 20:32:32 +0100 */ |