c-在9位体系结构中搜索8位对齐字符串

Question

我需要在字符流中搜索一个8位对齐的位字符串"00 00 01"(十六进制)。在一个典型的体系结构上，我会这样做：

char *find(char *first, char *last)
{
char pattern[] = {0, 0, 1};
char *p;
for (p = first; last - p >= sizeof(pattern); ++p) {
if (!memcmp(p, pattern, sizeof(pattern))
return p;
}
return 0;
}

然而，如果char不是8位，我不知道如何实现这个函数(具有良好的性能)。

Answer 1

这个任务非常有趣，所以我将提供另一个选项。它不需要将流比特转换为字符，相反，我们可以使用以下模式。

由于您的位值应具有8位对齐，可能的字符索引/它的起始位选项为：

char 0, bit 0 (its starting bit index)
char 0, bit 8
char 1, bit 7
char 2, bit 6
char 3, bit 5
char 4, bit 4
char 5, bit 3
char 6, bit 2
char 7, bit 1

对于字符8，起始位为0，因此与第一项(字符0，位0)相同

现在，除了第一个位置，剩下的8种可能性很容易通过单一表达式验证：

伪代码：

int   pattern = 0x000001L;
int   mask = ~pattern;
int   char_idx = 0;
while (first <= last-2)   // need to compare 3 chars
{
int   value = *((int*)first)); // this will actually access 4 chars, if stream has no 0 terminator, it will produce exception
// special [char 0, bit 0] case
if ( !char_idx && (value & mask) == pattern )
{
// match! do something with *first
}
if ( ((value >> (8 - char_idx)) & mask) == pattern ) 
{
// match! do something with *first
}
if ( ++char_idx == 9 )
char_idx = 0;
first++;
}

注意：如果您的int不是36位，您可以进行逐字符比较

Answer 2

以下代码应在以下条件下工作：

• long为36位(4个字节，每个字节9位)
• big-endian架构；CCD_ 2值的最高有效位存储在最低地址
• long *可以指向任何地址，而不一定是四的倍数；换句话说，没有字或双字对齐
• 我们正在搜索的模式是24位(可以调整，但这种方法的绝对最大值是28位)

函数不会返回char *，因为这并不能说明实际的位位置。相反，它返回匹配之前的8位组的数量，如果没有匹配，则返回-1。

long find(char *first, char *last)
{
long pattern = 0x000001L;      // the bit string we are searching for
long bitmask = -0x1000L;       // initial mask: 24 ones followed by 12 zeroes
long maxcount = ((last - first) * 9 - 24) / 8;    // 24 = pattern size (bits)
long count;                    // counts the 8-bit groups
char *slider = first;          // follows the 9-bit bytes
for (count = 0; count <= maxcount; count++) {
long actual = (*(long *)slider & bitmask);
long expect = (bitmask & -bitmask) * pattern;
if (actual == expect) return count;
if (bitmask & 0xFF) {    // less than 8 zeroes on the right-hand side
slider++;
bitmask <<= 1;       // shift 9 bits to left, then 8 bits to right
}
else {
bitmask >>= 8;       // shift 8 bits to the right, only
}
}
return -1;
}

我不知道如何测试它，所以它是在"原样"的基础上进行的。

该函数使用的bitmask正好有24个1。位连续向右移动8个位置。如果"1"有被移出的危险，则内存指针slider递增，bitmask相应调整。

slider被定义为char *，在被取消引用时被强制转换为long *，一次检索四个9位字节。如果我将slider定义为long *，那么slider++将使指针前进4个字节，而不是1个字节。

这里有一个例子来解释这个模糊的表达式：(bitmask & -bitmask) * pattern

• 00001111111111111111111111100000000=bitmask
• 111100000000000000000000000100000000=-bitmask
• 00000000000000000000000000000100000000=(bitmask & -bitmask)
• 0000ppppppppppm ppppppPPpppppp00000000=(bitmask & -bitmask) * pattern

如您所见，它将pattern(24位long0)与bitmask对齐。

请告诉我这对你有什么好处。

Answer 3

9位架构到底是什么？：)所以"char"类型也是9位？：)

快速而肮脏的方法是将char流转换为bit-to-char表示，换句话说，每个char表示一个位。然后只需搜索"000001"的子字符串，对齐8个字符(先是memcmp[0]，然后是memcp[8]等)。。。当然，以"二进制"/正确的方式进行操作是可能的，但根据流的长度，这可能是"良好性能"的方式。。。