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 <linux/export.h> 22 23 #include "mpi-internal.h" 24 #include "longlong.h" 25 26 #define A_LIMB_1 ((mpi_limb_t) 1) 27 28 /**************** 29 * Sometimes we have MSL (most significant limbs) which are 0; 30 * this is for some reasons not good, so this function removes them. 31 */ 32 void mpi_normalize(MPI a) 33 { 34 for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--) 35 ; 36 } 37 38 /**************** 39 * Return the number of bits in A. 40 */ 41 unsigned mpi_get_nbits(MPI a) 42 { 43 unsigned n; 44 45 mpi_normalize(a); 46 47 if (a->nlimbs) { 48 mpi_limb_t alimb = a->d[a->nlimbs - 1]; 49 if (alimb) 50 n = count_leading_zeros(alimb); 51 else 52 n = BITS_PER_MPI_LIMB; 53 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB; 54 } else 55 n = 0; 56 return n; 57 } 58 EXPORT_SYMBOL_GPL(mpi_get_nbits); 59 60 /**************** 61 * Test whether bit N is set. 62 */ 63 int mpi_test_bit(MPI a, unsigned int n) 64 { 65 unsigned int limbno, bitno; 66 mpi_limb_t limb; 67 68 limbno = n / BITS_PER_MPI_LIMB; 69 bitno = n % BITS_PER_MPI_LIMB; 70 71 if (limbno >= a->nlimbs) 72 return 0; /* too far left: this is a 0 */ 73 limb = a->d[limbno]; 74 return (limb & (A_LIMB_1 << bitno)) ? 1 : 0; 75 } 76 EXPORT_SYMBOL_GPL(mpi_test_bit); 77 78 /**************** 79 * Set bit N of A. 80 */ 81 int mpi_set_bit(MPI a, unsigned int n) 82 { 83 unsigned int i, limbno, bitno; 84 int err; 85 86 limbno = n / BITS_PER_MPI_LIMB; 87 bitno = n % BITS_PER_MPI_LIMB; 88 89 if (limbno >= a->nlimbs) { 90 for (i = a->nlimbs; i < a->alloced; i++) 91 a->d[i] = 0; 92 err = mpi_resize(a, limbno+1); 93 if (err) 94 return err; 95 a->nlimbs = limbno+1; 96 } 97 a->d[limbno] |= (A_LIMB_1<<bitno); 98 return 0; 99 } 100 EXPORT_SYMBOL_GPL(mpi_set_bit); 101 102 /* 103 * Shift A by N bits to the right. 104 */ 105 int mpi_rshift(MPI x, MPI a, unsigned int n) 106 { 107 mpi_size_t xsize; 108 unsigned int i; 109 unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); 110 unsigned int nbits = (n%BITS_PER_MPI_LIMB); 111 int err; 112 113 if (x == a) { 114 /* In-place operation. */ 115 if (nlimbs >= x->nlimbs) { 116 x->nlimbs = 0; 117 return 0; 118 } 119 120 if (nlimbs) { 121 for (i = 0; i < x->nlimbs - nlimbs; i++) 122 x->d[i] = x->d[i+nlimbs]; 123 x->d[i] = 0; 124 x->nlimbs -= nlimbs; 125 } 126 if (x->nlimbs && nbits) 127 mpihelp_rshift(x->d, x->d, x->nlimbs, nbits); 128 } else if (nlimbs) { 129 /* Copy and shift by more or equal bits than in a limb. */ 130 xsize = a->nlimbs; 131 x->sign = a->sign; 132 err = RESIZE_IF_NEEDED(x, xsize); 133 if (err) 134 return err; 135 x->nlimbs = xsize; 136 for (i = 0; i < a->nlimbs; i++) 137 x->d[i] = a->d[i]; 138 x->nlimbs = i; 139 140 if (nlimbs >= x->nlimbs) { 141 x->nlimbs = 0; 142 return 0; 143 } 144 145 for (i = 0; i < x->nlimbs - nlimbs; i++) 146 x->d[i] = x->d[i+nlimbs]; 147 x->d[i] = 0; 148 x->nlimbs -= nlimbs; 149 150 if (x->nlimbs && nbits) 151 mpihelp_rshift(x->d, x->d, x->nlimbs, nbits); 152 } else { 153 /* Copy and shift by less than bits in a limb. */ 154 xsize = a->nlimbs; 155 x->sign = a->sign; 156 err = RESIZE_IF_NEEDED(x, xsize); 157 if (err) 158 return err; 159 x->nlimbs = xsize; 160 161 if (xsize) { 162 if (nbits) 163 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits); 164 else { 165 /* The rshift helper function is not specified for 166 * NBITS==0, thus we do a plain copy here. 167 */ 168 for (i = 0; i < x->nlimbs; i++) 169 x->d[i] = a->d[i]; 170 } 171 } 172 } 173 MPN_NORMALIZE(x->d, x->nlimbs); 174 175 return 0; 176 } 177 EXPORT_SYMBOL_GPL(mpi_rshift); 178