854c9c6da025ef905178cd1b568ff0cbeb1609f2
[linux-2.6.git] / lib / 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 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 "mpi-internal.h"
22 #include "longlong.h"
23
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,
26             5, 5, 5, 5, 5, 5, 5, 5,
27         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
28             6, 6, 6, 6, 6, 6, 6, 6,
29         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
30             7, 7, 7, 7, 7, 7, 7, 7,
31         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
32             7, 7, 7, 7, 7, 7, 7, 7,
33         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
34             8, 8, 8, 8, 8, 8, 8, 8,
35         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
36             8, 8, 8, 8, 8, 8, 8, 8,
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,
38             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,
40             8, 8, 8, 8, 8, 8, 8, 8,
41 };
42
43 #define A_LIMB_1 ((mpi_limb_t) 1)
44
45 /****************
46  * Sometimes we have MSL (most significant limbs) which are 0;
47  * this is for some reasons not good, so this function removes them.
48  */
49 void mpi_normalize(MPI a)
50 {
51         for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
52                 ;
53 }
54
55 /****************
56  * Return the number of bits in A.
57  */
58 unsigned mpi_get_nbits(MPI a)
59 {
60         unsigned n;
61
62         mpi_normalize(a);
63
64         if (a->nlimbs) {
65                 mpi_limb_t alimb = a->d[a->nlimbs - 1];
66                 if (alimb)
67                         count_leading_zeros(n, alimb);
68                 else
69                         n = BITS_PER_MPI_LIMB;
70                 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
71         } else
72                 n = 0;
73         return n;
74 }
75 EXPORT_SYMBOL_GPL(mpi_get_nbits);
76
77 /****************
78  * Test whether bit N is set.
79  */
80 int mpi_test_bit(MPI a, unsigned n)
81 {
82         unsigned limbno, bitno;
83         mpi_limb_t limb;
84
85         limbno = n / BITS_PER_MPI_LIMB;
86         bitno = n % BITS_PER_MPI_LIMB;
87
88         if (limbno >= a->nlimbs)
89                 return 0;       /* too far left: this is a 0 */
90         limb = a->d[limbno];
91         return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
92 }
93
94 /****************
95  * Set bit N of A.
96  */
97 int mpi_set_bit(MPI a, unsigned n)
98 {
99         unsigned limbno, bitno;
100
101         limbno = n / BITS_PER_MPI_LIMB;
102         bitno = n % BITS_PER_MPI_LIMB;
103
104         if (limbno >= a->nlimbs) {      /* resize */
105                 if (a->alloced >= limbno)
106                         if (mpi_resize(a, limbno + 1) < 0)
107                                 return -ENOMEM;
108                 a->nlimbs = limbno + 1;
109         }
110         a->d[limbno] |= (A_LIMB_1 << bitno);
111         return 0;
112 }
113
114 /****************
115  * Set bit N of A. and clear all bits above
116  */
117 int mpi_set_highbit(MPI a, unsigned n)
118 {
119         unsigned limbno, bitno;
120
121         limbno = n / BITS_PER_MPI_LIMB;
122         bitno = n % BITS_PER_MPI_LIMB;
123
124         if (limbno >= a->nlimbs) {      /* resize */
125                 if (a->alloced >= limbno)
126                         if (mpi_resize(a, limbno + 1) < 0)
127                                 return -ENOMEM;
128                 a->nlimbs = limbno + 1;
129         }
130         a->d[limbno] |= (A_LIMB_1 << bitno);
131         for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
132                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
133         a->nlimbs = limbno + 1;
134         return 0;
135 }
136
137 /****************
138  * clear bit N of A and all bits above
139  */
140 void mpi_clear_highbit(MPI a, unsigned n)
141 {
142         unsigned limbno, bitno;
143
144         limbno = n / BITS_PER_MPI_LIMB;
145         bitno = n % BITS_PER_MPI_LIMB;
146
147         if (limbno >= a->nlimbs)
148                 return;         /* not allocated, so need to clear bits :-) */
149
150         for (; bitno < BITS_PER_MPI_LIMB; bitno++)
151                 a->d[limbno] &= ~(A_LIMB_1 << bitno);
152         a->nlimbs = limbno + 1;
153 }
154
155 /****************
156  * Clear bit N of A.
157  */
158 void mpi_clear_bit(MPI a, unsigned n)
159 {
160         unsigned limbno, bitno;
161
162         limbno = n / BITS_PER_MPI_LIMB;
163         bitno = n % BITS_PER_MPI_LIMB;
164
165         if (limbno >= a->nlimbs)
166                 return;         /* don't need to clear this bit, it's to far to left */
167         a->d[limbno] &= ~(A_LIMB_1 << bitno);
168 }
169
170 /****************
171  * Shift A by N bits to the right
172  * FIXME: should use alloc_limb if X and A are same.
173  */
174 int mpi_rshift(MPI x, MPI a, unsigned n)
175 {
176         mpi_ptr_t xp;
177         mpi_size_t xsize;
178
179         xsize = a->nlimbs;
180         x->sign = a->sign;
181         if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
182                 return -ENOMEM;
183         xp = x->d;
184
185         if (xsize) {
186                 mpihelp_rshift(xp, a->d, xsize, n);
187                 MPN_NORMALIZE(xp, xsize);
188         }
189         x->nlimbs = xsize;
190         return 0;
191 }
192
193 /****************
194  * Shift A by COUNT limbs to the left
195  * This is used only within the MPI library
196  */
197 int mpi_lshift_limbs(MPI a, unsigned int count)
198 {
199         mpi_ptr_t ap = a->d;
200         int n = a->nlimbs;
201         int i;
202
203         if (!count || !n)
204                 return 0;
205
206         if (RESIZE_IF_NEEDED(a, n + count) < 0)
207                 return -ENOMEM;
208
209         for (i = n - 1; i >= 0; i--)
210                 ap[i + count] = ap[i];
211         for (i = 0; i < count; i++)
212                 ap[i] = 0;
213         a->nlimbs += count;
214         return 0;
215 }
216
217 /****************
218  * Shift A by COUNT limbs to the right
219  * This is used only within the MPI library
220  */
221 void mpi_rshift_limbs(MPI a, unsigned int count)
222 {
223         mpi_ptr_t ap = a->d;
224         mpi_size_t n = a->nlimbs;
225         unsigned int i;
226
227         if (count >= n) {
228                 a->nlimbs = 0;
229                 return;
230         }
231
232         for (i = 0; i < n - count; i++)
233                 ap[i] = ap[i + count];
234         ap[i] = 0;
235         a->nlimbs -= count;
236 }