* gpgkeys_hkp.c (send_key, get_key, get_name, search_key, main): Add
[gnupg.git] / mpi / mpi-bit.c
1 /* mpi-bit.c  -  MPI bit level fucntions
2  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
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 3 of the License, or
9  * (at your option) any later version.
10  *
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.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #include <config.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <assert.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 __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 mpi_normalize( MPI 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
70 mpi_get_nbits( MPI a )
71 {
72     unsigned n;
73
74     mpi_normalize( a );
75     if( a->nlimbs ) {
76         mpi_limb_t alimb = a->d[a->nlimbs-1];
77         if( alimb )
78             count_leading_zeros( n, alimb );
79         else
80             n = BITS_PER_MPI_LIMB;
81         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
82     }
83     else
84         n = 0;
85     return n;
86 }
87
88
89 /****************
90  * Test whether bit N is set.
91  */
92 int
93 mpi_test_bit( MPI a, unsigned n )
94 {
95     unsigned limbno, bitno;
96     mpi_limb_t limb;
97
98     limbno = n / BITS_PER_MPI_LIMB;
99     bitno  = n % BITS_PER_MPI_LIMB;
100
101     if( limbno >= a->nlimbs )
102         return 0; /* too far left: this is a 0 */
103     limb = a->d[limbno];
104     return (limb & (A_LIMB_1 << bitno))? 1: 0;
105 }
106
107
108 /****************
109  * Set bit N of A.
110  */
111 void
112 mpi_set_bit( MPI a, unsigned n )
113 {
114     unsigned limbno, bitno;
115
116     limbno = n / BITS_PER_MPI_LIMB;
117     bitno  = n % BITS_PER_MPI_LIMB;
118
119     if( limbno >= a->nlimbs ) { /* resize */
120         if( a->alloced >= limbno )
121             mpi_resize(a, limbno+1 );
122         a->nlimbs = limbno+1;
123     }
124     a->d[limbno] |= (A_LIMB_1<<bitno);
125 }
126
127 /****************
128  * Set bit N of A. and clear all bits above
129  */
130 void
131 mpi_set_highbit( MPI a, unsigned n )
132 {
133     unsigned limbno, bitno;
134
135     limbno = n / BITS_PER_MPI_LIMB;
136     bitno  = n % BITS_PER_MPI_LIMB;
137
138     if( limbno >= a->nlimbs ) { /* resize */
139         if( a->alloced >= limbno )
140             mpi_resize(a, limbno+1 );
141         a->nlimbs = limbno+1;
142     }
143     a->d[limbno] |= (A_LIMB_1<<bitno);
144     for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
145         a->d[limbno] &= ~(A_LIMB_1 << bitno);
146     a->nlimbs = limbno+1;
147 }
148
149 /****************
150  * clear bit N of A and all bits above
151  */
152 void
153 mpi_clear_highbit( MPI a, unsigned n )
154 {
155     unsigned limbno, bitno;
156
157     limbno = n / BITS_PER_MPI_LIMB;
158     bitno  = n % BITS_PER_MPI_LIMB;
159
160     if( limbno >= a->nlimbs )
161         return; /* not allocated, so need to clear bits :-) */
162
163     for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
164         a->d[limbno] &= ~(A_LIMB_1 << bitno);
165     a->nlimbs = limbno+1;
166 }
167
168 /****************
169  * Clear bit N of A.
170  */
171 void
172 mpi_clear_bit( MPI a, unsigned n )
173 {
174     unsigned limbno, bitno;
175
176     limbno = n / BITS_PER_MPI_LIMB;
177     bitno  = n % BITS_PER_MPI_LIMB;
178
179     if( limbno >= a->nlimbs )
180         return; /* don't need to clear this bit, it's to far to left */
181     a->d[limbno] &= ~(A_LIMB_1 << bitno);
182 }
183
184
185 /****************
186  * Shift A by N bits to the right
187  * FIXME: should use alloc_limb if X and A are same.
188  */
189 void
190 mpi_rshift( MPI x, MPI a, unsigned n )
191 {
192     mpi_ptr_t xp;
193     mpi_size_t xsize;
194
195     xsize = a->nlimbs;
196     x->sign = a->sign;
197     RESIZE_IF_NEEDED(x, xsize);
198     xp = x->d;
199
200     if( xsize ) {
201         mpihelp_rshift( xp, a->d, xsize, n);
202         MPN_NORMALIZE( xp, xsize);
203     }
204     x->nlimbs = xsize;
205 }
206
207
208 /****************
209  * Shift A by COUNT limbs to the left
210  * This is used only within the MPI library
211  */
212 void
213 mpi_lshift_limbs( MPI a, unsigned int count )
214 {
215     mpi_ptr_t ap = a->d;
216     int n = a->nlimbs;
217     int i;
218
219     if( !count || !n )
220         return;
221
222     RESIZE_IF_NEEDED( a, n+count );
223
224     for( i = n-1; i >= 0; i-- )
225         ap[i+count] = ap[i];
226     for(i=0; i < count; i++ )
227         ap[i] = 0;
228     a->nlimbs += count;
229 }
230
231
232 /****************
233  * Shift A by COUNT limbs to the right
234  * This is used only within the MPI library
235  */
236 void
237 mpi_rshift_limbs( MPI a, unsigned int count )
238 {
239     mpi_ptr_t ap = a->d;
240     mpi_size_t n = a->nlimbs;
241     unsigned int i;
242
243     if( count >= n ) {
244         a->nlimbs = 0;
245         return;
246     }
247
248     for( i = 0; i < n - count; i++ )
249         ap[i] = ap[i+count];
250     ap[i] = 0;
251     a->nlimbs -= count;
252 }
253
254