1 #if !defined HAVE_BITLOW_H__
2 #define HAVE_BITLOW_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2012, 2013, 2014 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8 #include "fxttypes.h"
9 #include "bits/bitsperlong.h"
10 #include "bits/bitasm.h"
11
12
lowest_one_idx(ulong x)13 static inline ulong lowest_one_idx(ulong x)
14 // Return index of lowest bit set.
15 // Bit index ranges from zero to BITS_PER_LONG-1.
16 // Examples:
17 // ***1 --> 0
18 // **10 --> 1
19 // *100 --> 2
20 // Return 0 (also) if no bit is set.
21 {
22 #if defined BITS_USE_ASM
23 return asm_bsf(x);
24 #else // BITS_USE_ASM
25
26 // if ( 1>=x ) return x-1; // 0 if 1, ~0 if 0
27 // if ( 0==x ) return 0;
28
29 ulong r = 0;
30 x &= -x; // isolate lowest bit
31
32 #if 1 // branchless version
33 #if BITS_PER_LONG >= 64
34 r |= ( (x & 0xffffffff00000000UL) != 0 ); r <<= 1;
35 r |= ( (x & 0xffff0000ffff0000UL) != 0 ); r <<= 1;
36 r |= ( (x & 0xff00ff00ff00ff00UL) != 0 ); r <<= 1;
37 r |= ( (x & 0xf0f0f0f0f0f0f0f0UL) != 0 ); r <<= 1;
38 r |= ( (x & 0xccccccccccccccccUL) != 0 ); r <<= 1;
39 r |= ( (x & 0xaaaaaaaaaaaaaaaaUL) != 0 );
40 #else // BITS_PER_LONG >= 64
41 r |= ( (x & 0xffff0000UL) != 0 ); r <<= 1;
42 r |= ( (x & 0xff00ff00UL) != 0 ); r <<= 1;
43 r |= ( (x & 0xf0f0f0f0UL) != 0 ); r <<= 1;
44 r |= ( (x & 0xccccccccUL) != 0 ); r <<= 1;
45 r |= ( (x & 0xaaaaaaaaUL) != 0 );
46 #endif // BITS_PER_LONG >= 64
47
48 #else // version by Nathan Bullock
49
50 #if BITS_PER_LONG >= 64
51 if ( x & 0xffffffff00000000UL ) r += 32;
52 if ( x & 0xffff0000ffff0000UL ) r += 16;
53 if ( x & 0xff00ff00ff00ff00UL ) r += 8;
54 if ( x & 0xf0f0f0f0f0f0f0f0UL ) r += 4;
55 if ( x & 0xccccccccccccccccUL ) r += 2;
56 if ( x & 0xaaaaaaaaaaaaaaaaUL ) r += 1;
57 #else // BITS_PER_LONG >= 64
58 if ( x & 0xffff0000UL ) r += 16;
59 if ( x & 0xff00ff00UL ) r += 8;
60 if ( x & 0xf0f0f0f0UL ) r += 4;
61 if ( x & 0xccccccccUL ) r += 2;
62 if ( x & 0xaaaaaaaaUL ) r += 1;
63 #endif // BITS_PER_LONG >= 64
64 #endif
65
66 return r;
67 #endif // BITS_USE_ASM
68 }
69 // -------------------------
70
71
lowest_one_idx_parity(ulong x)72 static inline ulong lowest_one_idx_parity(ulong x)
73 // Return the parity of the index of the lowest set bit.
74 // Return zero with x=0.
75 // Sequence for x>=0 (OEIS sequence A096268):
76 // 0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,...
77 {
78 x &= -x; // isolate lowest bit
79 #if BITS_PER_LONG == 64
80 return 0 != (x & 0xaaaaaaaaaaaaaaaaUL);
81 #else
82 return 0 != (x & 0xaaaaaaaaUL);
83 #endif
84 }
85 // -------------------------
86
87
lowest_one(ulong x)88 static inline ulong lowest_one(ulong x)
89 // Return word where only the lowest set bit in x is set.
90 // Return 0 if no bit is set.
91 {
92 // if ( 0==x ) return 0;
93 // return ((x^(x-1)) >> 1) + 1;
94
95 // return (x & (x-1)) ^ x;
96
97 return x & -x; // use: -x == ~x + 1
98 }
99 // -------------------------
100
lowest_zero(ulong x)101 static inline ulong lowest_zero(ulong x)
102 // Return word where only the lowest unset bit in x is set.
103 // Return 0 if all bits are set.
104 {
105 // return (x ^ (x+1)) & ~x;
106 // return ((x ^ (x+1)) >> 1 ) + 1;
107 // return (x+1) & ~x;
108
109 x = ~x;
110 return x & -x;
111 }
112 // -------------------------
113
114
lowest_block(ulong x)115 static inline ulong lowest_block(ulong x)
116 // Isolate lowest block of ones.
117 {
118 #if 0 // jj's version, printed in the fxtbook (incorrect for words 1+0*)
119
120 ulong l = x & -x; // lowest bit
121 ulong y = x + l;
122 x ^= y;
123 return x & (x>>1);
124
125 #else // Mike Engber's (correct) versions
126
127 # if 1
128
129 // Example:
130 // x = *****011100
131 // l = 00000000100
132 // y = *****100000
133 // x^y = 00000111100
134 // ret = 00000011100
135
136 ulong l = x & -x; // lowest bit
137 ulong y = x + l;
138 y ^= x;
139 return y & x;
140
141 # else
142
143 ulong l = x & -x; // low bit mask
144 ulong c = (l + x) & x; // low bit run cleared
145 return c ^ x; // low bit run mask
146
147 # endif
148 #endif
149 }
150 // -------------------------
151
clear_lowest_one(ulong x)152 static inline ulong clear_lowest_one(ulong x)
153 // Return word where the lowest bit set in x is cleared.
154 // Return 0 for input == 0.
155 {
156 return x & (x-1);
157 }
158 // -------------------------
159
set_lowest_zero(ulong x)160 static inline ulong set_lowest_zero(ulong x)
161 // Return word where the lowest unset bit in x is set.
162 // Return ~0 for input == ~0.
163 {
164 return x | (x+1);
165 }
166 // -------------------------
167
168
low_ones(ulong x)169 static inline ulong low_ones(ulong x)
170 // Return word where all the (low end) ones are set.
171 // Example: 01011011 --> 00000011
172 // Return 0 if lowest bit is zero:
173 // 10110110 --> 0
174 {
175 x = ~x;
176 x &= -x;
177 --x;
178 return x;
179
180 // if ( ~0UL==x ) return ~0UL;
181 // return (((x+1)^x) >> 1);
182 }
183 // -------------------------
184
low_zeros(ulong x)185 static inline ulong low_zeros(ulong x)
186 // Return word where all the (low end) zeros are set.
187 // Example: 01011000 --> 00000111
188 // Return 0 if all bits are set.
189 {
190 x &= -x;
191 --x;
192 return x;
193
194 // if ( 0==x ) return ~0UL;
195 // return (((x-1)^x) >> 1);
196 }
197 // -------------------------
198
199
low_match(ulong x,ulong y)200 static inline ulong low_match(ulong x, ulong y)
201 // Return word that contains all bits at the low end where x and y match.
202 // If x = *0W and y = *1W, then 00W is returned.
203 {
204 x ^= y; // bit-wise difference
205 x &= -x; // lowest bit that differs in both words
206 x -= 1; // mask that covers equal bits at low end
207 x &= y; // isolate matching bits
208 return x;
209 }
210 // -------------------------
211
212
213 #endif // !defined HAVE_BITLOW_H__
214