hunting for a particular pair of bits ’10’ or ’01’ in a character array
这可能是一个有点理论的问题。我有一个包含网络数据包的 char 字节数组。我想每 66 位检查一对特定位(\\’01\\’ 或 \\’10\\’)的出现。也就是说，一旦我找到第一对位，我就必须跳过 66 位并再次检查同一对位的存在。我正在尝试使用掩码和班次实现一个程序，它有点变得复杂。我想知道是否有人可以提出更好的方法来做同样的事情。
到目前为止，我编写的代码看起来像这样。虽然它不完整。
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
test_sync_bits(char *rec, int len)
{ uint8_t target_byte = 0; int offset = 0; int save_offset = 0; uint8_t *pload = (uint8_t*)(rec + 24); /*hunt for the first ’10’ or ’01’ combination.*/ |
我想出的另一个想法是使用下面定义的结构
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
typedef struct
{ int remainder_bits; int extra_bits; int extra_byte; }remainder_bits_extra_bits_map_t; static remainder_bits_extra_bits_map_t sync_bit_check [] = |
我的方法正确吗？任何人都可以提出任何改进建议吗？
- 我建议使用或编写某种位数组(也许是 boost\\’s dynamic_bitset？)。就个人而言，我自己写的。但它应该处理在位位置 y 读取 x 位并处理所有烦人的边缘情况。然后你可以更简洁地编写你的想法。
- 你能显示一个包含这些同步位的 100 字节的十六进制转储吗？
查找表的想法
只有 256 个可能的字节。这足以让您构建一个查找表，其中包含一个字节中可能发生的所有可能的位组合。
查找表值可以记录模式的位位置，也可以有特殊值来标记可能的延续开始或延续结束值。
编辑：
我认为延续值会很愚蠢。相反，要检查与字节重叠的模式，请将字节和 OR 与另一个字节相移，或手动检查每个字节的结束位。也许 ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x80 和 ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x01 对你有用。
你没有说，所以我也假设你正在寻找任何字节中的第一个匹配项。如果您正在寻找每个匹配项，然后检查 66 位的结束模式，那是一个不同的问题。
要创建查找表，我会编写一个程序来为我完成。它可以是您最喜欢的脚本语言，也可以是 C。程序会编写一个类似于以下内容的文件：
|
1
2 3 4 5 6 7 8 9 10 11 12 |
/* each value is the bit position of a possible pattern OR’d with a pattern ID bit. */
/* 0 is no match */ #define P_01 0x00 #define P_10 0x10 const char byte_lookup[256] = { /* 0: 0000_0000, 0000_0001, 0000_0010, 0000_0011 */ 0, 2|P_01, 3|P_01, 3|P_01, /* 4: 0000_0100, 0000_0101, 0000_0110, 0000_0111, */ 4|P_01, 4|P_01, 4|P_01, 4|P_01, /* 8: 0000_1000, 0000_1001, 0000_1010, 0000_1011, */ 5|P_01, 5|P_01, 5|P_01, 5|P_01, }; |
乏味。这就是为什么我会编写一个程序来为我编写它。
- 256 个可能的字节是什么意思？你能解释一下吗？
- @liv2hak：2^8 = 256。一个字节内有 256 种不同的位组合。我的想法是一次扫描一个字节，而不是像你做的那样一次扫描一个字节。
- 好的。我决定继续使用 byte_lookup 的想法。但首先你已经定义了 P_01 0x00。我认为它应该是 0x01(因为 0x01 和 0x10 是我正在寻找的位模式。)。我仍然不明白你为什么会或可能的模式(所有组合00,01,10 和 11 在所有具有模式 ID 位的位置(这是什么意思？))抱歉打扰你。但我发现很难理解这个概念。
- 我只看到 9*4 = 36 个有效组合的总数。它们基本上是位位置的 00,01,01,11 对。(0,1)(1,2)(2,3)(3,4)( 4,5)(5,6)(6,7)(7,0)(重叠案例) 其中9*2 = 18个案例有效，其他18个案例无效(00,11个案例) .我的逻辑听起来合理吗？我怀疑我可能遗漏了您所说的内容。
- @liv2hak：P_01 和 P_10 是为了让您知道找到了什么模式。 if( (byte_lookup[byte] & 0x10) == P_01) {} if( (byte_lookup[byte] & 0x10) == P_10) {}
这是从流中读取时经常出现的经典去块问题的变体。也就是说，数据以与您希望扫描的单位大小不匹配的离散单位出现。这方面的挑战是 1)缓冲(这不会影响您，因为您可以访问整个数组)和 2)管理所有状态(如您所见)。一个好的方法是编写一个消费者函数，其行为类似于 fread() 和 fseek() 来维护自己的状态。它返回您感兴趣的请求数据，并与您提供的缓冲区正确对齐。
来源：https://www.codenong.com/7829282/
