[原创]暴力搜索内存必备Sig特征码SSE2加速(支持模糊匹配)

暴力搜索爱好者必备工具函数，SSE2加速，支持模糊匹配（内核，用户，32BIT，64BIT通用）
这样基本就够用了，如搜索字符串、特征码，模糊匹配动态代码、函数地址、数据地址等
因为某些原因需要暴力搜索整个物理内存（本人电脑是8G物理内存），但极端情况下（8G内存
全部命中失败，特征码长度超过30位）时效率不能满足需要（一次完整遍历需要9025毫秒）。
又因为某些原因，在下几年前曾实现了一套 stristr strista 等的 sse2 加速版本。当时实
现时 google 百度了几乎所有的相关信息（发现还蛮多人在搞这个的，因为标准库刚好缺这个
函数），并反复 profile 了各种实现，从代码级别到算法级别，自认实现了我所知的最快版
本。
因此，为了能愉快的玩耍一下，所以优化了一下标准SIG特征码匹配查找函数（655毫秒），加
速了大概13倍。
想必来这个论坛的兄弟姐妹没有几位的代码库里没有与此相似工具函数，小弟不才，分享给大
家，抛砖引玉。

#ifdef WIN32

#    ifndef WIN32_LEAN_AND_MEAN 

#        define WIN32_LEAN_AND_MEAN

#    endif

#    include <windows.h>

#    ifndef PAGE_SIZE

#        define PAGE_SIZE 0x1000

#    endif

#else

#    include <ntifs.h>

#    ifndef MAX_PATH

#        define MAX_PATH 260

#    endif

#endif

#include <emmintrin.h>

// 1、搜索字符串

//    SigPattern = "This is a null terminated string."

//    SigMask = NULL or "xxxxxxxxxxx" or "x?xx????xxx"

//

// 2、搜索代码、函数或数据

//    SigPattern = "\x8B\xCE\xE8\x00\x00\x00\x00\x8B"

//    SigMask = "xxxxxxxx" or "xxx????x"

//

// Mask 中的 ? 可用于模糊匹配，在被搜索代码片段中有动态变化的内容时使用(如指令操作的地址、数据等)

//

// 这里是搜索虚拟内存对应的子函数，物理内存操作方面，各人有各人的方法，与此主题无关就省略了

//

ULONGLONG SearchVirtualMemory(ULONGLONG VirtualAddress, ULONGLONG VirtualLength, PUCHAR SigPattern, PCHAR SigMask)

{

    // SigMask 未指定时自动生成简化调用（如只是想简单搜索字符串）

    CHAR TmpMask[PAGE_SIZE];

    if (SigMask == NULL || SigMask[0] == 0) {

        ULONG SigLen = (ULONG)strlen((PCHAR)SigPattern);

        if (SigLen > PAGE_SIZE - 1) SigLen = PAGE_SIZE - 1;

        memset(TmpMask, 'x', SigLen);

        TmpMask[SigLen] = 0;

        SigMask = TmpMask;

    }

    // 常规变量

    PUCHAR MaxAddress = (PUCHAR)(VirtualAddress + VirtualLength);

    PUCHAR BaseAddress;

    PUCHAR CurrAddress;

    PUCHAR CurrPattern;

    PCHAR CurrMask;

    BOOLEAN CurrEqual;

    register UCHAR CurrUChar;

    // SSE 加速相关变量

    __m128i SigHead = _mm_set1_epi8((CHAR)SigPattern[0]);

    __m128i CurHead, CurComp;

    ULONG MskComp, IdxComp;

    ULONGLONG i, j;

    //

    // 第一层遍历使用 SSE 将逐字节加速为逐 16 字节每次（最终加速 12 倍获益主要来源与此）

    //

    // 第二层子串匹配不能使用 SSE 加速，原因有四

    //     1. SSE 虽为单指令多数据，但单个指令 CPU 周期比常规指令要高

    //

    //     2. 从概率上来说，子串匹配时第一个字节命中失败与 SSE 一次性对比 16 个字节命中失败在概率上几乎相等

    //

    //     3. 根据实验采用 SSE 优化第二层子串匹配将显著降低最终查找速度

    //

    //     4. 理论上，即使 SSE 单条指令与常规指令具有同样的CPU周期，最高也只能加速 16 倍

    //

    for (i = 0; i <= VirtualLength - 16; i += 16)

    {

        CurHead = _mm_loadu_si128((__m128i*)(VirtualAddress + i));

        CurComp = _mm_cmpeq_epi8(SigHead, CurHead);

        MskComp = _mm_movemask_epi8(CurComp);

        BaseAddress = (PUCHAR)(VirtualAddress + i);

        j = 0;

        while (_BitScanForward(&IdxComp, MskComp))

        {

            CurrAddress = BaseAddress + j + IdxComp;

            CurrPattern = SigPattern;

            CurrMask = SigMask;

            for (; CurrAddress <= MaxAddress; CurrAddress++, CurrPattern++, CurrMask++)

            {

                // 因为是暴力搜索整个系统的物理内存，而本函数自身的堆栈区当然也属于整个物理内存的一部分

                // 因此为了避免匹配到参数 SigPattern 本身，对其做了相应过滤操作，如不需要可以自行简化 2 行

                CurrUChar = *CurrPattern;

                // *CurrPattern = CurrUChar + 0x1;

                CurrEqual = (*CurrAddress == CurrUChar);

                // *CurrPattern = CurrUChar;

                if (!CurrEqual) { if (*CurrMask == 'x') break; }

                if (*CurrMask == 0) { return (ULONGLONG)(BaseAddress + j + IdxComp); }

            }

            ++IdxComp;

            MskComp = MskComp >> IdxComp;

            j += IdxComp;

        }

    }

    return 0x0;

}