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

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