8#ifndef SDSL_CODER_ELIAS_GAMMA
9#define SDSL_CODER_ELIAS_GAMMA
23template <
typename T =
void>
36 uint32_t prefixsum[1 << 16];
38 uint16_t prefixsum_8bit[(1 << 8) * 8];
43 for (uint64_t x = 0; x < (1 << 16); ++x)
45 uint64_t
const * w = &x;
47 uint16_t numbers = 0, offset = 0, offset2 = 0;
48 while ((x >> offset) != 0)
59 offset2 = offset + len_1 + 1;
60 if (offset2 + len_1 <= 16)
63 offset = offset2 + len_1;
73 result = (offset << 24) | (numbers << 16) | value;
75 assert(offset > 0 and numbers > 0 and offset <= 16 and numbers <= 16);
76 prefixsum[x] = result;
80 for (uint32_t maxi = 1, idx = 0; maxi <= 8; ++maxi)
82 for (uint64_t x = 0; x < (1 << 8); ++x)
84 uint64_t
const * w = &x;
86 uint32_t numbers = 0, offset = 0, offset2 = 0;
87 while ((x >> offset) != 0 and numbers < maxi)
98 offset2 = offset + len_1 + 1;
99 if (offset2 + len_1 <= 8)
102 offset = offset2 + len_1;
112 result = (offset << 12) | (numbers << 8) | value;
113 prefixsum_8bit[idx++] = result;
127 template <
bool t_sumup,
bool t_inc,
class t_iter>
141 template <
class int_vector>
143 template <
class int_vector>
151 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
153 template <
class int_vector>
164 uint8_t len_1 = w ?
bits::hi(w) : 64;
165 return 2 * len_1 + 1;
169template <
class int_vector>
176 const uint64_t zero_val = v.
width() < 64 ? (1ULL) << v.
width() : 0;
185 z.bit_resize(z_bit_size);
187 if (z_bit_size & 0x3F)
189 *(z.m_data + (z_bit_size >> 6)) = 0;
192 uint64_t * z_data = z.m_data;
244template <
class int_vector>
248 uint64_t
const * z_data = z.
data();
249 uint64_t
const * z_end = z.
data() + (z.
bit_size() >> 6);
251 while ((z_data < z_end) or (z_data == z_end and offset < (z.
bit_size() & 0x3F)))
267template <
bool t_sumup,
bool t_inc,
class t_iter>
270 d += (start_idx >> 6);
274 uint8_t offset = start_idx & 0x3F;
300 uint64_t
const * lastdata = d + ((end_idx + 63) >> 6);
301 d += (start_idx >> 6);
302 uint64_t w = 0, value = 0;
303 int16_t buffered = 0, read = start_idx & 0x3F;
320 if (*d == 0xFFFFFFFFFFFFFFFFULL)
338 while (buffered < 64 and d < lastdata)
341 w |= (((*d) >> read) << buffered);
342 if (read >= buffered)
345 buffered += 64 - read;
350 read += 64 - buffered;
361 return value - (i - n);
363 assert((int64_t)buffered >= rbp);
373 if (!psum or i + ((psum >> 16) & 0x00FF) > n)
377 w |= (((*d) >> read) << buffered);
378 if (read >= buffered)
381 buffered += 64 - read;
386 read += 64 - buffered;
391 w |= (((*d) >> read) << buffered);
392 if (read >= buffered)
395 buffered += 64 - read;
400 read += 64 - buffered;
407 buffered -= (len_1 + 1);
409 if (len_1 > buffered)
411 w |= (((*d) >> read) << buffered);
412 if (read >= buffered)
415 buffered += 64 - read;
420 read += 64 - buffered;
423 if (len_1 > buffered)
425 w |= (((*d) >> read) << buffered);
426 if (read >= buffered)
429 buffered += 64 - read;
434 read += 64 - buffered;
439 value += (w &
bits::lo_set[len_1]) + (len_1 < 64) * (1ULL << len_1);
457 value += (psum & 0x0000FFFF);
458 i += ((psum >> 16) & 0x00FF);
461 buffered -= (psum >> 24);
476 d += (start_idx >> 6);
479 uint8_t offset = start_idx & 0x3F;
483 if (n + offset <= 64)
498 if (*d == 0xFFFFFFFFFFFFFFFFULL)
525 if (((*d >> offset) & 0xF) == 0xF)
527 uint8_t maxdecode = n - i > 63 ? 63 : n - i;
531 if (rbp + offset >= 64)
534 offset = (rbp + offset) & 0x3F;
540 if (rbp == maxdecode)
551 else if (i + ((psum >> 16) & 0x00FF) > n)
558 value += (psum & 0xFF);
559 i += ((psum >> 8) & 0xF);
560 offset += (psum >> 12);
572 value += (psum & 0x0000FFFF);
573 i += ((psum >> 16) & 0x00FF);
574 offset += (psum >> 24);
bits.hpp contains the sdsl::bits class.
A class to encode and decode between Elias- and binary code.
static bool encode(int_vector const &v, int_vector &z)
static uint64_t decode(uint64_t const *data, const size_type start_idx, size_type n, t_iter it=(t_iter) nullptr)
Decode n Elias-delta encoded bits beginning at start_idx in the bitstring "data".
static struct sdsl::coder::elias_gamma::impl data
static uint64_t * raw_data(int_vector &v)
static uint64_t decode_prefix_sum(uint64_t const *d, const size_type start_idx, size_type n)
Decode n Elias gamma encoded integers beginning at start_idx in the bitstring "data" and return the s...
static uint8_t encoding_length(uint64_t)
static const uint8_t min_codeword_length
A generic vector class for integers of width .
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
int_vector_size_type size_type
size_type bit_size() const noexcept
The number of bits in the int_vector.
int_vector_trait< t_width >::const_iterator const_iterator
void shrink_to_fit()
Free unused allocated memory.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
void resize(const size_type size)
Resize the int_vector in terms of elements.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
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 read_int_bounded(uint64_t const *word, uint8_t offset=0, const uint8_t len=64)
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 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.
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.
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
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 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.
static constexpr uint64_t read_unary_bounded(uint64_t const *word, uint8_t offset=0)
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.