Mercurial > dropbear

comparison libtommath/bn_mp_dr_reduce.c @ 1733:d529a52b2f7c coverity coverity

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge coverity from main
author Matt Johnston <matt@ucc.asn.au>
date Fri, 26 Jun 2020 21:07:34 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1643:b59623a64678 1733:d529a52b2f7c
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 * 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 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. 6 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
19 * 7 *
20 * Based on algorithm from the paper 8 * Based on algorithm from the paper
21 * 9 *
27 * 15 *
28 * 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
29 * 17 *
30 * 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
31 */ 19 */
32 int 20 mp_err mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k)
33 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
34 { 21 {
35 int err, i, m; 22 mp_err err;
36 mp_word r; 23 int i, m;
37 mp_digit mu, *tmpx1, *tmpx2; 24 mp_word r;
25 mp_digit mu, *tmpx1, *tmpx2;
38 26
39 /* m = digits in modulus */ 27 /* m = digits in modulus */
40 m = n->used; 28 m = n->used;
41 29
42 /* ensure that "x" has at least 2m digits */ 30 /* ensure that "x" has at least 2m digits */
43 if (x->alloc < (m + m)) { 31 if (x->alloc < (m + m)) {
44 if ((err = mp_grow (x, m + m)) != MP_OKAY) { 32 if ((err = mp_grow(x, m + m)) != MP_OKAY) {
45 return err; 33 return err;
46 } 34 }
47 } 35 }
48 36
49 /* top of loop, this is where the code resumes if 37 /* top of loop, this is where the code resumes if
50 * another reduction pass is required. 38 * another reduction pass is required.
51 */ 39 */
52 top: 40 top:
53 /* aliases for digits */ 41 /* aliases for digits */
54 /* alias for lower half of x */ 42 /* alias for lower half of x */
55 tmpx1 = x->dp; 43 tmpx1 = x->dp;
56 44
57 /* alias for upper half of x, or x/B**m */ 45 /* alias for upper half of x, or x/B**m */
58 tmpx2 = x->dp + m; 46 tmpx2 = x->dp + m;
59 47
60 /* set carry to zero */ 48 /* set carry to zero */
61 mu = 0; 49 mu = 0;
62 50
63 /* 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 */
64 for (i = 0; i < m; i++) { 52 for (i = 0; i < m; i++) {
65 r = (((mp_word)*tmpx2++) * (mp_word)k) + *tmpx1 + mu; 53 r = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu;
66 *tmpx1++ = (mp_digit)(r & MP_MASK); 54 *tmpx1++ = (mp_digit)(r & MP_MASK);
67 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); 55 mu = (mp_digit)(r >> ((mp_word)MP_DIGIT_BIT));
68 } 56 }
69 57
70 /* set final carry */ 58 /* set final carry */
71 *tmpx1++ = mu; 59 *tmpx1++ = mu;
72 60
73 /* zero words above m */ 61 /* zero words above m */
74 for (i = m + 1; i < x->used; i++) { 62 MP_ZERO_DIGITS(tmpx1, (x->used - m) - 1);
75 *tmpx1++ = 0;
76 }
77 63
78 /* clamp, sub and return */ 64 /* clamp, sub and return */
79 mp_clamp (x); 65 mp_clamp(x);
80 66
81 /* if x >= n then subtract and reduce again 67 /* if x >= n then subtract and reduce again
82 * Each successive "recursion" makes the input smaller and smaller. 68 * Each successive "recursion" makes the input smaller and smaller.
83 */ 69 */
84 if (mp_cmp_mag (x, n) != MP_LT) { 70 if (mp_cmp_mag(x, n) != MP_LT) {
85 if ((err = s_mp_sub(x, n, x)) != MP_OKAY) { 71 if ((err = s_mp_sub(x, n, x)) != MP_OKAY) {
86 return err; 72 return err;
87 } 73 }
88 goto top; 74 goto top;
89 } 75 }
90 return MP_OKAY; 76 return MP_OKAY;
91 } 77 }
92 #endif 78 #endif
93
94 /* ref: $Format:%D$ */
95 /* git commit: $Format:%H$ */
96 /* commit time: $Format:%ai$ */