Replace assert calls by a new gcry_assert at most places.
[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 "mpi-internal.h"
25 #include "longlong.h"
26
27
28 #ifdef MPI_INTERNAL_NEED_CLZ_TAB
29 #ifdef __STDC__
30 const
31 #endif
32 unsigned char
33 _gcry_clz_tab[] =
34 {
35   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,
36   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,
37   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,
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   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,
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 };
44 #endif
45
46
47 #define A_LIMB_1 ((mpi_limb_t)1)
48
49
50 /****************
51  * Sometimes we have MSL (most significant limbs) which are 0;
52  * this is for some reasons not good, so this function removes them.
53  */
54 void
55 _gcry_mpi_normalize( gcry_mpi_t a )
56 {
57     if( mpi_is_opaque(a) )
58         return;
59
60     for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
61         ;
62 }
63
64
65
66 /****************
67  * Return the number of bits in A.
68  */
69 unsigned int
70 gcry_mpi_get_nbits( gcry_mpi_t a )
71 {
72     unsigned n;
73
74     if( mpi_is_opaque(a) ) {
75         return a->sign; /* which holds the number of bits */
76     }
77
78     _gcry_mpi_normalize( a );
79     if( a->nlimbs ) {
80         mpi_limb_t alimb = a->d[a->nlimbs-1];
81         if( alimb )
82             count_leading_zeros( n, alimb );
83         else
84             n = BITS_PER_MPI_LIMB;
85         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
86     }
87     else
88         n = 0;
89     return n;
90 }
91
92
93 /****************
94  * Test whether bit N is set.
95  */
96 int
97 gcry_mpi_test_bit( gcry_mpi_t a, unsigned int n )
98 {
99     unsigned int limbno, bitno;
100     mpi_limb_t limb;
101
102     limbno = n / BITS_PER_MPI_LIMB;
103     bitno  = n % BITS_PER_MPI_LIMB;
104
105     if( limbno >= a->nlimbs )
106         return 0; /* too far left: this is a 0 */
107     limb = a->d[limbno];
108     return (limb & (A_LIMB_1 << bitno))? 1: 0;
109 }
110
111
112 /****************
113  * Set bit N of A.
114  */
115 void
116 gcry_mpi_set_bit( gcry_mpi_t a, unsigned int n )
117 {
118   unsigned int limbno, bitno;
119
120   limbno = n / BITS_PER_MPI_LIMB;
121   bitno  = n % BITS_PER_MPI_LIMB;
122
123   if ( limbno >= a->nlimbs ) 
124     {
125       mpi_resize (a, limbno+1 );
126       a->nlimbs = limbno+1;
127     }
128   a->d[limbno] |= (A_LIMB_1<<bitno);
129 }
130
131 /****************
132  * Set bit N of A. and clear all bits above
133  */
134 void
135 gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
136 {
137   unsigned int limbno, bitno;
138   
139   limbno = n / BITS_PER_MPI_LIMB;
140   bitno  = n % BITS_PER_MPI_LIMB;
141   
142   if ( limbno >= a->nlimbs ) 
143     { 
144       mpi_resize (a, limbno+1 );
145       a->nlimbs = limbno+1;
146     }
147   a->d[limbno] |= (A_LIMB_1<<bitno);
148   for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
149     a->d[limbno] &= ~(A_LIMB_1 << bitno);
150   a->nlimbs = limbno+1;
151 }
152
153 /****************
154  * clear bit N of A and all bits above
155  */
156 void
157 gcry_mpi_clear_highbit( gcry_mpi_t a, unsigned int n )
158 {
159     unsigned int limbno, bitno;
160
161     limbno = n / BITS_PER_MPI_LIMB;
162     bitno  = n % BITS_PER_MPI_LIMB;
163
164     if( limbno >= a->nlimbs )
165         return; /* not allocated, therefore no need to clear bits
166                    :-) */
167
168     for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
169         a->d[limbno] &= ~(A_LIMB_1 << bitno);
170     a->nlimbs = limbno+1;
171 }
172
173 /****************
174  * Clear bit N of A.
175  */
176 void
177 gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
178 {
179     unsigned int limbno, bitno;
180
181     limbno = n / BITS_PER_MPI_LIMB;
182     bitno  = n % BITS_PER_MPI_LIMB;
183
184     if( limbno >= a->nlimbs )
185         return; /* don't need to clear this bit, it's to far to left */
186     a->d[limbno] &= ~(A_LIMB_1 << bitno);
187 }
188
189
190 /****************
191  * Shift A by COUNT limbs to the right
192  * This is used only within the MPI library
193  */
194 void
195 _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
196 {
197     mpi_ptr_t ap = a->d;
198     mpi_size_t n = a->nlimbs;
199     unsigned int i;
200
201     if( count >= n ) {
202         a->nlimbs = 0;
203         return;
204     }
205
206     for( i = 0; i < n - count; i++ )
207         ap[i] = ap[i+count];
208     ap[i] = 0;
209     a->nlimbs -= count;
210 }
211
212
213 /*
214  * Shift A by N bits to the right.
215  */
216 void
217 gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
218 {
219   mpi_size_t xsize;
220   unsigned int i;
221   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
222   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
223
224   if ( x == a )
225     {
226       /* In-place operation.  */
227       if ( nlimbs >= x->nlimbs )
228         {
229           x->nlimbs = 0;
230           return;
231         }
232
233       if (nlimbs)
234         {
235           for (i=0; i < x->nlimbs - nlimbs; i++ )
236             x->d[i] = x->d[i+nlimbs];
237           x->d[i] = 0;
238           x->nlimbs -= nlimbs;
239
240         }
241       if ( x->nlimbs && nbits )
242         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
243     }
244   else if ( nlimbs )
245     {
246       /* Copy and shift by more or equal bits than in a limb. */
247       xsize = a->nlimbs;
248       x->sign = a->sign;
249       RESIZE_IF_NEEDED (x, xsize);
250       x->nlimbs = xsize;
251       for (i=0; i < a->nlimbs; i++ )
252         x->d[i] = a->d[i];
253       x->nlimbs = i;
254
255       if ( nlimbs >= x->nlimbs )
256         {
257           x->nlimbs = 0;
258           return;
259         }
260
261       if (nlimbs)
262         {
263           for (i=0; i < x->nlimbs - nlimbs; i++ )
264             x->d[i] = x->d[i+nlimbs];
265           x->d[i] = 0;
266           x->nlimbs -= nlimbs;
267         }
268
269       if ( x->nlimbs && nbits )
270         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
271     }
272   else
273     {
274       /* Copy and shift by less than bits in a limb.  */
275       xsize = a->nlimbs;
276       x->sign = a->sign;
277       RESIZE_IF_NEEDED (x, xsize);
278       x->nlimbs = xsize;
279       
280       if ( xsize )
281         {
282           if (nbits )
283             _gcry_mpih_rshift (x->d, a->d, x->nlimbs, nbits );
284           else
285             {
286               /* The rshift helper function is not specified for
287                  NBITS==0, thus we do a plain copy here. */
288               for (i=0; i < x->nlimbs; i++ )
289                 x->d[i] = a->d[i];
290             }
291         }
292     }
293   MPN_NORMALIZE (x->d, x->nlimbs);
294 }
295
296
297 /****************
298  * Shift A by COUNT limbs to the left
299  * This is used only within the MPI library
300  */
301 void
302 _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
303 {
304   mpi_ptr_t ap;
305   int n = a->nlimbs;
306   int i;
307
308   if (!count || !n)
309     return;
310
311   RESIZE_IF_NEEDED (a, n+count);
312
313   ap = a->d;
314   for (i = n-1; i >= 0; i--)
315     ap[i+count] = ap[i];
316   for (i=0; i < count; i++ )
317     ap[i] = 0;
318   a->nlimbs += count;
319 }
320
321
322 /*
323  * Shift A by N bits to the left.
324  */
325 void
326 gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
327 {
328   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
329   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
330
331   if (x == a && !n)
332     return;  /* In-place shift with an amount of zero.  */
333
334   if ( x != a )
335     {
336       /* Copy A to X.  */
337       unsigned int alimbs = a->nlimbs;
338       int asign  = a->sign;
339       mpi_ptr_t xp, ap;
340
341       RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
342       xp = x->d;
343       ap = a->d;
344       MPN_COPY (xp, ap, alimbs);
345       x->nlimbs = alimbs;
346       x->flags = a->flags;
347       x->sign = asign;
348     }
349
350   if (nlimbs && !nbits)
351     {
352       /* Shift a full number of limbs.  */
353       _gcry_mpi_lshift_limbs (x, nlimbs);
354     }
355   else if (n)
356     {
357       /* We use a very dump approach: Shift left by the number of
358          limbs plus one and than fix it up by an rshift.  */
359       _gcry_mpi_lshift_limbs (x, nlimbs+1);
360       gcry_mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
361     }
362
363   MPN_NORMALIZE (x->d, x->nlimbs);
364 }
365