SDSL  3.0.0
Succinct Data Structure Library
bits.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_BITS
9 #define INCLUDED_SDSL_BITS
10 
11 #include <cassert>
12 #include <iostream> // for cerr
13 #include <stdint.h> // for uint64_t uint32_t declaration
14 #ifdef __SSE4_2__
15 #include <xmmintrin.h>
16 #endif
17 #ifdef __BMI2__
18 #include <x86intrin.h>
19 #endif
20 
21 #ifdef WIN32
22 #include <sdsl/iso646.h>
23 #endif
24 
25 #ifdef __cpp_constexpr
26 #if __cpp_constexpr >= 201304
27 #define SDSL_CONSTEXPR constexpr
28 #else
29 #define SDSL_CONSTEXPR
30 #endif
31 #else
32 #define SDSL_CONSTEXPR
33 #endif
34 
36 namespace sdsl
37 {
38 
40 
54 template <typename T = void>
55 struct bits_impl
56 {
57  bits_impl() = delete;
59  constexpr static uint64_t all_set{ -1ULL };
60 
62 
67  constexpr static uint64_t deBruijn64{ 0x0218A392CD3D5DBFULL };
68 
70 
72  constexpr static uint32_t lt_deBruijn_to_idx[64] = {
73  0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46,
74  29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47,
75  30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58
76  };
77 
79  constexpr static uint64_t lt_fib[92] = { 1,
80  2,
81  3,
82  5,
83  8,
84  13,
85  21,
86  34,
87  55,
88  89,
89  144,
90  233,
91  377,
92  610,
93  987,
94  1597,
95  2584,
96  4181,
97  6765,
98  10946,
99  17711,
100  28657,
101  46368,
102  75025,
103  121393,
104  196418,
105  317811,
106  514229,
107  832040,
108  1346269,
109  2178309,
110  3524578,
111  5702887,
112  9227465,
113  14930352,
114  24157817,
115  39088169,
116  63245986,
117  102334155,
118  165580141,
119  267914296,
120  433494437,
121  701408733,
122  1134903170,
123  1836311903,
124  2971215073ULL,
125  0x11e8d0a40ULL,
126  0x1cfa62f21ULL,
127  0x2ee333961ULL,
128  0x4bdd96882ULL,
129  0x7ac0ca1e3ULL,
130  0xc69e60a65ULL,
131  0x1415f2ac48ULL,
132  0x207fd8b6adULL,
133  0x3495cb62f5ULL,
134  0x5515a419a2ULL,
135  0x89ab6f7c97ULL,
136  0xdec1139639ULL,
137  0x1686c8312d0ULL,
138  0x2472d96a909ULL,
139  0x3af9a19bbd9ULL,
140  0x5f6c7b064e2ULL,
141  0x9a661ca20bbULL,
142  0xf9d297a859dULL,
143  0x19438b44a658ULL,
144  0x28e0b4bf2bf5ULL,
145  0x42244003d24dULL,
146  0x6b04f4c2fe42ULL,
147  0xad2934c6d08fULL,
148  0x1182e2989ced1ULL,
149  0x1c5575e509f60ULL,
150  0x2dd8587da6e31ULL,
151  0x4a2dce62b0d91ULL,
152  0x780626e057bc2ULL,
153  0xc233f54308953ULL,
154  0x13a3a1c2360515ULL,
155  0x1fc6e116668e68ULL,
156  0x336a82d89c937dULL,
157  0x533163ef0321e5ULL,
158  0x869be6c79fb562ULL,
159  0xd9cd4ab6a2d747ULL,
160  0x16069317e428ca9ULL,
161  0x23a367c34e563f0ULL,
162  0x39a9fadb327f099ULL,
163  0x5d4d629e80d5489ULL,
164  0x96f75d79b354522ULL,
165  0xf444c01834299abULL,
166  0x18b3c1d91e77decdULL,
167  0x27f80ddaa1ba7878ULL,
168  0x40abcfb3c0325745ULL,
169  0x68a3dd8e61eccfbdULL,
170  0xa94fad42221f2702ULL };
171 
173  constexpr static uint8_t lt_cnt[256] = {
174  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
175  3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
176  3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
177  6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
178  3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
179  5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
180  6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
181  };
182 
184  constexpr static uint32_t lt_hi[256] = {
185  0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
186  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
187  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
188  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
189  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
190  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
191  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
192  };
193 
195 
197  constexpr static uint64_t lo_set[65] = {
198  0x0000000000000000ULL, 0x0000000000000001ULL, 0x0000000000000003ULL, 0x0000000000000007ULL,
199  0x000000000000000FULL, 0x000000000000001FULL, 0x000000000000003FULL, 0x000000000000007FULL,
200  0x00000000000000FFULL, 0x00000000000001FFULL, 0x00000000000003FFULL, 0x00000000000007FFULL,
201  0x0000000000000FFFULL, 0x0000000000001FFFULL, 0x0000000000003FFFULL, 0x0000000000007FFFULL,
202  0x000000000000FFFFULL, 0x000000000001FFFFULL, 0x000000000003FFFFULL, 0x000000000007FFFFULL,
203  0x00000000000FFFFFULL, 0x00000000001FFFFFULL, 0x00000000003FFFFFULL, 0x00000000007FFFFFULL,
204  0x0000000000FFFFFFULL, 0x0000000001FFFFFFULL, 0x0000000003FFFFFFULL, 0x0000000007FFFFFFULL,
205  0x000000000FFFFFFFULL, 0x000000001FFFFFFFULL, 0x000000003FFFFFFFULL, 0x000000007FFFFFFFULL,
206  0x00000000FFFFFFFFULL, 0x00000001FFFFFFFFULL, 0x00000003FFFFFFFFULL, 0x00000007FFFFFFFFULL,
207  0x0000000FFFFFFFFFULL, 0x0000001FFFFFFFFFULL, 0x0000003FFFFFFFFFULL, 0x0000007FFFFFFFFFULL,
208  0x000000FFFFFFFFFFULL, 0x000001FFFFFFFFFFULL, 0x000003FFFFFFFFFFULL, 0x000007FFFFFFFFFFULL,
209  0x00000FFFFFFFFFFFULL, 0x00001FFFFFFFFFFFULL, 0x00003FFFFFFFFFFFULL, 0x00007FFFFFFFFFFFULL,
210  0x0000FFFFFFFFFFFFULL, 0x0001FFFFFFFFFFFFULL, 0x0003FFFFFFFFFFFFULL, 0x0007FFFFFFFFFFFFULL,
211  0x000FFFFFFFFFFFFFULL, 0x001FFFFFFFFFFFFFULL, 0x003FFFFFFFFFFFFFULL, 0x007FFFFFFFFFFFFFULL,
212  0x00FFFFFFFFFFFFFFULL, 0x01FFFFFFFFFFFFFFULL, 0x03FFFFFFFFFFFFFFULL, 0x07FFFFFFFFFFFFFFULL,
213  0x0FFFFFFFFFFFFFFFULL, 0x1FFFFFFFFFFFFFFFULL, 0x3FFFFFFFFFFFFFFFULL, 0x7FFFFFFFFFFFFFFFULL,
214  0xFFFFFFFFFFFFFFFFULL
215  };
216 
218 
220  constexpr static uint64_t lo_unset[65] = {
221  0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFF8ULL,
222  0xFFFFFFFFFFFFFFF0ULL, 0xFFFFFFFFFFFFFFE0ULL, 0xFFFFFFFFFFFFFFC0ULL, 0xFFFFFFFFFFFFFF80ULL,
223  0xFFFFFFFFFFFFFF00ULL, 0xFFFFFFFFFFFFFE00ULL, 0xFFFFFFFFFFFFFC00ULL, 0xFFFFFFFFFFFFF800ULL,
224  0xFFFFFFFFFFFFF000ULL, 0xFFFFFFFFFFFFE000ULL, 0xFFFFFFFFFFFFC000ULL, 0xFFFFFFFFFFFF8000ULL,
225  0xFFFFFFFFFFFF0000ULL, 0xFFFFFFFFFFFE0000ULL, 0xFFFFFFFFFFFC0000ULL, 0xFFFFFFFFFFF80000ULL,
226  0xFFFFFFFFFFF00000ULL, 0xFFFFFFFFFFE00000ULL, 0xFFFFFFFFFFC00000ULL, 0xFFFFFFFFFF800000ULL,
227  0xFFFFFFFFFF000000ULL, 0xFFFFFFFFFE000000ULL, 0xFFFFFFFFFC000000ULL, 0xFFFFFFFFF8000000ULL,
228  0xFFFFFFFFF0000000ULL, 0xFFFFFFFFE0000000ULL, 0xFFFFFFFFC0000000ULL, 0xFFFFFFFF80000000ULL,
229  0xFFFFFFFF00000000ULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFF800000000ULL,
230  0xFFFFFFF000000000ULL, 0xFFFFFFE000000000ULL, 0xFFFFFFC000000000ULL, 0xFFFFFF8000000000ULL,
231  0xFFFFFF0000000000ULL, 0xFFFFFE0000000000ULL, 0xFFFFFC0000000000ULL, 0xFFFFF80000000000ULL,
232  0xFFFFF00000000000ULL, 0xFFFFE00000000000ULL, 0xFFFFC00000000000ULL, 0xFFFF800000000000ULL,
233  0xFFFF000000000000ULL, 0xFFFE000000000000ULL, 0xFFFC000000000000ULL, 0xFFF8000000000000ULL,
234  0xFFF0000000000000ULL, 0xFFE0000000000000ULL, 0xFFC0000000000000ULL, 0xFF80000000000000ULL,
235  0xFF00000000000000ULL, 0xFE00000000000000ULL, 0xFC00000000000000ULL, 0xF800000000000000ULL,
236  0xF000000000000000ULL, 0xE000000000000000ULL, 0xC000000000000000ULL, 0x8000000000000000ULL,
237  0x0000000000000000ULL
238  };
239 
241  constexpr static uint8_t lt_lo[256] = {
242  0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00,
243  0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00,
244  0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00,
245  0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
246  0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
247  0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
248  0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00,
249  0x01, 0x00, 0x07, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
250  0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00,
251  0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00,
252  0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00,
253  0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
254  0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
255  0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
256  0x02, 0x00, 0x01, 0x00
257  };
258 
260 
263  constexpr static uint8_t lt_sel[256 * 8] = {
264  0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,
265  0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0,
266  1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1,
267  0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
268  2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
269  0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
270  1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
271 
272  0, 0, 0, 1, 0, 2, 2, 1, 0, 3, 3, 1, 3, 2, 2, 1, 0, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 5, 5, 1, 5,
273  2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 6, 6, 1, 6, 2, 2, 1, 6, 3,
274  3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2,
275  1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, 7, 4, 4, 1,
276  4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4,
277  3, 3, 1, 3, 2, 2, 1, 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2,
278  2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
279 
280  0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 3, 2, 0, 0, 0, 4, 0, 4, 4, 2, 0, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 5, 0,
281  5, 5, 2, 0, 5, 5, 3, 5, 3, 3, 2, 0, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 6, 0, 6, 6, 2, 0, 6,
282  6, 3, 6, 3, 3, 2, 0, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2, 0, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3,
283  2, 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 7, 0, 7, 7, 2, 0, 7, 7, 3, 7, 3, 3, 2, 0, 7, 7, 4,
284  7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2, 0, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2, 7, 5, 5, 4, 5, 4, 4, 2, 5,
285  4, 4, 3, 4, 3, 3, 2, 0, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2, 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3,
286  3, 2, 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2, 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
287 
288  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 0, 4, 4, 3, 0, 0, 0, 0, 0,
289  0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 3, 0, 0, 0, 5, 0, 5, 5, 4, 0, 5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0,
290  0, 6, 0, 6, 6, 3, 0, 0, 0, 6, 0, 6, 6, 4, 0, 6, 6, 4, 6, 4, 4, 3, 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5,
291  3, 0, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 3, 0, 0, 0, 7,
292  0, 7, 7, 4, 0, 7, 7, 4, 7, 4, 4, 3, 0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 3, 0, 7, 7, 5, 7, 5, 5, 4, 7,
293  5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 3, 0, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4,
294  4, 3, 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
295 
296  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0,
297  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
298  0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 4, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6,
299  5, 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0,
300  0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 4, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5, 0, 0, 0, 7, 0, 7, 7, 5, 0,
301  7, 7, 5, 7, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6,
302  6, 4, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5, 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
303 
304  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
305  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
306  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
307  6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
308  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0,
309  0, 0, 7, 0, 7, 7, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7,
310  7, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
311 
312  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
313  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
314  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
315  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
316  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
317  0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
318  0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
319 
320  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
321  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
322  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
323  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
324  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
325  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
326  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
327  };
328 
330  constexpr static uint64_t ps_overflow[65] = {
331  0x8080808080808080ULL, 0x7f7f7f7f7f7f7f7fULL, 0x7e7e7e7e7e7e7e7eULL, 0x7d7d7d7d7d7d7d7dULL,
332  0x7c7c7c7c7c7c7c7cULL, 0x7b7b7b7b7b7b7b7bULL, 0x7a7a7a7a7a7a7a7aULL, 0x7979797979797979ULL,
333  0x7878787878787878ULL, 0x7777777777777777ULL, 0x7676767676767676ULL, 0x7575757575757575ULL,
334  0x7474747474747474ULL, 0x7373737373737373ULL, 0x7272727272727272ULL, 0x7171717171717171ULL,
335  0x7070707070707070ULL, 0x6f6f6f6f6f6f6f6fULL, 0x6e6e6e6e6e6e6e6eULL, 0x6d6d6d6d6d6d6d6dULL,
336  0x6c6c6c6c6c6c6c6cULL, 0x6b6b6b6b6b6b6b6bULL, 0x6a6a6a6a6a6a6a6aULL, 0x6969696969696969ULL,
337  0x6868686868686868ULL, 0x6767676767676767ULL, 0x6666666666666666ULL, 0x6565656565656565ULL,
338  0x6464646464646464ULL, 0x6363636363636363ULL, 0x6262626262626262ULL, 0x6161616161616161ULL,
339  0x6060606060606060ULL, 0x5f5f5f5f5f5f5f5fULL, 0x5e5e5e5e5e5e5e5eULL, 0x5d5d5d5d5d5d5d5dULL,
340  0x5c5c5c5c5c5c5c5cULL, 0x5b5b5b5b5b5b5b5bULL, 0x5a5a5a5a5a5a5a5aULL, 0x5959595959595959ULL,
341  0x5858585858585858ULL, 0x5757575757575757ULL, 0x5656565656565656ULL, 0x5555555555555555ULL,
342  0x5454545454545454ULL, 0x5353535353535353ULL, 0x5252525252525252ULL, 0x5151515151515151ULL,
343  0x5050505050505050ULL, 0x4f4f4f4f4f4f4f4fULL, 0x4e4e4e4e4e4e4e4eULL, 0x4d4d4d4d4d4d4d4dULL,
344  0x4c4c4c4c4c4c4c4cULL, 0x4b4b4b4b4b4b4b4bULL, 0x4a4a4a4a4a4a4a4aULL, 0x4949494949494949ULL,
345  0x4848484848484848ULL, 0x4747474747474747ULL, 0x4646464646464646ULL, 0x4545454545454545ULL,
346  0x4444444444444444ULL, 0x4343434343434343ULL, 0x4242424242424242ULL, 0x4141414141414141ULL,
347  0x4040404040404040ULL
348  };
349 
351 
354  SDSL_CONSTEXPR static uint64_t cnt(uint64_t x);
355 
357 
362  SDSL_CONSTEXPR static uint32_t hi(uint64_t x);
363 
365 
370  SDSL_CONSTEXPR static uint32_t lo(uint64_t x);
371 
373 
379  SDSL_CONSTEXPR static uint32_t cnt32(uint32_t x);
380 
382 
386  SDSL_CONSTEXPR static uint32_t cnt11(uint64_t x, uint64_t & c);
387 
389 
392  SDSL_CONSTEXPR static uint32_t cnt11(uint64_t x);
393 
395 
399  SDSL_CONSTEXPR static uint32_t cnt10(uint64_t x, uint64_t & c);
400 
402 
406  SDSL_CONSTEXPR static uint32_t cnt01(uint64_t x, uint64_t & c);
407 
409  SDSL_CONSTEXPR static uint64_t map10(uint64_t x, uint64_t c = 0);
410 
412  SDSL_CONSTEXPR static uint64_t map01(uint64_t x, uint64_t c = 1);
413 
415 
421  SDSL_CONSTEXPR static uint32_t sel(uint64_t x, uint32_t i);
422  SDSL_CONSTEXPR static uint32_t _sel(uint64_t x, uint32_t i);
423 
425 
433  SDSL_CONSTEXPR static uint32_t sel11(uint64_t x, uint32_t i, uint32_t c = 0);
434 
436 
442  SDSL_CONSTEXPR static uint32_t hi11(uint64_t x);
443 
445  SDSL_CONSTEXPR static void write_int(uint64_t * word, uint64_t x, const uint8_t offset = 0, const uint8_t len = 64);
446 
448  SDSL_CONSTEXPR static void write_int_and_move(uint64_t *& word, uint64_t x, uint8_t & offset, const uint8_t len);
449 
451  SDSL_CONSTEXPR static uint64_t read_int(const uint64_t * word, uint8_t offset = 0, const uint8_t len = 64);
452  SDSL_CONSTEXPR static uint64_t read_int_bounded(const uint64_t * word, uint8_t offset = 0, const uint8_t len = 64);
453 
455  SDSL_CONSTEXPR static uint64_t read_int_and_move(const uint64_t *& word, uint8_t & offset, const uint8_t len = 64);
456 
458  SDSL_CONSTEXPR static uint64_t read_unary(const uint64_t * word, uint8_t offset = 0);
459  SDSL_CONSTEXPR static uint64_t read_unary_bounded(const uint64_t * word, uint8_t offset = 0);
460 
462  SDSL_CONSTEXPR static uint64_t read_unary_and_move(const uint64_t *& word, uint8_t & offset);
463 
465 
470  SDSL_CONSTEXPR static void move_right(const uint64_t *& word, uint8_t & offset, const uint8_t len);
471 
473 
478  SDSL_CONSTEXPR static void move_left(const uint64_t *& word, uint8_t & offset, const uint8_t len);
479 
481  SDSL_CONSTEXPR static uint64_t next(const uint64_t * word, uint64_t idx);
482 
484  SDSL_CONSTEXPR static uint64_t prev(const uint64_t * word, uint64_t idx);
485 
487  SDSL_CONSTEXPR static uint64_t rev(uint64_t x);
488 };
489 
490 // ============= inline - implementations ================
491 
492 // see page 11, Knuth TAOCP Vol 4 F1A
493 template <typename T>
494 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::cnt(uint64_t x)
495 {
496 #ifdef __SSE4_2__
497  return __builtin_popcountll(x);
498 #else
499 #ifdef POPCOUNT_TL
500  return lt_cnt[x & 0xFFULL] + lt_cnt[(x >> 8) & 0xFFULL] + lt_cnt[(x >> 16) & 0xFFULL] +
501  lt_cnt[(x >> 24) & 0xFFULL] + lt_cnt[(x >> 32) & 0xFFULL] + lt_cnt[(x >> 40) & 0xFFULL] +
502  lt_cnt[(x >> 48) & 0xFFULL] + lt_cnt[(x >> 56) & 0xFFULL];
503 #else
504  x = x - ((x >> 1) & 0x5555555555555555ull);
505  x = (x & 0x3333333333333333ull) + ((x >> 2) & 0x3333333333333333ull);
506  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0full;
507  return (0x0101010101010101ull * x >> 56);
508 #endif
509 #endif
510 }
511 
512 template <typename T>
513 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::cnt32(uint32_t x)
514 {
515 #ifdef __SSE4_2__
516  return __builtin_popcount(x);
517 #else
518  x = x - ((x >> 1) & 0x55555555);
519  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
520  return (0x10101010 * x >> 28) + (0x01010101 * x >> 28);
521 #endif
522 }
523 
524 // We produce a 1 bit in the upper bit of each disjoint 2-bit group of
525 // ones, and then count the 1 bits.
526 //
527 // Consider a 2-bit group at an even position that does not receive a
528 // carry from the '+':
529 //
530 // x ^ + ^ & carry
531 // 00 01 10 11 00
532 // 01 00 01 00 00
533 // 10 11 00 01 00 x
534 // 11 10 11 10 10
535 //
536 // We get an 1 bit if and only if we have a 2-bit group that is to be
537 // counted, and a carry is produced if and only if the top bit is a 1
538 // that could start another 2-bit group.
539 //
540 // For a 2-bit group that does receive a carry:
541 //
542 // ^ + ^ & carry
543 // 00 01 11 10 00
544 // 01 00 10 11 01
545 // 10 11 01 00 00 x
546 // 11 10 00 01 01 x
547 //
548 // Also here we get the correct 1 bits and carries.
549 //
550 template <typename T>
551 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::cnt11(uint64_t x, uint64_t & c)
552 {
553  uint64_t t1 = x ^ 0x5555555555555555ULL;
554  uint64_t t2 = t1 + 0x5555555555555555ULL + c;
555  c = t1 > t2; // detect overflow in the sum
556  return cnt((t2 ^ 0x5555555555555555ULL) & x);
557 }
558 
559 template <typename T>
560 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::cnt11(uint64_t x)
561 {
562  return cnt((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL) ^ 0x5555555555555555ULL) & x);
563 }
564 
565 template <typename T>
566 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::cnt10(uint64_t x, uint64_t & c)
567 {
568  uint32_t res = cnt(((x << 1) | c) & (~x));
569  c = (x >> 63);
570  return res;
571 }
572 
573 template <typename T>
574 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::map10(uint64_t x, uint64_t c)
575 {
576  return (((x << 1) | c) & (~x));
577 }
578 
579 template <typename T>
580 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::cnt01(uint64_t x, uint64_t & c)
581 {
582  uint32_t res = cnt((x ^ ((x << 1) | c)) & x);
583  c = (x >> 63);
584  return res;
585 }
586 
587 template <typename T>
588 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::map01(uint64_t x, uint64_t c)
589 {
590  return ((x ^ ((x << 1) | c)) & x);
591 }
592 
593 template <typename T>
594 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::sel(uint64_t x, uint32_t i)
595 {
596 #ifdef __BMI2__
597  // taken from folly
598  return _tzcnt_u64(_pdep_u64(1ULL << (i - 1), x));
599 #endif
600 #ifdef __SSE4_2__
601  uint64_t s = x, b{};
602  s = s - ((s >> 1) & 0x5555555555555555ULL);
603  s = (s & 0x3333333333333333ULL) + ((s >> 2) & 0x3333333333333333ULL);
604  s = (s + (s >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
605  s = 0x0101010101010101ULL * s;
606  // now s contains 8 bytes s[7],...,s[0]; s[j] contains the cumulative sum
607  // of (j+1)*8 least significant bits of s
608  b = (s + ps_overflow[i]) & 0x8080808080808080ULL;
609  // ps_overflow contains a bit mask x consisting of 8 bytes
610  // x[7],...,x[0] and x[j] is set to 128-j
611  // => a byte b[j] in b is >= 128 if cum sum >= j
612 
613  // __builtin_ctzll returns the number of trailing zeros, if b!=0
614  int byte_nr = __builtin_ctzll(b) >> 3; // byte nr in [0..7]
615  s <<= 8;
616  i -= (s >> (byte_nr << 3)) & 0xFFULL;
617  return (byte_nr << 3) + lt_sel[((i - 1) << 8) + ((x >> (byte_nr << 3)) & 0xFFULL)];
618 #endif
619  return _sel(x, i);
620 }
621 
622 template <typename T>
623 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::_sel(uint64_t x, uint32_t i)
624 {
625  uint64_t s = x, b{}; // s = sum
626  s = s - ((s >> 1) & 0x5555555555555555ULL);
627  s = (s & 0x3333333333333333ULL) + ((s >> 2) & 0x3333333333333333ULL);
628  s = (s + (s >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
629  s = 0x0101010101010101ULL * s;
630  b = (s + ps_overflow[i]); //&0x8080808080808080ULL;// add something to the partial sums to cause overflow
631  i = (i - 1) << 8;
632  if (b & 0x0000000080000000ULL) // byte <=3
633  if (b & 0x0000000000008000ULL) // byte <= 1
634  if (b & 0x0000000000000080ULL)
635  return lt_sel[(x & 0xFFULL) + i];
636  else
637  return 8 + lt_sel[(((x >> 8) & 0xFFULL) + i - ((s & 0xFFULL) << 8)) & 0x7FFULL]; // byte 1;
638  else // byte >1
639  if (b & 0x0000000000800000ULL) // byte <=2
640  return 16 + lt_sel[(((x >> 16) & 0xFFULL) + i - (s & 0xFF00ULL)) & 0x7FFULL]; // byte 2;
641  else
642  return 24 + lt_sel[(((x >> 24) & 0xFFULL) + i - ((s >> 8) & 0xFF00ULL)) & 0x7FFULL]; // byte 3;
643  else // byte > 3
644  if (b & 0x0000800000000000ULL) // byte <=5
645  if (b & 0x0000008000000000ULL) // byte <=4
646  return 32 + lt_sel[(((x >> 32) & 0xFFULL) + i - ((s >> 16) & 0xFF00ULL)) & 0x7FFULL]; // byte 4;
647  else
648  return 40 + lt_sel[(((x >> 40) & 0xFFULL) + i - ((s >> 24) & 0xFF00ULL)) & 0x7FFULL]; // byte 5;
649  else // byte >5
650  if (b & 0x0080000000000000ULL) // byte<=6
651  return 48 + lt_sel[(((x >> 48) & 0xFFULL) + i - ((s >> 32) & 0xFF00ULL)) & 0x7FFULL]; // byte 6;
652  else
653  return 56 + lt_sel[(((x >> 56) & 0xFFULL) + i - ((s >> 40) & 0xFF00ULL)) & 0x7FFULL]; // byte 7;
654  return 0;
655 }
656 
657 // using built-in method or
658 // 64-bit version of 32-bit proposal of
659 // http://www-graphics.stanford.edu/~seander/bithacks.html
660 template <typename T>
661 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::hi(uint64_t x)
662 {
663 #ifdef __SSE4_2__
664  if (x == 0) return 0;
665  return 63 - __builtin_clzll(x);
666 #else
667  uint64_t t{}, tt{}; // temporaries
668  if ((tt = x >> 32))
669  { // hi >= 32
670  if ((t = tt >> 16))
671  { // hi >= 48
672  return (tt = t >> 8) ? 56 + lt_hi[tt] : 48 + lt_hi[t];
673  }
674  else
675  { // hi < 48
676  return (t = tt >> 8) ? 40 + lt_hi[t] : 32 + lt_hi[tt];
677  }
678  }
679  else
680  { // hi < 32
681  if ((t = x >> 16))
682  { // hi >= 16
683  return (tt = t >> 8) ? 24 + lt_hi[tt] : 16 + lt_hi[t];
684  }
685  else
686  { // hi < 16
687  return (tt = x >> 8) ? 8 + lt_hi[tt] : lt_hi[x];
688  }
689  }
690 #endif
691 }
692 
693 // details see: http://citeseer.ist.psu.edu/leiserson98using.html
694 // or page 10, Knuth TAOCP Vol 4 F1A
695 template <typename T>
696 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::lo(uint64_t x)
697 {
698 #ifdef __SSE4_2__
699  if (x == 0) return 0;
700  return __builtin_ctzll(x);
701 #else
702  if (x & 1) return 0;
703  if (x & 3) return 1;
704  if (x & 7) return 2;
705  if (x & 0x7FF)
706  { // in average every second random number x can be answered this way
707  return lt_lo[(x & 0x7FF) >> 3] + 3;
708  }
709  // x&-x equals x with only the lsb set
710  return lt_deBruijn_to_idx[((x & -x) * deBruijn64) >> 58];
711 #endif
712 }
713 
714 template <typename T>
715 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::hi11(uint64_t x)
716 {
717  return hi((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL) ^ 0x5555555555555555ULL) & x);
718 }
719 
720 template <typename T>
721 SDSL_CONSTEXPR inline uint32_t bits_impl<T>::sel11(uint64_t x, uint32_t i, uint32_t c)
722 {
723  return sel((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL + c) ^ 0x5555555555555555ULL) & x, i);
724 }
725 
726 template <typename T>
727 SDSL_CONSTEXPR inline void bits_impl<T>::write_int(uint64_t * word, uint64_t x, uint8_t offset, const uint8_t len)
728 {
729  x &= bits_impl<T>::lo_set[len];
730  if (offset + len < 64)
731  {
732  *word &= ((bits_impl<T>::all_set << (offset + len)) | bits_impl<T>::lo_set[offset]); // mask 1..10..01..1
733  *word |= (x << offset);
734  // *word ^= ((*word ^ x) & (bits_impl<T>::lo_set[len] << offset) );
735  // surprisingly the above line is slower than the lines above
736  }
737  else
738  {
739  *word &= ((bits_impl<T>::lo_set[offset])); // mask 0....01..1
740  *word |= (x << offset);
741  if ((offset = (offset + len) & 0x3F))
742  { // offset+len > 64
743  *(word + 1) &= (~bits_impl<T>::lo_set[offset]); // mask 1...10..0
744  // *(word+1) &= bits_impl<T>::lo_unset[offset]; // mask 1...10..0
745  // surprisingly the above line is slower than the line above
746  *(word + 1) |= (x >> (len - offset));
747  }
748  }
749 }
750 
751 template <typename T>
753  uint64_t x,
754  uint8_t & offset,
755  const uint8_t len)
756 {
757  x &= bits_impl<T>::lo_set[len];
758  if (offset + len < 64)
759  {
760  *word &= ((bits_impl<T>::all_set << (offset + len)) | bits_impl<T>::lo_set[offset]); // mask 1..10..01..1
761  *word |= (x << offset);
762  offset += len;
763  }
764  else
765  {
766  *word &= ((bits_impl<T>::lo_set[offset])); // mask 0....01..1
767  *word |= (x << offset);
768  if ((offset = (offset + len)) > 64)
769  { // offset+len >= 64
770  offset &= 0x3F;
771  *(++word) &= (~bits_impl<T>::lo_set[offset]); // mask 1...10..0
772  *word |= (x >> (len - offset));
773  }
774  else
775  {
776  offset = 0;
777  ++word;
778  }
779  }
780 }
781 
782 template <typename T>
783 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_int(const uint64_t * word, uint8_t offset, const uint8_t len)
784 {
785  uint64_t w1 = (*word) >> offset;
786  if ((offset + len) > 64)
787  { // if offset+len > 64
788  return w1 | // w1 or w2 adepted:
789  ((*(word + 1) & bits_impl<T>::lo_set[(offset + len) & 0x3F]) // set higher bits zero
790  << (64 - offset)); // move bits to the left
791  }
792  else
793  {
794  return w1 & bits_impl<T>::lo_set[len];
795  }
796 }
797 
798 template <typename T>
799 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_int_bounded(const uint64_t * word, uint8_t offset, const uint8_t len)
800 {
801  return ((*word) >> offset) & bits_impl<T>::lo_set[len];
802 }
803 
804 template <typename T>
805 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_int_and_move(const uint64_t *& word,
806  uint8_t & offset,
807  const uint8_t len)
808 {
809  uint64_t w1 = (*word) >> offset;
810  if ((offset = (offset + len)) >= 64)
811  { // if offset+len > 64
812  if (offset == 64)
813  {
814  offset &= 0x3F;
815  ++word;
816  return w1;
817  }
818  else
819  {
820  offset &= 0x3F;
821  return w1 | (((*(++word)) & bits_impl<T>::lo_set[offset]) << (len - offset));
822  }
823  }
824  else
825  {
826  return w1 & bits_impl<T>::lo_set[len];
827  }
828 }
829 
830 template <typename T>
831 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_unary(const uint64_t * word, uint8_t offset)
832 {
833  uint64_t w = *word >> offset;
834  if (w) { return bits_impl<T>::lo(w); }
835  else
836  {
837  if (0 != (w = *(++word))) return bits_impl<T>::lo(w) + 64 - offset;
838  uint64_t cnt = 2;
839  while (0 == (w = *(++word))) ++cnt;
840  return bits_impl<T>::lo(w) + (cnt << 6) - offset;
841  }
842  return 0;
843 }
844 
845 template <typename T>
846 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_unary_bounded(const uint64_t * word, uint8_t offset)
847 {
848  uint64_t w = *word >> offset;
849  if (w) { return bits_impl<T>::lo(w); }
850  else
851  {
852  return 0;
853  }
854 }
855 
856 template <typename T>
857 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::read_unary_and_move(const uint64_t *& word, uint8_t & offset)
858 {
859  uint64_t w = (*word) >> offset; // temporary variable is good for the performance
860  if (w)
861  {
862  uint8_t r = bits_impl<T>::lo(w);
863  offset = (offset + r + 1) & 0x3F;
864  // we know that offset + r +1 <= 64, so if the new offset equals 0 increase word
865  word += (offset == 0);
866  return r;
867  }
868  else
869  {
870  uint8_t rr = 0;
871  if (0 != (w = *(++word)))
872  {
873  rr = bits_impl<T>::lo(w) + 64 - offset;
874  offset = (offset + rr + 1) & 0x3F;
875  word += (offset == 0);
876  return rr;
877  }
878  else
879  {
880  uint64_t cnt_1 = 1;
881  while (0 == (w = *(++word))) ++cnt_1;
882  rr = bits_impl<T>::lo(w) + 64 - offset;
883  offset = (offset + rr + 1) & 0x3F;
884  word += (offset == 0);
885  return ((cnt_1) << 6) + rr;
886  }
887  }
888  return 0;
889 }
890 
891 template <typename T>
892 SDSL_CONSTEXPR inline void bits_impl<T>::move_right(const uint64_t *& word, uint8_t & offset, const uint8_t len)
893 {
894  if ((offset += len) & 0xC0)
895  { // if offset >= 65
896  offset &= 0x3F;
897  ++word;
898  }
899 }
900 
901 template <typename T>
902 SDSL_CONSTEXPR inline void bits_impl<T>::move_left(const uint64_t *& word, uint8_t & offset, const uint8_t len)
903 {
904  if ((offset -= len) & 0xC0)
905  { // if offset-len<0
906  offset &= 0x3F;
907  --word;
908  }
909 }
910 
911 template <typename T>
912 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::next(const uint64_t * word, uint64_t idx)
913 {
914  word += (idx >> 6);
915  if (*word & ~lo_set[idx & 0x3F]) { return (idx & ~((size_t)0x3F)) + lo(*word & ~lo_set[idx & 0x3F]); }
916  idx = (idx & ~((size_t)0x3F)) + 64;
917  ++word;
918  while (*word == 0)
919  {
920  idx += 64;
921  ++word;
922  }
923  return idx + lo(*word);
924 }
925 
926 template <typename T>
927 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::prev(const uint64_t * word, uint64_t idx)
928 {
929  word += (idx >> 6);
930  if (*word & lo_set[(idx & 0x3F) + 1]) { return (idx & ~((size_t)0x3F)) + hi(*word & lo_set[(idx & 0x3F) + 1]); }
931  idx = (idx & ~((size_t)0x3F)) - 64;
932  --word;
933  while (*word == 0)
934  {
935  idx -= 64;
936  --word;
937  }
938  return idx + hi(*word);
939 }
940 
941 template <typename T>
942 SDSL_CONSTEXPR inline uint64_t bits_impl<T>::rev(uint64_t x)
943 {
944  x = ((x & 0x5555555555555555ULL) << 1) | ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
945  x = ((x & 0x3333333333333333ULL) << 2) | ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
946  x = ((x & 0x0F0F0F0F0F0F0F0FULL) << 4) | ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);
947  x = ((x & 0x00FF00FF00FF00FFULL) << 8) | ((x & 0xFF00FF00FF00FF00ULL) >> 8);
948  x = ((x & 0x0000FFFF0000FFFFULL) << 16) | ((x & 0xFFFF0000FFFF0000ULL) >> 16);
949  x = ((x & 0x00000000FFFFFFFFULL) << 32) | ((x & 0xFFFFFFFF00000000ULL) >> 32);
950  return x;
951 }
952 
953 template <typename T>
954 constexpr uint8_t bits_impl<T>::lt_cnt[256];
955 template <typename T>
956 constexpr uint32_t bits_impl<T>::lt_deBruijn_to_idx[64];
957 template <typename T>
958 constexpr uint32_t bits_impl<T>::lt_hi[256];
959 template <typename T>
960 constexpr uint64_t bits_impl<T>::lo_set[65];
961 template <typename T>
962 constexpr uint64_t bits_impl<T>::lo_unset[65];
963 template <typename T>
964 constexpr uint64_t bits_impl<T>::ps_overflow[65];
965 template <typename T>
966 constexpr uint8_t bits_impl<T>::lt_sel[256 * 8];
967 template <typename T>
968 constexpr uint64_t bits_impl<T>::lt_fib[92];
969 template <typename T>
970 constexpr uint8_t bits_impl<T>::lt_lo[256];
971 
973 
974 } // end namespace sdsl
975 
976 #endif
#define SDSL_CONSTEXPR
Definition: bits.hpp:32
Namespace for the succinct data structure library.
A helper class for bitwise tricks on 64 bit words.
Definition: bits.hpp:56
static SDSL_CONSTEXPR uint32_t _sel(uint64_t x, uint32_t i)
Definition: bits.hpp:623
constexpr static uint64_t lt_fib[92]
Array containing Fibonacci numbers less than .
Definition: bits.hpp:79
static SDSL_CONSTEXPR uint32_t cnt11(uint64_t x, uint64_t &c)
Count the number of consecutive and distinct 11 in the 64bit integer x.
Definition: bits.hpp:551
static SDSL_CONSTEXPR uint64_t read_unary_and_move(const uint64_t *&word, uint8_t &offset)
Reads an unary decoded value from a bit position in an array and moves the bit-pointer.
Definition: bits.hpp:857
static SDSL_CONSTEXPR uint64_t read_int(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
Definition: bits.hpp:783
static SDSL_CONSTEXPR uint64_t read_unary(const uint64_t *word, uint8_t offset=0)
Reads an unary decoded value from a bit position in an array.
Definition: bits.hpp:831
static SDSL_CONSTEXPR uint32_t hi11(uint64_t x)
Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in ...
Definition: bits.hpp:715
static SDSL_CONSTEXPR void write_int(uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64)
Writes value x to an bit position in an array.
Definition: bits.hpp:727
constexpr static uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
Definition: bits.hpp:220
static SDSL_CONSTEXPR uint32_t sel11(uint64_t x, uint32_t i, uint32_t c=0)
Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integ...
Definition: bits.hpp:721
constexpr static uint8_t lt_sel[256 *8]
Lookup table for select on bytes.
Definition: bits.hpp:263
static SDSL_CONSTEXPR void move_right(const uint64_t *&word, uint8_t &offset, const uint8_t len)
Move the bit-pointer (=uint64_t word and offset) len to the right.
Definition: bits.hpp:892
static SDSL_CONSTEXPR uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
Definition: bits.hpp:594
static SDSL_CONSTEXPR void move_left(const uint64_t *&word, uint8_t &offset, const uint8_t len)
Move the bit-pointer (=uint64_t word and offset) len to the left.
Definition: bits.hpp:902
static SDSL_CONSTEXPR uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:566
static SDSL_CONSTEXPR uint64_t next(const uint64_t *word, uint64_t idx)
Get the first one bit in the interval .
Definition: bits.hpp:912
constexpr static uint32_t lt_deBruijn_to_idx[64]
This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx.
Definition: bits.hpp:72
static SDSL_CONSTEXPR uint32_t cnt32(uint32_t x)
Counts the number of 1-bits in the 32bit integer x.
Definition: bits.hpp:513
static SDSL_CONSTEXPR uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:588
static SDSL_CONSTEXPR uint64_t rev(uint64_t x)
reverses a given 64 bit word
Definition: bits.hpp:942
constexpr static uint32_t lt_hi[256]
Lookup table for most significant set bit in a byte.
Definition: bits.hpp:184
constexpr static uint64_t all_set
64bit mask with all bits set to 1.
Definition: bits.hpp:59
static SDSL_CONSTEXPR uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition: bits.hpp:580
static SDSL_CONSTEXPR void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
Definition: bits.hpp:752
static SDSL_CONSTEXPR uint64_t prev(const uint64_t *word, uint64_t idx)
Get the one bit with the greatest position in the interval .
Definition: bits.hpp:927
constexpr static uint8_t lt_lo[256]
Lookup table for least significant set bit in a byte.
Definition: bits.hpp:241
static SDSL_CONSTEXPR uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition: bits.hpp:696
constexpr static uint64_t ps_overflow[65]
Use to help to decide if a prefix sum stored in a byte overflows.
Definition: bits.hpp:330
constexpr static uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition: bits.hpp:197
constexpr static uint8_t lt_cnt[256]
Lookup table for byte popcounts.
Definition: bits.hpp:173
static SDSL_CONSTEXPR uint64_t read_unary_bounded(const uint64_t *word, uint8_t offset=0)
Definition: bits.hpp:846
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
static SDSL_CONSTEXPR uint64_t read_int_and_move(const uint64_t *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.
Definition: bits.hpp:805
static SDSL_CONSTEXPR uint64_t read_int_bounded(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Definition: bits.hpp:799
constexpr static uint64_t deBruijn64
This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6.
Definition: bits.hpp:67
bits_impl()=delete
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494
static SDSL_CONSTEXPR uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:574