8 #if defined(__i386__) || defined(__x86_64__)
9 #define COULD_HAVE_SSE2
10 #include <immintrin.h>
11 #define TARGET_DEFAULT __attribute__((target("default")))
13 // Function multiversioning is x86-only.
14 #define TARGET_DEFAULT
17 #include "turbopfor-common.h"
20 //#define dprintf(...) fprintf(stderr, __VA_ARGS__);
22 // Forward declarations to declare to the template code below that they exist.
23 // (These must seemingly be non-templates for function multiversioning to work.)
26 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
29 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
32 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
34 #ifdef COULD_HAVE_SSE2
35 __attribute__((target("sse2")))
37 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
38 __attribute__((target("sse2")))
40 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
41 __attribute__((target("sse2")))
43 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
47 Docid read_le(const void *in)
50 memcpy(&val, in, sizeof(val));
51 if constexpr (sizeof(Docid) == 8) {
53 } else if constexpr (sizeof(Docid) == 4) {
55 } else if constexpr (sizeof(Docid) == 2) {
57 } else if constexpr (sizeof(Docid) == 1) {
64 // Reads a single value with an encoding that looks a bit like PrefixVarint.
65 // It's unclear why this doesn't use the varbyte encoding.
67 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
69 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
73 } else if (*in < 192) {
74 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
76 } else if (*in < 224) {
77 *out = ((uint32_t(in[0]) << 16) |
78 (uint32_t(in[2]) << 8) |
79 (uint32_t(in[1]))) & 0x1fffff;
81 } else if (*in < 240) {
82 *out = ((uint32_t(in[0]) << 24) |
83 (uint32_t(in[1]) << 16) |
84 (uint32_t(in[2]) << 8) |
85 (uint32_t(in[3]))) & 0xfffffff;
88 assert(false); // Not implemented.
92 // Does not read past the end of the input.
94 const unsigned char *read_vb(const unsigned char *in, Docid *out)
99 } else if (*in <= 240) {
100 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
102 } else if (*in <= 248) {
103 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
105 } else if (*in == 249) {
106 *out = (uint32_t(in[1])) |
107 (uint32_t(in[2]) << 8) |
108 (uint32_t(in[3]) << 16);
110 } else if (*in == 250) {
111 *out = read_le<uint32_t>(in + 1);
120 BitReader(const unsigned char *in, unsigned bits)
121 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
123 // Can read 4 bytes past the end of the input (if bits_used == 0).
126 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
136 const unsigned char *in;
139 unsigned bits_used = 0;
142 template<unsigned NumStreams>
143 struct InterleavedBitReader {
145 InterleavedBitReader(const unsigned char *in, unsigned bits)
146 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
148 // Can read 4 bytes past the end of the input (if bit_width == 0).
152 if (bits_used + bits > 32) {
153 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
155 val = (read_le<uint32_t>(in) >> bits_used);
159 in += Stride * (bits_used / 32);
166 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
167 const unsigned char *in;
170 unsigned bits_used = 0;
173 #ifdef COULD_HAVE_SSE2
174 struct InterleavedBitReaderSSE2 {
176 __attribute__((target("sse2")))
177 InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
178 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
180 // Can read 16 bytes past the end of the input (if bit_width == 0).
181 __attribute__((target("sse2")))
185 __m128i val = _mm_srli_epi32(_mm_loadu_si128(in), bits_used);
186 if (bits_used + bits > 32) {
187 __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(in + 1), 32 - bits_used);
188 val = _mm_or_si128(val, val_upper);
190 val = _mm_and_si128(val, mask);
193 in += bits_used / 32;
202 unsigned bits_used = 0;
206 // Constant block. Layout:
208 // - Bit width (6 bits) | type << 6
209 // - Base values (<bits> bits, rounded up to nearest byte)
211 // Can read 4 bytes past the end of the input (if bit_width == 0).
212 template<class Docid>
213 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
215 const unsigned bit_width = *in++ & 0x3f;
216 Docid val = read_le<Docid>(in);
217 if (bit_width < sizeof(Docid) * 8) {
218 val &= mask_for_bits(bit_width);
221 Docid prev_val = out[-1];
222 for (unsigned i = 0; i < num; ++i) {
223 out[i] = prev_val = val + prev_val + 1;
225 return in + div_round_up(bit_width, 8);
228 // FOR block (ie., PFor without exceptions). Layout:
230 // - Bit width (6 bits) | type << 6
231 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
233 // Can read 4 bytes past the end of the input (inherit from BitReader).
234 template<class Docid>
235 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
237 const unsigned bit_width = *in++ & 0x3f;
239 Docid prev_val = out[-1];
240 BitReader bs(in, bit_width);
241 for (unsigned i = 0; i < num; ++i) {
242 prev_val = out[i] = bs.read() + prev_val + 1;
244 return in + bytes_for_packed_bits(num, bit_width);
247 #ifdef COULD_HAVE_SSE2
248 class DeltaDecoderSSE2 {
250 __attribute__((target("sse2")))
251 DeltaDecoderSSE2(uint32_t prev_val)
252 : prev_val(_mm_set1_epi32(prev_val)) {}
254 __attribute__((target("sse2")))
258 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
259 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
260 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
261 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
266 // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
267 // in parallel with something else.
268 const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
273 template<unsigned BlockSize>
274 __attribute__((target("sse2"))) inline void delta_decode_sse2(uint32_t *out)
276 DeltaDecoderSSE2 delta(out[-1]);
277 __m128i *outvec = reinterpret_cast<__m128i *>(out);
278 for (unsigned i = 0; i < BlockSize / 4; ++i) {
279 __m128i val = _mm_loadu_si128(outvec + i);
280 _mm_storeu_si128(outvec + i, delta.decode(val));
284 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
285 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
286 __attribute__((target("sse2")))
287 const unsigned char *
288 decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
290 __m128i *outvec = reinterpret_cast<__m128i *>(out);
291 DeltaDecoderSSE2 delta(out[-1]);
292 InterleavedBitReaderSSE2 bs(in, bit_width);
293 #pragma GCC unroll 32
294 for (unsigned i = 0; i < BlockSize / 4; ++i) {
295 __m128i val = bs.read();
296 if constexpr (OrWithExisting) {
297 val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
299 if constexpr (DeltaDecode) {
300 val = delta.decode(val);
302 _mm_storeu_si128(outvec + i, val);
304 in += bytes_for_packed_bits(BlockSize, bit_width);
308 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReaderSSE2).
309 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
310 __attribute__((target("sse2")))
311 const unsigned char *
312 decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
316 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
318 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
320 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
322 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
324 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
326 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
328 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
330 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
332 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
334 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
336 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
338 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
340 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
342 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
344 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
346 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
348 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
350 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
352 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
354 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
356 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
358 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
360 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
362 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
364 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
366 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
368 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
370 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
372 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
374 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
376 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
378 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
380 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
386 // Like decode_for(), but the values are organized in four independent streams,
387 // for SIMD (presumably SSE2). Supports a whole block only.
389 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
390 template<unsigned BlockSize, class Docid>
391 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
393 const unsigned bit_width = *in++ & 0x3f;
395 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
396 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
397 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
398 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
399 for (unsigned i = 0; i < BlockSize / 4; ++i) {
400 out[i * 4 + 0] = bs0.read();
401 out[i * 4 + 1] = bs1.read();
402 out[i * 4 + 2] = bs2.read();
403 out[i * 4 + 3] = bs3.read();
405 Docid prev_val = out[-1];
406 for (unsigned i = 0; i < BlockSize; ++i) {
407 out[i] = prev_val = out[i] + prev_val + 1;
409 return in + bytes_for_packed_bits(BlockSize, bit_width);
412 // Does not read past the end of the input.
413 template<unsigned BlockSize, class Docid>
414 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
416 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
417 return decode_for_interleaved_128_32(in, out);
419 return decode_for_interleaved_generic(in, out);
423 // Does not read past the end of the input.
425 const unsigned char *
426 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
428 return decode_for_interleaved_generic<128>(in, out);
431 #ifdef COULD_HAVE_SSE2
432 // Specialized version for SSE2.
433 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
434 __attribute__((target("sse2")))
435 const unsigned char *
436 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
438 constexpr unsigned BlockSize = 128;
440 const unsigned bit_width = *in++ & 0x3f;
442 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
448 // Can read 4 bytes past the end of the input (inherit from BitReader).
449 template<class Docid>
450 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
452 const unsigned exception_bit_width = *in++;
453 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
454 in += div_round_up(num, 8);
456 int num_exceptions = 0;
458 BitReader bs(in, exception_bit_width);
459 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
460 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
462 // We've read some bytes past the end, so clear out the junk bits.
463 exceptions &= (1ULL << (num - i)) - 1;
465 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
466 unsigned idx = (ffsll(exceptions) - 1) + i;
467 out[idx] = bs.read();
470 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
474 // PFor block with bitmap exceptions. Layout:
476 // - Bit width (6 bits) | type << 6
477 // - Exception bit width (8 bits)
478 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
479 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
480 // - Base values (<num> values of <bits> bits, rounded up to a byte)
482 // Can read 4 bytes past the end of the input (inherit from BitReader).
483 template<class Docid>
484 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
486 memset(out, 0, num * sizeof(Docid));
488 const unsigned bit_width = *in++ & 0x3f;
490 in = decode_pfor_bitmap_exceptions(in, num, out);
492 // Decode the base values, and delta-decode.
493 Docid prev_val = out[-1];
494 BitReader bs(in, bit_width);
495 for (unsigned i = 0; i < num; ++i) {
496 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
498 return in + bytes_for_packed_bits(num, bit_width);
501 // Like decode_pfor_bitmap(), but the base values are organized in four
502 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
504 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReader
505 // and decode_pfor_bitmap_exceptions()).
506 template<unsigned BlockSize, class Docid>
507 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
509 memset(out, 0, BlockSize * sizeof(Docid));
511 const unsigned bit_width = *in++ & 0x3f;
513 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
515 // Decode the base values.
516 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
517 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
518 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
519 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
520 for (unsigned i = 0; i < BlockSize / 4; ++i) {
521 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
522 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
523 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
524 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
528 Docid prev_val = out[-1];
529 for (unsigned i = 0; i < BlockSize; ++i) {
530 out[i] = prev_val = out[i] + prev_val + 1;
532 return in + bytes_for_packed_bits(BlockSize, bit_width);
535 // Can read 16 bytes past the end of the input (inherit from decode_pfor_bitmap_interleaved_generic()).
536 template<unsigned BlockSize, class Docid>
537 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
539 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
540 return decode_pfor_bitmap_interleaved_128_32(in, out);
542 return decode_pfor_bitmap_interleaved_generic(in, out);
547 const unsigned char *
548 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
550 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
553 #ifdef COULD_HAVE_SSE2
554 // Specialized version for SSE2.
556 // Can read 16 bytes past the end of the input (inherit from InterleavedBitReaderSSE2
557 // and decode_pfor_bitmap_exceptions()).
558 __attribute__((target("sse2")))
559 const unsigned char *
560 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
562 constexpr unsigned BlockSize = 128;
564 // Set all output values to zero, before the exceptions are filled in.
566 for (unsigned i = 0; i < BlockSize / 4; ++i) {
567 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
570 const unsigned bit_width = *in++ & 0x3f;
572 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
573 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
579 // PFor block with variable-byte exceptions. Layout:
581 // - Bit width (6 bits) | type << 6
582 // - Number of exceptions (8 bits)
583 // - Base values (<num> values of <bits> bits, rounded up to a byte)
585 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
586 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
587 // - Indexes of exceptions (<num_exc> bytes).
589 // Can read 4 bytes past the end of the input (inherit from BitReader,
590 // assuming zero exceptions).
591 template<unsigned BlockSize, class Docid>
592 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
594 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
596 const unsigned bit_width = *in++ & 0x3f;
597 unsigned num_exceptions = *in++;
599 // Decode the base values.
600 BitReader bs(in, bit_width);
601 for (unsigned i = 0; i < num; ++i) {
604 in += bytes_for_packed_bits(num, bit_width);
606 // Decode exceptions.
607 Docid exceptions[BlockSize];
610 for (unsigned i = 0; i < num_exceptions; ++i) {
611 exceptions[i] = read_le<Docid>(in);
615 for (unsigned i = 0; i < num_exceptions; ++i) {
616 in = read_vb(in, &exceptions[i]);
620 for (unsigned i = 0; i < num_exceptions; ++i) {
621 unsigned idx = *in++;
622 out[idx] |= exceptions[i] << bit_width;
626 Docid prev_val = out[-1];
627 for (unsigned i = 0; i < num; ++i) {
628 out[i] = prev_val = out[i] + prev_val + 1;
634 // Like decode_pfor_vb(), but the base values are organized in four
635 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
636 // Can read 16 bytes past the end of its input (inherit from InterleavedBitReader).
637 template<unsigned BlockSize, class Docid>
638 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
640 const unsigned bit_width = *in++ & 0x3f;
641 unsigned num_exceptions = *in++;
643 // Decode the base values.
644 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
645 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
646 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
647 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
648 for (unsigned i = 0; i < BlockSize / 4; ++i) {
649 out[i * 4 + 0] = bs0.read();
650 out[i * 4 + 1] = bs1.read();
651 out[i * 4 + 2] = bs2.read();
652 out[i * 4 + 3] = bs3.read();
654 in += bytes_for_packed_bits(BlockSize, bit_width);
656 // Decode exceptions.
657 Docid exceptions[BlockSize];
660 for (unsigned i = 0; i < num_exceptions; ++i) {
661 exceptions[i] = read_le<Docid>(in);
665 for (unsigned i = 0; i < num_exceptions; ++i) {
666 in = read_vb(in, &exceptions[i]);
671 for (unsigned i = 0; i < num_exceptions; ++i) {
672 unsigned idx = *in++;
673 out[idx] |= exceptions[i] << bit_width;
677 Docid prev_val = out[-1];
678 for (unsigned i = 0; i < BlockSize; ++i) {
679 out[i] = prev_val = out[i] + prev_val + 1;
685 // Can read 16 bytes past the end of its input (inherit from decode_pfor_vb_interleaved_generic()).
686 template<unsigned BlockSize, class Docid>
687 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
689 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
690 return decode_pfor_vb_interleaved_128_32(in, out);
692 return decode_pfor_vb_interleaved_generic(in, out);
697 const unsigned char *
698 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
700 return decode_pfor_vb_interleaved_generic<128>(in, out);
703 #ifdef COULD_HAVE_SSE2
704 // Specialized version for SSE2.
705 // Can read 16 bytes past the end of the input (inherit from decode_bitmap_sse2()).
706 __attribute__((target("sse2")))
707 const unsigned char *
708 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
710 constexpr unsigned BlockSize = 128;
711 using Docid = uint32_t;
713 const unsigned bit_width = *in++ & 0x3f;
714 unsigned num_exceptions = *in++;
716 // Decode the base values.
717 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
719 // Decode exceptions.
720 Docid exceptions[BlockSize];
723 for (unsigned i = 0; i < num_exceptions; ++i) {
724 exceptions[i] = read_le<Docid>(in);
728 for (unsigned i = 0; i < num_exceptions; ++i) {
729 in = read_vb(in, &exceptions[i]);
734 for (unsigned i = 0; i < num_exceptions; ++i) {
735 unsigned idx = *in++;
736 out[idx] |= exceptions[i] << bit_width;
739 delta_decode_sse2<BlockSize>(out);
745 // Can read 16 bytes past the end of the input (inherit from several functions).
746 template<unsigned BlockSize, class Docid>
747 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
752 in = read_baseval(in, out++);
754 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
755 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
756 switch (in[0] >> 6) {
758 if (interleaved && num_this_block == BlockSize) {
759 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
760 in = decode_for_interleaved<BlockSize>(in, out);
762 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
763 in = decode_for(in, num_this_block, out);
766 case BlockType::PFOR_VB:
767 if (interleaved && num_this_block == BlockSize) {
768 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
769 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
771 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
772 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
775 case BlockType::PFOR_BITMAP:
776 if (interleaved && num_this_block == BlockSize) {
777 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
778 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
780 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
781 in = decode_pfor_bitmap(in, num_this_block, out);
784 case BlockType::CONSTANT:
785 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
786 in = decode_constant(in, num_this_block, out);
794 const unsigned char *decode_pfor_delta1_128(const unsigned char *in, unsigned num, bool interleaved, uint32_t *out)
796 return decode_pfor_delta1<128>(in, num, interleaved, out);