fastfilter Namespace Reference

Classes
struct	Bloom
struct	ACNode
struct	Automaton
struct	LRUCache
struct	Config
struct	Verdict
class	Engine

Functions
static uint64_t	rotl64 (uint64_t x, int8_t r)
static uint64_t	fmix64 (uint64_t k)
static uint64_t	murmur3_64 (const void *key, size_t len, uint32_t seed=0xB00B1E)

Function Documentation

fmix64()

uint64_t fastfilter::fmix64 ( uint64_t k )

inlinestatic

Definition at line 49 of file fast_filter.h.

                                         {
  k ^= k >> 33; k *= 0xff51afd7ed558ccdULL; k ^= k >> 33; k *= 0xc4ceb9fe1a85ec53ULL; k ^= k >> 33; return k;
}

References fmix64().

Referenced by fmix64(), and murmur3_64().

murmur3_64()

uint64_t fastfilter::murmur3_64 ( const void * key, size_t len, uint32_t seed = 0xB00B1E )

inlinestatic

Definition at line 52 of file fast_filter.h.

                                                                                    {
  const uint8_t* data = (const uint8_t*)key; const int nblocks = len / 16;
  uint64_t h1 = seed, h2 = seed;
  const uint64_t c1 = 0x87c37b91114253d5ULL, c2 = 0x4cf5ad432745937fULL;
  const uint64_t* blocks = (const uint64_t*)(data);
  for(int i = 0; i < nblocks; i++){
    uint64_t k1 = blocks[i*2+0]; uint64_t k2 = blocks[i*2+1];
    k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1; h1 = rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
    k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2; h2 = rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
  }
  const uint8_t* tail = (const uint8_t*)(data + nblocks*16);
  uint64_t k1 = 0, k2 = 0;
  switch(len & 15){
    case 15: k2 ^= ((uint64_t)tail[14]) << 48; [[fallthrough]];
    case 14: k2 ^= ((uint64_t)tail[13]) << 40; [[fallthrough]];
    case 13: k2 ^= ((uint64_t)tail[12]) << 32; [[fallthrough]];
    case 12: k2 ^= ((uint64_t)tail[11]) << 24; [[fallthrough]];
    case 11: k2 ^= ((uint64_t)tail[10]) << 16; [[fallthrough]];
    case 10: k2 ^= ((uint64_t)tail[9]) << 8;  [[fallthrough]];
    case 9:  k2 ^= ((uint64_t)tail[8]) << 0;  k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2; [[fallthrough]];
    case 8:  k1 ^= ((uint64_t)tail[7]) << 56; [[fallthrough]];
    case 7:  k1 ^= ((uint64_t)tail[6]) << 48; [[fallthrough]];
    case 6:  k1 ^= ((uint64_t)tail[5]) << 40; [[fallthrough]];
    case 5:  k1 ^= ((uint64_t)tail[4]) << 32; [[fallthrough]];
    case 4:  k1 ^= ((uint64_t)tail[3]) << 24; [[fallthrough]];
    case 3:  k1 ^= ((uint64_t)tail[2]) << 16; [[fallthrough]];
    case 2:  k1 ^= ((uint64_t)tail[1]) << 8;  [[fallthrough]];
    case 1:  k1 ^= ((uint64_t)tail[0]) << 0;  k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1; [[fallthrough]];
    default: break;
  }
  h1 ^= len; h2 ^= len; h1 += h2; h2 += h1; h1 = fmix64(h1); h2 = fmix64(h2); h1 += h2;
  return h1;
}

References fmix64(), murmur3_64(), and rotl64().

Referenced by fastfilter::Bloom::add(), fastfilter::Engine::check_url(), fastfilter::Bloom::might_contain(), and murmur3_64().

rotl64()

uint64_t fastfilter::rotl64 ( uint64_t x, int8_t r )

inlinestatic

Definition at line 48 of file fast_filter.h.

{ return (x << r) | (x >> (64 - r)); }

References rotl64().

Referenced by murmur3_64(), and rotl64().