LCOV - code coverage report
Current view: top level - source4/heimdal/lib/hcrypto/libtommath - bn_fast_s_mp_mul_digs.c (source / functions) Hit Total Coverage
Test: coverage report for abartlet/fix-coverage dd10fb34 Lines: 23 25 92.0 %
Date: 2021-09-23 10:06:22 Functions: 1 1 100.0 %

          Line data    Source code
       1             : #include <tommath.h>
       2             : #ifdef BN_FAST_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://libtom.org
      16             :  */
      17             : 
      18             : /* Fast (comba) multiplier
      19             :  *
      20             :  * This is the fast column-array [comba] multiplier.  It is
      21             :  * designed to compute the columns of the product first
      22             :  * then handle the carries afterwards.  This has the effect
      23             :  * of making the nested loops that compute the columns very
      24             :  * simple and schedulable on super-scalar processors.
      25             :  *
      26             :  * This has been modified to produce a variable number of
      27             :  * digits of output so if say only a half-product is required
      28             :  * you don't have to compute the upper half (a feature
      29             :  * required for fast Barrett reduction).
      30             :  *
      31             :  * Based on Algorithm 14.12 on pp.595 of HAC.
      32             :  *
      33             :  */
      34      106127 : int fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
      35             : {
      36             :   int     olduse, res, pa, ix, iz;
      37             :   mp_digit W[MP_WARRAY];
      38             :   register mp_word  _W;
      39             : 
      40             :   /* grow the destination as required */
      41      106127 :   if (c->alloc < digs) {
      42       20486 :     if ((res = mp_grow (c, digs)) != MP_OKAY) {
      43           0 :       return res;
      44             :     }
      45             :   }
      46             : 
      47             :   /* number of output digits to produce */
      48      106127 :   pa = MIN(digs, a->used + b->used);
      49             : 
      50             :   /* clear the carry */
      51      106127 :   _W = 0;
      52     6038969 :   for (ix = 0; ix < pa; ix++) {
      53             :       int      tx, ty;
      54             :       int      iy;
      55             :       mp_digit *tmpx, *tmpy;
      56             : 
      57             :       /* get offsets into the two bignums */
      58     5932842 :       ty = MIN(b->used-1, ix);
      59     5932842 :       tx = ix - ty;
      60             : 
      61             :       /* setup temp aliases */
      62     5932842 :       tmpx = a->dp + tx;
      63     5932842 :       tmpy = b->dp + ty;
      64             : 
      65             :       /* this is the number of times the loop will iterrate, essentially
      66             :          while (tx++ < a->used && ty-- >= 0) { ... }
      67             :        */
      68     5932842 :       iy = MIN(a->used-tx, ty+1);
      69             : 
      70             :       /* execute loop */
      71   101994080 :       for (iz = 0; iz < iy; ++iz) {
      72    96061238 :          _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
      73             : 
      74             :       }
      75             : 
      76             :       /* store term */
      77     5932842 :       W[ix] = ((mp_digit)_W) & MP_MASK;
      78             : 
      79             :       /* make next carry */
      80     5932842 :       _W = _W >> ((mp_word)DIGIT_BIT);
      81             :  }
      82             : 
      83             :   /* setup dest */
      84      106127 :   olduse  = c->used;
      85      106127 :   c->used = pa;
      86             : 
      87             :   {
      88             :     register mp_digit *tmpc;
      89      106127 :     tmpc = c->dp;
      90     6145096 :     for (ix = 0; ix < pa+1; ix++) {
      91             :       /* now extract the previous digit [below the carry] */
      92     6038969 :       *tmpc++ = W[ix];
      93             :     }
      94             : 
      95             :     /* clear unused digits [that existed in the old copy of c] */
      96      100847 :     for (; ix < olduse; ix++) {
      97           0 :       *tmpc++ = 0;
      98             :     }
      99             :   }
     100      106127 :   mp_clamp (c);
     101      106127 :   return MP_OKAY;
     102             : }
     103             : #endif
     104             : 
     105             : /* $Source: /cvs/libtom/libtommath/bn_fast_s_mp_mul_digs.c,v $ */
     106             : /* $Revision: 1.8 $ */
     107             : /* $Date: 2006/12/28 01:25:13 $ */

Generated by: LCOV version 1.13