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