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