Home | History | Annotate | Download | only in mpi
      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 /*
     42  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
     43  * Use is subject to license terms.
     44  *
     45  * Sun elects to use this software under the MPL license.
     46  */
     47 
     48 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     49 
     50 /* $Id: mplogic.c,v 1.15 2004/04/27 23:04:36 gerv%gerv.net Exp $ */
     51 
     52 #include "mpi-priv.h"
     53 #include "mplogic.h"
     54 
     55 /* {{{ Lookup table for population count */
     56 
     57 static unsigned char bitc[] = {
     58    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
     59    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     60    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     61    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     62    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     63    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     64    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     65    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     66    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     67    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     68    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     69    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     70    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     71    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     72    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     73    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
     74 };
     75 
     76 /* }}} */
     77 
     78 /*
     79   mpl_rsh(a, b, d)     - b = a >> d
     80   mpl_lsh(a, b, d)     - b = a << d
     81  */
     82 
     83 /* {{{ mpl_rsh(a, b, d) */
     84 
     85 mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d)
     86 {
     87   mp_err   res;
     88 
     89   ARGCHK(a != NULL && b != NULL, MP_BADARG);
     90 
     91   if((res = mp_copy(a, b)) != MP_OKAY)
     92     return res;
     93 
     94   s_mp_div_2d(b, d);
     95 
     96   return MP_OKAY;
     97 
     98 } /* end mpl_rsh() */
     99 
    100 /* }}} */
    101 
    102 /* {{{ mpl_lsh(a, b, d) */
    103 
    104 mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d)
    105 {
    106   mp_err   res;
    107 
    108   ARGCHK(a != NULL && b != NULL, MP_BADARG);
    109 
    110   if((res = mp_copy(a, b)) != MP_OKAY)
    111     return res;
    112 
    113   return s_mp_mul_2d(b, d);
    114 
    115 } /* end mpl_lsh() */
    116 
    117 /* }}} */
    118 
    119 /*------------------------------------------------------------------------*/
    120 /*
    121   mpl_set_bit
    122 
    123   Returns MP_OKAY or some error code.
    124   Grows a if needed to set a bit to 1.
    125  */
    126 mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value)
    127 {
    128   mp_size      ix;
    129   mp_err       rv;
    130   mp_digit     mask;
    131 
    132   ARGCHK(a != NULL, MP_BADARG);
    133 
    134   ix = bitNum / MP_DIGIT_BIT;
    135   if (ix + 1 > MP_USED(a)) {
    136     rv = s_mp_pad(a, ix + 1);
    137     if (rv != MP_OKAY)
    138       return rv;
    139   }
    140 
    141   bitNum = bitNum % MP_DIGIT_BIT;
    142   mask = (mp_digit)1 << bitNum;
    143   if (value)
    144     MP_DIGIT(a,ix) |= mask;
    145   else
    146     MP_DIGIT(a,ix) &= ~mask;
    147   s_mp_clamp(a);
    148   return MP_OKAY;
    149 }
    150 
    151 /*
    152   mpl_get_bit
    153 
    154   returns 0 or 1 or some (negative) error code.
    155  */
    156 mp_err mpl_get_bit(const mp_int *a, mp_size bitNum)
    157 {
    158   mp_size      bit, ix;
    159   mp_err       rv;
    160 
    161   ARGCHK(a != NULL, MP_BADARG);
    162 
    163   ix = bitNum / MP_DIGIT_BIT;
    164   ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE);
    165 
    166   bit   = bitNum % MP_DIGIT_BIT;
    167   rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1;
    168   return rv;
    169 }
    170 
    171 /*
    172   mpl_get_bits
    173   - Extracts numBits bits from a, where the least significant extracted bit
    174   is bit lsbNum.  Returns a negative value if error occurs.
    175   - Because sign bit is used to indicate error, maximum number of bits to
    176   be returned is the lesser of (a) the number of bits in an mp_digit, or
    177   (b) one less than the number of bits in an mp_err.
    178   - lsbNum + numbits can be greater than the number of significant bits in
    179   integer a, as long as bit lsbNum is in the high order digit of a.
    180  */
    181 mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits)
    182 {
    183   mp_size    rshift = (lsbNum % MP_DIGIT_BIT);
    184   mp_size    lsWndx = (lsbNum / MP_DIGIT_BIT);
    185   mp_digit * digit  = MP_DIGITS(a) + lsWndx;
    186   mp_digit   mask   = ((1 << numBits) - 1);
    187 
    188   ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG);
    189   ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE);
    190 
    191   if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) ||
    192       (lsWndx + 1 >= MP_USED(a))) {
    193     mask &= (digit[0] >> rshift);
    194   } else {
    195     mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift)));
    196   }
    197   return (mp_err)mask;
    198 }
    199 
    200 /*
    201   mpl_significant_bits
    202   returns number of significnant bits in abs(a).
    203   returns 1 if value is zero.
    204  */
    205 mp_err mpl_significant_bits(const mp_int *a)
    206 {
    207   mp_err bits 	= 0;
    208   int    ix;
    209 
    210   ARGCHK(a != NULL, MP_BADARG);
    211 
    212   ix = MP_USED(a);
    213   for (ix = MP_USED(a); ix > 0; ) {
    214     mp_digit d;
    215     d = MP_DIGIT(a, --ix);
    216     if (d) {
    217       while (d) {
    218 	++bits;
    219 	d >>= 1;
    220       }
    221       break;
    222     }
    223   }
    224   bits += ix * MP_DIGIT_BIT;
    225   if (!bits)
    226     bits = 1;
    227   return bits;
    228 }
    229 
    230 /*------------------------------------------------------------------------*/
    231 /* HERE THERE BE DRAGONS                                                  */
    232