使用 SSE4.2 Intel CRC32 指令实现 CRC-32C(Castagnoli)。
以下链接有助于理解此处采用的方法:
字段
crc: u32
std.hash.crc.Crc32c.crc32
函数
fn crc32(crc: u32, input: []const u8) u32
参数
crc: u32
input: []const u8
std.hash.crc.Crc32c.final
函数
pub fn final(w: Wrapper) u32
参数
w: Wrapper
std.hash.crc.Crc32c.genTable
函数
为高效合并长度为 length 的数据块上的 CRC,生成查找表。
其做法是构造一个运算符,使 CRC 状态前进到仿佛已追加 length 个零字节后的状态。
我们预先计算 4 张表,每张包含 256 个条目,分别对应一个字节偏移。
这张表背后的思路相当有趣。CRC 状态等价于消息多项式(定义在 GF(2) 上)除以 CRC 多项式所得的余数。
将 CRC 寄存器前进 k 个零位,等价于将当前 CRC 状态乘以 x^k,再对 CRC 多项式取模。此运算可表示为 GF(2) 上的线性变换,也就是矩阵。
我们通过重复平方构造该矩阵:
- odd 表示前进 1 个零位的运算符(即乘以
x^1 mod POLY) - even 表示前进 2 个零位的运算符(
x^2 mod POLY) - 再平方得到
x^4 mod POLY,依此类推,直到达到所需大小。
通过对移位后的 len 逐次平方,构造 x^l mod POLY 对应的运算符。
fn genTable(length: usize) [4][256]u32
参数
length: usize
std.hash.crc.Crc32c.hash
函数
pub fn hash(bytes: []const u8) u32
参数
bytes: []const u8
std.hash.crc.Crc32c.init
函数
pub fn init() Wrapper
std.hash.crc.Crc32c.LONG
常量
std.hash.crc.Crc32c.long_lookup_table
常量
std.hash.crc.Crc32c.POLY
常量
std.hash.crc.Crc32c.shift
函数
fn shift(table: *const [4][256]u32, crc: u32) u32
参数
table: *const [4][256]u32
crc: u32
std.hash.crc.Crc32c.SHORT
常量
std.hash.crc.Crc32c.short_lookup_table
常量
std.hash.crc.Crc32c.square
函数
计算 GF(2) 上矩阵的平方,即 dst = dst x src。
这会生成将零的数量加倍的算子:若 src 表示将 CRC 向前推进 k 个零,则 dest 表示向前推进 2k 个零。
由于模 POLY 的多项式乘法是线性的,mat(mat(x)) = mat^2(x) 具有连续应用两次算子的效果。
fn square(dst: *[32]u32, src: *const [32]u32) void
参数
dst: *[32]u32
src: *const [32]u32
std.hash.crc.Crc32c.times
函数
计算 mat * vec,运算位于 GF(2),其中 mat 为 32×32 二进制矩阵,vec
为 32 位向量。这在某种程度上“模拟”了移位时
各位在 CRC 寄存器中的传播。
- 在 GF(2),即只含 0 和 1 的二元域中,乘法
对应
AND,加法对应XOR。 - 此点积对
vec中值为 1 的位所对应的矩阵行进行异或,即相加, 从而确定输入向量各位对最终 CRC 状态的“贡献”。
fn times(mat: *const [32]u32, vec: u32) u32
参数
mat: *const [32]u32
vec: u32
std.hash.crc.Crc32c.update
函数
pub fn update(w: *Wrapper, bytes: []const u8) void
参数
w: *Wrapper
bytes: []const u8
std.hash.crc.Crc32c.Wrapper
别名
别名目标 std.hash.crc.Crc32c
源码
std/hash/crc/Crc32c.zig
//! 使用 SSE4.2 Intel CRC32 指令实现 CRC-32C(Castagnoli)。
//!
//! 以下链接有助于理解此处采用的方法:
//! - https://github.com/madler/brotli/blob/1d428d3a9baade233ebc3ac108293256bcb813d1/crc32c.c
//! - https://github.com/madler/zlib/blob/5a82f71ed1dfc0bec044d9702463dbdf84ea3b71/crc32.c
//! - http://www.ross.net/crc/download/crc_v3.txt
// 以二进制形式表示的反射 CRC-32C 多项式。
const POLY = 0x82f63b78;
const LONG = 8192;
const SHORT = 256;
const long_lookup_table = genTable(LONG);
const short_lookup_table = genTable(SHORT);
const Wrapper = @This();
crc: u32,
pub fn init() Wrapper {
return .{ .crc = 0 };
}
pub fn update(w: *Wrapper, bytes: []const u8) void {
w.crc = crc32(w.crc, bytes);
}
pub fn final(w: Wrapper) u32 {
return w.crc;
}
pub fn hash(bytes: []const u8) u32 {
var c = init();
c.update(bytes);
return c.final();
}
/// 为高效合并长度为 `length` 的数据块上的 CRC,生成查找表。
/// 其做法是构造一个运算符,使 CRC 状态前进到仿佛已追加 `length` 个零字节后的状态。
/// 我们预先计算 4 张表,每张包含 256 个条目,分别对应一个字节偏移。
///
///
/// 这张表背后的思路相当有趣。CRC 状态等价于消息多项式(定义在 GF(2) 上)除以 CRC 多项式所得的余数。
///
/// 将 CRC 寄存器前进 `k` 个零位,等价于将当前 CRC 状态乘以 `x^k`,再对 CRC 多项式取模。此运算可表示为 GF(2) 上的线性变换,也就是矩阵。
///
/// 我们通过重复平方构造该矩阵:
/// - odd 表示前进 1 个零位的运算符(即乘以 `x^1 mod POLY`)
/// - even 表示前进 2 个零位的运算符(`x^2 mod POLY`)
/// - 再平方得到 `x^4 mod POLY`,依此类推,直到达到所需大小。
///
/// 通过对移位后的 `len` 逐次平方,构造 `x^l mod POLY` 对应的运算符。
///
///
///
fn genTable(length: usize) [4][256]u32 {
@setEvalBranchQuota(250000);
var even: [32]u32 = undefined;
zeroes: {
var odd: [32]u32 = undefined;
// 使用单个零位的运算符初始化 `odd` 数组:
// - odd[0] 是多项式本身(作用于最高有效位)。
// - odd[1..32] 表示将单个位移过 31 个位置。
odd[0] = POLY;
var row: u32 = 1;
for (1..32) |n| {
odd[n] = row;
row <<= 1;
}
// even = odd 的平方:even 表示 `x^2 mod POLY`。
square(&even, &odd);
// odd = even 的平方:此时 odd 表示 `x^4 mod POLY`。
square(&odd, &even);
// 继续平方,使每次编码的零的数量翻倍:
//
// 在过程的每一步:
// - square(even, odd):even 获得对应当前长度两倍的算子。
// - square(odd, even):odd 获得对应原始长度四倍的算子。
var len = length;
while (true) {
square(&even, &odd);
len >>= 1;
if (len == 0) break :zeroes;
square(&odd, &even);
len >>= 1;
if (len == 0) break;
}
@memcpy(&even, &odd);
}
var zeroes: [4][256]u32 = undefined;
for (0..256) |n| {
zeroes[0][n] = times(&even, n);
zeroes[1][n] = times(&even, n << 8);
zeroes[2][n] = times(&even, n << 16);
zeroes[3][n] = times(&even, n << 24);
}
return zeroes;
}
/// 计算 `mat * vec`,运算位于 `GF(2)`,其中 `mat` 为 32×32 二进制矩阵,`vec`
/// 为 32 位向量。这在某种程度上“模拟”了移位时
/// 各位在 CRC 寄存器中的传播。
///
/// - 在 GF(2),即只含 0 和 1 的二元域中,乘法
/// 对应 `AND`,加法对应 `XOR`。
/// - 此点积对 `vec` 中值为 1 的位所对应的矩阵行进行异或,即相加,
/// 从而确定输入向量各位对最终 CRC 状态的“贡献”。
fn times(mat: *const [32]u32, vec: u32) u32 {
var sum: u32 = 0;
var v = vec;
var i: u32 = 0;
while (v != 0) {
if (v & 1 != 0) sum ^= mat[i];
v >>= 1;
i += 1;
}
return sum;
}
/// 计算 GF(2) 上矩阵的平方,即 `dst = dst x src`。
///
/// 这会生成将零的数量加倍的算子:若 `src` 表示将 CRC 向前推进 `k` 个零,则 `dest` 表示向前推进 2k 个零。
///
/// 由于模 POLY 的多项式乘法是线性的,`mat(mat(x)) = mat^2(x)` 具有连续应用两次算子的效果。
///
///
///
fn square(dst: *[32]u32, src: *const [32]u32) void {
for (dst, src) |*d, s| {
d.* = times(src, s);
}
}
fn shift(table: *const [4][256]u32, crc: u32) u32 {
return table[0][crc & 0xFF] ^ table[1][(crc >> 8) & 0xFF] ^ table[2][(crc >> 16) & 0xFF] ^ table[3][crc >> 24];
}
fn crc32(crc: u32, input: []const u8) u32 {
var crc0: u64 = ~crc;
// 计算最多七个前导字节的 CRC,
// 使 `next` 指针对齐到八字节边界。
var next = input;
while (next.len > 0 and @intFromPtr(next.ptr) & 7 != 0) {
asm volatile ("crc32b %[out], %[in]"
: [in] "+r" (crc0),
: [out] "rm" (next[0]),
);
next = next[1..];
}
// 针对每组 LONG * 3 字节计算 CRC,执行三条彼此独立的
// CRC 指令,每条处理 LONG 字节。当目标上的 CRC 指令吞吐率为每
// 周期一条、延迟为三个周期时,此操作可提高性能。
//
while (next.len >= LONG * 3) {
var crc1: u64 = 0;
var crc2: u64 = 0;
const start = next.len;
while (true) {
// @alignCast() 是安全的,因为在此循环之前已将指针对齐到 8 字节。
const long: [*]const u64 = @ptrCast(@alignCast(next));
asm volatile (
\\crc32q %[out0], %[in0]
\\crc32q %[out1], %[in1]
\\crc32q %[out2], %[in2]
: [in0] "+r" (crc0),
[in1] "+r" (crc1),
[in2] "+r" (crc2),
: [out0] "rm" (long[0 * LONG / 8]),
[out1] "rm" (long[1 * LONG / 8]),
[out2] "rm" (long[2 * LONG / 8]),
);
next = next[8..];
if (next.len <= start - LONG) break;
}
crc0 = shift(&long_lookup_table, @truncate(crc0)) ^ crc1;
crc0 = shift(&long_lookup_table, @truncate(crc0)) ^ crc2;
next = next[LONG * 2 ..];
}
// 与上面相同,但处理较小的 SHORT 字节块。
while (next.len >= SHORT * 3) {
var crc1: u64 = 0;
var crc2: u64 = 0;
const start = next.len;
while (true) {
const long: [*]const u64 = @ptrCast(@alignCast(next));
asm volatile (
\\crc32q %[out0], %[in0]
\\crc32q %[out1], %[in1]
\\crc32q %[out2], %[in2]
: [in0] "+r" (crc0),
[in1] "+r" (crc1),
[in2] "+r" (crc2),
: [out0] "rm" (long[0 * SHORT / 8]),
[out1] "rm" (long[1 * SHORT / 8]),
[out2] "rm" (long[2 * SHORT / 8]),
);
next = next[8..];
if (next.len <= start - SHORT) break;
}
crc0 = shift(&short_lookup_table, @truncate(crc0)) ^ crc1;
crc0 = shift(&short_lookup_table, @truncate(crc0)) ^ crc2;
next = next[SHORT * 2 ..];
}
// 按 8 字节数据块计算,直到剩余数据不足 8 字节。
while (next.len >= 8) {
const long: [*]const u64 = @ptrCast(@alignCast(next));
asm volatile ("crc32q %[out], %[in]"
: [in] "+r" (crc0),
: [out] "rm" (long[0]),
);
next = next[8..];
}
// 仅使用单条指令处理最后几个字节。
while (next.len > 0) {
asm volatile ("crc32b %[out], %[in]"
: [in] "+r" (crc0),
: [out] "rm" (next[0]),
);
next = next[1..];
}
return @truncate(~crc0);
}