Artifact 53788e02f497c1ed6889306615e49ca6f88e226d247c2349df645809b7bbb199:
- File
src/flate/token.zig
— part of check-in
[46fcd75fc3]
at
2026-09-19 14:40:06
on branch trunk
— container: a damaged container is an error, never a crash or wrong bytes
The first nightly soak flipped one bit in a valid container and brought the process down inside the standard inflate: an integer underflow in its end-of-input bit peek that a truncated stream can arrange, reachable from any peer through every sync body. The decoder is now the tree's own copy of the standard one (Zig 0.16.0, MIT) with the comparison reordered so the stream ends, and its origin noted. With the crash gone the same bytes decoded to 58 bytes reported as good: the flip made a block final, and the zlib footer's Adler-32 was read but never checked, by the decoder or by us. The codec now requires a finished stream and verifies the footer against the output. The exact bytes are a fixed test. (user: dmestas, size: 10730) [annotate] [blame] [check-ins using]
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 }; }; // All paramters of codes can be derived matchematically, however some are faster to // do via lookup table. For ReleaseSmall, we do all mathematically to save space. pub const LenCode = if (builtin.mode != .ReleaseSmall) LookupLenCode else ShortLenCode; pub const DistCode = if (builtin.mode != .ReleaseSmall) LookupDistCode else ShortDistCode; const ShortLenCode = ShortCode(u8, u2, u3, true); const ShortDistCode = ShortCode(u15, u1, u4, false); /// For length and distance codes, they having this format. /// /// For example, length code 0b1101 (13 or literal 270) has high_bits=0b01 and high_log2=3 /// and is 1_01_xx (2 extra bits). It is then offsetted by the min length of 3. /// ^ bit 4 = 2 + high_log2 - 1 /// /// An exception is Length codes, where value 255 is assigned the special zero-bit code 28 or /// literal 285. fn ShortCode(Value: type, HighBits: type, HighLog2: type, len_special: bool) type { return packed struct(u5) { /// Bits preceding high bit or start if none high_bits: HighBits, /// High bit, 0 means none, otherwise it is at bit `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| { // Check against the RFC 1951 table 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()); } } } }