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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
21 #include "mpi-internal.h"
24 const unsigned char __clz_tab[] = {
25 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,
26 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,
27 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,
28 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,
29 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,
30 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,
31 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,
32 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,
35 #define A_LIMB_1 ((mpi_limb_t) 1)
39 * Sometimes we have MSL (most significant limbs) which are 0;
40 * this is for some reasons not good, so this function removes them.
43 mpi_normalize( MPI a )
45 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
52 * Return the number of bits in A.
55 mpi_get_nbits( MPI a )
62 mpi_limb_t alimb = a->d[a->nlimbs-1];
64 count_leading_zeros( n, alimb );
67 n = BITS_PER_MPI_LIMB;
68 n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
77 * Test whether bit N is set.
80 mpi_test_bit( MPI a, unsigned n )
82 unsigned limbno, bitno;
85 limbno = n / BITS_PER_MPI_LIMB;
86 bitno = n % BITS_PER_MPI_LIMB;
88 if( limbno >= a->nlimbs )
89 return 0; /* too far left: this is a 0 */
91 return (limb & (A_LIMB_1 << bitno))? 1: 0;
99 mpi_set_bit( MPI a, unsigned n )
101 unsigned limbno, bitno;
103 limbno = n / BITS_PER_MPI_LIMB;
104 bitno = n % BITS_PER_MPI_LIMB;
106 if( limbno >= a->nlimbs ) { /* resize */
107 if( a->alloced >= limbno )
108 if (mpi_resize(a, limbno+1 ) < 0) return -ENOMEM;
109 a->nlimbs = limbno+1;
111 a->d[limbno] |= (A_LIMB_1<<bitno);
116 * Set bit N of A. and clear all bits above
119 mpi_set_highbit( MPI a, unsigned n )
121 unsigned limbno, bitno;
123 limbno = n / BITS_PER_MPI_LIMB;
124 bitno = n % BITS_PER_MPI_LIMB;
126 if( limbno >= a->nlimbs ) { /* resize */
127 if( a->alloced >= limbno )
128 if (mpi_resize(a, limbno+1 ) < 0) return -ENOMEM;
129 a->nlimbs = limbno+1;
131 a->d[limbno] |= (A_LIMB_1<<bitno);
132 for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
133 a->d[limbno] &= ~(A_LIMB_1 << bitno);
134 a->nlimbs = limbno+1;
139 * clear bit N of A and all bits above
142 mpi_clear_highbit( MPI a, unsigned n )
144 unsigned limbno, bitno;
146 limbno = n / BITS_PER_MPI_LIMB;
147 bitno = n % BITS_PER_MPI_LIMB;
149 if( limbno >= a->nlimbs )
150 return; /* not allocated, so need to clear bits :-) */
152 for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
153 a->d[limbno] &= ~(A_LIMB_1 << bitno);
154 a->nlimbs = limbno+1;
161 mpi_clear_bit( MPI a, unsigned n )
163 unsigned limbno, bitno;
165 limbno = n / BITS_PER_MPI_LIMB;
166 bitno = n % BITS_PER_MPI_LIMB;
168 if( limbno >= a->nlimbs )
169 return; /* don't need to clear this bit, it's to far to left */
170 a->d[limbno] &= ~(A_LIMB_1 << bitno);
175 * Shift A by N bits to the right
176 * FIXME: should use alloc_limb if X and A are same.
179 mpi_rshift( MPI x, MPI a, unsigned n )
186 if (RESIZE_IF_NEEDED(x, (size_t)xsize) < 0) return -ENOMEM;
190 mpihelp_rshift( xp, a->d, xsize, n);
191 MPN_NORMALIZE( xp, xsize);
199 * Shift A by COUNT limbs to the left
200 * This is used only within the MPI library
203 mpi_lshift_limbs( MPI a, unsigned int count )
212 if (RESIZE_IF_NEEDED( a, n+count ) < 0) return -ENOMEM;
214 for( i = n-1; i >= 0; i-- )
216 for(i=0; i < count; i++ )
224 * Shift A by COUNT limbs to the right
225 * This is used only within the MPI library
228 mpi_rshift_limbs( MPI a, unsigned int count )
231 mpi_size_t n = a->nlimbs;
239 for( i = 0; i < n - count; i++ )