type
status
slug
summary
tags
category
icon
password
new update day
Property
Oct 22, 2023 01:31 PM
created days
Last edited time
Oct 22, 2023 01:31 PM
CRC32 是一种校验和/散列算法,在内核和 Internet 校验和中非常常用。它与 MD5 校验和算法非常相似。

1 基本算法

从 32 位校验和开始,所有位都被置为1 (0xffffffff)。这有助于为 “0” 字节的输入字符串提供 0 以外的输出值。
在一个循环中:
  • 根据下一条输入数据(通常是一个字节)和前一个CRC值的低 N 位(其中N是您正在操作的数据的大小——通常是 8 位字节)异或的结果,在表中查找“多项式”(实际上只是一个 32 位值)。
  • 将先前的 32 位 CRC 值向下移动 N 位。
  • 将“多项式”与移位后的 CRC 值进行异或运算以产生新值。
循环结束后,将计算出的 CRC 值与 0xffffffff 进行异或运算(这等同于对 CRC 值执行二进制非运算)。最终得到 CRC32 计算结果。

2 构建查找表

这是一个比实际计算校验和本身更复杂的过程。
要构建一个具有 256 条目(字节)的查找表,应采用 8 位索引并位反射该字节中的所有位。将其移至 32 位变量的高 8 位。遍历这 8 位。如果设置了最高(符号)位,则将 uint32_t 向上移动一位并将其与魔法值 0x04C11DB7 进行异或运算。否则只需将 uint32_t 向上移动一位。然后重复。当循环完成时,整个 uint32_t 的位反射已经完成。这是表中的值。
或者,您可以通过这种方式简单地避免位反射:获取 8 位索引并将其转换为 32 位变量。循环低位字节。如果最低有效位 (0x00000001) 已设置,则将 uint32_t 向下移动一位并将其与值 0xEDB88320(即 0x04C11DB7 位反射)进行异或运算。否则只需将其向下移动一位。然后重复。当循环完成时,最终的uint32_t 就是表中的值。

3 Example Code

此处是对构建查找表的第一种方法的汇编代码实现(我还没看懂😂)

4 See Also

4.1 External Links

wiki.osdev.org 系列之 - Category:Common Algorithmswiki.osdev.org 系列之 - Dithering