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 // Unlike the reference code, only GCC and GCC-compatible compilers
  12 // (e.g. Clang) are supported.
  13 //
  14 // The main reference is https://michael.stapelberg.ch/posts/2019-02-05-turbopfor-analysis/,
  15 // although some implementation details have been worked out by studying the
  16 // TurboPFor code.
  17 //
  18 // The decoder, like the reference implementation, is not robust against
  19 // malicious of corrupted. Several functions (again like the reference
  20 // implementation) can read N bytes past the end, so you need to have some slop
  21 // in the input buffers; this is documented for each function (unlike
  22 // the reference implementation), but the documented slop assumes a
  23 // non-malicious encoder.
  24 //
  25 // Although all of these algorithms are templatized, we expose only
  26 // the single specialization that we need, in order to increase the
  27 // speed of incremental compilation.
  28
  29 const unsigned char *decode_pfor_delta1_128(const unsigned char *in, unsigned num, bool interleaved, uint32_t *out);
  30
  31 #endif  // !defined(_TURBOPFOR_H)