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