Commit | Line | Data |
---|---|---|
8d8472cf | 1 | /* mpi-bit.c - MPI bit level functions |
cdec9cb5 DK |
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 | ||
cdec9cb5 DK |
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 | } | |
a8ea8bdd | 35 | EXPORT_SYMBOL_GPL(mpi_normalize); |
cdec9cb5 DK |
36 | |
37 | /**************** | |
38 | * Return the number of bits in A. | |
39 | */ | |
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) | |
aacf29bf | 49 | n = count_leading_zeros(alimb); |
cdec9cb5 DK |
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); | |
a8ea8bdd TZ |
58 | |
59 | /**************** | |
60 | * Test whether bit N is set. | |
61 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | } | |
81771ff2 | 245 | EXPORT_SYMBOL_GPL(mpi_rshift); |
a8ea8bdd TZ |
246 | |
247 | /**************** | |
248 | * Shift A by COUNT limbs to the left | |
249 | * This is used only within the MPI library | |
250 | */ | |
251 | void mpi_lshift_limbs(MPI a, unsigned int count) | |
252 | { | |
253 | mpi_ptr_t ap; | |
254 | int n = a->nlimbs; | |
255 | int i; | |
256 | ||
257 | if (!count || !n) | |
258 | return; | |
259 | ||
260 | RESIZE_IF_NEEDED(a, n+count); | |
261 | ||
262 | ap = a->d; | |
263 | for (i = n-1; i >= 0; i--) | |
264 | ap[i+count] = ap[i]; | |
265 | for (i = 0; i < count; i++) | |
266 | ap[i] = 0; | |
267 | a->nlimbs += count; | |
268 | } | |
269 | ||
270 | /* | |
271 | * Shift A by N bits to the left. | |
272 | */ | |
273 | void mpi_lshift(MPI x, MPI a, unsigned int n) | |
274 | { | |
275 | unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); | |
276 | unsigned int nbits = (n%BITS_PER_MPI_LIMB); | |
277 | ||
278 | if (x == a && !n) | |
279 | return; /* In-place shift with an amount of zero. */ | |
280 | ||
281 | if (x != a) { | |
282 | /* Copy A to X. */ | |
283 | unsigned int alimbs = a->nlimbs; | |
284 | int asign = a->sign; | |
285 | mpi_ptr_t xp, ap; | |
286 | ||
287 | RESIZE_IF_NEEDED(x, alimbs+nlimbs+1); | |
288 | xp = x->d; | |
289 | ap = a->d; | |
290 | MPN_COPY(xp, ap, alimbs); | |
291 | x->nlimbs = alimbs; | |
292 | x->flags = a->flags; | |
293 | x->sign = asign; | |
294 | } | |
295 | ||
296 | if (nlimbs && !nbits) { | |
297 | /* Shift a full number of limbs. */ | |
298 | mpi_lshift_limbs(x, nlimbs); | |
299 | } else if (n) { | |
300 | /* We use a very dump approach: Shift left by the number of | |
301 | * limbs plus one and than fix it up by an rshift. | |
302 | */ | |
303 | mpi_lshift_limbs(x, nlimbs+1); | |
304 | mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits); | |
305 | } | |
306 | ||
307 | MPN_NORMALIZE(x->d, x->nlimbs); | |
308 | } |