1 /* $NetBSD: bn_fast_s_mp_mul_digs.c,v 1.1.1.1 2011/04/13 18:14:54 elric 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 */ 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