aboutsummaryrefslogtreecommitdiff
path: root/vendor/libghostty-vt/src/terminal/compress/lz4.zig
diff options
context:
space:
mode:
authorOgulcan Celik <ogulcancelik@gmail.com>2026-07-16 23:28:05 +0300
committerOgulcan Celik <ogulcancelik@gmail.com>2026-07-16 23:29:28 +0300
commit4a3302d19a2baa3a33e910e0088c24e780905b90 (patch)
treedcaf76fae1c82102d933c9225b17ca7ac5d3a847 /vendor/libghostty-vt/src/terminal/compress/lz4.zig
parent550e9f8cc085f428429f5cf2da0bb2dba897e8b8 (diff)
chore: update vendored libghostty-vt
refs #276
Diffstat (limited to 'vendor/libghostty-vt/src/terminal/compress/lz4.zig')
-rw-r--r--vendor/libghostty-vt/src/terminal/compress/lz4.zig891
1 files changed, 891 insertions, 0 deletions
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");
+}