1 /* $NetBSD: bn_fast_s_mp_mul_high_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_HIGH_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 /* this is a modified version of fast_s_mul_digs that only produces
21 * output digits *above* digs. See the comments for fast_s_mul_digs
22 * to see how it works.
23 *
24 * This is used in the Barrett reduction since for one of the multiplications
25 * only the higher digits were needed. This essentially halves the work.
26 *
27 * Based on Algorithm 14.12 on pp.595 of HAC.
28 */
fast_s_mp_mul_high_digs(mp_int * a,mp_int * b,mp_int * c,int digs)29 int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
30 {
31 int olduse, res, pa, ix, iz;
32 mp_digit W[MP_WARRAY];
33 mp_word _W;
34
35 /* grow the destination as required */
36 pa = a->used + b->used;
37 if (c->alloc < pa) {
38 if ((res = mp_grow (c, pa)) != MP_OKAY) {
39 return res;
40 }
41 }
42
43 /* number of output digits to produce */
44 pa = a->used + b->used;
45 _W = 0;
46 for (ix = digs; ix < pa; ix++) {
47 int tx, ty, iy;
48 mp_digit *tmpx, *tmpy;
49
50 /* get offsets into the two bignums */
51 ty = MIN(b->used-1, ix);
52 tx = ix - ty;
53
54 /* setup temp aliases */
55 tmpx = a->dp + tx;
56 tmpy = b->dp + ty;
57
58 /* this is the number of times the loop will iterrate, essentially its
59 while (tx++ < a->used && ty-- >= 0) { ... }
60 */
61 iy = MIN(a->used-tx, ty+1);
62
63 /* execute loop */
64 for (iz = 0; iz < iy; iz++) {
65 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
66 }
67
68 /* store term */
69 W[ix] = ((mp_digit)_W) & MP_MASK;
70
71 /* make next carry */
72 _W = _W >> ((mp_word)DIGIT_BIT);
73 }
74
75 /* setup dest */
76 olduse = c->used;
77 c->used = pa;
78
79 {
80 register mp_digit *tmpc;
81
82 tmpc = c->dp + digs;
83 for (ix = digs; ix < pa; ix++) {
84 /* now extract the previous digit [below the carry] */
85 *tmpc++ = W[ix];
86 }
87
88 /* clear unused digits [that existed in the old copy of c] */
89 for (; ix < olduse; ix++) {
90 *tmpc++ = 0;
91 }
92 }
93 mp_clamp (c);
94 return MP_OKAY;
95 }
96 #endif
97
98 /* Source: /cvs/libtom/libtommath/bn_fast_s_mp_mul_high_digs.c,v */
99 /* Revision: 1.6 */
100 /* Date: 2006/12/28 01:25:13 */
101