CRC32(C)能否返回0？

Question

我想知道CRC32校验和，特别是CRC32C是否会返回0？简单的答案是，如果数据集足够大，那么会返回0。然而，我想知道是否有任何在CRC32C标准中的规定可以明确防止这种情况发生。

这个用例是，我需要检查远程文件是否为空，我只有它的CRC32C校验和。换句话说，如果CRC32C为0，那么文件是否保证为空。

如果可能的话，请提供定义此内容的标准参考。

- dtoux

---

你能使用自己的校验和吗？在这种情况下，定义零仅用于空文件。如果哈希函数产生了零，只需将其设置为1即可。 - usr

你知道CRC32值，但不知道文件长度？嗯？ - Kijewski

@usr CRC32C算法在速度方面进行了高度优化，并且在英特尔CPU上已经实现了硬件化。我需要它来进行线速计算，因此自定义实现不是一个选项。 - dtoux

@Kay 这只是一个例子。实际使用情况比这更加复杂。 - dtoux

你只需要添加这样一行代码：if (crcValue == 0) crcValue = 1;，就可以了。这就是全部内容。 - usr

@usr，这是个不错的想法，谢谢。 - dtoux

Answer 1

@Yanek的说法几乎完全正确。

只是为了好玩，这里有一个五个字符的序列 DYB|O，它的CRC-32C值为零。这里还有一个以十六进制表示的四字节序列，其值也为零: ab 9b e0 9b。 实际上，这是唯一能够产生零的四字节序列。对于一个、两个或三个字节序列，没有任何能够产生零的序列。这就是@Yanek不完全正确的地方，在这些情况下，获得零的概率为零。

- Mark Adler

---

对于3字节的输入，大约有256个输出的概率为零。据我所知，零输出并没有什么特别之处。 - usr

必须有比那更多的东西。只有2^24个可能的3字节输入，因此必须有2^32-2^24 == 4,278,190,080个概率为零的输出。其余的概率为2^-24。 - Mark Adler

对，我错误地除以了数字而不是减去。 - usr

@MarkAdler 谢谢Mark，非常有用。 - dtoux

Answer 2

在CRC32校验和中，0的概率与任何其他值相等。CRC本质上是将整个输入（作为一个大二进制数）除以预选值的余数。如果输入恰好可被该值整除，则余数和因此CRC为零。

- Yanek Martinson

---

这是我目前的理解，但我仍然希望有人能证明我错了 :-) - dtoux

Answer 3

这个怎么样，虽然不是32位的CRC：

1011 | 110011001010.000
       1011
       ----
        1111
        1011
        ----
         1001
         1011
         ----
           1000
           1011
           ----
             1110
             1011
             ----
              1011
              1011
              ----
                  0000 (...)
                  1011
                  ----
                  1011
                  1011
                  ----
                  0000

或者：

1100 | 11001010.000
       1100
       ----
           1010
           1100
           ----
            1100
            1100
            ----
            (...) 0

- Sparky