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 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.
  11 // Unlike the reference code, only GCC and GCC-compatible compilers
  12 // (e.g. Clang) are supported.
  13 //
  14 // The main reference is https://michael.stapelberg.ch/posts/2019-02-05-turbopfor-analysis/,
  15 // although some implementation details have been worked out by studying the
  16 // TurboPFor code.
  17
  18 #include <algorithm>
  19 #include <assert.h>
  20 #include <endian.h>
  21 #include <limits.h>
  22 #include <stdint.h>
  23 #include <string.h>
  24
  25 #if defined(__i386__) || defined(__x86_64__)
  26 #define COULD_HAVE_SSE2
  27 #include <immintrin.h>
  28 #endif
  29
  30 #include "turbopfor-common.h"
  31
  32 // Forward declarations to declare to the template code below that they exist.
  33 // (These must seemingly be non-templates for function multiversioning to work.)
  34 __attribute__((target("default")))
  35 const unsigned char *
  36 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
  37 __attribute__((target("default")))
  38 const unsigned char *
  39 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
  40 __attribute__((target("default")))
  41 const unsigned char *
  42 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
  43
  44 #ifdef COULD_HAVE_SSE2
  45 __attribute__((target("sse2")))
  46 const unsigned char *
  47 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
  48 __attribute__((target("sse2")))
  49 const unsigned char *
  50 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
  51 __attribute__((target("sse2")))
  52 const unsigned char *
  53 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
  54 #endif
  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         __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))) {}
 178
 179         __attribute__((target("sse2")))
 180         __m128i
 181         read()
 182         {
 183                 __m128i val = _mm_srli_epi32(_mm_loadu_si128(in), bits_used);
 184                 if (bits_used + bits > 32) {
 185                         __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(in + 1), 32 - bits_used);
 186                         val = _mm_or_si128(val, val_upper);
 187                 }
 188                 val = _mm_and_si128(val, mask);
 189
 190                 bits_used += bits;
 191                 in += bits_used / 32;
 192                 bits_used %= 32;
 193                 return val;
 194         }
 195
 196 private:
 197         const __m128i *in;
 198         const unsigned bits;
 199         const __m128i mask;
 200         unsigned bits_used = 0;
 201 };
 202 #endif
 203
 204 // Constant block. Layout:
 205 //
 206 //  - Bit width (6 bits) | type << 6
 207 //  - Base values (<bits> bits, rounded up to nearest byte)
 208 template<class Docid>
 209 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
 210 {
 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);
 215         }
 216
 217         Docid prev_val = out[-1];
 218         for (unsigned i = 0; i < num; ++i) {
 219                 out[i] = prev_val = val + prev_val + 1;
 220         }
 221         return in + div_round_up(bit_width, 8);
 222 }
 223
 224 // FOR block (ie., PFor without exceptions). Layout:
 225 //
 226 //  - Bit width (6 bits) | type << 6
 227 //  - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
 228 template<class Docid>
 229 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
 230 {
 231         const unsigned bit_width = *in++ & 0x3f;
 232
 233         Docid prev_val = out[-1];
 234         BitReader bs(in, bit_width);
 235         for (unsigned i = 0; i < num; ++i) {
 236                 prev_val = out[i] = bs.read() + prev_val + 1;
 237         }
 238         return in + bytes_for_packed_bits(num, bit_width);
 239 }
 240
 241 #ifdef COULD_HAVE_SSE2
 242 class DeltaDecoderSSE2 {
 243 public:
 244         __attribute__((target("sse2")))
 245         DeltaDecoderSSE2(uint32_t prev_val)
 246                 : prev_val(_mm_set1_epi32(prev_val)) {}
 247
 248         __attribute__((target("sse2")))
 249         __m128i
 250         decode(__m128i val)
 251         {
 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"))) inline void delta_decode_sse2(uint32_t *out)
 269 {
 270         DeltaDecoderSSE2 delta(out[-1]);
 271         __m128i *outvec = reinterpret_cast<__m128i *>(out);
 272         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 273                 __m128i val = _mm_loadu_si128(outvec + i);
 274                 _mm_storeu_si128(outvec + i, delta.decode(val));
 275         }
 276 }
 277
 278 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode, unsigned bit_width>
 279 __attribute__((target("sse2")))
 280 const unsigned char *
 281 decode_bitmap_sse2_unrolled(const unsigned char *in, uint32_t *out)
 282 {
 283         __m128i *outvec = reinterpret_cast<__m128i *>(out);
 284         DeltaDecoderSSE2 delta(out[-1]);
 285         InterleavedBitReaderSSE2 bs(in, bit_width);
 286 #pragma GCC unroll 32
 287         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 288                 __m128i val = bs.read();
 289                 if constexpr (OrWithExisting) {
 290                         val = _mm_or_si128(val, _mm_slli_epi32(_mm_loadu_si128(outvec + i), bit_width));
 291                 }
 292                 if constexpr (DeltaDecode) {
 293                         val = delta.decode(val);
 294                 }
 295                 _mm_storeu_si128(outvec + i, val);
 296         }
 297         in += bytes_for_packed_bits(BlockSize, bit_width);
 298         return in;
 299 }
 300
 301 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
 302 __attribute__((target("sse2")))
 303 const unsigned char *
 304 decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
 305 {
 306         switch (bit_width) {
 307         case 0:
 308                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 0>(in, out);
 309         case 1:
 310                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 1>(in, out);
 311         case 2:
 312                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 2>(in, out);
 313         case 3:
 314                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 3>(in, out);
 315         case 4:
 316                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 4>(in, out);
 317         case 5:
 318                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 5>(in, out);
 319         case 6:
 320                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 6>(in, out);
 321         case 7:
 322                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 7>(in, out);
 323         case 8:
 324                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 8>(in, out);
 325         case 9:
 326                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 9>(in, out);
 327         case 10:
 328                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 10>(in, out);
 329         case 11:
 330                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 11>(in, out);
 331         case 12:
 332                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 12>(in, out);
 333         case 13:
 334                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 13>(in, out);
 335         case 14:
 336                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 14>(in, out);
 337         case 15:
 338                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 15>(in, out);
 339         case 16:
 340                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 16>(in, out);
 341         case 17:
 342                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 17>(in, out);
 343         case 18:
 344                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 18>(in, out);
 345         case 19:
 346                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 19>(in, out);
 347         case 20:
 348                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 20>(in, out);
 349         case 21:
 350                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 21>(in, out);
 351         case 22:
 352                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 22>(in, out);
 353         case 23:
 354                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 23>(in, out);
 355         case 24:
 356                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 24>(in, out);
 357         case 25:
 358                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 25>(in, out);
 359         case 26:
 360                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 26>(in, out);
 361         case 27:
 362                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 27>(in, out);
 363         case 28:
 364                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 28>(in, out);
 365         case 29:
 366                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 29>(in, out);
 367         case 30:
 368                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 30>(in, out);
 369         case 31:
 370                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 31>(in, out);
 371         case 32:
 372                 return decode_bitmap_sse2_unrolled<BlockSize, OrWithExisting, DeltaDecode, 32>(in, out);
 373         }
 374         assert(false);
 375 }
 376 #endif
 377
 378 // Like decode_for(), but the values are organized in four independent streams,
 379 // for SIMD (presumably SSE2). Supports a whole block only.
 380 template<unsigned BlockSize, class Docid>
 381 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
 382 {
 383         const unsigned bit_width = *in++ & 0x3f;
 384
 385         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 386         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 387         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 388         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 389         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 390                 out[i * 4 + 0] = bs0.read();
 391                 out[i * 4 + 1] = bs1.read();
 392                 out[i * 4 + 2] = bs2.read();
 393                 out[i * 4 + 3] = bs3.read();
 394         }
 395         Docid prev_val = out[-1];
 396         for (unsigned i = 0; i < BlockSize; ++i) {
 397                 out[i] = prev_val = out[i] + prev_val + 1;
 398         }
 399         return in + bytes_for_packed_bits(BlockSize, bit_width);
 400 }
 401
 402 template<unsigned BlockSize, class Docid>
 403 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
 404 {
 405         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 406                 return decode_for_interleaved_128_32(in, out);
 407         } else {
 408                 return decode_for_interleaved_generic(in, out);
 409         }
 410 }
 411
 412 __attribute__((target("default")))
 413 const unsigned char *
 414 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
 415 {
 416         return decode_for_interleaved_generic<128>(in, out);
 417 }
 418
 419 #ifdef COULD_HAVE_SSE2
 420 // Specialized version for SSE2.
 421 __attribute__((target("sse2")))
 422 const unsigned char *
 423 decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
 424 {
 425         constexpr unsigned BlockSize = 128;
 426
 427         const unsigned bit_width = *in++ & 0x3f;
 428
 429         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
 430
 431         return in;
 432 }
 433 #endif
 434
 435 template<class Docid>
 436 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, Docid *out)
 437 {
 438         const unsigned exception_bit_width = *in++;
 439         const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
 440         in += div_round_up(num, 8);
 441
 442         int num_exceptions = 0;
 443
 444         BitReader bs(in, exception_bit_width);
 445         for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
 446                 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
 447                 if (num - i < 64) {
 448                         // We've read some bytes past the end, so clear out the junk bits.
 449                         exceptions &= (1ULL << (num - i)) - 1;
 450                 }
 451                 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
 452                         unsigned idx = (ffsll(exceptions) - 1) + i;
 453                         out[idx] = bs.read();
 454                 }
 455         }
 456         in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
 457         return in;
 458 }
 459
 460 // PFor block with bitmap exceptions. Layout:
 461 //
 462 //  - Bit width (6 bits) | type << 6
 463 //  - Exception bit width (8 bits)
 464 //  - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
 465 //  - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
 466 //  - Base values (<num> values of <bits> bits, rounded up to a byte)
 467 template<class Docid>
 468 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
 469 {
 470         memset(out, 0, num * sizeof(Docid));
 471
 472         const unsigned bit_width = *in++ & 0x3f;
 473
 474         in = decode_pfor_bitmap_exceptions(in, num, out);
 475
 476         // Decode the base values, and delta-decode.
 477         Docid prev_val = out[-1];
 478         BitReader bs(in, bit_width);
 479         for (unsigned i = 0; i < num; ++i) {
 480                 out[i] = prev_val = ((out[i] << bit_width) | bs.read()) + prev_val + 1;
 481         }
 482         return in + bytes_for_packed_bits(num, bit_width);
 483 }
 484
 485 // Like decode_pfor_bitmap(), but the base values are organized in four
 486 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
 487 template<unsigned BlockSize, class Docid>
 488 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
 489 {
 490         memset(out, 0, BlockSize * sizeof(Docid));
 491
 492         const unsigned bit_width = *in++ & 0x3f;
 493
 494         in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
 495
 496         // Decode the base values.
 497         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 498         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 499         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 500         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 501         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 502                 out[i * 4 + 0] = bs0.read() | (out[i * 4 + 0] << bit_width);
 503                 out[i * 4 + 1] = bs1.read() | (out[i * 4 + 1] << bit_width);
 504                 out[i * 4 + 2] = bs2.read() | (out[i * 4 + 2] << bit_width);
 505                 out[i * 4 + 3] = bs3.read() | (out[i * 4 + 3] << bit_width);
 506         }
 507
 508         // Delta-decode.
 509         Docid prev_val = out[-1];
 510         for (unsigned i = 0; i < BlockSize; ++i) {
 511                 out[i] = prev_val = out[i] + prev_val + 1;
 512         }
 513         return in + bytes_for_packed_bits(BlockSize, bit_width);
 514 }
 515
 516 template<unsigned BlockSize, class Docid>
 517 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
 518 {
 519         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 520                 return decode_pfor_bitmap_interleaved_128_32(in, out);
 521         } else {
 522                 return decode_pfor_bitmap_interleaved_generic(in, out);
 523         }
 524 }
 525
 526 __attribute__((target("default")))
 527 const unsigned char *
 528 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
 529 {
 530         return decode_pfor_bitmap_interleaved_generic<128>(in, out);
 531 }
 532
 533 #ifdef COULD_HAVE_SSE2
 534 // Specialized version for SSE2.
 535 __attribute__((target("sse2")))
 536 const unsigned char *
 537 decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
 538 {
 539         constexpr unsigned BlockSize = 128;
 540
 541 // Set all output values to zero, before the exceptions are filled in.
 542 #pragma GCC unroll 4
 543         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 544                 _mm_storeu_si128(reinterpret_cast<__m128i *>(out) + i, _mm_setzero_si128());
 545         }
 546
 547         const unsigned bit_width = *in++ & 0x3f;
 548
 549         in = decode_pfor_bitmap_exceptions(in, BlockSize, out);
 550         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
 551
 552         return in;
 553 }
 554 #endif
 555
 556 // PFor block with variable-byte exceptions. Layout:
 557 //
 558 //  - Bit width (6 bits) | type << 6
 559 //  - Number of exceptions (8 bits)
 560 //  - Base values (<num> values of <bits> bits, rounded up to a byte)
 561 //  - Exceptions:
 562 //    - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
 563 //    - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
 564 //  - Indexes of exceptions (<num_exc> bytes).
 565 template<unsigned BlockSize, class Docid>
 566 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
 567 {
 568         //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
 569
 570         const unsigned bit_width = *in++ & 0x3f;
 571         unsigned num_exceptions = *in++;
 572
 573         // Decode the base values.
 574         BitReader bs(in, bit_width);
 575         for (unsigned i = 0; i < num; ++i) {
 576                 out[i] = bs.read();
 577         }
 578         in += bytes_for_packed_bits(num, bit_width);
 579
 580         // Decode exceptions.
 581         Docid exceptions[BlockSize];
 582         if (*in == 255) {
 583                 ++in;
 584                 for (unsigned i = 0; i < num_exceptions; ++i) {
 585                         exceptions[i] = read_le<Docid>(in);
 586                         in += sizeof(Docid);
 587                 }
 588         } else {
 589                 for (unsigned i = 0; i < num_exceptions; ++i) {
 590                         in = read_vb(in, &exceptions[i]);
 591                 }
 592         }
 593         // Apply exceptions.
 594         for (unsigned i = 0; i < num_exceptions; ++i) {
 595                 unsigned idx = *in++;
 596                 out[idx] |= exceptions[i] << bit_width;
 597         }
 598
 599         // Delta-decode.
 600         Docid prev_val = out[-1];
 601         for (unsigned i = 0; i < num; ++i) {
 602                 out[i] = prev_val = out[i] + prev_val + 1;
 603         }
 604
 605         return in;
 606 }
 607
 608 // Like decode_pfor_vb(), but the base values are organized in four
 609 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
 610 template<unsigned BlockSize, class Docid>
 611 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
 612 {
 613         const unsigned bit_width = *in++ & 0x3f;
 614         unsigned num_exceptions = *in++;
 615
 616         // Decode the base values.
 617         InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
 618         InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
 619         InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
 620         InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
 621         for (unsigned i = 0; i < BlockSize / 4; ++i) {
 622                 out[i * 4 + 0] = bs0.read();
 623                 out[i * 4 + 1] = bs1.read();
 624                 out[i * 4 + 2] = bs2.read();
 625                 out[i * 4 + 3] = bs3.read();
 626         }
 627         in += bytes_for_packed_bits(BlockSize, bit_width);
 628
 629         // Decode exceptions.
 630         Docid exceptions[BlockSize];
 631         if (*in == 255) {
 632                 ++in;
 633                 for (unsigned i = 0; i < num_exceptions; ++i) {
 634                         exceptions[i] = read_le<Docid>(in);
 635                         in += sizeof(Docid);
 636                 }
 637         } else {
 638                 for (unsigned i = 0; i < num_exceptions; ++i) {
 639                         in = read_vb(in, &exceptions[i]);
 640                 }
 641         }
 642
 643         // Apply exceptions.
 644         for (unsigned i = 0; i < num_exceptions; ++i) {
 645                 unsigned idx = *in++;
 646                 out[idx] |= exceptions[i] << bit_width;
 647         }
 648
 649         // Delta-decode.
 650         Docid prev_val = out[-1];
 651         for (unsigned i = 0; i < BlockSize; ++i) {
 652                 out[i] = prev_val = out[i] + prev_val + 1;
 653         }
 654
 655         return in;
 656 }
 657
 658 template<unsigned BlockSize, class Docid>
 659 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
 660 {
 661         if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
 662                 return decode_pfor_vb_interleaved_128_32(in, out);
 663         } else {
 664                 return decode_pfor_vb_interleaved_generic(in, out);
 665         }
 666 }
 667
 668 __attribute__((target("default")))
 669 const unsigned char *
 670 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
 671 {
 672         return decode_pfor_vb_interleaved_generic<128>(in, out);
 673 }
 674
 675 // Specialized version for SSE2.
 676 __attribute__((target("sse2")))
 677 const unsigned char *
 678 decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
 679 {
 680         constexpr unsigned BlockSize = 128;
 681         using Docid = uint32_t;
 682
 683         const unsigned bit_width = *in++ & 0x3f;
 684         unsigned num_exceptions = *in++;
 685
 686         // Decode the base values.
 687         in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
 688
 689         // Decode exceptions.
 690         Docid exceptions[BlockSize];
 691         if (*in == 255) {
 692                 ++in;
 693                 for (unsigned i = 0; i < num_exceptions; ++i) {
 694                         exceptions[i] = read_le<Docid>(in);
 695                         in += sizeof(Docid);
 696                 }
 697         } else {
 698                 for (unsigned i = 0; i < num_exceptions; ++i) {
 699                         in = read_vb(in, &exceptions[i]);
 700                 }
 701         }
 702
 703         // Apply exceptions.
 704         for (unsigned i = 0; i < num_exceptions; ++i) {
 705                 unsigned idx = *in++;
 706                 out[idx] |= exceptions[i] << bit_width;
 707         }
 708
 709         delta_decode_sse2<BlockSize>(out);
 710
 711         return in;
 712 }
 713
 714 template<unsigned BlockSize, class Docid>
 715 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
 716 {
 717         if (num == 0) {
 718                 return in;
 719         }
 720         in = read_baseval(in, out++);
 721
 722         for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
 723                 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
 724                 switch (in[0] >> 6) {
 725                 case BlockType::FOR:
 726                         if (interleaved && num_this_block == BlockSize) {
 727                                 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 728                                 in = decode_for_interleaved<BlockSize>(in, out);
 729                         } else {
 730                                 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 731                                 in = decode_for(in, num_this_block, out);
 732                         }
 733                         break;
 734                 case BlockType::PFOR_VB:
 735                         if (interleaved && num_this_block == BlockSize) {
 736                                 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 737                                 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
 738                         } else {
 739                                 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 740                                 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
 741                         }
 742                         break;
 743                 case BlockType::PFOR_BITMAP:
 744                         if (interleaved && num_this_block == BlockSize) {
 745                                 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 746                                 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
 747                         } else {
 748                                 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 749                                 in = decode_pfor_bitmap(in, num_this_block, out);
 750                         }
 751                         break;
 752                 case BlockType::CONSTANT:
 753                         dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
 754                         in = decode_constant(in, num_this_block, out);
 755                         break;
 756                 }
 757         }
 758
 759         return in;
 760 }
 761
 762 #endif  // !defined(_TURBOPFOR_H)