-// - Bit width (6 bits) | type << 6
-// - Exception bit width (8 bits)
-// - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
-// - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
-// - Base values (<num> values of <bits> bits, rounded up to a byte)
-template<class Docid>
-const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
-{
- memset(out, 0, num * sizeof(Docid));
-
- const unsigned bit_width = *in++ & 0x3f;
-
- in = decode_pfor_bitmap_exceptions(in, num, bit_width, out);
-
- // Decode the base values, and delta-decode.
- Docid prev_val = out[-1];
- BitReader bs(in, bit_width);
- for (unsigned i = 0; i < num; ++i) {
- out[i] = prev_val = (out[i] | bs.read()) + prev_val + 1;
- }
- return in + bytes_for_packed_bits(num, bit_width);
-}
-
-// Like decode_pfor_bitmap(), but the base 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_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
-{
- memset(out, 0, BlockSize * sizeof(Docid));
-
- const unsigned bit_width = *in++ & 0x3f;
-
- in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
-
- // Decode the base values.
- 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();
- }
-
- // Delta-decode.
- 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<unsigned BlockSize, class Docid>
-const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
-{
- if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
- return decode_pfor_bitmap_interleaved_128_32(in, out);
- } else {
- return decode_pfor_bitmap_interleaved_generic(in, out);
- }
-}
-
-__attribute__((target("default")))
-const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
-{
- return decode_pfor_bitmap_interleaved_generic<128>(in, out);
-}
-
-#ifdef COULD_HAVE_SSE2
-// Specialized version for SSE2.
-__attribute__((target("sse2")))
-const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
-{
- constexpr unsigned BlockSize = 128;
- using Docid = uint32_t;
-
- memset(out, 0, BlockSize * sizeof(Docid));
-
- const unsigned bit_width = *in++ & 0x3f;
-
- in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
- in = decode_bitmap_sse2<BlockSize, true>(in, bit_width, out);
- delta_decode_sse2<BlockSize>(out);
-
- return in;
-}
-#endif
-
-// PFor block with variable-byte exceptions. Layout:
-//
-// - Bit width (6 bits) | type << 6
-// - Number of exceptions (8 bits)
-// - Base values (<num> values of <bits> bits, rounded up to a byte)
-// - Exceptions:
-// - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
-// - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
-// - Indexes of exceptions (<num_exc> bytes).
-template<unsigned BlockSize, class Docid>
-const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
-{
- //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
-
- const unsigned bit_width = *in++ & 0x3f;
- unsigned num_exceptions = *in++;
-
- // Decode the base values.
- BitReader bs(in, bit_width);
- for (unsigned i = 0; i < num; ++i) {
- out[i] = bs.read();
- }
- in += bytes_for_packed_bits(num, bit_width);
-
- // Decode exceptions.
- Docid exceptions[BlockSize];
- if (*in == 255) {
- ++in;
- for (unsigned i = 0; i < num_exceptions; ++i) {
- exceptions[i] = read_le<Docid>(in);
- in += sizeof(Docid);
- }
- } else {
- for (unsigned i = 0; i < num_exceptions; ++i) {
- in = read_vb(in, &exceptions[i]);
- }
- }
- // Apply exceptions.
- for (unsigned i = 0; i < num_exceptions; ++i) {
- unsigned idx = *in++;
- out[idx] |= exceptions[i] << bit_width;
- }
-
- // Delta-decode.
- Docid prev_val = out[-1];
- for (unsigned i = 0; i < num; ++i) {
- out[i] = prev_val = out[i] + prev_val + 1;
- }
-
- return in;
-}
-
-// Like decode_pfor_vb(), but the base 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_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
-{
- const unsigned bit_width = *in++ & 0x3f;
- unsigned num_exceptions = *in++;
-
- // Decode the base values.
- 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();
- }
- in += bytes_for_packed_bits(BlockSize, bit_width);
-
- // Decode exceptions.
- Docid exceptions[BlockSize];
- if (*in == 255) {
- ++in;
- for (unsigned i = 0; i < num_exceptions; ++i) {
- exceptions[i] = read_le<Docid>(in);
- in += sizeof(Docid);
- }
- } else {
- for (unsigned i = 0; i < num_exceptions; ++i) {
- in = read_vb(in, &exceptions[i]);
- }
- }
-
- // Apply exceptions.
- for (unsigned i = 0; i < num_exceptions; ++i) {
- unsigned idx = *in++;
- out[idx] |= exceptions[i] << bit_width;
- }
-
- // Delta-decode.
- Docid prev_val = out[-1];
- for (unsigned i = 0; i < BlockSize; ++i) {
- out[i] = prev_val = out[i] + prev_val + 1;
- }
-
- return in;
-}
-
-template<unsigned BlockSize, class Docid>
-const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
-{
- if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
- return decode_pfor_vb_interleaved_128_32(in, out);
- } else {
- return decode_pfor_vb_interleaved_generic(in, out);
- }
-}
-
-__attribute__((target("default")))
-const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
-{
- return decode_pfor_vb_interleaved_generic<128>(in, out);
-}
-
-// Specialized version for SSE2.
-__attribute__((target("sse2")))
-const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
-{
- constexpr unsigned BlockSize = 128;
- using Docid = uint32_t;
-
- const unsigned bit_width = *in++ & 0x3f;
- unsigned num_exceptions = *in++;
-
- // Decode the base values.
- in = decode_bitmap_sse2<BlockSize, false>(in, bit_width, out);
-
- // Decode exceptions.
- Docid exceptions[BlockSize];
- if (*in == 255) {
- ++in;
- for (unsigned i = 0; i < num_exceptions; ++i) {
- exceptions[i] = read_le<Docid>(in);
- in += sizeof(Docid);
- }
- } else {
- for (unsigned i = 0; i < num_exceptions; ++i) {
- in = read_vb(in, &exceptions[i]);
- }
- }
-
- // Apply exceptions.
- for (unsigned i = 0; i < num_exceptions; ++i) {
- unsigned idx = *in++;
- out[idx] |= exceptions[i] << bit_width;
- }
-
- delta_decode_sse2<BlockSize>(out);
-
- return in;
-}
-
-enum BlockType {
- FOR = 0,
- PFOR_VB = 1,
- PFOR_BITMAP = 2,
- CONSTANT = 3
-};
-
-template<unsigned BlockSize, class Docid>
-const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
-{
- if (num == 0) {
- return in;
- }
- in = read_baseval(in, out++);
-
- for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
- const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
- switch (in[0] >> 6) {
- case BlockType::FOR:
- if (interleaved && num_this_block == BlockSize) {
- dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_for_interleaved<BlockSize>(in, out);
- } else {
- dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_for(in, num_this_block, out);
- }
- break;
- case BlockType::PFOR_VB:
- if (interleaved && num_this_block == BlockSize) {
- dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_pfor_vb_interleaved<BlockSize>(in, out);
- } else {
- dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
- }
- break;
- case BlockType::PFOR_BITMAP:
- if (interleaved && num_this_block == BlockSize) {
- dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
- } else {
- dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_pfor_bitmap(in, num_this_block, out);
- }
- break;
- case BlockType::CONSTANT:
- dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
- in = decode_constant(in, num_this_block, out);
- break;
- }
- }