fast_filter.h

Go to the documentation of this file.

/*
 * BastionGuard™
 * Copyright (C) 2025–2026 Calogero Scarnà
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * BastionGuard™ is a trademark of Calogero Scarnà.
 * The BastionGuard™ name and branding are not licensed under the GPL.
 */
 
#pragma once
#include <cstdint>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <shared_mutex>
#include <fstream>
#include <sstream>
#include <deque>
#include <memory>
#include <optional>
#include <chrono>
#include <mutex>
#include <algorithm>
#include <list>
#include <cmath>
#include <cctype>
#include <sqlite3.h>
 
#ifdef FASTFILTER_USE_RE2
  #include <re2/re2.h>
#endif
 
namespace fastfilter {
 
 
static inline uint64_t rotl64(uint64_t x, int8_t r) { return (x << r) | (x >> (64 - r)); }
static inline uint64_t fmix64(uint64_t k){
  k ^= k >> 33; k *= 0xff51afd7ed558ccdULL; k ^= k >> 33; k *= 0xc4ceb9fe1a85ec53ULL; k ^= k >> 33; return k;
}
static inline uint64_t murmur3_64(const void* key, size_t len, uint32_t seed=0xB00B1E){
  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;
}
 
 
struct Bloom {
  size_t m_bits = 0; size_t k_hashes = 0; std::vector<uint8_t> buf;
  void init(size_t n_items, double fp_rate){
 
    double ln2 = 0.6931471805599453;
    double m = -(double)n_items * std::log(fp_rate) / (ln2*ln2);
    m_bits = (size_t)std::max( (double)8.0, std::ceil(m) );
    k_hashes = std::max<size_t>(1, (size_t)std::round((m_bits/(double)std::max<size_t>(1,n_items))*ln2));
    buf.assign((m_bits + 7)/8, 0);
  }
  inline void _setbit(uint64_t h){ size_t i = h % m_bits; buf[i>>3] |= (uint8_t)(1u << (i & 7)); }
  inline bool _getbit(uint64_t h) const { size_t i = h % m_bits; return (buf[i>>3] >> (i & 7)) & 1u; }
  void add(const std::string& s){
    uint64_t h1 = murmur3_64(s.data(), s.size(), 0xA5A5A5A5);
    uint64_t h2 = murmur3_64(s.data(), s.size(), 0x5A5A5A5A);
    for(size_t i=0;i<k_hashes;i++) _setbit(h1 + i*h2);
  }
  bool might_contain(const std::string& s) const {
    uint64_t h1 = murmur3_64(s.data(), s.size(), 0xA5A5A5A5);
    uint64_t h2 = murmur3_64(s.data(), s.size(), 0x5A5A5A5A);
    for(size_t i=0;i<k_hashes;i++) if(!_getbit(h1 + i*h2)) return false; return true;
  }
};
 
 
struct ACNode {
  std::unordered_map<char,int> next; int fail = 0; bool out = false;
};
 
struct Automaton {
  std::vector<ACNode> g; size_t patterns = 0;
  Automaton(){ g.reserve(1024); g.push_back(ACNode()); }
  static inline char norm(char c){ return (char)std::tolower((unsigned char)c); }
  void add(const std::string& pat){
    int v = 0; for(char cc : pat){ char c = norm(cc); if(!g[v].next.count(c)){ g[v].next[c] = (int)g.size(); g.push_back(ACNode()); } v = g[v].next[c]; }
    g[v].out = true; patterns++; }
  void build(){
    std::deque<int> q; // BFS
    for(auto &kv : g[0].next){ q.push_back(kv.second); g[kv.second].fail = 0; }
    while(!q.empty()){
      int v = q.front(); q.pop_front();
      for(auto &kv : g[v].next){ char c = kv.first; int u = kv.second; q.push_back(u);
        int f = g[v].fail; while(f && !g[f].next.count(c)) f = g[f].fail; if(g[f].next.count(c) && g[f].next[c]!=u) g[u].fail = g[f].next[c]; else g[u].fail = 0; g[u].out = g[u].out || g[g[u].fail].out; }
    }
  }
  bool search_any(const std::string& s) const {
    int v = 0; for(char cc: s){ char c = norm(cc); while(v && !g[v].next.count(c)) v = g[v].fail; if(g[v].next.count(c)) v = g[v].next.at(c); if(g[v].out) return true; }
    return false; }
};
 
 
struct LRUCache {
  size_t cap; std::list<uint64_t> order; std::unordered_map<uint64_t, std::pair<bool,std::list<uint64_t>::iterator>> map;
  explicit LRUCache(size_t c=100000): cap(c){}
  bool get(uint64_t k, bool &out){ auto it = map.find(k); if(it==map.end()) return false; order.erase(it->second.second); order.push_front(k); it->second.second = order.begin(); out = it->second.first; return true; }
  void put(uint64_t k, bool v){ auto it = map.find(k); if(it!=map.end()){ it->second.first=v; order.erase(it->second.second); order.push_front(k); it->second.second=order.begin(); return;} if(map.size()>=cap){ uint64_t ev = order.back(); order.pop_back(); map.erase(ev);} order.push_front(k); map.emplace(k, std::make_pair(v, order.begin())); }
};
 
 
struct Config { size_t cache_capacity=100000; double bloom_fp_rate=0.01; };
 
struct Verdict { bool block=false; enum Stage{ NONE, BLOOM, AC, REGEX } stage = NONE; std::string why; };
 
class Engine {
public:
  Engine() : cfg(Config{}), cache(cfg.cache_capacity) {}
  explicit Engine(const Config& c): cfg(c), cache(c.cache_capacity) {}
 
 
  bool load_patterns_file(const std::string& path){
    std::ifstream in(path); if(!in) return false; std::vector<std::string> pats; pats.reserve(100000);
    std::string line; while(std::getline(in,line)){ trim(line); if(line.empty()||line[0]=='#') continue; tolower_inplace(line); pats.push_back(line); }
    build_bloom(pats.size()); for(const auto& p: pats){ bloom.add(p);} for(const auto& p: pats){ ac.add(p);} ac.build(); total_patterns = pats.size(); return true;
  }
 
