1*2a598d0bSHerbert Xu /* mpi-bit.c - MPI bit level functions
2*2a598d0bSHerbert Xu * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3*2a598d0bSHerbert Xu *
4*2a598d0bSHerbert Xu * This file is part of GnuPG.
5*2a598d0bSHerbert Xu *
6*2a598d0bSHerbert Xu * GnuPG is free software; you can redistribute it and/or modify
7*2a598d0bSHerbert Xu * it under the terms of the GNU General Public License as published by
8*2a598d0bSHerbert Xu * the Free Software Foundation; either version 2 of the License, or
9*2a598d0bSHerbert Xu * (at your option) any later version.
10*2a598d0bSHerbert Xu *
11*2a598d0bSHerbert Xu * GnuPG is distributed in the hope that it will be useful,
12*2a598d0bSHerbert Xu * but WITHOUT ANY WARRANTY; without even the implied warranty of
13*2a598d0bSHerbert Xu * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14*2a598d0bSHerbert Xu * GNU General Public License for more details.
15*2a598d0bSHerbert Xu *
16*2a598d0bSHerbert Xu * You should have received a copy of the GNU General Public License
17*2a598d0bSHerbert Xu * along with this program; if not, write to the Free Software
18*2a598d0bSHerbert Xu * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19*2a598d0bSHerbert Xu */
20*2a598d0bSHerbert Xu
21*2a598d0bSHerbert Xu #include "mpi-internal.h"
22*2a598d0bSHerbert Xu #include "longlong.h"
23*2a598d0bSHerbert Xu
24*2a598d0bSHerbert Xu #define A_LIMB_1 ((mpi_limb_t) 1)
25*2a598d0bSHerbert Xu
26*2a598d0bSHerbert Xu /****************
27*2a598d0bSHerbert Xu * Sometimes we have MSL (most significant limbs) which are 0;
28*2a598d0bSHerbert Xu * this is for some reasons not good, so this function removes them.
29*2a598d0bSHerbert Xu */
mpi_normalize(MPI a)30*2a598d0bSHerbert Xu void mpi_normalize(MPI a)
31*2a598d0bSHerbert Xu {
32*2a598d0bSHerbert Xu for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
33*2a598d0bSHerbert Xu ;
34*2a598d0bSHerbert Xu }
35*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_normalize);
36*2a598d0bSHerbert Xu
37*2a598d0bSHerbert Xu /****************
38*2a598d0bSHerbert Xu * Return the number of bits in A.
39*2a598d0bSHerbert Xu */
mpi_get_nbits(MPI a)40*2a598d0bSHerbert Xu unsigned mpi_get_nbits(MPI a)
41*2a598d0bSHerbert Xu {
42*2a598d0bSHerbert Xu unsigned n;
43*2a598d0bSHerbert Xu
44*2a598d0bSHerbert Xu mpi_normalize(a);
45*2a598d0bSHerbert Xu
46*2a598d0bSHerbert Xu if (a->nlimbs) {
47*2a598d0bSHerbert Xu mpi_limb_t alimb = a->d[a->nlimbs - 1];
48*2a598d0bSHerbert Xu if (alimb)
49*2a598d0bSHerbert Xu n = count_leading_zeros(alimb);
50*2a598d0bSHerbert Xu else
51*2a598d0bSHerbert Xu n = BITS_PER_MPI_LIMB;
52*2a598d0bSHerbert Xu n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
53*2a598d0bSHerbert Xu } else
54*2a598d0bSHerbert Xu n = 0;
55*2a598d0bSHerbert Xu return n;
56*2a598d0bSHerbert Xu }
57*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_get_nbits);
58*2a598d0bSHerbert Xu
59*2a598d0bSHerbert Xu /****************
60*2a598d0bSHerbert Xu * Test whether bit N is set.
61*2a598d0bSHerbert Xu */
mpi_test_bit(MPI a,unsigned int n)62*2a598d0bSHerbert Xu int mpi_test_bit(MPI a, unsigned int n)
63*2a598d0bSHerbert Xu {
64*2a598d0bSHerbert Xu unsigned int limbno, bitno;
65*2a598d0bSHerbert Xu mpi_limb_t limb;
66*2a598d0bSHerbert Xu
67*2a598d0bSHerbert Xu limbno = n / BITS_PER_MPI_LIMB;
68*2a598d0bSHerbert Xu bitno = n % BITS_PER_MPI_LIMB;
69*2a598d0bSHerbert Xu
70*2a598d0bSHerbert Xu if (limbno >= a->nlimbs)
71*2a598d0bSHerbert Xu return 0; /* too far left: this is a 0 */
72*2a598d0bSHerbert Xu limb = a->d[limbno];
73*2a598d0bSHerbert Xu return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
74*2a598d0bSHerbert Xu }
75*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_test_bit);
76*2a598d0bSHerbert Xu
77*2a598d0bSHerbert Xu /****************
78*2a598d0bSHerbert Xu * Set bit N of A.
79*2a598d0bSHerbert Xu */
mpi_set_bit(MPI a,unsigned int n)80*2a598d0bSHerbert Xu void mpi_set_bit(MPI a, unsigned int n)
81*2a598d0bSHerbert Xu {
82*2a598d0bSHerbert Xu unsigned int i, limbno, bitno;
83*2a598d0bSHerbert Xu
84*2a598d0bSHerbert Xu limbno = n / BITS_PER_MPI_LIMB;
85*2a598d0bSHerbert Xu bitno = n % BITS_PER_MPI_LIMB;
86*2a598d0bSHerbert Xu
87*2a598d0bSHerbert Xu if (limbno >= a->nlimbs) {
88*2a598d0bSHerbert Xu for (i = a->nlimbs; i < a->alloced; i++)
89*2a598d0bSHerbert Xu a->d[i] = 0;
90*2a598d0bSHerbert Xu mpi_resize(a, limbno+1);
91*2a598d0bSHerbert Xu a->nlimbs = limbno+1;
92*2a598d0bSHerbert Xu }
93*2a598d0bSHerbert Xu a->d[limbno] |= (A_LIMB_1<<bitno);
94*2a598d0bSHerbert Xu }
95*2a598d0bSHerbert Xu
96*2a598d0bSHerbert Xu /****************
97*2a598d0bSHerbert Xu * Set bit N of A. and clear all bits above
98*2a598d0bSHerbert Xu */
mpi_set_highbit(MPI a,unsigned int n)99*2a598d0bSHerbert Xu void mpi_set_highbit(MPI a, unsigned int n)
100*2a598d0bSHerbert Xu {
101*2a598d0bSHerbert Xu unsigned int i, limbno, bitno;
102*2a598d0bSHerbert Xu
103*2a598d0bSHerbert Xu limbno = n / BITS_PER_MPI_LIMB;
104*2a598d0bSHerbert Xu bitno = n % BITS_PER_MPI_LIMB;
105*2a598d0bSHerbert Xu
106*2a598d0bSHerbert Xu if (limbno >= a->nlimbs) {
107*2a598d0bSHerbert Xu for (i = a->nlimbs; i < a->alloced; i++)
108*2a598d0bSHerbert Xu a->d[i] = 0;
109*2a598d0bSHerbert Xu mpi_resize(a, limbno+1);
110*2a598d0bSHerbert Xu a->nlimbs = limbno+1;
111*2a598d0bSHerbert Xu }
112*2a598d0bSHerbert Xu a->d[limbno] |= (A_LIMB_1<<bitno);
113*2a598d0bSHerbert Xu for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
114*2a598d0bSHerbert Xu a->d[limbno] &= ~(A_LIMB_1 << bitno);
115*2a598d0bSHerbert Xu a->nlimbs = limbno+1;
116*2a598d0bSHerbert Xu }
117*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_set_highbit);
118*2a598d0bSHerbert Xu
119*2a598d0bSHerbert Xu /****************
120*2a598d0bSHerbert Xu * clear bit N of A and all bits above
121*2a598d0bSHerbert Xu */
mpi_clear_highbit(MPI a,unsigned int n)122*2a598d0bSHerbert Xu void mpi_clear_highbit(MPI a, unsigned int n)
123*2a598d0bSHerbert Xu {
124*2a598d0bSHerbert Xu unsigned int limbno, bitno;
125*2a598d0bSHerbert Xu
126*2a598d0bSHerbert Xu limbno = n / BITS_PER_MPI_LIMB;
127*2a598d0bSHerbert Xu bitno = n % BITS_PER_MPI_LIMB;
128*2a598d0bSHerbert Xu
129*2a598d0bSHerbert Xu if (limbno >= a->nlimbs)
130*2a598d0bSHerbert Xu return; /* not allocated, therefore no need to clear bits :-) */
131*2a598d0bSHerbert Xu
132*2a598d0bSHerbert Xu for ( ; bitno < BITS_PER_MPI_LIMB; bitno++)
133*2a598d0bSHerbert Xu a->d[limbno] &= ~(A_LIMB_1 << bitno);
134*2a598d0bSHerbert Xu a->nlimbs = limbno+1;
135*2a598d0bSHerbert Xu }
136*2a598d0bSHerbert Xu
137*2a598d0bSHerbert Xu /****************
138*2a598d0bSHerbert Xu * Clear bit N of A.
139*2a598d0bSHerbert Xu */
mpi_clear_bit(MPI a,unsigned int n)140*2a598d0bSHerbert Xu void mpi_clear_bit(MPI a, unsigned int n)
141*2a598d0bSHerbert Xu {
142*2a598d0bSHerbert Xu unsigned int limbno, bitno;
143*2a598d0bSHerbert Xu
144*2a598d0bSHerbert Xu limbno = n / BITS_PER_MPI_LIMB;
145*2a598d0bSHerbert Xu bitno = n % BITS_PER_MPI_LIMB;
146*2a598d0bSHerbert Xu
147*2a598d0bSHerbert Xu if (limbno >= a->nlimbs)
148*2a598d0bSHerbert Xu return; /* Don't need to clear this bit, it's far too left. */
149*2a598d0bSHerbert Xu a->d[limbno] &= ~(A_LIMB_1 << bitno);
150*2a598d0bSHerbert Xu }
151*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_clear_bit);
152*2a598d0bSHerbert Xu
153*2a598d0bSHerbert Xu
154*2a598d0bSHerbert Xu /****************
155*2a598d0bSHerbert Xu * Shift A by COUNT limbs to the right
156*2a598d0bSHerbert Xu * This is used only within the MPI library
157*2a598d0bSHerbert Xu */
mpi_rshift_limbs(MPI a,unsigned int count)158*2a598d0bSHerbert Xu void mpi_rshift_limbs(MPI a, unsigned int count)
159*2a598d0bSHerbert Xu {
160*2a598d0bSHerbert Xu mpi_ptr_t ap = a->d;
161*2a598d0bSHerbert Xu mpi_size_t n = a->nlimbs;
162*2a598d0bSHerbert Xu unsigned int i;
163*2a598d0bSHerbert Xu
164*2a598d0bSHerbert Xu if (count >= n) {
165*2a598d0bSHerbert Xu a->nlimbs = 0;
166*2a598d0bSHerbert Xu return;
167*2a598d0bSHerbert Xu }
168*2a598d0bSHerbert Xu
169*2a598d0bSHerbert Xu for (i = 0; i < n - count; i++)
170*2a598d0bSHerbert Xu ap[i] = ap[i+count];
171*2a598d0bSHerbert Xu ap[i] = 0;
172*2a598d0bSHerbert Xu a->nlimbs -= count;
173*2a598d0bSHerbert Xu }
174*2a598d0bSHerbert Xu
175*2a598d0bSHerbert Xu /*
176*2a598d0bSHerbert Xu * Shift A by N bits to the right.
177*2a598d0bSHerbert Xu */
mpi_rshift(MPI x,MPI a,unsigned int n)178*2a598d0bSHerbert Xu void mpi_rshift(MPI x, MPI a, unsigned int n)
179*2a598d0bSHerbert Xu {
180*2a598d0bSHerbert Xu mpi_size_t xsize;
181*2a598d0bSHerbert Xu unsigned int i;
182*2a598d0bSHerbert Xu unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
183*2a598d0bSHerbert Xu unsigned int nbits = (n%BITS_PER_MPI_LIMB);
184*2a598d0bSHerbert Xu
185*2a598d0bSHerbert Xu if (x == a) {
186*2a598d0bSHerbert Xu /* In-place operation. */
187*2a598d0bSHerbert Xu if (nlimbs >= x->nlimbs) {
188*2a598d0bSHerbert Xu x->nlimbs = 0;
189*2a598d0bSHerbert Xu return;
190*2a598d0bSHerbert Xu }
191*2a598d0bSHerbert Xu
192*2a598d0bSHerbert Xu if (nlimbs) {
193*2a598d0bSHerbert Xu for (i = 0; i < x->nlimbs - nlimbs; i++)
194*2a598d0bSHerbert Xu x->d[i] = x->d[i+nlimbs];
195*2a598d0bSHerbert Xu x->d[i] = 0;
196*2a598d0bSHerbert Xu x->nlimbs -= nlimbs;
197*2a598d0bSHerbert Xu }
198*2a598d0bSHerbert Xu if (x->nlimbs && nbits)
199*2a598d0bSHerbert Xu mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
200*2a598d0bSHerbert Xu } else if (nlimbs) {
201*2a598d0bSHerbert Xu /* Copy and shift by more or equal bits than in a limb. */
202*2a598d0bSHerbert Xu xsize = a->nlimbs;
203*2a598d0bSHerbert Xu x->sign = a->sign;
204*2a598d0bSHerbert Xu RESIZE_IF_NEEDED(x, xsize);
205*2a598d0bSHerbert Xu x->nlimbs = xsize;
206*2a598d0bSHerbert Xu for (i = 0; i < a->nlimbs; i++)
207*2a598d0bSHerbert Xu x->d[i] = a->d[i];
208*2a598d0bSHerbert Xu x->nlimbs = i;
209*2a598d0bSHerbert Xu
210*2a598d0bSHerbert Xu if (nlimbs >= x->nlimbs) {
211*2a598d0bSHerbert Xu x->nlimbs = 0;
212*2a598d0bSHerbert Xu return;
213*2a598d0bSHerbert Xu }
214*2a598d0bSHerbert Xu
215*2a598d0bSHerbert Xu if (nlimbs) {
216*2a598d0bSHerbert Xu for (i = 0; i < x->nlimbs - nlimbs; i++)
217*2a598d0bSHerbert Xu x->d[i] = x->d[i+nlimbs];
218*2a598d0bSHerbert Xu x->d[i] = 0;
219*2a598d0bSHerbert Xu x->nlimbs -= nlimbs;
220*2a598d0bSHerbert Xu }
221*2a598d0bSHerbert Xu
222*2a598d0bSHerbert Xu if (x->nlimbs && nbits)
223*2a598d0bSHerbert Xu mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
224*2a598d0bSHerbert Xu } else {
225*2a598d0bSHerbert Xu /* Copy and shift by less than bits in a limb. */
226*2a598d0bSHerbert Xu xsize = a->nlimbs;
227*2a598d0bSHerbert Xu x->sign = a->sign;
228*2a598d0bSHerbert Xu RESIZE_IF_NEEDED(x, xsize);
229*2a598d0bSHerbert Xu x->nlimbs = xsize;
230*2a598d0bSHerbert Xu
231*2a598d0bSHerbert Xu if (xsize) {
232*2a598d0bSHerbert Xu if (nbits)
233*2a598d0bSHerbert Xu mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
234*2a598d0bSHerbert Xu else {
235*2a598d0bSHerbert Xu /* The rshift helper function is not specified for
236*2a598d0bSHerbert Xu * NBITS==0, thus we do a plain copy here.
237*2a598d0bSHerbert Xu */
238*2a598d0bSHerbert Xu for (i = 0; i < x->nlimbs; i++)
239*2a598d0bSHerbert Xu x->d[i] = a->d[i];
240*2a598d0bSHerbert Xu }
241*2a598d0bSHerbert Xu }
242*2a598d0bSHerbert Xu }
243*2a598d0bSHerbert Xu MPN_NORMALIZE(x->d, x->nlimbs);
244*2a598d0bSHerbert Xu }
245*2a598d0bSHerbert Xu EXPORT_SYMBOL_GPL(mpi_rshift);
246*2a598d0bSHerbert Xu
247*2a598d0bSHerbert Xu /****************
248*2a598d0bSHerbert Xu * Shift A by COUNT limbs to the left
249*2a598d0bSHerbert Xu * This is used only within the MPI library
250*2a598d0bSHerbert Xu */
mpi_lshift_limbs(MPI a,unsigned int count)251*2a598d0bSHerbert Xu void mpi_lshift_limbs(MPI a, unsigned int count)
252*2a598d0bSHerbert Xu {
253*2a598d0bSHerbert Xu mpi_ptr_t ap;
254*2a598d0bSHerbert Xu int n = a->nlimbs;
255*2a598d0bSHerbert Xu int i;
256*2a598d0bSHerbert Xu
257*2a598d0bSHerbert Xu if (!count || !n)
258*2a598d0bSHerbert Xu return;
259*2a598d0bSHerbert Xu
260*2a598d0bSHerbert Xu RESIZE_IF_NEEDED(a, n+count);
261*2a598d0bSHerbert Xu
262*2a598d0bSHerbert Xu ap = a->d;
263*2a598d0bSHerbert Xu for (i = n-1; i >= 0; i--)
264*2a598d0bSHerbert Xu ap[i+count] = ap[i];
265*2a598d0bSHerbert Xu for (i = 0; i < count; i++)
266*2a598d0bSHerbert Xu ap[i] = 0;
267*2a598d0bSHerbert Xu a->nlimbs += count;
268*2a598d0bSHerbert Xu }
269*2a598d0bSHerbert Xu
270*2a598d0bSHerbert Xu /*
271*2a598d0bSHerbert Xu * Shift A by N bits to the left.
272*2a598d0bSHerbert Xu */
mpi_lshift(MPI x,MPI a,unsigned int n)273*2a598d0bSHerbert Xu void mpi_lshift(MPI x, MPI a, unsigned int n)
274*2a598d0bSHerbert Xu {
275*2a598d0bSHerbert Xu unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
276*2a598d0bSHerbert Xu unsigned int nbits = (n%BITS_PER_MPI_LIMB);
277*2a598d0bSHerbert Xu
278*2a598d0bSHerbert Xu if (x == a && !n)
279*2a598d0bSHerbert Xu return; /* In-place shift with an amount of zero. */
280*2a598d0bSHerbert Xu
281*2a598d0bSHerbert Xu if (x != a) {
282*2a598d0bSHerbert Xu /* Copy A to X. */
283*2a598d0bSHerbert Xu unsigned int alimbs = a->nlimbs;
284*2a598d0bSHerbert Xu int asign = a->sign;
285*2a598d0bSHerbert Xu mpi_ptr_t xp, ap;
286*2a598d0bSHerbert Xu
287*2a598d0bSHerbert Xu RESIZE_IF_NEEDED(x, alimbs+nlimbs+1);
288*2a598d0bSHerbert Xu xp = x->d;
289*2a598d0bSHerbert Xu ap = a->d;
290*2a598d0bSHerbert Xu MPN_COPY(xp, ap, alimbs);
291*2a598d0bSHerbert Xu x->nlimbs = alimbs;
292*2a598d0bSHerbert Xu x->flags = a->flags;
293*2a598d0bSHerbert Xu x->sign = asign;
294*2a598d0bSHerbert Xu }
295*2a598d0bSHerbert Xu
296*2a598d0bSHerbert Xu if (nlimbs && !nbits) {
297*2a598d0bSHerbert Xu /* Shift a full number of limbs. */
298*2a598d0bSHerbert Xu mpi_lshift_limbs(x, nlimbs);
299*2a598d0bSHerbert Xu } else if (n) {
300*2a598d0bSHerbert Xu /* We use a very dump approach: Shift left by the number of
301*2a598d0bSHerbert Xu * limbs plus one and than fix it up by an rshift.
302*2a598d0bSHerbert Xu */
303*2a598d0bSHerbert Xu mpi_lshift_limbs(x, nlimbs+1);
304*2a598d0bSHerbert Xu mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits);
305*2a598d0bSHerbert Xu }
306*2a598d0bSHerbert Xu
307*2a598d0bSHerbert Xu MPN_NORMALIZE(x->d, x->nlimbs);
308*2a598d0bSHerbert Xu }
309