如何快速找到C中的不匹配模式

陈怎么

前提:

  1. 我不能使用malloc。
  2. 错误将在两个字节内发生,这意味着我可以逐字搜索。
  3. 我的CPU是32位ARM11,在此期间没有操作系统。
  4. 前两个字节很重要,如果前两个字节为0x00,则意味着其余所有字节应为0x00。
  5. 如果前两个字节为0xFF,则其余所有字节应为0xFF。
  6. 如果前两个字节不是0x0000和0xFFFF,我只是报告一个错误,不需要比较其余字节。

我读取了256KB的块数据,该数据应该只有两种状态:

  1. 全部为0xFF
  2. 全部0x00

但是,某些数据可能会更改为不可预测的值。我需要找到他们。我可以一个字节一个字节地搜索它,但是似乎太慢了,所以我决定使用二分法进行搜索-看起来像:

  1. 将读出的数据分成相等的一半,然后进行比较。
  2. 如果两者都不等于0或F,则意味着数据在两边都损坏了,我只需要找到最早的那个,所以我应该放弃第二部分,然后再次将第一部分除。如果只有一方有问题,请放弃好一方并专注于有问题的方面。e
  3. 循环以上的想法
  4. 似乎经过17次之后,应该找到重点了。

如何将代码写入循环?我需要17种不同大小的参考静态数据并使用memcmp吗?

我当前的代码如下:

unsigned char gReferData1[2] = {0xFF, 0xFF};
unsigned char gReferData2[2] = {0x00, 0x00};

int main(void)
{
    int i = 0, result1 = 0, result2 =0;

    read_somewhere(readBuff, sizeof(readBuff)); //read out data

    //first test first two bytes
    result1 = memcmp(gReferData1, readBuff, 2); //test if 0xFFFF
    result2 = memcmp(gReferData2, readBuff, 2); //test if 0x0000
    if(result1 == 0)
    {
        // means all rest data should be 0xFF 
        for(i=2; i<(0x40000/2); i++)
        {
            result1 = memcmp(gReferData1, readBuff + offet, 2); //test if 0xFFFF
            if(result1 != 0)
            {
                //means find
                // do error handle
            }
            offset+=2;
        }
    }
    else if(result2 == 0)
    {
        // means all rest data should be 0x00
        for(i=2; i<(0x40000/2); i++)
        {
            result2 = memcmp(gReferData2, readBuff + offet, 2); //test if 0x0000
            if(result2 != 0)
            {
                //means find
                // do error handle
            }
            offset+=2;
        }
    }
    else
    {
        //just error
        // do error handle
    }

    return 0;
}
菲利普

为了在随机位置发现缺陷,您将需要检查每个字节至少一次。没有比O(n)更快的算法了。

但是,您提出的算法要求检查每个字节不止一次。为了“将读出的数据分成相等的一半,然后进行比较”,您将必须读取每个字节。这是memcmp内部操作:从头到尾循环遍历两个内存段,直到出现差异为止。这不是魔术。它无法比简单的循环更有效地做到这一点。

其中优化可能会加快这(测试和测量它!)可能是无法通过数据阵列逐字节但在步骤走sizeof(long),然后施放该段long你比较之前。这利用了以下事实:在许多32位CPU(不是全部,请对其进行测试和测量!)上,比较两个32位值所花的时间不会比比较两个8位值所花的时间更多。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章