patternfilter.cpp

// Pattern filter
// 
// Simplified code as example for a pattern filter algorithm.
//
// by feyd//godX.de
 
#include <stdint.h>
#include <vector>
#include <string>
#include <stdio.h>
 
// Pattern filter generation from string with triplets
uint64_t BuildPattern(const std::string& sTextPattern)
{
    uint64_t nPattern = 0;
    if(sTextPattern.length()>2)
        for(size_t n=0; n<sTextPattern.length()-2; n++)
            nPattern |= 1LL<<(((int)sTextPattern[n]+(int)sTextPattern[n+1]*7-(int)sTextPattern[n+2]*13)&63);
    return nPattern;
}
 
// Is the search pattern included?
bool IsPatternMatch(uint64_t nPattern, uint64_t nSearch)
{
    return (nPattern&nSearch)==nSearch?true:false;
}
 
// class holding string and pattern data
class CPatternString : public std::string
{
public:
    CPatternString() {}
    CPatternString(const char* pString) : std::string(pString)
    {
        UpdatePattern();
    }
 
    virtual ~CPatternString() {}
 
    CPatternString& operator=(const char* pString)
    {
        this->assign(pString);
        UpdatePattern();
        return *this;
    }
 
    void UpdatePattern()
    {
        m_nPattern = BuildPattern(*this);
    }
 
    uint64_t GetPattern() const
    {
        return m_nPattern;
    }
protected:
    uint64_t m_nPattern;
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Pattern filter test...\r\n\r\n");
 
    if(argc>1)
    {
        uint64_t nGlobalPattern = 0;
        std::vector<CPatternString> strings(argc-2);
        for(int n=0; n<argc-2; n++)
        {
            strings[n] = argv[n+1];
            nGlobalPattern |= strings[n].GetPattern();
            printf("  %d: %016llx\r\n", n, strings[n].GetPattern());
        }
 
        CPatternString search(argv[argc-1]);
        printf("  S: %016llx\r\n", search.GetPattern());
 
        if(IsPatternMatch(nGlobalPattern, search.GetPattern()))
        {
            int nMatches = 0;
            printf("  found in global search pattern\r\n");
            for(int n=0; n<argc-2; n++)
            {
                if(IsPatternMatch(strings[n].GetPattern(), search.GetPattern()))
                {
                    printf("    string %d matched filter\r\n", n, strings[n].GetPattern());
                    nMatches++;
                }
            }
            printf("  %d possible matches for given string\r\n", nMatches);
        } else {
            printf("  not found in global search pattern\r\n");
        }
    } else {
        printf("not enough arguments\r\n");
    }
    return 0;
}