Mercurial > dropbear

comparison bn_fast_s_mp_mul_high_digs.c @ 142:d29b64170cf0 libtommath-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children d8254fc979e9
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
1 #include <tommath.h>
2 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 * 4 *
3 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
5 * 7 *
10 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
11 * guarantee it works. 13 * guarantee it works.
12 * 14 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */ 16 */
15 #include <tommath.h>
16 17
17 /* this is a modified version of fast_s_mp_mul_digs that only produces 18 /* this is a modified version of fast_s_mul_digs that only produces
18 * output digits *above* digs. See the comments for fast_s_mp_mul_digs 19 * output digits *above* digs. See the comments for fast_s_mul_digs
19 * to see how it works. 20 * to see how it works.
20 * 21 *
21 * This is used in the Barrett reduction since for one of the multiplications 22 * This is used in the Barrett reduction since for one of the multiplications
22 * only the higher digits were needed. This essentially halves the work. 23 * only the higher digits were needed. This essentially halves the work.
23 * 24 *
24 * Based on Algorithm 14.12 on pp.595 of HAC. 25 * Based on Algorithm 14.12 on pp.595 of HAC.
25 */ 26 */
26 int 27 int
27 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 28 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
28 { 29 {
29 int oldused, newused, res, pa, pb, ix; 30 int olduse, res, pa, ix, iz;
30 mp_word W[MP_WARRAY]; 31 mp_digit W[MP_WARRAY];
32 mp_word _W;
31 33
32 /* calculate size of product and allocate more space if required */ 34 /* grow the destination as required */
33 newused = a->used + b->used + 1; 35 pa = a->used + b->used;
34 if (c->alloc < newused) { 36 if (c->alloc < pa) {
35 if ((res = mp_grow (c, newused)) != MP_OKAY) { 37 if ((res = mp_grow (c, pa)) != MP_OKAY) {
36 return res; 38 return res;
37 } 39 }
38 } 40 }
39 41
40 /* like the other comba method we compute the columns first */ 42 /* number of output digits to produce */
41 pa = a->used; 43 pa = a->used + b->used;
42 pb = b->used; 44 _W = 0;
43 memset (W + digs, 0, (pa + pb + 1 - digs) * sizeof (mp_word)); 45 for (ix = digs; ix <= pa; ix++) {
44 for (ix = 0; ix < pa; ix++) { 46 int tx, ty, iy;
45 { 47 mp_digit *tmpx, *tmpy;
46 register mp_digit tmpx, *tmpy;
47 register int iy;
48 register mp_word *_W;
49 48
50 /* work todo, that is we only calculate digits that are at "digs" or above */ 49 /* get offsets into the two bignums */
51 iy = digs - ix; 50 ty = MIN(b->used-1, ix);
51 tx = ix - ty;
52 52
53 /* copy of word on the left of A[ix] * B[iy] */ 53 /* setup temp aliases */
54 tmpx = a->dp[ix]; 54 tmpx = a->dp + tx;
55 tmpy = b->dp + ty;
55 56
56 /* alias for right side */ 57 /* this is the number of times the loop will iterrate, essentially its
57 tmpy = b->dp + iy; 58 while (tx++ < a->used && ty-- >= 0) { ... }
58
59 /* alias for the columns of output. Offset to be equal to or above the
60 * smallest digit place requested
61 */ 59 */
62 _W = W + digs; 60 iy = MIN(a->used-tx, ty+1);
63 61
64 /* skip cases below zero where ix > digs */ 62 /* execute loop */
65 if (iy < 0) { 63 for (iz = 0; iz < iy; iz++) {
66 iy = abs(iy); 64 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
67 tmpy += iy;
68 _W += iy;
69 iy = 0;
70 } 65 }
71 66
72 /* compute column products for digits above the minimum */ 67 /* store term */
73 for (; iy < pb; iy++) { 68 W[ix] = ((mp_digit)_W) & MP_MASK;
74 *_W++ += ((mp_word) tmpx) * ((mp_word)*tmpy++); 69
75 } 70 /* make next carry */
76 } 71 _W = _W >> ((mp_word)DIGIT_BIT);
77 } 72 }
78 73
79 /* setup dest */ 74 /* setup dest */
80 oldused = c->used; 75 olduse = c->used;
81 c->used = newused; 76 c->used = pa;
82 77
83 /* now convert the array W downto what we need 78 {
84 * 79 register mp_digit *tmpc;
85 * See comments in bn_fast_s_mp_mul_digs.c
86 */
87 for (ix = digs + 1; ix < newused; ix++) {
88 W[ix] += (W[ix - 1] >> ((mp_word) DIGIT_BIT));
89 c->dp[ix - 1] = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK));
90 }
91 c->dp[newused - 1] = (mp_digit) (W[newused - 1] & ((mp_word) MP_MASK));
92 80
93 for (; ix < oldused; ix++) { 81 tmpc = c->dp + digs;
94 c->dp[ix] = 0; 82 for (ix = digs; ix <= pa; ix++) {
83 /* now extract the previous digit [below the carry] */
84 *tmpc++ = W[ix];
85 }
86
87 /* clear unused digits [that existed in the old copy of c] */
88 for (; ix < olduse; ix++) {
89 *tmpc++ = 0;
90 }
95 } 91 }
96 mp_clamp (c); 92 mp_clamp (c);
97 return MP_OKAY; 93 return MP_OKAY;
98 } 94 }
95 #endif