/src/dropbear/libtommath/bn_mp_reduce_2k.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_REDUCE_2K_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* reduces a modulo n where n is of the form 2**p - d */ |
7 | | mp_err mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d) |
8 | 0 | { |
9 | 0 | mp_int q; |
10 | 0 | mp_err err; |
11 | 0 | int p; |
12 | |
|
13 | 0 | if ((err = mp_init(&q)) != MP_OKAY) { |
14 | 0 | return err; |
15 | 0 | } |
16 | | |
17 | 0 | p = mp_count_bits(n); |
18 | 0 | top: |
19 | | /* q = a/2**p, a = a mod 2**p */ |
20 | 0 | if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) { |
21 | 0 | goto LBL_ERR; |
22 | 0 | } |
23 | | |
24 | 0 | if (d != 1u) { |
25 | | /* q = q * d */ |
26 | 0 | if ((err = mp_mul_d(&q, d, &q)) != MP_OKAY) { |
27 | 0 | goto LBL_ERR; |
28 | 0 | } |
29 | 0 | } |
30 | | |
31 | | /* a = a + q */ |
32 | 0 | if ((err = s_mp_add(a, &q, a)) != MP_OKAY) { |
33 | 0 | goto LBL_ERR; |
34 | 0 | } |
35 | | |
36 | 0 | if (mp_cmp_mag(a, n) != MP_LT) { |
37 | 0 | if ((err = s_mp_sub(a, n, a)) != MP_OKAY) { |
38 | 0 | goto LBL_ERR; |
39 | 0 | } |
40 | 0 | goto top; |
41 | 0 | } |
42 | | |
43 | 0 | LBL_ERR: |
44 | 0 | mp_clear(&q); |
45 | 0 | return err; |
46 | 0 | } |
47 | | |
48 | | #endif |