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

          Line data    Source code
       1             : #include <tommath.h>
       2             : #ifdef BN_MP_DR_REDUCE_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             : /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
      19             :  *
      20             :  * Based on algorithm from the paper
      21             :  *
      22             :  * "Generating Efficient Primes for Discrete Log Cryptosystems"
      23             :  *                 Chae Hoon Lim, Pil Joong Lee,
      24             :  *          POSTECH Information Research Laboratories
      25             :  *
      26             :  * The modulus must be of a special format [see manual]
      27             :  *
      28             :  * Has been modified to use algorithm 7.10 from the LTM book instead
      29             :  *
      30             :  * Input x must be in the range 0 <= x <= (n-1)**2
      31             :  */
      32             : int
      33           0 : mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
      34             : {
      35             :   int      err, i, m;
      36             :   mp_word  r;
      37             :   mp_digit mu, *tmpx1, *tmpx2;
      38             : 
      39             :   /* m = digits in modulus */
      40           0 :   m = n->used;
      41             : 
      42             :   /* ensure that "x" has at least 2m digits */
      43           0 :   if (x->alloc < m + m) {
      44           0 :     if ((err = mp_grow (x, m + m)) != MP_OKAY) {
      45           0 :       return err;
      46             :     }
      47             :   }
      48             : 
      49             : /* top of loop, this is where the code resumes if
      50             :  * another reduction pass is required.
      51             :  */
      52           0 : top:
      53             :   /* aliases for digits */
      54             :   /* alias for lower half of x */
      55           0 :   tmpx1 = x->dp;
      56             : 
      57             :   /* alias for upper half of x, or x/B**m */
      58           0 :   tmpx2 = x->dp + m;
      59             : 
      60             :   /* set carry to zero */
      61           0 :   mu = 0;
      62             : 
      63             :   /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
      64           0 :   for (i = 0; i < m; i++) {
      65           0 :       r         = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
      66           0 :       *tmpx1++  = (mp_digit)(r & MP_MASK);
      67           0 :       mu        = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
      68             :   }
      69             : 
      70             :   /* set final carry */
      71           0 :   *tmpx1++ = mu;
      72             : 
      73             :   /* zero words above m */
      74           0 :   for (i = m + 1; i < x->used; i++) {
      75           0 :       *tmpx1++ = 0;
      76             :   }
      77             : 
      78             :   /* clamp, sub and return */
      79           0 :   mp_clamp (x);
      80             : 
      81             :   /* if x >= n then subtract and reduce again
      82             :    * Each successive "recursion" makes the input smaller and smaller.
      83             :    */
      84           0 :   if (mp_cmp_mag (x, n) != MP_LT) {
      85           0 :     s_mp_sub(x, n, x);
      86           0 :     goto top;
      87             :   }
      88           0 :   return MP_OKAY;
      89             : }
      90             : #endif
      91             : 
      92             : /* $Source: /cvs/libtom/libtommath/bn_mp_dr_reduce.c,v $ */
      93             : /* $Revision: 1.4 $ */
      94             : /* $Date: 2006/12/28 01:25:13 $ */

Generated by: LCOV version 1.13