1 /*
2 * bits.c - Bit manipulation utilities
3 *
4 * Copyright (c) 2007-2020 Shiro Kawai <shiro@acm.org>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/bits_inline.h"
37
38 /*===================================================================
39 * Construct, copy, fill
40 */
41
Scm_MakeBits(int numbits)42 ScmBits *Scm_MakeBits(int numbits)
43 {
44 size_t nw = SCM_BITS_NUM_WORDS(numbits);
45 ScmBits *bits = SCM_NEW_ATOMIC_ARRAY(ScmBits, nw);
46 memset(bits, 0, nw * SIZEOF_LONG);
47 return bits;
48 }
49
Scm_BitsCopyX(ScmBits * target,int tstart,ScmBits * src,int sstart,int send)50 void Scm_BitsCopyX(ScmBits *target, int tstart,
51 ScmBits *src, int sstart, int send)
52 {
53 if (tstart%SCM_WORD_BITS == 0
54 && sstart%SCM_WORD_BITS == 0
55 && send%SCM_WORD_BITS == 0) {
56 /* easy path */
57 int tw = tstart/SCM_WORD_BITS;
58 int sw = sstart/SCM_WORD_BITS;
59 int ew = send/SCM_WORD_BITS;
60 while (sw < ew) target[tw++] = src[sw++];
61 } else {
62 /* TODO: make this more efficient. */
63 int t, s;
64 for (t=tstart, s=sstart; s < send; t++, s++) {
65 if (SCM_BITS_TEST(src, s)) SCM_BITS_SET(target, t);
66 else SCM_BITS_RESET(target, t);
67 }
68 }
69 }
70
Scm_BitsFill(ScmBits * bits,int start,int end,int b)71 void Scm_BitsFill(ScmBits *bits, int start, int end, int b)
72 {
73 int sw = start / SCM_WORD_BITS;
74 int ew = end / SCM_WORD_BITS;
75 int sb = start % SCM_WORD_BITS;
76 int eb = end % SCM_WORD_BITS;
77
78 if (sw == ew) {
79 u_long mask = ((1UL<<eb) - 1) & ~((1UL<<sb) - 1);
80 if (b) bits[sw] |= mask;
81 else bits[sw] &= ~mask;
82 } else {
83 if (b) bits[sw] |= ~((1UL<<sb)-1);
84 else bits[sw] &= ((1UL<<sb)-1);
85 for (sw++; sw < ew; sw++) {
86 if (b) bits[sw] = ~0UL;
87 else bits[sw] = 0;
88 }
89 if (b) bits[ew] |= ((1UL<<eb)-1);
90 else bits[ew] &= ~((1UL<<eb)-1);
91 }
92 }
93
Scm_BitsOperate(ScmBits * r,ScmBitOp op,const ScmBits * a,const ScmBits * b,int s,int e)94 void Scm_BitsOperate(ScmBits *r, ScmBitOp op,
95 const ScmBits *a, const ScmBits *b,
96 int s, int e)
97 {
98 int sw = s/SCM_WORD_BITS;
99 int sb = s%SCM_WORD_BITS;
100 int ew = e/SCM_WORD_BITS;
101 int eb = e%SCM_WORD_BITS;
102
103 /* NB: Not very optimized for speed. Rewrite when we hit a bottleneck. */
104 for (int w = sw; w < ew + (eb?1:0); w++) {
105 u_long z = 0;
106 switch (op) {
107 case SCM_BIT_AND: z = a[w] & b[w]; break;
108 case SCM_BIT_IOR: z = a[w] | b[w]; break;
109 case SCM_BIT_XOR: z = a[w] ^ b[w]; break;
110 case SCM_BIT_NAND: z = ~(a[w] & b[w]); break;
111 case SCM_BIT_NOR: z = ~(a[w] | b[w]); break;
112 case SCM_BIT_EQV: z = ~(a[w] ^ b[w]); break;
113 case SCM_BIT_ANDC1:z = ~a[w] & b[w]; break;
114 case SCM_BIT_ANDC2:z = a[w] & ~b[w]; break;
115 case SCM_BIT_IORC1:z = ~a[w] | b[w]; break;
116 case SCM_BIT_IORC2:z = a[w] | ~b[w]; break;
117 case SCM_BIT_XORC1:z = ~a[w] ^ b[w]; break;
118 case SCM_BIT_XORC2:z = a[w] ^ ~b[w]; break;
119 case SCM_BIT_SRC1: z = a[w]; break;
120 case SCM_BIT_SRC2: z = b[w]; break;
121 case SCM_BIT_NOT1: z = ~a[w]; break;
122 case SCM_BIT_NOT2: z = ~b[w]; break;
123 }
124 if (w == sw && sb != 0) z &= ~((1UL<<sb)-1);
125 else if (w == ew) z &= (1UL<<eb)-1;
126 r[w] = z;
127 }
128 }
129
130 /*===================================================================
131 * Comparison
132 */
133
Scm_BitsEqual(const ScmBits * a,const ScmBits * b,int s,int e)134 int Scm_BitsEqual(const ScmBits *a, const ScmBits *b, int s, int e)
135 {
136 int sw = s/SCM_WORD_BITS;
137 int sb = s%SCM_WORD_BITS;
138 int ew = e/SCM_WORD_BITS;
139 int eb = e%SCM_WORD_BITS;
140
141 if (sb) {
142 if (((a[sw]^b[sw])&~((1UL<<sb)-1)) != 0) return FALSE;
143 else sw++;
144 }
145 if (eb) {
146 if (((a[ew]^b[ew])& ((1UL<<eb)-1)) != 0) return FALSE;
147 }
148 for (;sw < ew; sw++) {
149 if ((a[sw]^b[sw]) != 0) return FALSE;
150 }
151 return TRUE;
152 }
153
154 /* Returns iff all '1' bits in B is also '1' in A. */
Scm_BitsIncludes(const ScmBits * a,const ScmBits * b,int s,int e)155 int Scm_BitsIncludes(const ScmBits *a, const ScmBits *b, int s, int e)
156 {
157 int sw = s/SCM_WORD_BITS;
158 int sb = s%SCM_WORD_BITS;
159 int ew = e/SCM_WORD_BITS;
160 int eb = e%SCM_WORD_BITS;
161
162 if (sb) {
163 if (((a[sw]^(a[sw]|b[sw]))&~((1UL<<sb)-1)) != 0) return FALSE;
164 else sw++;
165 }
166 if (eb) {
167 if (((a[ew]^(a[ew]|b[ew]))& ((1UL<<eb)-1)) != 0) return FALSE;
168 }
169 for (;sw < ew; sw++) {
170 if ((a[sw]^(a[sw]|b[sw])) != 0) return FALSE;
171 }
172 return TRUE;
173 }
174
175 /*===================================================================
176 * Bit counting
177 */
178
179 #define count_bits Scm__CountBitsInWord /* defined in bits_inline.h */
180
181 /* count number of '1's from the start-th bit (inclusive) and end-th
182 bit (exclusiv) */
Scm_BitsCount1(const ScmBits * bits,int start,int end)183 int Scm_BitsCount1(const ScmBits *bits, int start, int end)
184 {
185 int sw = start / SCM_WORD_BITS;
186 int ew = (end-1)/ SCM_WORD_BITS;
187 int sb = start % SCM_WORD_BITS;
188 int eb = end % SCM_WORD_BITS;
189
190 if (start == end) return 0;
191 if (sw == ew) return count_bits(bits[sw] & SCM_BITS_MASK(sb, eb));
192
193 u_long num = count_bits(bits[sw] & SCM_BITS_MASK(sb, 0));
194 for (sw++; sw < ew; sw++) num += count_bits(bits[sw]);
195 return num + (count_bits((bits[ew]) & SCM_BITS_MASK(0, eb)));
196 }
197
Scm_BitsCount0(const ScmBits * bits,int start,int end)198 int Scm_BitsCount0(const ScmBits *bits, int start, int end)
199 {
200 int sw = start / SCM_WORD_BITS;
201 int ew = (end-1)/ SCM_WORD_BITS;
202 int sb = start % SCM_WORD_BITS;
203 int eb = end % SCM_WORD_BITS;
204
205 if (start == end) return 0;
206 if (sw == ew) return count_bits(~bits[sw] & SCM_BITS_MASK(sb, eb));
207
208 u_long num = count_bits(~bits[sw] & SCM_BITS_MASK(sb, 0));
209 for (sw++; sw < ew; sw++) num += count_bits(~bits[sw]);
210 return num + (count_bits(~bits[ew] & SCM_BITS_MASK(0, eb)));
211 }
212
213 /*===================================================================
214 * Bit finding
215 */
216
217 #define lowest Scm__LowestBitNumber
218 #define highest Scm__HighestBitNumber
219
220 /* Returns the lowest bit number between start and end, or -1 if all
221 the bits there is zero. */
Scm_BitsLowest1(const ScmBits * bits,int start,int end)222 int Scm_BitsLowest1(const ScmBits *bits, int start, int end)
223 {
224 int sw = start/SCM_WORD_BITS;
225 int sb = start%SCM_WORD_BITS;
226 int ew = (end-1)/SCM_WORD_BITS;
227 int eb = end%SCM_WORD_BITS;
228
229 if (start == end) return -1;
230 if (ew == sw) {
231 u_long w = bits[sw] & SCM_BITS_MASK(sb, eb);
232 if (w) return lowest(w) + sw*SCM_WORD_BITS;
233 else return -1;
234 } else {
235 u_long w = bits[sw] & SCM_BITS_MASK(sb, 0);
236 if (w) return lowest(w) + sw*SCM_WORD_BITS;
237 for (;sw < ew; sw++) {
238 if (bits[sw]) return lowest(bits[sw])+sw*SCM_WORD_BITS;
239 }
240 w = bits[ew] & SCM_BITS_MASK(0, eb);
241 if (w) return lowest(w) + ew*SCM_WORD_BITS;
242 return -1;
243 }
244 }
245
Scm_BitsLowest0(const ScmBits * bits,int start,int end)246 int Scm_BitsLowest0(const ScmBits *bits, int start, int end)
247 {
248 int sw = start/SCM_WORD_BITS;
249 int sb = start%SCM_WORD_BITS;
250 int ew = (end-1)/SCM_WORD_BITS;
251 int eb = end%SCM_WORD_BITS;
252
253 if (start == end) return -1;
254 if (ew == sw) {
255 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, eb);
256 if (w) return lowest(w) + sw*SCM_WORD_BITS;
257 else return -1;
258 } else {
259 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, 0);
260 if (w) return lowest(w) + sw*SCM_WORD_BITS;
261 for (;sw < ew; sw++) {
262 if (~bits[sw]) return lowest(~bits[sw])+sw*SCM_WORD_BITS;
263 }
264 w = ~bits[ew] & SCM_BITS_MASK(0, eb);
265 if (w) return lowest(w) + ew*SCM_WORD_BITS;
266 return -1;
267 }
268 }
269
270 /* Returns the highest bit number between start and end, or -1 if all
271 the bits there is zero. */
Scm_BitsHighest1(const ScmBits * bits,int start,int end)272 int Scm_BitsHighest1(const ScmBits *bits, int start, int end)
273 {
274 int sw = start/SCM_WORD_BITS;
275 int sb = start%SCM_WORD_BITS;
276 int ew = (end-1)/SCM_WORD_BITS;
277 int eb = end%SCM_WORD_BITS;
278
279 if (start == end) return -1;
280 if (ew == sw) {
281 u_long w = bits[sw] & SCM_BITS_MASK(sb, eb);
282 if (w) return highest(w) + sw*SCM_WORD_BITS;
283 else return -1;
284 } else {
285 u_long w = bits[ew] & SCM_BITS_MASK(0, eb);
286 if (w) return highest(w) + ew*SCM_WORD_BITS;
287 for (ew--;sw < ew; ew--) {
288 if (bits[ew]) return highest(bits[ew])+ew*SCM_WORD_BITS;
289 }
290 w = bits[sw] & SCM_BITS_MASK(sb, 0);
291 if (w) return highest(w) + sw*SCM_WORD_BITS;
292 return -1;
293 }
294 }
295
Scm_BitsHighest0(const ScmBits * bits,int start,int end)296 int Scm_BitsHighest0(const ScmBits *bits, int start, int end)
297 {
298 int sw = start/SCM_WORD_BITS;
299 int sb = start%SCM_WORD_BITS;
300 int ew = (end-1)/SCM_WORD_BITS;
301 int eb = end%SCM_WORD_BITS;
302
303 if (start == end) return -1;
304 if (ew == sw) {
305 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, eb);
306 if (w) return highest(w) + sw*SCM_WORD_BITS;
307 else return -1;
308 } else {
309 u_long w = ~bits[ew] & SCM_BITS_MASK(0, eb);
310 if (w) return highest(w) + ew*SCM_WORD_BITS;
311 for (ew--;sw < ew; ew--) {
312 if (~bits[ew]) return highest(~bits[ew])+ew*SCM_WORD_BITS;
313 }
314 w = ~bits[sw] & SCM_BITS_MASK(sb, 0);
315 if (w) return highest(w) + sw*SCM_WORD_BITS;
316 return -1;
317 }
318 }
319