pattern.cpp (1881B)
1 #include "pattern.hpp" 2 3 #include <libshit/assert.hpp> 4 5 #include <boost/algorithm/searching/boyer_moore.hpp> 6 7 #define LIBSHIT_LOG_NAME "pattern" 8 #include <libshit/logger_helper.hpp> 9 10 namespace Neptools 11 { 12 13 static bool CheckPattern( 14 const Byte* ptr, const Byte* pattern, const Byte* mask, size_t len) 15 { 16 while (len--) 17 if ((*ptr++ & *mask++) != *pattern++) 18 return false; 19 return true; 20 } 21 22 const Byte* Pattern::MaybeFind(Libshit::StringView data) const noexcept 23 { 24 size_t max_len = 0, max_i = 0; 25 size_t start_i = 0; 26 for (size_t i = 0; i < size; ++i) 27 if (mask[i] == 0xff) 28 { 29 if (i - start_i + 1 > max_len) 30 { 31 max_len = i - start_i + 1; 32 max_i = start_i; 33 } 34 } 35 else 36 start_i = i+1; 37 38 LIBSHIT_ASSERT(max_i + max_len <= size); 39 boost::algorithm::boyer_moore<const Byte*> bm{ 40 pattern + max_i, pattern + max_i + max_len}; 41 42 auto ptr = data.udata() + max_i; 43 auto ptr_end = data.udata() + data.length() - (size - max_len - max_i); 44 const Byte* res = nullptr; 45 46 while (true) 47 { 48 DBG(4) << "finding " << static_cast<const void*>(ptr) << "..." 49 << static_cast<const void*>(ptr_end) << std::endl; 50 auto match = bm(ptr, ptr_end).first; 51 DBG(4) << "match @" << static_cast<const void*>(match) << std::endl; 52 if (match == ptr_end) break; 53 54 if (CheckPattern(match - max_i, pattern, mask, size)) 55 if (res) 56 { 57 // todo? 58 WARN << "Multiple matches for pattern " 59 << static_cast<const void*>(res) << " and " 60 << static_cast<const void*>(match - max_i) << std::endl; 61 return nullptr; 62 } 63 else 64 res = match - max_i; 65 ptr = match + 1; 66 } 67 DBG(3) << "Found pattern @" << static_cast<const void*>(res) << std::endl; 68 return res; 69 } 70 71 }