二进制序列检测器

Question

有没有人知道在二进制数据块中检测37位序列的优化方法是最佳的。当然，我可以使用窗口进行强力比较(只需从索引0+next 36位开始比较，递增并循环，直到找到它)，但有没有更好的方法？也许是一些散列搜索，返回序列位于二进制块内的概率？或者我只是把那玩意儿从我的屁股里拉出来？无论如何，我将继续进行暴力搜索，但我很好奇是否有更优化的方法。顺便说一下，这是用C语言写的。

Answer 1

您可以将这些位视为{0,1}字母表中的字符，并对数据运行any of several相对有效的已知子字符串搜索算法。

Answer 2

如果您正在分析一个模式的前N位，那么根据前M位(当然不能是模式的一部分)确定从哪位继续模式搜索应该不难(如果模式是可以确定的)。

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
<--            N bits           -->
<--   'ugly' M bits    -->|<-- continue here

这应该会缩短它的使用时间。

当然，最有效的方法之一是使用像DFA这样的状态机来解析输入，但这似乎有点过头了。取决于您的使用场景。

Answer 3

如果您正在寻找的模式是fix，您可以构建一系列的数组，这些数组是掩码中的移位，以进行比较。要进行比较，请使用xor函数，如果返回0，则匹配。任何其他值都不匹配。这将允许检查字符串中的字节，只要数组中至少还有2个字节。在剩下2个字节的情况下，您将无法递增完整的8位。下面是一个17位的示例，但概念是相同的。(我正在寻找所有的位，因为它很容易在转换演示的比特时使用)

/* Data is passed in, and offset is the number of bits offset from the first
   bit where the mask is located
   returns true if match was found.
*/
bool checkData(char* data, int* offset)
{
    /* Mask to mask off the first bits  not being used or examined*/
    static char firstMask[8] = { 0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };

    /* Mask to mask off the end bits not used  or examined*/
    static char endMask[8] = { 0x80, 0xC0, 0xE0, 0x0F, 0xF8, 0xFC, 0xFE, 0xFF };

    /* Pattern which is being search, with each row being the about shifted and 
       columns contain the pattern to be compared.  for example index 0 is a 
       shift of 0 bits in the pattern and 7 is a shift of seven bits
       NOTE: Bits not being used are set to zero.  
    */
    static char pattern[8][3] = { { 0xFF, 0xFF, 0x80 },  /* Original pattern */
                                  { 0x8F, 0xFF, 0xC0 },  /* Shifted by one */
                                  { 0x3F, 0xFF, 0xE0 },  /* Shifted by two */
                                  { 0x1F, 0xFF, 0xF0 },
                                  { 0x0F, 0xFF, 0xF8 },
                                  { 0x07, 0xFF, 0xFC },
                                  { 0x03, 0xFF, 0xFE },
                                  { 0x01, 0xFF, 0xFF }}; /* shifted by seven */

    /* outer loop control variable */
    int lcv;

    /* inter loop control variable */
    int lcv2;

    /* value to to contain the value results */
    char value;

    /* if there is no match, pass back a negative number to indicate no match */
    *offset = -1;

    /* Loop through the shifted patterns looking for a match */
    for ( lcv = 0; lcv < 8 ; lcv++ ) 
    {
        /* check the first part of the pattern.  
           mask of part that is not to be check and xor it with the 
           first part of the pattern */

        value = (firstMask[lcv] & *data) ^ pattern[lcv][0];
        /* if value is not zero, no match, so goto the next */
        if ( 0 != value ) 
        {
            continue;
        }

        /* loop through the middle of the pattern make sure it matches
           if it does not, break the loop
           NOTE:  Adjust the condition to match 1 less then the number 
                  of 8 bit items  you are comparing
        */
        for ( lcv2 = 1; lcv2 < 2; lcv2++)
        {
            if ( 0 != (*(data+lcv2)^pattern[lcv][lcv2]))
            {
                break;
            }
        }

        /* if the end of the loop was not reached, pattern 
           does not match, to continue to the next one
           NOTE: See note above about the condition 
        */   
        if ( 2 != lcv2)
        {
          continue;
        }

        /* Check the end of the pattern to see if there is a match after masking
           off the bits which are not being checked.
        */  
        value = (*(data + lcv2) & endMask[lcv]) ^ pattern[lcv][lcv2];

        /* if value is not zero, no match so continue */
        if ( 0 != value ) 
        {
          continue;
        }
    }
    /* If the end of the loop was not reached, set the offset as it 
       is the number of bits the pattern is offset in the byte and 
       return true
    */
    if ( lcv < 8 ) 
    {
        *offset = lcv ;
        return true;
    }
    /* No match was found */
    return false;
}

这需要用户提供一个指向数据的指针，并为下一个字节调用它。用户需要确保他们不会在模式匹配中超过数据的末尾。

如果在模式的早期没有匹配，它将不会继续检查其余的比特，这应该有助于搜索时间。

这个实现应该是相当可移植的，但它需要对37位进行一些返工。