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  */
mpi_normalize(MPI a)30 void mpi_normalize(MPI a)
31 {
32 	for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
33 		;
34 }
35 EXPORT_SYMBOL_GPL(mpi_normalize);
36 
37 /****************
38  * Return the number of bits in A.
39  */
mpi_get_nbits(MPI a)40 unsigned mpi_get_nbits(MPI a)
41 {
42 	unsigned n;
43 
44 	mpi_normalize(a);
45 
46 	if (a->nlimbs) {
47 		mpi_limb_t alimb = a->d[a->nlimbs - 1];
48 		if (alimb)
49 			n = count_leading_zeros(alimb);
50 		else
51 			n = BITS_PER_MPI_LIMB;
52 		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
53 	} else
54 		n = 0;
55 	return n;
56 }
57 EXPORT_SYMBOL_GPL(mpi_get_nbits);
58 
59 /****************
60  * Test whether bit N is set.
61  */
mpi_test_bit(MPI a,unsigned int n)62 int mpi_test_bit(MPI a, unsigned int n)
63 {
64 	unsigned int limbno, bitno;
65 	mpi_limb_t limb;
66 
67 	limbno = n / BITS_PER_MPI_LIMB;
68 	bitno  = n % BITS_PER_MPI_LIMB;
69 
70 	if (limbno >= a->nlimbs)
71 		return 0; /* too far left: this is a 0 */
72 	limb = a->d[limbno];
73 	return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
74 }
75 EXPORT_SYMBOL_GPL(mpi_test_bit);
76 
77 /****************
78  * Set bit N of A.
79  */
mpi_set_bit(MPI a,unsigned int n)80 void mpi_set_bit(MPI a, unsigned int n)
81 {
82 	unsigned int i, limbno, bitno;
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 		mpi_resize(a, limbno+1);
91 		a->nlimbs = limbno+1;
92 	}
93 	a->d[limbno] |= (A_LIMB_1<<bitno);
94 }
95 
96 /****************
97  * Set bit N of A. and clear all bits above
98  */
mpi_set_highbit(MPI a,unsigned int n)99 void mpi_set_highbit(MPI a, unsigned int n)
100 {
101 	unsigned int i, limbno, bitno;
102 
103 	limbno = n / BITS_PER_MPI_LIMB;
104 	bitno  = n % BITS_PER_MPI_LIMB;
105 
106 	if (limbno >= a->nlimbs) {
107 		for (i = a->nlimbs; i < a->alloced; i++)
108 			a->d[i] = 0;
109 		mpi_resize(a, limbno+1);
110 		a->nlimbs = limbno+1;
111 	}
112 	a->d[limbno] |= (A_LIMB_1<<bitno);
113 	for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
114 		a->d[limbno] &= ~(A_LIMB_1 << bitno);
115 	a->nlimbs = limbno+1;
116 }
117 EXPORT_SYMBOL_GPL(mpi_set_highbit);
118 
119 /****************
120  * clear bit N of A and all bits above
121  */
mpi_clear_highbit(MPI a,unsigned int n)122 void mpi_clear_highbit(MPI a, unsigned int n)
123 {
124 	unsigned int limbno, bitno;
125 
126 	limbno = n / BITS_PER_MPI_LIMB;
127 	bitno  = n % BITS_PER_MPI_LIMB;
128 
129 	if (limbno >= a->nlimbs)
130 		return; /* not allocated, therefore no need to clear bits :-) */
131 
132 	for ( ; bitno < BITS_PER_MPI_LIMB; bitno++)
133 		a->d[limbno] &= ~(A_LIMB_1 << bitno);
134 	a->nlimbs = limbno+1;
135 }
136 
137 /****************
138  * Clear bit N of A.
139  */
mpi_clear_bit(MPI a,unsigned int n)140 void mpi_clear_bit(MPI a, unsigned int n)
141 {
142 	unsigned int 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; /* Don't need to clear this bit, it's far too left.  */
149 	a->d[limbno] &= ~(A_LIMB_1 << bitno);
150 }
151 EXPORT_SYMBOL_GPL(mpi_clear_bit);
152 
153 
154 /****************
155  * Shift A by COUNT limbs to the right
156  * This is used only within the MPI library
157  */
mpi_rshift_limbs(MPI a,unsigned int count)158 void mpi_rshift_limbs(MPI a, unsigned int count)
159 {
160 	mpi_ptr_t ap = a->d;
161 	mpi_size_t n = a->nlimbs;
162 	unsigned int i;
163 
164 	if (count >= n) {
165 		a->nlimbs = 0;
166 		return;
167 	}
168 
169 	for (i = 0; i < n - count; i++)
170 		ap[i] = ap[i+count];
171 	ap[i] = 0;
172 	a->nlimbs -= count;
173 }
174 
175 /*
176  * Shift A by N bits to the right.
177  */
mpi_rshift(MPI x,MPI a,unsigned int n)178 void mpi_rshift(MPI x, MPI a, unsigned int n)
179 {
180 	mpi_size_t xsize;
181 	unsigned int i;
182 	unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
183 	unsigned int nbits = (n%BITS_PER_MPI_LIMB);
184 
185 	if (x == a) {
186 		/* In-place operation.  */
187 		if (nlimbs >= x->nlimbs) {
188 			x->nlimbs = 0;
189 			return;
190 		}
191 
192 		if (nlimbs) {
193 			for (i = 0; i < x->nlimbs - nlimbs; i++)
194 				x->d[i] = x->d[i+nlimbs];
195 			x->d[i] = 0;
196 			x->nlimbs -= nlimbs;
197 		}
198 		if (x->nlimbs && nbits)
199 			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
200 	} else if (nlimbs) {
201 		/* Copy and shift by more or equal bits than in a limb. */
202 		xsize = a->nlimbs;
203 		x->sign = a->sign;
204 		RESIZE_IF_NEEDED(x, xsize);
205 		x->nlimbs = xsize;
206 		for (i = 0; i < a->nlimbs; i++)
207 			x->d[i] = a->d[i];
208 		x->nlimbs = i;
209 
210 		if (nlimbs >= x->nlimbs) {
211 			x->nlimbs = 0;
212 			return;
213 		}
214 
215 		if (nlimbs) {
216 			for (i = 0; i < x->nlimbs - nlimbs; i++)
217 				x->d[i] = x->d[i+nlimbs];
218 			x->d[i] = 0;
219 			x->nlimbs -= nlimbs;
220 		}
221 
222 		if (x->nlimbs && nbits)
223 			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
224 	} else {
225 		/* Copy and shift by less than bits in a limb.  */
226 		xsize = a->nlimbs;
227 		x->sign = a->sign;
228 		RESIZE_IF_NEEDED(x, xsize);
229 		x->nlimbs = xsize;
230 
231 		if (xsize) {
232 			if (nbits)
233 				mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
234 			else {
235 				/* The rshift helper function is not specified for
236 				 * NBITS==0, thus we do a plain copy here.
237 				 */
238 				for (i = 0; i < x->nlimbs; i++)
239 					x->d[i] = a->d[i];
240 			}
241 		}
242 	}
243 	MPN_NORMALIZE(x->d, x->nlimbs);
244 }
245 
246 /****************
247  * Shift A by COUNT limbs to the left
248  * This is used only within the MPI library
249  */
mpi_lshift_limbs(MPI a,unsigned int count)250 void mpi_lshift_limbs(MPI a, unsigned int count)
251 {
252 	mpi_ptr_t ap;
253 	int n = a->nlimbs;
254 	int i;
255 
256 	if (!count || !n)
257 		return;
258 
259 	RESIZE_IF_NEEDED(a, n+count);
260 
261 	ap = a->d;
262 	for (i = n-1; i >= 0; i--)
263 		ap[i+count] = ap[i];
264 	for (i = 0; i < count; i++)
265 		ap[i] = 0;
266 	a->nlimbs += count;
267 }
268 
269 /*
270  * Shift A by N bits to the left.
271  */
mpi_lshift(MPI x,MPI a,unsigned int n)272 void mpi_lshift(MPI x, MPI a, unsigned int n)
273 {
274 	unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
275 	unsigned int nbits = (n%BITS_PER_MPI_LIMB);
276 
277 	if (x == a && !n)
278 		return;  /* In-place shift with an amount of zero.  */
279 
280 	if (x != a) {
281 		/* Copy A to X.  */
282 		unsigned int alimbs = a->nlimbs;
283 		int asign = a->sign;
284 		mpi_ptr_t xp, ap;
285 
286 		RESIZE_IF_NEEDED(x, alimbs+nlimbs+1);
287 		xp = x->d;
288 		ap = a->d;
289 		MPN_COPY(xp, ap, alimbs);
290 		x->nlimbs = alimbs;
291 		x->flags = a->flags;
292 		x->sign = asign;
293 	}
294 
295 	if (nlimbs && !nbits) {
296 		/* Shift a full number of limbs.  */
297 		mpi_lshift_limbs(x, nlimbs);
298 	} else if (n) {
299 		/* We use a very dump approach: Shift left by the number of
300 		 * limbs plus one and than fix it up by an rshift.
301 		 */
302 		mpi_lshift_limbs(x, nlimbs+1);
303 		mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits);
304 	}
305 
306 	MPN_NORMALIZE(x->d, x->nlimbs);
307 }
308