OLD | NEW |
1 /* | 1 /* |
2 * mplogic.c | 2 * mplogic.c |
3 * | 3 * |
4 * Bitwise logical operations on MPI values | 4 * Bitwise logical operations on MPI values |
5 * | 5 * |
6 * This Source Code Form is subject to the terms of the Mozilla Public | 6 * This Source Code Form is subject to the terms of the Mozilla Public |
7 * License, v. 2.0. If a copy of the MPL was not distributed with this | 7 * License, v. 2.0. If a copy of the MPL was not distributed with this |
8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
9 | 9 |
10 #include "mpi-priv.h" | 10 #include "mpi-priv.h" |
11 #include "mplogic.h" | 11 #include "mplogic.h" |
12 | 12 |
13 /* {{{ Lookup table for population count */ | 13 /* {{{ Lookup table for population count */ |
14 | 14 |
15 static unsigned char bitc[] = { | 15 static unsigned char bitc[] = { |
16 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,· | 16 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, |
17 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,· | 17 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
18 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,· | 18 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, |
19 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | 19 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
20 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,· | 20 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, |
21 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | 21 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
22 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | 22 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, |
23 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,· | 23 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
24 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,· | 24 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, |
25 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | 25 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
26 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | 26 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; |
27 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,· | |
28 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,· | |
29 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,· | |
30 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,· | |
31 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 | |
32 }; | |
33 | 27 |
34 /* }}} */ | 28 /* }}} */ |
35 | 29 |
36 /*------------------------------------------------------------------------*/ | 30 /*------------------------------------------------------------------------*/ |
37 /* | 31 /* |
38 mpl_not(a, b) - compute b = ~a | 32 mpl_not(a, b) - compute b = ~a |
39 mpl_and(a, b, c) - compute c = a & b | 33 mpl_and(a, b, c) - compute c = a & b |
40 mpl_or(a, b, c) - compute c = a | b | 34 mpl_or(a, b, c) - compute c = a | b |
41 mpl_xor(a, b, c) - compute c = a ^ b | 35 mpl_xor(a, b, c) - compute c = a ^ b |
42 */ | 36 */ |
43 | 37 |
44 /* {{{ mpl_not(a, b) */ | 38 /* {{{ mpl_not(a, b) */ |
45 | 39 |
46 mp_err mpl_not(mp_int *a, mp_int *b) | 40 mp_err mpl_not(mp_int *a, mp_int *b) { |
47 { | 41 mp_err res; |
48 mp_err res; | 42 unsigned int ix; |
49 unsigned int ix; | |
50 | 43 |
51 ARGCHK(a != NULL && b != NULL, MP_BADARG); | 44 ARGCHK(a != NULL && b != NULL, MP_BADARG); |
52 | 45 |
53 if((res = mp_copy(a, b)) != MP_OKAY) | 46 if ((res = mp_copy(a, b)) != MP_OKAY) return res; |
54 return res; | |
55 | 47 |
56 /* This relies on the fact that the digit type is unsigned */ | 48 /* This relies on the fact that the digit type is unsigned */ |
57 for(ix = 0; ix < USED(b); ix++) | 49 for (ix = 0; ix < USED(b); ix++) DIGIT(b, ix) = ~DIGIT(b, ix); |
58 DIGIT(b, ix) = ~DIGIT(b, ix); | |
59 | 50 |
60 s_mp_clamp(b); | 51 s_mp_clamp(b); |
61 | 52 |
62 return MP_OKAY; | 53 return MP_OKAY; |
63 | 54 |
64 } /* end mpl_not() */ | 55 } /* end mpl_not() */ |
65 | 56 |
66 /* }}} */ | 57 /* }}} */ |
67 | 58 |
68 /* {{{ mpl_and(a, b, c) */ | 59 /* {{{ mpl_and(a, b, c) */ |
69 | 60 |
70 mp_err mpl_and(mp_int *a, mp_int *b, mp_int *c) | 61 mp_err mpl_and(mp_int *a, mp_int *b, mp_int *c) { |
71 { | 62 mp_int *which, *other; |
72 mp_int *which, *other; | 63 mp_err res; |
73 mp_err res; | 64 unsigned int ix; |
74 unsigned int ix; | |
75 | 65 |
76 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); | 66 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); |
77 | 67 |
78 if(USED(a) <= USED(b)) { | 68 if (USED(a) <= USED(b)) { |
79 which = a; | 69 which = a; |
80 other = b; | 70 other = b; |
81 } else { | 71 } else { |
82 which = b; | 72 which = b; |
83 other = a; | 73 other = a; |
84 } | 74 } |
85 | 75 |
86 if((res = mp_copy(which, c)) != MP_OKAY) | 76 if ((res = mp_copy(which, c)) != MP_OKAY) return res; |
87 return res; | |
88 | 77 |
89 for(ix = 0; ix < USED(which); ix++) | 78 for (ix = 0; ix < USED(which); ix++) DIGIT(c, ix) &= DIGIT(other, ix); |
90 DIGIT(c, ix) &= DIGIT(other, ix); | |
91 | 79 |
92 s_mp_clamp(c); | 80 s_mp_clamp(c); |
93 | 81 |
94 return MP_OKAY; | 82 return MP_OKAY; |
95 | 83 |
96 } /* end mpl_and() */ | 84 } /* end mpl_and() */ |
97 | 85 |
98 /* }}} */ | 86 /* }}} */ |
99 | 87 |
100 /* {{{ mpl_or(a, b, c) */ | 88 /* {{{ mpl_or(a, b, c) */ |
101 | 89 |
102 mp_err mpl_or(mp_int *a, mp_int *b, mp_int *c) | 90 mp_err mpl_or(mp_int *a, mp_int *b, mp_int *c) { |
103 { | 91 mp_int *which, *other; |
104 mp_int *which, *other; | 92 mp_err res; |
105 mp_err res; | 93 unsigned int ix; |
106 unsigned int ix; | |
107 | 94 |
108 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); | 95 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); |
109 | 96 |
110 if(USED(a) >= USED(b)) { | 97 if (USED(a) >= USED(b)) { |
111 which = a; | 98 which = a; |
112 other = b; | 99 other = b; |
113 } else { | 100 } else { |
114 which = b; | 101 which = b; |
115 other = a; | 102 other = a; |
116 } | 103 } |
117 | 104 |
118 if((res = mp_copy(which, c)) != MP_OKAY) | 105 if ((res = mp_copy(which, c)) != MP_OKAY) return res; |
119 return res; | |
120 | 106 |
121 for(ix = 0; ix < USED(which); ix++) | 107 for (ix = 0; ix < USED(which); ix++) DIGIT(c, ix) |= DIGIT(other, ix); |
122 DIGIT(c, ix) |= DIGIT(other, ix); | |
123 | 108 |
124 return MP_OKAY; | 109 return MP_OKAY; |
125 | 110 |
126 } /* end mpl_or() */ | 111 } /* end mpl_or() */ |
127 | 112 |
128 /* }}} */ | 113 /* }}} */ |
129 | 114 |
130 /* {{{ mpl_xor(a, b, c) */ | 115 /* {{{ mpl_xor(a, b, c) */ |
131 | 116 |
132 mp_err mpl_xor(mp_int *a, mp_int *b, mp_int *c) | 117 mp_err mpl_xor(mp_int *a, mp_int *b, mp_int *c) { |
133 { | 118 mp_int *which, *other; |
134 mp_int *which, *other; | 119 mp_err res; |
135 mp_err res; | 120 unsigned int ix; |
136 unsigned int ix; | |
137 | 121 |
138 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); | 122 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); |
139 | 123 |
140 if(USED(a) >= USED(b)) { | 124 if (USED(a) >= USED(b)) { |
141 which = a; | 125 which = a; |
142 other = b; | 126 other = b; |
143 } else { | 127 } else { |
144 which = b; | 128 which = b; |
145 other = a; | 129 other = a; |
146 } | 130 } |
147 | 131 |
148 if((res = mp_copy(which, c)) != MP_OKAY) | 132 if ((res = mp_copy(which, c)) != MP_OKAY) return res; |
149 return res; | |
150 | 133 |
151 for(ix = 0; ix < USED(which); ix++) | 134 for (ix = 0; ix < USED(which); ix++) DIGIT(c, ix) ^= DIGIT(other, ix); |
152 DIGIT(c, ix) ^= DIGIT(other, ix); | |
153 | 135 |
154 s_mp_clamp(c); | 136 s_mp_clamp(c); |
155 | 137 |
156 return MP_OKAY; | 138 return MP_OKAY; |
157 | 139 |
158 } /* end mpl_xor() */ | 140 } /* end mpl_xor() */ |
159 | 141 |
160 /* }}} */ | 142 /* }}} */ |
161 | 143 |
162 /*------------------------------------------------------------------------*/ | 144 /*------------------------------------------------------------------------*/ |
163 /* | 145 /* |
164 mpl_rsh(a, b, d) - b = a >> d | 146 mpl_rsh(a, b, d) - b = a >> d |
165 mpl_lsh(a, b, d) - b = a << d | 147 mpl_lsh(a, b, d) - b = a << d |
166 */ | 148 */ |
167 | 149 |
168 /* {{{ mpl_rsh(a, b, d) */ | 150 /* {{{ mpl_rsh(a, b, d) */ |
169 | 151 |
170 mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d) | 152 mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d) { |
171 { | 153 mp_err res; |
172 mp_err res; | |
173 | 154 |
174 ARGCHK(a != NULL && b != NULL, MP_BADARG); | 155 ARGCHK(a != NULL && b != NULL, MP_BADARG); |
175 | 156 |
176 if((res = mp_copy(a, b)) != MP_OKAY) | 157 if ((res = mp_copy(a, b)) != MP_OKAY) return res; |
177 return res; | |
178 | 158 |
179 s_mp_div_2d(b, d); | 159 s_mp_div_2d(b, d); |
180 | 160 |
181 return MP_OKAY; | 161 return MP_OKAY; |
182 | 162 |
183 } /* end mpl_rsh() */ | 163 } /* end mpl_rsh() */ |
184 | 164 |
185 /* }}} */ | 165 /* }}} */ |
186 | 166 |
187 /* {{{ mpl_lsh(a, b, d) */ | 167 /* {{{ mpl_lsh(a, b, d) */ |
188 | 168 |
189 mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d) | 169 mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d) { |
190 { | 170 mp_err res; |
191 mp_err res; | |
192 | 171 |
193 ARGCHK(a != NULL && b != NULL, MP_BADARG); | 172 ARGCHK(a != NULL && b != NULL, MP_BADARG); |
194 | 173 |
195 if((res = mp_copy(a, b)) != MP_OKAY) | 174 if ((res = mp_copy(a, b)) != MP_OKAY) return res; |
196 return res; | |
197 | 175 |
198 return s_mp_mul_2d(b, d); | 176 return s_mp_mul_2d(b, d); |
199 | 177 |
200 } /* end mpl_lsh() */ | 178 } /* end mpl_lsh() */ |
201 | 179 |
202 /* }}} */ | 180 /* }}} */ |
203 | 181 |
204 /*------------------------------------------------------------------------*/ | 182 /*------------------------------------------------------------------------*/ |
205 /* | 183 /* |
206 mpl_num_set(a, num) | 184 mpl_num_set(a, num) |
207 | 185 |
208 Count the number of set bits in the binary representation of a. | 186 Count the number of set bits in the binary representation of a. |
209 Returns MP_OKAY and sets 'num' to be the number of such bits, if | 187 Returns MP_OKAY and sets 'num' to be the number of such bits, if |
210 possible. If num is NULL, the result is thrown away, but it is | 188 possible. If num is NULL, the result is thrown away, but it is |
211 not considered an error. | 189 not considered an error. |
212 | 190 |
213 mpl_num_clear() does basically the same thing for clear bits. | 191 mpl_num_clear() does basically the same thing for clear bits. |
214 */ | 192 */ |
215 | 193 |
216 /* {{{ mpl_num_set(a, num) */ | 194 /* {{{ mpl_num_set(a, num) */ |
217 | 195 |
218 mp_err mpl_num_set(mp_int *a, int *num) | 196 mp_err mpl_num_set(mp_int *a, int *num) { |
219 { | 197 unsigned int ix; |
220 unsigned int ix; | 198 int db, nset = 0; |
221 int db, nset = 0; | 199 mp_digit cur; |
222 mp_digit cur; | 200 unsigned char reg; |
223 unsigned char reg; | |
224 | 201 |
225 ARGCHK(a != NULL, MP_BADARG); | 202 ARGCHK(a != NULL, MP_BADARG); |
226 | 203 |
227 for(ix = 0; ix < USED(a); ix++) { | 204 for (ix = 0; ix < USED(a); ix++) { |
228 cur = DIGIT(a, ix); | 205 cur = DIGIT(a, ix); |
229 | 206 |
230 for(db = 0; db < sizeof(mp_digit); db++) { | 207 for (db = 0; db < sizeof(mp_digit); db++) { |
231 reg = (unsigned char)(cur >> (CHAR_BIT * db)); | 208 reg = (unsigned char)(cur >> (CHAR_BIT * db)); |
232 | 209 |
233 nset += bitc[reg]; | 210 nset += bitc[reg]; |
234 } | 211 } |
235 } | 212 } |
236 | 213 |
237 if(num) | 214 if (num) *num = nset; |
238 *num = nset; | |
239 | 215 |
240 return MP_OKAY; | 216 return MP_OKAY; |
241 | 217 |
242 } /* end mpl_num_set() */ | 218 } /* end mpl_num_set() */ |
243 | 219 |
244 /* }}} */ | 220 /* }}} */ |
245 | 221 |
246 /* {{{ mpl_num_clear(a, num) */ | 222 /* {{{ mpl_num_clear(a, num) */ |
247 | 223 |
248 mp_err mpl_num_clear(mp_int *a, int *num) | 224 mp_err mpl_num_clear(mp_int *a, int *num) { |
249 { | 225 unsigned int ix; |
250 unsigned int ix; | 226 int db, nset = 0; |
251 int db, nset = 0; | 227 mp_digit cur; |
252 mp_digit cur; | 228 unsigned char reg; |
253 unsigned char reg; | |
254 | 229 |
255 ARGCHK(a != NULL, MP_BADARG); | 230 ARGCHK(a != NULL, MP_BADARG); |
256 | 231 |
257 for(ix = 0; ix < USED(a); ix++) { | 232 for (ix = 0; ix < USED(a); ix++) { |
258 cur = DIGIT(a, ix); | 233 cur = DIGIT(a, ix); |
259 | 234 |
260 for(db = 0; db < sizeof(mp_digit); db++) { | 235 for (db = 0; db < sizeof(mp_digit); db++) { |
261 reg = (unsigned char)(cur >> (CHAR_BIT * db)); | 236 reg = (unsigned char)(cur >> (CHAR_BIT * db)); |
262 | 237 |
263 nset += bitc[UCHAR_MAX - reg]; | 238 nset += bitc[UCHAR_MAX - reg]; |
264 } | 239 } |
265 } | 240 } |
266 | 241 |
267 if(num) | 242 if (num) *num = nset; |
268 *num = nset; | |
269 | 243 |
270 return MP_OKAY; | 244 return MP_OKAY; |
271 | 245 |
272 | |
273 } /* end mpl_num_clear() */ | 246 } /* end mpl_num_clear() */ |
274 | 247 |
275 /* }}} */ | 248 /* }}} */ |
276 | 249 |
277 /*------------------------------------------------------------------------*/ | 250 /*------------------------------------------------------------------------*/ |
278 /* | 251 /* |
279 mpl_parity(a) | 252 mpl_parity(a) |
280 | 253 |
281 Determines the bitwise parity of the value given. Returns MP_EVEN | 254 Determines the bitwise parity of the value given. Returns MP_EVEN |
282 if an even number of digits are set, MP_ODD if an odd number are | 255 if an even number of digits are set, MP_ODD if an odd number are |
283 set. | 256 set. |
284 */ | 257 */ |
285 | 258 |
286 /* {{{ mpl_parity(a) */ | 259 /* {{{ mpl_parity(a) */ |
287 | 260 |
288 mp_err mpl_parity(mp_int *a) | 261 mp_err mpl_parity(mp_int *a) { |
289 { | |
290 unsigned int ix; | 262 unsigned int ix; |
291 int par = 0; | 263 int par = 0; |
292 mp_digit cur; | 264 mp_digit cur; |
293 | 265 |
294 ARGCHK(a != NULL, MP_BADARG); | 266 ARGCHK(a != NULL, MP_BADARG); |
295 | 267 |
296 for(ix = 0; ix < USED(a); ix++) { | 268 for (ix = 0; ix < USED(a); ix++) { |
297 int shft = (sizeof(mp_digit) * CHAR_BIT) / 2; | 269 int shft = (sizeof(mp_digit) * CHAR_BIT) / 2; |
298 | 270 |
299 cur = DIGIT(a, ix); | 271 cur = DIGIT(a, ix); |
300 | 272 |
301 /* Compute parity for current digit */ | 273 /* Compute parity for current digit */ |
302 while(shft != 0) { | 274 while (shft != 0) { |
303 cur ^= (cur >> shft); | 275 cur ^= (cur >> shft); |
304 shft >>= 1; | 276 shft >>= 1; |
305 } | 277 } |
306 cur &= 1; | 278 cur &= 1; |
307 | 279 |
308 /* XOR with running parity so far */ | 280 /* XOR with running parity so far */ |
309 par ^= cur; | 281 par ^= cur; |
310 } | 282 } |
311 | 283 |
312 if(par) | 284 if (par) |
313 return MP_ODD; | 285 return MP_ODD; |
314 else | 286 else |
315 return MP_EVEN; | 287 return MP_EVEN; |
316 | 288 |
317 } /* end mpl_parity() */ | 289 } /* end mpl_parity() */ |
318 | 290 |
319 /* }}} */ | 291 /* }}} */ |
320 | 292 |
321 /* | 293 /* |
322 mpl_set_bit | 294 mpl_set_bit |
323 | 295 |
324 Returns MP_OKAY or some error code. | 296 Returns MP_OKAY or some error code. |
325 Grows a if needed to set a bit to 1. | 297 Grows a if needed to set a bit to 1. |
326 */ | 298 */ |
327 mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value) | 299 mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value) { |
328 { | 300 mp_size ix; |
329 mp_size ix; | 301 mp_err rv; |
330 mp_err rv; | 302 mp_digit mask; |
331 mp_digit mask; | |
332 | 303 |
333 ARGCHK(a != NULL, MP_BADARG); | 304 ARGCHK(a != NULL, MP_BADARG); |
334 | 305 |
335 ix = bitNum / MP_DIGIT_BIT; | 306 ix = bitNum / MP_DIGIT_BIT; |
336 if (ix + 1 > MP_USED(a)) { | 307 if (ix + 1 > MP_USED(a)) { |
337 rv = s_mp_pad(a, ix + 1); | 308 rv = s_mp_pad(a, ix + 1); |
338 if (rv != MP_OKAY) | 309 if (rv != MP_OKAY) return rv; |
339 return rv; | |
340 } | 310 } |
341 | 311 |
342 bitNum = bitNum % MP_DIGIT_BIT; | 312 bitNum = bitNum % MP_DIGIT_BIT; |
343 mask = (mp_digit)1 << bitNum; | 313 mask = (mp_digit)1 << bitNum; |
344 if (value) | 314 if (value) |
345 MP_DIGIT(a,ix) |= mask; | 315 MP_DIGIT(a, ix) |= mask; |
346 else | 316 else |
347 MP_DIGIT(a,ix) &= ~mask; | 317 MP_DIGIT(a, ix) &= ~mask; |
348 s_mp_clamp(a); | 318 s_mp_clamp(a); |
349 return MP_OKAY; | 319 return MP_OKAY; |
350 } | 320 } |
351 | 321 |
352 /* | 322 /* |
353 mpl_get_bit | 323 mpl_get_bit |
354 | 324 |
355 returns 0 or 1 or some (negative) error code. | 325 returns 0 or 1 or some (negative) error code. |
356 */ | 326 */ |
357 mp_err mpl_get_bit(const mp_int *a, mp_size bitNum) | 327 mp_err mpl_get_bit(const mp_int *a, mp_size bitNum) { |
358 { | 328 mp_size bit, ix; |
359 mp_size bit, ix; | 329 mp_err rv; |
360 mp_err rv; | |
361 | 330 |
362 ARGCHK(a != NULL, MP_BADARG); | 331 ARGCHK(a != NULL, MP_BADARG); |
363 | 332 |
364 ix = bitNum / MP_DIGIT_BIT; | 333 ix = bitNum / MP_DIGIT_BIT; |
365 ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE); | 334 ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE); |
366 | 335 |
367 bit = bitNum % MP_DIGIT_BIT; | 336 bit = bitNum % MP_DIGIT_BIT; |
368 rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1; | 337 rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1; |
369 return rv; | 338 return rv; |
370 } | 339 } |
371 | 340 |
372 /* | 341 /* |
373 mpl_get_bits | 342 mpl_get_bits |
374 - Extracts numBits bits from a, where the least significant extracted bit | 343 - Extracts numBits bits from a, where the least significant extracted bit |
375 is bit lsbNum. Returns a negative value if error occurs. | 344 is bit lsbNum. Returns a negative value if error occurs. |
376 - Because sign bit is used to indicate error, maximum number of bits to | 345 - Because sign bit is used to indicate error, maximum number of bits to |
377 be returned is the lesser of (a) the number of bits in an mp_digit, or | 346 be returned is the lesser of (a) the number of bits in an mp_digit, or |
378 (b) one less than the number of bits in an mp_err. | 347 (b) one less than the number of bits in an mp_err. |
379 - lsbNum + numbits can be greater than the number of significant bits in | 348 - lsbNum + numbits can be greater than the number of significant bits in |
380 integer a, as long as bit lsbNum is in the high order digit of a. | 349 integer a, as long as bit lsbNum is in the high order digit of a. |
381 */ | 350 */ |
382 mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits) | 351 mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits) { |
383 { | 352 mp_size rshift = (lsbNum % MP_DIGIT_BIT); |
384 mp_size rshift = (lsbNum % MP_DIGIT_BIT); | 353 mp_size lsWndx = (lsbNum / MP_DIGIT_BIT); |
385 mp_size lsWndx = (lsbNum / MP_DIGIT_BIT); | 354 mp_digit *digit = MP_DIGITS(a) + lsWndx; |
386 mp_digit * digit = MP_DIGITS(a) + lsWndx; | 355 mp_digit mask = ((1 << numBits) - 1); |
387 mp_digit mask = ((1 << numBits) - 1); | |
388 | 356 |
389 ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG); | 357 ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG); |
390 ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE); | 358 ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE); |
391 | 359 |
392 if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) || | 360 if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) || |
393 (lsWndx + 1 >= MP_USED(a))) { | 361 (lsWndx + 1 >= MP_USED(a))) { |
394 mask &= (digit[0] >> rshift); | 362 mask &= (digit[0] >> rshift); |
395 } else { | 363 } else { |
396 mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift))); | 364 mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift))); |
397 } | 365 } |
398 return (mp_err)mask; | 366 return (mp_err)mask; |
399 } | 367 } |
400 | 368 |
401 /* | 369 /* |
402 mpl_significant_bits | 370 mpl_significant_bits |
403 returns number of significnant bits in abs(a). | 371 returns number of significnant bits in abs(a). |
404 returns 1 if value is zero. | 372 returns 1 if value is zero. |
405 */ | 373 */ |
406 mp_err mpl_significant_bits(const mp_int *a) | 374 mp_err mpl_significant_bits(const mp_int *a) { |
407 { | 375 mp_err bits = 0; |
408 mp_err bits » = 0; | 376 int ix; |
409 int ix; | |
410 | 377 |
411 ARGCHK(a != NULL, MP_BADARG); | 378 ARGCHK(a != NULL, MP_BADARG); |
412 | 379 |
413 ix = MP_USED(a); | 380 ix = MP_USED(a); |
414 for (ix = MP_USED(a); ix > 0; ) { | 381 for (ix = MP_USED(a); ix > 0;) { |
415 mp_digit d; | 382 mp_digit d; |
416 d = MP_DIGIT(a, --ix); | 383 d = MP_DIGIT(a, --ix); |
417 if (d) { | 384 if (d) { |
418 while (d) { | 385 while (d) { |
419 » ++bits; | 386 ++bits; |
420 » d >>= 1; | 387 d >>= 1; |
421 } | 388 } |
422 break; | 389 break; |
423 } | 390 } |
424 } | 391 } |
425 bits += ix * MP_DIGIT_BIT; | 392 bits += ix * MP_DIGIT_BIT; |
426 if (!bits) | 393 if (!bits) bits = 1; |
427 bits = 1; | |
428 return bits; | 394 return bits; |
429 } | 395 } |
430 | 396 |
431 /*------------------------------------------------------------------------*/ | 397 /*------------------------------------------------------------------------*/ |
432 /* HERE THERE BE DRAGONS */ | 398 /* HERE THERE BE DRAGONS */ |
OLD | NEW |