  bool load_regex_file(const std::string& path){
#ifdef FASTFILTER_USE_RE2
    std::ifstream in(path); if(!in) return false; std::string line; size_t cnt=0; regexes.clear();
    while(std::getline(in,line)){
      trim(line); if(line.rfind("Pattern:",0)==0){ std::string pat = line.substr(8); trim(pat); if(!pat.empty()){ regexes.emplace_back(std::make_unique<RE2>(pat)); cnt++; } }
    }
    return cnt>0;
#else
    (void)path; return false;
#endif
  }
 
  bool load_patterns_sqlite(const std::string& db_path, const std::string& table = "phishing_rules");
 
  Verdict check_url(const std::string& url){
    auto norm = lowercase(url);
    uint64_t key = murmur3_64(norm.data(), norm.size()); bool cv; if(cache.get(key, cv)) return {cv, cv?Verdict::AC:Verdict::NONE, cv?"cache-hit": "cache-hit"};
    if(!bloom.m_bits || !bloom.might_contain(norm)){ cache.put(key,false); return {false, Verdict::BLOOM, "bloom-negative"}; }
    bool hit = ac.search_any(norm);
    if(!hit){ cache.put(key,false); return {false, Verdict::AC, "ac-nohit"}; }
#ifdef FASTFILTER_USE_RE2
    // stage 3: regex (if any)
    for(const auto& r: regexes){ if(RE2::PartialMatch(norm, *r)){ cache.put(key,true); return {true, Verdict::REGEX, "regex-match"}; } }
    cache.put(key,true); return {true, Verdict::AC, "ac-match"};
#else
    cache.put(key,true); return {true, Verdict::AC, "ac-match"};
#endif
  }
 
  size_t get_pattern_count() const { return total_patterns; }
 
private:
  Config cfg; Bloom bloom; Automaton ac; LRUCache cache; size_t total_patterns=0;
#ifdef FASTFILTER_USE_RE2
  std::vector<std::unique_ptr<RE2>> regexes;
#endif
 
  void build_bloom(size_t n){ bloom.init(n>0?n:1, cfg.bloom_fp_rate); }
 
  static inline void trim(std::string& s){ size_t a=0; while(a<s.size() && std::isspace((unsigned char)s[a])) a++; size_t b=s.size(); while(b>a && std::isspace((unsigned char)s[b-1])) b--; s.assign(s.substr(a,b-a)); }
  static inline void tolower_inplace(std::string& s){ for(char& c: s) c=(char)std::tolower((unsigned char)c); }
  static inline std::string lowercase(const std::string& s){ std::string t=s; tolower_inplace(t); return t; }
};
 
// --- Definition outside class (no default args here) ---
inline bool Engine::load_patterns_sqlite(const std::string& db_path, const std::string& table) {
    sqlite3* db = nullptr;
    if (sqlite3_open(db_path.c_str(), &db) != SQLITE_OK) return false;
 
    std::string sql = "SELECT pattern, is_regex FROM " + table + ";";
    sqlite3_stmt* stmt = nullptr;
    if (sqlite3_prepare_v2(db, sql.c_str(), -1, &stmt, nullptr) != SQLITE_OK) {
        sqlite3_close(db);
        return false;
    }
 
    std::vector<std::string> pats; pats.reserve(100000);
    std::vector<std::string> regex_pats; regex_pats.reserve(10000);
 
    while (sqlite3_step(stmt) == SQLITE_ROW) {
        const unsigned char* p = sqlite3_column_text(stmt, 0);
        int is_regex = sqlite3_column_int(stmt, 1);
        if (!p) continue;
        std::string s = reinterpret_cast<const char*>(p);
        trim(s); tolower_inplace(s);
        if (s.empty()) continue;
        if (is_regex) regex_pats.push_back(s); else pats.push_back(s);
    }
    sqlite3_finalize(stmt);
    sqlite3_close(db);
 
    // build bloom + AC
    build_bloom(pats.size());
    for (auto& p : pats) bloom.add(p);
    for (auto& p : pats) ac.add(p);
    ac.build();
    total_patterns = pats.size();
 
#ifdef FASTFILTER_USE_RE2
    regexes.clear();
    for (auto& r : regex_pats) regexes.emplace_back(std::make_unique<RE2>(r));
#endif
 
    return true;
}
 
} // namespace fastfilter
 
#ifdef FASTFILTER_IMPLEMENTATION
// header-only: nothing separate to compile
#endif