Mercurial > dropbear

comparison libtommath/bn_mp_reduce.c @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
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 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 /* reduces x mod m, assumes 0 < x < m**2, mu is 6 /* reduces x mod m, assumes 0 < x < m**2, mu is
19 * precomputed via mp_reduce_setup. 7 * precomputed via mp_reduce_setup.
20 * From HAC pp.604 Algorithm 14.42 8 * From HAC pp.604 Algorithm 14.42
21 */ 9 */
22 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu) 10 mp_err mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu)
23 { 11 {
24 mp_int q; 12 mp_int q;
25 int res, um = m->used; 13 mp_err err;
14 int um = m->used;
26 15
27 /* q = x */ 16 /* q = x */
28 if ((res = mp_init_copy (&q, x)) != MP_OKAY) { 17 if ((err = mp_init_copy(&q, x)) != MP_OKAY) {
29 return res; 18 return err;
30 } 19 }
31 20
32 /* q1 = x / b**(k-1) */ 21 /* q1 = x / b**(k-1) */
33 mp_rshd (&q, um - 1); 22 mp_rshd(&q, um - 1);
34 23
35 /* according to HAC this optimization is ok */ 24 /* according to HAC this optimization is ok */
36 if (((mp_digit) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) { 25 if ((mp_digit)um > ((mp_digit)1 << (MP_DIGIT_BIT - 1))) {
37 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;
36 }
37 } else {
38 err = MP_VAL;
38 goto CLEANUP; 39 goto CLEANUP;
39 } 40 }
40 } else { 41
41 #ifdef BN_S_MP_MUL_HIGH_DIGS_C 42 /* q3 = q2 / b**(k+1) */
42 if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { 43 mp_rshd(&q, um + 1);
44
45 /* x = x mod b**(k+1), quick (no division) */
46 if ((err = mp_mod_2d(x, MP_DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
43 goto CLEANUP; 47 goto CLEANUP;
44 } 48 }
45 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C) 49
46 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { 50 /* q = q * m mod b**(k+1), quick (no division) */
51 if ((err = s_mp_mul_digs(&q, m, &q, um + 1)) != MP_OKAY) {
47 goto CLEANUP; 52 goto CLEANUP;
48 } 53 }
49 #else 54
50 { 55 /* x = x - q */
51 res = MP_VAL; 56 if ((err = mp_sub(x, &q, x)) != MP_OKAY) {
52 goto CLEANUP; 57 goto CLEANUP;
53 } 58 }
54 #endif
55 }
56 59
57 /* q3 = q2 / b**(k+1) */ 60 /* If x < 0, add b**(k+1) to it */
58 mp_rshd (&q, um + 1); 61 if (mp_cmp_d(x, 0uL) == MP_LT) {
62 mp_set(&q, 1uL);
63 if ((err = mp_lshd(&q, um + 1)) != MP_OKAY) {
64 goto CLEANUP;
65 }
66 if ((err = mp_add(x, &q, x)) != MP_OKAY) {
67 goto CLEANUP;
68 }
69 }
59 70
60 /* x = x mod b**(k+1), quick (no division) */ 71 /* Back off if it's too big */
61 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { 72 while (mp_cmp(x, m) != MP_LT) {
62 goto CLEANUP; 73 if ((err = s_mp_sub(x, m, x)) != MP_OKAY) {
63 } 74 goto CLEANUP;
64 75 }
65 /* q = q * m mod b**(k+1), quick (no division) */ 76 }
66 if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
67 goto CLEANUP;
68 }
69
70 /* x = x - q */
71 if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
72 goto CLEANUP;
73 }
74
75 /* If x < 0, add b**(k+1) to it */
76 if (mp_cmp_d (x, 0) == MP_LT) {
77 mp_set (&q, 1);
78 if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
79 goto CLEANUP;
80 if ((res = mp_add (x, &q, x)) != MP_OKAY)
81 goto CLEANUP;
82 }
83
84 /* Back off if it's too big */
85 while (mp_cmp (x, m) != MP_LT) {
86 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
87 goto CLEANUP;
88 }
89 }
90 77
91 CLEANUP: 78 CLEANUP:
92 mp_clear (&q); 79 mp_clear(&q);
93 80
94 return res; 81 return err;
95 } 82 }
96 #endif 83 #endif
97
98 /* ref: $Format:%D$ */
99 /* git commit: $Format:%H$ */
100 /* commit time: $Format:%ai$ */