| 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@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: /cvsroot/tcl/libtommath/bn_s_mp_mul_digs.c,v $ */ |
|---|
| 89 | /* $Revision: 1.1.1.4 $ */ |
|---|
| 90 | /* $Date: 2006/12/01 00:08:11 $ */ |
|---|
