1/*
2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24/* *********************************************************************
25 *
26 * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
27 *
28 * The Initial Developer of the Original Code is
29 * Michael J. Fromberger.
30 * Portions created by the Initial Developer are Copyright (C) 1998
31 * the Initial Developer. All Rights Reserved.
32 *
33 * Contributor(s):
34 *
35 *********************************************************************** */
36
37/* Bitwise logical operations on MPI values */
38
39#include "mpi-priv.h"
40#include "mplogic.h"
41
42/* {{{ Lookup table for population count */
43
44static unsigned char bitc[] = {
45 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
46 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
47 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
48 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
49 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
50 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
51 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
52 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
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 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
58 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
59 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
60 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
61};
62
63/* }}} */
64
65/*
66 mpl_rsh(a, b, d) - b = a >> d
67 mpl_lsh(a, b, d) - b = a << d
68 */
69
70/* {{{ mpl_rsh(a, b, d) */
71
72mp_err mpl_rsh(const mp_int *a, mp_int *b, mp_digit d)
73{
74 mp_err res;
75
76 ARGCHK(a != NULL && b != NULL, MP_BADARG);
77
78 if((res = mp_copy(a, b)) != MP_OKAY)
79 return res;
80
81 s_mp_div_2d(b, d);
82
83 return MP_OKAY;
84
85} /* end mpl_rsh() */
86
87/* }}} */
88
89/* {{{ mpl_lsh(a, b, d) */
90
91mp_err mpl_lsh(const mp_int *a, mp_int *b, mp_digit d)
92{
93 mp_err res;
94
95 ARGCHK(a != NULL && b != NULL, MP_BADARG);
96
97 if((res = mp_copy(a, b)) != MP_OKAY)
98 return res;
99
100 return s_mp_mul_2d(b, d);
101
102} /* end mpl_lsh() */
103
104/* }}} */
105
106/*------------------------------------------------------------------------*/
107/*
108 mpl_set_bit
109
110 Returns MP_OKAY or some error code.
111 Grows a if needed to set a bit to 1.
112 */
113mp_err mpl_set_bit(mp_int *a, mp_size bitNum, mp_size value)
114{
115 mp_size ix;
116 mp_err rv;
117 mp_digit mask;
118
119 ARGCHK(a != NULL, MP_BADARG);
120
121 ix = bitNum / MP_DIGIT_BIT;
122 if (ix + 1 > MP_USED(a)) {
123 rv = s_mp_pad(a, ix + 1);
124 if (rv != MP_OKAY)
125 return rv;
126 }
127
128 bitNum = bitNum % MP_DIGIT_BIT;
129 mask = (mp_digit)1 << bitNum;
130 if (value)
131 MP_DIGIT(a,ix) |= mask;
132 else
133 MP_DIGIT(a,ix) &= ~mask;
134 s_mp_clamp(a);
135 return MP_OKAY;
136}
137
138/*
139 mpl_get_bit
140
141 returns 0 or 1 or some (negative) error code.
142 */
143mp_err mpl_get_bit(const mp_int *a, mp_size bitNum)
144{
145 mp_size bit, ix;
146 mp_err rv;
147
148 ARGCHK(a != NULL, MP_BADARG);
149
150 ix = bitNum / MP_DIGIT_BIT;
151 ARGCHK(ix <= MP_USED(a) - 1, MP_RANGE);
152
153 bit = bitNum % MP_DIGIT_BIT;
154 rv = (mp_err)(MP_DIGIT(a, ix) >> bit) & 1;
155 return rv;
156}
157
158/*
159 mpl_get_bits
160 - Extracts numBits bits from a, where the least significant extracted bit
161 is bit lsbNum. Returns a negative value if error occurs.
162 - Because sign bit is used to indicate error, maximum number of bits to
163 be returned is the lesser of (a) the number of bits in an mp_digit, or
164 (b) one less than the number of bits in an mp_err.
165 - lsbNum + numbits can be greater than the number of significant bits in
166 integer a, as long as bit lsbNum is in the high order digit of a.
167 */
168mp_err mpl_get_bits(const mp_int *a, mp_size lsbNum, mp_size numBits)
169{
170 mp_size rshift = (lsbNum % MP_DIGIT_BIT);
171 mp_size lsWndx = (lsbNum / MP_DIGIT_BIT);
172 mp_digit * digit = MP_DIGITS(a) + lsWndx;
173 mp_digit mask = ((1 << numBits) - 1);
174
175 ARGCHK(numBits < CHAR_BIT * sizeof mask, MP_BADARG);
176 ARGCHK(MP_HOWMANY(lsbNum, MP_DIGIT_BIT) <= MP_USED(a), MP_RANGE);
177
178 if ((numBits + lsbNum % MP_DIGIT_BIT <= MP_DIGIT_BIT) ||
179 (lsWndx + 1 >= MP_USED(a))) {
180 mask &= (digit[0] >> rshift);
181 } else {
182 mask &= ((digit[0] >> rshift) | (digit[1] << (MP_DIGIT_BIT - rshift)));
183 }
184 return (mp_err)mask;
185}
186
187/*
188 mpl_significant_bits
189 returns number of significnant bits in abs(a).
190 returns 1 if value is zero.
191 */
192mp_err mpl_significant_bits(const mp_int *a)
193{
194 mp_err bits = 0;
195 int ix;
196
197 ARGCHK(a != NULL, MP_BADARG);
198
199 ix = MP_USED(a);
200 for (ix = MP_USED(a); ix > 0; ) {
201 mp_digit d;
202 d = MP_DIGIT(a, --ix);
203 if (d) {
204 while (d) {
205 ++bits;
206 d >>= 1;
207 }
208 break;
209 }
210 }
211 bits += ix * MP_DIGIT_BIT;
212 if (!bits)
213 bits = 1;
214 return bits;
215}
216
217/*------------------------------------------------------------------------*/
218/* HERE THERE BE DRAGONS */
219