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

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