用于在位阵列中查找字节的高效算法

Question

鉴于为bytearray uint8_t data[N]什么是要找到一个字节的有效方法,uint8_t search在其中,即使search是没有被字节对齐？即前三位search可以在data[i]和接下来的5位data[i+1].

我当前的方法涉及创建一个bool get_bit(const uint8_t* src, struct internal_state* state)函数(struct internal_state包含一个右移位的掩码,&用src编辑并返回,维护size_t src_index < size_t src_len),将返回的位移动到a uint8_t my_register并search每次比较它,并使用state->src_index和state->src_mask获取匹配字节的位置.

有更好的方法吗？

Answer 1

我不知道这是否会更好，但我会使用滑动窗口。

uint counter = 0, feeder = 8;
uint window = data[0];

while (search ^ (window & 0xff)){
    window >>= 1;
    feeder--;
    if (feeder < 8){
        counter++;
        if (counter >= data.length) {
            feeder = 0;
            break;
        }
        window |= data[counter] << feeder;
        feeder += 8;
    }
}

//Returns index of first bit of first sequence occurrence or -1 if sequence is not found
return (feeder > 0) ? (counter+1)*8-feeder : -1;

另外，通过一些更改，您可以使用此方法来搜索任意长度（1 到 64-array_element_size_in_bits）位序列。