为对某软件的指定模块打特征码补丁，最近研究学习了各种搜索算法（Sunday、Shift_And、BNDM等），对比发现，内存特征码搜索还是下面两位大佬基于SSE2指令集的搜索算法速度最快。
于是认真学习了两位大佬的文章，根据自己的理解做了一点点改造和优化，分享给大家，欢迎拍砖！！！

学习参考文章如下，感谢大佬们分享的好文！
https://bbs.kanxue.com/thread-209946.htm
https://www.52pojie.cn/thread-1854232-1-1.html

主要改进：
①通过掩码的方式使其支持 前、中、后通配符 及半字节；
②通过SSE2指令集找到特征码字节序列中的第一个不为'??'的元素后，后续的字节只比较不是'??'的特征字节，优化比较字节数。

通过测试，根据不同的特征码型式(特征码长度不同、通配符数量不同等)，在我的环境中，比优化前（上面文章中代码）搜索速度提升5%~15%左右。

本人不是计算机专业，也不从事相关工作，纯属业余爱好，代码难免错漏，更谈不上优雅，望各位大佬批评指正！

/****************************************************************************************
* @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[0]; // 特征码字节序列的首地址
        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[vecIdx.at(iCh)];
                                // currPattern[vecIdx.at(iCh)] = currPtnCh + 0x1;  // 要排除本函数自身的特征码字节序列，可以打开这两行
                                // currEqual为0时表示两个字节相同(包含半字节'?'的判断)
                                currEqual = ( ( currAddress[vecIdx.at(iCh)] | vecMsk.at(vecIdx.at(iCh)) ) ^ currPtnCh );
                                // currPattern[vecIdx.at(iCh)] = 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;
}

[课程]Android-CTF解题方法汇总！