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