跳转到内容

std.hash.crc.Crc32c

标准库Zig 0.17.1官方原文
源码std/hash/crc/Crc32c.zig

第 1 行

字段

crc: u32

std.hash.crc.Crc32c.crc32

函数

第 144 行

fn crc32(crc: u32, input: []const u8) u32

参数

crc: u32
input: []const u8

std.hash.crc.Crc32c.final

函数

第 28 行

pub fn final(w: Wrapper) u32

参数

w: Wrapper

std.hash.crc.Crc32c.genTable

函数

第 56 行

为高效合并长度为 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

函数

第 32 行

pub fn hash(bytes: []const u8) u32

参数

bytes: []const u8

std.hash.crc.Crc32c.init

函数

第 20 行

pub fn init() Wrapper

std.hash.crc.Crc32c.LONG

常量

第 11 行

std.hash.crc.Crc32c.long_lookup_table

常量

第 13 行

std.hash.crc.Crc32c.POLY

常量

第 9 行

std.hash.crc.Crc32c.shift

函数

第 140 行

fn shift(table: *const [4][256]u32, crc: u32) u32

参数

table: *const [4][256]u32
crc: u32

std.hash.crc.Crc32c.SHORT

常量

第 12 行

std.hash.crc.Crc32c.short_lookup_table

常量

第 14 行

std.hash.crc.Crc32c.square

函数

第 134 行

计算 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

函数

第 114 行

计算 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

函数

第 24 行

pub fn update(w: *Wrapper, bytes: []const u8) void

参数

w: *Wrapper
bytes: []const u8

std.hash.crc.Crc32c.Wrapper

别名

第 16 行

别名目标 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);
}