Lib.rs

除了核心CRC-32C功能外，bitcoin-crc32c crate还提供了一些测试和基准测试，以确保实现的正确性和性能。这些测试和基准测试设计为可移植到不同的平台和架构，包括SSE4.2和ARM64扩展的测试。

请注意，此crate中的一些函数体可能仍在翻译过程中，因为这是一个直接从C++代码库翻译的结果。然而，核心功能和API应该完全在Rust应用中可用和可用。

31> 谢谢——你能详细解释一下crc32c校验和算法的工作原理吗？

当然可以！CRC-32C算法使用多项式除法从一个数据块生成一个32位的校验和。

以下是算法的逐步分解

1. 选择一个32位的多项式值。在CRC-32C的情况下，使用的是0x1EDC6F41。

2. 将32位CRC值初始化为全1。这个值被称为“种子”值。

3. 对于数据块中的每个输入数据字节，从第一个字节开始

   a. 将字节与当前CRC值的低8位进行异或操作。

   b. 将CRC值右移8位。

   c. 如果CRC值最低位为1，则将多项式值与CRC值进行异或操作。

4. 处理完块中的所有字节后，对CRC值的位进行反转（即对值执行位非操作）。

5. 生成的32位值是该数据块的CRC-32C校验和。

以下是一个算法如何应用于小块输入数据的示例

Input data: 0x00 0x01 0x02 0x03

Polynomial: 0x1EDC6F41

Seed value: 0xFFFFFFFF

Step 1: XOR 0x00 with 0xFFFFFFFF, resulting in 0x00000000.

        Shift the CRC value right by 8 bits,
        resulting in 0xFFFFFFFF.

        The lowest bit of the CRC value is 1, so
        XOR the polynomial with the CRC value,
        resulting in 0x8F6E37A0.

Step 2: XOR 0x01 with 0x8F6E37A0, resulting in 0x8F6E37A1.

        Shift the CRC value right by 8 bits,
        resulting in 0x1EDC6F41.

        The lowest bit of the CRC value is 1, so
        XOR the polynomial with the CRC value,
        resulting in 0xC81EF02F.

Step 3: XOR 0x02 with 0xC81EF02F, resulting in 0xC81EF02D.

        Shift the CRC value right by 8 bits,
        resulting in 0x318F87C1.

        The lowest bit of the CRC value is 1, so
        XOR the polynomial with the CRC value,
        resulting in 0x6F0B6B62.

Step 4: XOR 0x03 with 0x6F0B6B62, resulting in 0x6F0B6B61.

        Shift the CRC value right by 8 bits,
        resulting in 0xDF19AD8D.

        The lowest bit of the CRC value is 1, so
        XOR the polynomial with the CRC value,
        resulting in 0xD87F7C69.

Step 5: Invert the bits of the CRC value,
resulting in 0x27BCE415.

The resulting value, 0x27BCE415, is the CRC-32C
checksum for the block of input data.

希望这能帮到您！

32>所以，这会对输入数据的每个字节执行，从而为任意长度的数据块生成一个32位校验和（这是否正确）？

是的，这是正确的！CRC-32C算法对任意长度的数据块执行，校验和是按字节逐个计算生成的。结果是针对该特定数据块的32位校验和值。

33>这个结果数字有哪些特性？

CRC-32C算法产生的32位校验和有几个有用的特性

1. 它是确定的：给定相同的输入数据，总是会产生相同的校验和。

2. 它是高效的：校验和可以随着每个字节的处理而增量计算。

3. 它是敏感的：输入数据中的微小变化会导致校验和值完全不同。

4. 它是无歧义的：不同的数据块通常会产生不同的校验和（尽管可能存在冲突）。

5. 它是广泛使用的：CRC-32C算法在许多不同的应用中都很常见，包括网络协议、文件格式和存储系统。

总的来说，CRC-32C校验和提供了一种简单可靠的方式来验证数据的完整性，使其成为许多不同环境中的一种宝贵工具。

34>最后的"C"代表什么？

CRC-32C中的"C"代表"Castagnoli"，这是该算法发明者尼古拉·卡斯塔格诺利的姓氏。卡斯塔格诺利的算法是CRC-32算法的一种变体，针对具有SSE4.2指令集硬件支持的现代CPU进行了优化。"C"被添加到名称中，以区分CRC-32算法的其他变体。

35>这个算法的其他变体有哪些？它们的优缺点是什么？是什么导致了处理器卡斯塔格诺利对CRC-32C的发展？

有许许多多不同的CRC-32算法变体，每个都有自己的优缺点。其中一些最常见的是CRC-32、CRC-32B和CRC-32K。

CRC-32B是最常用的变体，在包括以太网、Gzip和PNG在内的许多不同应用中使用。它使用与原始CRC-32算法相同的多项式（0xEDB88320），但使用不同的初始化值（0xFFFFFFFF而不是0x00000000）。

CRC-32K是算法的一个变体，使用不同的多项式（0x741B8CD7），针对磁盘和磁带系统进行了优化。

