4 // A reimplementation of parts of the TurboPFor codecs, using the same
5 // storage format. These are not as fast as the reference implementation
6 // (about 80% of the performance, averaged over a real plocate corpus),
7 // and do not support the same breadth of codecs (in particular, only
8 // delta-plus-1 is implemented, and only 32-bit docids are tested),
9 // but aim to be more portable and (ideally) easier-to-understand.
10 // In particular, they will compile on x86 without SSE4.1 or AVX support.
12 // The main reference is https://michael.stapelberg.ch/posts/2019-02-05-turbopfor-analysis/,
13 // although some implementation details have been worked out by studying the
23 #if defined(__i386__) || defined(__x86_64__)
24 #define COULD_HAVE_SSE2
25 #include <immintrin.h>
28 #include "turbopfor-common.h"
30 // Forward declarations to declare to the template code below that they exist.
31 // (These must seemingly be non-templates for function multiversioning to work.)
32 __attribute__((target("default")))
34 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
35 __attribute__((target("default")))
37 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
38 __attribute__((target("default")))
40 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
42 #ifdef COULD_HAVE_SSE2
43 __attribute__((target("sse2")))
45 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
46 __attribute__((target("sse2")))
48 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
49 __attribute__((target("sse2")))
51 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
55 Docid read_le(const void *in)
58 memcpy(&val, in, sizeof(val));
59 if constexpr (sizeof(Docid) == 8) {
61 } else if constexpr (sizeof(Docid) == 4) {
63 } else if constexpr (sizeof(Docid) == 2) {
65 } else if constexpr (sizeof(Docid) == 1) {
72 // Reads a single value with an encoding that looks a bit like PrefixVarint.
73 // It's unclear why this doesn't use the varbyte encoding.
75 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
77 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
81 } else if (*in < 192) {
82 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
84 } else if (*in < 224) {
85 *out = ((uint32_t(in[0]) << 16) |
86 (uint32_t(in[2]) << 8) |
87 (uint32_t(in[1]))) & 0x1fffff;
90 assert(false); // Not implemented.
95 const unsigned char *read_vb(const unsigned char *in, Docid *out)
100 } else if (*in <= 240) {
101 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
103 } else if (*in <= 248) {
104 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
106 } else if (*in == 249) {
107 *out = (uint32_t(in[1])) |
108 (uint32_t(in[2]) << 8) |
109 (uint32_t(in[3]) << 16);
111 } else if (*in == 250) {
112 *out = read_le<uint32_t>(in + 1);
121 BitReader(const unsigned char *in, unsigned bits)
122 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
125 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
135 const unsigned char *in;
138 unsigned bits_used = 0;
141 template<unsigned NumStreams>
142 struct InterleavedBitReader {
144 InterleavedBitReader(const unsigned char *in, unsigned bits)
145 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
149 if (bits_used + bits > 32) {
150 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
152 val = (read_le<uint32_t>(in) >> bits_used);
156 in += Stride * (bits_used / 32);
163 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
164 const unsigned char *in;
167 unsigned bits_used = 0;
170 #ifdef COULD_HAVE_SSE2
171 struct InterleavedBitReaderSSE2 {
173 __attribute__((target("sse2")))
174 InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
175 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
177 __attribute__((target("sse2")))
181 __m128i val = _mm_srli_epi32(_mm_loadu_si128(in), bits_used);
182 if (bits_used + bits > 32) {
183 __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(in + 1), 32 - bits_used);
184 val = _mm_or_si128(val, val_upper);
186 val = _mm_and_si128(val, mask);
189 in += bits_used / 32;
198 unsigned bits_used = 0;
202 // Constant block. Layout:
204 // - Bit width (6 bits) | type << 6
205 // - Base values (<bits> bits, rounded up to nearest byte)
206 template<class Docid>
207 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
209 const unsigned bit_width = *in++ & 0x3f;
210 Docid val = read_le<Docid>(in);
211 if (bit_width < sizeof(Docid) * 8) {
212 val &= mask_for_bits(bit_width);
215 Docid prev_val = out[-1];
216 for (unsigned i = 0; i < num; ++i) {
217 out[i] = prev_val = val + prev_val + 1;
219 return in + div_round_up(bit_width, 8);
222 // FOR block (ie., PFor without exceptions). Layout:
224 // - Bit width (6 bits) | type << 6
225 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
226 template<class Docid>
227 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
229 const unsigned bit_width = *in++ & 0x3f;
231 Docid prev_val = out[-1];
232 BitReader bs(in, bit_width);
233 for (unsigned i = 0; i < num; ++i) {
234 prev_val = out[i] = bs.read() + prev_val + 1;
236 return in + bytes_for_packed_bits(num, bit_width);
239 #ifdef COULD_HAVE_SSE2
240 class DeltaDecoderSSE2 {
242 __attribute__((target("sse2")))
243 DeltaDecoderSSE2(uint32_t prev_val)
244 : prev_val(_mm_set1_epi32(prev_val)) {}
246 __attribute__((target("sse2")))
250 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
251 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
252 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
253 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
258 // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
259 // in parallel with something else.
260 const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
265 template<unsigned BlockSize>
266 __attribute__((target("sse2"))) inline void delta_decode_sse2(uint32_t *out)
268 DeltaDecoderSSE2 delta(out[-1]);
269 __m128i *outvec = reinterpret_cast<__m128i *>(out);
270 for (unsigned i = 0; i < BlockSize / 4; ++i) {
271 __m128i val = _mm_loadu_si128(outvec + i);
272 _mm_storeu_si128(outvec + i, delta.decode(val));
276 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
277 __attribute__((target("sse2")))
278 const unsigned char *
279 decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
281 __m128i *outvec = reinterpret_cast<__m128i *>(out);
282 DeltaDecoderSSE2 delta(out[-1]);
283 InterleavedBitReaderSSE2 bs(in, bit_width);
284 #pragma GCC unroll 32
285 for (unsigned i = 0; i < BlockSize / 4; ++i) {
286 __m128i val = bs.read();
287 if constexpr (OrWithExisting) {
288 val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
290 if constexpr (DeltaDecode) {
291 val = delta.decode(val);
293 _mm_storeu_si128(outvec + i, val);
295 in += bytes_for_packed_bits(BlockSize, bit_width);
299 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
300 __attribute__((target("sse2")))
301 const unsigned char *
302 decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
306 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
308 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
310 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
312 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
314 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
316 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
318 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
320 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
322 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
324 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
326 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
328 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
330 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
332 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
334 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
336 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
338 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
340 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
342 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
344 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
346 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
348 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
350 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
352 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
354 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
356 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
358 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
360 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
362 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
364 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
366 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
368 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
370 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
376 // Like decode_for(), but the values are organized in four independent streams,
377 // for SIMD (presumably SSE2). Supports a whole block only.
378 template<unsigned BlockSize, class Docid>
379 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
381 const unsigned bit_width = *in++ & 0x3f;
383 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
384 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
385 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
386 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
387 for (unsigned i = 0; i < BlockSize / 4; ++i) {
388 out[i * 4 + 0] = bs0.read();
389 out[i * 4 + 1] = bs1.read();
390 out[i * 4 + 2] = bs2.read();
391 out[i * 4 + 3] = bs3.read();
393 Docid prev_val = out[-1];
394 for (unsigned i = 0; i < BlockSize; ++i) {
395 out[i] = prev_val = out[i] + prev_val + 1;
397 return in + bytes_for_packed_bits(BlockSize, bit_width);
400 template<unsigned BlockSize, class Docid>
401 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
403 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
404 return decode_for_interleaved_128_32(in, out);
406 return decode_for_interleaved_generic(in, out);
410 __attribute__((target("default")))
411 const unsigned char *
412 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
414 return decode_for_interleaved_generic<128>(in, out);
417 #ifdef COULD_HAVE_SSE2
418 // Specialized version for SSE2.
419 __attribute__((target("sse2")))
420 const unsigned char *
421 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
423 constexpr unsigned BlockSize = 128;
425 const unsigned bit_width = *in++ & 0x3f;
427 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
433 template<class Docid>
434 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
436 const unsigned exception_bit_width = *in++;
437 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
438 in += div_round_up(num, 8);
440 int num_exceptions = 0;
442 BitReader bs(in, exception_bit_width);
443 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
444 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
446 // We've read some bytes past the end, so clear out the junk bits.
447 exceptions &= (1ULL << (num - i)) - 1;
449 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
450 unsigned idx = (ffsll(exceptions) - 1) + i;
451 out[idx] = bs.read();
454 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
458 // PFor block with bitmap exceptions. Layout:
460 // - Bit width (6 bits) | type << 6
461 // - Exception bit width (8 bits)
462 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
463 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
464 // - Base values (<num> values of <bits> bits, rounded up to a byte)
465 template<class Docid>
466 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
468 memset(out, 0, num * sizeof(Docid));
470 const unsigned bit_width = *in++ & 0x3f;
472 in = decode_pfor_bitmap_exceptions(in, num, out);
474 // Decode the base values, and delta-decode.
475 Docid prev_val = out[-1];
476 BitReader bs(in, bit_width);
477 for (unsigned i = 0; i < num; ++i) {
478 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
480 return in + bytes_for_packed_bits(num, bit_width);
483 // Like decode_pfor_bitmap(), but the base values are organized in four
484 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
485 template<unsigned BlockSize, class Docid>
486 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
488 memset(out, 0, BlockSize * sizeof(Docid));
490 const unsigned bit_width = *in++ & 0x3f;
492 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
494 // Decode the base values.
495 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
496 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
497 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
498 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
499 for (unsigned i = 0; i < BlockSize / 4; ++i) {
500 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
501 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
502 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
503 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
507 Docid prev_val = out[-1];
508 for (unsigned i = 0; i < BlockSize; ++i) {
509 out[i] = prev_val = out[i] + prev_val + 1;
511 return in + bytes_for_packed_bits(BlockSize, bit_width);
514 template<unsigned BlockSize, class Docid>
515 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
517 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
518 return decode_pfor_bitmap_interleaved_128_32(in, out);
520 return decode_pfor_bitmap_interleaved_generic(in, out);
524 __attribute__((target("default")))
525 const unsigned char *
526 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
528 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
531 #ifdef COULD_HAVE_SSE2
532 // Specialized version for SSE2.
533 __attribute__((target("sse2")))
534 const unsigned char *
535 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
537 constexpr unsigned BlockSize = 128;
539 // Set all output values to zero, before the exceptions are filled in.
541 for (unsigned i = 0; i < BlockSize / 4; ++i) {
542 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
545 const unsigned bit_width = *in++ & 0x3f;
547 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
548 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
554 // PFor block with variable-byte exceptions. Layout:
556 // - Bit width (6 bits) | type << 6
557 // - Number of exceptions (8 bits)
558 // - Base values (<num> values of <bits> bits, rounded up to a byte)
560 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
561 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
562 // - Indexes of exceptions (<num_exc> bytes).
563 template<unsigned BlockSize, class Docid>
564 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
566 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
568 const unsigned bit_width = *in++ & 0x3f;
569 unsigned num_exceptions = *in++;
571 // Decode the base values.
572 BitReader bs(in, bit_width);
573 for (unsigned i = 0; i < num; ++i) {
576 in += bytes_for_packed_bits(num, bit_width);
578 // Decode exceptions.
579 Docid exceptions[BlockSize];
582 for (unsigned i = 0; i < num_exceptions; ++i) {
583 exceptions[i] = read_le<Docid>(in);
587 for (unsigned i = 0; i < num_exceptions; ++i) {
588 in = read_vb(in, &exceptions[i]);
592 for (unsigned i = 0; i < num_exceptions; ++i) {
593 unsigned idx = *in++;
594 out[idx] |= exceptions[i] << bit_width;
598 Docid prev_val = out[-1];
599 for (unsigned i = 0; i < num; ++i) {
600 out[i] = prev_val = out[i] + prev_val + 1;
606 // Like decode_pfor_vb(), but the base values are organized in four
607 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
608 template<unsigned BlockSize, class Docid>
609 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
611 const unsigned bit_width = *in++ & 0x3f;
612 unsigned num_exceptions = *in++;
614 // Decode the base values.
615 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
616 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
617 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
618 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
619 for (unsigned i = 0; i < BlockSize / 4; ++i) {
620 out[i * 4 + 0] = bs0.read();
621 out[i * 4 + 1] = bs1.read();
622 out[i * 4 + 2] = bs2.read();
623 out[i * 4 + 3] = bs3.read();
625 in += bytes_for_packed_bits(BlockSize, bit_width);
627 // Decode exceptions.
628 Docid exceptions[BlockSize];
631 for (unsigned i = 0; i < num_exceptions; ++i) {
632 exceptions[i] = read_le<Docid>(in);
636 for (unsigned i = 0; i < num_exceptions; ++i) {
637 in = read_vb(in, &exceptions[i]);
642 for (unsigned i = 0; i < num_exceptions; ++i) {
643 unsigned idx = *in++;
644 out[idx] |= exceptions[i] << bit_width;
648 Docid prev_val = out[-1];
649 for (unsigned i = 0; i < BlockSize; ++i) {
650 out[i] = prev_val = out[i] + prev_val + 1;
656 template<unsigned BlockSize, class Docid>
657 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
659 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
660 return decode_pfor_vb_interleaved_128_32(in, out);
662 return decode_pfor_vb_interleaved_generic(in, out);
666 __attribute__((target("default")))
667 const unsigned char *
668 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
670 return decode_pfor_vb_interleaved_generic<128>(in, out);
673 // Specialized version for SSE2.
674 __attribute__((target("sse2")))
675 const unsigned char *
676 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
678 constexpr unsigned BlockSize = 128;
679 using Docid = uint32_t;
681 const unsigned bit_width = *in++ & 0x3f;
682 unsigned num_exceptions = *in++;
684 // Decode the base values.
685 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
687 // Decode exceptions.
688 Docid exceptions[BlockSize];
691 for (unsigned i = 0; i < num_exceptions; ++i) {
692 exceptions[i] = read_le<Docid>(in);
696 for (unsigned i = 0; i < num_exceptions; ++i) {
697 in = read_vb(in, &exceptions[i]);
702 for (unsigned i = 0; i < num_exceptions; ++i) {
703 unsigned idx = *in++;
704 out[idx] |= exceptions[i] << bit_width;
707 delta_decode_sse2<BlockSize>(out);
712 template<unsigned BlockSize, class Docid>
713 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
718 in = read_baseval(in, out++);
720 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
721 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
722 switch (in[0] >> 6) {
724 if (interleaved && num_this_block == BlockSize) {
725 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
726 in = decode_for_interleaved<BlockSize>(in, out);
728 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
729 in = decode_for(in, num_this_block, out);
732 case BlockType::PFOR_VB:
733 if (interleaved && num_this_block == BlockSize) {
734 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
735 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
737 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
738 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
741 case BlockType::PFOR_BITMAP:
742 if (interleaved && num_this_block == BlockSize) {
743 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
744 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
746 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
747 in = decode_pfor_bitmap(in, num_this_block, out);
750 case BlockType::CONSTANT:
751 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
752 in = decode_constant(in, num_this_block, out);
760 #endif // !defined(_TURBOPFOR_H)