doc: Add DCO for Paul Wolneykien
[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 i, 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       for (i=a->nlimbs; i < a->alloced; i++)
133         a->d[i] = 0;
134       mpi_resize (a, limbno+1 );
135       a->nlimbs = limbno+1;
136     }
137   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 _gcry_mpi_set_highbit( gcry_mpi_t a, unsigned int n )
145 {
146   unsigned int i, limbno, bitno;
147
148   if (mpi_is_immutable (a))
149     {
150       mpi_immutable_failed ();
151       return;
152     }
153
154   limbno = n / BITS_PER_MPI_LIMB;
155   bitno  = n % BITS_PER_MPI_LIMB;
156
157   if ( limbno >= a->nlimbs )
158     {
159       for (i=a->nlimbs; i < a->alloced; i++)
160         a->d[i] = 0;
161       mpi_resize (a, limbno+1 );
162       a->nlimbs = limbno+1;
163     }
164   a->d[limbno] |= (A_LIMB_1<<bitno);
165   for ( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
166     a->d[limbno] &= ~(A_LIMB_1 << bitno);
167   a->nlimbs = limbno+1;
168 }
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 {
176   unsigned int limbno, bitno;
177
178   if (mpi_is_immutable (a))
179     {
180       mpi_immutable_failed ();
181       return;
182     }
183
184   limbno = n / BITS_PER_MPI_LIMB;
185   bitno  = n % BITS_PER_MPI_LIMB;
186
187   if( limbno >= a->nlimbs )
188     return; /* not allocated, therefore no need to clear bits :-) */
189
190   for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
191     a->d[limbno] &= ~(A_LIMB_1 << bitno);
192   a->nlimbs = limbno+1;
193 }
194
195 /****************
196  * Clear bit N of A.
197  */
198 void
199 _gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
200 {
201   unsigned int limbno, bitno;
202
203   if (mpi_is_immutable (a))
204     {
205       mpi_immutable_failed ();
206       return;
207     }
208
209   limbno = n / BITS_PER_MPI_LIMB;
210   bitno  = n % BITS_PER_MPI_LIMB;
211
212   if (limbno >= a->nlimbs)
213     return; /* Don't need to clear this bit, it's far too left.  */
214   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 _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
224 {
225   mpi_ptr_t ap = a->d;
226   mpi_size_t n = a->nlimbs;
227   unsigned int i;
228
229   if (mpi_is_immutable (a))
230     {
231       mpi_immutable_failed ();
232       return;
233     }
234
235   if (count >= n)
236     {
237       a->nlimbs = 0;
238       return;
239     }
240
241   for( i = 0; i < n - count; i++ )
242     ap[i] = ap[i+count];
243   ap[i] = 0;
244   a->nlimbs -= count;
245 }
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 {
254   mpi_size_t xsize;
255   unsigned int i;
256   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
257   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
258
259   if (mpi_is_immutable (x))
260     {
261       mpi_immutable_failed ();
262       return;
263     }
264
265   if ( x == a )
266     {
267       /* In-place operation.  */
268       if ( nlimbs >= x->nlimbs )
269         {
270           x->nlimbs = 0;
271           return;
272         }
273
274       if (nlimbs)
275         {
276           for (i=0; i < x->nlimbs - nlimbs; i++ )
277             x->d[i] = x->d[i+nlimbs];
278           x->d[i] = 0;
279           x->nlimbs -= nlimbs;
280
281         }
282       if ( x->nlimbs && nbits )
283         _gcry_mpih_rshift ( x->d, x->d, x->nlimbs, nbits );
284     }
285   else if ( nlimbs )
286     {
287       /* Copy and shift by more or equal bits than in a limb. */
288       xsize = a->nlimbs;
289       x->sign = a->sign;
290       RESIZE_IF_NEEDED (x, xsize);
291       x->nlimbs = xsize;
292       for (i=0; i < a->nlimbs; i++ )
293         x->d[i] = a->d[i];
294       x->nlimbs = i;
295
296       if ( nlimbs >= x->nlimbs )
297         {
298           x->nlimbs = 0;
299           return;
300         }
301
302       if (nlimbs)
303         {
304           for (i=0; i < x->nlimbs - nlimbs; i++ )
305             x->d[i] = x->d[i+nlimbs];
306           x->d[i] = 0;
307           x->nlimbs -= nlimbs;
308         }
309
310       if ( x->nlimbs && nbits )
311         _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       xsize = a->nlimbs;
317       x->sign = a->sign;
318       RESIZE_IF_NEEDED (x, xsize);
319       x->nlimbs = xsize;
320
321       if ( xsize )
322         {
323           if (nbits )
324             _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               for (i=0; i < x->nlimbs; i++ )
330                 x->d[i] = a->d[i];
331             }
332         }
333     }
334   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 _gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
344 {
345   mpi_ptr_t ap;
346   int n = a->nlimbs;
347   int i;
348
349   if (!count || !n)
350     return;
351
352   RESIZE_IF_NEEDED (a, n+count);
353
354   ap = a->d;
355   for (i = n-1; i >= 0; i--)
356     ap[i+count] = ap[i];
357   for (i=0; i < count; i++ )
358     ap[i] = 0;
359   a->nlimbs += count;
360 }
361
362
363 /*
364  * Shift A by N bits to the left.
365  */
366 void
367 _gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
368 {
369   unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
370   unsigned int nbits = (n%BITS_PER_MPI_LIMB);
371
372   if (mpi_is_immutable (x))
373     {
374       mpi_immutable_failed ();
375       return;
376     }
377
378   if (x == a && !n)
379     return;  /* In-place shift with an amount of zero.  */
380
381   if ( x != a )
382     {
383       /* Copy A to X.  */
384       unsigned int alimbs = a->nlimbs;
385       int asign  = a->sign;
386       mpi_ptr_t xp, ap;
387
388       RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
389       xp = x->d;
390       ap = a->d;
391       MPN_COPY (xp, ap, alimbs);
392       x->nlimbs = alimbs;
393       x->flags = a->flags;
394       x->sign = asign;
395     }
396
397   if (nlimbs && !nbits)
398     {
399       /* Shift a full number of limbs.  */
400       _gcry_mpi_lshift_limbs (x, nlimbs);
401     }
402   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       _gcry_mpi_lshift_limbs (x, nlimbs+1);
407       mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
408     }
409
410   MPN_NORMALIZE (x->d, x->nlimbs);
411 }