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