Zig 0.17.0-dev (Split by item)

This is an example of documentation generated by ZigDoc, an alternative to Zig's built-in Auto Doc feature. See also examples in other modes/formats. The project being documented here (as the example) is the Zig library itself.

genTable

Generates the lookup table for efficiently combining CRCs over a block of a given length length. This works by building an operator that advances the CRC state as if length zero-bytes were appended. We pre-compute 4 tables of 256 entries each (one per byte offset).

The idea behind this table is quite interesting. The CRC state is equivalent to the remainder of dividing the message polynomial (over GF(2)) by the CRC polynomial.

Advancing the CRC register by k zero bits is equivalent to multiplying the current CRC state by x^k modulo the CRC polynomial. This operation can be represented as a linear transformation in GF(2), i.e, a matrix.

We build up this matrix via repeated squaring:

By squaring the shifting len, we build the operator for x^l mod POLY.

Crc32c.genTable
fn genTable(length: usize) [4][256]u32

File

lib/std/hash/crc/Crc32c.zig:56

Code

fn genTable(length: usize) [4][256]u32 {
    @setEvalBranchQuota(250000);

    var even: [32]u32 = undefined;
    zeroes: {
        var odd: [32]u32 = undefined;

        // Initialize our `odd` array with the operator for a single zero bit:
        // - odd[0] is the polynomial itself (acts on the MSB).
        // - odd[1..32] represent shifting a single bit through 31 positions.
        odd[0] = POLY;
        var row: u32 = 1;
        for (1..32) |n| {
            odd[n] = row;
            row <<= 1;
        }

        // even = odd squared: even represents `x^2 mod POLY`.
        square(&even, &odd);
        // odd = even squared: odd now represents `x^4 mod POLY`.
        square(&odd, &even);

        // Continue squaring to double the number of zeroes encoded each time:
        //
        // At each point in the process:
        // - square(even, odd): even gets the operator for twice the current length.
        // - square(odd, even): odd gets the operator for 4 times the original length.
        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;
}