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