/src/dropbear/libtommath/bn_mp_reduce_2k_l.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_REDUCE_2K_L_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 | | This differs from reduce_2k since "d" can be larger |
8 | | than a single digit. |
9 | | */ |
10 | | mp_err mp_reduce_2k_l(mp_int *a, const mp_int *n, const mp_int *d) |
11 | 45.8k | { |
12 | 45.8k | mp_int q; |
13 | 45.8k | mp_err err; |
14 | 45.8k | int p; |
15 | | |
16 | 45.8k | if ((err = mp_init(&q)) != MP_OKAY) { |
17 | 0 | return err; |
18 | 0 | } |
19 | | |
20 | 45.8k | p = mp_count_bits(n); |
21 | 8.03M | top: |
22 | | /* q = a/2**p, a = a mod 2**p */ |
23 | 8.03M | if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) { |
24 | 0 | goto LBL_ERR; |
25 | 0 | } |
26 | | |
27 | | /* q = q * d */ |
28 | 8.03M | if ((err = mp_mul(&q, d, &q)) != MP_OKAY) { |
29 | 0 | goto LBL_ERR; |
30 | 0 | } |
31 | | |
32 | | /* a = a + q */ |
33 | 8.03M | if ((err = s_mp_add(a, &q, a)) != MP_OKAY) { |
34 | 0 | goto LBL_ERR; |
35 | 0 | } |
36 | | |
37 | 8.03M | if (mp_cmp_mag(a, n) != MP_LT) { |
38 | 7.99M | if ((err = s_mp_sub(a, n, a)) != MP_OKAY) { |
39 | 0 | goto LBL_ERR; |
40 | 0 | } |
41 | 7.99M | goto top; |
42 | 7.99M | } |
43 | | |
44 | 45.8k | LBL_ERR: |
45 | 45.8k | mp_clear(&q); |
46 | 45.8k | return err; |
47 | 8.03M | } |
48 | | |
49 | | #endif |