some cleanups
[gnupg.git] / mpi / mpi-bit.c
1 /* mpi-bit.c  -  MPI bit level fucntions
2  *      Copyright (C) 1998 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 2 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, 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 <assert.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 __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
53
54
55 /****************
56  * Return the number of bits in A.
57  */
58 unsigned
59 mpi_get_nbits( MPI a )
60 {
61     unsigned n;
62
63     if( a->nlimbs ) {
64         mpi_limb_t alimb = a->d[a->nlimbs-1];
65         if( alimb )
66             count_leading_zeros( n, alimb );
67         else
68             n = BITS_PER_MPI_LIMB;
69         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
70     }
71     else
72         n = 0;
73     return n;
74 }
75
76
77 /****************
78  * Test wether bit N is set.
79  */
80 int
81 mpi_test_bit( MPI a, unsigned n )
82 {
83     unsigned limbno, bitno;
84     mpi_limb_t limb;
85
86     limbno = n / BITS_PER_MPI_LIMB;
87     bitno  = n % BITS_PER_MPI_LIMB;
88
89     if( limbno >= a->nlimbs )
90         return 0; /* too far left: this is a 0 */
91     limb = a->d[limbno];
92     return (limb & (A_LIMB_1 << bitno))? 1: 0;
93 }
94
95
96 /****************
97  * Set bit N of A.
98  */
99 void
100 mpi_set_bit( MPI a, unsigned n )
101 {
102     unsigned limbno, bitno;
103
104     limbno = n / BITS_PER_MPI_LIMB;
105     bitno  = n % BITS_PER_MPI_LIMB;
106
107     if( limbno >= a->nlimbs ) { /* resize */
108         if( a->alloced >= limbno )
109             mpi_resize(a, limbno+1 );
110         a->nlimbs = limbno+1;
111     }
112     a->d[limbno] |= (A_LIMB_1<<bitno);
113 }
114
115 /****************
116  * Set bit N of A. and clear all bits above
117  */
118 void
119 mpi_set_highbit( MPI a, unsigned n )
120 {
121     unsigned limbno, bitno;
122
123     limbno = n / BITS_PER_MPI_LIMB;
124     bitno  = n % BITS_PER_MPI_LIMB;
125
126     if( limbno >= a->nlimbs ) { /* resize */
127         if( a->alloced >= limbno )
128             mpi_resize(a, limbno+1 );
129         a->nlimbs = limbno+1;
130     }
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;
135 }
136
137 /****************
138  * clear bit N of A and all bits above
139  */
140 void
141 mpi_clear_highbit( MPI a, unsigned n )
142 {
143     unsigned limbno, bitno;
144
145     limbno = n / BITS_PER_MPI_LIMB;
146     bitno  = n % BITS_PER_MPI_LIMB;
147
148     if( limbno >= a->nlimbs )
149         return; /* not allocated, so need to clear bits :-) */
150
151     for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
152         a->d[limbno] &= ~(A_LIMB_1 << bitno);
153     a->nlimbs = limbno+1;
154 }
155
156 /****************
157  * Clear bit N of A.
158  */
159 void
160 mpi_clear_bit( MPI a, unsigned n )
161 {
162     unsigned limbno, bitno;
163
164     limbno = n / BITS_PER_MPI_LIMB;
165     bitno  = n % BITS_PER_MPI_LIMB;
166
167     if( limbno >= a->nlimbs )
168         return; /* don't need to clear this bit, it's to far to left */
169     a->d[limbno] &= ~(A_LIMB_1 << bitno);
170 }
171
172
173 void
174 mpi_set_bytes( MPI a, unsigned nbits, byte (*fnc)(int), int opaque )
175 {
176     byte *p;
177     unsigned nlimbs, nlimbs2, xbits, xbytes;
178     unsigned n;
179     int i;
180
181     nlimbs = nbits / BITS_PER_MPI_LIMB;
182     xbits = nbits % BITS_PER_MPI_LIMB;
183     nlimbs2 = xbits? (nlimbs+1):nlimbs;
184     xbytes = xbits / 8;
185     xbits = xbits % 8;
186     if( a->alloced < nlimbs2 )
187         mpi_resize(a, nlimbs2 );
188     a->nlimbs = nlimbs2;
189     for(n=0; n < nlimbs; n++ ) {
190         p = (byte*)(a->d+n);
191       #ifdef LITTLE_ENDIAN_HOST
192         for(i=0; i < BYTES_PER_MPI_LIMB; i++ )
193             p[i] = fnc(opaque);
194       #else
195         for(i=BYTES_PER_MPI_LIMB-1; i>=0; i-- )
196             p[i] = fnc(opaque);
197       #endif
198     }
199     if( xbytes ) {
200         p = (byte*)(a->d+n);
201       #ifdef LITTLE_ENDIAN_HOST
202         for(i=0; i < xbytes; i++ )
203             p[i] = fnc(opaque);
204       #else
205         for(i=xbytes-1; i>=0; i-- )
206             p[i] = fnc(opaque);
207       #endif
208     }
209   #if 0 /* fixme: set complete random byte and clear out the unwanted ones*/
210     if( xbits ) {
211         p = (byte*)(a->d+n);
212       #ifdef LITTLE_ENDIAN_HOST
213         for(i=0; i < xbytes; i++ )
214             p[i] = fnc(opaque);
215       #else
216         for(i=xbytes-1; i>=0; i-- )
217             p[i] = fnc(opaque);
218       #endif
219     }
220   #endif
221 }
222
223 /****************
224  * Shift A by N bits to the right
225  * FIXME: should use alloc_limb if X and A are same.
226  */
227 void
228 mpi_rshift( MPI x, MPI a, unsigned n )
229 {
230     mpi_ptr_t xp;
231     mpi_size_t xsize;
232
233     xsize = a->nlimbs;
234     x->sign = a->sign;
235     RESIZE_IF_NEEDED(x, xsize);
236     xp = x->d;
237
238     if( xsize ) {
239         mpihelp_rshift( xp, a->d, xsize, n);
240         MPN_NORMALIZE( xp, xsize);
241     }
242     x->nlimbs = xsize;
243 }
244