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, tomstdenis (at) gmail.com, http://math.libtomcrypt.com 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 87 88 /* $Source: /cvs/libtom/libtommath/bn_s_mp_mul_digs.c,v $ */ 89 /* $Revision: 1.3 $ */ 90 /* $Date: 2006/03/31 14:18:44 $ */ 91
