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

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