c - 在位数组中查找字节的高效算法

Question

给定一个字节数组 uint8_t data[N]什么是查找字节的有效方法 uint8_t search在其中即使search不是八位字节对齐？即 search 的前三位可能在 data[i] data[i+1] 中接下来的 5 位.

我目前的方法是创建一个 bool get_bit(const uint8_t* src, struct internal_state* state)函数(struct internal_state 包含一个向右移位的掩码，& 用 src 编辑并返回，保持 size_t src_index < size_t src_len )，将返回的位左移到 uint8_t my_register 中并将其与 search 进行比较每次，并使用 state->src_index和 state->src_mask获取匹配字节的位置。

有更好的方法吗？

Answer 1

如果您要在大型数组中搜索八位模式，您可以在 16 位值上实现一个滑动窗口，以检查搜索到的模式是否是构成该 16 位值的两个字节的一部分。

为了便携，您必须处理字节顺序问题，这是由我的实现通过构建 16 位值来手动搜索模式来完成的。高字节始终是当前迭代的字节，低字节是后续字节。如果你做一个像 value = *((unsigned short *)pData) 这样的简单转换，你将在 x86 处理器上遇到麻烦......

Once value, cmp and mask setup cmp and mask 是转移。如果在 hi 高字节内未找到模式，则循环继续检查下一个字节作为起始字节。

这是我的实现，包括一些调试打印输出(如果未找到模式，该函数返回位位置或 -1):

int findPattern(unsigned char *data, int size, unsigned char pattern)
{
    int result = -1;
    unsigned char *pData;
    unsigned char *pEnd;
    unsigned short value;
    unsigned short mask;
    unsigned short cmp;
    int tmpResult;



    if ((data != NULL) && (size > 0))
    {
        pData = data;
        pEnd = data + size;

        while ((pData < pEnd) && (result == -1))
        {
            printf("\n\npData = {%02x, %02x, ...};\n", pData[0], pData[1]);

            if ((pData + 1) < pEnd)   /* still at least two bytes to check? */
            {
                tmpResult = (int)(pData - data) * 8;   /* calculate bit offset according to current byte */

                /* avoid endianness troubles by "manually" building value! */
                value = *pData << 8;
                pData++;
                value += *pData;

                /* create a sliding window to check if search patter is within value */
                cmp = pattern << 8;
                mask = 0xFF00;
                while (mask > 0x00FF)   /* the low byte is checked within next iteration! */
                {
                    printf("cmp = %04x, mask = %04x, tmpResult = %d\n", cmp, mask, tmpResult);

                    if ((value & mask) == cmp)
                    {
                        result = tmpResult;
                        break;
                    }

                    tmpResult++;   /* count bits! */
                    mask >>= 1;
                    cmp >>= 1;
                }
            }
            else
            {
                /* only one chance left if there is only one byte left to check! */
                if (*pData == pattern)
                {
                    result = (int)(pData - data) * 8;
                }

                pData++;
            }
        }
    }

    return (result);
}