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

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