Line data Source code
1 : /*
2 : * Copyright (c) 2015 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 : /*
16 : Copyright (c) 2005 Eliot Dresselhaus
17 :
18 : Permission is hereby granted, free of charge, to any person obtaining
19 : a copy of this software and associated documentation files (the
20 : "Software"), to deal in the Software without restriction, including
21 : without limitation the rights to use, copy, modify, merge, publish,
22 : distribute, sublicense, and/or sell copies of the Software, and to
23 : permit persons to whom the Software is furnished to do so, subject to
24 : the following conditions:
25 :
26 : The above copyright notice and this permission notice shall be
27 : included in all copies or substantial portions of the Software.
28 :
29 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 : */
37 :
38 : #ifndef included_clib_bitops_h
39 : #define included_clib_bitops_h
40 :
41 : #define SET_BIT(i) (1 << i)
42 : #define GET_BIT(n, i) (n >> i) & 1U
43 :
44 : static_always_inline uword
45 0 : clear_lowest_set_bit (uword x)
46 : {
47 : #ifdef __BMI__
48 0 : return uword_bits > 32 ? _blsr_u64 (x) : _blsr_u32 (x);
49 : #else
50 0 : return x & (x - 1);
51 : #endif
52 : }
53 :
54 : static_always_inline uword
55 : get_lowest_set_bit (uword x)
56 : {
57 : #ifdef __BMI__
58 : return uword_bits > 32 ? _blsi_u64 (x) : _blsi_u32 (x);
59 : #else
60 : return x & -x;
61 : #endif
62 : }
63 :
64 : static_always_inline u8
65 563011400 : get_lowest_set_bit_index (uword x)
66 : {
67 563011400 : return uword_bits > 32 ? __builtin_ctzll (x) : __builtin_ctz (x);
68 : }
69 :
70 : /* Population count from Hacker's Delight. */
71 : always_inline uword
72 912343893 : count_set_bits (uword x)
73 : {
74 : #ifdef __POPCNT__
75 912343893 : return uword_bits > 32 ? __builtin_popcountll (x) : __builtin_popcount (x);
76 : #else
77 : #if uword_bits == 64
78 : const uword c1 = 0x5555555555555555;
79 : const uword c2 = 0x3333333333333333;
80 : const uword c3 = 0x0f0f0f0f0f0f0f0f;
81 : #else
82 : const uword c1 = 0x55555555;
83 : const uword c2 = 0x33333333;
84 : const uword c3 = 0x0f0f0f0f;
85 : #endif
86 :
87 : /* Sum 1 bit at a time. */
88 : x = x - ((x >> (uword) 1) & c1);
89 :
90 : /* 2 bits at a time. */
91 : x = (x & c2) + ((x >> (uword) 2) & c2);
92 :
93 : /* 4 bits at a time. */
94 : x = (x + (x >> (uword) 4)) & c3;
95 :
96 : /* 8, 16, 32 bits at a time. */
97 : x = x + (x >> (uword) 8);
98 : x = x + (x >> (uword) 16);
99 : #if uword_bits == 64
100 : x = x + (x >> (uword) 32);
101 : #endif
102 :
103 : return x & (2 * BITS (uword) - 1);
104 : #endif
105 : }
106 :
107 : #if uword_bits == 64
108 : #define count_leading_zeros(x) __builtin_clzll (x)
109 : #else
110 : #define count_leading_zeros(x) __builtin_clzll (x)
111 : #endif
112 :
113 : #define count_trailing_zeros(x) get_lowest_set_bit_index (x)
114 : #define log2_first_set(x) get_lowest_set_bit_index (x)
115 :
116 : /* Based on "Hacker's Delight" code from GLS. */
117 : typedef struct
118 : {
119 : uword masks[1 + log2_uword_bits];
120 : } compress_main_t;
121 :
122 : always_inline void
123 : compress_init (compress_main_t * cm, uword mask)
124 : {
125 : uword q, m, zm, n, i;
126 :
127 : m = ~mask;
128 : zm = mask;
129 :
130 : cm->masks[0] = mask;
131 : for (i = 0; i < log2_uword_bits; i++)
132 : {
133 : q = m;
134 : m ^= m << 1;
135 : m ^= m << 2;
136 : m ^= m << 4;
137 : m ^= m << 8;
138 : m ^= m << 16;
139 : #if uword_bits > 32
140 : m ^= m << (uword) 32;
141 : #endif
142 : cm->masks[1 + i] = n = (m << 1) & zm;
143 : m = q & ~m;
144 : q = zm & n;
145 : zm = zm ^ q ^ (q >> (1 << i));
146 : }
147 : }
148 :
149 : always_inline uword
150 : compress_bits (compress_main_t * cm, uword x)
151 : {
152 : uword q, r;
153 :
154 : r = x & cm->masks[0];
155 : q = r & cm->masks[1];
156 : r ^= q ^ (q >> 1);
157 : q = r & cm->masks[2];
158 : r ^= q ^ (q >> 2);
159 : q = r & cm->masks[3];
160 : r ^= q ^ (q >> 4);
161 : q = r & cm->masks[4];
162 : r ^= q ^ (q >> 8);
163 : q = r & cm->masks[5];
164 : r ^= q ^ (q >> 16);
165 : #if uword_bits > 32
166 : q = r & cm->masks[6];
167 : r ^= q ^ (q >> (uword) 32);
168 : #endif
169 :
170 : return r;
171 : }
172 :
173 : always_inline uword
174 0 : rotate_left (uword x, uword i)
175 : {
176 0 : return (x << i) | (x >> (BITS (i) - i));
177 : }
178 :
179 : always_inline uword
180 : rotate_right (uword x, uword i)
181 : {
182 : return (x >> i) | (x << (BITS (i) - i));
183 : }
184 :
185 : /* Returns snoob from Hacker's Delight. Next highest number
186 : with same number of set bits. */
187 : always_inline uword
188 : next_with_same_number_of_set_bits (uword x)
189 : {
190 : uword smallest, ripple, ones;
191 : smallest = x & -x;
192 : ripple = x + smallest;
193 : ones = x ^ ripple;
194 : ones = ones >> (2 + log2_first_set (x));
195 : return ripple | ones;
196 : }
197 :
198 : #define foreach_set_bit_index(i, v) \
199 : for (uword _tmp = (v) + 0 * (uword) (i = get_lowest_set_bit_index (v)); \
200 : _tmp; \
201 : i = get_lowest_set_bit_index (_tmp = clear_lowest_set_bit (_tmp)))
202 :
203 : static_always_inline uword
204 : uword_bitmap_count_set_bits (uword *bmp, uword n_uwords)
205 : {
206 : uword count = 0;
207 : while (n_uwords--)
208 : count += count_set_bits (bmp++[0]);
209 : return count;
210 : }
211 :
212 : static_always_inline uword
213 : uword_bitmap_is_bit_set (uword *bmp, uword bit_index)
214 : {
215 : bmp += bit_index / uword_bits;
216 : bit_index %= uword_bits;
217 : return (bmp[0] >> bit_index) & 1;
218 : }
219 :
220 : static_always_inline void
221 : uword_bitmap_set_bits_at_index (uword *bmp, uword bit_index, uword n_bits)
222 : {
223 : bmp += bit_index / uword_bits;
224 : bit_index %= uword_bits;
225 : uword max_bits = uword_bits - bit_index;
226 :
227 : if (n_bits < max_bits)
228 : {
229 : bmp[0] |= pow2_mask (n_bits) << bit_index;
230 : return;
231 : }
232 :
233 : bmp++[0] |= pow2_mask (max_bits) << bit_index;
234 : n_bits -= max_bits;
235 :
236 : for (; n_bits >= uword_bits; bmp++, n_bits -= uword_bits)
237 : bmp[0] = ~0ULL;
238 :
239 : if (n_bits)
240 : bmp[0] |= pow2_mask (n_bits);
241 : }
242 :
243 : static_always_inline void
244 : uword_bitmap_clear_bits_at_index (uword *bmp, uword bit_index, uword n_bits)
245 : {
246 : bmp += bit_index / uword_bits;
247 : bit_index %= uword_bits;
248 : uword max_bits = uword_bits - bit_index;
249 :
250 : if (n_bits < max_bits)
251 : {
252 : bmp[0] &= ~(pow2_mask (n_bits) << bit_index);
253 : return;
254 : }
255 :
256 : bmp++[0] &= ~(pow2_mask (max_bits) << bit_index);
257 : n_bits -= max_bits;
258 :
259 : for (; n_bits >= uword_bits; bmp++, n_bits -= uword_bits)
260 : bmp[0] = 0ULL;
261 :
262 : if (n_bits)
263 : bmp[0] &= ~pow2_mask (n_bits);
264 : }
265 :
266 : static_always_inline int
267 : uword_bitmap_find_first_set (uword *bmp)
268 : {
269 : uword *b = bmp;
270 : while (b[0] == 0)
271 : b++;
272 :
273 : return (b - bmp) * uword_bits + get_lowest_set_bit_index (b[0]);
274 : }
275 :
276 : static_always_inline u32
277 : bit_extract_u32 (u32 v, u32 mask)
278 : {
279 : #ifdef __BMI2__
280 : return _pext_u32 (v, mask);
281 : #else
282 : u32 rv = 0;
283 : u32 bit = 1;
284 :
285 : while (mask)
286 : {
287 : u32 lowest_mask_bit = get_lowest_set_bit (mask);
288 : mask ^= lowest_mask_bit;
289 : rv |= (v & lowest_mask_bit) ? bit : 0;
290 : bit <<= 1;
291 : }
292 :
293 : return rv;
294 : #endif
295 : }
296 :
297 : static_always_inline u64
298 : bit_extract_u64 (u64 v, u64 mask)
299 : {
300 : #ifdef __BMI2__
301 : return _pext_u64 (v, mask);
302 : #else
303 : u64 rv = 0;
304 : u64 bit = 1;
305 :
306 : while (mask)
307 : {
308 : u64 lowest_mask_bit = get_lowest_set_bit (mask);
309 : mask ^= lowest_mask_bit;
310 : rv |= (v & lowest_mask_bit) ? bit : 0;
311 : bit <<= 1;
312 : }
313 :
314 : return rv;
315 : #endif
316 : }
317 :
318 : #else
319 : #warning "already included"
320 : #endif /* included_clib_bitops_h */
321 :
322 : /*
323 : * fd.io coding-style-patch-verification: ON
324 : *
325 : * Local Variables:
326 : * eval: (c-set-style "gnu")
327 : * End:
328 : */
|
