1 /* $NetBSD: bn_fast_s_mp_mul_digs.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */
2
3 #include <tommath.h>
4 #ifdef BN_FAST_S_MP_MUL_DIGS_C
5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6 *
7 * LibTomMath is a library that provides multiple-precision
8 * integer arithmetic as well as number theoretic functionality.
9 *
10 * The library was designed directly after the MPI library by
11 * Michael Fromberger but has been written from scratch with
12 * additional optimizations in place.
13 *
14 * The library is free for all purposes without any express
15 * guarantee it works.
16 *
17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
18 */
19
20 /* Fast (comba) multiplier
21 *
22 * This is the fast column-array [comba] multiplier. It is
23 * designed to compute the columns of the product first
24 * then handle the carries afterwards. This has the effect
25 * of making the nested loops that compute the columns very
26 * simple and schedulable on super-scalar processors.
27 *
28 * This has been modified to produce a variable number of
29 * digits of output so if say only a half-product is required
30 * you don't have to compute the upper half (a feature
31 * required for fast Barrett reduction).
32 *
33 * Based on Algorithm 14.12 on pp.595 of HAC.
34 *
35 */
fast_s_mp_mul_digs(mp_int * a,mp_int * b,mp_int * c,int digs)36 int fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
37 {
38 int olduse, res, pa, ix, iz;
39 mp_digit W[MP_WARRAY];
40 register mp_word _W;
41
42 /* grow the destination as required */
43 if (c->alloc < digs) {
44 if ((res = mp_grow (c, digs)) != MP_OKAY) {
45 return res;
46 }
47 }
48
49 /* number of output digits to produce */
50 pa = MIN(digs, a->used + b->used);
51
52 /* clear the carry */
53 _W = 0;
54 for (ix = 0; ix < pa; ix++) {
55 int tx, ty;
56 int iy;
57 mp_digit *tmpx, *tmpy;
58
59 /* get offsets into the two bignums */
60 ty = MIN(b->used-1, ix);
61 tx = ix - ty;
62
63 /* setup temp aliases */
64 tmpx = a->dp + tx;
65 tmpy = b->dp + ty;
66
67 /* this is the number of times the loop will iterrate, essentially
68 while (tx++ < a->used && ty-- >= 0) { ... }
69 */
70 iy = MIN(a->used-tx, ty+1);
71
72 /* execute loop */
73 for (iz = 0; iz < iy; ++iz) {
74 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
75
76 }
77
78 /* store term */
79 W[ix] = ((mp_digit)_W) & MP_MASK;
80
81 /* make next carry */
82 _W = _W >> ((mp_word)DIGIT_BIT);
83 }
84
85 /* setup dest */
86 olduse = c->used;
87 c->used = pa;
88
89 {
90 register mp_digit *tmpc;
91 tmpc = c->dp;
92 for (ix = 0; ix < pa+1; ix++) {
93 /* now extract the previous digit [below the carry] */
94 *tmpc++ = W[ix];
95 }
96
97 /* clear unused digits [that existed in the old copy of c] */
98 for (; ix < olduse; ix++) {
99 *tmpc++ = 0;
100 }
101 }
102 mp_clamp (c);
103 return MP_OKAY;
104 }
105 #endif
106
107 /* Source: /cvs/libtom/libtommath/bn_fast_s_mp_mul_digs.c,v */
108 /* Revision: 1.8 */
109 /* Date: 2006/12/28 01:25:13 */
110