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