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