lib/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 EXPORT_SYMBOL_GPL(mpi_normalize);
  36
  37 /****************
  38  * Return the number of bits in A.
  39  */
  40 unsigned mpi_get_nbits(MPI a)
  41 {
  42         unsigned n;
  43
  44         mpi_normalize(a);
  45
  46         if (a->nlimbs) {
  47                 mpi_limb_t alimb = a->d[a->nlimbs - 1];
  48                 if (alimb)
  49                         n = count_leading_zeros(alimb);
  50                 else
  51                         n = BITS_PER_MPI_LIMB;
  52                 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
  53         } else
  54                 n = 0;
  55         return n;
  56 }
  57 EXPORT_SYMBOL_GPL(mpi_get_nbits);
  58
  59 /****************
  60  * Test whether bit N is set.
  61  */
  62 int mpi_test_bit(MPI a, unsigned int n)
  63 {
  64         unsigned int limbno, bitno;
  65         mpi_limb_t limb;
  66
  67         limbno = n / BITS_PER_MPI_LIMB;
  68         bitno  = n % BITS_PER_MPI_LIMB;
  69
  70         if (limbno >= a->nlimbs)
  71                 return 0; /* too far left: this is a 0 */
  72         limb = a->d[limbno];
  73         return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
  74 }
  75 EXPORT_SYMBOL_GPL(mpi_test_bit);
  76
  77 /****************
  78  * Set bit N of A.
  79  */
  80 void mpi_set_bit(MPI a, unsigned int n)
  81 {
  82         unsigned int i, limbno, bitno;
  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                 mpi_resize(a, limbno+1);
  91                 a->nlimbs = limbno+1;
  92         }
  93         a->d[limbno] |= (A_LIMB_1<<bitno);
  94 }
  95
  96 /****************
  97  * Set bit N of A. and clear all bits above
  98  */
  99 void mpi_set_highbit(MPI a, unsigned int n)
 100 {
 101         unsigned int i, limbno, bitno;
 102
 103         limbno = n / BITS_PER_MPI_LIMB;
 104         bitno  = n % BITS_PER_MPI_LIMB;
 105
 106         if (limbno >= a->nlimbs) {
 107                 for (i = a->nlimbs; i < a->alloced; i++)
 108                         a->d[i] = 0;
 109                 mpi_resize(a, limbno+1);
 110                 a->nlimbs = limbno+1;
 111         }
 112         a->d[limbno] |= (A_LIMB_1<<bitno);
 113         for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
 114                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 115         a->nlimbs = limbno+1;
 116 }
 117 EXPORT_SYMBOL_GPL(mpi_set_highbit);
 118
 119 /****************
 120  * clear bit N of A and all bits above
 121  */
 122 void mpi_clear_highbit(MPI a, unsigned int n)
 123 {
 124         unsigned int limbno, bitno;
 125
 126         limbno = n / BITS_PER_MPI_LIMB;
 127         bitno  = n % BITS_PER_MPI_LIMB;
 128
 129         if (limbno >= a->nlimbs)
 130                 return; /* not allocated, therefore no need to clear bits :-) */
 131
 132         for ( ; bitno < BITS_PER_MPI_LIMB; bitno++)
 133                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 134         a->nlimbs = limbno+1;
 135 }
 136
 137 /****************
 138  * Clear bit N of A.
 139  */
 140 void mpi_clear_bit(MPI a, unsigned int n)
 141 {
 142         unsigned int limbno, bitno;
 143
 144         limbno = n / BITS_PER_MPI_LIMB;
 145         bitno  = n % BITS_PER_MPI_LIMB;
 146
 147         if (limbno >= a->nlimbs)
 148                 return; /* Don't need to clear this bit, it's far too left.  */
 149         a->d[limbno] &= ~(A_LIMB_1 << bitno);
 150 }
 151 EXPORT_SYMBOL_GPL(mpi_clear_bit);
 152
 153
 154 /****************
 155  * Shift A by COUNT limbs to the right
 156  * This is used only within the MPI library
 157  */
 158 void mpi_rshift_limbs(MPI a, unsigned int count)
 159 {
 160         mpi_ptr_t ap = a->d;
 161         mpi_size_t n = a->nlimbs;
 162         unsigned int i;
 163
 164         if (count >= n) {
 165                 a->nlimbs = 0;
 166                 return;
 167         }
 168
 169         for (i = 0; i < n - count; i++)
 170                 ap[i] = ap[i+count];
 171         ap[i] = 0;
 172         a->nlimbs -= count;
 173 }
 174
 175 /*
 176  * Shift A by N bits to the right.
 177  */
 178 void mpi_rshift(MPI x, MPI a, unsigned int n)
 179 {
 180         mpi_size_t xsize;
 181         unsigned int i;
 182         unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 183         unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 184
 185         if (x == a) {
 186                 /* In-place operation.  */
 187                 if (nlimbs >= x->nlimbs) {
 188                         x->nlimbs = 0;
 189                         return;
 190                 }
 191
 192                 if (nlimbs) {
 193                         for (i = 0; i < x->nlimbs - nlimbs; i++)
 194                                 x->d[i] = x->d[i+nlimbs];
 195                         x->d[i] = 0;
 196                         x->nlimbs -= nlimbs;
 197                 }
 198                 if (x->nlimbs && nbits)
 199                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 200         } else if (nlimbs) {
 201                 /* Copy and shift by more or equal bits than in a limb. */
 202                 xsize = a->nlimbs;
 203                 x->sign = a->sign;
 204                 RESIZE_IF_NEEDED(x, xsize);
 205                 x->nlimbs = xsize;
 206                 for (i = 0; i < a->nlimbs; i++)
 207                         x->d[i] = a->d[i];
 208                 x->nlimbs = i;
 209
 210                 if (nlimbs >= x->nlimbs) {
 211                         x->nlimbs = 0;
 212                         return;
 213                 }
 214
 215                 if (nlimbs) {
 216                         for (i = 0; i < x->nlimbs - nlimbs; i++)
 217                                 x->d[i] = x->d[i+nlimbs];
 218                         x->d[i] = 0;
 219                         x->nlimbs -= nlimbs;
 220                 }
 221
 222                 if (x->nlimbs && nbits)
 223                         mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
 224         } else {
 225                 /* Copy and shift by less than bits in a limb.  */
 226                 xsize = a->nlimbs;
 227                 x->sign = a->sign;
 228                 RESIZE_IF_NEEDED(x, xsize);
 229                 x->nlimbs = xsize;
 230
 231                 if (xsize) {
 232                         if (nbits)
 233                                 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
 234                         else {
 235                                 /* The rshift helper function is not specified for
 236                                  * NBITS==0, thus we do a plain copy here.
 237                                  */
 238                                 for (i = 0; i < x->nlimbs; i++)
 239                                         x->d[i] = a->d[i];
 240                         }
 241                 }
 242         }
 243         MPN_NORMALIZE(x->d, x->nlimbs);
 244 }
 245
 246 /****************
 247  * Shift A by COUNT limbs to the left
 248  * This is used only within the MPI library
 249  */
 250 void mpi_lshift_limbs(MPI a, unsigned int count)
 251 {
 252         mpi_ptr_t ap;
 253         int n = a->nlimbs;
 254         int i;
 255
 256         if (!count || !n)
 257                 return;
 258
 259         RESIZE_IF_NEEDED(a, n+count);
 260
 261         ap = a->d;
 262         for (i = n-1; i >= 0; i--)
 263                 ap[i+count] = ap[i];
 264         for (i = 0; i < count; i++)
 265                 ap[i] = 0;
 266         a->nlimbs += count;
 267 }
 268
 269 /*
 270  * Shift A by N bits to the left.
 271  */
 272 void mpi_lshift(MPI x, MPI a, unsigned int n)
 273 {
 274         unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
 275         unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 276
 277         if (x == a && !n)
 278                 return;  /* In-place shift with an amount of zero.  */
 279
 280         if (x != a) {
 281                 /* Copy A to X.  */
 282                 unsigned int alimbs = a->nlimbs;
 283                 int asign = a->sign;
 284                 mpi_ptr_t xp, ap;
 285
 286                 RESIZE_IF_NEEDED(x, alimbs+nlimbs+1);
 287                 xp = x->d;
 288                 ap = a->d;
 289                 MPN_COPY(xp, ap, alimbs);
 290                 x->nlimbs = alimbs;
 291                 x->flags = a->flags;
 292                 x->sign = asign;
 293         }
 294
 295         if (nlimbs && !nbits) {
 296                 /* Shift a full number of limbs.  */
 297                 mpi_lshift_limbs(x, nlimbs);
 298         } else if (n) {
 299                 /* We use a very dump approach: Shift left by the number of
 300                  * limbs plus one and than fix it up by an rshift.
 301                  */
 302                 mpi_lshift_limbs(x, nlimbs+1);
 303                 mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits);
 304         }
 305
 306         MPN_NORMALIZE(x->d, x->nlimbs);
 307 }