/home/ntakagi/work/tcl8.5.1/libtommath/bn_s_mp_mul_digs.c Source File

00001 #include <tommath.h>
00002 #ifdef BN_S_MP_MUL_DIGS_C
00003 /* LibTomMath, multiple-precision integer library -- Tom St Denis
00004  *
00005  * LibTomMath is a library that provides multiple-precision
00006  * integer arithmetic as well as number theoretic functionality.
00007  *
00008  * The library was designed directly after the MPI library by
00009  * Michael Fromberger but has been written from scratch with
00010  * additional optimizations in place.
00011  *
00012  * The library is free for all purposes without any express
00013  * guarantee it works.
00014  *
00015  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
00016  */
00017 
00018 /* multiplies |a| * |b| and only computes upto digs digits of result
00019  * HAC pp. 595, Algorithm 14.12  Modified so you can control how 
00020  * many digits of output are created.
00021  */
00022 int s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
00023 {
00024   mp_int  t;
00025   int     res, pa, pb, ix, iy;
00026   mp_digit u;
00027   mp_word r;
00028   mp_digit tmpx, *tmpt, *tmpy;
00029 
00030   /* can we use the fast multiplier? */
00031   if (((digs) < MP_WARRAY) &&
00032       MIN (a->used, b->used) < 
00033           (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
00034     return fast_s_mp_mul_digs (a, b, c, digs);
00035   }
00036 
00037   if ((res = mp_init_size (&t, digs)) != MP_OKAY) {
00038     return res;
00039   }
00040   t.used = digs;
00041 
00042   /* compute the digits of the product directly */
00043   pa = a->used;
00044   for (ix = 0; ix < pa; ix++) {
00045     /* set the carry to zero */
00046     u = 0;
00047 
00048     /* limit ourselves to making digs digits of output */
00049     pb = MIN (b->used, digs - ix);
00050 
00051     /* setup some aliases */
00052     /* copy of the digit from a used within the nested loop */
00053     tmpx = a->dp[ix];
00054     
00055     /* an alias for the destination shifted ix places */
00056     tmpt = t.dp + ix;
00057     
00058     /* an alias for the digits of b */
00059     tmpy = b->dp;
00060 
00061     /* compute the columns of the output and propagate the carry */
00062     for (iy = 0; iy < pb; iy++) {
00063       /* compute the column as a mp_word */
00064       r       = ((mp_word)*tmpt) +
00065                 ((mp_word)tmpx) * ((mp_word)*tmpy++) +
00066                 ((mp_word) u);
00067 
00068       /* the new column is the lower part of the result */
00069       *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
00070 
00071       /* get the carry word from the result */
00072       u       = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
00073     }
00074     /* set carry if it is placed below digs */
00075     if (ix + iy < digs) {
00076       *tmpt = u;
00077     }
00078   }
00079 
00080   mp_clamp (&t);
00081   mp_exch (&t, c);
00082 
00083   mp_clear (&t);
00084   return MP_OKAY;
00085 }
00086 #endif
00087 
00088 /* $Source: /cvsroot/tcl/libtommath/bn_s_mp_mul_digs.c,v $ */
00089 /* $Revision: 1.1.1.4 $ */
00090 /* $Date: 2006/12/01 00:08:11 $ */