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