Mercurial > dropbear

comparison libtommath/bn_mp_dr_reduce.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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_DR_REDUCE_C 2 #ifdef BN_MP_DR_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 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. 6 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
16 * 7 *
17 * Based on algorithm from the paper 8 * Based on algorithm from the paper
18 * 9 *
24 * 15 *
25 * Has been modified to use algorithm 7.10 from the LTM book instead 16 * Has been modified to use algorithm 7.10 from the LTM book instead
26 * 17 *
27 * Input x must be in the range 0 <= x <= (n-1)**2 18 * Input x must be in the range 0 <= x <= (n-1)**2
28 */ 19 */
29 int mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k) 20 mp_err mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k)
30 { 21 {
31 int err, i, m; 22 mp_err err;
23 int i, m;
32 mp_word r; 24 mp_word r;
33 mp_digit mu, *tmpx1, *tmpx2; 25 mp_digit mu, *tmpx1, *tmpx2;
34 26
35 /* m = digits in modulus */ 27 /* m = digits in modulus */
36 m = n->used; 28 m = n->used;
58 50
59 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ 51 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
60 for (i = 0; i < m; i++) { 52 for (i = 0; i < m; i++) {
61 r = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu; 53 r = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu;
62 *tmpx1++ = (mp_digit)(r & MP_MASK); 54 *tmpx1++ = (mp_digit)(r & MP_MASK);
63 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); 55 mu = (mp_digit)(r >> ((mp_word)MP_DIGIT_BIT));
64 } 56 }
65 57
66 /* set final carry */ 58 /* set final carry */
67 *tmpx1++ = mu; 59 *tmpx1++ = mu;
68 60
69 /* zero words above m */ 61 /* zero words above m */
70 for (i = m + 1; i < x->used; i++) { 62 MP_ZERO_DIGITS(tmpx1, (x->used - m) - 1);
71 *tmpx1++ = 0;
72 }
73 63
74 /* clamp, sub and return */ 64 /* clamp, sub and return */
75 mp_clamp(x); 65 mp_clamp(x);
76 66
77 /* if x >= n then subtract and reduce again 67 /* if x >= n then subtract and reduce again
84 goto top; 74 goto top;
85 } 75 }
86 return MP_OKAY; 76 return MP_OKAY;
87 } 77 }
88 #endif 78 #endif
89
90 /* ref: HEAD -> master, tag: v1.1.0 */
91 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
92 /* commit time: 2019-01-28 20:32:32 +0100 */