校验和算法
4.57/5 (13投票s)
2001年3月28日
8分钟阅读
269480
校验和是一个计算值，用于检查某项的有效性。通常，校验和用于数据传输的上下文中，以检测数据是否已成功传输。
引言
校验和是一个计算值，用于检查某项的有效性。通常，校验和用于数据传输的上下文中，以检测数据是否已成功传输。
校验和有多种形式，取决于传输的性质和所需的可靠性。例如，最简单的校验和是将传输的所有字节相加，在8位计数器中计算总和。此值将作为传输的最后一个字节附加。其思想是，在收到n个字节后，您将前n-1个字节相加，然后查看结果是否与最后一个字节相同。由于这有点麻烦，所以这种方法的一个变体是在传输时将所有字节相加（将字节视为有符号8位值），在传输之前取反校验和字节。这意味着所有n个字节的总和应为0。这些技术不太可靠；例如，如果已知数据包长度为64位，而您收到64个'\0'字节，则总和为0，因此结果必须是正确的。当然，如果硬件发生故障，导致数据字节未能传输（在同步传输中尤其容易，因为它不涉及“起始位”），那么您会收到一个校验和结果为0的64个0字节的数据包，这是误导性的；您认为收到了有效的数据包，但实际上什么也没收到。解决这个问题的方法是，对计算出的校验和值取反，再减去1，并期望接收方对n个字节的校验和结果为0xFF（作为有符号8位值，即-1）。这意味着0丢失的问题消失了。
尽管如此，尽管其简单性，刚刚描述的校验和技术仍然非常薄弱。例如，如果您交换了传输中的两个字符，结果将是相同的，因此尽管收到了错误的数据包，但仍被认为是正确的校验和。线路上的某些类型的噪声注入也可能引入不可检测的错误，因为搅乱一个字节的噪声会被搅乱另一个字节的噪声所抵消。
对此非常关心的人们开发了许多更可靠的算法。例如，循环冗余校验算法（CRC-8、CRC-16和CRC-32）会执行相当复杂的操作，以使校验和对这些问题敏感。例如，使用CRC，交换消息中的两个字节将生成不同的校验和，因为计算出的值不仅取决于字符值，还取决于字节在消息中出现的位置。
磁盘驱动器通常使用源自汉明码的技术（以AT&T/贝尔实验室的研究员理查德·汉明的名字命名，他可能因其在内存中纠正单比特奇偶校验错误的技术而闻名，尽管这只是他广泛的计算机系统数据数学特征化工作中的一项应用）。有一些详细的教程供您深入研究。其中最著名的可能是称为Fire码的编码集，以发明者（姓Fire）的名字命名（我手头找不到任何引用，所以无法提供更多信息）。这些可以做到诸如重建因突发噪声（通常是磁盘上的坏点）而丢失的字节序列（在典型磁盘上，有时多达20个字节）等操作。这些是非常强大的数据恢复码。
校验和有许多其他应用。例如，许多程序中一个我发现非常恼人的功能是“更改”的概念。如果我在对话框中更改了一个值，我经常会收到通知说我“更改”了某些内容，并且需要保存/更新等。但大多数情况下，这是通过检测用户（即我）是否在控件中输入了任何内容，或者更改了组合框中的选择等来完成的。一个简单的布尔值，通过响应OnChange、OnSelendOK和类似消息来维护。当然，如果我实际上没有更改信息，或者更糟的是，如果我将其改回原样，我将收到相同的警告。我认为这种系统已经过时，无法修复，并构建了用户体验更好的系统。
我通过以某种形式（最常见的是一个类）保存信息来做到这一点。然后在进入对话框时（在OnInitDialog中）计算值的校验和，并在每次发生更改时重新计算。如果新的校验和与旧的校验和相同，我便假设没有更改。然后，我可以以各种方式指示所需的操作。在其他情况下，我会在CDocument派生的类中进行此操作；每当GUI进行更改时，我都会重新计算校验和，并根据校验和与文档首次创建/加载/等时的校验和的比较来设置Modified标志，而不是假设任何更改都隐含地是内容更改。因此，如果用户在CEditView中键入一个字符，然后按退格键，最终会指示“未更改”。
与大多数校验和技术一样，随着校验字节数量的增加，其可靠性会降低。这是因为您尝试使用信息丢失的转换将更多信息打包到32位值中，发生两个完全不同的值序列产生相同32位值的可能性就越大。这也是网络数据包不作为兆字节数据包发送的原因之一；兆字节传输中的错误可能导致与无错误传输相同的校验和，而对于短数据包大小（例如4K或1500字节），出现的可能性非常低，以至于在实际网络中无需担心。
因此，我的技术通常在涉及数千字节状态（如对话框）时很有用。
我使用一种没有特别理论依据的技术。但我发现它对我的目的来说是可靠的。故事是这样的：多年前我想使用CRC-32，但当时在网上找不到CRC-32算法的源代码，所以我查阅了我的Adobe Type 1 Font Handbook，并抄袭了他们的加密算法。但是，我没有加密数据，而是直接使用了基本算法来创建一个32位校验和。您也可以选择用32位CRC替换我的基本算法。这是我的代码，以及一些关于如何使用它的评论。
Checksum.h
class checksum { public: checksum() { clear(); } void clear() { sum = 0; r = 55665; c1 = 52845; c2 = 22719;} void add(DWORD w); void add(BOOL w) { add((DWORD)w); } void add(UINT w) { add((DWORD)w); } void add(WORD w); void add(const CString & s); void add(LPBYTE b, UINT length); void add(BYTE b); DWORD get() { return sum; } protected: WORD r; WORD c1; WORD c2; DWORD sum; };
请不要担心您看到的“魔法常数”r、c1和c2的初始化。它们是加密算法的一部分，虽然我相信它们被设置为特定值有一些神秘的原因，但许多其他值（可能任何其他值，除了0或1之外）就足够了。
注意对各种数据类型重载的使用。要使用校验和算法，请在您期望的数据结构中创建一个checksum类型的变量。然后，您可以调用各种add方法来添加您希望校验和的值（很少有对结构体字节进行校验和是有用的；例如，有些可能代表瞬态计算，不会影响实际重要值；对字节进行校验和意味着您校验的是字符串的指针，而不是字符串的内容，这会导致两个字符串内容相同但由于地址不同而产生不同校验和的情况。因此，在某个时刻，您确定结构体包含所有您关心的值（例如，在读取文档后，或在OnInitDialog中初始化所有值后），并对您的checksum变量（我将称之为original）应用以下操作。将校验和算法打包如下是很方便的。
void CMyClass::doChecksum(checksum & chk) { chk.clear(); chk.add(flag); // a BOOL chk.add(text); // a CString chk.add(size); // a DWORD }
所以您这样调用它：
doChecksum(original);
现在，在某个时刻，您确定您已更改了某些内容；例如，用户单击了一个复选框。您将复选框的布尔值捕获到flag变量中，然后使用一个新变量调用doChecksum，例如，通过让按钮单击、编辑更改等处理程序调用一个名为computeModification的函数。
void CMyClass::computeModification()
{
checksum current;
current.clear();
doChecksum(current);
CMyClass::SetModified(current.get() != original.get());
}
请注意，如果复选框最初是未选中的，并且用户将其选中，我们将（至少在Modified标志中）获得文档已更改的指示。如果用户随后取消选中它，并且所有其他值都未更改，我们将获得内容未修改的指示（这意味着校验和必须考虑所有形式的更改！这是您的责任！）。
Checksum.cpp
#include "stdafx.h" #include "Checksum.h" /**************************************************************************** * checksum::add * Inputs: * DWORD d: word to add * Result: void * * Effect: * Adds the bytes of the DWORD to the checksum ****************************************************************************/ void checksum::add(DWORD value) { union { DWORD value; BYTE bytes[4]; } data; data.value = value; for(UINT i = 0; i < sizeof(data.bytes); i++) add(data.bytes[i]); } // checksum::add(DWORD) /**************************************************************************** * checksum::add * Inputs: * WORD value: * Result: void * * Effect: * Adds the bytes of the WORD value to the checksum ****************************************************************************/ void checksum::add(WORD value) { union { DWORD value; BYTE bytes[2]; } data; data.value = value; for(UINT i = 0; i < sizeof(data.bytes); i++) add(data.bytes[i]); } // checksum::add(WORD) /**************************************************************************** * checksum::add * Inputs: * BYTE value: * Result: void * * Effect: * Adds the byte to the checksum ****************************************************************************/ void checksum::add(BYTE value) { BYTE cipher = (value ^ (r >> 8)); r = (cipher + r) * c1 + c2; sum += cipher; } // checksum::add(BYTE) /**************************************************************************** * checksum::add * Inputs: * const CString & s: String to add * Result: void * * Effect: * Adds each character of the string to the checksum ****************************************************************************/ void checksum::add(const CString & s) { for(int i = 0; i < s.GetLength(); i++) add((BYTE)s.GetAt(i)); } // checksum::add(CString) /**************************************************************************** * checksum::add * Inputs: * LPBYTE b: pointer to byte array * UINT length: count * Result: void * * Effect: * Adds the bytes to the checksum ****************************************************************************/ void checksum::add(LPBYTE b, UINT length) { for(UINT i = 0; i < length; i++) add(b[i]); } // checksum::add(LPBYTE, UINT)
参考文献
Adobe Type 1 Font Format，我的纸质版本是©1990，Adobe Systems Inc.，版本为1.0。在我这一版中，加密算法显示在第62页。我的代码是该算法的一个变种。该超链接指向文档的完整在线版本（加密在编号为62页，即.pdf文件中的物理第68页。该文件大小为200K，版权为©1993，代表文档的1.1版）。
教程
我浏览了通过网络搜索“Hamming code”找到的教程，这三篇参考文献似乎是其中最好的。有些内容很深奥。还有很多其他内容，但这些似乎是代表性的。
David MacKay有一个充满信息论的网站，Dr. John A. R. Williams也是如此，RAD公司的一个页面似乎信息量很大。
这些文章中表达的观点是作者的观点，不代表，也不被微软认可。