lib/crypto/mpi/mpi-bit.c

   1 /* mpi-bit.c  -  MPI bit level functions
   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 #define A_LIMB_1 ((mpi_limb_t) 1)
  25
  26 /****************
  27  * Sometimes we have MSL (most significant limbs) which are 0;
  28  * this is for some reasons not good, so this function removes them.
  29  */
  30 void mpi_normalize(MPI a)
  31 {
  32         for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
  33                 ;
  34 }
  35
  36 /****************
  37  * Return the number of bits in A.
  38  */
  39 unsigned mpi_get_nbits(MPI a)
  40 {
  41         unsigned n;
  42
  43         mpi_normalize(a);
  44
  45         if (a->nlimbs) {
  46                 mpi_limb_t alimb = a->d[a->nlimbs - 1];
  47                 if (alimb)
  48                         n = count_leading_zeros(alimb);
  49                 else
  50                         n = BITS_PER_MPI_LIMB;
  51                 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
  52         } else
  53                 n = 0;
  54         return n;
  55 }
  56 EXPORT_SYMBOL_GPL(mpi_get_nbits);
  57
  58 /****************
  59  * Test whether bit N is set.
  60  */
  61 int mpi_test_bit(MPI a, unsigned int n)
  62 {
  63         unsigned int limbno, bitno;
  64         mpi_limb_t limb;
  65
  66         limbno = n / BITS_PER_MPI_LIMB;
  67         bitno  = n % BITS_PER_MPI_LIMB;
  68
  69         if (limbno >= a->nlimbs)
  70                 return 0; /* too far left: this is a 0 */
  71         limb = a->d[limbno];
  72         return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
  73 }
  74 EXPORT_SYMBOL_GPL(mpi_test_bit);
  75
  76 /****************
  77  * Set bit N of A.
  78  */
  79 int mpi_set_bit(MPI a, unsigned int n)
  80 {
  81         unsigned int i, limbno, bitno;
  82         int err;
  83
  84         limbno = n / BITS_PER_MPI_LIMB;
  85         bitno  = n % BITS_PER_MPI_LIMB;
  86
  87         if (limbno >= a->nlimbs) {
  88                 for (i = a->nlimbs; i < a->alloced; i++)
  89                         a->d[i] = 0;
  90                 err = mpi_resize(a, limbno+1);
  91                 if (err)
  92                         return err;
  93                 a->nlimbs = limbno+1;
  94         }
  95         a->d[limbno] |= (A_LIMB_1<<bitno);
  96         return 0;
  97 }
  98 EXPORT_SYMBOL_GPL(mpi_set_bit);
  99
 100 /*
 101  * Shift A by N bits to the right.
 102  */
 103 int mpi_rshift(MPI x, MPI a, unsigned int n)
 104 {
 105         mpi_size_t xsize;
 106         unsigned int i;
 107         unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 108         unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 109         int err;
 110
 111         if (x == a) {
 112                 /* In-place operation.  */
 113                 if (nlimbs >= x->nlimbs) {
 114                         x->nlimbs = 0;
 115                         return 0;
 116                 }
 117
 118                 if (nlimbs) {
 119                         for (i = 0; i < x->nlimbs - nlimbs; i++)
 120                                 x->d[i] = x->d[i+nlimbs];
 121                         x->d[i] = 0;
 122                         x->nlimbs -= nlimbs;
 123                 }
 124                 if (x->nlimbs && nbits)
 125                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 126         } else if (nlimbs) {
 127                 /* Copy and shift by more or equal bits than in a limb. */
 128                 xsize = a->nlimbs;
 129                 x->sign = a->sign;
 130                 err = RESIZE_IF_NEEDED(x, xsize);
 131                 if (err)
 132                         return err;
 133                 x->nlimbs = xsize;
 134                 for (i = 0; i < a->nlimbs; i++)
 135                         x->d[i] = a->d[i];
 136                 x->nlimbs = i;
 137
 138                 if (nlimbs >= x->nlimbs) {
 139                         x->nlimbs = 0;
 140                         return 0;
 141                 }
 142
 143                 for (i = 0; i < x->nlimbs - nlimbs; i++)
 144                         x->d[i] = x->d[i+nlimbs];
 145                 x->d[i] = 0;
 146                 x->nlimbs -= nlimbs;
 147
 148                 if (x->nlimbs && nbits)
 149                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 150         } else {
 151                 /* Copy and shift by less than bits in a limb.  */
 152                 xsize = a->nlimbs;
 153                 x->sign = a->sign;
 154                 err = RESIZE_IF_NEEDED(x, xsize);
 155                 if (err)
 156                         return err;
 157                 x->nlimbs = xsize;
 158
 159                 if (xsize) {
 160                         if (nbits)
 161                                 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
 162                         else {
 163                                 /* The rshift helper function is not specified for
 164                                  * NBITS==0, thus we do a plain copy here.
 165                                  */
 166                                 for (i = 0; i < x->nlimbs; i++)
 167                                         x->d[i] = a->d[i];
 168                         }
 169                 }
 170         }
 171         MPN_NORMALIZE(x->d, x->nlimbs);
 172
 173         return 0;
 174 }
 175 EXPORT_SYMBOL_GPL(mpi_rshift);