跳转到内容

std.compress.flate.token

标准库Zig 0.17.1官方原文
源码std/compress/flate/token.zig

第 1 行

std.compress.flate.token.builtin

常量

第 2 行

std.compress.flate.token.codegen_order

常量

第 10 行

[19]u8

std.compress.flate.token.DistCode

类型

第 62 行

std.compress.flate.token.fixed_dist

常量

第 49 行

std.compress.flate.token.fixed_dist_bits

常量

第 48 行

std.compress.flate.token.fixed_dist_codes

常量

第 47 行

std.compress.flate.token.fixed_lit

常量

第 24 行

std.compress.flate.token.fixed_lit_bits

常量

第 23 行

std.compress.flate.token.fixed_lit_codes

常量

第 22 行

std.compress.flate.token.LenCode

类型

第 61 行

std.compress.flate.token.LookupDistCode

容器

第 155 行

字段

std.compress.flate.token.LookupDistCode.base

函数

第 171 行

@ctz(return) >= extraBits()

pub fn base(c: LookupDistCode) u15

参数

std.compress.flate.token.LookupDistCode.base_table

常量

第 158 行

std.compress.flate.token.LookupDistCode.extraBits

函数

第 175 行

pub fn extraBits(c: LookupDistCode) u4

参数

std.compress.flate.token.LookupDistCode.fromInt

函数

第 183 行

pub fn fromInt(x: u5) LookupDistCode

参数

x: u5

std.compress.flate.token.LookupDistCode.fromVal

函数

第 166 行

pub fn fromVal(v: u15) LookupDistCode

参数

v: u15

std.compress.flate.token.LookupDistCode.toInt

函数

第 179 行

pub fn toInt(c: LookupDistCode) u5

参数

std.compress.flate.token.LookupLenCode

容器

第 114 行

字段

code: ShortLenCode

std.compress.flate.token.LookupLenCode.base

函数

第 138 行

@ctz(return) >= extraBits()

pub fn base(c: LookupLenCode) u8

参数

std.compress.flate.token.LookupLenCode.base_table

常量

第 125 行

std.compress.flate.token.LookupLenCode.code_table

常量

第 117 行

std.compress.flate.token.LookupLenCode.extraBits

函数

第 142 行

pub fn extraBits(c: LookupLenCode) u3

参数

std.compress.flate.token.LookupLenCode.fromInt

函数

第 150 行

pub fn fromInt(x: u5) LookupLenCode

参数

x: u5

std.compress.flate.token.LookupLenCode.fromVal

函数

第 133 行

pub fn fromVal(v: u8) LookupLenCode

参数

v: u8

std.compress.flate.token.LookupLenCode.toInt

函数

第 146 行

pub fn toInt(c: LookupLenCode) u5

参数

std.compress.flate.token.max_distance

别名

第 8 行

别名目标 std.compress.flate.history_len

std.compress.flate.token.max_length

常量

第 5 行

std.compress.flate.token.min_distance

常量

第 7 行

std.compress.flate.token.min_length

常量

第 4 行

std.compress.flate.token.ShortCode

类型函数

第 73 行

长度码和距离码具有如下格式。

例如,长度码 0b1101,即 13 或字面量 270,其 high_bits=0b01、high_log2=3, 形式为 1_01_xx,具有 2 个额外位。之后再加上最小长度 3。 ^ 第 4 位 = 2 + high_log2 - 1

长度码有一个例外:值 255 被分配给不含额外位的特殊码 28, 即字面量 285。

fn ShortCode(Value: type, HighBits: type, HighLog2: type, len_special: bool) type

参数

Value: type
HighBits: type
HighLog2: type
len_special: bool

字段

high_bits: HighBits

高位之前的各位;若无高位则从起始位置开始

high_log2: HighLog2

高位,0 表示没有,否则位于 x + high_log2 - 1 位

std.compress.flate.token.ShortCode.base

函数

第 90 行

@ctz(return) >= extraBits()

pub fn base(c: @This()) Value

参数

c: @This()

std.compress.flate.token.ShortCode.extraBits

函数

第 99 行

pub fn extraBits(c: @This()) std.math.IntFittingRange(0, max_extra)

参数

c: @This()

std.compress.flate.token.ShortCode.fromInt

函数

