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