Mercurial > dropbear
comparison libtommath/bn_mp_reduce.c @ 1692:1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
* update C files
* update other files
* update headers
* update makefiles
* remove mp_set/get_double()
* use ltm 1.2.0 API
* update ltm_desc
* use bundled tommath if system-tommath is too old
* XMALLOC etc. were changed to MP_MALLOC etc.
author | Steffen Jaeckel <s@jaeckel.eu> |
---|---|
date | Tue, 26 May 2020 17:36:47 +0200 |
parents | f52919ffd3b1 |
children |
comparison
equal
deleted
inserted
replaced
1691:2d3745d58843 | 1692:1051e4eea25a |
---|---|
1 #include "tommath_private.h" | 1 #include "tommath_private.h" |
2 #ifdef BN_MP_REDUCE_C | 2 #ifdef BN_MP_REDUCE_C |
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 * | 4 /* SPDX-License-Identifier: Unlicense */ |
5 * LibTomMath is a library that provides multiple-precision | |
6 * integer arithmetic as well as number theoretic functionality. | |
7 * | |
8 * The library was designed directly after the MPI library by | |
9 * Michael Fromberger but has been written from scratch with | |
10 * additional optimizations in place. | |
11 * | |
12 * SPDX-License-Identifier: Unlicense | |
13 */ | |
14 | 5 |
15 /* reduces x mod m, assumes 0 < x < m**2, mu is | 6 /* reduces x mod m, assumes 0 < x < m**2, mu is |
16 * precomputed via mp_reduce_setup. | 7 * precomputed via mp_reduce_setup. |
17 * From HAC pp.604 Algorithm 14.42 | 8 * From HAC pp.604 Algorithm 14.42 |
18 */ | 9 */ |
19 int mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu) | 10 mp_err mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu) |
20 { | 11 { |
21 mp_int q; | 12 mp_int q; |
22 int res, um = m->used; | 13 mp_err err; |
14 int um = m->used; | |
23 | 15 |
24 /* q = x */ | 16 /* q = x */ |
25 if ((res = mp_init_copy(&q, x)) != MP_OKAY) { | 17 if ((err = mp_init_copy(&q, x)) != MP_OKAY) { |
26 return res; | 18 return err; |
27 } | 19 } |
28 | 20 |
29 /* q1 = x / b**(k-1) */ | 21 /* q1 = x / b**(k-1) */ |
30 mp_rshd(&q, um - 1); | 22 mp_rshd(&q, um - 1); |
31 | 23 |
32 /* according to HAC this optimization is ok */ | 24 /* according to HAC this optimization is ok */ |
33 if ((mp_digit)um > ((mp_digit)1 << (DIGIT_BIT - 1))) { | 25 if ((mp_digit)um > ((mp_digit)1 << (MP_DIGIT_BIT - 1))) { |
34 if ((res = mp_mul(&q, mu, &q)) != MP_OKAY) { | 26 if ((err = mp_mul(&q, mu, &q)) != MP_OKAY) { |
27 goto CLEANUP; | |
28 } | |
29 } else if (MP_HAS(S_MP_MUL_HIGH_DIGS)) { | |
30 if ((err = s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { | |
31 goto CLEANUP; | |
32 } | |
33 } else if (MP_HAS(S_MP_MUL_HIGH_DIGS_FAST)) { | |
34 if ((err = s_mp_mul_high_digs_fast(&q, mu, &q, um)) != MP_OKAY) { | |
35 goto CLEANUP; | 35 goto CLEANUP; |
36 } | 36 } |
37 } else { | 37 } else { |
38 #ifdef BN_S_MP_MUL_HIGH_DIGS_C | 38 err = MP_VAL; |
39 if ((res = s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { | 39 goto CLEANUP; |
40 goto CLEANUP; | |
41 } | |
42 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C) | |
43 if ((res = fast_s_mp_mul_high_digs(&q, mu, &q, um)) != MP_OKAY) { | |
44 goto CLEANUP; | |
45 } | |
46 #else | |
47 { | |
48 res = MP_VAL; | |
49 goto CLEANUP; | |
50 } | |
51 #endif | |
52 } | 40 } |
53 | 41 |
54 /* q3 = q2 / b**(k+1) */ | 42 /* q3 = q2 / b**(k+1) */ |
55 mp_rshd(&q, um + 1); | 43 mp_rshd(&q, um + 1); |
56 | 44 |
57 /* x = x mod b**(k+1), quick (no division) */ | 45 /* x = x mod b**(k+1), quick (no division) */ |
58 if ((res = mp_mod_2d(x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { | 46 if ((err = mp_mod_2d(x, MP_DIGIT_BIT * (um + 1), x)) != MP_OKAY) { |
59 goto CLEANUP; | 47 goto CLEANUP; |
60 } | 48 } |
61 | 49 |
62 /* q = q * m mod b**(k+1), quick (no division) */ | 50 /* q = q * m mod b**(k+1), quick (no division) */ |
63 if ((res = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) { | 51 if ((err = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) { |
64 goto CLEANUP; | 52 goto CLEANUP; |
65 } | 53 } |
66 | 54 |
67 /* x = x - q */ | 55 /* x = x - q */ |
68 if ((res = mp_sub(x, &q, x)) != MP_OKAY) { | 56 if ((err = mp_sub(x, &q, x)) != MP_OKAY) { |
69 goto CLEANUP; | 57 goto CLEANUP; |
70 } | 58 } |
71 | 59 |
72 /* If x < 0, add b**(k+1) to it */ | 60 /* If x < 0, add b**(k+1) to it */ |
73 if (mp_cmp_d(x, 0uL) == MP_LT) { | 61 if (mp_cmp_d(x, 0uL) == MP_LT) { |
74 mp_set(&q, 1uL); | 62 mp_set(&q, 1uL); |
75 if ((res = mp_lshd(&q, um + 1)) != MP_OKAY) | 63 if ((err = mp_lshd(&q, um + 1)) != MP_OKAY) { |
76 goto CLEANUP; | 64 goto CLEANUP; |
77 if ((res = mp_add(x, &q, x)) != MP_OKAY) | 65 } |
66 if ((err = mp_add(x, &q, x)) != MP_OKAY) { | |
78 goto CLEANUP; | 67 goto CLEANUP; |
68 } | |
79 } | 69 } |
80 | 70 |
81 /* Back off if it's too big */ | 71 /* Back off if it's too big */ |
82 while (mp_cmp(x, m) != MP_LT) { | 72 while (mp_cmp(x, m) != MP_LT) { |
83 if ((res = s_mp_sub(x, m, x)) != MP_OKAY) { | 73 if ((err = s_mp_sub(x, m, x)) != MP_OKAY) { |
84 goto CLEANUP; | 74 goto CLEANUP; |
85 } | 75 } |
86 } | 76 } |
87 | 77 |
88 CLEANUP: | 78 CLEANUP: |
89 mp_clear(&q); | 79 mp_clear(&q); |
90 | 80 |
91 return res; | 81 return err; |
92 } | 82 } |
93 #endif | 83 #endif |
94 | |
95 /* ref: HEAD -> master, tag: v1.1.0 */ | |
96 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ | |
97 /* commit time: 2019-01-28 20:32:32 +0100 */ |