第 108 行

pub fn fromInt(x: u5) @This()

参数

x: u5

std.compress.flate.token.ShortCode.fromVal

函数

第 80 行

pub fn fromVal(v: Value) @This()

参数

v: Value

std.compress.flate.token.ShortCode.max_extra

常量

第 98 行

std.compress.flate.token.ShortCode.toInt

函数

第 104 行

pub fn toInt(c: @This()) u5

参数

c: @This()

std.compress.flate.token.ShortDistCode

类型

第 64 行

std.compress.flate.token.ShortLenCode

类型

第 63 行

std.compress.flate.token.std

别名

第 1 行

别名目标 std

源码

std/compress/flate/token.zig

const std = @import("std");
const builtin = @import("builtin");

pub const min_length = 3;
pub const max_length = 258;

pub const min_distance = 1;
pub const max_distance = std.compress.flate.history_len;

pub const codegen_order: [19]u8 = .{
    16, 17, 18,
    0, 8, //
    7, 9,
    6, 10,
    5, 11,
    4, 12,
    3, 13,
    2, 14,
    1, 15,
};

pub const fixed_lit_codes = fixed_lit[0];
pub const fixed_lit_bits = fixed_lit[1];
const fixed_lit = blk: {
    var codes: [286]u16 = undefined;
    var bits: [286]u4 = undefined;

    for (0..143 + 1, 0b00110000..0b10111111 + 1) |i, v| {
        codes[i] = @bitReverse(@as(u8, v));
        bits[i] = 8;
    }
    for (144..255 + 1, 0b110010000..0b111111111 + 1) |i, v| {
        codes[i] = @bitReverse(@as(u9, v));
        bits[i] = 9;
    }
    for (256..279 + 1, 0b0000000..0b0010111 + 1) |i, v| {
        codes[i] = @bitReverse(@as(u7, v));
        bits[i] = 7;
    }
    for (280..287 - 2 + 1, 0b11000000..0b11000111 - 2 + 1) |i, v| {
        codes[i] = @bitReverse(@as(u8, v));
        bits[i] = 8;
    }
    break :blk .{ codes, bits };
};

pub const fixed_dist_codes = fixed_dist[0];
pub const fixed_dist_bits = fixed_dist[1];
const fixed_dist = blk: {
    var codes: [30]u16 = undefined;
    const bits: [30]u4 = @splat(5);

    for (0..30) |i| {
        codes[i] = @bitReverse(@as(u5, i));
    }
    break :blk .{ codes, bits };
};

// 编码的所有参数均可通过数学方法推导,但某些参数查表更快。
// 使用 -Osmall 时,全部通过数学计算,以节省空间。
pub const LenCode = if (builtin.mode != .small) LookupLenCode else ShortLenCode;
pub const DistCode = if (builtin.mode != .small) LookupDistCode else ShortDistCode;
const ShortLenCode = ShortCode(u8, u2, u3, true);
const ShortDistCode = ShortCode(u15, u1, u4, false);
/// 长度码和距离码具有如下格式。
///
/// 例如,长度码 0b1101,即 13 或字面量 270,其 high_bits=0b01、high_log2=3,
/// 形式为 1_01_xx,具有 2 个额外位。之后再加上最小长度 3。
///        ^ 第 4 位 = 2 + high_log2 - 1
///
/// 长度码有一个例外:值 255 被分配给不含额外位的特殊码 28,
/// 即字面量 285。
fn ShortCode(Value: type, HighBits: type, HighLog2: type, len_special: bool) type {
    return packed struct(u5) {
        /// 高位之前的各位;若无高位则从起始位置开始
        high_bits: HighBits,
        /// 高位,0 表示没有,否则位于 `x + high_log2 - 1` 位
        high_log2: HighLog2,

        pub fn fromVal(v: Value) @This() {
            if (len_special and v == 255) return .fromInt(28);
            const high_bits = @bitSizeOf(HighBits) + 1;
            const bits = @bitSizeOf(Value) - @clz(v);
            if (bits <= high_bits) return @bitCast(@as(u5, @intCast(v)));
            const high = v >> @intCast(bits - high_bits);
            return .{ .high_bits = @truncate(high), .high_log2 = @intCast(bits - high_bits + 1) };
        }

        /// `@ctz(return) >= extraBits()`
        pub fn base(c: @This()) Value {
            if (len_special and c.toInt() == 28) return 255;
            if (c.high_log2 <= 1) return @as(u5, @bitCast(c));
            const high_value = (@as(Value, @intFromBool(c.high_log2 != 0)) << @bitSizeOf(HighBits)) | c.high_bits;
            const high_start = @as(std.math.Log2Int(Value), c.high_log2 - 1);
            return @shlExact(high_value, high_start);
        }

        const max_extra = @bitSizeOf(Value) - (1 + @bitSizeOf(HighLog2));
        pub fn extraBits(c: @This()) std.math.IntFittingRange(0, max_extra) {
            if (len_special and c.toInt() == 28) return 0;
            return @intCast(c.high_log2 -| 1);
        }

        pub fn toInt(c: @This()) u5 {
            return @bitCast(c);
        }

        pub fn fromInt(x: u5) @This() {
            return @bitCast(x);
        }
    };
}

