1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/mplogic.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,432 @@
1.4 +/*
1.5 + * mplogic.c
1.6 + *
1.7 + * Bitwise logical operations on MPI values
1.8 + *
1.9 + * This Source Code Form is subject to the terms of the Mozilla Public
1.10 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.11 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.12 +
1.13 +#include "mpi-priv.h"
1.14 +#include "mplogic.h"
1.15 +
1.16 +/* {{{ Lookup table for population count */
1.17 +
1.18 +static unsigned char bitc[] = {
1.19 + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1.20 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.21 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.22 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.23 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.24 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.25 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.26 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.27 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.28 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.29 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.30 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.31 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.32 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.33 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.34 + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
1.35 +};
1.36 +
1.37 +/* }}} */
1.38 +
1.39 +/*------------------------------------------------------------------------*/
1.40 +/*
1.41 + mpl_not(a, b) - compute b = ~a
1.42 + mpl_and(a, b, c) - compute c = a & b
1.43 + mpl_or(a, b, c) - compute c = a | b
1.44 + mpl_xor(a, b, c) - compute c = a ^ b
1.45 + */
1.46 +
1.47 +/* {{{ mpl_not(a, b) */
1.48 +
1.49 +mp_err mpl_not(mp_int *a, mp_int *b)
1.50 +{
1.51 + mp_err res;
1.52 + unsigned int ix;
1.53 +
1.54 + ARGCHK(a != NULL && b != NULL, MP_BADARG);
1.55 +
1.56 + if((res = mp_copy(a, b)) != MP_OKAY)
1.57 + return res;
1.58 +
1.59 + /* This relies on the fact that the digit type is unsigned */
1.60 + for(ix = 0; ix < USED(b); ix++)
1.61 + DIGIT(b, ix) = ~DIGIT(b, ix);
1.62 +
1.63 + s_mp_clamp(b);
1.64 +
1.65 + return MP_OKAY;
1.66 +
1.67 +} /* end mpl_not() */
1.68 +
1.69 +/* }}} */
1.70 +
1.71 +/* {{{ mpl_and(a, b, c) */
1.72 +
1.73 +mp_err mpl_and(mp_int *a, mp_int *b, mp_int *c)
1.74 +{
1.75 + mp_int *which, *other;
1.76 + mp_err res;
1.77 + unsigned int ix;
1.78 +
1.79 + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
1.80 +
1.81 + if(USED(a) <= USED(b)) {
1.82 + which = a;
1.83 + other = b;
1.84 + } else {
1.85 + which = b;
1.86 + other = a;
1.87 + }
1.88 +
1.89 + if((res = mp_copy(which, c)) != MP_OKAY)
1.90 + return res;
1.91 +
1.92 + for(ix = 0; ix < USED(which); ix++)
1.93 + DIGIT(c, ix) &= DIGIT(other, ix);
1.94 +
1.95 + s_mp_clamp(c);
1.96 +
1.97 + return MP_OKAY;
1.98 +
1.99 +} /* end mpl_and() */
1.100 +
1.101 +/* }}} */
1.102 +
1.103 +/* {{{ mpl_or(a, b, c) */
1.104 +
1.105 +mp_err mpl_or(mp_int *a, mp_int *b, mp_int *c)
1.106 +{
1.107 + mp_int *which, *other;
1.108 + mp_err res;
1.109 + unsigned int ix;
1.110 +
1.111 + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
1.112 +
1.113 + if(USED(a) >= USED(b)) {
1.114 + which = a;
1.115 + other = b;
1.116 + } else {
1.117 + which = b;
1.118 + other = a;
1.119 + }
1.120 +
1.121 + if((res = mp_copy(which, c)) != MP_OKAY)
1.122 + return res;
1.123 +
1.124 + for(ix = 0; ix < USED(which); ix++)
1.125 + DIGIT(c, ix) |= DIGIT(other, ix);
1.126 +
1.127 + return MP_OKAY;
1.128 +
1.129 +} /* end mpl_or() */
1.130 +
1.131 +/* }}} */
1.132 +
1.133 +/* {{{ mpl_xor(a, b, c) */
1.134 +
1.135 +mp_err mpl_xor(mp_int *a, mp_int *b, mp_int *c)
1.136 +{
1.137 + mp_int *which, *other;
1.138 + mp_err res;
1.139 + unsigned int ix;
1.140 +
1.141 + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
1.142 +
1.143 + if(USED(a) >= USED(b)) {
1.144 + which = a;
1.145 + other = b;
1.146 + } else {
1.147 + which = b;
1.148 + other = a;
1.149 + }
1.150 +
1.151 + if((res = mp_copy(which, c)) != MP_OKAY)
1.152 + return res;
1.153 +
1.154 + for(ix = 0; ix < USED(which); ix++)
1.155 + DIGIT(c, ix) ^= DIGIT(other, ix);
1.156 +
1.157 + s_mp_clamp(c);
1.158 +
1.159 + return MP_OKAY;
1.160 +
1.161 +} /* end mpl_xor() */
1.162 +
1.163 +/* }}} */
1.164 +
1.165 +/*------------------------------------------------------------------------*/
1.166 +/*
1.167 + mpl_rsh(a, b, d) - b = a >> d
1.168 + mpl_lsh(a, b, d) - b = a << d
1.169 + */
1.170 +
1.171 +/* {{{ mpl_rsh(a, b, d) */
1.172 +
1.173 +mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d)
1.174 +{
1.175 + mp_err res;
1.176 +
1.177 + ARGCHK(a != NULL && b != NULL, MP_BADARG);
1.178 +
1.179 + if((res = mp_copy(a, b)) != MP_OKAY)
1.180 + return res;
1.181 +
1.182 + s_mp_div_2d(b, d);
1.183 +
1.184 + return MP_OKAY;
1.185 +
1.186 +} /* end mpl_rsh() */
1.187 +
1.188 +/* }}} */
1.189 +
1.190 +/* {{{ mpl_lsh(a, b, d) */
1.191 +
1.192 +mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d)
1.193 +{
1.194 + mp_err res;
1.195 +
1.196 + ARGCHK(a != NULL && b != NULL, MP_BADARG);
1.197 +
1.198 + if((res = mp_copy(a, b)) != MP_OKAY)
1.199 + return res;
1.200 +
1.201 + return s_mp_mul_2d(b, d);
1.202 +
1.203 +} /* end mpl_lsh() */
1.204 +
1.205 +/* }}} */
1.206 +
1.207 +/*------------------------------------------------------------------------*/
1.208 +/*
1.209 + mpl_num_set(a, num)
1.210 +
1.211 + Count the number of set bits in the binary representation of a.
1.212 + Returns MP_OKAY and sets 'num' to be the number of such bits, if
1.213 + possible. If num is NULL, the result is thrown away, but it is
1.214 + not considered an error.
1.215 +
1.216 + mpl_num_clear() does basically the same thing for clear bits.
1.217 + */
1.218 +
1.219 +/* {{{ mpl_num_set(a, num) */
1.220 +
1.221 +mp_err mpl_num_set(mp_int *a, int *num)
1.222 +{
1.223 + unsigned int ix;
1.224 + int db, nset = 0;
1.225 + mp_digit cur;
1.226 + unsigned char reg;
1.227 +
1.228 + ARGCHK(a != NULL, MP_BADARG);
1.229 +
1.230 + for(ix = 0; ix < USED(a); ix++) {
1.231 + cur = DIGIT(a, ix);
1.232 +
1.233 + for(db = 0; db < sizeof(mp_digit); db++) {
1.234 + reg = (unsigned char)(cur >> (CHAR_BIT * db));
1.235 +
1.236 + nset += bitc[reg];
1.237 + }
1.238 + }
1.239 +
1.240 + if(num)
1.241 + *num = nset;
1.242 +
1.243 + return MP_OKAY;
1.244 +
1.245 +} /* end mpl_num_set() */
1.246 +
1.247 +/* }}} */
1.248 +
1.249 +/* {{{ mpl_num_clear(a, num) */
1.250 +
1.251 +mp_err mpl_num_clear(mp_int *a, int *num)
1.252 +{
1.253 + unsigned int ix;
1.254 + int db, nset = 0;
1.255 + mp_digit cur;
1.256 + unsigned char reg;
1.257 +
1.258 + ARGCHK(a != NULL, MP_BADARG);
1.259 +
1.260 + for(ix = 0; ix < USED(a); ix++) {
1.261 + cur = DIGIT(a, ix);
1.262 +
1.263 + for(db = 0; db < sizeof(mp_digit); db++) {
1.264 + reg = (unsigned char)(cur >> (CHAR_BIT * db));
1.265 +
1.266 + nset += bitc[UCHAR_MAX - reg];
1.267 + }
1.268 + }
1.269 +
1.270 + if(num)
1.271 + *num = nset;
1.272 +
1.273 + return MP_OKAY;
1.274 +
1.275 +
1.276 +} /* end mpl_num_clear() */
1.277 +
1.278 +/* }}} */
1.279 +
1.280 +/*------------------------------------------------------------------------*/
1.281 +/*
1.282 + mpl_parity(a)
1.283 +
1.284 + Determines the bitwise parity of the value given. Returns MP_EVEN
1.285 + if an even number of digits are set, MP_ODD if an odd number are
1.286 + set.
1.287 + */
1.288 +
1.289 +/* {{{ mpl_parity(a) */
1.290 +
1.291 +mp_err mpl_parity(mp_int *a)
1.292 +{
1.293 + unsigned int ix;
1.294 + int par = 0;
1.295 + mp_digit cur;
1.296 +
1.297 + ARGCHK(a != NULL, MP_BADARG);
1.298 +
1.299 + for(ix = 0; ix < USED(a); ix++) {
1.300 + int shft = (sizeof(mp_digit) * CHAR_BIT) / 2;
1.301 +
1.302 + cur = DIGIT(a, ix);
1.303 +
1.304 + /* Compute parity for current digit */
1.305 + while(shft != 0) {
1.306 + cur ^= (cur >> shft);
1.307 + shft >>= 1;
1.308 + }
1.309 + cur &= 1;
1.310 +
1.311 + /* XOR with running parity so far */
1.312 + par ^= cur;
1.313 + }
1.314 +
1.315 + if(par)
1.316 + return MP_ODD;
1.317 + else
1.318 + return MP_EVEN;
1.319 +
1.320 +} /* end mpl_parity() */
1.321 +
1.322 +/* }}} */
1.323 +
1.324 +/*
1.325 + mpl_set_bit
1.326 +
1.327 + Returns MP_OKAY or some error code.
1.328 + Grows a if needed to set a bit to 1.
1.329 + */
1.330 +mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value)
1.331 +{
1.332 + mp_size ix;
1.333 + mp_err rv;
1.334 + mp_digit mask;
1.335 +
1.336 + ARGCHK(a != NULL, MP_BADARG);
1.337 +
1.338 + ix = bitNum / MP_DIGIT_BIT;
1.339 + if (ix + 1 > MP_USED(a)) {
1.340 + rv = s_mp_pad(a, ix + 1);
1.341 + if (rv != MP_OKAY)
1.342 + return rv;
1.343 + }
1.344 +
1.345 + bitNum = bitNum % MP_DIGIT_BIT;
1.346 + mask = (mp_digit)1 << bitNum;
1.347 + if (value)
1.348 + MP_DIGIT(a,ix) |= mask;
1.349 + else
1.350 + MP_DIGIT(a,ix) &= ~mask;
1.351 + s_mp_clamp(a);
1.352 + return MP_OKAY;
1.353 +}
1.354 +
1.355 +/*
1.356 + mpl_get_bit
1.357 +
1.358 + returns 0 or 1 or some (negative) error code.
1.359 + */
1.360 +mp_err mpl_get_bit(const mp_int *a, mp_size bitNum)
1.361 +{
1.362 + mp_size bit, ix;
1.363 + mp_err rv;
1.364 +
1.365 + ARGCHK(a != NULL, MP_BADARG);
1.366 +
1.367 + ix = bitNum / MP_DIGIT_BIT;
1.368 + ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE);
1.369 +
1.370 + bit = bitNum % MP_DIGIT_BIT;
1.371 + rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1;
1.372 + return rv;
1.373 +}
1.374 +
1.375 +/*
1.376 + mpl_get_bits
1.377 + - Extracts numBits bits from a, where the least significant extracted bit
1.378 + is bit lsbNum. Returns a negative value if error occurs.
1.379 + - Because sign bit is used to indicate error, maximum number of bits to
1.380 + be returned is the lesser of (a) the number of bits in an mp_digit, or
1.381 + (b) one less than the number of bits in an mp_err.
1.382 + - lsbNum + numbits can be greater than the number of significant bits in
1.383 + integer a, as long as bit lsbNum is in the high order digit of a.
1.384 + */
1.385 +mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits)
1.386 +{
1.387 + mp_size rshift = (lsbNum % MP_DIGIT_BIT);
1.388 + mp_size lsWndx = (lsbNum / MP_DIGIT_BIT);
1.389 + mp_digit * digit = MP_DIGITS(a) + lsWndx;
1.390 + mp_digit mask = ((1 << numBits) - 1);
1.391 +
1.392 + ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG);
1.393 + ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE);
1.394 +
1.395 + if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) ||
1.396 + (lsWndx + 1 >= MP_USED(a))) {
1.397 + mask &= (digit[0] >> rshift);
1.398 + } else {
1.399 + mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift)));
1.400 + }
1.401 + return (mp_err)mask;
1.402 +}
1.403 +
1.404 +/*
1.405 + mpl_significant_bits
1.406 + returns number of significnant bits in abs(a).
1.407 + returns 1 if value is zero.
1.408 + */
1.409 +mp_err mpl_significant_bits(const mp_int *a)
1.410 +{
1.411 + mp_err bits = 0;
1.412 + int ix;
1.413 +
1.414 + ARGCHK(a != NULL, MP_BADARG);
1.415 +
1.416 + ix = MP_USED(a);
1.417 + for (ix = MP_USED(a); ix > 0; ) {
1.418 + mp_digit d;
1.419 + d = MP_DIGIT(a, --ix);
1.420 + if (d) {
1.421 + while (d) {
1.422 + ++bits;
1.423 + d >>= 1;
1.424 + }
1.425 + break;
1.426 + }
1.427 + }
1.428 + bits += ix * MP_DIGIT_BIT;
1.429 + if (!bits)
1.430 + bits = 1;
1.431 + return bits;
1.432 +}
1.433 +
1.434 +/*------------------------------------------------------------------------*/
1.435 +/* HERE THERE BE DRAGONS */
