Trust stuff works partly.
[libgcrypt.git] / mpi / mpi-bit.c
1 /* mpi-bit.c  -  MPI bit level fucntions
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 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  * G10 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 unsigned char
31 __clz_tab[] =
32 {
33   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,
34   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,
35   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,
36   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,
37   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,
38   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,
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 };
42 #endif
43
44
45
46
47
48
49
50
51 /****************
52  * Return the number of bits in A.
53  */
54 unsigned
55 mpi_get_nbits( MPI a )
56 {
57     unsigned n;
58
59     if( a->nlimbs ) {
60         mpi_limb_t alimb = a->d[a->nlimbs-1];
61         if( alimb )
62             count_leading_zeros( n, alimb );
63         else
64             n = BITS_PER_MPI_LIMB;
65         n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
66     }
67     else
68         n = 0;
69     return n;
70 }
71
72
73 /****************
74  * Test wether bit N is set.
75  */
76 int
77 mpi_test_bit( MPI a, unsigned n )
78 {
79     unsigned limbno, bitno;
80     mpi_limb_t limb;
81
82     limbno = n / BITS_PER_MPI_LIMB;
83     bitno  = n % BITS_PER_MPI_LIMB;
84
85     if( limbno >= a->nlimbs )
86         return 0; /* too far left: this is a 0 */
87     limb = a->d[limbno];
88     return (limb & (1 << bitno))? 1: 0;
89 }
90
91
92 /****************
93  * Set bit N of A.
94  */
95 void
96 mpi_set_bit( MPI a, unsigned n )
97 {
98     unsigned limbno, bitno;
99
100     limbno = n / BITS_PER_MPI_LIMB;
101     bitno  = n % BITS_PER_MPI_LIMB;
102
103     if( limbno >= a->nlimbs ) { /* resize */
104         if( a->alloced >= limbno )
105             mpi_resize(a, limbno+1 );
106         a->nlimbs = limbno+1;
107     }
108     a->d[limbno] |= (1<<bitno);
109 }
110
111 /****************
112  * Set bit N of A. and clear all bits above
113  */
114 void
115 mpi_set_highbit( MPI a, unsigned n )
116 {
117     unsigned limbno, bitno;
118
119     limbno = n / BITS_PER_MPI_LIMB;
120     bitno  = n % BITS_PER_MPI_LIMB;
121
122     if( limbno >= a->nlimbs ) { /* resize */
123         if( a->alloced >= limbno )
124             mpi_resize(a, limbno+1 );
125         a->nlimbs = limbno+1;
126     }
127     a->d[limbno] |= (1<<bitno);
128     for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
129         a->d[limbno] &= ~(1 << bitno);
130     a->nlimbs = limbno+1;
131 }
132
133 /****************
134  * Clear bit N of A.
135  */
136 void
137 mpi_clear_bit( MPI a, unsigned n )
138 {
139     unsigned limbno, bitno;
140
141     limbno = n / BITS_PER_MPI_LIMB;
142     bitno  = n % BITS_PER_MPI_LIMB;
143
144     if( limbno >= a->nlimbs )
145         return; /* don't need to clear this bit, it's to far to left */
146     a->d[limbno] &= ~(1 << bitno);
147 }
148
149
150 void
151 mpi_set_bytes( MPI a, unsigned nbits, byte (*fnc)(int), int opaque )
152 {
153     byte *p;
154     unsigned nlimbs, nlimbs2, xbits, xbytes;
155     unsigned n;
156     int i;
157
158     nlimbs = nbits / BITS_PER_MPI_LIMB;
159     xbits = nbits % BITS_PER_MPI_LIMB;
160     nlimbs2 = xbits? (nlimbs+1):nlimbs;
161     xbytes = xbits / 8;
162     xbits = xbits % 8;
163     if( a->alloced < nlimbs2 )
164         mpi_resize(a, nlimbs2 );
165     a->nlimbs = nlimbs2;
166     for(n=0; n < nlimbs; n++ ) {
167         p = (byte*)(a->d+n);
168       #ifdef LITTLE_ENDIAN_HOST
169         for(i=0; i < BYTES_PER_MPI_LIMB; i++ )
170             p[i] = fnc(opaque);
171       #else
172         for(i=BYTES_PER_MPI_LIMB-1; i>=0; i-- )
173             p[i] = fnc(opaque);
174       #endif
175     }
176     if( xbytes ) {
177         p = (byte*)(a->d+n);
178       #ifdef LITTLE_ENDIAN_HOST
179         for(i=0; i < xbytes; i++ )
180             p[i] = fnc(opaque);
181       #else
182         for(i=xbytes-1; i>=0; i-- )
183             p[i] = fnc(opaque);
184       #endif
185     }
186   #if 0 /* fixme: set complete random byte and clear out the unwanted ones*/
187     if( xbits ) {
188         p = (byte*)(a->d+n);
189       #ifdef LITTLE_ENDIAN_HOST
190         for(i=0; i < xbytes; i++ )
191             p[i] = fnc(opaque);
192       #else
193         for(i=xbytes-1; i>=0; i-- )
194             p[i] = fnc(opaque);
195       #endif
196     }
197   #endif
198 }
199
200 /****************
201  * Shift A by N bits to the right
202  * FIXME: should use alloc_limb if X and A are same.
203  */
204 void
205 mpi_rshift( MPI x, MPI a, unsigned n )
206 {
207     mpi_ptr_t xp;
208     mpi_size_t xsize;
209
210     xsize = a->nlimbs;
211     x->sign = a->sign;
212     RESIZE_IF_NEEDED(x, xsize);
213     xp = x->d;
214
215     if( xsize ) {
216         mpihelp_rshift( xp, a->d, xsize, n);
217         MPN_NORMALIZE( xp, xsize);
218     }
219     x->nlimbs = xsize;
220 }
221