CRC32：为文件生成校验和

• 下载源代码文件 - 17 Kb
• 下载演示项目 - 8 Kb

引言

最近我写了一个程序，我想为给定文件生成一个CRC。我在网上查找了一些CRC示例代码，但发现很少有算法能帮助我。所以我决定学习更多关于CRC的知识并编写自己的代码。本文介绍了CRC是什么，如何生成它们，它们的用途，最后是展示如何实现的源代码。

什么是CRC

CRC是循环冗余校验和或循环冗余校验的缩写（取决于你问谁）。CRC是代表数据的“数字签名”。最常见的CRC是CRC32，其中“数字签名”是一个32位数字。被CRC的“数据”可以是任何长度的任何数据；从文件到字符串，甚至是内存块。只要数据可以表示为一系列字节，就可以进行CRC。没有单一的CRC算法，算法可以像程序员一样多。理想的CRC算法具有几个特点。首先，如果你对相同的数据进行多次CRC，每次都必须得到相同的CRC。其次，如果你对两个不同的数据进行CRC，你应该得到两个非常不同的CRC值。如果你对相同的数据进行两次CRC，你会得到相同的数字签名。但如果你对不同的数据（即使只有一个字节不同）进行CRC，那么你应该得到两个非常不同的数字签名。使用32位CRC，有超过40亿个可能的CRC值。准确地说是2³²或4,294,967,296。有这么多CRC值，被CRC的每份数据都获得唯一的CRC值并不困难。然而，可能会发生虚假命中。换句话说，两份完全不同的数据可能具有相同的CRC。这种情况很少见，但并非不会发生。

为什么使用CRC

大多数情况下，CRC用于比较数据作为完整性检查。假设有两个文件需要比较以确定它们是否相同。第一个文件在 机器 A 上，另一个文件在 机器 B 上。每个文件都相当大（比如500 MB），并且两台机器之间没有网络连接。你如何比较这两个文件？答案是CRC。你对这两个文件进行CRC，这会给你两个32位数字。然后你比较这些32位数字，看看它们是否相同。如果CRC值不同，那么你可以100%保证文件不相同。如果CRC值相同，那么你可以99%确定文件相同。请记住，由于可能发生虚假命中，你无法确定两个文件完全相同。唯一能确定它们相同的方法是逐字节进行比较。但CRC提供了一种快速方法，可以合理确定两个文件是否相同。

如何生成CRC

生成CRC很像密码学，因为它涉及大量的数学理论。由于我自己没有完全理解，我不会在这里深入探讨这些细节。相反，我将重点介绍如何编写CRC算法。一旦你知道算法的工作原理，你就应该能够用任何语言在任何平台上编写CRC算法。生成CRC的第一部分是CRC查找表。在CRC32中，这是一个包含256个特定CRC数字的表。这些数字由多项式生成（这些数字的计算和使用哪个多项式是我正在回避的数学部分）。下一部分是CRC查找函数。这个函数接受两件事，一个要进行CRC的单字节数据和当前的CRC值。它根据提供的字节在CRC表中进行查找，然后进行一些数学运算，将该查找值应用于给定的CRC值，从而得到一个新的CRC值。所需的最后一部分是实际要进行CRC的数据。CRC算法读取数据的第一个字节并调用CRC查找函数，该函数返回该单字节的CRC值。然后它用数据的下一个字节调用CRC查找函数并传递上一个CRC值。第二次调用后，CRC值表示前两个字节的CRC。你不断调用CRC查找函数，直到处理完所有数据字节。结果值就是整个数据的CRC。

代码详情

在这个示例程序中，我想展示生成CRC有许多不同的方法。有超过8种不同的CRC函数，都基于上述生成CRC的步骤。每个函数在其预期用途或优化方面略有不同。有四个主要的CRC函数，每个函数都在下面描述。还有两个独立的CRC类，但稍后会详细介绍。最后还有一些用于CRC字符串的辅助函数。

C++ 流：第一个函数代表最简单的CRC函数。文件使用C++流类（ifstream）打开。此函数只使用标准C++调用，因此此函数应该可以在任何操作系统上使用任何C++编译器编译和运行。

Win32 I/O：此函数经过优化，因为它使用Win32 API进行文件I/O；CreateFile和ReadFile。这将加快处理速度，但由于使用了Win32 API，代码不再独立于平台。

文件映射：此函数使用内存映射文件来处理文件。文件映射可以极大地提高文件访问速度。它们允许像访问内存一样访问文件内容。程序员不再需要调用ReadFile和WriteFile。

汇编：最终的CRC函数是使用Intel汇编优化的函数。通过手工编写汇编代码，可以优化算法以提高速度，尽管牺牲了易读性和理解性。

以上是四个主要的CRC函数。但实际上每个函数都有两个版本。有两个类，CCrc32Dynamic和CCrc32Static，每个类都有上述四个函数，总共有八个。静态类和动态类之间唯一的区别是CRC表。在静态类中，CRC表和类中的所有函数都是静态的。权衡很简单。静态类使用起来更简单，但动态类更有效地使用内存，因为CRC表（1K大小）只在需要时才分配。

// Using the static class is as easy as one line of code
dwErrorCode = CCrc32Static::FileCrc32Assembly(m_strFilename, dwCrc32);

// Whereas there is more involved when using the dynamic class
CCrc32Dynamic *pobCrc32Dynamic = new CCrc32Dynamic;
pobCrc32Dynamic->Init();
dwErrorCode = pobCrc32Dynamic->FileCrc32Assembly(m_strFilename, dwCrc32);
pobCrc32Dynamic->Free();
delete pobCrc32Dynamic;

每当你计算CRC时，你需要考虑算法的速度。为文件生成CRC既是CPU密集型任务，也是磁盘密集型任务。下表显示了对三个不同文件进行CRC所需的时间。列是不同的文件大小，行是不同的CRC函数，表条目以秒为单位。捕获这些数字的系统是双Pentium III，1 GHz，带10,000 RPM SCSI Ultra160硬盘驱动器。

	44 Kb	34 Mb	5 Gb
C++ 流	0.0013	0.80	125
Win32 I/O	0.0009	0.60	85
文件映射	0.0010	0.60	87
程序集	0.0006	0.35	49

正如预期的那样，C++流是最慢的函数，其次是Win32 I/O。然而，我非常惊讶地发现文件映射并不比Win32 I/O快，实际上它们更慢。我仔细思考后意识到，内存映射文件旨在提供对文件的快速随机访问。但是当你进行CRC时，你顺序访问文件。因此，文件映射并不快，创建文件“视图”的额外开销是它变慢的原因。文件映射确实有一个其他函数没有的优势。内存映射文件保证能够访问NT中最大文件大小的文件，即2⁶⁴或18艾字节。尽管Win32 I/O可能处理这种大小的文件，但没有任何文档证实这一点。[注意：我进行CRC的最大文件是40 GB，所有八个函数都成功进行了CRC，但每个都花费了10多分钟。]

如果阅读本文的任何人知道进一步提高速度的方法，请发布代码或给我发送电子邮件。特别是如果你知道汇编代码的速度改进方法。我敢打赌汇编代码还可以进行进一步优化。毕竟我对Intel汇编不是很了解，因此我确信存在我不知道的优化。