/src/dropbear/libtommath/bn_mp_reduce.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_REDUCE_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* reduces x mod m, assumes 0 < x < m**2, mu is |
7 | | * precomputed via mp_reduce_setup. |
8 | | * From HAC pp.604 Algorithm 14.42 |
9 | | */ |
10 | | mp_err mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu) |
11 | 77.7k | { |
12 | 77.7k | mp_int q; |
13 | 77.7k | mp_err err; |
14 | 77.7k | int um = m->used; |
15 | | |
16 | | /* q = x */ |
17 | 77.7k | if ((err = mp_init_copy(&q, x)) != MP_OKAY) { |
18 | 0 | return err; |
19 | 0 | } |
20 | | |
21 | | /* q1 = x / b**(k-1) */ |
22 | 77.7k | mp_rshd(&q, um - 1); |
23 | | |
24 | | /* according to HAC this optimization is ok */ |
25 | 77.7k | if ((mp_digit)um > ((mp_digit)1 << (MP_DIGIT_BIT - 1))) { |
26 | 0 | if ((err = mp_mul(&q, mu, &q)) != MP_OKAY) { |
27 | 0 | goto CLEANUP; |
28 | 0 | } |
29 | 77.7k | } else if (MP_HAS(S_MP_MUL_HIGH_DIGS)) { |
30 | 77.7k | if ((err = s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { |
31 | 0 | goto CLEANUP; |
32 | 0 | } |
33 | 77.7k | } else if (MP_HAS(S_MP_MUL_HIGH_DIGS_FAST)) { |
34 | 0 | if ((err = s_mp_mul_high_digs_fast(&q, mu, &q, um)) != MP_OKAY) { |
35 | 0 | goto CLEANUP; |
36 | 0 | } |
37 | 0 | } else { |
38 | 0 | err = MP_VAL; |
39 | 0 | goto CLEANUP; |
40 | 0 | } |
41 | | |
42 | | /* q3 = q2 / b**(k+1) */ |
43 | 77.7k | mp_rshd(&q, um + 1); |
44 | | |
45 | | /* x = x mod b**(k+1), quick (no division) */ |
46 | 77.7k | if ((err = mp_mod_2d(x, MP_DIGIT_BIT * (um + 1), x)) != MP_OKAY) { |
47 | 0 | goto CLEANUP; |
48 | 0 | } |
49 | | |
50 | | /* q = q * m mod b**(k+1), quick (no division) */ |
51 | 77.7k | if ((err = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) { |
52 | 0 | goto CLEANUP; |
53 | 0 | } |
54 | | |
55 | | /* x = x - q */ |
56 | 77.7k | if ((err = mp_sub(x, &q, x)) != MP_OKAY) { |
57 | 0 | goto CLEANUP; |
58 | 0 | } |
59 | | |
60 | | /* If x < 0, add b**(k+1) to it */ |
61 | 77.7k | if (mp_cmp_d(x, 0uL) == MP_LT) { |
62 | 8.50k | mp_set(&q, 1uL); |
63 | 8.50k | if ((err = mp_lshd(&q, um + 1)) != MP_OKAY) { |
64 | 0 | goto CLEANUP; |
65 | 0 | } |
66 | 8.50k | if ((err = mp_add(x, &q, x)) != MP_OKAY) { |
67 | 0 | goto CLEANUP; |
68 | 0 | } |
69 | 8.50k | } |
70 | | |
71 | | /* Back off if it's too big */ |
72 | 175k | while (mp_cmp(x, m) != MP_LT) { |
73 | 98.0k | if ((err = s_mp_sub(x, m, x)) != MP_OKAY) { |
74 | 0 | goto CLEANUP; |
75 | 0 | } |
76 | 98.0k | } |
77 | | |
78 | 77.7k | CLEANUP: |
79 | 77.7k | mp_clear(&q); |
80 | | |
81 | 77.7k | return err; |
82 | 77.7k | } |
83 | | #endif |