LCOV - code coverage report
Current view: top level - mpi - mpi-bit.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 135 163 82.8 %
Date: 2016-09-12 12:56:58 Functions: 10 11 90.9 %

          Line data    Source code
       1             : /* mpi-bit.c  -  MPI bit level functions
       2             :  * Copyright (C) 1998, 1999, 2001, 2002, 2006 Free Software Foundation, Inc.
       3             :  * Copyright (C) 2013  g10 Code GmbH
       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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
      20             :  */
      21             : 
      22             : #include <config.h>
      23             : #include <stdio.h>
      24             : #include <stdlib.h>
      25             : #include "mpi-internal.h"
      26             : #include "longlong.h"
      27             : 
      28             : 
      29             : #ifdef MPI_INTERNAL_NEED_CLZ_TAB
      30             : #ifdef __STDC__
      31             : const
      32             : #endif
      33             : unsigned char
      34             : _gcry_clz_tab[] =
      35             : {
      36             :   0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
      37             :   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
      38             :   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      39             :   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      40             :   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      41             :   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      42             :   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      43             :   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      44             : };
      45             : #endif
      46             : 
      47             : 
      48             : #define A_LIMB_1 ((mpi_limb_t)1)
      49             : 
      50             : 
      51             : /****************
      52             :  * Sometimes we have MSL (most significant limbs) which are 0;
      53             :  * this is for some reasons not good, so this function removes them.
      54             :  */
      55             : void
      56     3458378 : _gcry_mpi_normalize( gcry_mpi_t a )
      57             : {
      58     3458378 :     if( mpi_is_opaque(a) )
      59     3458381 :         return;
      60             : 
      61     3458375 :     for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
      62             :         ;
      63             : }
      64             : 
      65             : 
      66             : 
      67             : /****************
      68             :  * Return the number of bits in A.
      69             :  */
      70             : unsigned int
      71       57225 : _gcry_mpi_get_nbits (gcry_mpi_t a)
      72             : {
      73             :     unsigned n;
      74             : 
      75       57225 :     if( mpi_is_opaque(a) ) {
      76           0 :         return a->sign; /* which holds the number of bits */
      77             :     }
      78             : 
      79       57225 :     _gcry_mpi_normalize( a );
      80       57225 :     if( a->nlimbs ) {
      81       56442 :         mpi_limb_t alimb = a->d[a->nlimbs-1];
      82       56442 :         if( alimb )
      83       56442 :             count_leading_zeros( n, alimb );
      84             :         else
      85           0 :             n = BITS_PER_MPI_LIMB;
      86       56442 :         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
      87             :     }
      88             :     else
      89         783 :         n = 0;
      90       57225 :     return n;
      91             : }
      92             : 
      93             : 
      94             : /****************
      95             :  * Test whether bit N is set.
      96             :  */
      97             : int
      98    11430731 : _gcry_mpi_test_bit( gcry_mpi_t a, unsigned int n )
      99             : {
     100             :     unsigned int limbno, bitno;
     101             :     mpi_limb_t limb;
     102             : 
     103    11430731 :     limbno = n / BITS_PER_MPI_LIMB;
     104    11430731 :     bitno  = n % BITS_PER_MPI_LIMB;
     105             : 
     106    11430731 :     if( limbno >= a->nlimbs )
     107       11420 :         return 0; /* too far left: this is a 0 */
     108    11419311 :     limb = a->d[limbno];
     109    11419311 :     return (limb & (A_LIMB_1 << bitno))? 1: 0;
     110             : }
     111             : 
     112             : 
     113             : /****************
     114             :  * Set bit N of A.
     115             :  */
     116             : void
     117        1605 : _gcry_mpi_set_bit( gcry_mpi_t a, unsigned int n )
     118             : {
     119             :   unsigned int i, limbno, bitno;
     120             : 
     121        1605 :   if (mpi_is_immutable (a))
     122             :     {
     123           0 :       mpi_immutable_failed ();
     124        1605 :       return;
     125             :     }
     126             : 
     127        1605 :   limbno = n / BITS_PER_MPI_LIMB;
     128        1605 :   bitno  = n % BITS_PER_MPI_LIMB;
     129             : 
     130        1605 :   if ( limbno >= a->nlimbs )
     131             :     {
     132          30 :       for (i=a->nlimbs; i < a->alloced; i++)
     133          26 :         a->d[i] = 0;
     134           4 :       mpi_resize (a, limbno+1 );
     135           4 :       a->nlimbs = limbno+1;
     136             :     }
     137        1605 :   a->d[limbno] |= (A_LIMB_1<<bitno);
     138             : }
     139             : 
     140             : /****************
     141             :  * Set bit N of A. and clear all bits above
     142             :  */
     143             : void
     144       11913 : _gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
     145             : {
     146             :   unsigned int i, limbno, bitno;
     147             : 
     148       11913 :   if (mpi_is_immutable (a))
     149             :     {
     150           0 :       mpi_immutable_failed ();
     151       11913 :       return;
     152             :     }
     153             : 
     154       11913 :   limbno = n / BITS_PER_MPI_LIMB;
     155       11913 :   bitno  = n % BITS_PER_MPI_LIMB;
     156             : 
     157       11913 :   if ( limbno >= a->nlimbs )
     158             :     {
     159      101139 :       for (i=a->nlimbs; i < a->alloced; i++)
     160       96614 :         a->d[i] = 0;
     161        4525 :       mpi_resize (a, limbno+1 );
     162        4525 :       a->nlimbs = limbno+1;
     163             :     }
     164       11913 :   a->d[limbno] |= (A_LIMB_1<<bitno);
     165      169611 :   for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
     166      157698 :     a->d[limbno] &= ~(A_LIMB_1 << bitno);
     167       11913 :   a->nlimbs = limbno+1;
     168             : }
     169             : 
     170             : /****************
     171             :  * clear bit N of A and all bits above
     172             :  */
     173             : void
     174        4654 : _gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
     175             : {
     176             :   unsigned int limbno, bitno;
     177             : 
     178        4654 :   if (mpi_is_immutable (a))
     179             :     {
     180           0 :       mpi_immutable_failed ();
     181           0 :       return;
     182             :     }
     183             : 
     184        4654 :   limbno = n / BITS_PER_MPI_LIMB;
     185        4654 :   bitno  = n % BITS_PER_MPI_LIMB;
     186             : 
     187        4654 :   if( limbno >= a->nlimbs )
     188          12 :     return; /* not allocated, therefore no need to clear bits :-) */
     189             : 
     190       53353 :   for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
     191       48711 :     a->d[limbno] &= ~(A_LIMB_1 << bitno);
     192        4642 :   a->nlimbs = limbno+1;
     193             : }
     194             : 
     195             : /****************
     196             :  * Clear bit N of A.
     197             :  */
     198             : void
     199        7310 : _gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
     200             : {
     201             :   unsigned int limbno, bitno;
     202             : 
     203        7310 :   if (mpi_is_immutable (a))
     204             :     {
     205           0 :       mpi_immutable_failed ();
     206           0 :       return;
     207             :     }
     208             : 
     209        7310 :   limbno = n / BITS_PER_MPI_LIMB;
     210        7310 :   bitno  = n % BITS_PER_MPI_LIMB;
     211             : 
     212        7310 :   if (limbno >= a->nlimbs)
     213           0 :     return; /* Don't need to clear this bit, it's far too left.  */
     214        7310 :   a->d[limbno] &= ~(A_LIMB_1 << bitno);
     215             : }
     216             : 
     217             : 
     218             : /****************
     219             :  * Shift A by COUNT limbs to the right
     220             :  * This is used only within the MPI library
     221             :  */
     222             : void
     223           0 : _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
     224             : {
     225           0 :   mpi_ptr_t ap = a->d;
     226           0 :   mpi_size_t n = a->nlimbs;
     227             :   unsigned int i;
     228             : 
     229           0 :   if (mpi_is_immutable (a))
     230             :     {
     231           0 :       mpi_immutable_failed ();
     232           0 :       return;
     233             :     }
     234             : 
     235           0 :   if (count >= n)
     236             :     {
     237           0 :       a->nlimbs = 0;
     238           0 :       return;
     239             :     }
     240             : 
     241           0 :   for( i = 0; i < n - count; i++ )
     242           0 :     ap[i] = ap[i+count];
     243           0 :   ap[i] = 0;
     244           0 :   a->nlimbs -= count;
     245             : }
     246             : 
     247             : 
     248             : /*
     249             :  * Shift A by N bits to the right.
     250             :  */
     251             : void
     252    10285088 : _gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
     253             : {
     254             :   mpi_size_t xsize;
     255             :   unsigned int i;
     256    10285088 :   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
     257    10285088 :   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
     258             : 
     259    10285088 :   if (mpi_is_immutable (x))
     260             :     {
     261           0 :       mpi_immutable_failed ();
     262           0 :       return;
     263             :     }
     264             : 
     265    10285088 :   if ( x == a )
     266             :     {
     267             :       /* In-place operation.  */
     268    10284713 :       if ( nlimbs >= x->nlimbs )
     269             :         {
     270         365 :           x->nlimbs = 0;
     271         365 :           return;
     272             :         }
     273             : 
     274    10284348 :       if (nlimbs)
     275             :         {
     276         864 :           for (i=0; i < x->nlimbs - nlimbs; i++ )
     277         662 :             x->d[i] = x->d[i+nlimbs];
     278         202 :           x->d[i] = 0;
     279         202 :           x->nlimbs -= nlimbs;
     280             : 
     281             :         }
     282    10284348 :       if ( x->nlimbs && nbits )
     283    10284248 :         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
     284             :     }
     285         375 :   else if ( nlimbs )
     286             :     {
     287             :       /* Copy and shift by more or equal bits than in a limb. */
     288          55 :       xsize = a->nlimbs;
     289          55 :       x->sign = a->sign;
     290          55 :       RESIZE_IF_NEEDED (x, xsize);
     291          55 :       x->nlimbs = xsize;
     292         165 :       for (i=0; i < a->nlimbs; i++ )
     293         110 :         x->d[i] = a->d[i];
     294          55 :       x->nlimbs = i;
     295             : 
     296          55 :       if ( nlimbs >= x->nlimbs )
     297             :         {
     298           0 :           x->nlimbs = 0;
     299           0 :           return;
     300             :         }
     301             : 
     302          55 :       if (nlimbs)
     303             :         {
     304         110 :           for (i=0; i < x->nlimbs - nlimbs; i++ )
     305          55 :             x->d[i] = x->d[i+nlimbs];
     306          55 :           x->d[i] = 0;
     307          55 :           x->nlimbs -= nlimbs;
     308             :         }
     309             : 
     310          55 :       if ( x->nlimbs && nbits )
     311          50 :         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
     312             :     }
     313             :   else
     314             :     {
     315             :       /* Copy and shift by less than bits in a limb.  */
     316         320 :       xsize = a->nlimbs;
     317         320 :       x->sign = a->sign;
     318         320 :       RESIZE_IF_NEEDED (x, xsize);
     319         320 :       x->nlimbs = xsize;
     320             : 
     321         320 :       if ( xsize )
     322             :         {
     323         320 :           if (nbits )
     324         315 :             _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
     325             :           else
     326             :             {
     327             :               /* The rshift helper function is not specified for
     328             :                  NBITS==0, thus we do a plain copy here. */
     329          15 :               for (i=0; i < x->nlimbs; i++ )
     330          10 :                 x->d[i] = a->d[i];
     331             :             }
     332             :         }
     333             :     }
     334    10284723 :   MPN_NORMALIZE (x->d, x->nlimbs);
     335             : }
     336             : 
     337             : 
     338             : /****************
     339             :  * Shift A by COUNT limbs to the left
     340             :  * This is used only within the MPI library
     341             :  */
     342             : void
     343     2028728 : _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
     344             : {
     345             :   mpi_ptr_t ap;
     346     2028728 :   int n = a->nlimbs;
     347             :   int i;
     348             : 
     349     2028728 :   if (!count || !n)
     350     2029098 :     return;
     351             : 
     352     2028358 :   RESIZE_IF_NEEDED (a, n+count);
     353             : 
     354     2028358 :   ap = a->d;
     355    10836159 :   for (i = n-1; i >= 0; i--)
     356     8807801 :     ap[i+count] = ap[i];
     357     4401421 :   for (i=0; i < count; i++ )
     358     2373063 :     ap[i] = 0;
     359     2028358 :   a->nlimbs += count;
     360             : }
     361             : 
     362             : 
     363             : /*
     364             :  * Shift A by N bits to the left.
     365             :  */
     366             : void
     367     2033320 : _gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
     368             : {
     369     2033320 :   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
     370     2033320 :   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
     371             : 
     372     2033320 :   if (mpi_is_immutable (x))
     373             :     {
     374           0 :       mpi_immutable_failed ();
     375           0 :       return;
     376             :     }
     377             : 
     378     2033320 :   if (x == a && !n)
     379        4557 :     return;  /* In-place shift with an amount of zero.  */
     380             : 
     381     2028763 :   if ( x != a )
     382             :     {
     383             :       /* Copy A to X.  */
     384     1832842 :       unsigned int alimbs = a->nlimbs;
     385     1832842 :       int asign  = a->sign;
     386             :       mpi_ptr_t xp, ap;
     387             : 
     388     1832842 :       RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
     389     1832842 :       xp = x->d;
     390     1832842 :       ap = a->d;
     391     1832842 :       MPN_COPY (xp, ap, alimbs);
     392     1832842 :       x->nlimbs = alimbs;
     393     1832842 :       x->flags = a->flags;
     394     1832842 :       x->sign = asign;
     395             :     }
     396             : 
     397     2028763 :   if (nlimbs && !nbits)
     398             :     {
     399             :       /* Shift a full number of limbs.  */
     400       14869 :       _gcry_mpi_lshift_limbs (x, nlimbs);
     401             :     }
     402     2013894 :   else if (n)
     403             :     {
     404             :       /* We use a very dump approach: Shift left by the number of
     405             :          limbs plus one and than fix it up by an rshift.  */
     406     2013859 :       _gcry_mpi_lshift_limbs (x, nlimbs+1);
     407     2013859 :       mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
     408             :     }
     409             : 
     410     2028763 :   MPN_NORMALIZE (x->d, x->nlimbs);
     411             : }

Generated by: LCOV version 1.11