8 #ifndef SDSL_CODER_FIBONACCI_INCLUDED
9 #define SDSL_CODER_FIBONACCI_INCLUDED
20 template <
typename T =
void>
26 uint64_t fib12bit_to_bin[(1 << 12) * 8];
33 uint8_t fib2bin_shift[(1 << 13)];
40 uint16_t fib2bin_16_greedy[(1 << 16)];
43 uint64_t fib2bin_0_95[(1 << 12) * 8];
47 for (uint32_t x = 0; x <= 0x1FFF; ++x)
55 for (uint32_t x = 0; x < 1 << 16; ++x)
80 fib2bin_16_greedy[x] = (offset << 11) | w;
82 for (uint32_t p = 0; p < 8; ++p)
84 for (uint32_t x = 0; x <= 0xFFF; ++x)
87 for (uint32_t j = 0; j < 12 and 12 * p + j < 92; ++j)
92 if (x >> (j + 1) & 1ULL) {
break; }
95 fib2bin_0_95[(p << 12) | x] = w;
114 template <
bool t_sumup,
bool t_inc,
class t_iter>
117 template <
bool t_sumup,
bool t_inc,
class t_iter>
121 t_iter it = (t_iter)
nullptr);
141 template <
class int_vector1,
class int_vector2>
142 static bool encode(
const int_vector1 & v, int_vector2 & z);
144 template <
class int_vector>
155 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
157 template <
class int_vector1,
class int_vector2>
158 static bool decode(
const int_vector1 & z, int_vector2 & v);
161 template <
typename T>
164 if (w == 0) {
return 93; }
172 template <
typename T>
173 template <
class int_vector1,
class int_vector2>
176 uint64_t z_bit_size = 0;
178 const uint64_t zero_val = v.width() < 64 ? (1ULL) << v.width() : 0;
179 for (
typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
183 if (v.width() < 64) { w = zero_val; }
185 z_bit_size += encoding_length(w);
187 z.bit_resize(z_bit_size);
189 if (z_bit_size & 0x3F)
191 *(z.m_data + (z_bit_size >> 6)) = 0;
193 uint64_t * z_data = z.m_data;
195 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
197 for (
typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
200 if (w == 0) { w = zero_val; }
201 int8_t len_1 = encoding_length(w) - 1, j;
202 fibword_low = 0x0000000000000001ULL;
206 fibword_high = 0x0000000000000001ULL;
230 fibword_high <<= (64 - j);
275 template <
typename T>
278 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
280 int8_t len_1 = encoding_length(x) - 1, j;
281 fibword_low = 0x0000000000000001ULL;
285 fibword_high = 0x0000000000000001ULL;
309 fibword_high <<= (64 - j);
350 template <
typename T>
351 template <
class int_vector1,
class int_vector2>
354 uint64_t n = 0, carry = 0;
355 const uint64_t * data = z.data();
368 if (z.bit_data_size() << 6 != z.bit_size())
379 return decode<false, true>(z.data(), 0, n, v.begin());
382 template <
typename T>
383 template <
bool t_sumup,
bool t_inc,
class t_iter>
386 data += (start_idx >> 6);
387 uint64_t w = 0, value = 0;
389 int8_t read = start_idx & 0x3F;
391 uint32_t fibtable = 0;
396 w |= (((*data) >> read) << buffered);
397 if (read >= buffered)
400 buffered += 64 - read;
405 read += 64 - buffered;
415 if (t_inc) *(it++) = value;
416 if (!t_sumup and n != 1) value = 0;
430 template <
typename T>
431 template <
bool t_sumup,
bool t_inc,
class t_iter>
434 d += (start_idx >> 6);
435 uint64_t w = 0, value = 0;
437 int8_t read = start_idx & 0x3F;
439 uint32_t fibtable = 0;
440 uint8_t blocknr = (start_idx >> 6) % 9;
445 w |= (((*d) >> read) << buffered);
446 if (read >= buffered)
455 buffered += 64 - read;
460 read += 64 - buffered;
470 if (t_inc) *(it++) = value;
471 if (!t_sumup) value = 0;
485 template <
typename T>
488 if (n == 0)
return 0;
490 d += (start_idx >> 6);
492 int32_t bits_to_decode = 0;
493 uint64_t w = 0, value = 0;
494 int16_t buffered = 0, read = start_idx & 0x3F, shift = 0;
506 bits_to_decode += ((w - 1) << 6) +
bits::sel11(*(d + w), n - (i - temp), oldcarry) + 65 - read;
513 if (((
size_type)bits_to_decode) == n << 1)
return n;
514 if (((
size_type)bits_to_decode) == (n << 1) + 1)
return n + 1;
518 while (buffered < 64 and bits_to_decode > 0)
520 w |= (((*d) >> read) << buffered);
521 if (read >= buffered)
524 buffered += 64 - read;
525 bits_to_decode -= (64 - read);
530 read += 64 - buffered;
531 bits_to_decode -= (64 - buffered);
534 if (bits_to_decode < 0)
536 buffered += bits_to_decode;
543 if ((w & 0xFFFFFF) == 0xFFFFFF)
548 if ((w & 0xFFFFFF) == 0xFFFFFF)
557 if ((shift = (temp >> 11)) > 0)
559 value += (temp & 0x7FFULL);
571 }
while (buffered > 15);
590 }
while (bits_to_decode > 0 or buffered > 0);
594 template <
typename T>
600 return decode_prefix_sum(d, start_idx, n);
603 template <
typename T>
A class to encode and decode between Fibonacci and binary code.
static uint64_t decode(const uint64_t *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
Decode n Fibonacci encoded bits beginning at start_idx in the bitstring "data".
static uint64_t decode_prefix_sum(const uint64_t *d, const size_type start_idx, size_type n)
Decode n Fibonacci encoded integers beginning at start_idx in the bitstring "data" and return the sum...
static uint64_t decode_prefix_sum(const uint64_t *d, const size_type start_idx, const size_type end_idx, size_type n)
Decode n Fibonacci encoded integers beginning at start_idx and ending at end_idx (exclusive) in the b...
static uint64_t decode1(const uint64_t *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
static struct sdsl::coder::fibonacci::impl data
static bool encode(const int_vector1 &v, int_vector2 &z)
static const uint8_t min_codeword_length
static uint8_t encoding_length(uint64_t w)
Get the number of bits that are necessary to encode the value w in Fibonacci code.
static uint64_t * raw_data(int_vector &v)
A generic vector class for integers of width .
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
constexpr static uint64_t lt_fib[92]
Array containing Fibonacci numbers less than .
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.
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...
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.
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.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.