LCOV - code coverage report
Current view: top level - mpi - mpi-mod.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 6 66 9.1 %
Date: 2016-09-12 12:56:58 Functions: 2 5 40.0 %

          Line data    Source code
       1             : /* mpi-mod.c -  Modular reduction
       2             :    Copyright (C) 1998, 1999, 2001, 2002, 2003,
       3             :                  2007  Free Software Foundation, Inc.
       4             : 
       5             :    This file is part of Libgcrypt.
       6             : 
       7             :    Libgcrypt is free software; you can redistribute it and/or modify
       8             :    it under the terms of the GNU Lesser General Public License as
       9             :    published by the Free Software Foundation; either version 2.1 of
      10             :    the License, or (at your option) any later version.
      11             : 
      12             :    Libgcrypt is distributed in the hope that it will be useful,
      13             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      14             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15             :    GNU Lesser General Public License for more details.
      16             : 
      17             :    You should have received a copy of the GNU Lesser General Public
      18             :    License along with this program; if not, write to the Free Software
      19             :    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
      20             :    USA.  */
      21             : 
      22             : 
      23             : #include <config.h>
      24             : #include <stdio.h>
      25             : #include <stdlib.h>
      26             : 
      27             : #include "mpi-internal.h"
      28             : #include "longlong.h"
      29             : #include "g10lib.h"
      30             : 
      31             : 
      32             : /* Context used with Barrett reduction.  */
      33             : struct barrett_ctx_s
      34             : {
      35             :   gcry_mpi_t m;   /* The modulus - may not be modified. */
      36             :   int m_copied;   /* If true, M needs to be released.  */
      37             :   int k;
      38             :   gcry_mpi_t y;
      39             :   gcry_mpi_t r1;  /* Helper MPI. */
      40             :   gcry_mpi_t r2;  /* Helper MPI. */
      41             :   gcry_mpi_t r3;  /* Helper MPI allocated on demand. */
      42             : };
      43             : 
      44             : 
      45             : 
      46             : void
      47    37933319 : _gcry_mpi_mod (gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor)
      48             : {
      49    37933319 :   _gcry_mpi_fdiv_r (rem, dividend, divisor);
      50    37933319 : }
      51             : 
      52             : 
      53             : /* This function returns a new context for Barrett based operations on
      54             :    the modulus M.  This context needs to be released using
      55             :    _gcry_mpi_barrett_free.  If COPY is true M will be transferred to
      56             :    the context and the user may change M.  If COPY is false, M may not
      57             :    be changed until gcry_mpi_barrett_free has been called. */
      58             : mpi_barrett_t
      59           0 : _gcry_mpi_barrett_init (gcry_mpi_t m, int copy)
      60             : {
      61             :   mpi_barrett_t ctx;
      62             :   gcry_mpi_t tmp;
      63             : 
      64           0 :   mpi_normalize (m);
      65           0 :   ctx = xcalloc (1, sizeof *ctx);
      66             : 
      67           0 :   if (copy)
      68             :     {
      69           0 :       ctx->m = mpi_copy (m);
      70           0 :       ctx->m_copied = 1;
      71             :     }
      72             :   else
      73           0 :     ctx->m = m;
      74             : 
      75           0 :   ctx->k = mpi_get_nlimbs (m);
      76           0 :   tmp = mpi_alloc (ctx->k + 1);
      77             : 
      78             :   /* Barrett precalculation: y = floor(b^(2k) / m). */
      79           0 :   mpi_set_ui (tmp, 1);
      80           0 :   mpi_lshift_limbs (tmp, 2 * ctx->k);
      81           0 :   mpi_fdiv_q (tmp, tmp, m);
      82             : 
      83           0 :   ctx->y  = tmp;
      84           0 :   ctx->r1 = mpi_alloc ( 2 * ctx->k + 1 );
      85           0 :   ctx->r2 = mpi_alloc ( 2 * ctx->k + 1 );
      86             : 
      87           0 :   return ctx;
      88             : }
      89             : 
      90             : void
      91        2474 : _gcry_mpi_barrett_free (mpi_barrett_t ctx)
      92             : {
      93        2474 :   if (ctx)
      94             :     {
      95           0 :       mpi_free (ctx->y);
      96           0 :       mpi_free (ctx->r1);
      97           0 :       mpi_free (ctx->r2);
      98           0 :       if (ctx->r3)
      99           0 :         mpi_free (ctx->r3);
     100           0 :       if (ctx->m_copied)
     101           0 :         mpi_free (ctx->m);
     102           0 :       xfree (ctx);
     103             :     }
     104        2474 : }
     105             : 
     106             : 
     107             : /* R = X mod M
     108             : 
     109             :    Using Barrett reduction.  Before using this function
     110             :    _gcry_mpi_barrett_init must have been called to do the
     111             :    precalculations.  CTX is the context created by this precalculation
     112             :    and also conveys M.  If the Barret reduction could no be done a
     113             :    straightforward reduction method is used.
     114             : 
     115             :    We assume that these conditions are met:
     116             :    Input:  x =(x_2k-1 ...x_0)_b
     117             :            m =(m_k-1 ....m_0)_b   with m_k-1 != 0
     118             :    Output: r = x mod m
     119             :  */
     120             : void
     121           0 : _gcry_mpi_mod_barrett (gcry_mpi_t r, gcry_mpi_t x, mpi_barrett_t ctx)
     122             : {
     123           0 :   gcry_mpi_t m = ctx->m;
     124           0 :   int k = ctx->k;
     125           0 :   gcry_mpi_t y = ctx->y;
     126           0 :   gcry_mpi_t r1 = ctx->r1;
     127           0 :   gcry_mpi_t r2 = ctx->r2;
     128             :   int sign;
     129             : 
     130           0 :   mpi_normalize (x);
     131           0 :   if (mpi_get_nlimbs (x) > 2*k )
     132             :     {
     133           0 :       mpi_mod (r, x, m);
     134           0 :       return;
     135             :     }
     136             : 
     137           0 :   sign = x->sign;
     138           0 :   x->sign = 0;
     139             : 
     140             :   /* 1. q1 = floor( x / b^k-1)
     141             :    *    q2 = q1 * y
     142             :    *    q3 = floor( q2 / b^k+1 )
     143             :    * Actually, we don't need qx, we can work direct on r2
     144             :    */
     145           0 :   mpi_set ( r2, x );
     146           0 :   mpi_rshift_limbs ( r2, k-1 );
     147           0 :   mpi_mul ( r2, r2, y );
     148           0 :   mpi_rshift_limbs ( r2, k+1 );
     149             : 
     150             :   /* 2. r1 = x mod b^k+1
     151             :    *    r2 = q3 * m mod b^k+1
     152             :    *    r  = r1 - r2
     153             :    * 3. if r < 0 then  r = r + b^k+1
     154             :    */
     155           0 :   mpi_set ( r1, x );
     156           0 :   if ( r1->nlimbs > k+1 ) /* Quick modulo operation.  */
     157           0 :     r1->nlimbs = k+1;
     158           0 :   mpi_mul ( r2, r2, m );
     159           0 :   if ( r2->nlimbs > k+1 ) /* Quick modulo operation. */
     160           0 :     r2->nlimbs = k+1;
     161           0 :   mpi_sub ( r, r1, r2 );
     162             : 
     163           0 :   if ( mpi_has_sign ( r ) )
     164             :     {
     165           0 :       if (!ctx->r3)
     166             :         {
     167           0 :           ctx->r3 = mpi_alloc ( k + 2 );
     168           0 :           mpi_set_ui (ctx->r3, 1);
     169           0 :           mpi_lshift_limbs (ctx->r3, k + 1 );
     170             :         }
     171           0 :       mpi_add ( r, r, ctx->r3 );
     172             :     }
     173             : 
     174             :   /* 4. while r >= m do r = r - m */
     175           0 :   while ( mpi_cmp( r, m ) >= 0 )
     176           0 :     mpi_sub ( r, r, m );
     177             : 
     178           0 :   x->sign = sign;
     179             : }
     180             : 
     181             : 
     182             : void
     183           0 : _gcry_mpi_mul_barrett (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v,
     184             :                        mpi_barrett_t ctx)
     185             : {
     186           0 :   mpi_mul (w, u, v);
     187           0 :   mpi_mod_barrett (w, w, ctx);
     188           0 : }

Generated by: LCOV version 1.11