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

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