Debian Codegraph @

src/bits.c

raw
1 /*
2 * bits.c - Bit manipulation utilities
3 *
4 * Copyright (c) 2007-2024 Shiro Kawai <[email protected]>
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/priv/configP.h"
37 #include "gauche/bits_inline.h"
38
39 /*===================================================================
40 * Construct, copy, fill
41 */
42
43 ScmBits *Scm_MakeBits(int numbits)
44 {
45 size_t nw = SCM_BITS_NUM_WORDS(numbits);
46 ScmBits *bits = SCM_NEW_ATOMIC_ARRAY(ScmBits, nw);
47 memset(bits, 0, nw * SIZEOF_LONG);
48 return bits;
49 }
50
51 void Scm_BitsCopyX(ScmBits *target, int tstart,
52 ScmBits *src, int sstart, int send)
53 {
54 if (tstart%SCM_WORD_BITS == 0
55 && sstart%SCM_WORD_BITS == 0
56 && send%SCM_WORD_BITS == 0) {
57 /* easy path */
58 int tw = tstart/SCM_WORD_BITS;
59 int sw = sstart/SCM_WORD_BITS;
60 int ew = send/SCM_WORD_BITS;
61 while (sw < ew) target[tw++] = src[sw++];
62 } else {
63 /* TODO: make this more efficient. */
64 int t, s;
65 for (t=tstart, s=sstart; s < send; t++, s++) {
66 if (SCM_BITS_TEST(src, s)) SCM_BITS_SET(target, t);
67 else SCM_BITS_RESET(target, t);
68 }
69 }
70 }
71
72 void Scm_BitsFill(ScmBits *bits, int start, int end, int b)
73 {
74 int sw = start / SCM_WORD_BITS;
75 int ew = end / SCM_WORD_BITS;
76 int sb = start % SCM_WORD_BITS;
77 int eb = end % SCM_WORD_BITS;
78
79 if (sw == ew) {
80 u_long mask = ((1UL<<eb) - 1) & ~((1UL<<sb) - 1);
81 if (b) bits[sw] |= mask;
82 else bits[sw] &= ~mask;
83 } else {
84 if (b) bits[sw] |= ~((1UL<<sb)-1);
85 else bits[sw] &= ((1UL<<sb)-1);
86 for (sw++; sw < ew; sw++) {
87 if (b) bits[sw] = ~0UL;
88 else bits[sw] = 0;
89 }
90 if (b) bits[ew] |= ((1UL<<eb)-1);
91 else bits[ew] &= ~((1UL<<eb)-1);
92 }
93 }
94
95 void Scm_BitsOperate(ScmBits *r, ScmBitOp op,
96 const ScmBits *a, const ScmBits *b,
97 int s, int e)
98 {
99 int sw = s/SCM_WORD_BITS;
100 int sb = s%SCM_WORD_BITS;
101 int ew = e/SCM_WORD_BITS;
102 int eb = e%SCM_WORD_BITS;
103
104 /* NB: Not very optimized for speed. Rewrite when we hit a bottleneck. */
105 for (int w = sw; w < ew + (eb?1:0); w++) {
106 u_long z = 0;
107 switch (op) {
108 case SCM_BIT_AND: z = a[w] & b[w]; break;
109 case SCM_BIT_IOR: z = a[w] | b[w]; break;
110 case SCM_BIT_XOR: z = a[w] ^ b[w]; break;
111 case SCM_BIT_NAND: z = ~(a[w] & b[w]); break;
112 case SCM_BIT_NOR: z = ~(a[w] | b[w]); break;
113 case SCM_BIT_EQV: z = ~(a[w] ^ b[w]); break;
114 case SCM_BIT_ANDC1:z = ~a[w] & b[w]; break;
115 case SCM_BIT_ANDC2:z = a[w] & ~b[w]; break;
116 case SCM_BIT_IORC1:z = ~a[w] | b[w]; break;
117 case SCM_BIT_IORC2:z = a[w] | ~b[w]; break;
118 case SCM_BIT_XORC1:z = ~a[w] ^ b[w]; break;
119 case SCM_BIT_XORC2:z = a[w] ^ ~b[w]; break;
120 case SCM_BIT_SRC1: z = a[w]; break;
121 case SCM_BIT_SRC2: z = b[w]; break;
122 case SCM_BIT_NOT1: z = ~a[w]; break;
123 case SCM_BIT_NOT2: z = ~b[w]; break;
124 }
125 if (w == sw && sb != 0) z &= ~((1UL<<sb)-1);
126 else if (w == ew) z &= (1UL<<eb)-1;
127 r[w] = z;
128 }
129 }
130
131 /*===================================================================
132 * Comparison
133 */
134
135 int Scm_BitsEqual(const ScmBits *a, const ScmBits *b, int s, int e)
136 {
137 int sw = s/SCM_WORD_BITS;
138 int sb = s%SCM_WORD_BITS;
139 int ew = e/SCM_WORD_BITS;
140 int eb = e%SCM_WORD_BITS;
141
142 if (sb) {
143 if (((a[sw]^b[sw])&~((1UL<<sb)-1)) != 0) return FALSE;
144 else sw++;
145 }
146 if (eb) {
147 if (((a[ew]^b[ew])& ((1UL<<eb)-1)) != 0) return FALSE;
148 }
149 for (;sw < ew; sw++) {
150 if ((a[sw]^b[sw]) != 0) return FALSE;
151 }
152 return TRUE;
153 }
154
155 /* Returns iff all '1' bits in B is also '1' in A. */
156 int Scm_BitsIncludes(const ScmBits *a, const ScmBits *b, int s, int e)
157 {
158 int sw = s/SCM_WORD_BITS;
159 int sb = s%SCM_WORD_BITS;
160 int ew = e/SCM_WORD_BITS;
161 int eb = e%SCM_WORD_BITS;
162
163 if (sb) {
164 if (((a[sw]^(a[sw]|b[sw]))&~((1UL<<sb)-1)) != 0) return FALSE;
165 else sw++;
166 }
167 if (eb) {
168 if (((a[ew]^(a[ew]|b[ew]))& ((1UL<<eb)-1)) != 0) return FALSE;
169 }
170 for (;sw < ew; sw++) {
171 if ((a[sw]^(a[sw]|b[sw])) != 0) return FALSE;
172 }
173 return TRUE;
174 }
175
176 /*===================================================================
177 * Bit checking
178 */
179
180 int Scm_BitsAny(const ScmBits *bits, int start, int end)
181 {
182 int sw = start / SCM_WORD_BITS;
183 int ew = (end-1)/ SCM_WORD_BITS;
184 int sb = start % SCM_WORD_BITS;
185 int eb = end % SCM_WORD_BITS;
186
187 if (start == end) return FALSE;
188 if (sw == ew) return !!(bits[sw] & SCM_BITS_MASK(sb, eb));
189
190 if (bits[sw] & SCM_BITS_MASK(sb, 0)) return TRUE;
191 for (sw++; sw < ew; sw++) if (bits[sw]) return TRUE;
192 if (bits[ew] & SCM_BITS_MASK(0, eb)) return TRUE;
193 return FALSE;
194 }
195
196 int Scm_BitsEvery(const ScmBits *bits, int start, int end)
197 {
198 int sw = start / SCM_WORD_BITS;
199 int ew = (end-1)/ SCM_WORD_BITS;
200 int sb = start % SCM_WORD_BITS;
201 int eb = end % SCM_WORD_BITS;
202
203 if (start == end) return TRUE;
204 if (sw == ew) return !(~bits[sw] & SCM_BITS_MASK(sb, eb));
205
206 if (~bits[sw] & SCM_BITS_MASK(sb, 0)) return FALSE;
207 for (sw++; sw < ew; sw++) if (~bits[sw]) return FALSE;
208 if (~bits[ew] & SCM_BITS_MASK(0, eb)) return FALSE;
209 return TRUE;
210 }
211
212 /*===================================================================
213 * Bit counting
214 */
215
216 #define count_bits Scm__CountBitsInWord /* defined in bits_inline.h */
217
218 /* count number of '1's from the start-th bit (inclusive) and end-th
219 bit (exclusive) */
220 int Scm_BitsCount1(const ScmBits *bits, int start, int end)
221 {
222 int sw = start / SCM_WORD_BITS;
223 int ew = (end-1)/ SCM_WORD_BITS;
224 int sb = start % SCM_WORD_BITS;
225 int eb = end % SCM_WORD_BITS;
226
227 if (start == end) return 0;
228 if (sw == ew) return count_bits(bits[sw] & SCM_BITS_MASK(sb, eb));
229
230 u_long num = count_bits(bits[sw] & SCM_BITS_MASK(sb, 0));
231 for (sw++; sw < ew; sw++) num += count_bits(bits[sw]);
232 return num + (count_bits((bits[ew]) & SCM_BITS_MASK(0, eb)));
233 }
234
235 int Scm_BitsCount0(const ScmBits *bits, int start, int end)
236 {
237 int sw = start / SCM_WORD_BITS;
238 int ew = (end-1)/ SCM_WORD_BITS;
239 int sb = start % SCM_WORD_BITS;
240 int eb = end % SCM_WORD_BITS;
241
242 if (start == end) return 0;
243 if (sw == ew) return count_bits(~bits[sw] & SCM_BITS_MASK(sb, eb));
244
245 u_long num = count_bits(~bits[sw] & SCM_BITS_MASK(sb, 0));
246 for (sw++; sw < ew; sw++) num += count_bits(~bits[sw]);
247 return num + (count_bits(~bits[ew] & SCM_BITS_MASK(0, eb)));
248 }
249
250 /*===================================================================
251 * Bit finding
252 */
253
254 #define lowest Scm__LowestBitNumber
255 #define highest Scm__HighestBitNumber
256
257 /* Returns the lowest bit number between start (inclusive) and end (exclusive),
258 or -1 if all the bits there is zero. */
259 int Scm_BitsLowest1(const ScmBits *bits, int start, int end)
260 {
261 int sw = start/SCM_WORD_BITS;
262 int sb = start%SCM_WORD_BITS;
263 int ew = (end-1)/SCM_WORD_BITS;
264 int eb = end%SCM_WORD_BITS;
265
266 if (start == end) return -1;
267 if (ew == sw) {
268 u_long w = bits[sw] & SCM_BITS_MASK(sb, eb);
269 if (w) return lowest(w) + sw*SCM_WORD_BITS;
270 else return -1;
271 } else {
272 u_long w = bits[sw] & SCM_BITS_MASK(sb, 0);
273 if (w) return lowest(w) + sw*SCM_WORD_BITS;
274 for (;sw < ew; sw++) {
275 if (bits[sw]) return lowest(bits[sw])+sw*SCM_WORD_BITS;
276 }
277 w = bits[ew] & SCM_BITS_MASK(0, eb);
278 if (w) return lowest(w) + ew*SCM_WORD_BITS;
279 return -1;
280 }
281 }
282
283 int Scm_BitsLowest0(const ScmBits *bits, int start, int end)
284 {
285 int sw = start/SCM_WORD_BITS;
286 int sb = start%SCM_WORD_BITS;
287 int ew = (end-1)/SCM_WORD_BITS;
288 int eb = end%SCM_WORD_BITS;
289
290 if (start == end) return -1;
291 if (ew == sw) {
292 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, eb);
293 if (w) return lowest(w) + sw*SCM_WORD_BITS;
294 else return -1;
295 } else {
296 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, 0);
297 if (w) return lowest(w) + sw*SCM_WORD_BITS;
298 for (;sw < ew; sw++) {
299 if (~bits[sw]) return lowest(~bits[sw])+sw*SCM_WORD_BITS;
300 }
301 w = ~bits[ew] & SCM_BITS_MASK(0, eb);
302 if (w) return lowest(w) + ew*SCM_WORD_BITS;
303 return -1;
304 }
305 }
306
307 /* Returns the highest bit number between start (inclusive) and end (exclusive),
308 or -1 if all the bits there is zero. */
309 int Scm_BitsHighest1(const ScmBits *bits, int start, int end)
310 {
311 int sw = start/SCM_WORD_BITS;
312 int sb = start%SCM_WORD_BITS;
313 int ew = (end-1)/SCM_WORD_BITS;
314 int eb = end%SCM_WORD_BITS;
315
316 if (start == end) return -1;
317 if (ew == sw) {
318 u_long w = bits[sw] & SCM_BITS_MASK(sb, eb);
319 if (w) return highest(w) + sw*SCM_WORD_BITS;
320 else return -1;
321 } else {
322 u_long w = bits[ew] & SCM_BITS_MASK(0, eb);
323 if (w) return highest(w) + ew*SCM_WORD_BITS;
324 for (ew--;sw < ew; ew--) {
325 if (bits[ew]) return highest(bits[ew])+ew*SCM_WORD_BITS;
326 }
327 w = bits[sw] & SCM_BITS_MASK(sb, 0);
328 if (w) return highest(w) + sw*SCM_WORD_BITS;
329 return -1;
330 }
331 }
332
333 int Scm_BitsHighest0(const ScmBits *bits, int start, int end)
334 {
335 int sw = start/SCM_WORD_BITS;
336 int sb = start%SCM_WORD_BITS;
337 int ew = (end-1)/SCM_WORD_BITS;
338 int eb = end%SCM_WORD_BITS;
339
340 if (start == end) return -1;
341 if (ew == sw) {
342 u_long w = ~bits[sw] & SCM_BITS_MASK(sb, eb);
343 if (w) return highest(w) + sw*SCM_WORD_BITS;
344 else return -1;
345 } else {
346 u_long w = ~bits[ew] & SCM_BITS_MASK(0, eb);
347 if (w) return highest(w) + ew*SCM_WORD_BITS;
348 for (ew--;sw < ew; ew--) {
349 if (~bits[ew]) return highest(~bits[ew])+ew*SCM_WORD_BITS;
350 }
351 w = ~bits[sw] & SCM_BITS_MASK(sb, 0);
352 if (w) return highest(w) + sw*SCM_WORD_BITS;
353 return -1;
354 }
355 }