CRC32 计算 CRC 消息开头的 CRC 散列

Question

我需要计算消息的 CRC 并将其放在该消息的开头，以便带有“前置”补丁字节的消息的最终 CRC 等于 0。我能够做到这在几篇文章的帮助下非常容易，但不适用于我的特定参数。问题是我必须使用给定的 CRC32 算法来计算内存块的 CRC，但我没有计算那 4 个补丁字节/“CRC 类型”的“反向”算法。给定的 CRC32 算法的参数是:

• 多项式:0x04C11DB7
• 字节顺序:大端
• 初始值:0xFFFFFFFF
• 反射:假
• 异或:0L
• 测试流:0x0123、0x4567、0x89AB、0xCDEF 结果为 CRC = 0x612793C3

计算CRC的代码(半字节，表驱动，希望数据类型定义不言自明):

uint32 crc32tab(uint16* data, uint32 len, uint32 crc)
{
    uint8 nibble;
    int i;
    while(len--)
    {
        for(i = 3; i >= 0; i--)
        {
            nibble = (*data >> i*4) & 0x0F;
            crc = ((crc << 4) | nibble) ^ tab[crc >> 28];
        }
        data++;
    }

    return crc;
}

所需的表是(我认为短 [16] 表应该包含大 [256] 表中的每第 16 个元素，但该表实际上包含前 16 个元素，但事实就是这样提供给我):

static const uint32 tab[16]=
{
    0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
    0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
    0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
    0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};  

我修改了代码，使其不那么长，但功能保持不变。问题是这个正向 CRC 计算看起来更像反向/反向 CRC 计算。
我花了将近一周的时间试图找出正确的多项式/算法/表格组合，但没有成功。如果有帮助，我想出了与上面的表驱动代码相对应的按位算法，尽管这毕竟不是那么难:

uint32 crc32(uint16* data, uint32 len, uint32 crc)
{
    uint32 i;
    while(len--)
    {
        for(i = 0; i < 16; i++)
        {
            // #define POLY 0x04C11DB7
            crc = (crc << 1) ^ (((crc ^ *data) & 0x80000000) ? POLY : 0);
        }
        crc ^= *data++;
    }

    return crc;
}

这是预期的结果 - 前 2 个 16 位字构成所需的未知 CRC，其余是已知数据本身(通过将这些示例提供给提供的算法，结果为 0)。

{0x3288, 0xD244, 0xCDEF, 0x89AB, 0x4567, 0x0123}
{0xC704, 0xDD7B, 0x0000} - append as many zeros as you like, the result is the same
{0xCEBD, 0x1ADD, 0xFFFF}
{0x81AB, 0xB932, 0xFFFF, 0xFFFF}
{0x0857, 0x0465, 0x0000, 0x0123}
{0x1583, 0xD959, 0x0123}
   ^        ^
   |        |
   unknown bytes that I need to calculate

我认为在 0xFFFF 或 0x0000 字上测试这个很方便，因为计算的方向和字节顺序并不重要(我希望 :D)。所以要小心使用其他测试字节，因为计算的方向很曲折:D。您还可以看到，通过仅向算法(向前和向后)提供零，结果是所谓的残差 (0xC704DD7B)，这可能会有所帮助。

所以...我写了至少 10 个不同的函数(逐位函数、表格、多项式组合等)试图解决这个问题，但没有成功。我在这里给你我寄予希望的功能。它是上面表驱动算法的“反向”算法，当然有不同的表。问题是我从中得到的唯一正确的 CRC 是全 0 消息，这并不意外。我还编写了按位算法的反向实现(反向移位等)，但该算法仅正确返回第一个字节。
这是表驱动的，指向 data 的指针应该指向消息的最后一个元素，crc 输入应该是请求的 crc(整个消息的 0s 或者你也许可以采取另一种方法 - 消息的最后 4 个字节是您正在寻找的 CRC:Calculating CRC initial value instead of appending the CRC to payload):

uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc)
{
    uint8 nibble;
    int i;
    while(len--)
    {
        for(i = 0; i < 4; i++)
        {
            nibble = (*data >> i*4) & 0x0F;
            crc = (crc >> 4) ^ revtab[((crc ^ nibble) & 0x0F)];
        }
        data--;
     }

     return reverse(crc); //reverse() flips all bits around center (MSB <-> LSB ...) 
}

这张 table ，我希望它是“被选中的那个”:

static const uint32 revtab[16]=
{
    0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
    0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
    0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
    0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
};

如您所见，此算法有一些好处，让我原地踏步，我想我可能走在正确的轨道上，但我遗漏了一些东西。我希望多一双眼睛能看到我看不到的东西。很抱歉发了这么长的帖子(没有土 bean :D)，但我认为所有这些解释都是必要的。提前感谢您的见解或建议。

Answer 1

我将回答您的 CRC 规范，即 CRC-32/MPEG-2 的规范。我将不得不忽略您计算该 CRC 的尝试，因为它们不正确。

无论如何，为了回答你的问题，我碰巧写了一个解决这个问题的程序。它被称为 spoof.c 。它可以非常快速地计算出要更改消息中的哪些位以获得所需的 CRC。它按照 log(n) 时间的顺序执行此操作，其中 n 是消息的长度。这是一个例子:

让我们以九字节消息 123456789(这些数字以 ASCII 表示)为例。我们将在它前面加上四个零字节，我们将对其进行更改以在最后获得所需的 CRC。十六进制的消息是:00 00 00 00 31 32 33 34 35 36 37 38 39。现在我们计算该消息的 CRC-32/MPEG-2。我们得到 373c5870。

现在我们用这个输入运行spoof，它是以位为单位的CRC长度，它没有反射(reflect)出来的事实，多项式，我们刚刚计算的CRC，以字节为单位的消息长度，以及前四个字节中的所有 32 位位置(这是我们允许 spoof 更改的内容):

32 0 04C11DB7
373c5870 13
0 0 1 2 3 4 5 6 7 
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7

它为这个输出提供了前四个字节中要设置的位:

invert these bits in the sequence:
offset bit
     0 1
     0 2
     0 4
     0 5
     0 6
     1 0
     1 2
     1 5
     1 7
     2 0
     2 2
     2 5
     2 6
     2 7
     3 0
     3 1
     3 2
     3 4
     3 5
     3 7

然后我们将前四个字节设置为:76 a5 e5 b7。然后，我们通过计算消息 76 a5 e5 b7 31 32 33 34 35 36 37 38 39 的 CRC-32/MPEG-2 进行测试，我们得到 00000000，即所需的结果。

您可以使 spoof.c 适应您的应用程序。

下面是一个使用按位算法正确计算字节流的 CRC-32/MPEG-2 的示例:

uint32_t crc32m(uint32_t crc, const unsigned char *buf, size_t len)
{
    int k;

    while (len--) {
        crc ^= (uint32_t)(*buf++) << 24;
        for (k = 0; k < 8; k++)
            crc = crc & 0x80000000 ? (crc << 1) ^ 0x04c11db7 : crc << 1;
    }
    return crc;
}

并使用问题中的表格进行 nybble-wise 算法(这是正确的):

uint32_t crc_table[] = {
    0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
    0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
    0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
    0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};

uint32_t crc32m_nyb(uint32_t crc, const unsigned char *buf, size_t len)
{
    while (len--) {
        crc ^= (uint32_t)(*buf++) << 24;
        crc = (crc << 4) ^ crc_table[crc >> 28];
        crc = (crc << 4) ^ crc_table[crc >> 28];
    }
    return crc;
}

在这两种情况下，初始 CRC 必须是 0xffffffff。