如果您的掩码是 8 位的倍数,则您的搜索将变成一个相对微不足道的字节比较,并且任何子字符串搜索算法就足够了(我不建议转换为字符串并使用内置搜索,因为您可能会遇到字符验证失败的问题问题。)
sequence = <list of 8-bit integers>
mask = [0b10010001, 0b01101101]
matches = my_substring_search(sequence, mask)
对于大于 8 位但不是 8 倍数的掩码,我建议将掩码截断为 8 的倍数并使用与上述相同的子字符串搜索。然后对于找到的任何匹配项,您可以测试其余部分。
sequence = <list of 8-bit integers>
mask_a = [0b10010001]
mask_b = 0b01100000
mask_b_pattern = 0b11110000 # relevant bits of mask_b
matches = my_substring_search(sequence, mask_a)
for match in matches:
if (sequence[match+len(mask_a)] & mask_b_pattern) == mask_b:
valid_match = True # or something more useful...
如果sequence
是 4096 字节的列表,您可能需要考虑部分之间的重叠。这可以通过制作sequence
一个4096+ceil(mask_bits/8.0)
字节列表来轻松完成,但每次读取下一个块时仍然只前进 4096。
作为生成和使用这些掩码的演示:
class Mask(object):
def __init__(self, source, source_mask):
self._masks = list(self._generate_masks(source, source_mask))
def match(self, buffer, i, j):
return any(m.match(buffer, i, j) for m in self._masks)
class MaskBits(object):
def __init__(self, pre, pre_mask, match_bytes, post, post_mask):
self.match_bytes = match_bytes
self.pre, self.pre_mask = pre, pre_mask
self.post, self.post_mask = post, post_mask
def __repr__(self):
return '(%02x %02x) (%s) (%02x %02x)' % (self.pre, self.pre_mask,
', '.join('%02x' % m for m in self.match_bytes),
self.post, self.post_mask)
def match(self, buffer, i, j):
return (buffer[i:j] == self.match_bytes and
buffer[i-1] & self.pre_mask == self.pre and
buffer[j] & self.post_mask == self.post)
def _generate_masks(self, src, src_mask):
pre_mask = 0
pre = 0
post_mask = 0
post = 0
while pre_mask != 0xFF:
src_bytes = []
for i in (24, 16, 8, 0):
if (src_mask >> i) & 0xFF == 0xFF:
src_bytes.append((src >> i) & 0xFF)
else:
post_mask = (src_mask >> i) & 0xFF
post = (src >> i) & 0xFF
break
yield self.MaskBits(pre, pre_mask, src_bytes, post, post_mask)
pre += pre
pre_mask += pre_mask
if src & 0x80000000: pre |= 0x00000001
pre_mask |= 0x00000001
src = (src & 0x7FFFFFFF) * 2
src_mask = (src_mask & 0x7FFFFFFF) * 2
此代码不是完整的搜索算法,它构成验证匹配的一部分。Mask 对象由源值和源掩码构成,均左对齐且(在此实现中)32 位长:
src = 0b11101011011011010101001010100000
src_mask = 0b11111111111111111111111111100000
缓冲区是一个字节值列表:
buffer_1 = [0x7e, 0xb6, 0xd5, 0x2b, 0x88]
一个 Mask 对象生成一个移位掩码的内部列表:
>> m = Mask(src, src_mask)
>> m._masks
[(00 00) (eb, 6d, 52) (a0 e0),
(01 01) (d6, da, a5) (40 c0),
(03 03) (ad, b5, 4a) (80 80),
(07 07) (5b, 6a, 95) (00 00),
(0e 0f) (b6, d5) (2a fe),
(1d 1f) (6d, aa) (54 fc),
(3a 3f) (db, 54) (a8 f8),
(75 7f) (b6, a9) (50 f0)]
中间元素是完全匹配的子字符串(没有简洁的方法可以按原样从该对象中获取它,但它是m._masks[i].match_bytes
)。一旦你使用了一种有效的算法来找到这个子序列,你就可以使用 来验证周围的位m.match(buffer, i, j)
,其中i
是第一个匹配字节j
的索引,是最后一个匹配字节之后的字节的索引(例如buffer[i:j] == match_bytes
)。
在buffer
上面,可以从第 5 位开始找到位序列,这意味着_masks[4].match_bytes
可以在buffer[1:3]
. 因此:
>> m.match(buffer, 1, 3)
True
(随意使用、改编、修改、出售或以任何可能的方式折磨此代码。我非常喜欢将它放在一起 - 一个有趣的问题 - 尽管我不会对任何错误负责,所以请确保你彻底测试它!)