1 /*
2 * gauche/bits_inline.h - Some speed-sensitive bit-manipulation routines
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 #ifndef GAUCHE_BITS_INLINE_H
35 #define GAUCHE_BITS_INLINE_H
36
37 /*
38 * These routines are a part of 'bits' module (src/bits.c), but splitted
39 * here so that other speed-sensitive modules can use them.
40 * THIS IS NOT FOR GENERAL INCLUSION. Only sources that needs these
41 * routines should explicitly #include <gauche/bits_inline.h>.
42 *
43 * Some of these routines can be further optimized for specific
44 * architectures if the CPU has special instructions. If needed,
45 * we'll gradually implement such specialized optimizations.
46 */
47
48 /* Counts '1' bits within a word */
Scm__CountBitsInWord(u_long word)49 static inline u_long Scm__CountBitsInWord(u_long word)
50 {
51 #if SIZEOF_LONG == 4
52 word = (word&0x55555555UL) + ((word>>1)&0x55555555UL);
53 word = (word&0x33333333UL) + ((word>>2)&0x33333333UL);
54 word = (word&0x0f0f0f0fUL) + ((word>>4)&0x0f0f0f0fUL);
55 word *= 0x01010101UL;
56 return word >> 24;
57 #else
58 word = (word&0x5555555555555555UL) + ((word>>1)&0x5555555555555555UL);
59 word = (word&0x3333333333333333UL) + ((word>>2)&0x3333333333333333UL);
60 word = (word&0x0f0f0f0f0f0f0f0fUL) + ((word>>4)&0x0f0f0f0f0f0f0f0fUL);
61 word *= 0x0101010101010101UL;
62 return word >> 56;
63 #endif
64 }
65
66 /* Counts '1' bits within a word, _below_ the n-th bit (exclusive) */
Scm__CountBitsBelow(u_long word,int n)67 static inline u_long Scm__CountBitsBelow(u_long word, int n)
68 {
69 u_long mask = (1UL<<n)-1;
70 return Scm__CountBitsInWord(word&mask);
71 }
72
73 /* Returns the bit number of the lowest '1' bit in the word, assuming
74 there's at least one '1'. */
Scm__LowestBitNumber(u_long word)75 static inline int Scm__LowestBitNumber(u_long word)
76 {
77 int n = 0;
78 word ^= (word&(word-1)); /* leave the rightmost '1' only */
79
80 #if SIZEOF_LONG == 4
81 if (word&0xffff0000) n += 16;
82 if (word&0xff00ff00) n += 8;
83 if (word&0xf0f0f0f0) n += 4;
84 if (word&0xcccccccc) n += 2;
85 if (word&0xaaaaaaaa) n += 1;
86 #else
87 if (word&0xffffffff00000000) n += 32;
88 if (word&0xffff0000ffff0000) n += 16;
89 if (word&0xff00ff00ff00ff00) n += 8;
90 if (word&0xf0f0f0f0f0f0f0f0) n += 4;
91 if (word&0xcccccccccccccccc) n += 2;
92 if (word&0xaaaaaaaaaaaaaaaa) n += 1;
93 #endif
94 return n;
95 }
96
97 /* Returns the bit number of the highest '1' bit in the word, assuming
98 there's at least one '1'. */
Scm__HighestBitNumber(u_long word)99 static inline int Scm__HighestBitNumber(u_long word)
100 {
101 int n = 0;
102 u_long z;
103
104 #if SIZEOF_LONG == 4
105 if ((z = word&0xffff0000) != 0) { n += 16; word = z; }
106 if ((z = word&0xff00ff00) != 0) { n += 8; word = z; }
107 if ((z = word&0xf0f0f0f0) != 0) { n += 4; word = z; }
108 if ((z = word&0xcccccccc) != 0) { n += 2; word = z; }
109 return (word&0xaaaaaaaa)? n+1 : n;
110 #else
111 if ((z = word&0xffffffff00000000) != 0) { n += 32; word = z; }
112 if ((z = word&0xffff0000ffff0000) != 0) { n += 16; word = z; }
113 if ((z = word&0xff00ff00ff00ff00) != 0) { n += 8; word = z; }
114 if ((z = word&0xf0f0f0f0f0f0f0f0) != 0) { n += 4; word = z; }
115 if ((z = word&0xcccccccccccccccc) != 0) { n += 2; word = z; }
116 return (word&0xaaaaaaaaaaaaaaaa)? n+1 : n;
117 #endif
118 }
119
120
121
122 #endif /*GAUCHE_BITS_INLINE_H*/
123