aboutsummaryrefslogtreecommitdiffstats
path: root/lib/mpi/mpi-bit.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/mpi/mpi-bit.c')
-rw-r--r--lib/mpi/mpi-bit.c236
1 files changed, 236 insertions, 0 deletions
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
new file mode 100644
index 000000000000..854c9c6da025
--- /dev/null
+++ b/lib/mpi/mpi-bit.c
@@ -0,0 +1,236 @@
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
24const 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 */
49void 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 */
58unsigned 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}
75EXPORT_SYMBOL_GPL(mpi_get_nbits);
76
77/****************
78 * Test whether bit N is set.
79 */
80int 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 */
97int 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 */
117int 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 */
140void 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 */
158void 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 */
174int 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 */
197int 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 */
221void 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}