Mercurial > dropbear

comparison bn_fast_s_mp_mul_high_digs.c @ 2:86e0b50a9b58 libtommath-orig ltm-0.30-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ltm 0.30 orig import
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:25:22 +0000
parents
children d29b64170cf0
comparison
equal deleted inserted replaced
-1:000000000000 2:86e0b50a9b58
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */
15 #include <tommath.h>
16
17 /* this is a modified version of fast_s_mp_mul_digs that only produces
18 * output digits *above* digs. See the comments for fast_s_mp_mul_digs
19 * to see how it works.
20 *
21 * 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 *
24 * Based on Algorithm 14.12 on pp.595 of HAC.
25 */
26 int
27 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
28 {
29 int oldused, newused, res, pa, pb, ix;
30 mp_word W[MP_WARRAY];
31
32 /* calculate size of product and allocate more space if required */
33 newused = a->used + b->used + 1;
34 if (c->alloc < newused) {
35 if ((res = mp_grow (c, newused)) != MP_OKAY) {
36 return res;
37 }
38 }
39
40 /* like the other comba method we compute the columns first */
41 pa = a->used;
42 pb = b->used;
43 memset (W + digs, 0, (pa + pb + 1 - digs) * sizeof (mp_word));
44 for (ix = 0; ix < pa; ix++) {
45 {
46 register mp_digit tmpx, *tmpy;
47 register int iy;
48 register mp_word *_W;
49
50 /* work todo, that is we only calculate digits that are at "digs" or above */
51 iy = digs - ix;
52
53 /* copy of word on the left of A[ix] * B[iy] */
54 tmpx = a->dp[ix];
55
56 /* alias for right side */
57 tmpy = b->dp + iy;
58
59 /* alias for the columns of output. Offset to be equal to or above the
60 * smallest digit place requested
61 */
62 _W = W + digs;
63
64 /* skip cases below zero where ix > digs */
65 if (iy < 0) {
66 iy = abs(iy);
67 tmpy += iy;
68 _W += iy;
69 iy = 0;
70 }
71
72 /* compute column products for digits above the minimum */
73 for (; iy < pb; iy++) {
74 *_W++ += ((mp_word) tmpx) * ((mp_word)*tmpy++);
75 }
76 }
77 }
78
79 /* setup dest */
80 oldused = c->used;
81 c->used = newused;
82
83 /* now convert the array W downto what we need
84 *
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
93 for (; ix < oldused; ix++) {
94 c->dp[ix] = 0;
95 }
96 mp_clamp (c);
97 return MP_OKAY;
98 }