diff options
| author | Ogulcan Celik <ogulcancelik@gmail.com> | 2026-07-16 23:28:05 +0300 |
|---|---|---|
| committer | Ogulcan Celik <ogulcancelik@gmail.com> | 2026-07-16 23:29:28 +0300 |
| commit | 4a3302d19a2baa3a33e910e0088c24e780905b90 (patch) | |
| tree | dcaf76fae1c82102d933c9225b17ca7ac5d3a847 /vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig | |
| parent | 550e9f8cc085f428429f5cf2da0bb2dba897e8b8 (diff) | |
chore: update vendored libghostty-vt
refs #276
Diffstat (limited to 'vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig')
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig | 493 |
1 files changed, 493 insertions, 0 deletions
diff --git a/vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig b/vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig new file mode 100644 index 00000000..bbf3b276 --- /dev/null +++ b/vendor/libghostty-vt/src/terminal/compress/lz4_differential.zig @@ -0,0 +1,493 @@ +//! Differential and property tests for the LZ4 block codec. +//! +//! Every generated input must compress into a block which: +//! +//! 1. fits within `compressBound`, +//! 2. is structurally valid LZ4 with the stricter guarantees our +//! compressor documents (final five bytes are literals, matches start +//! at least twelve bytes before the end), verified by an independent +//! walker which shares no code with the codec, +//! 3. decompresses to exactly the original bytes, and +//! 4. is rejected when decompressed into a buffer of the wrong size. +//! +//! Valid blocks are additionally mutated (bit flips, splices, truncations) +//! and fed to the decompressor, which must fail cleanly or succeed, but +//! never read or write out of bounds. The unit-test build enables runtime +//! safety, so any out-of-bounds slice access fails the test. +//! +//! The light suite below runs as a normal unit test and finishes quickly. +//! The exhaustive suite multiplies the same properties across far more +//! sizes, periods, seeds, and mutations; it is slow and therefore skipped +//! unless the environment variable `GHOSTTY_LZ4_SLOW` is set: +//! +//! GHOSTTY_LZ4_SLOW=1 zig build test -Dtest-filter="lz4 differential" +const std = @import("std"); +const testing = std.testing; +const Allocator = std.mem.Allocator; +const lz4 = @import("lz4.zig"); + +/// Number of trailing block bytes which must be literals, mirroring the +/// documented guarantee of the compressor. Kept as an independent constant +/// so a codec regression cannot silently weaken the check. +const last_literals = 5; + +/// A match may not begin in the final twelve bytes. See `last_literals`. +const match_find_limit = 12; + +/// Sizes around every encoding boundary: token nibble limits (14/15), +/// minimum match and find limits (4/12), length-extension steps (15 + 255k), +/// and power-of-two neighborhoods. +const boundary_sizes = [_]usize{ + 0, 1, 2, 3, 4, 5, 6, 7, + 8, 9, 11, 12, 13, 14, 15, 16, + 17, 18, 19, 20, 31, 32, 33, 63, + 64, 65, 254, 255, 256, 269, 270, 271, + 272, 1023, 1024, 4095, 4096, 4097, +}; + +/// Input generators exercising distinct codec behaviors. Every generator is +/// deterministic for a given random state. +const Generator = enum { + /// Uniform random bytes; largely incompressible. + random_bytes, + + /// Runs of one repeated byte with random lengths; period-one matches. + runs, + + /// One repeating pattern; exercises a fixed match period end to end. + periodic, + + /// Eight-byte records with random small payloads and zero padding, with + /// some records repeated; resembles terminal cell memory. + cells, + + /// Dictionary words with separators; text-like literal/match mix. + words, + + /// Mostly zeros with scattered random bytes; long matches with isolated + /// literals. + sparse, + + /// Random segments of all other generators; exercises transitions. + mixed, + + fn fill(gen: Generator, random: std.Random, buf: []u8) void { + switch (gen) { + .random_bytes => random.bytes(buf), + + .runs => { + var i: usize = 0; + while (i < buf.len) { + const run = @min( + random.intRangeAtMost(usize, 1, 300), + buf.len - i, + ); + @memset(buf[i..][0..run], random.int(u8)); + i += run; + } + }, + + .periodic => fillPeriodic( + random, + buf, + random.intRangeAtMost(usize, 1, 40), + ), + + .cells => { + var i: usize = 0; + while (i + 8 <= buf.len) : (i += 8) { + const cell = buf[i..][0..8]; + if (i >= 8 and random.boolean()) { + // Repeat one of the last 256 records. + const back = 8 * random.intRangeAtMost( + usize, + 1, + @min(i / 8, 256), + ); + cell.* = buf[i - back ..][0..8].*; + } else { + @memset(cell, 0); + cell[0] = ' ' + random.uintLessThan(u8, 95); + cell[1] = random.uintLessThan(u8, 4); + } + } + random.bytes(buf[i..]); + }, + + .words => { + const words = [_][]const u8{ + "the", "terminal", "page", "compress", + "row", "cell", "style", "zig", + "lz4", "block", "offset", "match", + "a", "of", "and", "literal", + "0x00", "0xFF", " ", "\r\n", + "-----", "=", "pub fn", "const", + }; + var i: usize = 0; + while (i < buf.len) { + const word = words[random.uintLessThan(usize, words.len)]; + const n = @min(word.len, buf.len - i); + @memcpy(buf[i..][0..n], word[0..n]); + i += n; + if (i < buf.len) { + buf[i] = if (random.boolean()) ' ' else '\n'; + i += 1; + } + } + }, + + .sparse => { + @memset(buf, 0); + if (buf.len == 0) return; + for (0..buf.len / 32 + 1) |_| { + const at = random.uintLessThan(usize, buf.len); + buf[at] = random.int(u8); + } + }, + + .mixed => { + var i: usize = 0; + while (i < buf.len) { + const segment = @min( + random.intRangeAtMost(usize, 1, 2048), + buf.len - i, + ); + const sub = random.enumValue(Generator); + if (sub != .mixed) sub.fill(random, buf[i..][0..segment]); + i += segment; + } + }, + } + } +}; + +/// Fill `buf` with one repeating pattern of the given period. +fn fillPeriodic(random: std.Random, buf: []u8, period: usize) void { + if (buf.len == 0) return; + const head = @min(period, buf.len); + random.bytes(buf[0..head]); + for (head..buf.len) |i| buf[i] = buf[i - period]; +} + +/// Reusable buffers sized for the largest input a suite generates. +const Workspace = struct { + input: []u8, + encoded: []u8, + decoded: []u8, + table: *lz4.HashTable, + + fn init(alloc: Allocator, max_input: usize) !Workspace { + const input = try alloc.alloc(u8, max_input); + errdefer alloc.free(input); + const encoded = try alloc.alloc(u8, try lz4.compressBound(max_input)); + errdefer alloc.free(encoded); + // One extra byte so wrong-size decompression can be tested above + // the exact length as well as below it. + const decoded = try alloc.alloc(u8, max_input + 1); + errdefer alloc.free(decoded); + const table = try alloc.create(lz4.HashTable); + return .{ + .input = input, + .encoded = encoded, + .decoded = decoded, + .table = table, + }; + } + + fn deinit(ws: *Workspace, alloc: Allocator) void { + alloc.free(ws.input); + alloc.free(ws.encoded); + alloc.free(ws.decoded); + alloc.destroy(ws.table); + ws.* = undefined; + } +}; + +/// Compress one input and verify every property promised by the codec. +/// Returns the encoded length so callers can reuse the encoded block. +fn expectCodecProperties(ws: *Workspace, input: []const u8) !usize { + const encoded_len = try lz4.compress(input, ws.encoded, ws.table); + try testing.expect(encoded_len <= try lz4.compressBound(input.len)); + const encoded = ws.encoded[0..encoded_len]; + + try expectValidBlock(encoded, input.len); + + // Exact-size decompression must reproduce the input bit for bit. The + // output is poisoned first so unwritten bytes cannot pass as correct. + const output = ws.decoded[0..input.len]; + @memset(output, 0xAA); + try testing.expectEqual(input.len, try lz4.decompress(encoded, output)); + try testing.expectEqualSlices(u8, input, output); + + // The exact-size contract must reject both smaller and larger buffers. + if (input.len > 0) { + try testing.expectError( + error.OutputTooSmall, + lz4.decompress(encoded, ws.decoded[0 .. input.len - 1]), + ); + } + try testing.expectError( + error.OutputSizeMismatch, + lz4.decompress(encoded, ws.decoded[0 .. input.len + 1]), + ); + + return encoded_len; +} + +/// Structurally validate one encoded block against the LZ4 block format and +/// the stricter guarantees documented by our compressor. This deliberately +/// reimplements the format rather than reusing codec internals. +fn expectValidBlock(encoded: []const u8, raw_len: usize) !void { + var ip: usize = 0; + var op: usize = 0; + var last_match_end: usize = 0; + + while (true) { + // Every sequence, including the final one, starts with a token. + try testing.expect(ip < encoded.len); + const token = encoded[ip]; + ip += 1; + + var literal_len: usize = token >> 4; + if (literal_len == 15) literal_len += try readExtension(encoded, &ip); + try testing.expect(encoded.len - ip >= literal_len); + ip += literal_len; + op += literal_len; + + // The final sequence contains only literals and ends the block. + if (ip == encoded.len) { + try testing.expectEqual(raw_len, op); + if (last_match_end > 0) + try testing.expect(raw_len - last_match_end >= last_literals); + return; + } + + try testing.expect(encoded.len - ip >= 2); + const offset = std.mem.readInt(u16, encoded[ip..][0..2], .little); + ip += 2; + try testing.expect(offset >= 1); + try testing.expect(offset <= op); + + // Our compressor starts matches at least `match_find_limit` bytes + // before the end and never lets one run into the final literals. + try testing.expect(op + match_find_limit <= raw_len); + var match_len: usize = (token & 0x0F) + 4; + if (token & 0x0F == 15) match_len += try readExtension(encoded, &ip); + op += match_len; + try testing.expect(op + last_literals <= raw_len); + last_match_end = op; + } +} + +/// Read one length extension: bytes of 255 accumulate until a terminator +/// below 255, which is included in the sum. +fn readExtension(encoded: []const u8, ip: *usize) !usize { + var total: usize = 0; + while (true) { + try testing.expect(ip.* < encoded.len); + const value = encoded[ip.*]; + ip.* += 1; + total += value; + if (value != 255) return total; + } +} + +/// Decode deterministic corruptions of a valid block. Any result is +/// acceptable except memory unsafety, which the safety-checked test build +/// turns into a failure. Mutations may still form a valid block, so output +/// contents are intentionally not asserted. +fn expectMutationSafety( + ws: *Workspace, + random: std.Random, + encoded_len: usize, + raw_len: usize, + mutations: usize, +) !void { + const original = try testing.allocator.dupe(u8, ws.encoded[0..encoded_len]); + defer testing.allocator.free(original); + + for (0..mutations) |_| { + const block = ws.encoded[0..encoded_len]; + @memcpy(block, original); + + switch (random.uintLessThan(u8, 4)) { + // Flip up to eight random bits. + 0 => for (0..random.intRangeAtMost(usize, 1, 8)) |_| { + const at = random.uintLessThan(usize, block.len); + block[at] ^= @as(u8, 1) << random.int(u3); + }, + // Overwrite one random byte. Token and length bytes are the + // most interesting targets and small blocks are mostly tokens. + 1 => block[random.uintLessThan(usize, block.len)] = + random.int(u8), + // Splice random garbage over a random span. + 2 => { + const at = random.uintLessThan(usize, block.len); + const span = @min( + random.intRangeAtMost(usize, 1, 16), + block.len - at, + ); + random.bytes(block[at..][0..span]); + }, + // Decode a random prefix of the intact block. + else => {}, + } + + const len = if (random.boolean()) + random.uintAtMost(usize, block.len) + else + block.len; + _ = lz4.decompress(block[0..len], ws.decoded[0..raw_len]) catch {}; + } +} + +/// Workload knobs shared by the light and exhaustive suites. +const Budget = struct { + /// Upper bound and step of the contiguous small-size sweep applied to + /// every generator. + sweep_max: usize, + sweep_step: usize, + + /// Number and maximum size of random-parameter inputs. + random_inputs: usize, + random_max: usize, + + /// Explicit match periods checked with `fillPeriodic`. + periods: []const usize, + period_len: usize, + + /// Number of corrupted decode attempts per mutation base block. + mutations: usize, + + fn maxInput(budget: Budget) usize { + return @max( + budget.random_max, + @max(budget.period_len, boundary_sizes[boundary_sizes.len - 1]), + ); + } +}; + +const light_budget: Budget = .{ + .sweep_max = 96, + .sweep_step = 1, + .random_inputs = 24, + .random_max = 32 * 1024, + // One period per copy strategy: byte propagation (3), pattern words + // (1/2/4/8), word strides (9), wide strides (17), plus the 64 KiB + // window edge cases. + .periods = &.{ 1, 2, 3, 4, 8, 9, 17, 65534, 65535, 65536, 65537 }, + .period_len = 160 * 1024, + .mutations = 64, +}; + +const exhaustive_budget: Budget = .{ + .sweep_max = 2048, + .sweep_step = 1, + .random_inputs = 512, + .random_max = 512 * 1024, + .periods = &.{ + 1, 2, 3, 4, 5, 6, 7, 8, + 9, 10, 11, 12, 13, 14, 15, 16, + 17, 18, 19, 23, 24, 31, 32, 33, + 48, 63, 64, 65, 127, 128, 255, 256, + 257, 4095, 4096, 32768, 65533, 65534, 65535, 65536, + 65537, 65538, + }, + .period_len = 320 * 1024, + .mutations = 4096, +}; + +fn runSuite(budget: Budget, seed: u64) !void { + var prng = std.Random.DefaultPrng.init(seed); + const random = prng.random(); + + var ws: Workspace = try .init(testing.allocator, budget.maxInput()); + defer ws.deinit(testing.allocator); + + // Every generator across every boundary size and the small-size sweep. + // Small inputs hit the literal-only format edges: below the minimum + // match sizes, around nibble limits, and around extension steps. + inline for (@typeInfo(Generator).@"enum".fields) |field| { + const gen: Generator = @enumFromInt(field.value); + + for (boundary_sizes) |size| { + const input = ws.input[0..size]; + gen.fill(random, input); + _ = try expectCodecProperties(&ws, input); + } + + var size: usize = 0; + while (size <= budget.sweep_max) : (size += budget.sweep_step) { + const input = ws.input[0..size]; + gen.fill(random, input); + _ = try expectCodecProperties(&ws, input); + } + } + + // Random generator and size pairs, biased toward interesting sizes by + // squaring so both tiny and large inputs appear. + for (0..budget.random_inputs) |_| { + const gen = random.enumValue(Generator); + const scale = random.float(f64); + const size: usize = @intFromFloat( + scale * scale * @as(f64, @floatFromInt(budget.random_max)), + ); + const input = ws.input[0..size]; + gen.fill(random, input); + const encoded_len = try expectCodecProperties(&ws, input); + + // Reuse a handful of these encodings as corruption bases. + try expectMutationSafety( + &ws, + random, + encoded_len, + input.len, + budget.mutations / budget.random_inputs + 1, + ); + } + + // Directed match periods, including the 64 KiB window edge where the + // compressor's 16-bit position arithmetic wraps. + for (budget.periods) |period| { + const input = ws.input[0..budget.period_len]; + fillPeriodic(random, input, period); + _ = try expectCodecProperties(&ws, input); + } + + // Dedicated corruption run over a text-like block, plus an exhaustive + // truncation sweep: every prefix of a valid block must decode cleanly + // or fail cleanly. + { + const input = ws.input[0..@min(16 * 1024, budget.random_max)]; + Generator.words.fill(random, input); + const encoded_len = try expectCodecProperties(&ws, input); + try expectMutationSafety( + &ws, + random, + encoded_len, + input.len, + budget.mutations, + ); + + for (0..encoded_len) |prefix| { + _ = lz4.decompress( + ws.encoded[0..prefix], + ws.decoded[0..input.len], + ) catch {}; + } + } +} + +test "lz4 differential light" { + try runSuite(light_budget, 0x4C5A_3403); +} + +test "lz4 differential exhaustive" { + // Slow. Enable explicitly, ideally together with a test filter: + // GHOSTTY_LZ4_SLOW=1 zig build test -Dtest-filter="lz4 differential" + if (!std.process.hasEnvVarConstant("GHOSTTY_LZ4_SLOW")) + return error.SkipZigTest; + + // Several independent seeds; the suite is deterministic per seed. + for (0..4) |seed| try runSuite(exhaustive_budget, 0x4C5A_4000 + seed); +} |
