git.sesse.net Git - plocate/blob - turbopfor.h

   1 #ifndef _TURBOPFOR_H
   2 #define _TURBOPFOR_H 1
   3
   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 60% 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.
  11 //
  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
  14 // TurboPFor code.
  15
  16 #include <assert.h>
  17 #include <endian.h>
  18 #include <stdint.h>
  19 #include <string.h>
  20 #include <limits.h>
  21
  22 #include <algorithm>
  23
  24 #if defined(__i386__) || defined(__x86_64__)
  25 #define COULD_HAVE_SSE2
  26 #include <immintrin.h>
  27 #endif
  28
  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);
  37
  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);
  45 #endif
  46
  47 constexpr uint32_t mask_for_bits(unsigned bit_width)
  48 {
  49         if (bit_width == 32) {
  50                 return 0xFFFFFFFF;
  51         } else {
  52                 return (1U << bit_width) - 1;
  53         }
  54 }
  55
  56 template<class Docid>
  57 Docid read_le(const void *in)
  58 {
  59         Docid val;
  60         memcpy(&val, in, sizeof(val));
  61         if constexpr (sizeof(Docid) == 8) {
  62                 return le64toh(val);
  63         } else if constexpr (sizeof(Docid) == 4) {
  64                 return le32toh(val);
  65         } else if constexpr (sizeof(Docid) == 2) {
  66                 return le16toh(val);
  67         } else if constexpr (sizeof(Docid) == 1) {
  68                 return val;
  69         } else {
  70                 assert(false);
  71         }
  72 }
  73
  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.
  76 template<class Docid>
  77 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
  78 {
  79         //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
  80         if (*in < 128) {
  81                 *out = *in;
  82                 return in + 1;
  83         } else if (*in < 192) {
  84                 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
  85                 return in + 2;
  86         } else if (*in < 224) {
  87                 *out = ((uint32_t(in[0]) << 16) |
  88                         (uint32_t(in[2]) << 8) |
  89                         (uint32_t(in[1]))) & 0x1fffff;
  90                 return in + 3;
  91         } else {
  92                 assert(false);  // Not implemented.
  93         }
  94 }
  95
  96 template<class Docid>
  97 const unsigned char *read_vb(const unsigned char *in, Docid *out)
  98 {
  99         if (*in <= 176) {
 100                 *out = *in;
 101                 return in + 1;
 102         } else if (*in <= 240) {
 103                 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
 104                 return in + 2;
 105         } else if (*in <= 248) {
 106                 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
 107                 return in + 3;
 108         } else if (*in == 249) {
 109                 *out = (uint32_t(in[1])) |
 110                         (uint32_t(in[2]) << 8) |
 111                         (uint32_t(in[3]) << 16);
 112                 return in + 4;
 113         } else if (*in == 250) {
 114                 *out = read_le<uint32_t>(in + 1);
 115                 return in + 5;
 116         } else {
 117                 assert(false);
 118         }
 119 }
 120
 121 struct BitReader {
 122 public:
 123         BitReader(const unsigned char *in, unsigned bits)
 124                 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
 125         uint32_t read()
 126         {
 127                 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
 128
 129                 bits_used += bits;
 130                 in += bits_used / 8;
 131                 bits_used %= 8;
 132
 133                 return val;
 134         }
 135
 136 private:
 137         const unsigned char *in;
 138         const unsigned bits;
 139         const unsigned mask;
 140         unsigned bits_used = 0;
 141 };
 142
 143 template<unsigned NumStreams>
 144 struct InterleavedBitReader {
 145 public:
 146         InterleavedBitReader(const unsigned char *in, unsigned bits)
 147                 : in(in), bits(bits), mask(mask_for_bits(bits)) {}
 148         uint32_t read()
 149         {
 150                 uint32_t val;
 151                 if (bits_used + bits > 32) {
 152                         val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
 153                 } else {
 154                         val = (read_le<uint32_t>(in) >> bits_used);
 155                 }
 156
 157                 bits_used += bits;
 158                 in += Stride * (bits_used / 32);
 159                 bits_used %= 32;
 160
 161                 return val & mask;
 162         }
 163
 164 private:
 165         static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
 166         const unsigned char *in;
 167         const unsigned bits;
 168         const unsigned mask;
 169         unsigned bits_used = 0;
 170 };
 171
 172 #ifdef COULD_HAVE_SSE2
 173 struct InterleavedBitReaderSSE2 {
 174 public:
 175         InterleavedBitReaderSSE2(const unsigned char *in, unsigned bits)
 176                 : in(reinterpret_cast<const __m128i *>(in)), bits(bits), mask(_mm_set1_epi32(mask_for_bits(bits))) {}
 177         __m128i read() {
 178                 __m128i val = _mm_srli_epi32(_mm_loadu_si128(in), bits_used);
 179                 if (bits_used + bits > 32) {
 180                         __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(in + 1), 32 - bits_used);
 181                         val = _mm_or_si128(val, val_upper);
 182                 }
 183                 val = _mm_and_si128(val, mask);
 184
 185                 bits_used += bits;
 186                 in += bits_used / 32;
 187                 bits_used %= 32;
 188                 return val;
 189         }
 190
 191 private:
 192         const __m128i *in;
 193         const unsigned bits;
 194         const __m128i mask;
 195         unsigned bits_used = 0;
 196 };
 197 #endif
 198
 199 // Does not properly account for overflow.
 200 inline unsigned div_round_up(unsigned val, unsigned div)
 201 {
 202         return (val + div - 1) / div;
 203 }
 204
 205 inline unsigned bytes_for_packed_bits(unsigned num, unsigned bit_width)
 206 {
 207         return div_round_up(num * bit_width, CHAR_BIT);
 208 }
 209
 210 // Constant block. Layout:
 211 //
 212 //  - Bit width (6 bits) | type << 6
 213 //  - Base values (<bits> bits, rounded up to nearest byte)
 214 template<class Docid>
 215 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
 216 {
 217         const unsigned bit_width = *in++ & 0x3f;
 218         Docid val = read_le<Docid>(in);
 219         if (bit_width < sizeof(Docid) * 8) {
 220                 val &= mask_for_bits(bit_width);
 221         }
 222
 223         Docid prev_val = out[-1];
 224         for (unsigned i = 0; i < num; ++i) {
 225                 out[i] = prev_val = val + prev_val + 1;
 226         }
 227         return in + div_round_up(bit_width, 8);
 228 }
 229
 230 // FOR block (ie., PFor without exceptions). Layout:
 231 //
 232 //  - Bit width (6 bits) | type << 6
 233 //  - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
 234 template<class Docid>
 235 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
 236 {
 237         const unsigned bit_width = *in++ & 0x3f;
 238
 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;
 243         }
 244         return in + bytes_for_packed_bits(num, bit_width);
 245 }
 246
 247 #ifdef COULD_HAVE_SSE2
 248 class DeltaDecoderSSE2 {
 249 public:
 250         DeltaDecoderSSE2(uint32_t prev_val) : prev_val(_mm_set1_epi32(prev_val)) {}
 251         __m128i decode(__m128i val) {
 252                 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
 253                 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
 254                 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
 255                 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
 256                 return val;
 257         }
 258
 259 private:
 260         // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
 261         // in parallel with something else.
 262         const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
 263
 264         __m128i prev_val;
 265 };
 266
 267 template<unsigned BlockSize>
 268 __attribute__((target("sse2")))
 269 inline void delta_decode_sse2(uint32_t *out)
 270 {
 271         DeltaDecoderSSE2 delta(out[-1]);
 272         __m128i *outvec = reinterpret_cast<__m128i *>(out);
 273         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 274                 __m128i val = _mm_loadu_si128(outvec + i);
 275                 _mm_storeu_si128(outvec + i, delta.decode(val));
 276         }
 277 }
 278
 279 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
 280 __attribute__((target("sse2")))
 281 const unsigned char *decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
 282 {
 283         __m128i *outvec = reinterpret_cast<__m128i *>(out);
 284         DeltaDecoderSSE2 delta(out[-1]);
 285         InterleavedBitReaderSSE2 bs(in, bit_width);
 286         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 287                 __m128i val = bs.read();
 288                 if constexpr (OrWithExisting) {
 289                         val = _mm_or_si128(val, _mm_loadu_si128(outvec + i));
 290                 }
 291                 if constexpr (DeltaDecode) {
 292                         val = delta.decode(val);
 293                 }
 294                 _mm_storeu_si128(outvec + i, val);
 295         }
 296         in += bytes_for_packed_bits(BlockSize, bit_width);
 297         return in;
 298 }
 299 #endif
 300
 301 // Like decode_for(), but the values are organized in four independent streams,
 302 // for SIMD (presumably SSE2). Supports a whole block only.
 303 template<unsigned BlockSize, class Docid>
 304 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
 305 {
 306         const unsigned bit_width = *in++ & 0x3f;
 307
 308         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 309         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 310         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 311         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 312         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 313                 out[i * 4 + 0] = bs0.read();
 314                 out[i * 4 + 1] = bs1.read();
 315                 out[i * 4 + 2] = bs2.read();
 316                 out[i * 4 + 3] = bs3.read();
 317         }
 318         Docid prev_val = out[-1];
 319         for (unsigned i = 0; i < BlockSize; ++i) {
 320                 out[i] = prev_val = out[i] + prev_val + 1;
 321         }
 322         return in + bytes_for_packed_bits(BlockSize, bit_width);
 323 }
 324
 325 template<unsigned BlockSize, class Docid>
 326 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
 327 {
 328         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 329                 return decode_for_interleaved_128_32(in, out);
 330         } else {
 331                 return decode_for_interleaved_generic(in, out);
 332         }
 333 }
 334
 335 __attribute__((target("default")))
 336 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
 337 {
 338         return decode_for_interleaved_generic<128>(in, out);
 339 }
 340
 341 #ifdef COULD_HAVE_SSE2
 342 // Specialized version for SSE2.
 343 __attribute__((target("sse2")))
 344 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
 345 {
 346         constexpr unsigned BlockSize = 128;
 347
 348         const unsigned bit_width = *in++ & 0x3f;
 349
 350         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
 351
 352         return in;
 353 }
 354 #endif
 355
 356 template<class Docid>
 357 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, unsigned bit_width, Docid *out)
 358 {
 359         const unsigned exception_bit_width = *in++;
 360         const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
 361         in += div_round_up(num, 8);
 362
 363         int num_exceptions = 0;
 364
 365         BitReader bs(in, exception_bit_width);
 366         for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
 367                 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
 368                 if (num - i < 64) {
 369                         // We've read some bytes past the end, so clear out the junk bits.
 370                         exceptions &= (1ULL << (num - i)) - 1;
 371                 }
 372                 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
 373                         unsigned idx = (ffsll(exceptions) - 1) + i;
 374                         out[idx] = bs.read() << bit_width;
 375                 }
 376         }
 377         in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
 378         return in;
 379 }
 380
 381 // PFor block with bitmap exceptions. Layout:
 382 //
 383 //  - Bit width (6 bits) | type << 6
 384 //  - Exception bit width (8 bits)
 385 //  - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
 386 //  - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
 387 //  - Base values (<num> values of <bits> bits, rounded up to a byte)
 388 template<class Docid>
 389 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
 390 {
 391         memset(out, 0, num * sizeof(Docid));
 392
 393         const unsigned bit_width = *in++ & 0x3f;
 394
 395         in = decode_pfor_bitmap_exceptions(in, num, bit_width, out);
 396
 397         // Decode the base values, and delta-decode.
 398         Docid prev_val = out[-1];
 399         BitReader bs(in, bit_width);
 400         for (unsigned i = 0; i < num; ++i) {
 401                 out[i] = prev_val = (out[i] | bs.read()) + prev_val + 1;
 402         }
 403         return in + bytes_for_packed_bits(num, bit_width);
 404 }
 405
 406 // Like decode_pfor_bitmap(), but the base values are organized in four
 407 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
 408 template<unsigned BlockSize, class Docid>
 409 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
 410 {
 411         memset(out, 0, BlockSize * sizeof(Docid));
 412
 413         const unsigned bit_width = *in++ & 0x3f;
 414
 415         in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
 416
 417         // Decode the base values.
 418         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 419         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 420         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 421         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 422         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 423                 out[i * 4 + 0] |= bs0.read();
 424                 out[i * 4 + 1] |= bs1.read();
 425                 out[i * 4 + 2] |= bs2.read();
 426                 out[i * 4 + 3] |= bs3.read();
 427         }
 428
 429         // Delta-decode.
 430         Docid prev_val = out[-1];
 431         for (unsigned i = 0; i < BlockSize; ++i) {
 432                 out[i] = prev_val = out[i] + prev_val + 1;
 433         }
 434         return in + bytes_for_packed_bits(BlockSize, bit_width);
 435 }
 436
 437 template<unsigned BlockSize, class Docid>
 438 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
 439 {
 440         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 441                 return decode_pfor_bitmap_interleaved_128_32(in, out);
 442         } else {
 443                 return decode_pfor_bitmap_interleaved_generic(in, out);
 444         }
 445 }
 446
 447 __attribute__((target("default")))
 448 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
 449 {
 450         return decode_pfor_bitmap_interleaved_generic<128>(in, out);
 451 }
 452
 453 #ifdef COULD_HAVE_SSE2
 454 // Specialized version for SSE2.
 455 __attribute__((target("sse2")))
 456 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
 457 {
 458         constexpr unsigned BlockSize = 128;
 459         using Docid = uint32_t;
 460
 461         memset(out, 0, BlockSize * sizeof(Docid));
 462
 463         const unsigned bit_width = *in++ & 0x3f;
 464
 465         in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
 466         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
 467
 468         return in;
 469 }
 470 #endif
 471
 472 // PFor block with variable-byte exceptions. Layout:
 473 //
 474 //  - Bit width (6 bits) | type << 6
 475 //  - Number of exceptions (8 bits)
 476 //  - Base values (<num> values of <bits> bits, rounded up to a byte)
 477 //  - Exceptions:
 478 //    - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
 479 //    - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
 480 //  - Indexes of exceptions (<num_exc> bytes).
 481 template<unsigned BlockSize, class Docid>
 482 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
 483 {
 484         //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
 485
 486         const unsigned bit_width = *in++ & 0x3f;
 487         unsigned num_exceptions = *in++;
 488
 489         // Decode the base values.
 490         BitReader bs(in, bit_width);
 491         for (unsigned i = 0; i < num; ++i) {
 492                 out[i] = bs.read();
 493         }
 494         in += bytes_for_packed_bits(num, bit_width);
 495
 496         // Decode exceptions.
 497         Docid exceptions[BlockSize];
 498         if (*in == 255) {
 499                 ++in;
 500                 for (unsigned i = 0; i < num_exceptions; ++i) {
 501                         exceptions[i] = read_le<Docid>(in);
 502                         in += sizeof(Docid);
 503                 }
 504         } else {
 505                 for (unsigned i = 0; i < num_exceptions; ++i) {
 506                         in = read_vb(in, &exceptions[i]);
 507                 }
 508         }
 509         // Apply exceptions.
 510         for (unsigned i = 0; i < num_exceptions; ++i) {
 511                 unsigned idx = *in++;
 512                 out[idx] |= exceptions[i] << bit_width;
 513         }
 514
 515         // Delta-decode.
 516         Docid prev_val = out[-1];
 517         for (unsigned i = 0; i < num; ++i) {
 518                 out[i] = prev_val = out[i] + prev_val + 1;
 519         }
 520
 521         return in;
 522 }
 523
 524 // Like decode_pfor_vb(), but the base values are organized in four
 525 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
 526 template<unsigned BlockSize, class Docid>
 527 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
 528 {
 529         const unsigned bit_width = *in++ & 0x3f;
 530         unsigned num_exceptions = *in++;
 531
 532         // Decode the base values.
 533         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 534         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 535         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 536         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 537         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 538                 out[i * 4 + 0] = bs0.read();
 539                 out[i * 4 + 1] = bs1.read();
 540                 out[i * 4 + 2] = bs2.read();
 541                 out[i * 4 + 3] = bs3.read();
 542         }
 543         in += bytes_for_packed_bits(BlockSize, bit_width);
 544
 545         // Decode exceptions.
 546         Docid exceptions[BlockSize];
 547         if (*in == 255) {
 548                 ++in;
 549                 for (unsigned i = 0; i < num_exceptions; ++i) {
 550                         exceptions[i] = read_le<Docid>(in);
 551                         in += sizeof(Docid);
 552                 }
 553         } else {
 554                 for (unsigned i = 0; i < num_exceptions; ++i) {
 555                         in = read_vb(in, &exceptions[i]);
 556                 }
 557         }
 558
 559         // Apply exceptions.
 560         for (unsigned i = 0; i < num_exceptions; ++i) {
 561                 unsigned idx = *in++;
 562                 out[idx] |= exceptions[i] << bit_width;
 563         }
 564
 565         // Delta-decode.
 566         Docid prev_val = out[-1];
 567         for (unsigned i = 0; i < BlockSize; ++i) {
 568                 out[i] = prev_val = out[i] + prev_val + 1;
 569         }
 570
 571         return in;
 572 }
 573
 574 template<unsigned BlockSize, class Docid>
 575 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
 576 {
 577         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 578                 return decode_pfor_vb_interleaved_128_32(in, out);
 579         } else {
 580                 return decode_pfor_vb_interleaved_generic(in, out);
 581         }
 582 }
 583
 584 __attribute__((target("default")))
 585 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
 586 {
 587         return decode_pfor_vb_interleaved_generic<128>(in, out);
 588 }
 589
 590 // Specialized version for SSE2.
 591 __attribute__((target("sse2")))
 592 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
 593 {
 594         constexpr unsigned BlockSize = 128;
 595         using Docid = uint32_t;
 596
 597         const unsigned bit_width = *in++ & 0x3f;
 598         unsigned num_exceptions = *in++;
 599
 600         // Decode the base values.
 601         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
 602
 603         // Decode exceptions.
 604         Docid exceptions[BlockSize];
 605         if (*in == 255) {
 606                 ++in;
 607                 for (unsigned i = 0; i < num_exceptions; ++i) {
 608                         exceptions[i] = read_le<Docid>(in);
 609                         in += sizeof(Docid);
 610                 }
 611         } else {
 612                 for (unsigned i = 0; i < num_exceptions; ++i) {
 613                         in = read_vb(in, &exceptions[i]);
 614                 }
 615         }
 616
 617         // Apply exceptions.
 618         for (unsigned i = 0; i < num_exceptions; ++i) {
 619                 unsigned idx = *in++;
 620                 out[idx] |= exceptions[i] << bit_width;
 621         }
 622
 623         delta_decode_sse2<BlockSize>(out);
 624
 625         return in;
 626 }
 627
 628 enum BlockType {
 629         FOR = 0,
 630         PFOR_VB = 1,
 631         PFOR_BITMAP = 2,
 632         CONSTANT = 3
 633 };
 634
 635 template<unsigned BlockSize, class Docid>
 636 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
 637 {
 638         if (num == 0) {
 639                 return in;
 640         }
 641         in = read_baseval(in, out++);
 642
 643         for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
 644                 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
 645                 switch (in[0] >> 6) {
 646                 case BlockType::FOR:
 647                         if (interleaved && num_this_block == BlockSize) {
 648                                 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 649                                 in = decode_for_interleaved<BlockSize>(in, out);
 650                         } else {
 651                                 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 652                                 in = decode_for(in, num_this_block, out);
 653                         }
 654                         break;
 655                 case BlockType::PFOR_VB:
 656                         if (interleaved && num_this_block == BlockSize) {
 657                                 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 658                                 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
 659                         } else {
 660                                 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 661                                 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
 662                         }
 663                         break;
 664                 case BlockType::PFOR_BITMAP:
 665                         if (interleaved && num_this_block == BlockSize) {
 666                                 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 667                                 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
 668                         } else {
 669                                 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 670                                 in = decode_pfor_bitmap(in, num_this_block, out);
 671                         }
 672                         break;
 673                 case BlockType::CONSTANT:
 674                         dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 675                         in = decode_constant(in, num_this_block, out);
 676                         break;
 677                 }
 678         }
 679
 680         return in;
 681 }
 682
 683 #endif  // !defined(_TURBOPFOR_H)