const LookupLenCode = packed struct(u5) {
    code: ShortLenCode,

    const code_table = table: {
        var codes: [256]ShortLenCode = undefined;
        for (0.., &codes) |v, *c| {
            c.* = .fromVal(v);
        }
        break :table codes;
    };

    const base_table = table: {
        var bases: [29]u8 = undefined;
        for (0.., &bases) |c, *b| {
            b.* = ShortLenCode.fromInt(c).base();
        }
        break :table bases;
    };

    pub fn fromVal(v: u8) LookupLenCode {
        return .{ .code = code_table[v] };
    }

    /// `@ctz(return) >= extraBits()`
    pub fn base(c: LookupLenCode) u8 {
        return base_table[c.toInt()];
    }

    pub fn extraBits(c: LookupLenCode) u3 {
        return c.code.extraBits();
    }

    pub fn toInt(c: LookupLenCode) u5 {
        return @bitCast(c);
    }

    pub fn fromInt(x: u5) LookupLenCode {
        return @bitCast(x);
    }
};

const LookupDistCode = packed struct(u5) {
    code: ShortDistCode,

    const base_table = table: {
        var bases: [30]u15 = undefined;
        for (0.., &bases) |c, *b| {
            b.* = ShortDistCode.fromInt(c).base();
        }
        break :table bases;
    };

    pub fn fromVal(v: u15) LookupDistCode {
        return .{ .code = .fromVal(v) };
    }

    /// `@ctz(return) >= extraBits()`
    pub fn base(c: LookupDistCode) u15 {
        return base_table[c.toInt()];
    }

    pub fn extraBits(c: LookupDistCode) u4 {
        return c.code.extraBits();
    }

    pub fn toInt(c: LookupDistCode) u5 {
        return @bitCast(c);
    }

    pub fn fromInt(x: u5) LookupDistCode {
        return @bitCast(x);
    }
};

test LenCode {
    inline for ([_]type{ ShortLenCode, LookupLenCode }) |Code| {
        // 与 RFC 1951 表核对
        for (0.., [_]struct {
            base: u8,
            extra_bits: u4,
        }{
            // zig fmt: off
            .{ .base = 3   - min_length, .extra_bits = 0 },
            .{ .base = 4   - min_length, .extra_bits = 0 },
            .{ .base = 5   - min_length, .extra_bits = 0 },
            .{ .base = 6   - min_length, .extra_bits = 0 },
            .{ .base = 7   - min_length, .extra_bits = 0 },
            .{ .base = 8   - min_length, .extra_bits = 0 },
            .{ .base = 9   - min_length, .extra_bits = 0 },
            .{ .base = 10  - min_length, .extra_bits = 0 },
            .{ .base = 11  - min_length, .extra_bits = 1 },
            .{ .base = 13  - min_length, .extra_bits = 1 },
            .{ .base = 15  - min_length, .extra_bits = 1 },
            .{ .base = 17  - min_length, .extra_bits = 1 },
            .{ .base = 19  - min_length, .extra_bits = 2 },
            .{ .base = 23  - min_length, .extra_bits = 2 },
            .{ .base = 27  - min_length, .extra_bits = 2 },
            .{ .base = 31  - min_length, .extra_bits = 2 },
            .{ .base = 35  - min_length, .extra_bits = 3 },
            .{ .base = 43  - min_length, .extra_bits = 3 },
            .{ .base = 51  - min_length, .extra_bits = 3 },
            .{ .base = 59  - min_length, .extra_bits = 3 },
            .{ .base = 67  - min_length, .extra_bits = 4 },
            .{ .base = 83  - min_length, .extra_bits = 4 },
            .{ .base = 99  - min_length, .extra_bits = 4 },
            .{ .base = 115 - min_length, .extra_bits = 4 },
            .{ .base = 131 - min_length, .extra_bits = 5 },
            .{ .base = 163 - min_length, .extra_bits = 5 },
            .{ .base = 195 - min_length, .extra_bits = 5 },
            .{ .base = 227 - min_length, .extra_bits = 5 },
            .{ .base = 258 - min_length, .extra_bits = 0 },
        }) |code, params| {
            // zig fmt: on
            const c: u5 = @intCast(code);
            try std.testing.expectEqual(params.extra_bits, Code.extraBits(.fromInt(@intCast(c))));
            try std.testing.expectEqual(params.base, Code.base(.fromInt(@intCast(c))));
            for (params.base..params.base + @shlExact(@as(u16, 1), params.extra_bits) -
                @intFromBool(c == 27)) |v|
            {
                try std.testing.expectEqual(c, Code.fromVal(@intCast(v)).toInt());
            }
        }
    }
}

