8#ifndef SDSL_CODER_ELIAS_GAMMA
9#define SDSL_CODER_ELIAS_GAMMA
20template <
typename T =
void>
33 uint32_t prefixsum[1 << 16];
35 uint16_t prefixsum_8bit[(1 << 8) * 8];
40 for (uint64_t x = 0; x < (1 << 16); ++x)
42 const uint64_t * w = &x;
44 uint16_t numbers = 0, offset = 0, offset2 = 0;
45 while ((x >> offset) != 0)
56 offset2 = offset + len_1 + 1;
57 if (offset2 + len_1 <= 16)
60 offset = offset2 + len_1;
70 result = (offset << 24) | (numbers << 16) | value;
71 if (value > 0) assert(offset > 0 and numbers > 0 and offset <= 16 and numbers <= 16);
72 prefixsum[x] = result;
76 for (uint32_t maxi = 1, idx = 0; maxi <= 8; ++maxi)
78 for (uint64_t x = 0; x < (1 << 8); ++x)
80 const uint64_t * w = &x;
82 uint32_t numbers = 0, offset = 0, offset2 = 0;
83 while ((x >> offset) != 0 and numbers < maxi)
94 offset2 = offset + len_1 + 1;
95 if (offset2 + len_1 <= 8)
98 offset = offset2 + len_1;
108 result = (offset << 12) | (numbers << 8) | value;
109 prefixsum_8bit[idx++] = result;
123 template <
bool t_sumup,
bool t_inc,
class t_iter>
139 template <
class int_vector>
141 template <
class int_vector>
149 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
151 template <
class int_vector>
162 uint8_t len_1 = w ?
bits::hi(w) : 64;
163 return 2 * len_1 + 1;
167template <
class int_vector>
174 const uint64_t zero_val = v.
width() < 64 ? (1ULL) << v.
width() : 0;
177 if ((w = *it) == 0) { w = zero_val; }
178 z_bit_size += encoding_length(w);
180 z.bit_resize(z_bit_size);
182 if (z_bit_size & 0x3F)
184 *(z.m_data + (z_bit_size >> 6)) = 0;
187 uint64_t * z_data = z.m_data;
193 if (w == 0) { w = zero_val; }
230template <
class int_vector>
234 const uint64_t * z_data = z.
data();
235 const uint64_t * z_end = z.
data() + (z.
bit_size() >> 6);
237 while ((z_data < z_end) or (z_data == z_end and offset < (z.
bit_size() & 0x3F)))
246 return decode<false, true>(z.
data(), 0, n, v.
begin());
250template <
bool t_sumup,
bool t_inc,
class t_iter>
253 d += (start_idx >> 6);
257 uint8_t offset = start_idx & 0x3F;
260 if (!t_sumup) value = 0;
262 if (!len_1) { value += 1; }
267 if (t_inc) *(it++) = value;
278 if (n == 0)
return 0;
279 const uint64_t * lastdata = d + ((end_idx + 63) >> 6);
280 d += (start_idx >> 6);
281 uint64_t w = 0, value = 0;
282 int16_t buffered = 0, read = start_idx & 0x3F;
298 if (*d == 0xFFFFFFFFFFFFFFFFULL)
315 while (buffered < 64 and d < lastdata)
318 w |= (((*d) >> read) << buffered);
319 if (read >= buffered)
322 buffered += 64 - read;
327 read += 64 - buffered;
338 return value - (i - n);
340 assert((int64_t)buffered >= rbp);
343 if (buffered < 16)
goto fill_buffer;
349 if (!psum or i + ((psum >> 16) & 0x00FF) > n)
353 w |= (((*d) >> read) << buffered);
354 if (read >= buffered)
357 buffered += 64 - read;
362 read += 64 - buffered;
367 w |= (((*d) >> read) << buffered);
368 if (read >= buffered)
371 buffered += 64 - read;
376 read += 64 - buffered;
383 buffered -= (len_1 + 1);
385 if (len_1 > buffered)
387 w |= (((*d) >> read) << buffered);
388 if (read >= buffered)
391 buffered += 64 - read;
396 read += 64 - buffered;
399 if (len_1 > buffered)
401 w |= (((*d) >> read) << buffered);
402 if (read >= buffered)
405 buffered += 64 - read;
410 read += 64 - buffered;
415 value += (w &
bits::lo_set[len_1]) + (len_1 < 64) * (1ULL << len_1);
417 if (len_1 < 64) { w >>= len_1; }
423 if (i == n)
return value;
424 if (buffered >= 16)
goto begin_decode;
428 value += (psum & 0x0000FFFF);
429 i += ((psum >> 16) & 0x00FF);
430 if (i == n)
return value;
431 buffered -= (psum >> 24);
433 if (buffered >= 16)
goto begin_decode;
443 if (n == 0)
return 0;
444 d += (start_idx >> 6);
447 uint8_t offset = start_idx & 0x3F;
451 if (n + offset <= 64)
465 if (*d == 0xFFFFFFFFFFFFFFFFULL)
491 if (((*d >> offset) & 0xF) == 0xF)
493 uint8_t maxdecode = n - i > 63 ? 63 : n - i;
497 if (rbp + offset >= 64)
500 offset = (rbp + offset) & 0x3F;
506 if (rbp == maxdecode)
continue;
516 else if (i + ((psum >> 16) & 0x00FF) > n)
523 value += (psum & 0xFF);
524 i += ((psum >> 8) & 0xF);
525 offset += (psum >> 12);
537 value += (psum & 0x0000FFFF);
538 i += ((psum >> 16) & 0x00FF);
539 offset += (psum >> 24);
A class to encode and decode between Elias- and binary code.
static bool encode(const int_vector &v, int_vector &z)
static struct sdsl::coder::elias_gamma::impl data
static uint64_t * raw_data(int_vector &v)
static uint64_t decode_prefix_sum(const uint64_t *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
static uint64_t decode(const uint64_t *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".
A generic vector class for integers of width .
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.
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.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
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.
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
static constexpr uint64_t read_int(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
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_bounded(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
static constexpr uint64_t read_unary_and_move(const uint64_t *&word, uint8_t &offset)
Reads an unary decoded value from a bit position in an array and moves the bit-pointer.
static constexpr uint64_t read_unary_bounded(const uint64_t *word, uint8_t offset=0)
static constexpr uint64_t read_int_and_move(const uint64_t *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.
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(const uint64_t *&word, uint8_t &offset, const uint8_t len)
Move the bit-pointer (=uint64_t word and offset) len to the right.