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); 176