Mercurial > dropbear
comparison libtommath/bn_mp_dr_reduce.c @ 1436:60fc6476e044
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_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 * |
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 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. | 18 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. |
19 * | 19 * |
20 * Based on algorithm from the paper | 20 * Based on algorithm from the paper |
38 | 38 |
39 /* m = digits in modulus */ | 39 /* m = digits in modulus */ |
40 m = n->used; | 40 m = n->used; |
41 | 41 |
42 /* ensure that "x" has at least 2m digits */ | 42 /* ensure that "x" has at least 2m digits */ |
43 if (x->alloc < m + m) { | 43 if (x->alloc < (m + m)) { |
44 if ((err = mp_grow (x, m + m)) != MP_OKAY) { | 44 if ((err = mp_grow (x, m + m)) != MP_OKAY) { |
45 return err; | 45 return err; |
46 } | 46 } |
47 } | 47 } |
48 | 48 |
60 /* set carry to zero */ | 60 /* set carry to zero */ |
61 mu = 0; | 61 mu = 0; |
62 | 62 |
63 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ | 63 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ |
64 for (i = 0; i < m; i++) { | 64 for (i = 0; i < m; i++) { |
65 r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu; | 65 r = (((mp_word)*tmpx2++) * (mp_word)k) + *tmpx1 + mu; |
66 *tmpx1++ = (mp_digit)(r & MP_MASK); | 66 *tmpx1++ = (mp_digit)(r & MP_MASK); |
67 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); | 67 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); |
68 } | 68 } |
69 | 69 |
70 /* set final carry */ | 70 /* set final carry */ |
80 | 80 |
81 /* if x >= n then subtract and reduce again | 81 /* if x >= n then subtract and reduce again |
82 * Each successive "recursion" makes the input smaller and smaller. | 82 * Each successive "recursion" makes the input smaller and smaller. |
83 */ | 83 */ |
84 if (mp_cmp_mag (x, n) != MP_LT) { | 84 if (mp_cmp_mag (x, n) != MP_LT) { |
85 s_mp_sub(x, n, x); | 85 if ((err = s_mp_sub(x, n, x)) != MP_OKAY) { |
86 return err; | |
87 } | |
86 goto top; | 88 goto top; |
87 } | 89 } |
88 return MP_OKAY; | 90 return MP_OKAY; |
89 } | 91 } |
90 #endif | 92 #endif |
91 | 93 |
92 /* $Source: /cvs/libtom/libtommath/bn_mp_dr_reduce.c,v $ */ | 94 /* $Source$ */ |
93 /* $Revision: 1.3 $ */ | 95 /* $Revision$ */ |
94 /* $Date: 2006/03/31 14:18:44 $ */ | 96 /* $Date$ */ |