logo标签列表

初学者理解循环冗余校验码算法

javascriptpngcrccrc32
5
在PNG规范的第5.5节中，讨论了一种名为"CRC"或"Cyclic Redundancy Code"的PNG文件格式概念。我以前从未听说过它，所以我正在尝试理解它。
CRC多项式采用的是 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1。在PNG中，32位CRC初始化为全1，然后从最低有效位（1）到最高有效位（128）处理每个字节的数据。处理完所有数据字节后，对CRC进行反转（取其一补数）。该值被传输（存储在数据流中），先传输最高有效位。为了分离成字节并排序，32位CRC的最低有效位被定义为x31项的系数。关于这个问题，我理解的和不理解的内容如下。

我听说过多项式，但在这个上下文中，我有点困惑它们在这里是如何实现的。

在这种情况下，"x"代表什么？32位循环中的当前位？这就带我们来到下一个部分：

所以它说要制作一个空的32位数字（或者说全部设为1，因此是32个1），然后它说它是“从最不重要的位（1）到最重要的位（128）”进行处理的，但问题是，“最不重要的...最重要的...重要的位”是指什么 ？

其他块中的数据？

如果块设置为字节，并且这只有32位，那该怎么办？如果块数据中有超过32位的数据（肯定有）呢？

它是指“多项式”的“最不重要的...最重要的...重要的位”吗？

但是多项式究竟代表什么？x^32代表什么？

x由什么表示？

对于上述问题的任何帮助，以及使用示例IDATA块（即用基本解释计算其CRC块）的简单示例将是很好的：

0 0 2 3 IDAT 0 1 0 1 0 1 0 1 0 1 0 C

最后一个字节“C”应该被替换为它所说的32位CRC值。

有人能给我提供一个实际的例子吗？

1
我不知道他们在for循环中获取了那个大的位数，也不知道在哪里插入字节数组。这是32位CRC的标准数字之一。请前往维基文章，并向下滚动到32位CRC，您会在那里看到它。如何选择CRC是复杂的，我不知道为什么要从具有相同错误检测能力的CRC组中选择特定的CRC。 - rcgldr
@rcgldr，问题是我对多种格式和压缩不感兴趣，我只对非常简单的PNG生成器感兴趣（主要是为了在Google应用脚本中运行），而且几乎没有非常轻量级的JavaScript PNG库（pngJS太过于复杂）可以实现我想要的功能。 - B''H Bi'ezras -- Boruch Hashem
@YetAnotherUser 好的，在我解释之前，我需要一个适用于JavaScript的工作函数/公式来输入任何字节数组，然后我可以进行解释。 - B''H Bi'ezras -- Boruch Hashem
@greg-tumolo 哇，太棒了，这正是我在寻找的！我只是想稍微理解一下，数字“0xedb88320”与那个多项式x^32等有什么关系吗？ - B''H Bi'ezras -- Boruch Hashem
是的，只返回已翻译的文本。请查看我在答案中的最终评论。 - greg-tumolo
显示剩余6条评论
3个回答
3
我建议阅读Ross Williams经典著作《"CRC错误检测算法简明指南"》。您将在其中找到深入的解释和示例。
多项式是解释一串比特位的另一种方式。当你有一个包含n个比特位的寄存器时，它们通常被解释为独立的n个比特位列表，或者被解释为一个整数，其中你将每个比特位乘以2的0到n-1次幂并相加。多项式表示法则是将每个比特位解释为多项式的系数。由于一个比特位只能是0或1，所以结果的多项式实际上从不显示0或1。而是x^n项存在或不存在。因此，四个比特位1011可以被解释为1 x^3 + 0 x^2 + 1 x^1 + 1 x^0 = x^3 + x + 1。请注意，我选择最高有效位作为x^3项的系数是任意的，我也可以选择另一个方向。
关于x是什么，它只是一个占位符，用于系数和x的幂。你从不将x设置为某个值，也不确定x的任何信息。它的作用是允许你将这些位串作为多项式进行操作。在对这些多项式进行操作时，你像代数课上一样处理它们，只不过系数受到GF(2)域的限制，其中系数只能是0或1。乘法变成了与操作，加法变成了异或操作。因此，1加1等于0。你得到了一种新的、不同的方法来添加、乘以和除以位串。这种不同的方式对许多错误检测和纠正方案至关重要。

有趣的是，但最终不相关的是，在字符串的多项式表示中，如果你将x设置为2（按照正确的顺序选择），你会得到该字符串的整数解释。

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Samuel Liew
2
该规范包括一个指向示例代码的链接：

https://www.w3.org/TR/2003/REC-PNG-20031110/#D-CRCAppendix

