Back to index

lightning-sunbird  0.9+nobinonly
mplogic.c
Go to the documentation of this file.
00001 /*
00002  *  mplogic.c
00003  *
00004  *  Bitwise logical operations on MPI values
00005  *
00006  * ***** BEGIN LICENSE BLOCK *****
00007  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00008  *
00009  * The contents of this file are subject to the Mozilla Public License Version
00010  * 1.1 (the "License"); you may not use this file except in compliance with
00011  * the License. You may obtain a copy of the License at
00012  * http://www.mozilla.org/MPL/
00013  *
00014  * Software distributed under the License is distributed on an "AS IS" basis,
00015  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00016  * for the specific language governing rights and limitations under the
00017  * License.
00018  *
00019  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
00020  *
00021  * The Initial Developer of the Original Code is
00022  * Michael J. Fromberger.
00023  * Portions created by the Initial Developer are Copyright (C) 1998
00024  * the Initial Developer. All Rights Reserved.
00025  *
00026  * Contributor(s):
00027  *
00028  * Alternatively, the contents of this file may be used under the terms of
00029  * either the GNU General Public License Version 2 or later (the "GPL"), or
00030  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00031  * in which case the provisions of the GPL or the LGPL are applicable instead
00032  * of those above. If you wish to allow use of your version of this file only
00033  * under the terms of either the GPL or the LGPL, and not to allow others to
00034  * use your version of this file under the terms of the MPL, indicate your
00035  * decision by deleting the provisions above and replace them with the notice
00036  * and other provisions required by the GPL or the LGPL. If you do not delete
00037  * the provisions above, a recipient may use your version of this file under
00038  * the terms of any one of the MPL, the GPL or the LGPL.
00039  *
00040  * ***** END LICENSE BLOCK ***** */
00041 /* $Id: mplogic.c,v 1.15 2004/04/27 23:04:36 gerv%gerv.net Exp $ */
00042 
00043 #include "mpi-priv.h"
00044 #include "mplogic.h"
00045 
00046 /* {{{ Lookup table for population count */
00047 
00048 static unsigned char bitc[] = {
00049    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
00050    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
00051    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
00052    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00053    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
00054    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00055    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00056    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
00057    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
00058    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00059    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00060    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
00061    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
00062    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
00063    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
00064    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
00065 };
00066 
00067 /* }}} */
00068 
00069 /*------------------------------------------------------------------------*/
00070 /*
00071   mpl_not(a, b)    - compute b = ~a
00072   mpl_and(a, b, c) - compute c = a & b
00073   mpl_or(a, b, c)  - compute c = a | b
00074   mpl_xor(a, b, c) - compute c = a ^ b
00075  */
00076 
00077 /* {{{ mpl_not(a, b) */
00078 
00079 mp_err mpl_not(mp_int *a, mp_int *b)
00080 {
00081   mp_err   res;
00082   unsigned int      ix;
00083 
00084   ARGCHK(a != NULL && b != NULL, MP_BADARG);
00085 
00086   if((res = mp_copy(a, b)) != MP_OKAY)
00087     return res;
00088 
00089   /* This relies on the fact that the digit type is unsigned */
00090   for(ix = 0; ix < USED(b); ix++) 
00091     DIGIT(b, ix) = ~DIGIT(b, ix);
00092 
00093   s_mp_clamp(b);
00094 
00095   return MP_OKAY;
00096 
00097 } /* end mpl_not() */
00098 
00099 /* }}} */
00100 
00101 /* {{{ mpl_and(a, b, c) */
00102 
00103 mp_err mpl_and(mp_int *a, mp_int *b, mp_int *c)
00104 {
00105   mp_int  *which, *other;
00106   mp_err   res;
00107   unsigned int      ix;
00108 
00109   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
00110 
00111   if(USED(a) <= USED(b)) {
00112     which = a;
00113     other = b;
00114   } else {
00115     which = b;
00116     other = a;
00117   }
00118 
00119   if((res = mp_copy(which, c)) != MP_OKAY)
00120     return res;
00121 
00122   for(ix = 0; ix < USED(which); ix++)
00123     DIGIT(c, ix) &= DIGIT(other, ix);
00124 
00125   s_mp_clamp(c);
00126 
00127   return MP_OKAY;
00128 
00129 } /* end mpl_and() */
00130 
00131 /* }}} */
00132 
00133 /* {{{ mpl_or(a, b, c) */
00134 
00135 mp_err mpl_or(mp_int *a, mp_int *b, mp_int *c)
00136 {
00137   mp_int  *which, *other;
00138   mp_err   res;
00139   unsigned int      ix;
00140 
00141   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
00142 
00143   if(USED(a) >= USED(b)) {
00144     which = a;
00145     other = b;
00146   } else {
00147     which = b;
00148     other = a;
00149   }
00150 
00151   if((res = mp_copy(which, c)) != MP_OKAY)
00152     return res;
00153 
00154   for(ix = 0; ix < USED(which); ix++)
00155     DIGIT(c, ix) |= DIGIT(other, ix);
00156 
00157   return MP_OKAY;
00158 
00159 } /* end mpl_or() */
00160 
00161 /* }}} */
00162 
00163 /* {{{ mpl_xor(a, b, c) */
00164 
00165 mp_err mpl_xor(mp_int *a, mp_int *b, mp_int *c)
00166 {
00167   mp_int  *which, *other;
00168   mp_err   res;
00169   unsigned int      ix;
00170 
00171   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
00172 
00173   if(USED(a) >= USED(b)) {
00174     which = a;
00175     other = b;
00176   } else {
00177     which = b;
00178     other = a;
00179   }
00180 
00181   if((res = mp_copy(which, c)) != MP_OKAY)
00182     return res;
00183 
00184   for(ix = 0; ix < USED(which); ix++)
00185     DIGIT(c, ix) ^= DIGIT(other, ix);
00186 
00187   s_mp_clamp(c);
00188 
00189   return MP_OKAY;
00190 
00191 } /* end mpl_xor() */
00192 
00193 /* }}} */
00194 
00195 /*------------------------------------------------------------------------*/
00196 /*
00197   mpl_rsh(a, b, d)     - b = a >> d
00198   mpl_lsh(a, b, d)     - b = a << d
00199  */
00200 
00201 /* {{{ mpl_rsh(a, b, d) */
00202 
00203 mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d)
00204 {
00205   mp_err   res;
00206 
00207   ARGCHK(a != NULL && b != NULL, MP_BADARG);
00208 
00209   if((res = mp_copy(a, b)) != MP_OKAY)
00210     return res;
00211 
00212   s_mp_div_2d(b, d);
00213 
00214   return MP_OKAY;
00215 
00216 } /* end mpl_rsh() */
00217 
00218 /* }}} */
00219 
00220 /* {{{ mpl_lsh(a, b, d) */
00221 
00222 mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d)
00223 {
00224   mp_err   res;
00225 
00226   ARGCHK(a != NULL && b != NULL, MP_BADARG);
00227 
00228   if((res = mp_copy(a, b)) != MP_OKAY)
00229     return res;
00230 
00231   return s_mp_mul_2d(b, d);
00232 
00233 } /* end mpl_lsh() */
00234 
00235 /* }}} */
00236 
00237 /*------------------------------------------------------------------------*/
00238 /*
00239   mpl_num_set(a, num)
00240 
00241   Count the number of set bits in the binary representation of a.
00242   Returns MP_OKAY and sets 'num' to be the number of such bits, if
00243   possible.  If num is NULL, the result is thrown away, but it is
00244   not considered an error.
00245 
00246   mpl_num_clear() does basically the same thing for clear bits.
00247  */
00248 
00249 /* {{{ mpl_num_set(a, num) */
00250 
00251 mp_err mpl_num_set(mp_int *a, int *num)
00252 {
00253   unsigned int   ix;
00254   int            db, nset = 0;
00255   mp_digit       cur;
00256   unsigned char  reg;
00257 
00258   ARGCHK(a != NULL, MP_BADARG);
00259 
00260   for(ix = 0; ix < USED(a); ix++) {
00261     cur = DIGIT(a, ix);
00262     
00263     for(db = 0; db < sizeof(mp_digit); db++) {
00264       reg = (unsigned char)(cur >> (CHAR_BIT * db));
00265 
00266       nset += bitc[reg];
00267     }
00268   }
00269 
00270   if(num)
00271     *num = nset;
00272 
00273   return MP_OKAY;
00274 
00275 } /* end mpl_num_set() */
00276 
00277 /* }}} */
00278 
00279 /* {{{ mpl_num_clear(a, num) */
00280 
00281 mp_err mpl_num_clear(mp_int *a, int *num)
00282 {
00283   unsigned int   ix;
00284   int            db, nset = 0;
00285   mp_digit       cur;
00286   unsigned char  reg;
00287 
00288   ARGCHK(a != NULL, MP_BADARG);
00289 
00290   for(ix = 0; ix < USED(a); ix++) {
00291     cur = DIGIT(a, ix);
00292     
00293     for(db = 0; db < sizeof(mp_digit); db++) {
00294       reg = (unsigned char)(cur >> (CHAR_BIT * db));
00295 
00296       nset += bitc[UCHAR_MAX - reg];
00297     }
00298   }
00299 
00300   if(num)
00301     *num = nset;
00302 
00303   return MP_OKAY;
00304 
00305 
00306 } /* end mpl_num_clear() */
00307 
00308 /* }}} */
00309 
00310 /*------------------------------------------------------------------------*/
00311 /*
00312   mpl_parity(a)
00313 
00314   Determines the bitwise parity of the value given.  Returns MP_EVEN
00315   if an even number of digits are set, MP_ODD if an odd number are
00316   set.
00317  */
00318 
00319 /* {{{ mpl_parity(a) */
00320 
00321 mp_err mpl_parity(mp_int *a)
00322 {
00323   unsigned int ix;
00324   int      par = 0;
00325   mp_digit cur;
00326 
00327   ARGCHK(a != NULL, MP_BADARG);
00328 
00329   for(ix = 0; ix < USED(a); ix++) {
00330     int   shft = (sizeof(mp_digit) * CHAR_BIT) / 2;
00331 
00332     cur = DIGIT(a, ix);
00333 
00334     /* Compute parity for current digit */
00335     while(shft != 0) {
00336       cur ^= (cur >> shft);
00337       shft >>= 1;
00338     }
00339     cur &= 1;
00340 
00341     /* XOR with running parity so far   */
00342     par ^= cur;
00343   }
00344 
00345   if(par)
00346     return MP_ODD;
00347   else
00348     return MP_EVEN;
00349 
00350 } /* end mpl_parity() */
00351 
00352 /* }}} */
00353 
00354 /*
00355   mpl_set_bit
00356 
00357   Returns MP_OKAY or some error code.
00358   Grows a if needed to set a bit to 1.
00359  */
00360 mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value)
00361 {
00362   mp_size      ix;
00363   mp_err       rv;
00364   mp_digit     mask;
00365 
00366   ARGCHK(a != NULL, MP_BADARG);
00367 
00368   ix = bitNum / MP_DIGIT_BIT;
00369   if (ix + 1 > MP_USED(a)) {
00370     rv = s_mp_pad(a, ix + 1);
00371     if (rv != MP_OKAY)
00372       return rv;
00373   }
00374 
00375   bitNum = bitNum % MP_DIGIT_BIT;
00376   mask = (mp_digit)1 << bitNum;
00377   if (value)
00378     MP_DIGIT(a,ix) |= mask;
00379   else
00380     MP_DIGIT(a,ix) &= ~mask;
00381   s_mp_clamp(a);
00382   return MP_OKAY;
00383 }
00384 
00385 /*
00386   mpl_get_bit
00387 
00388   returns 0 or 1 or some (negative) error code.
00389  */
00390 mp_err mpl_get_bit(const mp_int *a, mp_size bitNum)
00391 {
00392   mp_size      bit, ix;
00393   mp_err       rv;
00394 
00395   ARGCHK(a != NULL, MP_BADARG);
00396 
00397   ix = bitNum / MP_DIGIT_BIT;
00398   ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE);
00399 
00400   bit   = bitNum % MP_DIGIT_BIT;
00401   rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1;
00402   return rv;
00403 }
00404 
00405 /*
00406   mpl_get_bits
00407   - Extracts numBits bits from a, where the least significant extracted bit
00408   is bit lsbNum.  Returns a negative value if error occurs.
00409   - Because sign bit is used to indicate error, maximum number of bits to 
00410   be returned is the lesser of (a) the number of bits in an mp_digit, or
00411   (b) one less than the number of bits in an mp_err.
00412   - lsbNum + numbits can be greater than the number of significant bits in
00413   integer a, as long as bit lsbNum is in the high order digit of a.
00414  */
00415 mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits) 
00416 {
00417   mp_size    rshift = (lsbNum % MP_DIGIT_BIT);
00418   mp_size    lsWndx = (lsbNum / MP_DIGIT_BIT);
00419   mp_digit * digit  = MP_DIGITS(a) + lsWndx;
00420   mp_digit   mask   = ((1 << numBits) - 1);
00421 
00422   ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG);
00423   ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE);
00424 
00425   if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) ||
00426       (lsWndx + 1 >= MP_USED(a))) {
00427     mask &= (digit[0] >> rshift);
00428   } else {
00429     mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift)));
00430   }
00431   return (mp_err)mask;
00432 }
00433 
00434 /*
00435   mpl_significant_bits
00436   returns number of significnant bits in abs(a).
00437   returns 1 if value is zero.
00438  */
00439 mp_err mpl_significant_bits(const mp_int *a)
00440 {
00441   mp_err bits        = 0;
00442   int    ix;
00443 
00444   ARGCHK(a != NULL, MP_BADARG);
00445 
00446   ix = MP_USED(a);
00447   for (ix = MP_USED(a); ix > 0; ) {
00448     mp_digit d;
00449     d = MP_DIGIT(a, --ix);
00450     if (d) {
00451       while (d) {
00452        ++bits;
00453        d >>= 1;
00454       }
00455       break;
00456     }
00457   }
00458   bits += ix * MP_DIGIT_BIT;
00459   if (!bits)
00460     bits = 1;
00461   return bits;
00462 }
00463 
00464 /*------------------------------------------------------------------------*/
00465 /* HERE THERE BE DRAGONS                                                  */