-
-#include <assert.h>
-#include <endian.h>
-#include <stdint.h>
-#include <string.h>
-#include <limits.h>
-
-#include <algorithm>
-
-template<class Docid>
-Docid read_le(const void *in)
-{
- Docid val;
- memcpy(&val, in, sizeof(val));
- if constexpr (sizeof(Docid) == 8) {
- return le64toh(val);
- } else if constexpr (sizeof(Docid) == 4) {
- return le32toh(val);
- } else if constexpr (sizeof(Docid) == 2) {
- return le16toh(val);
- } else if constexpr (sizeof(Docid) == 1) {
- return val;
- } else {
- assert(false);
- }
-}
-
-// Reads a single value with an encoding that looks a bit like PrefixVarint.
-// It's unclear why this doesn't use the varbyte encoding.
-template<class Docid>
-const unsigned char *read_baseval(const unsigned char *in, Docid *out)
-{
- //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
- if (*in < 128) {
- *out = *in;
- return in + 1;
- } else if (*in < 192) {
- *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
- return in + 2;
- } else if (*in < 224) {
- *out = ((uint32_t(in[0]) << 16) |
- (uint32_t(in[2]) << 8) |
- (uint32_t(in[1]))) & 0x1fffff;
- return in + 3;
- } else {
- assert(false); // Not implemented.
- }
-}
-
-template<class Docid>
-const unsigned char *read_vb(const unsigned char *in, Docid *out)
-{
- if (*in <= 176) {
- *out = *in;
- return in + 1;
- } else if (*in <= 240) {
- *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
- return in + 2;
- } else if (*in <= 248) {
- *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
- return in + 3;
- } else if (*in == 249) {
- *out = (uint32_t(in[1])) |
- (uint32_t(in[2]) << 8) |
- (uint32_t(in[3]) << 16);
- return in + 4;
- } else if (*in == 250) {
- *out = read_le<uint32_t>(in + 1);
- return in + 5;
- } else {
- assert(false);
- }
-}
-
-struct BitReader {
-public:
- BitReader(const unsigned char *in, unsigned bits)
- : in(in), bits(bits), mask((1U << bits) - 1) {}
- uint32_t read()
- {
- uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
-
- bits_used += bits;
- in += bits_used / 8;
- bits_used %= 8;
-
- return val;
- }
-
-private:
- const unsigned char *in;
- const unsigned bits;
- const unsigned mask;
- unsigned bits_used = 0;
-};
-
-template<unsigned NumStreams>
-struct InterleavedBitReader {
-public:
- InterleavedBitReader(const unsigned char *in, unsigned bits)
- : in(in), bits(bits), mask((1U << bits) - 1) {}
- uint32_t read()
- {
- uint32_t val;
- if (bits_used + bits > 32) {
- val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
- } else {
- val = (read_le<uint32_t>(in) >> bits_used);
- }
-
- bits_used += bits;
- in += Stride * (bits_used / 32);
- bits_used %= 32;
-
- return val & mask;
- }
-
-private:
- static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
- const unsigned char *in;
- const unsigned bits;
- const unsigned mask;
- unsigned bits_used = 0;
-};
-
-// Does not properly account for overflow.
-inline unsigned div_round_up(unsigned val, unsigned div)
-{
- return (val + div - 1) / div;
-}
-
-inline unsigned bytes_for_packed_bits(unsigned num, unsigned bit_width)
-{
- return div_round_up(num * bit_width, CHAR_BIT);
-}
-
-// Constant block. Layout:
-//
-// - Bit width (6 bits) | type << 6
-// - Base values (<bits> bits, rounded up to nearest byte)
-template<class Docid>
-const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
-{
- const unsigned bit_width = *in++ & 0x3f;
- Docid val = read_le<Docid>(in);
- if (bit_width < sizeof(Docid) * 8) {
- val &= ((1U << bit_width) - 1);
- }
-
- Docid prev_val = out[-1];
- for (unsigned i = 0; i < num; ++i) {
- out[i] = prev_val = val + prev_val + 1;
- }
- return in + div_round_up(bit_width, 8);
-}
-
-// FOR block (ie., PFor without exceptions). Layout:
-//
-// - Bit width (6 bits) | type << 6
-// - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
-template<class Docid>
-const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
-{
- const unsigned bit_width = *in++ & 0x3f;
-
- Docid prev_val = out[-1];
- BitReader bs(in, bit_width);
- for (unsigned i = 0; i < num; ++i) {
- prev_val = out[i] = bs.read() + prev_val + 1;
- }
- return in + bytes_for_packed_bits(num, bit_width);
-}
-
-// Like decode_for(), but the values are organized in four independent streams,
-// for SIMD (presumably SSE2). Supports a whole block only.
-template<unsigned BlockSize, class Docid>
-const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
-{
- const unsigned bit_width = *in++ & 0x3f;
-
- InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
- InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
- InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
- InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
- for (unsigned i = 0; i < BlockSize / 4; ++i) {
- out[i * 4 + 0] = bs0.read();
- out[i * 4 + 1] = bs1.read();
- out[i * 4 + 2] = bs2.read();
- out[i * 4 + 3] = bs3.read();
- }
- Docid prev_val = out[-1];
- for (unsigned i = 0; i < BlockSize; ++i) {
- out[i] = prev_val = out[i] + prev_val + 1;
- }
- return in + bytes_for_packed_bits(BlockSize, bit_width);
-}
-
-template<class Docid>
-const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, unsigned bit_width, Docid *out)
-{
- const unsigned exception_bit_width = *in++;
- const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
- in += div_round_up(num, 8);
-
- int num_exceptions = 0;
-
- BitReader bs(in, exception_bit_width);
- for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
- uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
- if (num - i < 64) {
- // We've read some bytes past the end, so clear out the junk bits.
- exceptions &= (1ULL << (num - i)) - 1;
- }
- for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
- unsigned idx = (ffsll(exceptions) - 1) + i;
- out[idx] = bs.read() << bit_width;
- }
- }
- in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
- return in;
-}
-
-// PFor block with bitmap exceptions. Layout: