Fix a special case bug in mpi_powm for e==0.
[libgcrypt.git] / mpi / mpi-bit.c
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 _gcry_mpi_normalize( gcry_mpi_t a )
57 {
58     if( mpi_is_opaque(a) )
59         return;
60
61     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 gcry_mpi_get_nbits( gcry_mpi_t a )
72 {
73     unsigned n;
74
75     if( mpi_is_opaque(a) ) {
76         return a->sign; /* which holds the number of bits */
77     }
78
79     _gcry_mpi_normalize( a );
80     if( a->nlimbs ) {
81         mpi_limb_t alimb = a->d[a->nlimbs-1];
82         if( alimb )
83             count_leading_zeros( n, alimb );
84         else
85             n = BITS_PER_MPI_LIMB;
86         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
87     }
88     else
89         n = 0;
90     return n;
91 }
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 {
100     unsigned int limbno, bitno;
101     mpi_limb_t limb;
102
103     limbno = n / BITS_PER_MPI_LIMB;
104     bitno  = n % BITS_PER_MPI_LIMB;
105
106     if( limbno >= a->nlimbs )
107         return 0; /* too far left: this is a 0 */
108     limb = a->d[limbno];
109     return (limb & (A_LIMB_1 << bitno))? 1: 0;
110 }
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 {
119   unsigned int limbno, bitno;
120
121   if (mpi_is_immutable (a))
122     {
123       mpi_immutable_failed ();
124       return;
125     }
126
127   limbno = n / BITS_PER_MPI_LIMB;
128   bitno  = n % BITS_PER_MPI_LIMB;
129
130   if ( limbno >= a->nlimbs )
131     {
132       mpi_resize (a, limbno+1 );
133       a->nlimbs = limbno+1;
134     }
135   a->d[limbno] |= (A_LIMB_1<<bitno);
136 }
137
138 /****************
139  * Set bit N of A. and clear all bits above
140  */
141 void
142 gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
143 {
144   unsigned int limbno, bitno;
145
146   if (mpi_is_immutable (a))
147     {
148       mpi_immutable_failed ();
149       return;
150     }
151
152   limbno = n / BITS_PER_MPI_LIMB;
153   bitno  = n % BITS_PER_MPI_LIMB;
154
155   if ( limbno >= a->nlimbs )
156     {
157       mpi_resize (a, limbno+1 );
158       a->nlimbs = limbno+1;
159     }
160   a->d[limbno] |= (A_LIMB_1<<bitno);
161   for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
162     a->d[limbno] &= ~(A_LIMB_1 << bitno);
163   a->nlimbs = limbno+1;
164 }
165
166 /****************
167  * clear bit N of A and all bits above
168  */
169 void
170 gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
171 {
172   unsigned int limbno, bitno;
173
174   if (mpi_is_immutable (a))
175     {
176       mpi_immutable_failed ();
177       return;
178     }
179
180   limbno = n / BITS_PER_MPI_LIMB;
181   bitno  = n % BITS_PER_MPI_LIMB;
182
183   if( limbno >= a->nlimbs )
184     return; /* not allocated, therefore no need to clear bits :-) */
185
186   for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
187     a->d[limbno] &= ~(A_LIMB_1 << bitno);
188   a->nlimbs = limbno+1;
189 }
190
191 /****************
192  * Clear bit N of A.
193  */
194 void
195 gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
196 {
197   unsigned int limbno, bitno;
198
199   if (mpi_is_immutable (a))
200     {
201       mpi_immutable_failed ();
202       return;
203     }
204
205   limbno = n / BITS_PER_MPI_LIMB;
206   bitno  = n % BITS_PER_MPI_LIMB;
207
208   if (limbno >= a->nlimbs)
209     return; /* Don't need to clear this bit, it's far too left.  */
210   a->d[limbno] &= ~(A_LIMB_1 << bitno);
211 }
212
213
214 /****************
215  * Shift A by COUNT limbs to the right
216  * This is used only within the MPI library
217  */
218 void
219 _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
220 {
221   mpi_ptr_t ap = a->d;
222   mpi_size_t n = a->nlimbs;
223   unsigned int i;
224
225   if (mpi_is_immutable (a))
226     {
227       mpi_immutable_failed ();
228       return;
229     }
230
231   if (count >= n)
232     {
233       a->nlimbs = 0;
234       return;
235     }
236
237   for( i = 0; i < n - count; i++ )
238     ap[i] = ap[i+count];
239   ap[i] = 0;
240   a->nlimbs -= count;
241 }
242
243
244 /*
245  * Shift A by N bits to the right.
246  */
247 void
248 gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
249 {
250   mpi_size_t xsize;
251   unsigned int i;
252   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
253   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
254
255   if (mpi_is_immutable (x))
256     {
257       mpi_immutable_failed ();
258       return;
259     }
260
261   if ( x == a )
262     {
263       /* In-place operation.  */
264       if ( nlimbs >= x->nlimbs )
265         {
266           x->nlimbs = 0;
267           return;
268         }
269
270       if (nlimbs)
271         {
272           for (i=0; i < x->nlimbs - nlimbs; i++ )
273             x->d[i] = x->d[i+nlimbs];
274           x->d[i] = 0;
275           x->nlimbs -= nlimbs;
276
277         }
278       if ( x->nlimbs && nbits )
279         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
280     }
281   else if ( nlimbs )
282     {
283       /* Copy and shift by more or equal bits than in a limb. */
284       xsize = a->nlimbs;
285       x->sign = a->sign;
286       RESIZE_IF_NEEDED (x, xsize);
287       x->nlimbs = xsize;
288       for (i=0; i < a->nlimbs; i++ )
289         x->d[i] = a->d[i];
290       x->nlimbs = i;
291
292       if ( nlimbs >= x->nlimbs )
293         {
294           x->nlimbs = 0;
295           return;
296         }
297
298       if (nlimbs)
299         {
300           for (i=0; i < x->nlimbs - nlimbs; i++ )
301             x->d[i] = x->d[i+nlimbs];
302           x->d[i] = 0;
303           x->nlimbs -= nlimbs;
304         }
305
306       if ( x->nlimbs && nbits )
307         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
308     }
309   else
310     {
311       /* Copy and shift by less than bits in a limb.  */
312       xsize = a->nlimbs;
313       x->sign = a->sign;
314       RESIZE_IF_NEEDED (x, xsize);
315       x->nlimbs = xsize;
316
317       if ( xsize )
318         {
319           if (nbits )
320             _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
321           else
322             {
323               /* The rshift helper function is not specified for
324                  NBITS==0, thus we do a plain copy here. */
325               for (i=0; i < x->nlimbs; i++ )
326                 x->d[i] = a->d[i];
327             }
328         }
329     }
330   MPN_NORMALIZE (x->d, x->nlimbs);
331 }
332
333
334 /****************
335  * Shift A by COUNT limbs to the left
336  * This is used only within the MPI library
337  */
338 void
339 _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
340 {
341   mpi_ptr_t ap;
342   int n = a->nlimbs;
343   int i;
344
345   if (!count || !n)
346     return;
347
348   RESIZE_IF_NEEDED (a, n+count);
349
350   ap = a->d;
351   for (i = n-1; i >= 0; i--)
352     ap[i+count] = ap[i];
353   for (i=0; i < count; i++ )
354     ap[i] = 0;
355   a->nlimbs += count;
356 }
357
358
359 /*
360  * Shift A by N bits to the left.
361  */
362 void
363 gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
364 {
365   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
366   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
367
368   if (mpi_is_immutable (x))
369     {
370       mpi_immutable_failed ();
371       return;
372     }
373
374   if (x == a && !n)
375     return;  /* In-place shift with an amount of zero.  */
376
377   if ( x != a )
378     {
379       /* Copy A to X.  */
380       unsigned int alimbs = a->nlimbs;
381       int asign  = a->sign;
382       mpi_ptr_t xp, ap;
383
384       RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
385       xp = x->d;
386       ap = a->d;
387       MPN_COPY (xp, ap, alimbs);
388       x->nlimbs = alimbs;
389       x->flags = a->flags;
390       x->sign = asign;
391     }
392
393   if (nlimbs && !nbits)
394     {
395       /* Shift a full number of limbs.  */
396       _gcry_mpi_lshift_limbs (x, nlimbs);
397     }
398   else if (n)
399     {
400       /* We use a very dump approach: Shift left by the number of
401          limbs plus one and than fix it up by an rshift.  */
402       _gcry_mpi_lshift_limbs (x, nlimbs+1);
403       gcry_mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
404     }
405
406   MPN_NORMALIZE (x->d, x->nlimbs);
407 }