10 // This is a mess. :-/ Maybe it would be good just to drop support for
11 // multiversioning; the only platform it really helps is 32-bit x86.
12 // This may change if we decide to use AVX or similar in the future, though.
13 #if defined(__i386__) || defined(__x86_64__)
15 #define COULD_HAVE_SSE2
16 #define SUPPRESS_DEFAULT
17 #include <immintrin.h>
19 #elif defined(HAS_FUNCTION_MULTIVERSIONING)
20 #define COULD_HAVE_SSE2
21 #include <immintrin.h>
22 #define TARGET_SSE2 __attribute__((target("sse2")))
23 #define TARGET_DEFAULT __attribute__((target("default")))
25 #define TARGET_DEFAULT
28 // Function multiversioning is x86-only.
29 #define TARGET_DEFAULT
32 #include "turbopfor-common.h"
35 //#define dprintf(...) fprintf(stderr, __VA_ARGS__);
37 #ifndef SUPPRESS_DEFAULT
38 // Forward declarations to declare to the template code below that they exist.
39 // (These must seemingly be non-templates for function multiversioning to work.)
42 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
45 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
48 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
51 #ifdef COULD_HAVE_SSE2
54 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
57 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
60 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
64 Docid read_le(const void *in)
67 memcpy(&val, in, sizeof(val));
68 if constexpr (sizeof(Docid) == 8) {
70 } else if constexpr (sizeof(Docid) == 4) {
72 } else if constexpr (sizeof(Docid) == 2) {
74 } else if constexpr (sizeof(Docid) == 1) {
81 // Reads a single value with an encoding that looks a bit like PrefixVarint.
82 // It's unclear why this doesn't use the varbyte encoding.
84 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
86 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
90 } else if (*in < 192) {
91 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
93 } else if (*in < 224) {
94 *out = ((uint32_t(in[0]) << 16) |
95 (uint32_t(in[2]) << 8) |
96 (uint32_t(in[1]))) & 0x1fffff;
98 } else if (*in < 240) {
99 *out = ((uint32_t(in[0]) << 24) |
100 (uint32_t(in[1]) << 16) |
101 (uint32_t(in[2]) << 8) |
102 (uint32_t(in[3]))) & 0xfffffff;
105 assert(false); // Not implemented.
109 // Does not read past the end of the input.
110 template<class Docid>
111 const unsigned char *read_vb(const unsigned char *in, Docid *out)
116 } else if (*in <= 240) {
117 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
119 } else if (*in <= 248) {
120 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
122 } else if (*in == 249) {
123 *out = (uint32_t(in[1])) |
124 (uint32_t(in[2]) << 8) |
125 (uint32_t(in[3]) << 16);
127 } else if (*in == 250) {
128 *out = read_le<uint32_t>(in + 1);
137 BitReader(const unsigned char *in, unsigned bits)
138 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
140 // Can read 4 bytes past the end of the input (if bits_used == 0).
143 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
153 const unsigned char *in;
156 unsigned bits_used = 0;
159 template<unsigned NumStreams>
160 struct InterleavedBitReader {
162 InterleavedBitReader(const unsigned char *in, unsigned bits)
163 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
165 // Can read 4 bytes past the end of the input (if bit_width == 0).
169 if (bits_used + bits > 32) {
170 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
172 val = (read_le<uint32_t>(in) >> bits_used);
176 in += Stride * (bits_used / 32);
183 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
184 const unsigned char *in;
187 unsigned bits_used = 0;
190 #ifdef COULD_HAVE_SSE2
191 struct InterleavedBitReaderSSE2 {
194 InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
195 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
197 // Can read 16 bytes past the end of the input (if bit_width == 0).
202 __m128i val = _mm_srli_epi32(_mm_loadu_si128(in), bits_used);
203 if (bits_used + bits > 32) {
204 __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(in + 1), 32 - bits_used);
205 val = _mm_or_si128(val, val_upper);
207 val = _mm_and_si128(val, mask);
210 in += bits_used / 32;
219 unsigned bits_used = 0;
223 // Constant block. Layout:
225 // - Bit width (6 bits) | type << 6
226 // - Base values (<bits> bits, rounded up to nearest byte)
228 // Can read 4 bytes past the end of the input (if bit_width == 0).
229 template<class Docid>
230 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
232 const unsigned bit_width = *in++ & 0x3f;
233 Docid val = read_le<Docid>(in);
234 if (bit_width < sizeof(Docid) * 8) {
235 val &= mask_for_bits(bit_width);
238 Docid prev_val = out[-1];
239 for (unsigned i = 0; i < num; ++i) {
240 out[i] = prev_val = val + prev_val + 1;
242 return in + div_round_up(bit_width, 8);
245 // FOR block (ie., PFor without exceptions). Layout:
247 // - Bit width (6 bits) | type << 6
248 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
250 // Can read 4 bytes past the end of the input (inherit from BitReader).
251 template<class Docid>
252 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
254 const unsigned bit_width = *in++ & 0x3f;
256 Docid prev_val = out[-1];
257 BitReader bs(in, bit_width);
258 for (unsigned i = 0; i < num; ++i) {
259 prev_val = out[i] = bs.read() + prev_val + 1;
261 return in + bytes_for_packed_bits(num, bit_width);
264 #ifdef COULD_HAVE_SSE2
265 class DeltaDecoderSSE2 {
268 DeltaDecoderSSE2(uint32_t prev_val)
269 : prev_val(_mm_set1_epi32(prev_val)) {}
275 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
276 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
277 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
278 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
283 // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
284 // in parallel with something else.
285 const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
290 template<unsigned BlockSize>
291 TARGET_SSE2 inline void delta_decode_sse2(uint32_t *out)
293 DeltaDecoderSSE2 delta(out[-1]);
294 __m128i *outvec = reinterpret_cast<__m128i *>(out);
295 for (unsigned i = 0; i < BlockSize / 4; ++i) {
296 __m128i val = _mm_loadu_si128(outvec + i);
297 _mm_storeu_si128(outvec + i, delta.decode(val));
301 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
302 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
303 TARGET_SSE2 const unsigned char *
304 decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
306 __m128i *outvec = reinterpret_cast<__m128i *>(out);
307 DeltaDecoderSSE2 delta(out[-1]);
308 InterleavedBitReaderSSE2 bs(in, bit_width);
309 #pragma GCC unroll 32
310 for (unsigned i = 0; i < BlockSize / 4; ++i) {
311 __m128i val = bs.read();
312 if constexpr (OrWithExisting) {
313 val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
315 if constexpr (DeltaDecode) {
316 val = delta.decode(val);
318 _mm_storeu_si128(outvec + i, val);
320 in += bytes_for_packed_bits(BlockSize, bit_width);
324 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
325 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
326 TARGET_SSE2 const unsigned char *
327 decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
331 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
333 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
335 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
337 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
339 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
341 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
343 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
345 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
347 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
349 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
351 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
353 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
355 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
357 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
359 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
361 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
363 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
365 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
367 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
369 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
371 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
373 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
375 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
377 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
379 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
381 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
383 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
385 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
387 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
389 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
391 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
393 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
395 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
401 // Like decode_for(), but the values are organized in four independent streams,
402 // for SIMD (presumably SSE2). Supports a whole block only.
404 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
405 template<unsigned BlockSize, class Docid>
406 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
408 const unsigned bit_width = *in++ & 0x3f;
410 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
411 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
412 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
413 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
414 for (unsigned i = 0; i < BlockSize / 4; ++i) {
415 out[i * 4 + 0] = bs0.read();
416 out[i * 4 + 1] = bs1.read();
417 out[i * 4 + 2] = bs2.read();
418 out[i * 4 + 3] = bs3.read();
420 Docid prev_val = out[-1];
421 for (unsigned i = 0; i < BlockSize; ++i) {
422 out[i] = prev_val = out[i] + prev_val + 1;
424 return in + bytes_for_packed_bits(BlockSize, bit_width);
427 // Does not read past the end of the input.
428 template<unsigned BlockSize, class Docid>
429 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
431 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
432 return decode_for_interleaved_128_32(in, out);
434 return decode_for_interleaved_generic(in, out);
438 #ifndef SUPPRESS_DEFAULT
439 // Does not read past the end of the input.
441 const unsigned char *
442 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
444 return decode_for_interleaved_generic<128>(in, out);
448 #ifdef COULD_HAVE_SSE2
449 // Specialized version for SSE2.
450 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
452 const unsigned char *
453 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
455 constexpr unsigned BlockSize = 128;
457 const unsigned bit_width = *in++ & 0x3f;
459 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
465 // Can read 4 bytes past the end of the input (inherit from BitReader).
466 template<class Docid>
467 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
469 const unsigned exception_bit_width = *in++;
470 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
471 in += div_round_up(num, 8);
473 int num_exceptions = 0;
475 BitReader bs(in, exception_bit_width);
476 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
477 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
479 // We've read some bytes past the end, so clear out the junk bits.
480 exceptions &= (1ULL << (num - i)) - 1;
482 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
483 unsigned idx = (ffsll(exceptions) - 1) + i;
484 out[idx] = bs.read();
487 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
491 // PFor block with bitmap exceptions. Layout:
493 // - Bit width (6 bits) | type << 6
494 // - Exception bit width (8 bits)
495 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
496 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
497 // - Base values (<num> values of <bits> bits, rounded up to a byte)
499 // Can read 4 bytes past the end of the input (inherit from BitReader).
500 template<class Docid>
501 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
503 memset(out, 0, num * sizeof(Docid));
505 const unsigned bit_width = *in++ & 0x3f;
507 in = decode_pfor_bitmap_exceptions(in, num, out);
509 // Decode the base values, and delta-decode.
510 Docid prev_val = out[-1];
511 BitReader bs(in, bit_width);
512 for (unsigned i = 0; i < num; ++i) {
513 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
515 return in + bytes_for_packed_bits(num, bit_width);
518 // Like decode_pfor_bitmap(), but the base values are organized in four
519 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
521 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReader
522 // and decode_pfor_bitmap_exceptions()).
523 template<unsigned BlockSize, class Docid>
524 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
526 memset(out, 0, BlockSize * sizeof(Docid));
528 const unsigned bit_width = *in++ & 0x3f;
530 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
532 // Decode the base values.
533 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
534 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
535 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
536 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
537 for (unsigned i = 0; i < BlockSize / 4; ++i) {
538 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
539 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
540 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
541 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
545 Docid prev_val = out[-1];
546 for (unsigned i = 0; i < BlockSize; ++i) {
547 out[i] = prev_val = out[i] + prev_val + 1;
549 return in + bytes_for_packed_bits(BlockSize, bit_width);
552 // Can read 16 bytes past the end of the input (inherit from decode_pfor_bitmap_interleaved_generic()).
553 template<unsigned BlockSize, class Docid>
554 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
556 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
557 return decode_pfor_bitmap_interleaved_128_32(in, out);
559 return decode_pfor_bitmap_interleaved_generic(in, out);
563 #ifndef SUPPRESS_DEFAULT
565 const unsigned char *
566 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
568 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
572 #ifdef COULD_HAVE_SSE2
573 // Specialized version for SSE2.
575 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReaderSSE2
576 // and decode_pfor_bitmap_exceptions()).
578 const unsigned char *
579 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
581 constexpr unsigned BlockSize = 128;
583 // Set all output values to zero, before the exceptions are filled in.
585 for (unsigned i = 0; i < BlockSize / 4; ++i) {
586 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
589 const unsigned bit_width = *in++ & 0x3f;
591 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
592 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
598 // PFor block with variable-byte exceptions. Layout:
600 // - Bit width (6 bits) | type << 6
601 // - Number of exceptions (8 bits)
602 // - Base values (<num> values of <bits> bits, rounded up to a byte)
604 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
605 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
606 // - Indexes of exceptions (<num_exc> bytes).
608 // Can read 4 bytes past the end of the input (inherit from BitReader,
609 // assuming zero exceptions).
610 template<unsigned BlockSize, class Docid>
611 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
613 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
615 const unsigned bit_width = *in++ & 0x3f;
616 unsigned num_exceptions = *in++;
618 // Decode the base values.
619 BitReader bs(in, bit_width);
620 for (unsigned i = 0; i < num; ++i) {
623 in += bytes_for_packed_bits(num, bit_width);
625 // Decode exceptions.
626 Docid exceptions[BlockSize];
629 for (unsigned i = 0; i < num_exceptions; ++i) {
630 exceptions[i] = read_le<Docid>(in);
634 for (unsigned i = 0; i < num_exceptions; ++i) {
635 in = read_vb(in, &exceptions[i]);
639 for (unsigned i = 0; i < num_exceptions; ++i) {
640 unsigned idx = *in++;
641 out[idx] |= exceptions[i] << bit_width;
645 Docid prev_val = out[-1];
646 for (unsigned i = 0; i < num; ++i) {
647 out[i] = prev_val = out[i] + prev_val + 1;
653 // Like decode_pfor_vb(), but the base values are organized in four
654 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
655 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
656 template<unsigned BlockSize, class Docid>
657 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
659 const unsigned bit_width = *in++ & 0x3f;
660 unsigned num_exceptions = *in++;
662 // Decode the base values.
663 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
664 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
665 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
666 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
667 for (unsigned i = 0; i < BlockSize / 4; ++i) {
668 out[i * 4 + 0] = bs0.read();
669 out[i * 4 + 1] = bs1.read();
670 out[i * 4 + 2] = bs2.read();
671 out[i * 4 + 3] = bs3.read();
673 in += bytes_for_packed_bits(BlockSize, bit_width);
675 // Decode exceptions.
676 Docid exceptions[BlockSize];
679 for (unsigned i = 0; i < num_exceptions; ++i) {
680 exceptions[i] = read_le<Docid>(in);
684 for (unsigned i = 0; i < num_exceptions; ++i) {
685 in = read_vb(in, &exceptions[i]);
690 for (unsigned i = 0; i < num_exceptions; ++i) {
691 unsigned idx = *in++;
692 out[idx] |= exceptions[i] << bit_width;
696 Docid prev_val = out[-1];
697 for (unsigned i = 0; i < BlockSize; ++i) {
698 out[i] = prev_val = out[i] + prev_val + 1;
704 // Can read 16 bytes past the end of its input (inherit from decode_pfor_vb_interleaved_generic()).
705 template<unsigned BlockSize, class Docid>
706 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
708 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
709 return decode_pfor_vb_interleaved_128_32(in, out);
711 return decode_pfor_vb_interleaved_generic(in, out);
715 #ifndef SUPPRESS_DEFAULT
717 const unsigned char *
718 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
720 return decode_pfor_vb_interleaved_generic<128>(in, out);
724 #ifdef COULD_HAVE_SSE2
725 // Specialized version for SSE2.
726 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
728 const unsigned char *
729 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
731 constexpr unsigned BlockSize = 128;
732 using Docid = uint32_t;
734 const unsigned bit_width = *in++ & 0x3f;
735 unsigned num_exceptions = *in++;
737 // Decode the base values.
738 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
740 // Decode exceptions.
741 Docid exceptions[BlockSize];
744 for (unsigned i = 0; i < num_exceptions; ++i) {
745 exceptions[i] = read_le<Docid>(in);
749 for (unsigned i = 0; i < num_exceptions; ++i) {
750 in = read_vb(in, &exceptions[i]);
755 for (unsigned i = 0; i < num_exceptions; ++i) {
756 unsigned idx = *in++;
757 out[idx] |= exceptions[i] << bit_width;
760 delta_decode_sse2<BlockSize>(out);
766 // Can read 16 bytes past the end of the input (inherit from several functions).
767 template<unsigned BlockSize, class Docid>
768 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
773 in = read_baseval(in, out++);
775 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
776 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
777 switch (in[0] >> 6) {
779 if (interleaved && num_this_block == BlockSize) {
780 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
781 in = decode_for_interleaved<BlockSize>(in, out);
783 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
784 in = decode_for(in, num_this_block, out);
787 case BlockType::PFOR_VB:
788 if (interleaved && num_this_block == BlockSize) {
789 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
790 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
792 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
793 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
796 case BlockType::PFOR_BITMAP:
797 if (interleaved && num_this_block == BlockSize) {
798 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
799 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
801 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
802 in = decode_pfor_bitmap(in, num_this_block, out);
805 case BlockType::CONSTANT:
806 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
807 in = decode_constant(in, num_this_block, out);
815 const unsigned char *decode_pfor_delta1_128(const unsigned char *in, unsigned num, bool interleaved, uint32_t *out)
817 return decode_pfor_delta1<128>(in, num, interleaved, out);