8#ifndef SDSL_CODER_FIBONACCI_INCLUDED
9#define SDSL_CODER_FIBONACCI_INCLUDED
23template <
typename T =
void>
29 uint64_t fib12bit_to_bin[(1 << 12) * 8];
36 uint8_t fib2bin_shift[(1 << 13)];
43 uint16_t fib2bin_16_greedy[(1 << 16)];
46 uint64_t fib2bin_0_95[(1 << 12) * 8];
50 for (uint32_t x = 0; x <= 0x1FFF; ++x)
61 for (uint32_t x = 0; x < 1 << 16; ++x)
88 fib2bin_16_greedy[x] = (offset << 11) | w;
90 for (uint32_t p = 0; p < 8; ++p)
92 for (uint32_t x = 0; x <= 0xFFF; ++x)
95 for (uint32_t j = 0; j < 12 and 12 * p + j < 92; ++j)
100 if (x >> (j + 1) & 1ULL)
106 fib2bin_0_95[(p << 12) | x] = w;
125 template <
bool t_sumup,
bool t_inc,
class t_iter>
128 template <
bool t_sumup,
bool t_inc,
class t_iter>
148 template <
class int_vector1,
class int_vector2>
149 static bool encode(int_vector1
const & v, int_vector2 & z);
151 template <
class int_vector>
162 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
164 template <
class int_vector1,
class int_vector2>
165 static bool decode(int_vector1
const & z, int_vector2 & v);
183template <
class int_vector1,
class int_vector2>
186 uint64_t z_bit_size = 0;
188 const uint64_t zero_val = v.width() < 64 ? (1ULL) << v.width() : 0;
189 for (
typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
200 z.bit_resize(z_bit_size);
202 if (z_bit_size & 0x3F)
204 *(z.m_data + (z_bit_size >> 6)) = 0;
206 uint64_t * z_data = z.m_data;
208 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
210 for (
typename int_vector1::const_iterator it = v.begin(), end = v.end(); it != end; ++it)
218 fibword_low = 0x0000000000000001ULL;
222 fibword_high = 0x0000000000000001ULL;
246 fibword_high <<= (64 - j);
294 uint64_t fibword_high = 0x0000000000000001ULL, fibword_low;
297 fibword_low = 0x0000000000000001ULL;
301 fibword_high = 0x0000000000000001ULL;
325 fibword_high <<= (64 - j);
367template <
class int_vector1,
class int_vector2>
370 uint64_t n = 0, carry = 0;
371 uint64_t
const *
data = z.data();
380 for (
typename int_vector1::size_type i = 0; i < z.bit_data_size() - 1; ++i, ++
data)
384 if (z.bit_data_size() << 6 != z.bit_size())
399template <
bool t_sumup,
bool t_inc,
class t_iter>
402 data += (start_idx >> 6);
403 uint64_t w = 0, value = 0;
405 int8_t read = start_idx & 0x3F;
407 uint32_t fibtable = 0;
412 w |= (((*data) >> read) << buffered);
413 if (read >= buffered)
416 buffered += 64 - read;
421 read += 64 - buffered;
433 if (!t_sumup and n != 1)
449template <
bool t_sumup,
bool t_inc,
class t_iter>
452 d += (start_idx >> 6);
453 uint64_t w = 0, value = 0;
455 int8_t read = start_idx & 0x3F;
457 uint32_t fibtable = 0;
458 uint8_t blocknr = (start_idx >> 6) % 9;
463 w |= (((*d) >> read) << buffered);
464 if (read >= buffered)
473 buffered += 64 - read;
478 read += 64 - buffered;
511 d += (start_idx >> 6);
513 int32_t bits_to_decode = 0;
514 uint64_t w = 0, value = 0;
515 int16_t buffered = 0, read = start_idx & 0x3F, shift = 0;
529 bits_to_decode += ((w - 1) << 6) +
bits::sel11(*(d + w), n - (i - temp), oldcarry) + 65 - read;
536 if (((
size_type)bits_to_decode) == n << 1)
538 if (((
size_type)bits_to_decode) == (n << 1) + 1)
544 while (buffered < 64 and bits_to_decode > 0)
546 w |= (((*d) >> read) << buffered);
547 if (read >= buffered)
550 buffered += 64 - read;
551 bits_to_decode -= (64 - read);
556 read += 64 - buffered;
557 bits_to_decode -= (64 - buffered);
560 if (bits_to_decode < 0)
562 buffered += bits_to_decode;
569 if ((w & 0xFFFFFF) == 0xFFFFFF)
574 if ((w & 0xFFFFFF) == 0xFFFFFF)
584 if ((shift = (temp >> 11)) > 0)
586 value += (temp & 0x7FFULL);
599 while (buffered > 15);
619 while (bits_to_decode > 0 or buffered > 0);
629 return decode_prefix_sum(d, start_idx, n);
bits.hpp contains the sdsl::bits class.
A class to encode and decode between Fibonacci and binary code.
static uint64_t * raw_data(int_vector &v)
static uint64_t decode(uint64_t const *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 bool encode(int_vector1 const &v, int_vector2 &z)
static struct sdsl::coder::fibonacci::impl data
static uint64_t decode1(uint64_t const *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
static const uint8_t min_codeword_length
static uint64_t decode_prefix_sum(uint64_t const *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 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 decode_prefix_sum(uint64_t const *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...
A generic vector class for integers of width .
Namespace for the different coder of the sdsl.
comma< t_width >::impl comma< t_width >::data
Namespace for the succinct data structure library.
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.
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...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static constexpr uint64_t lt_fib[92]
Array containing Fibonacci numbers less than .
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.
static constexpr uint32_t cnt11(uint64_t x, uint64_t &c)
Count the number of consecutive and distinct 11 in the 64bit integer x.