8 #if defined(__i386__) || defined(__x86_64__)
9 #define COULD_HAVE_SSE2
10 #include <immintrin.h>
13 #include "turbopfor-common.h"
16 //#define dprintf(...) fprintf(stderr, __VA_ARGS__);
18 // Forward declarations to declare to the template code below that they exist.
19 // (These must seemingly be non-templates for function multiversioning to work.)
20 __attribute__((target("default")))
22 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
23 __attribute__((target("default")))
25 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
26 __attribute__((target("default")))
28 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
30 #ifdef COULD_HAVE_SSE2
31 __attribute__((target("sse2")))
33 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
34 __attribute__((target("sse2")))
36 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
37 __attribute__((target("sse2")))
39 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
43 Docid read_le(const void *in)
46 memcpy(&val, in, sizeof(val));
47 if constexpr (sizeof(Docid) == 8) {
49 } else if constexpr (sizeof(Docid) == 4) {
51 } else if constexpr (sizeof(Docid) == 2) {
53 } else if constexpr (sizeof(Docid) == 1) {
60 // Reads a single value with an encoding that looks a bit like PrefixVarint.
61 // It's unclear why this doesn't use the varbyte encoding.
63 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
65 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
69 } else if (*in < 192) {
70 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
72 } else if (*in < 224) {
73 *out = ((uint32_t(in[0]) << 16) |
74 (uint32_t(in[2]) << 8) |
75 (uint32_t(in[1]))) & 0x1fffff;
77 } else if (*in < 240) {
78 *out = ((uint32_t(in[0]) << 24) |
79 (uint32_t(in[1]) << 16) |
80 (uint32_t(in[2]) << 8) |
81 (uint32_t(in[3]))) & 0xfffffff;
84 assert(false); // Not implemented.
88 // Does not read past the end of the input.
90 const unsigned char *read_vb(const unsigned char *in, Docid *out)
95 } else if (*in <= 240) {
96 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
98 } else if (*in <= 248) {
99 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
101 } else if (*in == 249) {
102 *out = (uint32_t(in[1])) |
103 (uint32_t(in[2]) << 8) |
104 (uint32_t(in[3]) << 16);
106 } else if (*in == 250) {
107 *out = read_le<uint32_t>(in + 1);
116 BitReader(const unsigned char *in, unsigned bits)
117 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
119 // Can read 4 bytes past the end of the input (if bits_used == 0).
122 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
132 const unsigned char *in;
135 unsigned bits_used = 0;
138 template<unsigned NumStreams>
139 struct InterleavedBitReader {
141 InterleavedBitReader(const unsigned char *in, unsigned bits)
142 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
144 // Can read 4 bytes past the end of the input (if bit_width == 0).
148 if (bits_used + bits > 32) {
149 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
151 val = (read_le<uint32_t>(in) >> bits_used);
155 in += Stride * (bits_used / 32);
162 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
163 const unsigned char *in;
166 unsigned bits_used = 0;
169 #ifdef COULD_HAVE_SSE2
170 struct InterleavedBitReaderSSE2 {
172 __attribute__((target("sse2")))
173 InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
174 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
176 // Can read 16 bytes past the end of the input (if bit_width == 0).
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)
207 // Can read 4 bytes past the end of the input (if bit_width == 0).
208 template<class Docid>
209 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
211 const unsigned bit_width = *in++ & 0x3f;
212 Docid val = read_le<Docid>(in);
213 if (bit_width < sizeof(Docid) * 8) {
214 val &= mask_for_bits(bit_width);
217 Docid prev_val = out[-1];
218 for (unsigned i = 0; i < num; ++i) {
219 out[i] = prev_val = val + prev_val + 1;
221 return in + div_round_up(bit_width, 8);
224 // FOR block (ie., PFor without exceptions). Layout:
226 // - Bit width (6 bits) | type << 6
227 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
229 // Can read 4 bytes past the end of the input (inherit from BitReader).
230 template<class Docid>
231 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
233 const unsigned bit_width = *in++ & 0x3f;
235 Docid prev_val = out[-1];
236 BitReader bs(in, bit_width);
237 for (unsigned i = 0; i < num; ++i) {
238 prev_val = out[i] = bs.read() + prev_val + 1;
240 return in + bytes_for_packed_bits(num, bit_width);
243 #ifdef COULD_HAVE_SSE2
244 class DeltaDecoderSSE2 {
246 __attribute__((target("sse2")))
247 DeltaDecoderSSE2(uint32_t prev_val)
248 : prev_val(_mm_set1_epi32(prev_val)) {}
250 __attribute__((target("sse2")))
254 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
255 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
256 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
257 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
262 // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
263 // in parallel with something else.
264 const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
269 template<unsigned BlockSize>
270 __attribute__((target("sse2"))) inline void delta_decode_sse2(uint32_t *out)
272 DeltaDecoderSSE2 delta(out[-1]);
273 __m128i *outvec = reinterpret_cast<__m128i *>(out);
274 for (unsigned i = 0; i < BlockSize / 4; ++i) {
275 __m128i val = _mm_loadu_si128(outvec + i);
276 _mm_storeu_si128(outvec + i, delta.decode(val));
280 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
281 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
282 __attribute__((target("sse2")))
283 const unsigned char *
284 decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
286 __m128i *outvec = reinterpret_cast<__m128i *>(out);
287 DeltaDecoderSSE2 delta(out[-1]);
288 InterleavedBitReaderSSE2 bs(in, bit_width);
289 #pragma GCC unroll 32
290 for (unsigned i = 0; i < BlockSize / 4; ++i) {
291 __m128i val = bs.read();
292 if constexpr (OrWithExisting) {
293 val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
295 if constexpr (DeltaDecode) {
296 val = delta.decode(val);
298 _mm_storeu_si128(outvec + i, val);
300 in += bytes_for_packed_bits(BlockSize, bit_width);
304 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
305 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
306 __attribute__((target("sse2")))
307 const unsigned char *
308 decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
312 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
314 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
316 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
318 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
320 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
322 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
324 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
326 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
328 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
330 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
332 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
334 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
336 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
338 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
340 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
342 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
344 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
346 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
348 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
350 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
352 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
354 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
356 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
358 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
360 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
362 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
364 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
366 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
368 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
370 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
372 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
374 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
376 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
382 // Like decode_for(), but the values are organized in four independent streams,
383 // for SIMD (presumably SSE2). Supports a whole block only.
385 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
386 template<unsigned BlockSize, class Docid>
387 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
389 const unsigned bit_width = *in++ & 0x3f;
391 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
392 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
393 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
394 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
395 for (unsigned i = 0; i < BlockSize / 4; ++i) {
396 out[i * 4 + 0] = bs0.read();
397 out[i * 4 + 1] = bs1.read();
398 out[i * 4 + 2] = bs2.read();
399 out[i * 4 + 3] = bs3.read();
401 Docid prev_val = out[-1];
402 for (unsigned i = 0; i < BlockSize; ++i) {
403 out[i] = prev_val = out[i] + prev_val + 1;
405 return in + bytes_for_packed_bits(BlockSize, bit_width);
408 // Does not read past the end of the input.
409 template<unsigned BlockSize, class Docid>
410 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
412 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
413 return decode_for_interleaved_128_32(in, out);
415 return decode_for_interleaved_generic(in, out);
419 // Does not read past the end of the input.
420 __attribute__((target("default")))
421 const unsigned char *
422 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
424 return decode_for_interleaved_generic<128>(in, out);
427 #ifdef COULD_HAVE_SSE2
428 // Specialized version for SSE2.
429 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
430 __attribute__((target("sse2")))
431 const unsigned char *
432 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
434 constexpr unsigned BlockSize = 128;
436 const unsigned bit_width = *in++ & 0x3f;
438 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
444 // Can read 4 bytes past the end of the input (inherit from BitReader).
445 template<class Docid>
446 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
448 const unsigned exception_bit_width = *in++;
449 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
450 in += div_round_up(num, 8);
452 int num_exceptions = 0;
454 BitReader bs(in, exception_bit_width);
455 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
456 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
458 // We've read some bytes past the end, so clear out the junk bits.
459 exceptions &= (1ULL << (num - i)) - 1;
461 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
462 unsigned idx = (ffsll(exceptions) - 1) + i;
463 out[idx] = bs.read();
466 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
470 // PFor block with bitmap exceptions. Layout:
472 // - Bit width (6 bits) | type << 6
473 // - Exception bit width (8 bits)
474 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
475 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
476 // - Base values (<num> values of <bits> bits, rounded up to a byte)
478 // Can read 4 bytes past the end of the input (inherit from BitReader).
479 template<class Docid>
480 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
482 memset(out, 0, num * sizeof(Docid));
484 const unsigned bit_width = *in++ & 0x3f;
486 in = decode_pfor_bitmap_exceptions(in, num, out);
488 // Decode the base values, and delta-decode.
489 Docid prev_val = out[-1];
490 BitReader bs(in, bit_width);
491 for (unsigned i = 0; i < num; ++i) {
492 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
494 return in + bytes_for_packed_bits(num, bit_width);
497 // Like decode_pfor_bitmap(), but the base values are organized in four
498 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
500 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReader
501 // and decode_pfor_bitmap_exceptions()).
502 template<unsigned BlockSize, class Docid>
503 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
505 memset(out, 0, BlockSize * sizeof(Docid));
507 const unsigned bit_width = *in++ & 0x3f;
509 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
511 // Decode the base values.
512 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
513 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
514 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
515 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
516 for (unsigned i = 0; i < BlockSize / 4; ++i) {
517 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
518 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
519 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
520 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
524 Docid prev_val = out[-1];
525 for (unsigned i = 0; i < BlockSize; ++i) {
526 out[i] = prev_val = out[i] + prev_val + 1;
528 return in + bytes_for_packed_bits(BlockSize, bit_width);
531 // Can read 16 bytes past the end of the input (inherit from decode_pfor_bitmap_interleaved_generic()).
532 template<unsigned BlockSize, class Docid>
533 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
535 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
536 return decode_pfor_bitmap_interleaved_128_32(in, out);
538 return decode_pfor_bitmap_interleaved_generic(in, out);
542 __attribute__((target("default")))
543 const unsigned char *
544 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
546 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
549 #ifdef COULD_HAVE_SSE2
550 // Specialized version for SSE2.
552 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReaderSSE2
553 // and decode_pfor_bitmap_exceptions()).
554 __attribute__((target("sse2")))
555 const unsigned char *
556 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
558 constexpr unsigned BlockSize = 128;
560 // Set all output values to zero, before the exceptions are filled in.
562 for (unsigned i = 0; i < BlockSize / 4; ++i) {
563 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
566 const unsigned bit_width = *in++ & 0x3f;
568 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
569 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
575 // PFor block with variable-byte exceptions. Layout:
577 // - Bit width (6 bits) | type << 6
578 // - Number of exceptions (8 bits)
579 // - Base values (<num> values of <bits> bits, rounded up to a byte)
581 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
582 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
583 // - Indexes of exceptions (<num_exc> bytes).
585 // Can read 4 bytes past the end of the input (inherit from BitReader,
586 // assuming zero exceptions).
587 template<unsigned BlockSize, class Docid>
588 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
590 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
592 const unsigned bit_width = *in++ & 0x3f;
593 unsigned num_exceptions = *in++;
595 // Decode the base values.
596 BitReader bs(in, bit_width);
597 for (unsigned i = 0; i < num; ++i) {
600 in += bytes_for_packed_bits(num, bit_width);
602 // Decode exceptions.
603 Docid exceptions[BlockSize];
606 for (unsigned i = 0; i < num_exceptions; ++i) {
607 exceptions[i] = read_le<Docid>(in);
611 for (unsigned i = 0; i < num_exceptions; ++i) {
612 in = read_vb(in, &exceptions[i]);
616 for (unsigned i = 0; i < num_exceptions; ++i) {
617 unsigned idx = *in++;
618 out[idx] |= exceptions[i] << bit_width;
622 Docid prev_val = out[-1];
623 for (unsigned i = 0; i < num; ++i) {
624 out[i] = prev_val = out[i] + prev_val + 1;
630 // Like decode_pfor_vb(), but the base values are organized in four
631 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
632 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
633 template<unsigned BlockSize, class Docid>
634 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
636 const unsigned bit_width = *in++ & 0x3f;
637 unsigned num_exceptions = *in++;
639 // Decode the base values.
640 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
641 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
642 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
643 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
644 for (unsigned i = 0; i < BlockSize / 4; ++i) {
645 out[i * 4 + 0] = bs0.read();
646 out[i * 4 + 1] = bs1.read();
647 out[i * 4 + 2] = bs2.read();
648 out[i * 4 + 3] = bs3.read();
650 in += bytes_for_packed_bits(BlockSize, bit_width);
652 // Decode exceptions.
653 Docid exceptions[BlockSize];
656 for (unsigned i = 0; i < num_exceptions; ++i) {
657 exceptions[i] = read_le<Docid>(in);
661 for (unsigned i = 0; i < num_exceptions; ++i) {
662 in = read_vb(in, &exceptions[i]);
667 for (unsigned i = 0; i < num_exceptions; ++i) {
668 unsigned idx = *in++;
669 out[idx] |= exceptions[i] << bit_width;
673 Docid prev_val = out[-1];
674 for (unsigned i = 0; i < BlockSize; ++i) {
675 out[i] = prev_val = out[i] + prev_val + 1;
681 // Can read 16 bytes past the end of its input (inherit from decode_pfor_vb_interleaved_generic()).
682 template<unsigned BlockSize, class Docid>
683 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
685 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
686 return decode_pfor_vb_interleaved_128_32(in, out);
688 return decode_pfor_vb_interleaved_generic(in, out);
692 __attribute__((target("default")))
693 const unsigned char *
694 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
696 return decode_pfor_vb_interleaved_generic<128>(in, out);
699 // Specialized version for SSE2.
700 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
701 __attribute__((target("sse2")))
702 const unsigned char *
703 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
705 constexpr unsigned BlockSize = 128;
706 using Docid = uint32_t;
708 const unsigned bit_width = *in++ & 0x3f;
709 unsigned num_exceptions = *in++;
711 // Decode the base values.
712 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
714 // Decode exceptions.
715 Docid exceptions[BlockSize];
718 for (unsigned i = 0; i < num_exceptions; ++i) {
719 exceptions[i] = read_le<Docid>(in);
723 for (unsigned i = 0; i < num_exceptions; ++i) {
724 in = read_vb(in, &exceptions[i]);
729 for (unsigned i = 0; i < num_exceptions; ++i) {
730 unsigned idx = *in++;
731 out[idx] |= exceptions[i] << bit_width;
734 delta_decode_sse2<BlockSize>(out);
739 // Can read 16 bytes past the end of the input (inherit from several functions).
740 template<unsigned BlockSize, class Docid>
741 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
746 in = read_baseval(in, out++);
748 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
749 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
750 switch (in[0] >> 6) {
752 if (interleaved && num_this_block == BlockSize) {
753 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
754 in = decode_for_interleaved<BlockSize>(in, out);
756 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
757 in = decode_for(in, num_this_block, out);
760 case BlockType::PFOR_VB:
761 if (interleaved && num_this_block == BlockSize) {
762 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
763 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
765 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
766 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
769 case BlockType::PFOR_BITMAP:
770 if (interleaved && num_this_block == BlockSize) {
771 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
772 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
774 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
775 in = decode_pfor_bitmap(in, num_this_block, out);
778 case BlockType::CONSTANT:
779 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
780 in = decode_constant(in, num_this_block, out);
788 const unsigned char *decode_pfor_delta1_128(const unsigned char *in, unsigned num, bool interleaved, uint32_t *out)
790 return decode_pfor_delta1<128>(in, num, interleaved, out);