test DistCode {
    inline for ([_]type{ ShortDistCode, LookupDistCode }) |Code| {
        for (0.., [_]struct {
            base: u15,
            extra_bits: u4,
        }{
            // zig fmt: off
            .{ .base = 1     - min_distance, .extra_bits =  0 },
            .{ .base = 2     - min_distance, .extra_bits =  0 },
            .{ .base = 3     - min_distance, .extra_bits =  0 },
            .{ .base = 4     - min_distance, .extra_bits =  0 },
            .{ .base = 5     - min_distance, .extra_bits =  1 },
            .{ .base = 7     - min_distance, .extra_bits =  1 },
            .{ .base = 9     - min_distance, .extra_bits =  2 },
            .{ .base = 13    - min_distance, .extra_bits =  2 },
            .{ .base = 17    - min_distance, .extra_bits =  3 },
            .{ .base = 25    - min_distance, .extra_bits =  3 },
            .{ .base = 33    - min_distance, .extra_bits =  4 },
            .{ .base = 49    - min_distance, .extra_bits =  4 },
            .{ .base = 65    - min_distance, .extra_bits =  5 },
            .{ .base = 97    - min_distance, .extra_bits =  5 },
            .{ .base = 129   - min_distance, .extra_bits =  6 },
            .{ .base = 193   - min_distance, .extra_bits =  6 },
            .{ .base = 257   - min_distance, .extra_bits =  7 },
            .{ .base = 385   - min_distance, .extra_bits =  7 },
            .{ .base = 513   - min_distance, .extra_bits =  8 },
            .{ .base = 769   - min_distance, .extra_bits =  8 },
            .{ .base = 1025  - min_distance, .extra_bits =  9 },
            .{ .base = 1537  - min_distance, .extra_bits =  9 },
            .{ .base = 2049  - min_distance, .extra_bits = 10 },
            .{ .base = 3073  - min_distance, .extra_bits = 10 },
            .{ .base = 4097  - min_distance, .extra_bits = 11 },
            .{ .base = 6145  - min_distance, .extra_bits = 11 },
            .{ .base = 8193  - min_distance, .extra_bits = 12 },
            .{ .base = 12289 - min_distance, .extra_bits = 12 },
            .{ .base = 16385 - min_distance, .extra_bits = 13 },
            .{ .base = 24577 - min_distance, .extra_bits = 13 },
        }) |code, params| {
            // zig fmt: on
            const c: u5 = @intCast(code);
            try std.testing.expectEqual(params.extra_bits, Code.extraBits(.fromInt(@intCast(c))));
            try std.testing.expectEqual(params.base, Code.base(.fromInt(@intCast(c))));
            for (params.base..params.base + @shlExact(@as(u16, 1), params.extra_bits)) |v| {
                try std.testing.expectEqual(c, Code.fromVal(@intCast(v)).toInt());
            }
        }
    }
}