Fixed a problem with shifting MPIs by 0.
[libgcrypt.git] / mpi / mpi-bit.c
1 /* mpi-bit.c  -  MPI bit level fucntions
2  * Copyright (C) 1998, 1999, 2001, 2002, 2006 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt 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 Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License 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 <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <assert.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   limbno = n / BITS_PER_MPI_LIMB;
122   bitno  = n % BITS_PER_MPI_LIMB;
123
124   if ( limbno >= a->nlimbs ) 
125     {
126       mpi_resize (a, limbno+1 );
127       a->nlimbs = limbno+1;
128     }
129   a->d[limbno] |= (A_LIMB_1<<bitno);
130 }
131
132 /****************
133  * Set bit N of A. and clear all bits above
134  */
135 void
136 gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
137 {
138   unsigned int limbno, bitno;
139   
140   limbno = n / BITS_PER_MPI_LIMB;
141   bitno  = n % BITS_PER_MPI_LIMB;
142   
143   if ( limbno >= a->nlimbs ) 
144     { 
145       mpi_resize (a, limbno+1 );
146       a->nlimbs = limbno+1;
147     }
148   a->d[limbno] |= (A_LIMB_1<<bitno);
149   for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
150     a->d[limbno] &= ~(A_LIMB_1 << bitno);
151   a->nlimbs = limbno+1;
152 }
153
154 /****************
155  * clear bit N of A and all bits above
156  */
157 void
158 gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
159 {
160     unsigned int limbno, bitno;
161
162     limbno = n / BITS_PER_MPI_LIMB;
163     bitno  = n % BITS_PER_MPI_LIMB;
164
165     if( limbno >= a->nlimbs )
166         return; /* not allocated, therefore no need to clear bits
167                    :-) */
168
169     for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
170         a->d[limbno] &= ~(A_LIMB_1 << bitno);
171     a->nlimbs = limbno+1;
172 }
173
174 /****************
175  * Clear bit N of A.
176  */
177 void
178 gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
179 {
180     unsigned int limbno, bitno;
181
182     limbno = n / BITS_PER_MPI_LIMB;
183     bitno  = n % BITS_PER_MPI_LIMB;
184
185     if( limbno >= a->nlimbs )
186         return; /* don't need to clear this bit, it's to far to left */
187     a->d[limbno] &= ~(A_LIMB_1 << bitno);
188 }
189
190
191 /*
192  * Shift A by N bits to the right.
193  */
194 void
195 gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
196 {
197   mpi_size_t xsize;
198   unsigned int i;
199   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
200   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
201
202   if ( x == a )
203     {
204       /* In-place operation.  */
205       if ( nlimbs >= x->nlimbs )
206         {
207           x->nlimbs = 0;
208           return;
209         }
210
211       if (nlimbs)
212         {
213           for (i=0; i < x->nlimbs - nlimbs; i++ )
214             x->d[i] = x->d[i+nlimbs];
215           x->d[i] = 0;
216           x->nlimbs -= nlimbs;
217
218         }
219       if ( x->nlimbs && nbits )
220         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
221     }
222   else if ( nlimbs )
223     {
224       /* Copy and shift by more or equal bits than in a limb. */
225       xsize = a->nlimbs;
226       x->sign = a->sign;
227       RESIZE_IF_NEEDED (x, xsize);
228       x->nlimbs = xsize;
229       for (i=0; i < a->nlimbs; i++ )
230         x->d[i] = a->d[i];
231       x->nlimbs = i;
232
233       if ( nlimbs >= x->nlimbs )
234         {
235           x->nlimbs = 0;
236           return;
237         }
238
239       if (nlimbs)
240         {
241           for (i=0; i < x->nlimbs - nlimbs; i++ )
242             x->d[i] = x->d[i+nlimbs];
243           x->d[i] = 0;
244           x->nlimbs -= nlimbs;
245         }
246
247       if ( x->nlimbs && nbits )
248         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
249     }
250   else
251     {
252       /* Copy and shift by less than bits in a limb.  */
253       xsize = a->nlimbs;
254       x->sign = a->sign;
255       RESIZE_IF_NEEDED (x, xsize);
256       x->nlimbs = xsize;
257       
258       if ( xsize )
259         {
260           if (nbits )
261             _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
262           else
263             {
264               /* The rshift helper function is not specified for
265                  NBITS==0, thus we do a plain copy here. */
266               for (i=0; i < x->nlimbs; i++ )
267                 x->d[i] = a->d[i];
268             }
269         }
270     }
271   MPN_NORMALIZE (x->d, x->nlimbs);
272 }
273
274
275 /****************
276  * Shift A by COUNT limbs to the left
277  * This is used only within the MPI library
278  */
279 void
280 _gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count )
281 {
282     mpi_ptr_t ap = a->d;
283     int n = a->nlimbs;
284     int i;
285
286     if( !count || !n )
287         return;
288
289     RESIZE_IF_NEEDED( a, n+count );
290
291     for( i = n-1; i >= 0; i-- )
292         ap[i+count] = ap[i];
293     for(i=0; i < count; i++ )
294         ap[i] = 0;
295     a->nlimbs += count;
296 }
297
298
299 /****************
300  * Shift A by COUNT limbs to the right
301  * This is used only within the MPI library
302  */
303 void
304 _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
305 {
306     mpi_ptr_t ap = a->d;
307     mpi_size_t n = a->nlimbs;
308     unsigned int i;
309
310     if( count >= n ) {
311         a->nlimbs = 0;
312         return;
313     }
314
315     for( i = 0; i < n - count; i++ )
316         ap[i] = ap[i+count];
317     ap[i] = 0;
318     a->nlimbs -= count;
319 }