规范存在错误或不清晰。
应该是“每个字节的数据从最低有效位（0）到最高有效位（7）进行处理。”
CRC 是一个 33 项多项式，其中每一项都有一个一位系数，0 或 1，在描述多项式时忽略 0 系数。
将 CRC 视为保存在一个 32 位寄存器中。序列是将数据字节异或到 CRC 寄存器的最右字节中，位 7 到 0（技术上对应于 x^24 到 x^31 的多项式系数）。然后通过表查找将 CRC 向右循环移动 8 位。一旦所有数据字节都经过了这个循环，根据 Mark Adler 的评论，CRC 就被附加到数据中，以最高有效字节优先的方式，(CRC>>24)&0xff, (CRC>>16)&0xff, (CRC>>8)&0xff, (CRC)&0xff。
这篇维基百科的文章可能会有所帮助。在计算部分的例子中，被除数将是一个数据字节数组，其中每个字节的位都被反转了，而33位多项式的位将不被反转（0x104C11DB7）。计算完成后，余数的位将被反转并附加到数据字节中。

https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Mark Adler的回答包含了一个好的CRC教程链接。他的回答还解释了多项式中使用的x。它就像代数中的多项式一样，只是系数只能是0或1，并且使用异或进行加法（或减法）。
"X是什么？" 来自维基百科的例子：
data     = 11010011101100 = x^13 + x^12 + x^10 + x^7 + x^6 + x^5 + x^3 + x^2
divisor  =           1011 = x^3 + x + 1

数据末尾添加三个0比特，相当于将其乘以x^3：
dividend = 11010011101100000 = x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5

然后，CRC = 被除数 % 除数，其中系数限制为0或1。
(x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5) % (x^3 + x + 1) = x^2
11010011101100000 % 1011 = 100
不，CRC并不总是附加到数据的顺序，以产生固定的残留。事实上，在这种特殊情况下，PNG会以相反的字节顺序附加CRC。类型和数据字段上的CRC被计算，然后与在重新组装为大端序列的数据中的块中的CRC简单比较。 - Mark Adler
@MarkAdler - 谢谢 - 我更新了我的答案。该链接指出 MSB 优先，并且不清楚 MSB 是指反转多项式的最高有效字节，还是指保存 CRC 的寄存器的 MSB。 - rcgldr
是的，这个循环冗余校验已经在硬件中实现了。PNG没有。 - Mark Adler
@MarkAdler - 这个CRC需要比通常实现为LFSR的典型CRC更多的硬件，用于计算和输出（其中数据位设置为0）。对于这个CRC，在计算CRC之后，LFSR必须映射到另一个寄存器以移出CRC位。 CRC检查需要映射比较。我只是想知道选择非典型CRC实现（反转CRC字节）背后的原因是什么。 - rcgldr
@bluejayke - 在这种情况下，除数是0x04C11DB7（而不是0xB），但由于它是一个右移位CRC，整个操作的位是反转的（左/右），因此除数被反转为0xedb88320。 - rcgldr
显示剩余9条评论
1
注意：如果您使用(00000000)_2和(00000001)_2作为示例IDAT块中0和1的二进制表示，则会计算出错误的CRC。'0'和'1'的ASCII值分别为48 = (00110000)_2和49 = (00110001)_2；同样，'I'、'D'、'A'和'T'的ASCII值分别为73 = (01001001)_2、68 = (01000100)_2、65 = (01000001)_2和84 = (01010100)_2。因此，假设您想要计算的是值0和1而不是字符'0'和'1'，则必须计算的CRC是(01001001 01000100 01000001 01010100 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000)_2。

与CRC不相关，但对块的有效性有影响的是长度字段（即前4个字节），它应该仅包含数据的字节数，其值为11，这是垂直制表符（VT）的ASCII值，垂直制表符是一个非打印字符，但可以用十六进制转义序列\x0B表示为字符串。同样，前3个字节必须包含ASCII值为0（而不是48）的字符，即null（NUL），可以用十六进制转义序列\x00在字符串中表示。因此，长度字段必须包含类似于“\x00\x00\x00\x0B”的内容。

嘿，现在回头看看，那么它总是设置为0xedb88320吗？还是有时候不同？如果有时候不同，那么怎么找出它是什么呢？ - B''H Bi'ezras -- Boruch Hashem
这总是那个实现的数字。 - greg-tumolo
但是，究竟如何找出一个数字是为了什么，比如说这个实现呢？ - B''H Bi'ezras -- Boruch Hashem
通过阅读实现：https://www.w3.org/TR/2003/REC-PNG-20031110/#D-CRCAppendix - greg-tumolo
谢谢，但那对于我这个小脑袋来说太复杂了，有没有任何教程？ - B''H Bi'ezras -- Boruch Hashem
显示剩余10条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接