Mercurial > dropbear

comparison libtommath/bn_fast_mp_montgomery_reduce.c @ 1436:60fc6476e044

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtommath v1.0
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 22:37:14 +0800
parents 5ff8218bcee9
children 8bba51a55704
comparison
equal deleted inserted replaced
1435:f849a5ca2efc 1436:60fc6476e044
1 #include <tommath.h> 1 #include <tommath_private.h>
2 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C 2 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
13 * guarantee it works. 13 * guarantee it works.
14 * 14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com 15 * Tom St Denis, [email protected], http://libtom.org
16 */ 16 */
17 17
18 /* computes xR**-1 == x (mod N) via Montgomery Reduction 18 /* computes xR**-1 == x (mod N) via Montgomery Reduction
19 * 19 *
20 * This is an optimized implementation of montgomery_reduce 20 * This is an optimized implementation of montgomery_reduce
30 30
31 /* get old used count */ 31 /* get old used count */
32 olduse = x->used; 32 olduse = x->used;
33 33
34 /* grow a as required */ 34 /* grow a as required */
35 if (x->alloc < n->used + 1) { 35 if (x->alloc < (n->used + 1)) {
36 if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) { 36 if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) {
37 return res; 37 return res;
38 } 38 }
39 } 39 }
40 40
41 /* first we have to get the digits of the input into 41 /* first we have to get the digits of the input into
42 * an array of double precision words W[...] 42 * an array of double precision words W[...]
43 */ 43 */
44 { 44 {
45 register mp_word *_W; 45 mp_word *_W;
46 register mp_digit *tmpx; 46 mp_digit *tmpx;
47 47
48 /* alias for the W[] array */ 48 /* alias for the W[] array */
49 _W = W; 49 _W = W;
50 50
51 /* alias for the digits of x*/ 51 /* alias for the digits of x*/
55 for (ix = 0; ix < x->used; ix++) { 55 for (ix = 0; ix < x->used; ix++) {
56 *_W++ = *tmpx++; 56 *_W++ = *tmpx++;
57 } 57 }
58 58
59 /* zero the high words of W[a->used..m->used*2] */ 59 /* zero the high words of W[a->used..m->used*2] */
60 for (; ix < n->used * 2 + 1; ix++) { 60 for (; ix < ((n->used * 2) + 1); ix++) {
61 *_W++ = 0; 61 *_W++ = 0;
62 } 62 }
63 } 63 }
64 64
65 /* now we proceed to zero successive digits 65 /* now we proceed to zero successive digits
70 * 70 *
71 * We avoid a double precision multiplication (which isn't required) 71 * We avoid a double precision multiplication (which isn't required)
72 * by casting the value down to a mp_digit. Note this requires 72 * by casting the value down to a mp_digit. Note this requires
73 * that W[ix-1] have the carry cleared (see after the inner loop) 73 * that W[ix-1] have the carry cleared (see after the inner loop)
74 */ 74 */
75 register mp_digit mu; 75 mp_digit mu;
76 mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK); 76 mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK);
77 77
78 /* a = a + mu * m * b**i 78 /* a = a + mu * m * b**i
79 * 79 *
80 * This is computed in place and on the fly. The multiplication 80 * This is computed in place and on the fly. The multiplication
88 * handled by fixing up one carry after the inner loop. The 88 * handled by fixing up one carry after the inner loop. The
89 * carry fixups are done in order so after these loops the 89 * carry fixups are done in order so after these loops the
90 * first m->used words of W[] have the carries fixed 90 * first m->used words of W[] have the carries fixed
91 */ 91 */
92 { 92 {
93 register int iy; 93 int iy;
94 register mp_digit *tmpn; 94 mp_digit *tmpn;
95 register mp_word *_W; 95 mp_word *_W;
96 96
97 /* alias for the digits of the modulus */ 97 /* alias for the digits of the modulus */
98 tmpn = n->dp; 98 tmpn = n->dp;
99 99
100 /* Alias for the columns set by an offset of ix */ 100 /* Alias for the columns set by an offset of ix */
113 /* now we have to propagate the carries and 113 /* now we have to propagate the carries and
114 * shift the words downward [all those least 114 * shift the words downward [all those least
115 * significant digits we zeroed]. 115 * significant digits we zeroed].
116 */ 116 */
117 { 117 {
118 register mp_digit *tmpx; 118 mp_digit *tmpx;
119 register mp_word *_W, *_W1; 119 mp_word *_W, *_W1;
120 120
121 /* nox fix rest of carries */ 121 /* nox fix rest of carries */
122 122
123 /* alias for current word */ 123 /* alias for current word */
124 _W1 = W + ix; 124 _W1 = W + ix;
125 125
126 /* alias for next word, where the carry goes */ 126 /* alias for next word, where the carry goes */
127 _W = W + ++ix; 127 _W = W + ++ix;
128 128
129 for (; ix <= n->used * 2 + 1; ix++) { 129 for (; ix <= ((n->used * 2) + 1); ix++) {
130 *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT); 130 *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT);
131 } 131 }
132 132
133 /* copy out, A = A/b**n 133 /* copy out, A = A/b**n
134 * 134 *
141 tmpx = x->dp; 141 tmpx = x->dp;
142 142
143 /* alias for shifted double precision result */ 143 /* alias for shifted double precision result */
144 _W = W + n->used; 144 _W = W + n->used;
145 145
146 for (ix = 0; ix < n->used + 1; ix++) { 146 for (ix = 0; ix < (n->used + 1); ix++) {
147 *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK)); 147 *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK));
148 } 148 }
149 149
150 /* zero oldused digits, if the input a was larger than 150 /* zero oldused digits, if the input a was larger than
151 * m->used+1 we'll have to clear the digits 151 * m->used+1 we'll have to clear the digits
165 } 165 }
166 return MP_OKAY; 166 return MP_OKAY;
167 } 167 }
168 #endif 168 #endif
169 169
170 /* $Source: /cvs/libtom/libtommath/bn_fast_mp_montgomery_reduce.c,v $ */ 170 /* $Source$ */
171 /* $Revision: 1.3 $ */ 171 /* $Revision$ */
172 /* $Date: 2006/03/31 14:18:44 $ */ 172 /* $Date$ */