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 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,
  26             5, 5, 5, 5, 5, 5, 5, 5,
  27         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  28             6, 6, 6, 6, 6, 6, 6, 6,
  29         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  30             7, 7, 7, 7, 7, 7, 7, 7,
  31         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  32             7, 7, 7, 7, 7, 7, 7, 7,
  33         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  34             8, 8, 8, 8, 8, 8, 8, 8,
  35         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  36             8, 8, 8, 8, 8, 8, 8, 8,
  37         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  38             8, 8, 8, 8, 8, 8, 8, 8,
  39         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  40             8, 8, 8, 8, 8, 8, 8, 8,
  41 };
  42
  43 #define A_LIMB_1 ((mpi_limb_t) 1)
  44
  45 /****************
  46  * Sometimes we have MSL (most significant limbs) which are 0;
  47  * this is for some reasons not good, so this function removes them.
  48  */
  49 void mpi_normalize(MPI a)
  50 {
  51         for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
  52                 ;
  53 }
  54
  55 /****************
  56  * Return the number of bits in A.
  57  */
  58 unsigned mpi_get_nbits(MPI a)
  59 {
  60         unsigned n;
  61
  62         mpi_normalize(a);
  63
  64         if (a->nlimbs) {
  65                 mpi_limb_t alimb = a->d[a->nlimbs - 1];
  66                 if (alimb)
  67                         count_leading_zeros(n, alimb);
  68                 else
  69                         n = BITS_PER_MPI_LIMB;
  70                 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
  71         } else
  72                 n = 0;
  73         return n;
  74 }
  75 EXPORT_SYMBOL_GPL(mpi_get_nbits);
  76
  77 /****************
  78  * Test whether bit N is set.
  79  */
  80 int 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  * Set bit N of A.
  96  */
  97 int mpi_set_bit(MPI a, unsigned n)
  98 {
  99         unsigned limbno, bitno;
 100
 101         limbno = n / BITS_PER_MPI_LIMB;
 102         bitno = n % BITS_PER_MPI_LIMB;
 103
 104         if (limbno >= a->nlimbs) {      /* resize */
 105                 if (a->alloced >= limbno)
 106                         if (mpi_resize(a, limbno + 1) < 0)
 107                                 return -ENOMEM;
 108                 a->nlimbs = limbno + 1;
 109         }
 110         a->d[limbno] |= (A_LIMB_1 << bitno);
 111         return 0;
 112 }
 113
 114 /****************
 115  * Set bit N of A. and clear all bits above
 116  */
 117 int mpi_set_highbit(MPI a, unsigned n)
 118 {
 119         unsigned limbno, bitno;
 120
 121         limbno = n / BITS_PER_MPI_LIMB;
 122         bitno = n % BITS_PER_MPI_LIMB;
 123
 124         if (limbno >= a->nlimbs) {      /* resize */
 125                 if (a->alloced >= limbno)
 126                         if (mpi_resize(a, limbno + 1) < 0)
 127                                 return -ENOMEM;
 128                 a->nlimbs = limbno + 1;
 129         }
 130         a->d[limbno] |= (A_LIMB_1 << bitno);
 131         for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
 132                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 133         a->nlimbs = limbno + 1;
 134         return 0;
 135 }
 136
 137 /****************
 138  * clear bit N of A and all bits above
 139  */
 140 void mpi_clear_highbit(MPI a, unsigned n)
 141 {
 142         unsigned 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;         /* not allocated, so need to clear bits :-) */
 149
 150         for (; bitno < BITS_PER_MPI_LIMB; bitno++)
 151                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
 152         a->nlimbs = limbno + 1;
 153 }
 154
 155 /****************
 156  * Clear bit N of A.
 157  */
 158 void mpi_clear_bit(MPI a, unsigned n)
 159 {
 160         unsigned limbno, bitno;
 161
 162         limbno = n / BITS_PER_MPI_LIMB;
 163         bitno = n % BITS_PER_MPI_LIMB;
 164
 165         if (limbno >= a->nlimbs)
 166                 return;         /* don't need to clear this bit, it's to far to left */
 167         a->d[limbno] &= ~(A_LIMB_1 << bitno);
 168 }
 169
 170 /****************
 171  * Shift A by N bits to the right
 172  * FIXME: should use alloc_limb if X and A are same.
 173  */
 174 int mpi_rshift(MPI x, MPI a, unsigned n)
 175 {
 176         mpi_ptr_t xp;
 177         mpi_size_t xsize;
 178
 179         xsize = a->nlimbs;
 180         x->sign = a->sign;
 181         if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
 182                 return -ENOMEM;
 183         xp = x->d;
 184
 185         if (xsize) {
 186                 mpihelp_rshift(xp, a->d, xsize, n);
 187                 MPN_NORMALIZE(xp, xsize);
 188         }
 189         x->nlimbs = xsize;
 190         return 0;
 191 }
 192
 193 /****************
 194  * Shift A by COUNT limbs to the left
 195  * This is used only within the MPI library
 196  */
 197 int mpi_lshift_limbs(MPI a, unsigned int count)
 198 {
 199         mpi_ptr_t ap = a->d;
 200         int n = a->nlimbs;
 201         int i;
 202
 203         if (!count || !n)
 204                 return 0;
 205
 206         if (RESIZE_IF_NEEDED(a, n + count) < 0)
 207                 return -ENOMEM;
 208
 209         for (i = n - 1; i >= 0; i--)
 210                 ap[i + count] = ap[i];
 211         for (i = 0; i < count; i++)
 212                 ap[i] = 0;
 213         a->nlimbs += count;
 214         return 0;
 215 }
 216
 217 /****************
 218  * Shift A by COUNT limbs to the right
 219  * This is used only within the MPI library
 220  */
 221 void mpi_rshift_limbs(MPI a, unsigned int count)
 222 {
 223         mpi_ptr_t ap = a->d;
 224         mpi_size_t n = a->nlimbs;
 225         unsigned int i;
 226
 227         if (count >= n) {
 228                 a->nlimbs = 0;
 229                 return;
 230         }
 231
 232         for (i = 0; i < n - count; i++)
 233                 ap[i] = ap[i + count];
 234         ap[i] = 0;
 235         a->nlimbs -= count;
 236 }