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
  99 /*
 100  * Shift A by N bits to the right.
 101  */
 102 int mpi_rshift(MPI x, MPI a, unsigned int n)
 103 {
 104         mpi_size_t xsize;
 105         unsigned int i;
 106         unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 107         unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 108         int err;
 109
 110         if (x == a) {
 111                 /* In-place operation.  */
 112                 if (nlimbs >= x->nlimbs) {
 113                         x->nlimbs = 0;
 114                         return 0;
 115                 }
 116
 117                 if (nlimbs) {
 118                         for (i = 0; i < x->nlimbs - nlimbs; i++)
 119                                 x->d[i] = x->d[i+nlimbs];
 120                         x->d[i] = 0;
 121                         x->nlimbs -= nlimbs;
 122                 }
 123                 if (x->nlimbs && nbits)
 124                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 125         } else if (nlimbs) {
 126                 /* Copy and shift by more or equal bits than in a limb. */
 127                 xsize = a->nlimbs;
 128                 x->sign = a->sign;
 129                 err = RESIZE_IF_NEEDED(x, xsize);
 130                 if (err)
 131                         return err;
 132                 x->nlimbs = xsize;
 133                 for (i = 0; i < a->nlimbs; i++)
 134                         x->d[i] = a->d[i];
 135                 x->nlimbs = i;
 136
 137                 if (nlimbs >= x->nlimbs) {
 138                         x->nlimbs = 0;
 139                         return 0;
 140                 }
 141
 142                 for (i = 0; i < x->nlimbs - nlimbs; i++)
 143                         x->d[i] = x->d[i+nlimbs];
 144                 x->d[i] = 0;
 145                 x->nlimbs -= nlimbs;
 146
 147                 if (x->nlimbs && nbits)
 148                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 149         } else {
 150                 /* Copy and shift by less than bits in a limb.  */
 151                 xsize = a->nlimbs;
 152                 x->sign = a->sign;
 153                 err = RESIZE_IF_NEEDED(x, xsize);
 154                 if (err)
 155                         return err;
 156                 x->nlimbs = xsize;
 157
 158                 if (xsize) {
 159                         if (nbits)
 160                                 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
 161                         else {
 162                                 /* The rshift helper function is not specified for
 163                                  * NBITS==0, thus we do a plain copy here.
 164                                  */
 165                                 for (i = 0; i < x->nlimbs; i++)
 166                                         x->d[i] = a->d[i];
 167                         }
 168                 }
 169         }
 170         MPN_NORMALIZE(x->d, x->nlimbs);
 171
 172         return 0;
 173 }
 174 EXPORT_SYMBOL_GPL(mpi_rshift);