8#ifndef SDSL_CODER_ELIAS_DELTA
9#define SDSL_CODER_ELIAS_DELTA
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_len + 1;
62 if (offset2 + len - 1 <= 16)
65 offset = offset2 + len - 1;
75 result = (offset << 24) | (numbers << 16) | value;
77 assert(offset > 0 and numbers > 0 and offset <= 16 and numbers <= 16);
78 prefixsum[x] = result;
82 for (uint32_t maxi = 1, idx = 0; maxi <= 8; ++maxi)
84 for (uint64_t x = 0; x < (1 << 8); ++x)
86 uint64_t
const * w = &x;
88 uint32_t numbers = 0, offset = 0, offset2 = 0;
89 while ((x >> offset) != 0 and numbers < maxi)
100 offset2 = offset + len_1_len + 1;
102 offset2 += len_1_len;
103 if (offset2 + len - 1 <= 8)
106 offset = offset2 + len - 1;
116 result = (offset << 8) | (numbers << 4) | value;
117 prefixsum_8bit[idx++] = result;
131 template <
bool t_sumup,
bool t_inc,
class t_iter>
145 template <
class int_vector>
147 template <
class int_vector>
155 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
157 template <
class int_vector>
168 uint8_t len_1 = w ?
bits::hi(w) : 64;
169 return len_1 + (
bits::hi(len_1 + 1) << 1) + 1;
173template <
class int_vector>
180 const uint64_t zero_val = v.
width() < 64 ? (1ULL) << v.
width() : 0;
187 z_bit_size += encoding_length(w);
189 z.bit_resize(z_bit_size);
191 if (z_bit_size & 0x3F)
193 *(z.m_data + (z_bit_size >> 6)) = 0;
196 uint64_t * z_data = z.m_data;
224 uint8_t len, len_1_len;
244 uint64_t
const * lastdata = d + ((end_idx + 63) >> 6);
245 d += (start_idx >> 6);
246 uint64_t w = 0, value = 0;
247 int16_t buffered = 0, read = start_idx & 0x3F;
264 if (*d == 0xFFFFFFFFFFFFFFFFULL)
282 while (buffered < 64 and d < lastdata)
285 w |= (((*d) >> read) << buffered);
286 if (read >= buffered)
289 buffered += 64 - read;
294 read += 64 - buffered;
317 return value - (i - n);
319 assert((int64_t)buffered >= rbp);
332 if (!psum or i + ((psum >> 16) & 0x00FF) > n)
336 w |= (((*d) >> read) << buffered);
337 if (read >= buffered)
340 buffered += 64 - read;
345 read += 64 - buffered;
350 w |= (((*d) >> read) << buffered);
351 if (read >= buffered)
354 buffered += 64 - read;
359 read += 64 - buffered;
366 buffered -= (len_1_len + 1);
367 w >>= (len_1_len + 1);
368 if (len_1_len > buffered)
370 w |= (((*d) >> read) << buffered);
371 if (read >= buffered)
374 buffered += 64 - read;
379 read += 64 - buffered;
382 if (len_1_len > buffered)
384 w |= (((*d) >> read) << buffered);
385 if (read >= buffered)
388 buffered += 64 - read;
393 read += 64 - buffered;
399 uint16_t len_1 = (w &
bits::lo_set[len_1_len]) + (1ULL << len_1_len) - 1;
400 buffered -= len_1_len;
402 if (len_1 > buffered)
404 w |= (((*d) >> read) << buffered);
405 if (read >= buffered)
408 buffered += 64 - read;
413 read += 64 - buffered;
416 if (len_1 > buffered)
418 w |= (((*d) >> read) << buffered);
419 if (read >= buffered)
422 buffered += 64 - read;
427 read += 64 - buffered;
436 value += (w &
bits::lo_set[len_1]) + (len_1 < 64) * (1ULL << (len_1));
454 value += (psum & 0x0000FFFF);
455 i += ((psum >> 16) & 0x00FF);
458 buffered -= (psum >> 24);
475 d += (start_idx >> 6);
478 uint8_t offset = start_idx & 0x3F;
482 if (n + offset <= 64)
497 if (*d == 0xFFFFFFFFFFFFFFFFULL)
524 if (((*d >> offset) & 0xF) == 0xF)
526 uint8_t maxdecode = n - i > 63 ? 63 : n - i;
530 if (rbp + offset >= 64)
533 offset = (rbp + offset) & 0x3F;
539 if (rbp == maxdecode)
550 else if (i + ((psum >> 16) & 0x00FF) > n)
557 value += (psum & 0xF);
558 i += ((psum >> 4) & 0xF);
559 offset += (psum >> 8);
571 value += (psum & 0x0000FFFF);
572 i += ((psum >> 16) & 0x00FF);
573 offset += (psum >> 24);
595template <
class int_vector>
599 uint64_t
const * z_data = z.
data();
600 uint64_t
const * z_end = z.
data() + (z.
bit_size() >> 6);
602 while ((z_data < z_end) or (z_data == z_end and offset < (z.
bit_size() & 0x3F)))
615 return decode<false, true>(z.
data(), 0, n, v.
begin());
619template <
bool t_sumup,
bool t_inc,
class t_iter>
622 d += (start_idx >> 6);
626 uint8_t offset = start_idx & 0x3F;
bits.hpp contains the sdsl::bits class.
A class to encode and decode between Elias- and binary code.
static struct sdsl::coder::elias_delta::impl data
static const uint8_t min_codeword_length
static uint8_t encoding_length(uint64_t)
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 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 delta encoded integers beginning at start_idx in the bitstring "data" and return the s...
static bool encode(int_vector const &v, int_vector &z)
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
void shrink_to_fit()
Free unused allocated memory.
void resize(const size_type size)
Resize the int_vector in terms of elements.
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
size_type bit_size() const noexcept
The number of bits in the int_vector.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
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 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.
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.