首页
社区
课程
招聘
[原创]C++二进制特征码暴力匹配
发表于: 2023-3-25 14:59 9960

[原创]C++二进制特征码暴力匹配

2023-3-25 14:59
9960

看到https://bbs.kanxue.com/thread-209946.htm这个帖子,当时我把这代码抄下来运行,发现没跑起来,索性自己就根据这个前人的思路,按照我自己的理解写了一份:

https://github.com/fjqisba/FastBinSearch

 

几乎没有任何算法,就是暴力匹配,核心代码不到50行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
std::vector<size_t> FastSearchPattern::searchAll(void* pBuffer, size_t bufSize)
{
    std::vector<size_t> retList;
    size_t searchEnd = bufSize - sigLen;
    __m128i sigHead = _mm_set1_epi8(firstSig);
    for (size_t i = 0; i <= searchEnd; i = i + 16) {
        unsigned char* pSearchBuf = (unsigned char*)pBuffer + i;
        __m128i startBuf = _mm_loadu_si128((__m128i*)pSearchBuf);
        __m128i curComp = _mm_cmpeq_epi8(sigHead, startBuf);
        unsigned long comMask = _mm_movemask_epi8(curComp);
        unsigned long idxCom;
        while (_BitScanForward(&idxCom, comMask)) {
            bool bFind = true;
            unsigned char* pComBuf = pSearchBuf + 1 + idxCom;
            for (unsigned int n = 0; n < ruleList.size(); ++n) {
                __m128i compareBuf1 = _mm_loadu_si128((__m128i*)(pComBuf + (n << 4)));
                __m128i compareBuf2 = _mm_loadu_si128((__m128i*)ruleList[n].bytes);
                __m128i xmm3 = _mm_cmpeq_epi8(compareBuf1, compareBuf2);
                unsigned long mask = _mm_movemask_epi8(xmm3);
                if ((mask | ruleList[n].mask) != 0xFFFF) {
                    bFind = false;
                    break;
                }
            }
            if (bFind) {
                retList.push_back(i + idxCom);
            }
            comMask &= comMask - 1;
        }
    }
    return retList;
}

速度怎么样,我也懒得测试了,理论上应该能满足大部分场景把。

 

另外,代码我随手写完就扔出来了,可能会存在严重的逻辑Bug,希望有人能帮我找出来( ̄▽ ̄)"


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

最后于 2023-3-25 15:09 被fjqisba编辑 ,原因:
收藏
免费 1
支持
分享
最新回复 (7)
雪    币: 3720
活跃值: (4106)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2

大佬,没看到模糊匹配的部分呢。在gt上看到了,感谢大佬分享。

最后于 2023-3-26 12:35 被院士编辑 ,原因: 补充内容。
2023-3-26 12:32
0
雪    币: 4506
活跃值: (4483)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
模糊匹配很简单,就是搜索可匹配的部分, 然后匹配到正常数据之后比较 ?? 以外的数据
2023-3-26 13:43
0
雪    币: 2402
活跃值: (6808)
能力值: ( LV7,RANK:102 )
在线值:
发帖
回帖
粉丝
4
Mxixihaha 模糊匹配很简单,就是搜索可匹配的部分, 然后匹配到正常数据之后比较 ?? 以外的数据
确实简单,但是要写好我感觉还是很有难度的。
2023-3-26 14:11
0
雪    币: 51
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
5
#include <iostream>
#include <vector>
#include <immintrin.h>

class FastSearchPattern {
public:
    // 构造函数,sig为模式串,sigLen为模式串长度
    FastSearchPattern(const char* sig, size_t sigLen) : sigLen(sigLen), firstSig(sig[0]) {
        ruleList.reserve(sigLen - 1);
        for (size_t i = 1; i < sigLen; ++i) {
            Rule rule;
            rule.mask = (1 << i) - 1; // 生成掩码
            rule.bytes[i - 1] = sig[i]; // 记录字节
            ruleList.push_back(rule); // 添加规则
        }
    }

    // 在pBuffer中查找所有匹配的位置,bufSize为pBuffer的大小
    std::vector<size_t> searchAll(void* pBuffer, size_t bufSize);

private:
    struct Rule {
        unsigned short mask; // 掩码
        unsigned char bytes[15]; // 字节
    };

    size_t sigLen; // 模式串长度
    unsigned char firstSig; // 模式串第一个字符
    std::vector<Rule> ruleList; // 规则列表
};

int main() {
    FastSearchPattern fsp("test", 4); // 创建FastSearchPattern对象
    char buffer[] = "this is a test string for testing"; // 待查找的字符串
    std::vector<size_t> result = fsp.searchAll(buffer, sizeof(buffer)); // 查找所有匹配的位置
    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << result[i] << std::endl; // 输出匹配位置
    }
    return 0;
}

用chatgpt修改的

2023-3-27 09:07
0
雪    币: 1585
活跃值: (182)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
2023-3-30 20:06
0
雪    币: 221
活跃值: (2391)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
7
强大!!!
2023-3-30 21:31
0
雪    币: 15613
活跃值: (4270)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
Mxixihaha 模糊匹配很简单,就是搜索可匹配的部分, 然后匹配到正常数据之后比较 ?? 以外的数据
能搜索类似 D? AB ?3 53之类的模糊搜索吗?
2023-5-11 11:50
0
游客
登录 | 注册 方可回帖
返回
//