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

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