1/* mpi-bit.c  -  MPI bit level functions
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__
30const
31#endif
32unsigned 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 */
54void
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 */
69unsigned int
70gcry_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 */
96int
97gcry_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 */
115void
116gcry_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 */
134void
135gcry_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 */
156void
157gcry_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 */
176void
177gcry_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 */
194void
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 */
216void
217gcry_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 */
301void
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 */
325void
326gcry_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