Line data    Source code

       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@gmail.com, http://libtom.org
      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           0 : 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           0 :   pa = a->used + b->used;
      35           0 :   if (c->alloc < pa) {
      36           0 :     if ((res = mp_grow (c, pa)) != MP_OKAY) {
      37           0 :       return res;
      38             :     }
      39             :   }
      40             : 
      41             :   /* number of output digits to produce */
      42           0 :   pa = a->used + b->used;
      43           0 :   _W = 0;
      44           0 :   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           0 :       ty = MIN(b->used-1, ix);
      50           0 :       tx = ix - ty;
      51             : 
      52             :       /* setup temp aliases */
      53           0 :       tmpx = a->dp + tx;
      54           0 :       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           0 :       iy = MIN(a->used-tx, ty+1);
      60             : 
      61             :       /* execute loop */
      62           0 :       for (iz = 0; iz < iy; iz++) {
      63           0 :          _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
      64             :       }
      65             : 
      66             :       /* store term */
      67           0 :       W[ix] = ((mp_digit)_W) & MP_MASK;
      68             : 
      69             :       /* make next carry */
      70           0 :       _W = _W >> ((mp_word)DIGIT_BIT);
      71             :   }
      72             : 
      73             :   /* setup dest */
      74           0 :   olduse  = c->used;
      75           0 :   c->used = pa;
      76             : 
      77             :   {
      78             :     register mp_digit *tmpc;
      79             : 
      80           0 :     tmpc = c->dp + digs;
      81           0 :     for (ix = digs; ix < pa; ix++) {
      82             :       /* now extract the previous digit [below the carry] */
      83           0 :       *tmpc++ = W[ix];
      84             :     }
      85             : 
      86             :     /* clear unused digits [that existed in the old copy of c] */
      87           0 :     for (; ix < olduse; ix++) {
      88           0 :       *tmpc++ = 0;
      89             :     }
      90             :   }
      91           0 :   mp_clamp (c);
      92           0 :   return MP_OKAY;
      93             : }
      94             : #endif
      95             : 
      96             : /* $Source: /cvs/libtom/libtommath/bn_fast_s_mp_mul_high_digs.c,v $ */
      97             : /* $Revision: 1.6 $ */
      98             : /* $Date: 2006/12/28 01:25:13 $ */