chore: update vendored libghostty-vt

refs #276

4 files changed, 1872 insertions, 0 deletions

diff --git a/vendor/libghostty-vt/src/terminal/compress/AGENTS.md b/vendor/libghostty-vt/src/terminal/compress/AGENTS.md
new file mode 100644
index 00000000..172891d9
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/compress/AGENTS.md
@@ -0,0 +1,90 @@
+# Terminal Compression
+
+Guidance for the codecs and the compressed page representation
+(`Page.zig`) in this directory. These compress terminal page backing
+memory (`terminal.Page`).
+
+## Priorities
+
+When making tradeoffs, in order:
+
+1. **Compression ratio on page-shaped data.** Encoded bytes are retained
+   scrollback memory, and raw `terminal.Page` backing memory is the only
+   thing we actually compress. Ratio on text files or synthetic data is a
+   secondary signal.
+2. **Decompression throughput.** Pages are compressed once when they go
+   cold but restored on demand (scrollback access, search, inspection), so
+   restore latency is felt directly.
+3. **Compression throughput.** Runs on idle pages in the background; being
+   fast is nice, being slow is tolerable.
+
+## Testing
+
+- Targeted tests: `zig build test -Dtest-filter=<codec>`
+- Prefer `zig build test-lib-vt -Dtest-filter=<codec>` when practical;
+  this code ships in libghostty-vt.
+- Codecs must keep building for `wasm32-freestanding` (libghostty-vt):
+  no libc, no `src/simd` (Highway) dependencies. Verify with
+  `zig build -Demit-lib-vt -Dtarget=wasm32-freestanding -Doptimize=ReleaseSmall`.
+- Every codec needs a differential property suite: round-trip identity,
+  an independent format walker, wrong-size output rejection, and
+  corruption/truncation decoding. Keep a light version in normal unit
+  tests and gate the exhaustive version behind an environment variable so
+  the default test suite stays fast.
+
+## Verifying Correctness
+
+- Decoders must be memory-safe for arbitrary input bytes. Every blind or
+  wide copy needs a stated margin argument bounding it by the output
+  buffer; keep those arguments in comments next to the code.
+- Writing scratch bytes past a copy's logical end is safe only inside the
+  output buffer, because in-order decoding rewrites them before any match
+  can read them back. Do not weaken the exact-size output contract.
+- When a change should not alter compressor output, prove it: compare
+  encoded sizes (or a sequence-count fingerprint) on the same corpus
+  before and after. Ratio drift is a functional change, not noise.
+
+## Benchmarking
+
+- Use `ghostty-bench +page-compression` (see `src/benchmark/AGENTS.md`
+  for the general workflow). Modes: `compress`, `decompress`, `store`,
+  and `report` for ratio.
+- Build: `zig build -Demit-bench -Doptimize=ReleaseFast -Demit-macos-app=false`
+- The most representative corpus is a raw dump of real page backing
+  memory, chunked at the page size (400 KiB on ReleaseFast targets).
+  Supplement with a text corpus and random bytes for worst cases, but
+  weigh page corpora highest per the priorities above. Keep corpora
+  outside the repository and reuse identical files across comparisons.
+- `ghostty-bench +scrollback-compression` measures the PageList
+  transitions around the codec rather than the codec itself.
+- For fast iteration, keep codecs dependent only on `std` so a standalone
+  harness can build them directly with `zig build-exe -O ReleaseFast` and
+  time the codec in-process (report min-of-N, verify round-trips).
+- Measure one change at a time and re-measure the final state; run-to-run
+  noise is a few percent, so re-run before believing small deltas.
+
+## Performance Notes
+
+- Real page data decodes as millions of tiny operations (in LZ4: mostly
+  zero literals plus a 4-18 byte match). Per-item overhead dominates, so
+  branch-light fast paths with blind fixed-size copies win.
+- Wide copies are the only SIMD that pays here. Vectorized compares and
+  other wide-stride tricks measured as net losses because matches are
+  short; prefer the simple word loop unless a measurement on page corpora
+  says otherwise.
+- `@memcpy` beats stride loops only for long copies (roughly 64 bytes and
+  up); call overhead loses below that.
+
+## LZ4 Specific
+
+- The codec is `lz4.zig`, an allocation-free raw block (not frame)
+  implementation. Blocks do not carry their decoded size; callers supply
+  an exact-size output buffer.
+- Tests: `zig build test -Dtest-filter=lz4`. The differential suite is
+  `lz4_differential.zig`; run the exhaustive version for any codec
+  change:
+  `GHOSTTY_LZ4_SLOW=1 zig build test -Dtest-filter="lz4 differential"`
+- The compressor must keep the standard format restrictions (final five
+  bytes literal, matches start at least twelve bytes before the end) so
+  blocks stay consumable by optimized external decoders. The differential
+  walker checks this.
diff --git a/vendor/libghostty-vt/src/terminal/compress/Page.zig b/vendor/libghostty-vt/src/terminal/compress/Page.zig
new file mode 100644
index 00000000..b7ad8025
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/compress/Page.zig
@@ -0,0 +1,398 @@
+//! A compressed terminal page which retains its resident virtual mapping.
+//!
+//! Terminal pages have two kinds of state: the large `Page.memory` allocation
+//! and a comparatively small `Page` value containing offsets, dimensions,
+//! dirty state, and allocator metadata. Not all of the latter state lives in
+//! the backing memory, so preserving only the memory bytes is insufficient.
+//! We preserve the complete `Page` value instead. This follows the same model
+//! as `Page.cloneBuf`: page internals use offsets, so a shallow page copy remains
+//! valid when its memory contents are restored at the same address.
+//!
+//! The resident memory is deliberately not freed by this type. `PageList`
+//! keeps the virtual range allocated while asking the operating system to
+//! discard its physical pages. Keeping the range has two useful properties:
+//! the embedded page never contains a dangling pointer, and restoring the page
+//! does not require a fallible allocation.
+//!
+//! The intended state transition is:
+//!
+//! 1. Create this value while the source page is resident.
+//! 2. Ask the OS to decommit the source page's memory.
+//! 3. Replace the PageList node's resident state with this value.
+//! 4. To restore, recommit the retained range and call `restore`.
+//! 5. After committing the resident state, call `deinit` to free the encoded
+//!    bytes.
+//!
+//! If decommit is unavailable or fails, the caller should deinitialize the
+//! compressed candidate and leave the source page resident. This type does not
+//! perform any virtual-memory operations itself.
+//!
+//! The planned native implementation uses `MADV_DONTNEED` on Linux and pairs
+//! `MADV_FREE_REUSABLE` with `MADV_FREE_REUSE` on Darwin. Targets without a
+//! reliable retained-mapping decommit operation should leave page compression
+//! disabled rather than free and later reallocate the resident memory.
+const Page = @This();
+
+const std = @import("std");
+const assert = std.debug.assert;
+const Allocator = std.mem.Allocator;
+const TerminalPage = @import("../page.zig").Page;
+const lz4 = @import("lz4.zig");
+
+/// Complete page metadata together with the retained resident mapping.
+///
+/// The bytes in `page.memory` may have been discarded by the OS while this
+/// value is in compressed state. They must not be read until `restore` has
+/// successfully decoded the page.
+page: TerminalPage,
+
+/// Exact raw LZ4 block for `page.memory`.
+encoded: []u8,
+
+/// Allocator which owns `encoded`.
+///
+/// The allocator's backing state must outlive this compressed page. Storing
+/// the allocator here lets a PageList node restore and discard its compressed
+/// state without needing a reference back to the PageList.
+alloc: Allocator,
+
+/// Return the largest scratch buffer that can produce a useful compressed
+/// representation for `raw_len` bytes.
+///
+/// This is deliberately smaller than the general LZ4 compression bound. The
+/// compressed representation includes an additional slice compared to a
+/// resident terminal page, so an encoded block which fills more than this
+/// buffer cannot reduce resident memory. Limiting the output here lets a
+/// PageList borrow a standard page-pool item as scratch instead of retaining a
+/// larger, compression-bound allocation.
+///
+/// Callers are expected to reuse the scratch memory when practical. The
+/// scratch buffer and hash table are never retained by this type.
+pub fn requiredScratch(raw_len: usize) lz4.CompressError!usize {
+    // Validate the codec's input limit before doing arithmetic based on the
+    // raw size. The bound itself is intentionally not returned; see above.
+    _ = try lz4.compressBound(raw_len);
+
+    const representation_overhead = @sizeOf(Page) - @sizeOf(TerminalPage);
+    if (raw_len <= representation_overhead) return 0;
+
+    // The savings comparison is strict, so reserve one fewer byte than the
+    // break-even encoded size.
+    return raw_len - representation_overhead - 1;
+}
+
+/// Create a compressed representation of `source`.
+///
+/// `source` is not modified and continues to own its backing allocation. The
+/// scratch buffer must be at least `requiredScratch(source.memory.len)` bytes.
+/// It must not overlap the source memory. On success, the returned value aliases
+/// the source's resident mapping and owns only its exact-sized `encoded`
+/// allocation. The allocator and its backing state must remain valid until
+/// `deinit` is called.
+///
+/// Returns null if retaining the compressed representation would not use less
+/// memory than the resident representation. An `OutputTooSmall` result from
+/// the codec also means the encoding crossed that break-even point and is
+/// therefore returned as null. This comparison includes the in-memory size of
+/// both representation structs but does not include allocator metadata or the
+/// retained virtual address range.
+pub fn init(
+    alloc: Allocator,
+    source: *const TerminalPage,
+    scratch: []u8,
+    table: *lz4.HashTable,
+) (Allocator.Error || lz4.CompressError)!?Page {
+    const required = try requiredScratch(source.memory.len);
+    if (scratch.len < required) return error.OutputTooSmall;
+    if (required == 0) return null;
+
+    const encoded_len = lz4.compress(
+        source.memory,
+        scratch[0..required],
+        table,
+    ) catch |err| switch (err) {
+        // The scratch limit is the largest representation worth retaining.
+        // Running out of room therefore means compression cannot save memory,
+        // rather than that the caller failed to provide the documented size.
+        error.OutputTooSmall => return null,
+        error.InputTooLarge => return err,
+    };
+
+    // requiredScratch already accounts for the representation structs. The
+    // retained virtual range contributes no resident bytes after PageList
+    // decommits it.
+    assert(@sizeOf(Page) + encoded_len <
+        @sizeOf(TerminalPage) + source.memory.len);
+
+    return .{
+        .page = source.*,
+        .encoded = try alloc.dupe(u8, scratch[0..encoded_len]),
+        .alloc = alloc,
+    };
+}
+
+/// Free the encoded block.
+///
+/// This intentionally does not free `page.memory`. The PageList node which
+/// supplied the source page continues to own that pool or heap allocation.
+pub fn deinit(self: *Page) void {
+    self.alloc.free(self.encoded);
+    self.* = undefined;
+}
+
+/// Restore the embedded terminal page into its retained resident mapping.
+///
+/// The caller must recommit `page.memory` before calling this on platforms
+/// which require an explicit recommit operation. The compressed value remains
+/// valid whether decoding succeeds or fails, allowing the caller to retry or
+/// discard it. On success the returned page aliases the same resident mapping;
+/// it does not own a new allocation.
+pub fn restore(self: *const Page) lz4.DecompressError!TerminalPage {
+    const result = self.page;
+    _ = try lz4.decompress(self.encoded, result.memory);
+    return result;
+}
+
+/// Clone this page into caller-owned memory without restoring its mapping.
+///
+/// `memory` must be at least as large as the retained page mapping. Decoding
+/// writes only to that buffer, so both the discarded contents of `page.memory`
+/// and this value's encoded representation remain unchanged. The returned Page
+/// borrows `memory`; the caller must keep it alive for the Page's lifetime and
+/// release it directly rather than calling `TerminalPage.deinit`.
+pub fn cloneBuf(
+    self: *const Page,
+    memory: []align(std.heap.page_size_min) u8,
+) lz4.DecompressError!TerminalPage {
+    assert(memory.len >= self.page.memory.len);
+
+    // Page internals are offsets into the backing buffer, so all metadata can
+    // be copied verbatim when paired with an equally laid-out mapping.
+    var result = self.page;
+    result.memory = memory[0..self.page.memory.len];
+    _ = try lz4.decompress(self.encoded, result.memory);
+    return result;
+}
+
+test "compressed Page retained mapping round trip" {
+    const testing = std.testing;
+
+    var resident = try TerminalPage.init(.{
+        .cols = 12,
+        .rows = 9,
+        .styles = 8,
+        .grapheme_bytes = 128,
+        .string_bytes = 128,
+    });
+    defer resident.deinit();
+    resident.size = .{ .cols = 10, .rows = 7 };
+    resident.dirty = true;
+
+    // Put state in both the backing memory and the Page value. In particular,
+    // the style and hyperlink sets retain live counters outside Page.memory.
+    const rac = resident.getRowAndCell(2, 3);
+    rac.cell.* = .init('A');
+    try resident.appendGrapheme(rac.row, rac.cell, 0x0301);
+
+    const style_id = try resident.styles.add(resident.memory, .{ .flags = .{
+        .bold = true,
+    } });
+    rac.cell.style_id = style_id;
+    rac.row.styled = true;
+
+    const hyperlink_id = try resident.insertHyperlink(.{
+        .id = .{ .explicit = "compressed-page" },
+        .uri = "https://ghostty.org/docs",
+    });
+    try resident.setHyperlink(rac.row, rac.cell, hyperlink_id);
+    try resident.verifyIntegrity(testing.allocator);
+
+    const expected = try testing.allocator.dupe(u8, resident.memory);
+    defer testing.allocator.free(expected);
+    const memory_ptr = resident.memory.ptr;
+    const memory_len = resident.memory.len;
+
+    const scratch = try testing.allocator.alloc(
+        u8,
+        try requiredScratch(resident.memory.len),
+    );
+    defer testing.allocator.free(scratch);
+    var table: lz4.HashTable = undefined;
+    var compressed = (try Page.init(
+        testing.allocator,
+        &resident,
+        scratch,
+        &table,
+    )).?;
+    defer compressed.deinit();
+
+    try testing.expectEqual(memory_ptr, compressed.page.memory.ptr);
+    try testing.expectEqual(memory_len, compressed.page.memory.len);
+    try testing.expect(compressed.encoded.len < resident.memory.len);
+    const expected_encoded = try testing.allocator.dupe(u8, compressed.encoded);
+    defer testing.allocator.free(expected_encoded);
+
+    // Virtual-memory operations belong to PageList, so clearing the contents
+    // models a successful decommit: none of the resident bytes remain.
+    @memset(resident.memory, 0);
+
+    // A clone decodes into independent storage for read-only consumers which
+    // must not change the compressed representation. In particular, it does
+    // not recommit or overwrite the retained source mapping.
+    const clone_memory = try testing.allocator.alignedAlloc(
+        u8,
+        .fromByteUnits(std.heap.page_size_min),
+        resident.memory.len,
+    );
+    defer testing.allocator.free(clone_memory);
+    const cloned = try compressed.cloneBuf(clone_memory);
+    try testing.expect(cloned.memory.ptr != memory_ptr);
+    try testing.expect(std.mem.allEqual(u8, resident.memory, 0));
+    try testing.expectEqualSlices(u8, expected_encoded, compressed.encoded);
+    try testing.expectEqualSlices(u8, expected, cloned.memory);
+    try testing.expectEqual(resident.size, cloned.size);
+    try testing.expect(cloned.dirty);
+    try cloned.verifyIntegrity(testing.allocator);
+
+    const restored = try compressed.restore();
+    try testing.expectEqual(memory_ptr, restored.memory.ptr);
+    try testing.expectEqual(memory_len, restored.memory.len);
+    try testing.expectEqualSlices(u8, expected, restored.memory);
+    try testing.expectEqual(resident.size, restored.size);
+    try testing.expect(restored.dirty);
+    try restored.verifyIntegrity(testing.allocator);
+
+    const restored_rac = restored.getRowAndCell(2, 3);
+    try testing.expectEqualSlices(
+        u21,
+        &.{0x0301},
+        restored.lookupGrapheme(restored_rac.cell).?,
+    );
+    try testing.expect(restored.styles.get(
+        restored.memory,
+        restored_rac.cell.style_id,
+    ).flags.bold);
+
+    const restored_hyperlink_id = restored.lookupHyperlink(restored_rac.cell).?;
+    const restored_hyperlink = restored.hyperlink_set.get(
+        restored.memory,
+        restored_hyperlink_id,
+    );
+    try testing.expectEqualStrings(
+        "https://ghostty.org/docs",
+        restored_hyperlink.uri.slice(restored.memory),
+    );
+}
+
+test "compressed Page requires the maximum useful scratch" {
+    const testing = std.testing;
+
+    var resident = try TerminalPage.init(.{ .cols = 4, .rows = 4 });
+    defer resident.deinit();
+    const expected = try testing.allocator.dupe(u8, resident.memory);
+    defer testing.allocator.free(expected);
+
+    const required = try requiredScratch(resident.memory.len);
+    try testing.expectEqual(
+        resident.memory.len - (@sizeOf(Page) - @sizeOf(TerminalPage)) - 1,
+        required,
+    );
+    try testing.expect(required < try lz4.compressBound(resident.memory.len));
+
+    const scratch = try testing.allocator.alloc(u8, required - 1);
+    defer testing.allocator.free(scratch);
+    var table: lz4.HashTable = undefined;
+
+    try testing.expectError(error.OutputTooSmall, Page.init(
+        testing.allocator,
+        &resident,
+        scratch,
+        &table,
+    ));
+    try testing.expectEqualSlices(u8, expected, resident.memory);
+}
+
+test "compressed Page rejects a representation without savings" {
+    const testing = std.testing;
+
+    var resident = try TerminalPage.init(.{
+        .cols = 4,
+        .rows = 4,
+        .styles = 0,
+        .grapheme_bytes = 0,
+        .string_bytes = 0,
+        .hyperlink_bytes = 0,
+    });
+    defer resident.deinit();
+
+    var prng = std.Random.DefaultPrng.init(0x4C5A_3402);
+    prng.random().bytes(resident.memory);
+
+    const scratch = try testing.allocator.alloc(
+        u8,
+        try requiredScratch(resident.memory.len),
+    );
+    defer testing.allocator.free(scratch);
+    var table: lz4.HashTable = undefined;
+    var failing = testing.FailingAllocator.init(testing.allocator, .{
+        .fail_index = 0,
+    });
+
+    try testing.expect((try Page.init(
+        failing.allocator(),
+        &resident,
+        scratch,
+        &table,
+    )) == null);
+    try testing.expect(!failing.has_induced_failure);
+}
+
+test "compressed Page can retry after malformed encoded data" {
+    const testing = std.testing;
+
+    var resident = try TerminalPage.init(.{ .cols = 8, .rows = 8 });
+    defer resident.deinit();
+    const expected = try testing.allocator.dupe(u8, resident.memory);
+    defer testing.allocator.free(expected);
+
+    const scratch = try testing.allocator.alloc(
+        u8,
+        try requiredScratch(resident.memory.len),
+    );
+    defer testing.allocator.free(scratch);
+    var table: lz4.HashTable = undefined;
+    var compressed = (try Page.init(
+        testing.allocator,
+        &resident,
+        scratch,
+        &table,
+    )).?;
+    defer compressed.deinit();
+
+    const full_encoded = compressed.encoded;
+    const first_byte = full_encoded[0];
+    defer {
+        compressed.encoded = full_encoded;
+        compressed.encoded[0] = first_byte;
+    }
+    compressed.encoded = full_encoded[0..1];
+    compressed.encoded[0] = 0xF0;
+
+    const clone_memory = try testing.allocator.alignedAlloc(
+        u8,
+        .fromByteUnits(std.heap.page_size_min),
+        resident.memory.len,
+    );
+    defer testing.allocator.free(clone_memory);
+    try testing.expectError(
+        error.TruncatedInput,
+        compressed.cloneBuf(clone_memory),
+    );
+    try testing.expectError(error.TruncatedInput, compressed.restore());
+
+    compressed.encoded = full_encoded;
+    compressed.encoded[0] = first_byte;
+    @memset(resident.memory, 0);
+    const restored = try compressed.restore();
+    try testing.expectEqualSlices(u8, expected, restored.memory);
+}
diff --git a/vendor/libghostty-vt/src/terminal/compress/lz4.zig b/vendor/libghostty-vt/src/terminal/compress/lz4.zig
new file mode 100644
index 00000000..a6b07763
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/compress/lz4.zig
@@ -0,0 +1,891 @@
+//! An allocation-free implementation of the raw LZ4 block format.
+//!
+//! LZ4 has two relevant layers: the block format describes the compressed
+//! bytes, while the frame format adds headers, sizes, checksums, and support
+//! for a stream of blocks. Terminal pages already have their own ownership
+//! and metadata, so this implements only blocks. In particular, an encoded
+//! block does not contain its decompressed size. The caller must store that
+//! separately and provide an exactly sized buffer when decoding.
+//!
+//! A block is a series of sequences. Each non-final sequence has this shape:
+//!
+//!     token | literal length extensions | literals | offset | match length extensions
+//!
+//! The token's high nibble contains the literal length and its low nibble
+//! contains the match length minus four. A nibble value of 15 means that the
+//! length continues in extension bytes at the corresponding point in the
+//! sequence. Each extension byte adds to the length; a value of 255 means
+//! another byte follows. The literal bytes are copied directly. The two-byte
+//! little-endian offset then points backwards in the already decompressed
+//! output to the match bytes.
+//!
+//! The last sequence is special: it contains literals only and ends directly
+//! after them. The reference format also requires the last five input bytes to
+//! be literals and the final match to begin at least twelve bytes before the
+//! end of the input. The compressor observes these restrictions so its output
+//! can be consumed by optimized LZ4 decoders which copy in larger units.
+//!
+//! Compression uses the fast LZ4 strategy: hash each four-byte input sequence
+//! and test recent positions as match candidates. Two 16-bit positions fit in
+//! each hash-table entry because the format cannot refer further than 64 KiB
+//! backwards. Retaining the displaced position recovers useful matches after
+//! hash collisions without increasing the fixed 16 KiB workspace. Long runs
+//! without matches gradually skip input positions, while matching runs are
+//! extended a machine word at a time. The implementation allocates nothing;
+//! all input, output, and scratch memory is supplied by the caller.
+//!
+//! Format reference:
+//! https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md
+const std = @import("std");
+const assert = std.debug.assert;
+const testing = std.testing;
+
+/// Maximum input accepted by the reference LZ4 block API. Keeping the same
+/// limit means `compressBound` fits in the integer sizes used by LZ4 callers
+/// and gives us the same compatibility boundary as other implementations.
+pub const max_input_size: usize = 0x7E000000;
+
+/// Every LZ4 match represents at least four bytes. The token stores the number
+/// of bytes beyond this minimum rather than the full match length.
+const min_match = 4;
+
+/// Number of bytes at the end of a conforming block which must remain literals.
+const last_literals = 5;
+
+/// A match may not begin in the final 12 bytes. This leaves enough room for the
+/// minimum match and the required five trailing literals.
+const match_find_limit = 12;
+
+/// We retain one input position for each 12-bit hash. LZ4 refers to this as
+/// memory usage 14 because the 4096 entries are four bytes each (16 KiB).
+const hash_log = 12;
+
+/// Multiplicative hash used by the reference LZ4 fast compressor. The high
+/// `hash_log` bits provide the table index.
+const hash_multiplier: u32 = 2_654_435_761;
+
+/// Scratch memory used while compressing one block. Each entry packs the low
+/// 16 bits of the two most recent input positions for its hash. All-ones marks
+/// an empty half; LZ4's 16-bit offset is enough to reconstruct the only useful
+/// preceding address from the current position.
+/// The table is reset by every call to `compress` and can be reused afterwards.
+pub const HashTable = [1 << hash_log]u32;
+
+/// Errors which can occur while encoding a block.
+pub const CompressError = error{
+    /// The input exceeds the maximum size supported by the block compressor.
+    InputTooLarge,
+
+    /// The provided output buffer cannot hold the encoded block.
+    OutputTooSmall,
+};
+
+/// Errors which can occur while decoding a block.
+pub const DecompressError = error{
+    /// The encoded block ended in the middle of a sequence.
+    TruncatedInput,
+
+    /// A match offset was zero or pointed before the produced output.
+    InvalidOffset,
+
+    /// A sequence would write beyond the provided output buffer.
+    OutputTooSmall,
+
+    /// The block ended before filling the exact-size output buffer.
+    OutputSizeMismatch,
+};
+
+/// Return the maximum number of bytes needed to encode `input_len` bytes.
+///
+/// Incompressible input is represented as one literal run. Every 255 literal
+/// bytes can require one extension byte. The additional 16-byte margin covers
+/// the token and the format's fixed overhead. Callers can allocate this amount
+/// once and reuse it for any block no larger than `input_len`.
+pub fn compressBound(input_len: usize) CompressError!usize {
+    if (input_len > max_input_size) return error.InputTooLarge;
+    return input_len + input_len / 255 + 16;
+}
+
+/// Compress `input` into a raw LZ4 block in `output`.
+///
+/// Returns the initialized length of `output`. The input and output buffers
+/// must not overlap. `table` is scratch space and does not need to be
+/// initialized by the caller; it is reset before use.
+pub fn compress(
+    input: []const u8,
+    output: []u8,
+    table: *HashTable,
+) CompressError!usize {
+    if (input.len > max_input_size) return error.InputTooLarge;
+
+    // All-ones in either packed half means "no previous position".
+    @memset(table, std.math.maxInt(u32));
+
+    // `ip` is the current input position, `anchor` is the first literal not yet
+    // emitted, and `op` is the next output position. A successful match emits
+    // input[anchor..ip] as literals followed by the match, then moves both input
+    // positions to the end of that match.
+    var op: usize = 0;
+    var anchor: usize = 0;
+
+    // LZ4's format leaves the final five input bytes as literals and starts
+    // the final match at least twelve bytes before the end. This is not
+    // required by our safe decoder, but makes blocks compatible with fast
+    // decoders that rely on the standard format restrictions. Inputs too
+    // short for any match are emitted below as one literal-only sequence.
+    if (input.len >= match_find_limit) {
+        const search_end = input.len - match_find_limit;
+        const match_end_limit = input.len - last_literals;
+        var ip: usize = 0;
+        var search_attempts: usize = 0;
+
+        search: while (ip <= search_end) {
+            // Hash the next four bytes and replace the table entry
+            // immediately. Hash collisions are expected, so equality is
+            // checked below before accepting a saved position as a match.
+            const sequence = readU32(input, ip);
+            const hash = hashSequence(sequence);
+            const candidates = table[hash];
+            rememberPosition(table, hash, ip);
+
+            var match_pos = candidatePosition(ip, @truncate(candidates)) orelse
+                candidatePosition(ip, @truncate(candidates >> 16)) orelse
+                {
+                    advanceSearch(&ip, anchor, &search_attempts);
+                    continue :search;
+                };
+
+            if (readU32(input, match_pos) != sequence) {
+                // The nearest candidate collided. Fall back to the older
+                // one, which must additionally match one byte beyond the
+                // minimum so collision-prone minimum-length matches from
+                // the stale half are not emitted.
+                match_pos = older: {
+                    if (candidatePosition(
+                        ip,
+                        @truncate(candidates >> 16),
+                    )) |older| {
+                        if (readU32(input, older) == sequence and
+                            input[older + min_match] == input[ip + min_match])
+                        {
+                            break :older older;
+                        }
+                    }
+
+                    advanceSearch(&ip, anchor, &search_attempts);
+                    continue :search;
+                };
+            }
+
+            // Pull the match backwards into the current literal run. This is
+            // particularly helpful around aligned cell records. As with
+            // forward extension, compare words before locating the first
+            // differing byte.
+            const match_begin = matchBegin(input, ip, match_pos, anchor);
+            ip = match_begin.position;
+            match_pos = match_begin.candidate;
+
+            // We already compared the first four bytes. Continue up to the
+            // point where the required last five literals begin. `matchEnd`
+            // compares a machine word at a time before locating the first
+            // differing byte.
+            const match_end = matchEnd(
+                input,
+                ip + min_match,
+                match_pos + min_match,
+                match_end_limit,
+            );
+
+            try emitSequence(
+                output,
+                &op,
+                input[anchor..ip],
+                @intCast(ip - match_pos),
+                match_end - ip,
+            );
+
+            // The main loop jumps over the matched bytes rather than hashing
+            // every position within them. Seed one position near the end so
+            // an adjacent repeated record can still refer back into this
+            // match. The next loop iteration will then seed `match_end`
+            // normally.
+            if (match_end >= 2 and match_end - 2 + min_match <= input.len) {
+                const seed = match_end - 2;
+                rememberPosition(
+                    table,
+                    hashSequence(readU32(input, seed)),
+                    seed,
+                );
+            }
+
+            ip = match_end;
+            anchor = ip;
+            search_attempts = 0;
+        }
+    }
+
+    // Whatever remains after the last match is the terminal literal-only
+    // sequence. For short inputs this is also the only sequence in the block.
+    try emitLastLiterals(output, &op, input[anchor..]);
+    return op;
+}
+
+/// Decompress a raw LZ4 block into an exact-size output buffer.
+///
+/// Returns `output.len` on success. Both consuming all input and filling all
+/// output are required. Raw LZ4 blocks do not carry their decoded size, so this
+/// exact-size contract validates the size metadata maintained by the caller.
+/// The input and output buffers must not overlap.
+pub fn decompress(input: []const u8, output: []u8) DecompressError!usize {
+    // `ip` and `op` always identify the next unread input byte and the next
+    // unwritten output byte respectively.
+    //
+    // The decoder is written around one observation: almost every sequence
+    // in real blocks has a short literal run and a short match. Both fast
+    // paths below copy a fixed number of bytes blindly and let the length
+    // arithmetic sort out how many of them were meaningful. Writing past a
+    // run's logical end is safe within the output buffer because decoding
+    // is strictly in order: every byte past `op` is either rewritten by a
+    // later copy before anything can read it, or lies beyond the block's
+    // final length and is never part of the result. The margin conditions
+    // on the fast paths also subsume the exact bounds checks they replace,
+    // which keeps decoding of malformed blocks memory-safe.
+    var ip: usize = 0;
+    var op: usize = 0;
+
+    while (true) {
+        // A normal block ends after the literal bytes of its final sequence.
+        // This also accepts the empty block produced by our compressor, which
+        // consists of a zero token and no literals.
+        if (ip == input.len) {
+            if (op != output.len) return error.OutputSizeMismatch;
+            return op;
+        }
+
+        const token = input[ip];
+        ip += 1;
+
+        // The high nibble and any extension bytes describe the literal run.
+        // The literals are copied as a side effect of computing the length.
+        const literal_len: usize = len: {
+            const nibble: usize = token >> 4;
+            if (nibble != 15 and
+                @min(input.len - ip, output.len - op) >= 16)
+            {
+                // A run below the extension threshold is at most 14 bytes,
+                // so with a 16-byte margin on both buffers one wide copy
+                // covers it.
+                copyIntAt(u128, output, op, input, ip);
+                break :len nibble;
+            }
+
+            // Extended or margin-poor runs take the checked path. Bounds are
+            // verified before copying so malformed blocks never cause a
+            // partial read or write.
+            const len = try decodeLength(input, &ip, nibble);
+            if (len > input.len - ip) return error.TruncatedInput;
+            if (len > output.len - op) return error.OutputTooSmall;
+            @memcpy(output[op..][0..len], input[ip..][0..len]);
+            break :len len;
+        };
+        ip += literal_len;
+        op += literal_len;
+
+        // Ending immediately after the literals marks the final sequence. Any
+        // non-final sequence must continue with an offset and match length.
+        if (ip == input.len) {
+            if (op != output.len) return error.OutputSizeMismatch;
+            return op;
+        }
+
+        if (input.len - ip < 2) return error.TruncatedInput;
+        const offset = readIntAt(u16, input, ip);
+        ip += 2;
+        if (offset == 0 or offset > op) return error.InvalidOffset;
+
+        // The token stores the match length minus the four-byte minimum. As
+        // with literals, a low nibble of 15 is extended by following bytes.
+        const match_nibble: usize = token & 0x0F;
+
+        // A match whose length fits its nibble spans at most 18 bytes, so
+        // three blind copies always cover it. They are overlap-safe when the
+        // offset is at least a word: each load lies a full word behind the
+        // store which could observe it, so repeating patterns propagate
+        // correctly.
+        if (match_nibble != 15 and offset >= 8 and output.len - op >= 18) {
+            const match = op - offset;
+            copyIntAt(u64, output, op, output, match);
+            copyIntAt(u64, output, op + 8, output, match + 8);
+            copyIntAt(u16, output, op + 16, output, match + 16);
+            op += match_nibble + min_match;
+            continue;
+        }
+
+        const encoded_match_len = try decodeLength(input, &ip, match_nibble);
+        const match_len = std.math.add(
+            usize,
+            encoded_match_len,
+            min_match,
+        ) catch return error.OutputTooSmall;
+        if (match_len > output.len - op) return error.OutputTooSmall;
+
+        // Match copies may overlap, so this cannot always be one memcpy.
+        // `copyMatch` expands the common small repeating periods into wide
+        // stores and uses word copies for larger offsets.
+        copyMatch(output, op, offset, match_len);
+        op += match_len;
+    }
+}
+
+/// Emit one non-final sequence.
+///
+/// A sequence starts with a token, followed by optional literal length bytes,
+/// the literals themselves, the two-byte offset, and optional match length
+/// bytes. This function computes the complete size first so `OutputTooSmall`
+/// is reported without partially writing a sequence.
+fn emitSequence(
+    output: []u8,
+    op: *usize,
+    literals: []const u8,
+    offset: u16,
+    match_len: usize,
+) CompressError!void {
+    assert(match_len >= min_match);
+    assert(offset > 0);
+
+    const encoded_match_len = match_len - min_match;
+
+    // One byte is always needed for the token and two for the offset. Each
+    // length may additionally need extension bytes after its token nibble.
+    const required = 1 +
+        encodedLengthBytes(literals.len) + literals.len +
+        2 + encodedLengthBytes(encoded_match_len);
+    if (required > output.len - op.*) return error.OutputTooSmall;
+
+    const token_pos = op.*;
+    op.* += 1;
+
+    // Lengths below 15 fit directly in their nibble. Larger values put 15 in
+    // the nibble and encode the remainder immediately after the token.
+    output[token_pos] = (@as(u8, @intCast(@min(literals.len, 15))) << 4) |
+        @as(u8, @intCast(@min(encoded_match_len, 15)));
+
+    // Literal length extensions precede the literals they describe.
+    if (literals.len >= 15) writeLength(output, op, literals.len - 15);
+    @memcpy(output[op.*..][0..literals.len], literals);
+    op.* += literals.len;
+
+    // Match length extensions follow the offset because this is where the
+    // decoder expects them in an LZ4 sequence.
+    writeIntAt(u16, output, op.*, offset);
+    op.* += 2;
+    if (encoded_match_len >= 15)
+        writeLength(output, op, encoded_match_len - 15);
+}
+
+/// Emit the literal-only sequence which terminates every block.
+///
+/// There is no offset or match length after these bytes. As with
+/// `emitSequence`, capacity is checked before modifying the output.
+fn emitLastLiterals(
+    output: []u8,
+    op: *usize,
+    literals: []const u8,
+) CompressError!void {
+    const required = 1 + encodedLengthBytes(literals.len) + literals.len;
+    if (required > output.len - op.*) return error.OutputTooSmall;
+
+    output[op.*] = @as(u8, @intCast(@min(literals.len, 15))) << 4;
+    op.* += 1;
+    if (literals.len >= 15) writeLength(output, op, literals.len - 15);
+    @memcpy(output[op.*..][0..literals.len], literals);
+    op.* += literals.len;
+}
+
+/// Return the number of extension bytes needed when a length is represented by
+/// a token nibble plus zero or more bytes. An extended length always ends with
+/// a byte below 255, so an exact multiple of 255 requires a final zero byte.
+fn encodedLengthBytes(encoded_len: usize) usize {
+    if (encoded_len < 15) return 0;
+    return (encoded_len - 15) / 255 + 1;
+}
+
+/// Write the portion of a length which did not fit in the token nibble.
+///
+/// Each 255 byte means "add 255 and continue". The final byte is always less
+/// than 255 and may be zero.
+fn writeLength(output: []u8, op: *usize, length_: usize) void {
+    var length = length_;
+    while (length >= 255) {
+        output[op.*] = 255;
+        op.* += 1;
+        length -= 255;
+    }
+    output[op.*] = @intCast(length);
+    op.* += 1;
+}
+
+/// Decode a length from its token nibble and any following extension bytes.
+/// `ip` is advanced past every consumed extension byte.
+fn decodeLength(
+    input: []const u8,
+    ip: *usize,
+    nibble: usize,
+) DecompressError!usize {
+    var length: usize = nibble;
+    if (nibble != 15) return length;
+
+    while (true) {
+        if (ip.* >= input.len) return error.TruncatedInput;
+        const value = input[ip.*];
+        ip.* += 1;
+        length = std.math.add(usize, length, value) catch
+            return error.TruncatedInput;
+        if (value != 255) return length;
+    }
+}
+
+/// Read an unaligned little-endian integer at `position`.
+inline fn readIntAt(
+    comptime Int: type,
+    input: []const u8,
+    position: usize,
+) Int {
+    return std.mem.readInt(
+        Int,
+        input[position..][0..@sizeOf(Int)],
+        .little,
+    );
+}
+
+/// Write an unaligned little-endian integer at `position`.
+inline fn writeIntAt(
+    comptime Int: type,
+    output: []u8,
+    position: usize,
+    value: Int,
+) void {
+    std.mem.writeInt(
+        Int,
+        output[position..][0..@sizeOf(Int)],
+        value,
+        .little,
+    );
+}
+
+/// Copy one fixed-size integer between non-overlapping byte ranges.
+inline fn copyIntAt(
+    comptime Int: type,
+    output: []u8,
+    output_position: usize,
+    input: []const u8,
+    input_position: usize,
+) void {
+    writeIntAt(
+        Int,
+        output,
+        output_position,
+        readIntAt(Int, input, input_position),
+    );
+}
+
+/// Read the four-byte sequence used for match finding. Callers only use this
+/// where at least four input bytes remain.
+inline fn readU32(input: []const u8, pos: usize) u32 {
+    return readIntAt(u32, input, pos);
+}
+
+/// Add a position to one hash slot and shift the previous newest position into
+/// the fallback half. A position whose low bits are 0xFFFF conflicts with the
+/// sentinel and is simply not stored.
+inline fn rememberPosition(table: *HashTable, hash: usize, position: usize) void {
+    const low: u16 = @truncate(position);
+    if (low == std.math.maxInt(u16)) return;
+    table[hash] = (@as(u32, @truncate(table[hash])) << 16) | low;
+}
+
+/// Recover the nearest preceding position from a stored low half. Modular
+/// subtraction directly produces the LZ4 offset within the current window.
+inline fn candidatePosition(ip: usize, stored: u16) ?usize {
+    if (stored == std.math.maxInt(u16)) return null;
+    const distance: u16 = @as(u16, @truncate(ip)) -% stored;
+    if (distance == 0) return null;
+    return ip - distance;
+}
+
+/// Advance through a literal run. The first KiB inspects every byte without
+/// maintaining a counter, which keeps ordinary terminal-page searches cheap.
+/// Longer runs enable gradually increasing steps for incompressible data.
+inline fn advanceSearch(
+    ip: *usize,
+    anchor: usize,
+    attempts: *usize,
+) void {
+    if (attempts.* == 0) {
+        ip.* += 1;
+        if (ip.* - anchor == 1024) attempts.* = 1;
+        return;
+    }
+
+    attempts.* += 1;
+    ip.* += 1 + attempts.* / 64;
+}
+
+/// Extend a match backwards without crossing the current literal anchor or the
+/// beginning of the candidate. The returned positions preserve their offset.
+fn matchBegin(
+    input: []const u8,
+    position_: usize,
+    candidate_: usize,
+    anchor: usize,
+) struct { position: usize, candidate: usize } {
+    var position = position_;
+    var candidate = candidate_;
+
+    while (@min(position - anchor, candidate) >= @sizeOf(u64)) {
+        const position_word = position - @sizeOf(u64);
+        const candidate_word = candidate - @sizeOf(u64);
+        const difference = readIntAt(u64, input, position_word) ^
+            readIntAt(u64, input, candidate_word);
+        if (difference != 0) {
+            const equal_bytes: usize = @intCast(@clz(difference) / 8);
+            position -= equal_bytes;
+            candidate -= equal_bytes;
+            return .{ .position = position, .candidate = candidate };
+        }
+
+        position = position_word;
+        candidate = candidate_word;
+    }
+
+    while (position > anchor and candidate > 0 and
+        input[position - 1] == input[candidate - 1])
+    {
+        position -= 1;
+        candidate -= 1;
+    }
+    return .{ .position = position, .candidate = candidate };
+}
+
+/// Return the first input position where two matching runs differ, or `limit`
+/// when they remain equal. Both positions are known to have matched through
+/// `min_match` before this is called.
+fn matchEnd(
+    input: []const u8,
+    position_: usize,
+    candidate_: usize,
+    limit: usize,
+) usize {
+    var position = position_;
+    var candidate = candidate_;
+
+    // Reading as little endian makes the least-significant differing bit map
+    // to the earliest byte in memory on every target. Unaligned reads are
+    // lowered appropriately by Zig and require no target-specific intrinsics.
+    while (limit - position >= @sizeOf(u64)) {
+        const difference = readIntAt(u64, input, position) ^
+            readIntAt(u64, input, candidate);
+        if (difference != 0) {
+            const equal_bytes: usize = @intCast(@ctz(difference) / 8);
+            return position + equal_bytes;
+        }
+
+        position += @sizeOf(u64);
+        candidate += @sizeOf(u64);
+    }
+
+    while (position < limit and input[position] == input[candidate]) {
+        position += 1;
+        candidate += 1;
+    }
+    return position;
+}
+
+/// Copy one decoded match from `offset` bytes behind `op`.
+///
+/// The caller has validated that the match fits: `op + match_len` never
+/// exceeds `output.len`. Wide copies may write a few scratch bytes past the
+/// match's logical end; as described in `decompress`, that is safe anywhere
+/// the write stays inside the output buffer. Every path therefore bounds its
+/// wide stores by both the match end and the buffer end, and the bytewise
+/// loop at the bottom finishes whatever remains.
+fn copyMatch(output: []u8, op_: usize, offset: usize, match_len: usize) void {
+    var op = op_;
+    const end = op_ + match_len;
+
+    // A source which ends behind the copy can never overlap it. Long
+    // distant matches are common in structured pages (repeated rows and
+    // whole blank regions), and one exact memcpy moves them in cache-line
+    // units. Shorter matches are not worth the call overhead.
+    if (offset >= match_len and match_len >= 64) {
+        @memcpy(
+            output[op..][0..match_len],
+            output[op - offset ..][0..match_len],
+        );
+        return;
+    }
+
+    switch (offset) {
+        // A period which divides the word size expands into one repeated
+        // pattern word. Long runs (blank lines, repeated cells) then become
+        // independent stores, with no load waiting on a preceding store.
+        // Stores advance by whole words from `op`, which preserves the
+        // pattern's phase.
+        1, 2, 4, 8 => {
+            const pattern: u64 = switch (offset) {
+                1 => @as(u64, output[op - 1]) * 0x0101_0101_0101_0101,
+                2 => @as(u64, readIntAt(u16, output, op - 2)) *
+                    0x0001_0001_0001_0001,
+                4 => @as(u64, readIntAt(u32, output, op - 4)) *
+                    0x0000_0001_0000_0001,
+                8 => readIntAt(u64, output, op - 8),
+                else => unreachable,
+            };
+
+            const limit = @min(end, output.len -| 7);
+            while (op < limit) : (op += 8)
+                writeIntAt(u64, output, op, pattern);
+        },
+
+        // Wide copies are overlap-safe for the remaining offsets of at
+        // least a copy unit: each load lies a full unit behind the store
+        // which could observe it. Offsets 3, 5, 6, and 7 fall through to
+        // the bytewise loop; they are rare in real data and word tricks
+        // for them cost more in complexity than they return.
+        else => if (offset >= 16) {
+            const limit = @min(end, output.len -| 15);
+            while (op < limit) : (op += 16)
+                copyIntAt(u128, output, op, output, op - offset);
+        } else if (offset >= 8) {
+            const limit = @min(end, output.len -| 7);
+            while (op < limit) : (op += 8)
+                copyIntAt(u64, output, op, output, op - offset);
+        },
+    }
+
+    while (op < end) : (op += 1) output[op] = output[op - offset];
+}
+
+/// Map a four-byte input sequence to its scratch-table slot.
+inline fn hashSequence(sequence: u32) usize {
+    return @intCast((sequence *% hash_multiplier) >> (32 - hash_log));
+}
+
+/// Shared round-trip assertion used by the corpus-style tests below.
+fn expectRoundTrip(input: []const u8) !void {
+    const bound = try compressBound(input.len);
+    const encoded = try testing.allocator.alloc(u8, bound);
+    defer testing.allocator.free(encoded);
+    const decoded = try testing.allocator.alloc(u8, input.len);
+    defer testing.allocator.free(decoded);
+
+    var table: HashTable = undefined;
+    const encoded_len = try compress(input, encoded, &table);
+    try testing.expectEqual(input.len, try decompress(
+        encoded[0..encoded_len],
+        decoded,
+    ));
+    try testing.expectEqualSlices(u8, input, decoded);
+}
+
+test "compressBound" {
+    try testing.expectEqual(@as(usize, 16), try compressBound(0));
+    try testing.expectEqual(@as(usize, 272), try compressBound(255));
+    try testing.expectError(error.InputTooLarge, compressBound(max_input_size + 1));
+}
+
+test "literal-only compatibility vectors" {
+    var empty: [0]u8 = .{};
+    try testing.expectEqual(@as(usize, 0), try decompress(&.{0}, &empty));
+
+    var hello: [5]u8 = undefined;
+    try testing.expectEqual(@as(usize, 5), try decompress(
+        &.{ 0x50, 'h', 'e', 'l', 'l', 'o' },
+        &hello,
+    ));
+    try testing.expectEqualStrings("hello", &hello);
+
+    var fifteen: [15]u8 = undefined;
+    var encoded: [17]u8 = undefined;
+    encoded[0] = 0xF0;
+    encoded[1] = 0;
+    @memset(encoded[2..], 'x');
+    _ = try decompress(&encoded, &fifteen);
+    try testing.expect(std.mem.allEqual(u8, &fifteen, 'x'));
+}
+
+test "overlapping match compatibility vector" {
+    // One literal 'a', followed by a four-byte match at distance one.
+    var output: [5]u8 = undefined;
+    try testing.expectEqual(@as(usize, 5), try decompress(
+        &.{ 0x10, 'a', 0x01, 0x00 },
+        &output,
+    ));
+    try testing.expectEqualStrings("aaaaa", &output);
+}
+
+test "extended overlapping match compatibility vector" {
+    // One literal followed by a 274-byte match. The match extension is
+    // encoded as 255 + 0 after the low token nibble's initial 15 bytes.
+    var output: [275]u8 = undefined;
+    try testing.expectEqual(@as(usize, output.len), try decompress(
+        &.{ 0x1F, 'a', 0x01, 0x00, 0xFF, 0x00 },
+        &output,
+    ));
+    try testing.expect(std.mem.allEqual(u8, &output, 'a'));
+}
+
+test "short offset compatibility vectors" {
+
+    // These blocks end immediately after their match. Besides covering the
+    // repeating-pattern paths, they verify that the decoder uses exact copies
+    // when the block does not provide the standard trailing-literal margin.
+    var offset_two: [6]u8 = undefined;
+    _ = try decompress(&.{ 0x20, 'a', 'b', 0x02, 0x00 }, &offset_two);
+    try testing.expectEqualStrings("ababab", &offset_two);
+
+    var offset_three: [9]u8 = undefined;
+    _ = try decompress(
+        &.{ 0x32, 'a', 'b', 'c', 0x03, 0x00 },
+        &offset_three,
+    );
+    try testing.expectEqualStrings("abcabcabc", &offset_three);
+
+    var offset_four: [8]u8 = undefined;
+    _ = try decompress(
+        &.{ 0x40, 'a', 'b', 'c', 'd', 0x04, 0x00 },
+        &offset_four,
+    );
+    try testing.expectEqualStrings("abcdabcd", &offset_four);
+}
+
+test "bounded wild copies are overwritten by final literals" {
+
+    // The first sequence's nine-byte match leaves the five final literals
+    // required by the LZ4 block format. Its logical one-byte tail is copied as
+    // a word and the following literal sequence overwrites the extra bytes.
+    var repeated_byte: [15]u8 = undefined;
+    _ = try decompress(
+        &.{
+            0x15, 'a', 0x01, 0x00,
+            0x50, '1', '2',  '3',
+            '4',  '5',
+        },
+        &repeated_byte,
+    );
+    try testing.expectEqualStrings("aaaaaaaaaa12345", &repeated_byte);
+
+    // Exercise the same bounded tail copy with a non-overlapping offset.
+    var word_offset: [22]u8 = undefined;
+    _ = try decompress(
+        &.{
+            0x85, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 0x08, 0x00,
+            0x50, '1', '2', '3', '4', '5',
+        },
+        &word_offset,
+    );
+    try testing.expectEqualStrings(
+        "abcdefghabcdefgha12345",
+        &word_offset,
+    );
+}
+
+test "maximum match offset compatibility vector" {
+    const literal_len = std.math.maxInt(u16);
+    const extension_len = (literal_len - 15) / 255 + 1;
+    const encoded = try testing.allocator.alloc(
+        u8,
+        1 + extension_len + literal_len + 2,
+    );
+    defer testing.allocator.free(encoded);
+    const output = try testing.allocator.alloc(u8, literal_len + min_match);
+    defer testing.allocator.free(output);
+
+    var op: usize = 0;
+    encoded[op] = 0xF0;
+    op += 1;
+    writeLength(encoded, &op, literal_len - 15);
+    for (encoded[op..][0..literal_len], 0..) |*byte, i|
+        byte.* = @truncate(i);
+    op += literal_len;
+    std.mem.writeInt(u16, encoded[op..][0..2], std.math.maxInt(u16), .little);
+    op += 2;
+
+    try testing.expectEqual(encoded.len, op);
+    try testing.expectEqual(output.len, try decompress(encoded, output));
+    try testing.expectEqualSlices(u8, encoded[1 + extension_len ..][0..4], output[literal_len..]);
+}
+
+test "round trips boundary-sized inputs" {
+    const lengths = [_]usize{
+        0,   1,      3,      4,      5,   12,  15,  16,  19,
+        20,  254,    255,    256,    269, 270, 271, 510, 511,
+        512, 65_535, 65_536, 65_537,
+    };
+
+    for (lengths) |len| {
+        const buf = try testing.allocator.alloc(u8, len);
+        defer testing.allocator.free(buf);
+        for (buf, 0..) |*byte, i| byte.* = @truncate(i *% 31);
+        try expectRoundTrip(buf);
+    }
+}
+
+test "round trips compressible page-sized inputs" {
+    const page_len = 400 * 1024;
+
+    const zeros = try testing.allocator.alloc(u8, page_len);
+    defer testing.allocator.free(zeros);
+    @memset(zeros, 0);
+    try expectRoundTrip(zeros);
+
+    const structured = try testing.allocator.alloc(u8, page_len);
+    defer testing.allocator.free(structured);
+    @memset(structured, 0);
+    for (0..page_len / 8) |i| {
+        structured[i * 8] = @truncate(' ' + i % 95);
+        structured[i * 8 + 4] = @truncate((i / 80) % 16);
+    }
+    try expectRoundTrip(structured);
+}
+
+test "round trips deterministic random inputs" {
+    var prng = std.Random.DefaultPrng.init(0x4C5A_3401);
+    const random = prng.random();
+
+    for (0..256) |_| {
+        const len = random.uintLessThan(usize, 32 * 1024);
+        const input = try testing.allocator.alloc(u8, len);
+        defer testing.allocator.free(input);
+        random.bytes(input);
+        try expectRoundTrip(input);
+    }
+}
+
+test "compress reports short output" {
+    const input = "a terminal page needs enough output space";
+    var table: HashTable = undefined;
+    var output: [4]u8 = undefined;
+    try testing.expectError(
+        error.OutputTooSmall,
+        compress(input, &output, &table),
+    );
+}
+
+test "decompress rejects malformed blocks" {
+    var output: [32]u8 = undefined;
+
+    try testing.expectError(error.TruncatedInput, decompress(&.{0xF0}, &output));
+    try testing.expectError(error.TruncatedInput, decompress(&.{ 0x10, 'a', 1 }, output[0..5]));
+    try testing.expectError(error.InvalidOffset, decompress(&.{ 0x10, 'a', 0, 0 }, output[0..5]));
+    try testing.expectError(error.InvalidOffset, decompress(&.{ 0x10, 'a', 2, 0 }, output[0..5]));
+    try testing.expectError(error.OutputTooSmall, decompress(
+        &.{ 0x10, 'a', 1, 0 },
+        output[0..4],
+    ));
+    try testing.expectError(error.OutputSizeMismatch, decompress(&.{0}, output[0..1]));
+}
+
+test {
+    _ = @import("lz4_differential.zig");
+}
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);
+}