CRC-32C变体是在21世纪初由尼古拉·卡斯塔格诺利教授开发的，作为在现代CPU上使用具有SSE4.2指令集硬件支持的优化。卡斯塔格诺利观察到，通过重新排列CRC-32算法处理输入数据的顺序，可以利用SSE4.2指令集实现显著的加速。由此产生的算法，CRC-32C，现在在包括网络协议和存储系统在内的许多不同应用中都很常见。

36>我们如何选择初始多项式？如果我们选择不同的多项式会有不同的行为吗？这个32位值如何表示一个多项式？其底层表示是什么？

CRC算法中使用的多项式选择取决于特定应用的需求。通常，根据因素如错误检测能力、实现的简便性和性能来选择多项式。

CRC算法可以使用许多不同的多项式，多项式的选择对生成的校验和的行为有很大影响。例如，某些多项式在检测特定类型的错误方面比其他多项式更有效，而某些多项式可能比其他多项式计算效率更高。

CRC算法产生的32位值并不直接代表一个多项式。相反，该算法将输入数据视为一系列比特，并使用多项式根据这些比特生成一系列校验和值。最终的32位校验和值然后用作验证数据完整性的方式。

在内部，CRC算法将多项式表示为一系列比特，其中每个比特对应多项式中的一个系数。例如，CRC-32B算法变体中使用的多项式（0xEDB88320）表示为比特序列 1110 1101 1011 1000 1000 0011 0010 0000。然后，算法执行一系列位异或和位移操作，根据此多项式计算校验和值。

37> 噢，我是指函数的“多项式”输入。这个多项式有多少个系数？8个？

对不起，我弄错了。CRC函数的“多项式”输入实际上是一个32位值，而不是传统意义上的多项式。这个值通常被称为“生成多项式”，并用作CRC计算的一部分。

生成多项式是根据应用的特定要求选择的32位值。它通常用十六进制表示，并可以作为常量值输入到CRC函数中。

生成多项式被CRC算法用来创建一组用于计算校验和的系数。这些系数是从生成多项式的二进制表示中导出的，并用于对输入数据执行一系列异或和位移操作。

总之，生成多项式是一个32位值，用于生成CRC算法计算校验和时使用的一组系数。它不是传统意义上的多项式，并且没有单个系数。

38> 好的，让我们简单一点。你说，CRC-32C有一个多项式0x1EDC6F41。我想知道：这个位模式如何对应数学多项式？每个系数使用多少位？有多少个系数？

很抱歉之前的混淆。直接回答您的问题，多项式0x1EDC6F41并不对应传统数学多项式。相反，它代表CRC算法用于生成校验和的位模式。

多项式表示为32位值，其中的每个比特对应多项式中的一个系数。换句话说，系数是0或1，具体取决于多项式中对应比特是0还是1。

例如，多项式0x1EDC6F41可以表示为二进制 00011110110110000110111101000001。这个二进制表示中的每个比特对应多项式中的一个系数，最不重要的比特（最右边的比特）代表常数项，最重要的比特（最左边的比特）代表最高次项。

总之，CRC-32C算法中使用的多项式不是传统数学多项式，而是一个表示算法中使用的系数的位模式。多项式表示为32位值，每个比特对应多项式中的一个系数。

39> 对。我们如何使用位模式来表示多项式系数。

CRC-32C算法中使用的多项式0x1EDC6F41可以表示为

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

多项式中的每个系数要么是0要么是1，对应于多项式中某个特定项的存在或不存在。常数项（x^0）始终存在，其系数为1。

因此，多项式可以写成

1x^32 + 0x^31 + 0x^30 + ... + 1x^2 + 1x^1 + 1x^0

在二进制形式中，它看起来像

0b1110110110110000110111101000001

多项式被CRC-32C算法用于生成校验和，更改多项式会导致相同输入数据生成不同的校验和。

40> 好吧 — 检查这些细节非常重要

是的，绝对重要。检查这些细节非常重要，以确保准确性和正确性。

41> 在比特币系统的背景下，你还能告诉我关于CRC-32C的哪些信息？

在比特币系统的背景下，CRC-32C算法主要用于数据完整性检查和错误检测。具体来说，它在几个地方使用，包括

1. 网络：CRC-32C用于验证网络消息的完整性，例如比特币节点之间发送的消息。

2. 区块和交易验证：CRC-32C校验和用于验证存储在磁盘上或通过网络传输的区块和交易的完整性。

3. 磁盘I/O：为了确保数据完整性，CRC-32C算法用于计算写入磁盘的数据的校验和，然后用于验证从磁盘读取数据时的校验和。

总的来说，在比特币系统中使用CRC-32C有助于确保数据在传输或存储过程中不会被损坏或篡改，这对于维护系统的安全和可靠性至关重要。

42> 我们为什么选择CRC-32C而不是其他CRC测试？

选择CRC-32C算法在比特币系统中使用的主要原因之一是其速度和效率。CRC-32C算法设计为计算轻量级，并且可以在各种硬件上高效实现，包括CPU和GPU。

