Line data Source code
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, write to the Free Software
19 : * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
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 : #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 3458378 : _gcry_mpi_normalize( gcry_mpi_t a )
57 : {
58 3458378 : if( mpi_is_opaque(a) )
59 3458381 : return;
60 :
61 3458375 : for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
62 : ;
63 : }
64 :
65 :
66 :
67 : /****************
68 : * Return the number of bits in A.
69 : */
70 : unsigned int
71 57225 : _gcry_mpi_get_nbits (gcry_mpi_t a)
72 : {
73 : unsigned n;
74 :
75 57225 : if( mpi_is_opaque(a) ) {
76 0 : return a->sign; /* which holds the number of bits */
77 : }
78 :
79 57225 : _gcry_mpi_normalize( a );
80 57225 : if( a->nlimbs ) {
81 56442 : mpi_limb_t alimb = a->d[a->nlimbs-1];
82 56442 : if( alimb )
83 56442 : count_leading_zeros( n, alimb );
84 : else
85 0 : n = BITS_PER_MPI_LIMB;
86 56442 : n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
87 : }
88 : else
89 783 : n = 0;
90 57225 : return n;
91 : }
92 :
93 :
94 : /****************
95 : * Test whether bit N is set.
96 : */
97 : int
98 11430731 : _gcry_mpi_test_bit( gcry_mpi_t a, unsigned int n )
99 : {
100 : unsigned int limbno, bitno;
101 : mpi_limb_t limb;
102 :
103 11430731 : limbno = n / BITS_PER_MPI_LIMB;
104 11430731 : bitno = n % BITS_PER_MPI_LIMB;
105 :
106 11430731 : if( limbno >= a->nlimbs )
107 11420 : return 0; /* too far left: this is a 0 */
108 11419311 : limb = a->d[limbno];
109 11419311 : return (limb & (A_LIMB_1 << bitno))? 1: 0;
110 : }
111 :
112 :
113 : /****************
114 : * Set bit N of A.
115 : */
116 : void
117 1605 : _gcry_mpi_set_bit( gcry_mpi_t a, unsigned int n )
118 : {
119 : unsigned int i, limbno, bitno;
120 :
121 1605 : if (mpi_is_immutable (a))
122 : {
123 0 : mpi_immutable_failed ();
124 1605 : return;
125 : }
126 :
127 1605 : limbno = n / BITS_PER_MPI_LIMB;
128 1605 : bitno = n % BITS_PER_MPI_LIMB;
129 :
130 1605 : if ( limbno >= a->nlimbs )
131 : {
132 30 : for (i=a->nlimbs; i < a->alloced; i++)
133 26 : a->d[i] = 0;
134 4 : mpi_resize (a, limbno+1 );
135 4 : a->nlimbs = limbno+1;
136 : }
137 1605 : a->d[limbno] |= (A_LIMB_1<<bitno);
138 : }
139 :
140 : /****************
141 : * Set bit N of A. and clear all bits above
142 : */
143 : void
144 11913 : _gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
145 : {
146 : unsigned int i, limbno, bitno;
147 :
148 11913 : if (mpi_is_immutable (a))
149 : {
150 0 : mpi_immutable_failed ();
151 11913 : return;
152 : }
153 :
154 11913 : limbno = n / BITS_PER_MPI_LIMB;
155 11913 : bitno = n % BITS_PER_MPI_LIMB;
156 :
157 11913 : if ( limbno >= a->nlimbs )
158 : {
159 101139 : for (i=a->nlimbs; i < a->alloced; i++)
160 96614 : a->d[i] = 0;
161 4525 : mpi_resize (a, limbno+1 );
162 4525 : a->nlimbs = limbno+1;
163 : }
164 11913 : a->d[limbno] |= (A_LIMB_1<<bitno);
165 169611 : for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
166 157698 : a->d[limbno] &= ~(A_LIMB_1 << bitno);
167 11913 : a->nlimbs = limbno+1;
168 : }
169 :
170 : /****************
171 : * clear bit N of A and all bits above
172 : */
173 : void
174 4654 : _gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
175 : {
176 : unsigned int limbno, bitno;
177 :
178 4654 : if (mpi_is_immutable (a))
179 : {
180 0 : mpi_immutable_failed ();
181 0 : return;
182 : }
183 :
184 4654 : limbno = n / BITS_PER_MPI_LIMB;
185 4654 : bitno = n % BITS_PER_MPI_LIMB;
186 :
187 4654 : if( limbno >= a->nlimbs )
188 12 : return; /* not allocated, therefore no need to clear bits :-) */
189 :
190 53353 : for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
191 48711 : a->d[limbno] &= ~(A_LIMB_1 << bitno);
192 4642 : a->nlimbs = limbno+1;
193 : }
194 :
195 : /****************
196 : * Clear bit N of A.
197 : */
198 : void
199 7310 : _gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
200 : {
201 : unsigned int limbno, bitno;
202 :
203 7310 : if (mpi_is_immutable (a))
204 : {
205 0 : mpi_immutable_failed ();
206 0 : return;
207 : }
208 :
209 7310 : limbno = n / BITS_PER_MPI_LIMB;
210 7310 : bitno = n % BITS_PER_MPI_LIMB;
211 :
212 7310 : if (limbno >= a->nlimbs)
213 0 : return; /* Don't need to clear this bit, it's far too left. */
214 7310 : a->d[limbno] &= ~(A_LIMB_1 << bitno);
215 : }
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 0 : _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
224 : {
225 0 : mpi_ptr_t ap = a->d;
226 0 : mpi_size_t n = a->nlimbs;
227 : unsigned int i;
228 :
229 0 : if (mpi_is_immutable (a))
230 : {
231 0 : mpi_immutable_failed ();
232 0 : return;
233 : }
234 :
235 0 : if (count >= n)
236 : {
237 0 : a->nlimbs = 0;
238 0 : return;
239 : }
240 :
241 0 : for( i = 0; i < n - count; i++ )
242 0 : ap[i] = ap[i+count];
243 0 : ap[i] = 0;
244 0 : a->nlimbs -= count;
245 : }
246 :
247 :
248 : /*
249 : * Shift A by N bits to the right.
250 : */
251 : void
252 10285088 : _gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
253 : {
254 : mpi_size_t xsize;
255 : unsigned int i;
256 10285088 : unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
257 10285088 : unsigned int nbits = (n%BITS_PER_MPI_LIMB);
258 :
259 10285088 : if (mpi_is_immutable (x))
260 : {
261 0 : mpi_immutable_failed ();
262 0 : return;
263 : }
264 :
265 10285088 : if ( x == a )
266 : {
267 : /* In-place operation. */
268 10284713 : if ( nlimbs >= x->nlimbs )
269 : {
270 365 : x->nlimbs = 0;
271 365 : return;
272 : }
273 :
274 10284348 : if (nlimbs)
275 : {
276 864 : for (i=0; i < x->nlimbs - nlimbs; i++ )
277 662 : x->d[i] = x->d[i+nlimbs];
278 202 : x->d[i] = 0;
279 202 : x->nlimbs -= nlimbs;
280 :
281 : }
282 10284348 : if ( x->nlimbs && nbits )
283 10284248 : _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
284 : }
285 375 : else if ( nlimbs )
286 : {
287 : /* Copy and shift by more or equal bits than in a limb. */
288 55 : xsize = a->nlimbs;
289 55 : x->sign = a->sign;
290 55 : RESIZE_IF_NEEDED (x, xsize);
291 55 : x->nlimbs = xsize;
292 165 : for (i=0; i < a->nlimbs; i++ )
293 110 : x->d[i] = a->d[i];
294 55 : x->nlimbs = i;
295 :
296 55 : if ( nlimbs >= x->nlimbs )
297 : {
298 0 : x->nlimbs = 0;
299 0 : return;
300 : }
301 :
302 55 : if (nlimbs)
303 : {
304 110 : for (i=0; i < x->nlimbs - nlimbs; i++ )
305 55 : x->d[i] = x->d[i+nlimbs];
306 55 : x->d[i] = 0;
307 55 : x->nlimbs -= nlimbs;
308 : }
309 :
310 55 : if ( x->nlimbs && nbits )
311 50 : _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
312 : }
313 : else
314 : {
315 : /* Copy and shift by less than bits in a limb. */
316 320 : xsize = a->nlimbs;
317 320 : x->sign = a->sign;
318 320 : RESIZE_IF_NEEDED (x, xsize);
319 320 : x->nlimbs = xsize;
320 :
321 320 : if ( xsize )
322 : {
323 320 : if (nbits )
324 315 : _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
325 : else
326 : {
327 : /* The rshift helper function is not specified for
328 : NBITS==0, thus we do a plain copy here. */
329 15 : for (i=0; i < x->nlimbs; i++ )
330 10 : x->d[i] = a->d[i];
331 : }
332 : }
333 : }
334 10284723 : MPN_NORMALIZE (x->d, x->nlimbs);
335 : }
336 :
337 :
338 : /****************
339 : * Shift A by COUNT limbs to the left
340 : * This is used only within the MPI library
341 : */
342 : void
343 2028728 : _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
344 : {
345 : mpi_ptr_t ap;
346 2028728 : int n = a->nlimbs;
347 : int i;
348 :
349 2028728 : if (!count || !n)
350 2029098 : return;
351 :
352 2028358 : RESIZE_IF_NEEDED (a, n+count);
353 :
354 2028358 : ap = a->d;
355 10836159 : for (i = n-1; i >= 0; i--)
356 8807801 : ap[i+count] = ap[i];
357 4401421 : for (i=0; i < count; i++ )
358 2373063 : ap[i] = 0;
359 2028358 : a->nlimbs += count;
360 : }
361 :
362 :
363 : /*
364 : * Shift A by N bits to the left.
365 : */
366 : void
367 2033320 : _gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
368 : {
369 2033320 : unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
370 2033320 : unsigned int nbits = (n%BITS_PER_MPI_LIMB);
371 :
372 2033320 : if (mpi_is_immutable (x))
373 : {
374 0 : mpi_immutable_failed ();
375 0 : return;
376 : }
377 :
378 2033320 : if (x == a && !n)
379 4557 : return; /* In-place shift with an amount of zero. */
380 :
381 2028763 : if ( x != a )
382 : {
383 : /* Copy A to X. */
384 1832842 : unsigned int alimbs = a->nlimbs;
385 1832842 : int asign = a->sign;
386 : mpi_ptr_t xp, ap;
387 :
388 1832842 : RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
389 1832842 : xp = x->d;
390 1832842 : ap = a->d;
391 1832842 : MPN_COPY (xp, ap, alimbs);
392 1832842 : x->nlimbs = alimbs;
393 1832842 : x->flags = a->flags;
394 1832842 : x->sign = asign;
395 : }
396 :
397 2028763 : if (nlimbs && !nbits)
398 : {
399 : /* Shift a full number of limbs. */
400 14869 : _gcry_mpi_lshift_limbs (x, nlimbs);
401 : }
402 2013894 : else if (n)
403 : {
404 : /* We use a very dump approach: Shift left by the number of
405 : limbs plus one and than fix it up by an rshift. */
406 2013859 : _gcry_mpi_lshift_limbs (x, nlimbs+1);
407 2013859 : mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
408 : }
409 :
410 2028763 : MPN_NORMALIZE (x->d, x->nlimbs);
411 : }
|
