lib/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 #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                         count_leading_zeros(n, 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 n)
  62 {
  63         unsigned 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
  75 /****************
  76  * Set bit N of A.
  77  */
  78 int mpi_set_bit(MPI a, unsigned n)
  79 {
  80         unsigned limbno, bitno;
  81
  82         limbno = n / BITS_PER_MPI_LIMB;
  83         bitno = n % BITS_PER_MPI_LIMB;
  84
  85         if (limbno >= a->nlimbs) {      /* resize */
  86                 if (a->alloced >= limbno)
  87                         if (mpi_resize(a, limbno + 1) < 0)
  88                                 return -ENOMEM;
  89                 a->nlimbs = limbno + 1;
  90         }
  91         a->d[limbno] |= (A_LIMB_1 << bitno);
  92         return 0;
  93 }
  94
  95 /****************
  96  * Set bit N of A. and clear all bits above
  97  */
  98 int mpi_set_highbit(MPI a, unsigned n)
  99 {
 100         unsigned limbno, bitno;
 101
 102         limbno = n / BITS_PER_MPI_LIMB;
 103         bitno = n % BITS_PER_MPI_LIMB;
 104
 105         if (limbno >= a->nlimbs) {      /* resize */
 106                 if (a->alloced >= limbno)
 107                         if (mpi_resize(a, limbno + 1) < 0)
 108                                 return -ENOMEM;
 109                 a->nlimbs = limbno + 1;
 110         }
 111         a->d[limbno] |= (A_LIMB_1 << bitno);
 112         for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
 113                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 114         a->nlimbs = limbno + 1;
 115         return 0;
 116 }
 117
 118 /****************
 119  * clear bit N of A and all bits above
 120  */
 121 void mpi_clear_highbit(MPI a, unsigned n)
 122 {
 123         unsigned limbno, bitno;
 124
 125         limbno = n / BITS_PER_MPI_LIMB;
 126         bitno = n % BITS_PER_MPI_LIMB;
 127
 128         if (limbno >= a->nlimbs)
 129                 return;         /* not allocated, so need to clear bits :-) */
 130
 131         for (; bitno < BITS_PER_MPI_LIMB; bitno++)
 132                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 133         a->nlimbs = limbno + 1;
 134 }
 135
 136 /****************
 137  * Clear bit N of A.
 138  */
 139 void mpi_clear_bit(MPI a, unsigned n)
 140 {
 141         unsigned limbno, bitno;
 142
 143         limbno = n / BITS_PER_MPI_LIMB;
 144         bitno = n % BITS_PER_MPI_LIMB;
 145
 146         if (limbno >= a->nlimbs)
 147                 return;         /* don't need to clear this bit, it's to far to left */
 148         a->d[limbno] &= ~(A_LIMB_1 << bitno);
 149 }
 150
 151 /****************
 152  * Shift A by N bits to the right
 153  * FIXME: should use alloc_limb if X and A are same.
 154  */
 155 int mpi_rshift(MPI x, MPI a, unsigned n)
 156 {
 157         mpi_ptr_t xp;
 158         mpi_size_t xsize;
 159
 160         xsize = a->nlimbs;
 161         x->sign = a->sign;
 162         if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
 163                 return -ENOMEM;
 164         xp = x->d;
 165
 166         if (xsize) {
 167                 mpihelp_rshift(xp, a->d, xsize, n);
 168                 MPN_NORMALIZE(xp, xsize);
 169         }
 170         x->nlimbs = xsize;
 171         return 0;
 172 }
 173
 174 /****************
 175  * Shift A by COUNT limbs to the left
 176  * This is used only within the MPI library
 177  */
 178 int mpi_lshift_limbs(MPI a, unsigned int count)
 179 {
 180         mpi_ptr_t ap = a->d;
 181         int n = a->nlimbs;
 182         int i;
 183
 184         if (!count || !n)
 185                 return 0;
 186
 187         if (RESIZE_IF_NEEDED(a, n + count) < 0)
 188                 return -ENOMEM;
 189
 190         for (i = n - 1; i >= 0; i--)
 191                 ap[i + count] = ap[i];
 192         for (i = 0; i < count; i++)
 193                 ap[i] = 0;
 194         a->nlimbs += count;
 195         return 0;
 196 }
 197
 198 /****************
 199  * Shift A by COUNT limbs to the right
 200  * This is used only within the MPI library
 201  */
 202 void mpi_rshift_limbs(MPI a, unsigned int count)
 203 {
 204         mpi_ptr_t ap = a->d;
 205         mpi_size_t n = a->nlimbs;
 206         unsigned int i;
 207
 208         if (count >= n) {
 209                 a->nlimbs = 0;
 210                 return;
 211         }
 212
 213         for (i = 0; i < n - count; i++)
 214                 ap[i] = ap[i + count];
 215         ap[i] = 0;
 216         a->nlimbs -= count;
 217 }