Mercurial > dropbear
comparison libtommath/bn_s_mp_mul_digs.c @ 293:9d110777f345 contrib-blacklist
propagate from branch 'au.asn.ucc.matt.dropbear' (head 7ad1775ed65e75dbece27fe6b65bf1a234db386a)
to branch 'au.asn.ucc.matt.dropbear.contrib.blacklist' (head 1d86a4f0a401cc68c2670d821a2f6366c37af143)
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Fri, 10 Mar 2006 06:31:29 +0000 |
parents | eed26cff980b |
children | 5ff8218bcee9 |
comparison
equal
deleted
inserted
replaced
247:c07de41b53d7 | 293:9d110777f345 |
---|---|
1 #include <tommath.h> | |
2 #ifdef BN_S_MP_MUL_DIGS_C | |
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | |
4 * | |
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://math.libtomcrypt.org | |
16 */ | |
17 | |
18 /* multiplies |a| * |b| and only computes upto digs digits of result | |
19 * HAC pp. 595, Algorithm 14.12 Modified so you can control how | |
20 * many digits of output are created. | |
21 */ | |
22 int s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs) | |
23 { | |
24 mp_int t; | |
25 int res, pa, pb, ix, iy; | |
26 mp_digit u; | |
27 mp_word r; | |
28 mp_digit tmpx, *tmpt, *tmpy; | |
29 | |
30 /* can we use the fast multiplier? */ | |
31 if (((digs) < MP_WARRAY) && | |
32 MIN (a->used, b->used) < | |
33 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { | |
34 return fast_s_mp_mul_digs (a, b, c, digs); | |
35 } | |
36 | |
37 if ((res = mp_init_size (&t, digs)) != MP_OKAY) { | |
38 return res; | |
39 } | |
40 t.used = digs; | |
41 | |
42 /* compute the digits of the product directly */ | |
43 pa = a->used; | |
44 for (ix = 0; ix < pa; ix++) { | |
45 /* set the carry to zero */ | |
46 u = 0; | |
47 | |
48 /* limit ourselves to making digs digits of output */ | |
49 pb = MIN (b->used, digs - ix); | |
50 | |
51 /* setup some aliases */ | |
52 /* copy of the digit from a used within the nested loop */ | |
53 tmpx = a->dp[ix]; | |
54 | |
55 /* an alias for the destination shifted ix places */ | |
56 tmpt = t.dp + ix; | |
57 | |
58 /* an alias for the digits of b */ | |
59 tmpy = b->dp; | |
60 | |
61 /* compute the columns of the output and propagate the carry */ | |
62 for (iy = 0; iy < pb; iy++) { | |
63 /* compute the column as a mp_word */ | |
64 r = ((mp_word)*tmpt) + | |
65 ((mp_word)tmpx) * ((mp_word)*tmpy++) + | |
66 ((mp_word) u); | |
67 | |
68 /* the new column is the lower part of the result */ | |
69 *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK)); | |
70 | |
71 /* get the carry word from the result */ | |
72 u = (mp_digit) (r >> ((mp_word) DIGIT_BIT)); | |
73 } | |
74 /* set carry if it is placed below digs */ | |
75 if (ix + iy < digs) { | |
76 *tmpt = u; | |
77 } | |
78 } | |
79 | |
80 mp_clamp (&t); | |
81 mp_exch (&t, c); | |
82 | |
83 mp_clear (&t); | |
84 return MP_OKAY; | |
85 } | |
86 #endif |