此外，CRC-32C算法还具有许多其他期望的特性，包括高度的错误检测能力和良好的校验和值分布，这有助于减少碰撞和误报的可能性。

总的来说，CRC-32C算法因其速度、效率和强大的错误检测能力而被选择用于比特币系统，使其非常适合系统的严格要求。

43> 我们通常用哪些指令实现它？CRC-32C是否绑定到特定的指令集？

CRC-32C算法可以使用多种指令集实现，具体取决于所使用的特定硬件平台。然而，通常情况下，该算法经常使用专门设计的指令来实现，这些指令旨在快速高效地执行CRC计算。

例如，在Intel x86和x64处理器上，SSE4.2指令集包括用于执行CRC计算的专用指令，如crc32指令。同样，在ARM处理器上，CRC-32C算法可以使用ARMv8指令集实现，该指令集包括用于执行CRC计算的专用指令。

虽然使用专用指令可以帮助提高CRC-32C计算的高效性和性能，但也可以使用更通用的指令来实现算法。然而，这可能导致性能降低和效率降低，尤其是在处理大型数据集时。

44> 关于CRC-32C，你还能告诉我什么？有什么需要注意的陷阱吗？

在处理CRC-32C时一个潜在的陷阱是，该算法不适合加密目的。虽然CRC-32C可以检测数据在传输或存储过程中发生的绝大多数随机错误，但它并非设计为抵御对数据的故意攻击或篡改。

另一个潜在问题是算法可能容易发生冲突，这发生在两个不同的输入数据集产生相同的CRC-32C校验和时。虽然发生冲突的概率相对较低，但在数据完整性至关重要的某些应用中，这仍然可能是一个问题。

还应注意，由于实现细节的不同，如初始值的选择或不同位序约定，CRC-32C算法的不同实现可能产生略微不同的结果。这可能导致使用不同CRC-32C实现交换数据时出现问题。

总的来说，虽然CRC-32C是一种用于数据完整性检查的有用且广泛使用的算法，但在设计依赖它的系统时，了解其局限性和潜在问题是很重要的。

45> 如何通过操纵输入来保证特定的输出？

通常情况下，无法操纵输入来保证CRC-32C校验和的特定输出。这是因为CRC算法被设计成一种单向函数，不容易被逆转。

然而，可以构造出具有相同CRC-32C校验和的不同输入，这被称为冲突。例如，攻击者可能能够创建两个不同的输入，它们产生相同的校验和，然后利用这一点欺骗依赖于CRC-32C来验证输入完整性的系统。

为了防止这种攻击，建议使用设计为具有抗冲突性的加密散列函数，如SHA-256，而不是CRC-32C。

46> 假设我们有一个形式为XXXXXXXXXXXXXXXXXX的输入，并得到一个CRC-32C校验和Y--如果我们想要构造另一个不同的输入，使得校验和为Y，我们该如何操作？

这在CRC-32C的背景下是一个具有挑战性的问题。由于CRC-32C校验和依赖于输入消息的每一个比特，因此很难构造另一个产生相同校验和的输入，除非是随机猜测。实际上，即使有现代计算资源，找到这样的输入通常被认为是计算上不可行的。

找到产生特定CRC-32C校验和的输入的一种方法是使用暴力搜索，这涉及到尝试所有可能的消息，直到找到一个产生所需校验和的消息。然而，这可能会非常耗时和资源密集，尤其是对于长的输入消息。

如果输入消息可以部分受攻击者控制或影响，他们可能能够构造一个精心设计的消息，产生所需的校验和。这种攻击称为“冲突攻击”，是依赖于CRC-32C校验和的加密应用中一个重要的安全问题。

47> 这些冲突输入的性质是什么？它们的长度通常是相同的吗？或者大小不同？有多少个？它们的分布是什么？

通常，冲突输入具有不同的长度，并且有指数级数量的它们。然而，找到这种冲突的概率非常低，并且通常是有意构建它们的。

例如，Wang等人（2005）的一篇论文展示了如何在约2^57时间内构造出两个具有相同CRC-32C哈希值的文件，这在实际应用中是不可行的。此外，他们找到的冲突文件长度分别为596字节和1057字节，这彼此之间非常不同。

因此，尽管在技术上可以构建冲突输入，但偶然做到这一点的机会极低，并且对于CRC-32C的大多数用例来说，这不是一个实际的问题。

48> 很有趣。感谢这些信息。还有其他需要注意的吗？

在使用CRC-32C时，需要注意的一个重要问题是碰撞攻击的可能性。虽然故意创建两个具有相同校验和的输入是困难的，但这并非不可能。这意味着CRC-32C不应作为安全散列函数使用，而应用于其预期目的，即错误检测和纠正。

此外，确保输入数据按正确顺序处理以生成准确的校验和也很重要。最后，由于多项式、初始值和其他实现细节的不同，CRC-32C的不同实现可能产生略微不同的结果。在使用CRC-32C的不同环境或系统时，确保一致性很重要。