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
24 #if defined(__i386__) || defined(__x86_64__)
25 #define COULD_HAVE_SSE2
26 #include <immintrin.h>
29 // Forward declarations to declare to the template code below that they exist.
30 // (These must seemingly be non-templates for function multiversioning to work.)
31 __attribute__((target("default")))
32 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
33 __attribute__((target("default")))
34 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
35 __attribute__((target("default")))
36 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
38 #ifdef COULD_HAVE_SSE2
39 __attribute__((target("sse2")))
40 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
41 __attribute__((target("sse2")))
42 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
43 __attribute__((target("sse2")))
44 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
47 constexpr uint32_t mask_for_bits(unsigned bit_width)
49 if (bit_width == 32) {
52 return (1U << bit_width) - 1;
57 Docid read_le(const void *in)
60 memcpy(&val, in, sizeof(val));
61 if constexpr (sizeof(Docid) == 8) {
63 } else if constexpr (sizeof(Docid) == 4) {
65 } else if constexpr (sizeof(Docid) == 2) {
67 } else if constexpr (sizeof(Docid) == 1) {
74 // Reads a single value with an encoding that looks a bit like PrefixVarint.
75 // It's unclear why this doesn't use the varbyte encoding.
77 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
79 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
83 } else if (*in < 192) {
84 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
86 } else if (*in < 224) {
87 *out = ((uint32_t(in[0]) << 16) |
88 (uint32_t(in[2]) << 8) |
89 (uint32_t(in[1]))) & 0x1fffff;
92 assert(false); // Not implemented.
97 const unsigned char *read_vb(const unsigned char *in, Docid *out)
102 } else if (*in <= 240) {
103 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
105 } else if (*in <= 248) {
106 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
108 } else if (*in == 249) {
109 *out = (uint32_t(in[1])) |
110 (uint32_t(in[2]) << 8) |
111 (uint32_t(in[3]) << 16);
113 } else if (*in == 250) {
114 *out = read_le<uint32_t>(in + 1);
123 BitReader(const unsigned char *in, unsigned bits)
124 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
127 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
137 const unsigned char *in;
140 unsigned bits_used = 0;
143 template<unsigned NumStreams>
144 struct InterleavedBitReader {
146 InterleavedBitReader(const unsigned char *in, unsigned bits)
147 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
151 if (bits_used + bits > 32) {
152 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
154 val = (read_le<uint32_t>(in) >> bits_used);
158 in += Stride * (bits_used / 32);
165 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
166 const unsigned char *in;
169 unsigned bits_used = 0;
172 #ifdef COULD_HAVE_SSE2
173 struct InterleavedBitReaderSSE2 {
175 __attribute__((target("sse2")))
176 InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
177 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
179 __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 // Does not properly account for overflow.
203 inline unsigned div_round_up(unsigned val, unsigned div)
205 return (val + div - 1) / div;
208 inline unsigned bytes_for_packed_bits(unsigned num, unsigned bit_width)
210 return div_round_up(num * bit_width, CHAR_BIT);
213 // Constant block. Layout:
215 // - Bit width (6 bits) | type << 6
216 // - Base values (<bits> bits, rounded up to nearest byte)
217 template<class Docid>
218 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
220 const unsigned bit_width = *in++ & 0x3f;
221 Docid val = read_le<Docid>(in);
222 if (bit_width < sizeof(Docid) * 8) {
223 val &= mask_for_bits(bit_width);
226 Docid prev_val = out[-1];
227 for (unsigned i = 0; i < num; ++i) {
228 out[i] = prev_val = val + prev_val + 1;
230 return in + div_round_up(bit_width, 8);
233 // FOR block (ie., PFor without exceptions). Layout:
235 // - Bit width (6 bits) | type << 6
236 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
237 template<class Docid>
238 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
240 const unsigned bit_width = *in++ & 0x3f;
242 Docid prev_val = out[-1];
243 BitReader bs(in, bit_width);
244 for (unsigned i = 0; i < num; ++i) {
245 prev_val = out[i] = bs.read() + prev_val + 1;
247 return in + bytes_for_packed_bits(num, bit_width);
250 #ifdef COULD_HAVE_SSE2
251 class DeltaDecoderSSE2 {
253 __attribute__((target("sse2")))
254 DeltaDecoderSSE2(uint32_t prev_val) : prev_val(_mm_set1_epi32(prev_val)) {}
256 __attribute__((target("sse2")))
257 __m128i decode(__m128i val) {
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")))
275 inline void delta_decode_sse2(uint32_t *out)
277 DeltaDecoderSSE2 delta(out[-1]);
278 __m128i *outvec = reinterpret_cast<__m128i *>(out);
279 for (unsigned i = 0; i < BlockSize / 4; ++i) {
280 __m128i val = _mm_loadu_si128(outvec + i);
281 _mm_storeu_si128(outvec + i, delta.decode(val));
285 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
286 __attribute__((target("sse2")))
287 const unsigned char *decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
289 __m128i *outvec = reinterpret_cast<__m128i *>(out);
290 DeltaDecoderSSE2 delta(out[-1]);
291 InterleavedBitReaderSSE2 bs(in, bit_width);
292 #pragma GCC unroll 32
293 for (unsigned i = 0; i < BlockSize / 4; ++i) {
294 __m128i val = bs.read();
295 if constexpr (OrWithExisting) {
296 val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
298 if constexpr (DeltaDecode) {
299 val = delta.decode(val);
301 _mm_storeu_si128(outvec + i, val);
303 in += bytes_for_packed_bits(BlockSize, bit_width);
307 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
308 __attribute__((target("sse2")))
309 const unsigned char *decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
312 case 0: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
313 case 1: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
314 case 2: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
315 case 3: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
316 case 4: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
317 case 5: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
318 case 6: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
319 case 7: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
320 case 8: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
321 case 9: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
322 case 10: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
323 case 11: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
324 case 12: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
325 case 13: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
326 case 14: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
327 case 15: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
328 case 16: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
329 case 17: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
330 case 18: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
331 case 19: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
332 case 20: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
333 case 21: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
334 case 22: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
335 case 23: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
336 case 24: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
337 case 25: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
338 case 26: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
339 case 27: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
340 case 28: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
341 case 29: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
342 case 30: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
343 case 31: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
344 case 32: return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
350 // Like decode_for(), but the values are organized in four independent streams,
351 // for SIMD (presumably SSE2). Supports a whole block only.
352 template<unsigned BlockSize, class Docid>
353 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
355 const unsigned bit_width = *in++ & 0x3f;
357 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
358 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
359 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
360 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
361 for (unsigned i = 0; i < BlockSize / 4; ++i) {
362 out[i * 4 + 0] = bs0.read();
363 out[i * 4 + 1] = bs1.read();
364 out[i * 4 + 2] = bs2.read();
365 out[i * 4 + 3] = bs3.read();
367 Docid prev_val = out[-1];
368 for (unsigned i = 0; i < BlockSize; ++i) {
369 out[i] = prev_val = out[i] + prev_val + 1;
371 return in + bytes_for_packed_bits(BlockSize, bit_width);
374 template<unsigned BlockSize, class Docid>
375 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
377 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
378 return decode_for_interleaved_128_32(in, out);
380 return decode_for_interleaved_generic(in, out);
384 __attribute__((target("default")))
385 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
387 return decode_for_interleaved_generic<128>(in, out);
390 #ifdef COULD_HAVE_SSE2
391 // Specialized version for SSE2.
392 __attribute__((target("sse2")))
393 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
395 constexpr unsigned BlockSize = 128;
397 const unsigned bit_width = *in++ & 0x3f;
399 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
405 template<class Docid>
406 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
408 const unsigned exception_bit_width = *in++;
409 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
410 in += div_round_up(num, 8);
412 int num_exceptions = 0;
414 BitReader bs(in, exception_bit_width);
415 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
416 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
418 // We've read some bytes past the end, so clear out the junk bits.
419 exceptions &= (1ULL << (num - i)) - 1;
421 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
422 unsigned idx = (ffsll(exceptions) - 1) + i;
423 out[idx] = bs.read();
426 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
430 // PFor block with bitmap exceptions. Layout:
432 // - Bit width (6 bits) | type << 6
433 // - Exception bit width (8 bits)
434 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
435 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
436 // - Base values (<num> values of <bits> bits, rounded up to a byte)
437 template<class Docid>
438 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
440 memset(out, 0, num * sizeof(Docid));
442 const unsigned bit_width = *in++ & 0x3f;
444 in = decode_pfor_bitmap_exceptions(in, num, out);
446 // Decode the base values, and delta-decode.
447 Docid prev_val = out[-1];
448 BitReader bs(in, bit_width);
449 for (unsigned i = 0; i < num; ++i) {
450 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
452 return in + bytes_for_packed_bits(num, bit_width);
455 // Like decode_pfor_bitmap(), but the base values are organized in four
456 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
457 template<unsigned BlockSize, class Docid>
458 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
460 memset(out, 0, BlockSize * sizeof(Docid));
462 const unsigned bit_width = *in++ & 0x3f;
464 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
466 // Decode the base values.
467 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
468 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
469 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
470 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
471 for (unsigned i = 0; i < BlockSize / 4; ++i) {
472 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
473 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
474 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
475 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
479 Docid prev_val = out[-1];
480 for (unsigned i = 0; i < BlockSize; ++i) {
481 out[i] = prev_val = out[i] + prev_val + 1;
483 return in + bytes_for_packed_bits(BlockSize, bit_width);
486 template<unsigned BlockSize, class Docid>
487 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
489 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
490 return decode_pfor_bitmap_interleaved_128_32(in, out);
492 return decode_pfor_bitmap_interleaved_generic(in, out);
496 __attribute__((target("default")))
497 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
499 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
502 #ifdef COULD_HAVE_SSE2
503 // Specialized version for SSE2.
504 __attribute__((target("sse2")))
505 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
507 constexpr unsigned BlockSize = 128;
509 // Set all output values to zero, before the exceptions are filled in.
511 for (unsigned i = 0; i < BlockSize / 4; ++i) {
512 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
515 const unsigned bit_width = *in++ & 0x3f;
517 in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
518 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
524 // PFor block with variable-byte exceptions. Layout:
526 // - Bit width (6 bits) | type << 6
527 // - Number of exceptions (8 bits)
528 // - Base values (<num> values of <bits> bits, rounded up to a byte)
530 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
531 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
532 // - Indexes of exceptions (<num_exc> bytes).
533 template<unsigned BlockSize, class Docid>
534 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
536 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
538 const unsigned bit_width = *in++ & 0x3f;
539 unsigned num_exceptions = *in++;
541 // Decode the base values.
542 BitReader bs(in, bit_width);
543 for (unsigned i = 0; i < num; ++i) {
546 in += bytes_for_packed_bits(num, bit_width);
548 // Decode exceptions.
549 Docid exceptions[BlockSize];
552 for (unsigned i = 0; i < num_exceptions; ++i) {
553 exceptions[i] = read_le<Docid>(in);
557 for (unsigned i = 0; i < num_exceptions; ++i) {
558 in = read_vb(in, &exceptions[i]);
562 for (unsigned i = 0; i < num_exceptions; ++i) {
563 unsigned idx = *in++;
564 out[idx] |= exceptions[i] << bit_width;
568 Docid prev_val = out[-1];
569 for (unsigned i = 0; i < num; ++i) {
570 out[i] = prev_val = out[i] + prev_val + 1;
576 // Like decode_pfor_vb(), but the base values are organized in four
577 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
578 template<unsigned BlockSize, class Docid>
579 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
581 const unsigned bit_width = *in++ & 0x3f;
582 unsigned num_exceptions = *in++;
584 // Decode the base values.
585 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
586 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
587 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
588 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
589 for (unsigned i = 0; i < BlockSize / 4; ++i) {
590 out[i * 4 + 0] = bs0.read();
591 out[i * 4 + 1] = bs1.read();
592 out[i * 4 + 2] = bs2.read();
593 out[i * 4 + 3] = bs3.read();
595 in += bytes_for_packed_bits(BlockSize, bit_width);
597 // Decode exceptions.
598 Docid exceptions[BlockSize];
601 for (unsigned i = 0; i < num_exceptions; ++i) {
602 exceptions[i] = read_le<Docid>(in);
606 for (unsigned i = 0; i < num_exceptions; ++i) {
607 in = read_vb(in, &exceptions[i]);
612 for (unsigned i = 0; i < num_exceptions; ++i) {
613 unsigned idx = *in++;
614 out[idx] |= exceptions[i] << bit_width;
618 Docid prev_val = out[-1];
619 for (unsigned i = 0; i < BlockSize; ++i) {
620 out[i] = prev_val = out[i] + prev_val + 1;
626 template<unsigned BlockSize, class Docid>
627 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
629 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
630 return decode_pfor_vb_interleaved_128_32(in, out);
632 return decode_pfor_vb_interleaved_generic(in, out);
636 __attribute__((target("default")))
637 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
639 return decode_pfor_vb_interleaved_generic<128>(in, out);
642 // Specialized version for SSE2.
643 __attribute__((target("sse2")))
644 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
646 constexpr unsigned BlockSize = 128;
647 using Docid = uint32_t;
649 const unsigned bit_width = *in++ & 0x3f;
650 unsigned num_exceptions = *in++;
652 // Decode the base values.
653 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
655 // Decode exceptions.
656 Docid exceptions[BlockSize];
659 for (unsigned i = 0; i < num_exceptions; ++i) {
660 exceptions[i] = read_le<Docid>(in);
664 for (unsigned i = 0; i < num_exceptions; ++i) {
665 in = read_vb(in, &exceptions[i]);
670 for (unsigned i = 0; i < num_exceptions; ++i) {
671 unsigned idx = *in++;
672 out[idx] |= exceptions[i] << bit_width;
675 delta_decode_sse2<BlockSize>(out);
687 template<unsigned BlockSize, class Docid>
688 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
693 in = read_baseval(in, out++);
695 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
696 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
697 switch (in[0] >> 6) {
699 if (interleaved && num_this_block == BlockSize) {
700 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
701 in = decode_for_interleaved<BlockSize>(in, out);
703 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
704 in = decode_for(in, num_this_block, out);
707 case BlockType::PFOR_VB:
708 if (interleaved && num_this_block == BlockSize) {
709 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
710 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
712 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
713 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
716 case BlockType::PFOR_BITMAP:
717 if (interleaved && num_this_block == BlockSize) {
718 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
719 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
721 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
722 in = decode_pfor_bitmap(in, num_this_block, out);
725 case BlockType::CONSTANT:
726 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
727 in = decode_constant(in, num_this_block, out);
735 #endif // !defined(_TURBOPFOR_H)