1 /* mpi-bit.c - MPI bit level fucntions
2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
4 * This file is part of GnuPG.
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * GnuPG 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 General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
26 #include "mpi-internal.h"
30 #ifdef MPI_INTERNAL_NEED_CLZ_TAB
37 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,
38 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,
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 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,
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 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,
49 #define A_LIMB_1 ((mpi_limb_t)1)
53 * Sometimes we have MSL (most significant limbs) which are 0;
54 * this is for some reasons not good, so this function removes them.
57 mpi_normalize( MPI a )
59 if( mpi_is_opaque (a) )
62 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
69 * Return the number of bits in A.
72 mpi_get_nbits( MPI a )
78 mpi_limb_t alimb = a->d[a->nlimbs-1];
80 count_leading_zeros( n, alimb );
82 n = BITS_PER_MPI_LIMB;
83 n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
92 * Test whether bit N is set.
95 mpi_test_bit( MPI a, unsigned n )
97 unsigned limbno, bitno;
100 limbno = n / BITS_PER_MPI_LIMB;
101 bitno = n % BITS_PER_MPI_LIMB;
103 if( limbno >= a->nlimbs )
104 return 0; /* too far left: this is a 0 */
106 return (limb & (A_LIMB_1 << bitno))? 1: 0;
114 mpi_set_bit( MPI a, unsigned n )
116 unsigned limbno, bitno;
118 limbno = n / BITS_PER_MPI_LIMB;
119 bitno = n % BITS_PER_MPI_LIMB;
121 if( limbno >= a->nlimbs ) { /* resize */
122 if( a->alloced >= limbno )
123 mpi_resize(a, limbno+1 );
124 a->nlimbs = limbno+1;
126 a->d[limbno] |= (A_LIMB_1<<bitno);
130 * Set bit N of A. and clear all bits above
133 mpi_set_highbit( MPI a, unsigned n )
135 unsigned limbno, bitno;
137 limbno = n / BITS_PER_MPI_LIMB;
138 bitno = n % BITS_PER_MPI_LIMB;
140 if( limbno >= a->nlimbs ) { /* resize */
141 if( a->alloced >= limbno )
142 mpi_resize(a, limbno+1 );
143 a->nlimbs = limbno+1;
145 a->d[limbno] |= (A_LIMB_1<<bitno);
146 for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
147 a->d[limbno] &= ~(A_LIMB_1 << bitno);
148 a->nlimbs = limbno+1;
152 * clear bit N of A and all bits above
155 mpi_clear_highbit( MPI a, unsigned n )
157 unsigned limbno, bitno;
159 limbno = n / BITS_PER_MPI_LIMB;
160 bitno = n % BITS_PER_MPI_LIMB;
162 if( limbno >= a->nlimbs )
163 return; /* not allocated, so need to clear bits :-) */
165 for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
166 a->d[limbno] &= ~(A_LIMB_1 << bitno);
167 a->nlimbs = limbno+1;
174 mpi_clear_bit( MPI a, unsigned n )
176 unsigned limbno, bitno;
178 limbno = n / BITS_PER_MPI_LIMB;
179 bitno = n % BITS_PER_MPI_LIMB;
181 if( limbno >= a->nlimbs )
182 return; /* don't need to clear this bit, it's to far to left */
183 a->d[limbno] &= ~(A_LIMB_1 << bitno);
188 * Shift A by N bits to the right
189 * FIXME: should use alloc_limb if X and A are same.
192 mpi_rshift( MPI x, MPI a, unsigned n )
199 RESIZE_IF_NEEDED(x, xsize);
203 mpihelp_rshift( xp, a->d, xsize, n);
204 MPN_NORMALIZE( xp, xsize);
211 * Shift A by COUNT limbs to the left
212 * This is used only within the MPI library
215 mpi_lshift_limbs( MPI a, unsigned int count )
224 RESIZE_IF_NEEDED( a, n+count );
226 for( i = n-1; i >= 0; i-- )
228 for(i=0; i < count; i++ )
235 * Shift A by COUNT limbs to the right
236 * This is used only within the MPI library
239 mpi_rshift_limbs( MPI a, unsigned int count )
242 mpi_size_t n = a->nlimbs;
250 for( i = 0; i < n - count; i++ )