对SSE2模式匹配算法SSE2PatternFind的一点改造优化
本帖最后由 haogl 于 2024-9-4 10:35 编辑为对某软件的指定模块打特征码补丁，最近研究学习了各种搜索算法（Sunday、Shift_And、BNDM等），对比发现，内存特征码搜索还是下面两位大佬基于SSE2指令集的搜索算法速度最快。
于是认真学习了两位大佬的文章，根据自己的理解做了一点点改造和优化，分享给大家，欢迎拍砖！！！
学习参考文章如下，感谢大佬们分享的好文！
https://bbs.kanxue.com/thread-209946.htm
https://www.52pojie.cn/thread-1854232-1-1.html
主要改进：
①通过掩码的方式使其支持 前、中、后通配符 及半字节；
②通过SSE2指令集找到特征码字节序列中的第一个不为'??'的元素后，后续的字节只比较不是'??'的特征字节，优化比较字节数。
通过测试，根据不同的特征码型式(特征码长度不同、通配符数量不同等)，在我的环境中，比优化前（上面文章中代码）搜索速度提升5%~15%左右。
本人不是计算机专业，也不从事相关工作，纯属业余爱好，代码难免错漏，更谈不上优雅，望各位大佬批评指正！
20240904------判断特征码全都是'??'时，返回FALSE；修改结束搜索的条件。
/****************************************************************************************
* @brief SSE2PatternFindEx-使用SSE2加速暴力搜索内存特征码(支持模糊匹配)-By.Haogl优化-20240903
* @Param retList 用于存储搜索到的特征码对应的内存地址
* @param searchStartAddr 需要搜索的起始内存地址
* @param searchSize 要搜索的内存块的大小,可上负下正（以字节为单位）
* @param myPattern 搜索特征码，支持通配符??、?，如："?? 5? 77 ?? 88 ?? ?A ??"
* @param offsetSize 特征码地址离目标地址的偏移距离，上负下正，0不偏移
* @param searchNum 搜索个数，0为搜索整个模块，默认为0
* @Return 成功返回TRUE，失败返回FALSE
*
第一层遍历使用 SSE 将逐字节加速为逐 16 字节每次（最终加速 12 倍获益主要来源与此）
第二层子串匹配不能使用 SSE 加速，原因有四
1. SSE 虽为单指令多数据，但单个指令 CPU 周期比常规指令要高
2. 从概率上来说，子串匹配时第一个字节命中失败与 SSE 一次性对比 16 个字节命中失败在概率上几乎相等
3. 根据实验采用 SSE 优化第二层子串匹配将显著降低最终查找速度
4. 理论上，即使 SSE 单条指令与常规指令具有同样的CPU周期，最高也只能加速 16 倍
*/
// 特征码初始化，将传入的特征码字符串myPattern格式转化为目标特征码字节序列
BOOL InitPattern(const std::string& myPattern, std::vector<UCHAR>& vecPtn, std::vector<UCHAR>& vecMsk, std::vector<ULONG>& vecIdx)
{
std::string patternText = myPattern;
if (patternText.empty()) { return FALSE; }
patternText.erase(std::remove(patternText.begin(), patternText.end(), ' '), patternText.end());// 去除所有空格
for (char ch : patternText) {
if (ch != '?' && !((ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'F') || (ch >= 'a' && ch <= 'f'))) { return FALSE; }
}
if (patternText.length() % 2 != 0) { return FALSE; }
ULONG len = patternText.length() / 2;
for (ULONG i = 0; i < len; i++)
{
std::string tmpS = patternText.substr(i * 2, 2);
if ("??" != tmpS) // 不是"??"的特征字符
{
if ('?' == tmpS.at(0)) // 左半字节为'?'
{
tmpS.at(0) = 'F';
vecMsk.push_back(UCHAR(0xFF) << 4);
}
else if ('?' == tmpS.at(1)) // 右半字节为'?'
{
tmpS.at(1) = 'F';
vecMsk.push_back(UCHAR(0xFF) >> 4);
}
else
{
vecMsk.push_back(UCHAR(0x00));
}
vecIdx.push_back(i);
}
if ("??" == tmpS) // 为"??"的特征字符
{
tmpS.at(0) = 'F';
tmpS.at(1) = 'F';
vecMsk.push_back(UCHAR(0xFF));
}
vecPtn.push_back(strtoul(tmpS.c_str(), nullptr, 16));
}
if (0 == vecIdx.size()) { return FALSE; }
return TRUE;
}
// 使用SSE2加速暴力搜索内存特征码(支持模糊匹配，如："?? 5? 77 ?? 88 ?? ?A ??")
BOOL SSE2PatternFindEx(std::vector<ULONGLONG>& retList, const ULONGLONG searchStartAddr,
const LONGLONG searchSize, const std::string& myPattern, const LONGLONG offsetSize, const ULONGLONG searchNum)
{
if (0 == searchStartAddr || 0 == searchSize) { return FALSE; }
ULONGLONG realStartAddr = searchStartAddr;
if ((searchSize < 0) && (searchStartAddr > std::abs(searchSize))) //searchSize可上负下正（以字节为单位）
{
realStartAddr = searchStartAddr - std::abs(searchSize);
}
std::vector<UCHAR> vecPtn;// 存储转换后的特征码字节序列
std::vector<UCHAR> vecMsk;// 存储特征字符串中'??'、'?'的掩码('??'和'?'用1替代，非'?'为0)
std::vector<ULONG> vecIdx;// 存储不是'??'的特征码字节在原始特征码字节序列(传入的有'??'的特征码)中的索引下标
if ( !InitPattern(myPattern, vecPtn, vecMsk, vecIdx) ) { return FALSE; }
// 常规变量
PUCHAR maxAddress = (PUCHAR)(realStartAddr + std::abs(searchSize));
PUCHAR baseAddress;
PUCHAR currAddress;
PUCHAR currPattern = &vecPtn; // 特征码字节序列的首地址
UCHAR currEqual;
register UCHAR currPtnCh;
// SSE加速相关变量
__m128i ptnHead = _mm_set1_epi8(vecPtn.at(vecIdx.at(0)));
__m128i headMsk = _mm_set1_epi8(vecMsk.at(vecIdx.at(0)));
__m128i curHead, curComp;
ULONG bitComp, idxComp;
ULONG j;
for (ULONGLONG i = vecIdx.at(0); i <= searchSize - 16; i += 16)
{
baseAddress = (PUCHAR)(realStartAddr + i);
curHead = _mm_loadu_si128((__m128i*)(baseAddress));
curHead = _mm_or_si128(curHead, headMsk); // 将对应特征码中'?'位置的二进制位替换为1
curComp = _mm_cmpeq_epi8(ptnHead, curHead);
bitComp = _mm_movemask_epi8(curComp);
j = 0;
while (_BitScanForward(&idxComp, bitComp))
{
currAddress = baseAddress + j + idxComp - vecIdx.at(0);
for ( ULONG iCh = 1; iCh < vecIdx.size() && (size_t)currAddress <= (size_t)maxAddress - vecPtn.size(); iCh++ )
{
currPtnCh = currPattern;
// currPattern = currPtnCh + 0x1;// 要排除本函数自身的特征码字节序列，可以打开这两行
// currEqual为0时表示两个字节相同(包含半字节'?'的判断)
currEqual = ( ( currAddress | vecMsk.at(vecIdx.at(iCh)) ) ^ currPtnCh );
// currPattern = currPtnCh;
if ( currEqual ) { break; } // currEqual不为0时两个字节不相同
if ( iCh + 1 == vecIdx.size() ) // 找到特征码字节序列
{
retList.push_back((ULONGLONG)(currAddress + offsetSize));
if ( searchNum != 0 && retList.size() >= searchNum ) { return TRUE; }
break;
}
}
++idxComp;
bitComp = bitComp >> idxComp;
j += idxComp;
}
}
return TRUE;
} 太牛了，学习中 先收藏，再学习。 本帖最后由 Elaineliu 于 2024-9-4 16:17 编辑
你应该把代码放到github上
https://www-igm.univ-mlv.fr/~lecroq/string/
精确字符串匹配算法 36个，不知道你用的是哪个 有没有使用例子啊？来一个调用实例啊 收藏了，学习学习 这个适用于什么vs？？还有就是需要包含哪些h文件啊
页:
[1]