8#ifndef SDSL_CODER_ELIAS_DELTA
9#define SDSL_CODER_ELIAS_DELTA
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_len + 1;
59 if (offset2 + len - 1 <= 16)
62 offset = offset2 + len - 1;
72 result = (offset << 24) | (numbers << 16) | value;
73 if (value > 0) assert(offset > 0 and numbers > 0 and offset <= 16 and numbers <= 16);
74 prefixsum[x] = result;
78 for (uint32_t maxi = 1, idx = 0; maxi <= 8; ++maxi)
80 for (uint64_t x = 0; x < (1 << 8); ++x)
82 const uint64_t * w = &x;
84 uint32_t numbers = 0, offset = 0, offset2 = 0;
85 while ((x >> offset) != 0 and numbers < maxi)
96 offset2 = offset + len_1_len + 1;
99 if (offset2 + len - 1 <= 8)
102 offset = offset2 + len - 1;
112 result = (offset << 8) | (numbers << 4) | value;
113 prefixsum_8bit[idx++] = result;
127 template <
bool t_sumup,
bool t_inc,
class t_iter>
143 template <
class int_vector>
145 template <
class int_vector>
153 static void encode(uint64_t x, uint64_t *& z, uint8_t & offset);
155 template <
class int_vector>
166 uint8_t len_1 = w ?
bits::hi(w) : 64;
167 return len_1 + (
bits::hi(len_1 + 1) << 1) + 1;
171template <
class int_vector>
178 const uint64_t zero_val = v.
width() < 64 ? (1ULL) << v.
width() : 0;
181 if ((w = *it) == 0) { w = zero_val; }
182 z_bit_size += encoding_length(w);
184 z.bit_resize(z_bit_size);
186 if (z_bit_size & 0x3F)
188 *(z.m_data + (z_bit_size >> 6)) = 0;
191 uint64_t * z_data = z.m_data;
197 if (w == 0) { w = zero_val; }
216 uint8_t len, len_1_len;
236 if (n == 0)
return 0;
237 const uint64_t * lastdata = d + ((end_idx + 63) >> 6);
238 d += (start_idx >> 6);
239 uint64_t w = 0, value = 0;
240 int16_t buffered = 0, read = start_idx & 0x3F;
256 if (*d == 0xFFFFFFFFFFFFFFFFULL)
273 while (buffered < 64 and d < lastdata)
276 w |= (((*d) >> read) << buffered);
277 if (read >= buffered)
280 buffered += 64 - read;
285 read += 64 - buffered;
308 return value - (i - n);
310 assert((int64_t)buffered >= rbp);
323 if (!psum or i + ((psum >> 16) & 0x00FF) > n)
327 w |= (((*d) >> read) << buffered);
328 if (read >= buffered)
331 buffered += 64 - read;
336 read += 64 - buffered;
341 w |= (((*d) >> read) << buffered);
342 if (read >= buffered)
345 buffered += 64 - read;
350 read += 64 - buffered;
357 buffered -= (len_1_len + 1);
358 w >>= (len_1_len + 1);
359 if (len_1_len > buffered)
361 w |= (((*d) >> read) << buffered);
362 if (read >= buffered)
365 buffered += 64 - read;
370 read += 64 - buffered;
373 if (len_1_len > buffered)
375 w |= (((*d) >> read) << buffered);
376 if (read >= buffered)
379 buffered += 64 - read;
384 read += 64 - buffered;
390 uint16_t len_1 = (w &
bits::lo_set[len_1_len]) + (1ULL << len_1_len) - 1;
391 buffered -= len_1_len;
393 if (len_1 > buffered)
395 w |= (((*d) >> read) << buffered);
396 if (read >= buffered)
399 buffered += 64 - read;
404 read += 64 - buffered;
407 if (len_1 > buffered)
409 w |= (((*d) >> read) << buffered);
410 if (read >= buffered)
413 buffered += 64 - read;
418 read += 64 - buffered;
427 value += (w &
bits::lo_set[len_1]) + (len_1 < 64) * (1ULL << (len_1));
429 if (len_1 < 64) { w >>= len_1; }
435 if (i == n)
return value;
436 if (buffered >= 16)
goto begin_decode;
440 value += (psum & 0x0000FFFF);
441 i += ((psum >> 16) & 0x00FF);
442 if (i == n)
return value;
443 buffered -= (psum >> 24);
445 if (buffered >= 16)
goto begin_decode;
457 if (n == 0)
return 0;
458 d += (start_idx >> 6);
461 uint8_t offset = start_idx & 0x3F;
465 if (n + offset <= 64)
479 if (*d == 0xFFFFFFFFFFFFFFFFULL)
505 if (((*d >> offset) & 0xF) == 0xF)
507 uint8_t maxdecode = n - i > 63 ? 63 : n - i;
511 if (rbp + offset >= 64)
514 offset = (rbp + offset) & 0x3F;
520 if (rbp == maxdecode)
continue;
530 else if (i + ((psum >> 16) & 0x00FF) > n)
537 value += (psum & 0xF);
538 i += ((psum >> 4) & 0xF);
539 offset += (psum >> 8);
551 value += (psum & 0x0000FFFF);
552 i += ((psum >> 16) & 0x00FF);
553 offset += (psum >> 24);
575template <
class int_vector>
579 const uint64_t * z_data = z.
data();
580 const uint64_t * z_end = z.
data() + (z.
bit_size() >> 6);
582 while ((z_data < z_end) or (z_data == z_end and offset < (z.
bit_size() & 0x3F)))
595 return decode<false, true>(z.
data(), 0, n, v.
begin());
599template <
bool t_sumup,
bool t_inc,
class t_iter>
602 d += (start_idx >> 6);
606 uint8_t offset = start_idx & 0x3F;
609 if (!t_sumup) value = 0;
611 if (!len_1_len) { value += 1; }
617 if (t_inc) *(it++) = value;
A class to encode and decode between Elias- and binary code.
static bool encode(const int_vector &v, int_vector &z)
static uint64_t decode_prefix_sum(const uint64_t *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 struct sdsl::coder::elias_delta::impl data
static const uint8_t min_codeword_length
static uint8_t encoding_length(uint64_t)
static uint64_t * raw_data(int_vector &v)
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.
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.