/src/libgcrypt/mpi/mpi-bit.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* mpi-bit.c - MPI bit level functions |
2 | | * Copyright (C) 1998, 1999, 2001, 2002, 2006 Free Software Foundation, Inc. |
3 | | * Copyright (C) 2013 g10 Code GmbH |
4 | | * |
5 | | * This file is part of Libgcrypt. |
6 | | * |
7 | | * Libgcrypt is free software; you can redistribute it and/or modify |
8 | | * it under the terms of the GNU Lesser General Public License as |
9 | | * published by the Free Software Foundation; either version 2.1 of |
10 | | * the License, or (at your option) any later version. |
11 | | * |
12 | | * Libgcrypt is distributed in the hope that it will be useful, |
13 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 | | * GNU Lesser General Public License for more details. |
16 | | * |
17 | | * You should have received a copy of the GNU Lesser General Public |
18 | | * License along with this program; if not, see <https://www.gnu.org/licenses/>. |
19 | | * SPDX-License-Identifier: LGPL-2.1-or-later |
20 | | */ |
21 | | |
22 | | #include <config.h> |
23 | | #include <stdio.h> |
24 | | #include <stdlib.h> |
25 | | #include "mpi-internal.h" |
26 | | #include "longlong.h" |
27 | | |
28 | | |
29 | | #ifdef MPI_INTERNAL_NEED_CLZ_TAB |
30 | | #ifdef __STDC__ |
31 | | const |
32 | | #endif |
33 | | unsigned char |
34 | | _gcry_clz_tab[] = |
35 | | { |
36 | | 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, |
37 | | 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, |
38 | | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
39 | | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
40 | | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
41 | | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
42 | | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
43 | | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
44 | | }; |
45 | | #endif |
46 | | |
47 | | |
48 | 3.70M | #define A_LIMB_1 ((mpi_limb_t)1) |
49 | | |
50 | | |
51 | | /**************** |
52 | | * Sometimes we have MSL (most significant limbs) which are 0; |
53 | | * this is for some reasons not good, so this function removes them. |
54 | | */ |
55 | | void |
56 | | _gcry_mpi_normalize( gcry_mpi_t a ) |
57 | 5.56M | { |
58 | 5.56M | if( mpi_is_opaque(a) ) |
59 | 0 | return; |
60 | | |
61 | 5.59M | for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- ) |
62 | 31.5k | ; |
63 | 5.56M | } |
64 | | |
65 | | |
66 | | |
67 | | /**************** |
68 | | * Return the number of bits in A. |
69 | | */ |
70 | | unsigned int |
71 | | _gcry_mpi_get_nbits (gcry_mpi_t a) |
72 | 31.5k | { |
73 | 31.5k | unsigned n; |
74 | | |
75 | 31.5k | if( mpi_is_opaque(a) ) { |
76 | 0 | return a->sign; /* which holds the number of bits */ |
77 | 0 | } |
78 | | |
79 | 31.5k | _gcry_mpi_normalize( a ); |
80 | 31.5k | if( a->nlimbs ) { |
81 | 29.7k | mpi_limb_t alimb = a->d[a->nlimbs-1]; |
82 | 29.7k | if( alimb ) |
83 | 29.7k | count_leading_zeros( n, alimb ); |
84 | 0 | else |
85 | 0 | n = BITS_PER_MPI_LIMB; |
86 | 29.7k | n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB; |
87 | 29.7k | } |
88 | 1.83k | else |
89 | 1.83k | n = 0; |
90 | 31.5k | return n; |
91 | 31.5k | } |
92 | | |
93 | | |
94 | | /**************** |
95 | | * Test whether bit N is set. |
96 | | */ |
97 | | int |
98 | | _gcry_mpi_test_bit( gcry_mpi_t a, unsigned int n ) |
99 | 3.70M | { |
100 | 3.70M | unsigned int limbno, bitno; |
101 | 3.70M | mpi_limb_t limb; |
102 | | |
103 | 3.70M | limbno = n / BITS_PER_MPI_LIMB; |
104 | 3.70M | bitno = n % BITS_PER_MPI_LIMB; |
105 | | |
106 | 3.70M | if( limbno >= a->nlimbs ) |
107 | 495 | return 0; /* too far left: this is a 0 */ |
108 | 3.70M | limb = a->d[limbno]; |
109 | 3.70M | return (limb & (A_LIMB_1 << bitno))? 1: 0; |
110 | 3.70M | } |
111 | | |
112 | | |
113 | | /**************** |
114 | | * Set bit N of A. |
115 | | */ |
116 | | void |
117 | | _gcry_mpi_set_bit( gcry_mpi_t a, unsigned int n ) |
118 | 44 | { |
119 | 44 | unsigned int i, limbno, bitno; |
120 | | |
121 | 44 | if (mpi_is_immutable (a)) |
122 | 0 | { |
123 | 0 | mpi_immutable_failed (); |
124 | 0 | return; |
125 | 0 | } |
126 | | |
127 | 44 | limbno = n / BITS_PER_MPI_LIMB; |
128 | 44 | bitno = n % BITS_PER_MPI_LIMB; |
129 | | |
130 | 44 | if ( limbno >= a->nlimbs ) |
131 | 33 | { |
132 | 561 | for (i=a->nlimbs; i < a->alloced; i++) |
133 | 528 | a->d[i] = 0; |
134 | 33 | mpi_resize (a, limbno+1 ); |
135 | 33 | a->nlimbs = limbno+1; |
136 | 33 | } |
137 | 44 | a->d[limbno] |= (A_LIMB_1<<bitno); |
138 | 44 | } |
139 | | |
140 | | /**************** |
141 | | * Set bit N of A. and clear all bits above |
142 | | */ |
143 | | void |
144 | | _gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n ) |
145 | 208 | { |
146 | 208 | unsigned int i, limbno, bitno; |
147 | | |
148 | 208 | if (mpi_is_immutable (a)) |
149 | 0 | { |
150 | 0 | mpi_immutable_failed (); |
151 | 0 | return; |
152 | 0 | } |
153 | | |
154 | 208 | limbno = n / BITS_PER_MPI_LIMB; |
155 | 208 | bitno = n % BITS_PER_MPI_LIMB; |
156 | | |
157 | 208 | if ( limbno >= a->nlimbs ) |
158 | 0 | { |
159 | 0 | for (i=a->nlimbs; i < a->alloced; i++) |
160 | 0 | a->d[i] = 0; |
161 | 0 | mpi_resize (a, limbno+1 ); |
162 | 0 | a->nlimbs = limbno+1; |
163 | 0 | } |
164 | 208 | a->d[limbno] |= (A_LIMB_1<<bitno); |
165 | 767 | for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ ) |
166 | 559 | a->d[limbno] &= ~(A_LIMB_1 << bitno); |
167 | 208 | a->nlimbs = limbno+1; |
168 | 208 | } |
169 | | |
170 | | /**************** |
171 | | * clear bit N of A and all bits above |
172 | | */ |
173 | | void |
174 | | _gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n ) |
175 | 0 | { |
176 | 0 | unsigned int limbno, bitno; |
177 | |
|
178 | 0 | if (mpi_is_immutable (a)) |
179 | 0 | { |
180 | 0 | mpi_immutable_failed (); |
181 | 0 | return; |
182 | 0 | } |
183 | | |
184 | 0 | limbno = n / BITS_PER_MPI_LIMB; |
185 | 0 | bitno = n % BITS_PER_MPI_LIMB; |
186 | |
|
187 | 0 | if( limbno >= a->nlimbs ) |
188 | 0 | return; /* not allocated, therefore no need to clear bits :-) */ |
189 | | |
190 | 0 | for( ; bitno < BITS_PER_MPI_LIMB; bitno++ ) |
191 | 0 | a->d[limbno] &= ~(A_LIMB_1 << bitno); |
192 | 0 | a->nlimbs = limbno+1; |
193 | 0 | } |
194 | | |
195 | | /**************** |
196 | | * Clear bit N of A. |
197 | | */ |
198 | | void |
199 | | _gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n ) |
200 | 126 | { |
201 | 126 | unsigned int limbno, bitno; |
202 | | |
203 | 126 | if (mpi_is_immutable (a)) |
204 | 0 | { |
205 | 0 | mpi_immutable_failed (); |
206 | 0 | return; |
207 | 0 | } |
208 | | |
209 | 126 | limbno = n / BITS_PER_MPI_LIMB; |
210 | 126 | bitno = n % BITS_PER_MPI_LIMB; |
211 | | |
212 | 126 | if (limbno >= a->nlimbs) |
213 | 3 | return; /* Don't need to clear this bit, it's far too left. */ |
214 | 123 | a->d[limbno] &= ~(A_LIMB_1 << bitno); |
215 | 123 | } |
216 | | |
217 | | |
218 | | /**************** |
219 | | * Shift A by COUNT limbs to the right |
220 | | * This is used only within the MPI library |
221 | | */ |
222 | | void |
223 | | _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count ) |
224 | 94 | { |
225 | 94 | mpi_ptr_t ap = a->d; |
226 | 94 | mpi_size_t n = a->nlimbs; |
227 | 94 | unsigned int i; |
228 | | |
229 | 94 | if (mpi_is_immutable (a)) |
230 | 0 | { |
231 | 0 | mpi_immutable_failed (); |
232 | 0 | return; |
233 | 0 | } |
234 | | |
235 | 94 | if (count >= n) |
236 | 56 | { |
237 | 56 | a->nlimbs = 0; |
238 | 56 | return; |
239 | 56 | } |
240 | | |
241 | 225 | for( i = 0; i < n - count; i++ ) |
242 | 187 | ap[i] = ap[i+count]; |
243 | 38 | ap[i] = 0; |
244 | 38 | a->nlimbs -= count; |
245 | 38 | } |
246 | | |
247 | | |
248 | | /* |
249 | | * Shift A by N bits to the right. |
250 | | */ |
251 | | void |
252 | | _gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n ) |
253 | 715 | { |
254 | 715 | unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); |
255 | 715 | unsigned int nbits = (n%BITS_PER_MPI_LIMB); |
256 | 715 | unsigned int i; |
257 | 715 | mpi_size_t alimbs; |
258 | 715 | mpi_ptr_t xp, ap; |
259 | | |
260 | 715 | if (mpi_is_immutable (x)) |
261 | 0 | { |
262 | 0 | mpi_immutable_failed (); |
263 | 0 | return; |
264 | 0 | } |
265 | | |
266 | 715 | alimbs = a->nlimbs; |
267 | | |
268 | 715 | if (x != a) |
269 | 680 | { |
270 | 680 | RESIZE_IF_NEEDED (x, alimbs); |
271 | 680 | x->nlimbs = alimbs; |
272 | 680 | x->flags = a->flags; |
273 | 680 | x->sign = a->sign; |
274 | 680 | } |
275 | | |
276 | | /* In-place operation. */ |
277 | 715 | if (nlimbs >= alimbs) |
278 | 11 | { |
279 | 11 | x->nlimbs = 0; |
280 | 11 | return; |
281 | 11 | } |
282 | | |
283 | 704 | xp = x->d; |
284 | 704 | ap = a->d; |
285 | | |
286 | 704 | if (alimbs && nbits) |
287 | 669 | { |
288 | 669 | _gcry_mpih_rshift (xp, ap + nlimbs, alimbs - nlimbs, nbits); |
289 | 669 | if (nlimbs) |
290 | 150 | xp[alimbs - nlimbs] = 0; |
291 | 669 | x->nlimbs -= nlimbs; |
292 | 669 | } |
293 | 35 | else if (nlimbs || (x != a)) |
294 | 27 | { |
295 | 394 | for (i = 0; i < alimbs - nlimbs; i++ ) |
296 | 367 | xp[i] = ap[i + nlimbs]; |
297 | 27 | if (nlimbs) |
298 | 25 | xp[i] = 0; |
299 | 27 | x->nlimbs -= nlimbs; |
300 | 27 | } |
301 | | |
302 | 704 | MPN_NORMALIZE (x->d, x->nlimbs); |
303 | 704 | } |
304 | | |
305 | | |
306 | | /**************** |
307 | | * Shift A by COUNT limbs to the left |
308 | | * This is used only within the MPI library |
309 | | */ |
310 | | void |
311 | | _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count) |
312 | 71 | { |
313 | 71 | mpi_ptr_t ap; |
314 | 71 | int n = a->nlimbs; |
315 | 71 | int i; |
316 | | |
317 | 71 | if (!count || !n) |
318 | 0 | return; |
319 | | |
320 | 71 | RESIZE_IF_NEEDED (a, n+count); |
321 | | |
322 | 71 | ap = a->d; |
323 | 142 | for (i = n-1; i >= 0; i--) |
324 | 71 | ap[i+count] = ap[i]; |
325 | 3.48k | for (i=0; i < count; i++ ) |
326 | 3.41k | ap[i] = 0; |
327 | 71 | a->nlimbs += count; |
328 | 71 | } |
329 | | |
330 | | |
331 | | /* |
332 | | * Shift A by N bits to the left. |
333 | | */ |
334 | | void |
335 | | _gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n ) |
336 | 2.65M | { |
337 | 2.65M | unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); |
338 | 2.65M | unsigned int nbits = (n%BITS_PER_MPI_LIMB); |
339 | 2.65M | mpi_size_t alimbs; |
340 | 2.65M | mpi_ptr_t xp, ap; |
341 | 2.65M | int i; |
342 | | |
343 | 2.65M | if (mpi_is_immutable (x)) |
344 | 0 | { |
345 | 0 | mpi_immutable_failed (); |
346 | 0 | return; |
347 | 0 | } |
348 | | |
349 | 2.65M | if (x == a && !n) |
350 | 0 | return; /* In-place shift with an amount of zero. */ |
351 | | |
352 | | /* Note: might be in-place operation, so a==x or a!=x. */ |
353 | | |
354 | 2.65M | alimbs = a->nlimbs; |
355 | | |
356 | 2.65M | RESIZE_IF_NEEDED (x, alimbs + nlimbs + 1); |
357 | 2.65M | xp = x->d; |
358 | 2.65M | ap = a->d; |
359 | 2.65M | if (nbits && alimbs) |
360 | 2.65M | { |
361 | 2.65M | x->nlimbs = alimbs + nlimbs + 1; |
362 | 2.65M | xp[alimbs + nlimbs] = _gcry_mpih_lshift (xp + nlimbs, ap, alimbs, nbits); |
363 | 2.65M | } |
364 | 6 | else |
365 | 6 | { |
366 | 6 | x->nlimbs = alimbs + nlimbs; |
367 | 6 | for (i = alimbs - 1; i >= 0; i--) |
368 | 0 | xp[i + nlimbs] = ap[i]; |
369 | 6 | } |
370 | 2.65M | for (i = 0; i < nlimbs; i++) |
371 | 0 | xp[i] = 0; |
372 | 2.65M | x->flags = a->flags; |
373 | 2.65M | x->sign = a->sign; |
374 | 2.65M | MPN_NORMALIZE (x->d, x->nlimbs); |
375 | 2.65M | } |