crypto/mpi/mpi-bit.c

   1 /* mpi-bit.c  -  MPI bit level fucntions
   2  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GnuPG.
   5  *
   6  * GnuPG is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * GnuPG is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  19  */
  20
  21 #include "mpi-internal.h"
  22 #include "longlong.h"
  23
  24 const unsigned char __clz_tab[] = {
  25         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,
  26         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,
  27         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,
  28         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,
  29         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,
  30         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,
  31         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,
  32         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,
  33 };
  34
  35 #define A_LIMB_1 ((mpi_limb_t) 1)
  36
  37
  38 /****************
  39  * Sometimes we have MSL (most significant limbs) which are 0;
  40  * this is for some reasons not good, so this function removes them.
  41  */
  42 void
  43 mpi_normalize( MPI a )
  44 {
  45     for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
  46         ;
  47 }
  48
  49
  50
  51 /****************
  52  * Return the number of bits in A.
  53  */
  54 unsigned
  55 mpi_get_nbits( MPI a )
  56 {
  57     unsigned n;
  58
  59     mpi_normalize( a );
  60
  61     if( a->nlimbs ) {
  62         mpi_limb_t alimb = a->d[a->nlimbs-1];
  63         if( alimb ) {
  64           count_leading_zeros( n, alimb );
  65         }
  66         else
  67             n = BITS_PER_MPI_LIMB;
  68         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
  69     }
  70     else
  71         n = 0;
  72     return n;
  73 }
  74
  75
  76 /****************
  77  * Test whether bit N is set.
  78  */
  79 int
  80 mpi_test_bit( MPI a, unsigned n )
  81 {
  82     unsigned limbno, bitno;
  83     mpi_limb_t limb;
  84
  85     limbno = n / BITS_PER_MPI_LIMB;
  86     bitno  = n % BITS_PER_MPI_LIMB;
  87
  88     if( limbno >= a->nlimbs )
  89         return 0; /* too far left: this is a 0 */
  90     limb = a->d[limbno];
  91     return (limb & (A_LIMB_1 << bitno))? 1: 0;
  92 }
  93
  94
  95 /****************
  96  * Set bit N of A.
  97  */
  98 int
  99 mpi_set_bit( MPI a, unsigned n )
 100 {
 101     unsigned limbno, bitno;
 102
 103     limbno = n / BITS_PER_MPI_LIMB;
 104     bitno  = n % BITS_PER_MPI_LIMB;
 105
 106     if( limbno >= a->nlimbs ) { /* resize */
 107         if( a->alloced >= limbno )
 108             if (mpi_resize(a, limbno+1 ) < 0) return -ENOMEM;
 109         a->nlimbs = limbno+1;
 110     }
 111     a->d[limbno] |= (A_LIMB_1<<bitno);
 112     return 0;
 113 }
 114
 115 /****************
 116  * Set bit N of A. and clear all bits above
 117  */
 118 int
 119 mpi_set_highbit( MPI a, unsigned n )
 120 {
 121     unsigned limbno, bitno;
 122
 123     limbno = n / BITS_PER_MPI_LIMB;
 124     bitno  = n % BITS_PER_MPI_LIMB;
 125
 126     if( limbno >= a->nlimbs ) { /* resize */
 127         if( a->alloced >= limbno )
 128             if (mpi_resize(a, limbno+1 ) < 0) return -ENOMEM;
 129         a->nlimbs = limbno+1;
 130     }
 131     a->d[limbno] |= (A_LIMB_1<<bitno);
 132     for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
 133         a->d[limbno] &= ~(A_LIMB_1 << bitno);
 134     a->nlimbs = limbno+1;
 135     return 0;
 136 }
 137
 138 /****************
 139  * clear bit N of A and all bits above
 140  */
 141 void
 142 mpi_clear_highbit( MPI a, unsigned n )
 143 {
 144     unsigned limbno, bitno;
 145
 146     limbno = n / BITS_PER_MPI_LIMB;
 147     bitno  = n % BITS_PER_MPI_LIMB;
 148
 149     if( limbno >= a->nlimbs )
 150         return; /* not allocated, so need to clear bits :-) */
 151
 152     for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
 153         a->d[limbno] &= ~(A_LIMB_1 << bitno);
 154     a->nlimbs = limbno+1;
 155 }
 156
 157 /****************
 158  * Clear bit N of A.
 159  */
 160 void
 161 mpi_clear_bit( MPI a, unsigned n )
 162 {
 163     unsigned limbno, bitno;
 164
 165     limbno = n / BITS_PER_MPI_LIMB;
 166     bitno  = n % BITS_PER_MPI_LIMB;
 167
 168     if( limbno >= a->nlimbs )
 169         return; /* don't need to clear this bit, it's to far to left */
 170     a->d[limbno] &= ~(A_LIMB_1 << bitno);
 171 }
 172
 173
 174 /****************
 175  * Shift A by N bits to the right
 176  * FIXME: should use alloc_limb if X and A are same.
 177  */
 178 int
 179 mpi_rshift( MPI x, MPI a, unsigned n )
 180 {
 181     mpi_ptr_t xp;
 182     mpi_size_t xsize;
 183
 184     xsize = a->nlimbs;
 185     x->sign = a->sign;
 186     if (RESIZE_IF_NEEDED(x, (size_t)xsize) < 0) return -ENOMEM;
 187     xp = x->d;
 188
 189     if( xsize ) {
 190         mpihelp_rshift( xp, a->d, xsize, n);
 191         MPN_NORMALIZE( xp, xsize);
 192     }
 193     x->nlimbs = xsize;
 194     return 0;
 195 }
 196
 197
 198 /****************
 199  * Shift A by COUNT limbs to the left
 200  * This is used only within the MPI library
 201  */
 202 int
 203 mpi_lshift_limbs( MPI a, unsigned int count )
 204 {
 205     mpi_ptr_t ap = a->d;
 206     int n = a->nlimbs;
 207     int i;
 208
 209     if( !count || !n )
 210         return 0;
 211
 212     if (RESIZE_IF_NEEDED( a, n+count ) < 0) return -ENOMEM;
 213
 214     for( i = n-1; i >= 0; i-- )
 215         ap[i+count] = ap[i];
 216     for(i=0; i < count; i++ )
 217         ap[i] = 0;
 218     a->nlimbs += count;
 219     return 0;
 220 }
 221
 222
 223 /****************
 224  * Shift A by COUNT limbs to the right
 225  * This is used only within the MPI library
 226  */
 227 void
 228 mpi_rshift_limbs( MPI a, unsigned int count )
 229 {
 230     mpi_ptr_t ap = a->d;
 231     mpi_size_t n = a->nlimbs;
 232     unsigned int i;
 233
 234     if( count >= n ) {
 235         a->nlimbs = 0;
 236         return;
 237     }
 238
 239     for( i = 0; i < n - count; i++ )
 240         ap[i] = ap[i+count];
 241     ap[i] = 0;
 242     a->nlimbs -= count;
 243 }
 244
 245