security/nss/lib/freebl/mpi/mplogic.c@b8a032363ba2
security/nss/lib/freebl/mpi/mplogic.c
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
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/. */
10 #include "mpi-priv.h"
11 #include "mplogic.h"
13 /* {{{ Lookup table for population count */
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 };
34 /* }}} */
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 */
44 /* {{{ mpl_not(a, b) */
46 mp_err mpl_not(mp_int *a, mp_int *b)
47 {
48 mp_err res;
49 unsigned int ix;
51 ARGCHK(a != NULL && b != NULL, MP_BADARG);
53 if((res = mp_copy(a, b)) != MP_OKAY)
54 return res;
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);
60 s_mp_clamp(b);
62 return MP_OKAY;
64 } /* end mpl_not() */
66 /* }}} */
68 /* {{{ mpl_and(a, b, c) */
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;
76 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
78 if(USED(a) <= USED(b)) {
79 which = a;
80 other = b;
81 } else {
82 which = b;
83 other = a;
84 }
86 if((res = mp_copy(which, c)) != MP_OKAY)
87 return res;
89 for(ix = 0; ix < USED(which); ix++)
90 DIGIT(c, ix) &= DIGIT(other, ix);
92 s_mp_clamp(c);
94 return MP_OKAY;
96 } /* end mpl_and() */
98 /* }}} */
100 /* {{{ mpl_or(a, b, c) */
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;
108 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
110 if(USED(a) >= USED(b)) {
111 which = a;
112 other = b;
113 } else {
114 which = b;
115 other = a;
116 }
118 if((res = mp_copy(which, c)) != MP_OKAY)
119 return res;
121 for(ix = 0; ix < USED(which); ix++)
122 DIGIT(c, ix) |= DIGIT(other, ix);
124 return MP_OKAY;
126 } /* end mpl_or() */
128 /* }}} */
130 /* {{{ mpl_xor(a, b, c) */
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;
138 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
140 if(USED(a) >= USED(b)) {
141 which = a;
142 other = b;
143 } else {
144 which = b;
145 other = a;
146 }
148 if((res = mp_copy(which, c)) != MP_OKAY)
149 return res;
151 for(ix = 0; ix < USED(which); ix++)
152 DIGIT(c, ix) ^= DIGIT(other, ix);
154 s_mp_clamp(c);
156 return MP_OKAY;
158 } /* end mpl_xor() */
160 /* }}} */
162 /*------------------------------------------------------------------------*/
163 /*
164 mpl_rsh(a, b, d) - b = a >> d
165 mpl_lsh(a, b, d) - b = a << d
166 */
168 /* {{{ mpl_rsh(a, b, d) */
170 mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d)
171 {
172 mp_err res;
174 ARGCHK(a != NULL && b != NULL, MP_BADARG);
176 if((res = mp_copy(a, b)) != MP_OKAY)
177 return res;
179 s_mp_div_2d(b, d);
181 return MP_OKAY;
183 } /* end mpl_rsh() */
185 /* }}} */
187 /* {{{ mpl_lsh(a, b, d) */
189 mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d)
190 {
191 mp_err res;
193 ARGCHK(a != NULL && b != NULL, MP_BADARG);
195 if((res = mp_copy(a, b)) != MP_OKAY)
196 return res;
198 return s_mp_mul_2d(b, d);
200 } /* end mpl_lsh() */
202 /* }}} */
204 /*------------------------------------------------------------------------*/
205 /*
206 mpl_num_set(a, num)
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.
213 mpl_num_clear() does basically the same thing for clear bits.
214 */
216 /* {{{ mpl_num_set(a, num) */
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;
225 ARGCHK(a != NULL, MP_BADARG);
227 for(ix = 0; ix < USED(a); ix++) {
228 cur = DIGIT(a, ix);
230 for(db = 0; db < sizeof(mp_digit); db++) {
231 reg = (unsigned char)(cur >> (CHAR_BIT * db));
233 nset += bitc[reg];
234 }
235 }
237 if(num)
238 *num = nset;
240 return MP_OKAY;
242 } /* end mpl_num_set() */
244 /* }}} */
246 /* {{{ mpl_num_clear(a, num) */
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;
255 ARGCHK(a != NULL, MP_BADARG);
257 for(ix = 0; ix < USED(a); ix++) {
258 cur = DIGIT(a, ix);
260 for(db = 0; db < sizeof(mp_digit); db++) {
261 reg = (unsigned char)(cur >> (CHAR_BIT * db));
263 nset += bitc[UCHAR_MAX - reg];
264 }
265 }
267 if(num)
268 *num = nset;
270 return MP_OKAY;
273 } /* end mpl_num_clear() */
275 /* }}} */
277 /*------------------------------------------------------------------------*/
278 /*
279 mpl_parity(a)
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 */
286 /* {{{ mpl_parity(a) */
288 mp_err mpl_parity(mp_int *a)
289 {
290 unsigned int ix;
291 int par = 0;
292 mp_digit cur;
294 ARGCHK(a != NULL, MP_BADARG);
296 for(ix = 0; ix < USED(a); ix++) {
297 int shft = (sizeof(mp_digit) * CHAR_BIT) / 2;
299 cur = DIGIT(a, ix);
301 /* Compute parity for current digit */
302 while(shft != 0) {
303 cur ^= (cur >> shft);
304 shft >>= 1;
305 }
306 cur &= 1;
308 /* XOR with running parity so far */
309 par ^= cur;
310 }
312 if(par)
313 return MP_ODD;
314 else
315 return MP_EVEN;
317 } /* end mpl_parity() */
319 /* }}} */
321 /*
322 mpl_set_bit
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;
333 ARGCHK(a != NULL, MP_BADARG);
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 }
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 }
352 /*
353 mpl_get_bit
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;
362 ARGCHK(a != NULL, MP_BADARG);
364 ix = bitNum / MP_DIGIT_BIT;
365 ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE);
367 bit = bitNum % MP_DIGIT_BIT;
368 rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1;
369 return rv;
370 }
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);
389 ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG);
390 ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE);
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 }
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;
411 ARGCHK(a != NULL, MP_BADARG);
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 }
431 /*------------------------------------------------------------------------*/
432 /* HERE THERE BE DRAGONS */
