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