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