The Tor Browser / file comparison

comparison: security/nss/lib/freebl/mpi/mplogic.c

security/nss/lib/freebl/mpi/mplogic.c

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial