Not on the frontier · 0.592 α of 3,600 α earned
Gate
Where it sits
Standing
Scoring limits
Admission
The lower confidence bound is above zero: the speed improvement passed.
Speed test
Estimate 1.24% · Lower bound 1.08% · needs to stay above 0.00% · 90% interval · 56 files across corpus-stage1, corpus-stage2
This submission
Reference: 5GEDaN…y2nucH
The frontier it was judged against
Source
// Bounded suffix search with reduced generic primary probes; original modeled byte-difference helper, classifiers and trusted emitters retained.
// Generic compression-budget research from hash-verified released #567; original classifiers and routing predicates retained.
//! mA: a content-adaptive LZ77 parser for the fixed DEFLATE encoder (mid speed band).
//!
//! Lineage: fastX fx17 (fast band, Package 2 base) with per-class settings and four search additions.
//! * Content class from a small strided byte histogram: DNA-like inputs (0), text (1), peaky
//! high-entropy binaries such as 16-bit weights (2), other binaries (3), zero-rich high-entropy
//! data (4), prose (5), structured text with many digits (6) and flat high-entropy data without a
//! dominant byte value such as images or compressed streams (7). Every class has its own main walk
//! depth, lazy walk depth, lazy threshold, walk stop length, skip shift and insertion pattern.
//! * Search: hash chains keyed by the first 4 bytes (3 bytes for classes 3 and 7, 8 bytes for DNA),
//! a main walk and a lazy walk, both with a one-byte quick reject. The main walk (MAIN_GM) and the
//! lazy walks rank candidates by an estimated bit saving (a longer candidate must also save more).
//! * Lazy step: move to p+1 while it has a better candidate; when p+1 does not win, p+2 is tried
//! once (LAZY2) and wins if its saving exceeds the pending one by more than L2B/16 bits.
//! * Every new match first extends backwards over the tokens just written: literals that match
//! at its distance, and whole earlier matches whose bytes also match there, are folded into it.
//! Optionally (PARTIAL) a previous match whose tail the new match also covers is shortened
//! when a closer source covers the shorter length.
//! * DNA-like input: 8-byte chain keys and a 9-byte minimum match (run_dna).
//! * Skip acceleration through stretches without matches (capped for zero-rich data).
//! * Tables are sized by the input: small inputs clear and touch less memory.
//! * Emission optionally re-checks each match (VERIFY = 1); a failed check writes a literal.
//!
//! Tokens: t < 256 literal, else 2^24 + (dist-1)*256 + (len-3).
pub const HB: u32 = 16;
pub const HN: usize = 65536;
pub const WN: usize = 32768;
/// Inputs of at most SMALL bytes use HS chain heads and a WS window table.
pub const SMALL: usize = 65536;
pub const HS: usize = 8192;
pub const WS: usize = 16384;
pub const NICE: usize = 128;
pub const INS_MAX: usize = 16;
pub const TAIL: usize = 4;
/// Inside long matches, every STRIDE-th position between the head and the tail is chained
/// too (STRIDE = 0: none).
pub const STRIDE: usize = 4;
pub const BACKTOK: usize = 16;
pub const LDEPTH: usize = 1;
pub const SAMPLE: usize = 2048;
pub const VERIFY: usize = 0;
/// Lazy step: a candidate at p+1 needs length >= l + 1 - LSLACK (LSLACK = 1: at least as long
/// as the current match l) and must win on estimated saving (literal worth HLIT/16 bits,
/// match base cost GBASE/16 bits plus extra bits).
pub const LSLACK: usize = 1;
pub const HLIT: u32 = 64;
/// Literal worth (1/16 bit) in the saving estimate for binary classes (3 and 7).
pub const B_HLIT: u32 = 64;
pub const GBASE: i32 = 168;
/// Per class: main chain depth, lazy threshold, skip shift, skip cap (T text, P prose,
/// H high-entropy binary, Z high-entropy binary rich in zero bytes, B other binary,
/// DNA-like input is sent as literals).
pub const T_DEPTH: usize = 4;
pub const T_LAZY: usize = 128;
pub const T_SKIP: usize = 5;
pub const P_DEPTH: usize = 8;
pub const P_LAZY: usize = 258;
pub const P_SKIP: usize = 5;
pub const H_DEPTH: usize = 1;
pub const H_LAZY: usize = 0;
pub const H_SKIP: usize = 2;
pub const Z_DEPTH: usize = 3;
pub const Z_SKIP: usize = 6;
pub const Z_CAP: usize = 8;
pub const M_B_DEPTH: usize = 4;
pub const M_B_LAZY: usize = 258;
pub const B_SKIP: usize = 8;
/// Structured text (class 6: text with at least 1/SDIG of the sample in digits): main depth
/// S_DEPTH, lazy walk depth S_LDEPTH, lazy threshold S_LAZY.
pub const SDIG: u32 = 6;
pub const S_DEPTH: usize = 1;
pub const S_LDEPTH: usize = 3;
pub const S_LAZY: usize = 258;
/// Largest skip step (extra literals per miss) outside the Z class.
pub const SKCAP: usize = 1000000;
/// Per-class walk stop (NICE is the text value), lazy walk depth (LDEPTH is the text value),
/// insertion inside matches (INS_MAX/STRIDE/TAIL are the text values).
pub const P_NICE: usize = 258;
pub const S_NICE: usize = 258;
pub const H_NICE: usize = 32;
pub const Z_NICE: usize = 32;
pub const M_B_NICE: usize = 258;
pub const P_LDEPTH: usize = 1;
pub const H_LDEPTH: usize = 1;
pub const B_LDEPTH: usize = 2;
pub const P_INS: usize = 258;
pub const S_INS: usize = 8;
pub const B_INS: usize = 12;
pub const H_INS: usize = 12;
pub const P_STRIDE: usize = 1;
pub const S_STRIDE: usize = 8;
pub const B_STRIDE: usize = 32;
/// Two-step lazy: when p+1 does not beat the pending match, p+2 is tried (L2DEPTH chain steps)
/// and wins if its saving beats the pending one by more than L2B/16 bits (LAZY2 = 1; 0 = off).
pub const LAZY2: usize = 0;
pub const L2B: i32 = 40;
pub const L2DEPTH: usize = 1;
/// Main walk in gain mode (a longer candidate must also save more).
pub const MAIN_GM: usize = 0;
/// Partial merge: when the new match also covers the last k bytes of the previous match (but not
/// all of it), the previous match is shortened by k if a closer source (at most PDEPTH chain steps)
/// covers its shorter length; the new match then starts k bytes earlier (0 = off).
pub const PARTIAL: usize = 0;
pub const PDEPTH: usize = 8;
/// Class 7: high-entropy input without a dominant byte (no byte above 1/FLAT_DIV of the sample:
/// compressed data, images) parsed with 3-byte keys (F_ settings); class 2 keeps the peaky ones
/// (16-bit weights).
pub const FLAT_ON: usize = 1;
pub const FLAT_DIV: u32 = 16;
/// ... and whose byte collision rate (sum of squared sample counts * 256 / samples^2) is below
/// FLAT_SQ/16 (uniform data: 1; images and compressed streams: 1.1-1.4; 8-bit weights: 1.8).
pub const FLAT_SQ: u64 = 256;
pub const F_DEPTH: usize = 8;
pub const F_LAZY: usize = 0;
pub const F_LDEPTH: usize = 2;
pub const F_SKIP: usize = 6;
pub const H_STRIDE: usize = 32;
/// Eight bytes at `i`, first byte most significant (0 when out of range).
#[inline(always)]
pub fn be8(s: &[u8], i: usize) -> u64 {
if i + 8 <= s.len() {
((s[i] as u64) << 56)
| ((s[i + 1] as u64) << 48)
| ((s[i + 2] as u64) << 40)
| ((s[i + 3] as u64) << 32)
| ((s[i + 4] as u64) << 24)
| ((s[i + 5] as u64) << 16)
| ((s[i + 6] as u64) << 8)
| (s[i + 7] as u64)
} else {
0
}
}
/// Four bytes at `i`, first byte most significant (0 when out of range).
#[inline(always)]
pub fn be4(s: &[u8], i: usize) -> u32 {
if i + 4 <= s.len() {
((s[i] as u32) << 24) | ((s[i + 1] as u32) << 16) | ((s[i + 2] as u32) << 8) | (s[i + 3] as u32)
} else {
0
}
}
/// Input class from a strided byte histogram of at most ~SAMPLE bytes:
/// 0 DNA-like, 1 text, 2 high-entropy binary, 3 other binary, 4 high-entropy with zeros,
/// 5 prose (text of letters and spaces with almost no code symbols), 6 structured text (many
/// digits: tables, logs, dumps).
pub fn sniff(s: &[u8]) -> usize {
let n = s.len();
let mut cnt = [0u32; 256];
let step = (n / SAMPLE) | 1;
let mut i = 0usize;
let mut tot = 0u32;
// `tot < 4097` always holds here (at most 4096 samples); with it the loop is total even
// for a slice of usize::MAX bytes, where `i + step` could overflow.
while i < n && tot < 4097 {
cnt[s[i] as usize % 256] += 1;
tot += 1;
i = i.wrapping_add(step);
}
let dna = cnt[65] + cnt[67] + cnt[71] + cnt[84] + cnt[97] + cnt[99] + cnt[103] + cnt[116] + cnt[78] + cnt[110] + cnt[10];
let mut text = cnt[9] + cnt[10] + cnt[13];
let mut high = 0u32;
let mut words = cnt[32];
let mut b = 32usize;
while b < 256 {
if b != 127 {
text += cnt[b];
}
if b >= 128 {
high += cnt[b];
}
if (b >= 65 && b <= 90) || (b >= 97 && b <= 122) {
words += cnt[b];
}
b += 1;
}
let syms = cnt[35] + cnt[36] + cnt[37] + cnt[38] + cnt[40] + cnt[41] + cnt[42] + cnt[43] + cnt[47] + cnt[59] + cnt[60] + cnt[61] + cnt[62] + cnt[64] + cnt[91] + cnt[92] + cnt[93] + cnt[94] + cnt[95] + cnt[96] + cnt[123] + cnt[124] + cnt[125] + cnt[126];
let mut cls = 3usize;
if tot > 0 && dna >= tot - tot / 10 {
cls = 0;
} else if text >= tot - tot / 100 && cnt[0] == 0 {
cls = 1;
let digits = cnt[48] + cnt[49] + cnt[50] + cnt[51] + cnt[52] + cnt[53] + cnt[54] + cnt[55] + cnt[56] + cnt[57];
if words >= tot - tot / 7 && syms <= tot / 64 {
cls = 5;
} else if digits >= tot / SDIG {
cls = 6;
}
} else if high >= tot / 3 {
cls = 2;
if cnt[0] >= tot / 20 {
cls = 4;
} else if FLAT_ON == 1 {
let mut mx = 0u32;
let mut sq = 0u64;
let mut b2 = 0usize;
while b2 < 256 {
let c2 = cnt[b2] as u64;
if cnt[b2] > mx {
mx = cnt[b2];
}
sq = sq.wrapping_add(c2.wrapping_mul(c2));
b2 += 1;
}
let t2 = (tot as u64).wrapping_mul(tot as u64);
if mx < tot / FLAT_DIV && sq.wrapping_mul(256) < t2.wrapping_mul(FLAT_SQ) / 16 {
cls = 7;
}
}
}
cls
}
/// Estimated saving (1/16 bit) of a match of length `l` at distance `d` over literals.
#[inline(always)]
pub fn gain(l: usize, d: usize, hlit: i32) -> i32 {
let mut c = GBASE;
if l > 10 && l < 258 {
c += 16 * (29 - ((l - 3) as u32).leading_zeros()) as i32;
}
if d > 4 {
c += 16 * (30 - ((d - 1) as u32).leading_zeros()) as i32;
}
(l as i32) * hlit - c
}
/// Length of the common prefix of s[a..] and s[b..], at most `cap`.
#[inline(always)]
pub fn common(s: &[u8], a: usize, b: usize, cap: usize) -> usize {
let mut k = 0usize;
let mut run = 1u32;
while run == 1 && k + 8 <= cap {
let x = be8(s, a + k) ^ be8(s, b + k);
if x == 0 {
k += 8;
} else {
k += (x.leading_zeros() / 8) as usize;
run = 0;
}
}
while run == 1 && k < cap {
if s[a + k] == s[b + k] {
k += 1;
} else {
run = 0;
}
}
k
}
/// 1 when s[a..a+len] == s[b..b+len]: eight bytes at a time, the last partial word
/// under a mask when a full load fits, else byte by byte.
#[inline(always)]
pub fn same(s: &[u8], a: usize, b: usize, len: usize) -> usize {
let n = s.len();
let mut k = 0usize;
let mut ok = 1usize;
while ok == 1 && k + 8 <= len {
if be8(s, a + k) == be8(s, b + k) {
k += 8;
} else {
ok = 0;
}
}
if ok == 1 && k < len {
if a + k + 8 <= n && b + k + 8 <= n {
let x = be8(s, a + k) ^ be8(s, b + k);
if (x >> (64 - 8 * (len - k) as u32)) != 0 {
ok = 0;
}
} else {
while ok == 1 && k < len {
if s[a + k] == s[b + k] {
k += 1;
} else {
ok = 0;
}
}
}
}
ok
}
#[inline(always)]
pub fn put_lit(s: &[u8], out: &mut [u32], nt: usize, p: usize) -> usize {
out[nt] = s[p] as u32;
nt + 1
}
/// Emit a match (re-checked when VERIFY = 1), else a literal. Returns (tokens, next position).
#[inline(always)]
pub fn put_match(s: &[u8], out: &mut [u32], nt: usize, p: usize, d: usize, l: usize) -> (usize, usize) {
let n = s.len();
if d >= 1 && d <= 32768 && d <= p && l >= 3 && l <= 258 && p < n && l <= n - p && (VERIFY == 0 || same(s, p - d, p, l) == 1) {
out[nt] = 16777216u32 + ((d - 1) as u32) * 256 + ((l - 3) as u32);
(nt + 1, p + l)
} else {
out[nt] = s[p] as u32;
(nt + 1, p + 1)
}
}
/// Walk the chain from `start`: the longest match at `p` longer than `have` (with `gm` = 1,
/// a longer candidate must also have a higher estimated saving); distance 0 = none found.
/// Each candidate first compares the byte at `best`.
#[inline(always)]
pub fn walk<const W: usize>(s: &[u8], prev: &[u32; W], p: usize, start: usize, cap: usize, have: usize, depth: usize, nice: usize, gm: usize, hlit: i32) -> (usize, usize) {
let n = s.len();
let mut best = have;
let mut bd = 0usize;
let mut bg = -1000000i32;
let mut c = start;
let mut k = depth;
let mut stop = nice;
if stop > cap {
stop = cap;
}
let mut pb = 0u8;
if p + best < n {
pb = s[p + best];
}
while k > 0 {
let d = p.wrapping_sub(c);
if d.wrapping_sub(1) < 32768 && c + best < n {
if s[c + best] == pb {
let l = common(s, c, p, cap);
let mut take = 0usize;
if l > best {
take = 1;
if gm == 1 {
let g = gain(l, d, hlit);
if g > bg {
bg = g;
} else {
take = 0;
}
}
}
if take == 1 {
best = l;
bd = d;
if l >= stop || p + l >= n {
k = 1;
} else {
pb = s[p + l];
}
}
}
let nx = prev[c % W] as usize;
if nx < c {
c = nx;
k -= 1;
} else {
k = 0;
}
} else {
k = 0;
}
}
(best, bd)
}
/// Put position `i` at the head of its chain (key = first four bytes under `mask`);
/// returns the previous head.
#[inline(always)]
pub fn insert<const H: usize, const W: usize>(s: &[u8], head: &mut [u32; H], prev: &mut [u32; W], i: usize, mask: u32) -> usize {
let k = (be4(s, i) & mask) as u64;
let a = (k.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> (64 - HB)) as usize % H;
let old = head[a];
prev[i % W] = old;
head[a] = i as u32;
old as usize
}
/// Distance of the first chain entry from `start` (at most `depth` steps) whose next `len` bytes
/// equal those at `p` (0 = none).
#[inline(always)]
pub fn closest<const W: usize>(s: &[u8], prev: &[u32; W], p: usize, start: usize, len: usize, depth: usize) -> usize {
let n = s.len();
let mut c = start;
let mut k = depth;
let mut res = 0usize;
while k > 0 {
let d = p.wrapping_sub(c);
if d.wrapping_sub(1) < 32768 && len >= 1 && c < p && p + len <= n {
if s[c + len - 1] == s[p + len - 1] && same(s, c, p, len) == 1 {
res = d;
k = 0;
} else {
let nx = prev[c % W] as usize;
if nx < c {
c = nx;
k -= 1;
} else {
k = 0;
}
}
} else {
k = 0;
}
}
res
}
/// Partial merge (PARTIAL = 1): the new match `(l0, d)` at `p0` also covers the last `k` bytes of
/// the previous match token `t` (`w` bytes, ending at `p0`), but not all of it. When a closer
/// source (at most PDEPTH chain steps) covers its first `w - k` bytes, that token is shortened by
/// `k` and the new match starts `k` bytes earlier. Returns the new `(p, l)`.
#[inline(always)]
pub fn part_merge<const W: usize>(input: &[u8], out: &mut [u32], prev: &[u32; W], nt: usize, p0: usize, l0: usize, d: usize, t: u32, w: usize) -> (usize, usize) {
let mut p = p0;
let mut l = l0;
if PARTIAL == 1 && w > 4 && w <= p {
let mut k = 0usize;
while k + 4 < w && l + k < 258 && d + k < p && input[p - 1 - k] == input[p - 1 - k - d] {
k += 1;
}
let pd = ((t - 16777216) / 256 + 1) as usize;
if k > 0 {
let pp = p - w;
let nl = w - k;
let c = closest(input, prev, pp, prev[pp % W] as usize, nl, PDEPTH);
if c > 0 && c < pd && c <= pp && nl >= 3 && nl <= 258 {
out[nt - 1] = 16777216u32 + ((c - 1) as u32) * 256 + ((nl - 3) as u32);
p -= k;
l += k;
}
}
}
(p, l)
}
/// Best match at `p` longer than `have` and at least `minl` long; (0, 0) when none.
#[inline(always)]
pub fn find<const W: usize>(s: &[u8], prev: &[u32; W], p: usize, st: usize, have: usize, minl: usize, depth: usize, nice: usize, gm: usize, hlit: i32) -> (usize, usize) {
let n = s.len();
let mut cap = n - p;
if cap > 258 {
cap = 258;
}
let mut lo = have;
if lo + 1 < minl {
lo = minl - 1;
}
let f = walk(s, prev, p, st, cap, lo, depth, nice, gm, hlit);
let mut l = f.0;
if f.1 == 0 {
l = 0;
}
(l, f.1)
}
/// The parse for one input class (inlined so the text classes get constant settings), with
/// H chain heads and a window table of W entries.
#[inline(always)]
pub fn run<const H: usize, const W: usize, const MASK: u32, const MINL: usize,
const DEPTH: usize, const LAZY: usize, const SKIP: usize, const CAP: usize,
const STOP: usize, const LD: usize, const INS: usize, const STR: usize, const LIT: i32, const L2: usize>
(input: &[u8], out: &mut [u32]) -> usize {
let n = input.len();
let mut nt = 0usize;
let mut p = 0usize;
let mask = MASK;
let minl = MINL;
let depth = DEPTH;
let lazy = LAZY;
let skip = SKIP;
let skcap = CAP;
let nice = STOP;
let ldep = LD;
let insm = INS;
let stride = STR;
let hlit = LIT;
if n > 16 {
let mut head = [0u32; H];
let mut prev = [0u32; W];
let lim = n - 8;
let mut ins = 0usize; // next position to insert
let mut miss = 0usize; // literals since the last match
let mut fuel = n.saturating_add(16); // every pass advances p unless a re-check fails
while p < lim && fuel > 0 {
fuel -= 1;
while ins < p {
insert(input, &mut head, &mut prev, ins, mask);
ins += 1;
}
// `ins == p` here (a match leaves `ins = end = p`, literals leave `ins = p`)
let hc = insert(input, &mut head, &mut prev, p, mask);
ins = p + 1;
let f = find(input, &prev, p, hc, 0, minl, depth, nice, MAIN_GM, hlit);
let mut l = f.0;
let mut d = f.1;
if l >= 3 {
// Lazy: move on while the next position has a better match by the saving
// estimate (it may be as long but closer, or longer).import Lz77
import Slot
namespace Submission
open Aeneas Aeneas.Std Result ControlFlow
open LZ77 (toks bytes)
set_option maxRecDepth 8192
set_option hygiene false in
local notation "T1!" => (by
have h := Nat.two_pow_add_eq_or_of_lt ht (x / 2 ^ m)
have hx' : 2 ^ m * (x / 2 ^ m) = x := by
have := Nat.div_add_mod x (2 ^ m); omega
rw [hx'] at h
exact h.symm)
set_option hygiene false in
local notation "T2!" => (by
rw [Nat.shiftLeft_eq, U64.size_def]
apply Nat.mod_eq_of_lt
have : 2 ^ k ≤ 2 ^ 56 := Nat.pow_le_pow_right (by norm_num) hk
have : x * 2 ^ k < 256 * 2 ^ 56 := by
calc x * 2 ^ k < 256 * 2 ^ k := by
apply Nat.mul_lt_mul_of_pos_right hx (Nat.two_pow_pos _)
_ ≤ 256 * 2 ^ 56 := Nat.mul_le_mul_left _ this
simp only [U64.numBits] at *
omega)
set_option hygiene false in
local notation "T3!" => (by
have : a ^^^ (a ^^^ b) = b := by rw [← Nat.xor_assoc, Nat.xor_self, Nat.zero_xor]
rw [h, Nat.xor_zero] at this; exact this)
set_option hygiene false in
local notation "T4!" => (by
unfold BitVec.leadingZeros
split
case isTrue h => subst h; simp
case isFalse h =>
have hz : z.toNat ≠ 0 := by
intro h0; apply h; exact BitVec.eq_of_toNat_eq (by simpa using h0)
have hlog : Nat.log 2 z.toNat < 64 := Nat.log_lt_of_lt_pow hz z.isLt
have h1 : z.toNat < 2 ^ (Nat.log 2 z.toNat).succ := Nat.lt_pow_succ_log_self (by norm_num) _
refine lt_of_lt_of_le h1 (Nat.pow_le_pow_right (by norm_num) ?_)
omega)
set_option hygiene false in
local notation "T5!" => (by
simp only [lift, Std.WP.spec_ok, true_and]
have hle : BitVec.leadingZeros x.bv ≤ 64 := by unfold BitVec.leadingZeros; split <;> omega
simp only [core.num.U64.leading_zeros, UScalar.val, UScalarTy.U32_numBits_eq,
BitVec.natCast_eq_ofNat, BitVec.toNat_ofNat, Nat.reducePow]
omega)
set_option hygiene false in
local notation "T6!" => (by
have hle : BitVec.leadingZeros x.bv ≤ 64 := by unfold BitVec.leadingZeros; split <;> omega
simp only [core.num.U64.leading_zeros, UScalar.val, UScalarTy.U32_numBits_eq,
BitVec.natCast_eq_ofNat, BitVec.toNat_ofNat, Nat.reducePow]
omega)
set_option hygiene false in
local notation "T7!" => (by
rw [hl1]
apply LZ77.Matches.succ h
rw [← hpa, ← hpb, getElem!_pos input.val pa.val hpa', getElem!_pos input.val pb.val hpb',
← hx, ← hy, hxy])
set_option hygiene false in
local notation "T9!" => (by
have hne : x.bv ≠ 0 := by
intro h0
have : x.val = 0 := by simp [UScalar.val, h0]
have : 0 < 2 ^ k := Nat.two_pow_pos k
omega
have hlog : k ≤ Nat.log 2 x.bv.toNat := by
apply Nat.le_log_of_pow_le (by norm_num)
have : x.val = x.bv.toNat := rfl
omega
have hle : BitVec.leadingZeros x.bv ≤ 32 := by unfold BitVec.leadingZeros; split <;> omega
have hv : (core.num.U32.leading_zeros x).val = BitVec.leadingZeros x.bv := by
simp only [core.num.U32.leading_zeros, UScalar.val, UScalarTy.U32_numBits_eq,
BitVec.natCast_eq_ofNat, BitVec.toNat_ofNat, Nat.reducePow]
omega
rw [hv]
unfold BitVec.leadingZeros
simp only [hne, if_false]
omega)
set_option hygiene false in
local notation "T10!" => (by
subst hi
refine ⟨Int.mul_nonneg (by omega) h0, ?_⟩
calc (l : Int) * hlit ≤ 258 * hlit := Int.mul_le_mul_of_nonneg_right (by omega) h0
_ ≤ 258000000 := by omega)
set_option hygiene false in
local notation "T11!" => (by
intro j hj
rw [Std.Array.repeat_val] at hj ⊢
rw [List.getElem!_eq_getElem?_getD, List.getElem?_replicate_of_lt (by simpa using hj)]
rfl)
set_option hygiene false in
local notation "T12!" => (by
intro j hj
rw [Std.Array.set_val_eq] at hj ⊢
rw [List.length_set] at hj
by_cases hja : a.val = j
· subst hja
rw [List.getElem!_eq_getElem?_getD, List.getElem?_set_self hj]
exact hv
· rw [List.getElem!_eq_getElem?_getD, List.getElem?_set_ne hja, ← List.getElem!_eq_getElem?_getD]
exact h j hj)
set_option hygiene false in
local notation "T14!" => (by
have hsz : 4294967296 ≤ Usize.size := by scalar_tac
have hpl : p.val < Usize.size := by scalar_tac
have hdv : d.val = p.val - c.val := by
rw [hd, core.num.Usize.wrapping_sub_val_eq, UScalar.size_UScalarTyUsize]
rw [show p.val + (Usize.size - c.val) = (p.val - c.val) + Usize.size by omega,
Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]
have hiv : i.val < 32768 := by scalar_tac
have hdl : d.val < Usize.size := by omega
rw [hi, core.num.Usize.wrapping_sub_val_eq, UScalar.size_UScalarTyUsize] at hiv
simp only [show (1#usize).val = 1 by simp] at hiv
refine ⟨hdv, ?_, ?_⟩
· by_contra h0
have : d.val = 0 := by omega
rw [this, Nat.zero_add, Nat.mod_eq_of_lt (by omega)] at hiv
omega
· by_cases h0 : d.val = 0
· rw [h0, Nat.zero_add, Nat.mod_eq_of_lt (by omega)] at hiv
omega
· rw [show d.val + (Usize.size - 1) = (d.val - 1) + Usize.size by omega, Nat.add_mod_right,
Nat.mod_eq_of_lt (by omega)] at hiv
omega)
set_option hygiene false in
local notation "T15!" => (by
by_contra hcp
have hsz : 4294967296 ≤ Usize.size := by scalar_tac
have hcl : c.val < Usize.size := by scalar_tac
have hdv : d.val = Usize.size - (c.val - p.val) := by
rw [hd, core.num.Usize.wrapping_sub_val_eq, UScalar.size_UScalarTyUsize]
rw [show p.val + (Usize.size - c.val) = Usize.size - (c.val - p.val) by omega,
Nat.mod_eq_of_lt (by omega)]
have hiv : i.val < 32768 := by scalar_tac
rw [hi, core.num.Usize.wrapping_sub_val_eq, UScalar.size_UScalarTyUsize] at hiv
simp only [show (1#usize).val = 1 by simp] at hiv
rw [show d.val + (Usize.size - 1) = (d.val - 1) + Usize.size by omega, Nat.add_mod_right,
Nat.mod_eq_of_lt (by omega)] at hiv
omega)
set_option hygiene false in
local notation "T16!" => (by
have hd' : d.val ≠ 0 := by intro h; apply hd; exact UScalar.eq_of_val_eq (by simp [h])
rcases hc with h0 | ⟨_, _, _, hl, _⟩
· exact absurd h0 hd'
· omega)
set_option hygiene false in
local notation "T17!" => (by
intro n
induction n with
| zero => simp [copyN]
| succ m ih =>
simp only [copyN]
rw [List.take_append_of_le_length (by simp)]
exact ih)
set_option hygiene false in
local notation "T18!" => (by
intro ts
induction ts with
| nil => intro init acc h; simp at h; subst h; simp
| cons t ts ih =>
intro init acc h
simp only [List.foldlM_cons] at h
cases he : emit init t with
| none => rw [he] at h; simp at h
| some a =>
rw [he] at h
simp only [Option.bind_eq_bind, Option.bind_some] at h
have h1 := ih a acc h
have h2 : init.length + 1 ≤ a.length := by
simp only [emit] at he
split at he
· simp at he; subst he; simp
· split at he
· split at he
· simp at he; subst he; rw [copyN_length]; simp only [tokLen]; omega
· simp at he
· simp at he
simp only [List.length_cons]
omega)
set_option hygiene false in
local notation "T19!" => (by
rw [decode_snoc] at hd
cases hts : decode ts with
| none => rw [hts] at hd; simp at hd
| some acc =>
rw [hts] at hd
simp only [Option.bind_some, emit, if_pos ht] at hd
have hacc : acc ++ [t] = inp.take p := Option.some.inj hd
have hlen : acc.length + 1 = p := by
have := congrArg List.length hacc
simp [List.length_take] at this; omega
refine ⟨by omega, ?_⟩
apply congrArg some
have := congrArg (List.take acc.length) hacc
rw [List.take_append_of_le_length (le_refl _), List.take_length, List.take_take] at this
rw [this, show min acc.length p = p - 1 by omega])
set_option hygiene false in
local notation "T20!" => (by
rw [decode_snoc] at hd
cases hts : decode ts with
| none => rw [hts] at hd; simp at hd
| some acc =>
rw [hts] at hd
simp only [Option.bind_some, emit, if_neg (show ¬ t < 256 by omega)] at hd
split at hd
· split at hd
· have hacc : copyN acc (tokDist t) (tokLen t) = inp.take p := Option.some.inj hd
have hlen : acc.length + tokLen t = p := by
have := congrArg List.length hacc
simp [List.length_take] at this; omega
refine ⟨by omega, ?_⟩
apply congrArg some
have := congrArg (List.take acc.length) hacc
rw [copyN_take_prefix, List.take_take] at this
rw [this, show min acc.length p = p - tokLen t by omega]
· simp at hd
· simp at hd)
set_option hygiene false in
local notation "T21!" => (by
have hlt : nt - 1 < out.val.length := by
have : out.length = out.val.length := rfl
omega
simp only [toks]
conv_lhs => rw [show nt = (nt - 1) + 1 by omega]
rw [List.take_add_one, List.getElem?_eq_getElem hlt, Option.toList_some, List.map_append]
simp [getElem!_pos out.val (nt - 1) hlt])
set_option hygiene false in
local notation "T22!" => (by
simp only [toks, List.length_map, List.length_take]
have : out.length = out.val.length := rfl
omega)
set_option hygiene false in
local notation "T23!" => (by
obtain ⟨hps, hntp, hso, hde⟩ := h
have hntl : ntU.val < out.length := by omega
refine ⟨by omega, by omega, by rw [Std.Slice.set_length]; exact hso, ?_⟩
rw [← hnt]
refine emit_lit s out ntU p v (by rw [hnt]; exact hde) hp hntl ?_
have hpl : p < s.val.length := hp
rw [hv, bytes_getElem! s p hpl, getElem!_pos s.val p hpl])
set_option hygiene false in
local notation "T24!" => (by
obtain ⟨hps, hntp, hso, hde⟩ := h
obtain ⟨h3, h258, hpl, hd1, hd32, hdp, hmm⟩ := hm
have hntl : ntU.val < out.length := by omega
refine ⟨by omega, by omega, by rw [Std.Slice.set_length]; exact hso, ?_⟩
rw [← hnt]
exact emit_match s out ntU p d l v (by rw [hnt]; exact hde) hntl hd1 hdp hd32 h3 h258 hpl hmm hv)
set_option hygiene false in
local notation "T25!" => (by
obtain ⟨hps, hntp, hso, hde⟩ := h
rw [toks_pop out nt h0 hle] at hde
obtain ⟨hp1, hde'⟩ := decode_pop_lit (by simpa using hps) hde ht
exact ⟨hp1, by omega, by omega, hso, hde'⟩)
set_option hygiene false in
local notation "T26!" => (by
obtain ⟨hps, hntp, hso, hde⟩ := h
rw [toks_pop out nt h0 hle] at hde
obtain ⟨hw, hde'⟩ := decode_pop_match (by simpa using hps) hde ht
have hlen := decode_length_le hde'
rw [toks_length out (nt - 1) (by omega), List.length_take, bytes_length] at hlen
exact ⟨hw, by omega, by omega, hso, hde'⟩)
set_option hygiene false in
local notation "T27!" => (by
obtain ⟨h3, h258, hpl, hd1, hd32, _, hm⟩ := h
refine ⟨by omega, by omega, by omega, hd1, hd32, by omega, ?_⟩
intro k hk
rcases Nat.eq_zero_or_pos k with hk0 | hk0
· subst hk0
rw [Nat.add_zero, Nat.add_zero, show p - 1 - d = p - 1 - d by rfl]
exact heq
· have := hm (k - 1) (by omega)
rw [show p - 1 + k = p + (k - 1) by omega, show p - 1 - d + k = p - d + (k - 1) by omega]
exact this)
set_option hygiene false in
local notation "T28!" => (by
obtain ⟨h3, h258, hpl, hd1, hd32, _, hm⟩ := h
refine ⟨by omega, by omega, by omega, hd1, hd32, hdw, ?_⟩
intro k hk
rcases Nat.lt_or_ge k w with hkw | hkw
· have := hmw k hkw
rw [show p - w - d = p - w - d by rfl] at this
exact this
· have := hm (k - w) (by omega)
rw [show p - w + k = p + (k - w) by omega, show p - w - d + k = p - d + (k - w) by omega]
exact this)
set_option hygiene false in
local notation "T29!" => (by
intro k hk
rcases Nat.eq_zero_or_pos k with h0 | hk0
· subst h0; simpa using heq
· have := h (k - 1) (by omega)
rw [show b + 1 + (k - 1) = b + k by omega, show a + 1 + (k - 1) = a + k by omega] at this
exact this)
set_option hygiene false in
local notation "T30!" => (by
intro j hj
rcases Nat.lt_or_ge j k with hjk | hjk
· exact h1 j hjk
· have := h2 (j - k) (by omega)
rw [show b + k + (j - k) = b + j by omega, show a + k + (j - k) = a + j by omega] at this
exact this)
set_option hygiene false in
local notation "T31!" => (by
have hsz : Std.Usize.max < 2 ^ UScalarTy.Usize.numBits := by
rw [Std.Usize.max_def, Std.Usize.numBits]
have : 0 < 2 ^ UScalarTy.Usize.numBits := Nat.two_pow_pos _
omega
show (BitVec.ofNat _ (min (UScalar.max UScalarTy.Usize) (x.val + y.val))).toNat = _
rw [BitVec.toNat_ofNat, UScalar.max_USize_eq, Nat.mod_eq_of_lt (by omega)])
set_option hygiene false in
local notation "T32!" => (by
have hx := x.hBounds
show (BitVec.ofNat _ (max 0 (x.val - y.val))).toNat = x.val - y.val
rw [BitVec.toNat_ofNat, Nat.zero_max]
exact Nat.mod_eq_of_lt (lt_of_le_of_lt (Nat.sub_le _ _) hx))
set_option hygiene false in
local notation "T33!" => (by
have hsz : 4294967296 ≤ Usize.size := by scalar_tac
have hil : i.val < e.val := by scalar_tac
have hel : e.val < Usize.size := by scalar_tac
rw [hi, core.num.Usize.wrapping_add_val_eq, UScalar.size_UScalarTyUsize] at hil
by_cases hw : ins.val + t.val < Usize.size
· rw [Nat.mod_eq_of_lt hw] at hil; omega
· omega)
set_option hygiene false in
local notation "T40!" => (by
intro j hj
rw [Std.Array.repeat_val, List.getElem!_eq_getElem?_getD,
List.getElem?_replicate_of_lt (by simpa using hj)]
rfl)
set_option hygiene false in
local notation "T41!" => (by
intro j hj
rw [Std.Array.set_val_eq]
by_cases hja : a.val = j
· subst hja
have hlen : a.val < cnt.val.length := by simp; omega
rw [List.getElem!_eq_getElem?_getD, List.getElem?_set_self hlen]
exact hv
· rw [List.getElem!_eq_getElem?_getD, List.getElem?_set_ne hja, ← List.getElem!_eq_getElem?_getD]
exact le_trans (h j hj) (by omega))
set_option hygiene false in
local notation "T43!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat
(measure := fun r => 256 - r.2.2.val)
(inv := fun r => r.2.2.val ≤ 256)
· rintro ⟨mx, sq, b2⟩ hb
simp only at hb
simp only [q1__]
step*
repeat' (split <;> step*)
· exact hb)
namespace E_M
open Aeneas Aeneas.Std Result ControlFlow
set_option maxRecDepth 8192
set_option maxHeartbeats 4000000
set_option linter.unusedVariables false
open LZ77 (toks bytes bytes_length bytes_getElem! toks_update bytes_congr
Matches Found emit_lit emit_match ite_ok)
open LZ77 (decode emit copyN tokLen tokDist MATCH_BASE TOK_LIMIT decode_snoc copyN_length)
@[irreducible] def word8 (input : Slice Std.U8) (p : Nat) : Nat :=
(input.val[p]!).val * 2^56 + (input.val[p + 1]!).val * 2^48 + (input.val[p + 2]!).val * 2^40
+ (input.val[p + 3]!).val * 2^32 + (input.val[p + 4]!).val * 2^24
+ (input.val[p + 5]!).val * 2^16 + (input.val[p + 6]!).val * 2^8 + (input.val[p + 7]!).val
theorem u8_lt (x : Std.U8) : x.val < 256 := by scalar_tac
theorem word8_digit (input : Slice Std.U8) (p k : Nat) (hk : k < 8) :
(input.val[p + k]!).val = word8 input p / 256 ^ (7 - k) % 256 := by
have := u8_lt (input.val[p]!); have := u8_lt (input.val[p+1]!)
have := u8_lt (input.val[p+2]!); have := u8_lt (input.val[p+3]!)
have := u8_lt (input.val[p+4]!); have := u8_lt (input.val[p+5]!)
have := u8_lt (input.val[p+6]!); have := u8_lt (input.val[p+7]!)
simp only [word8]
rcases (show k = 0 ∨ k = 1 ∨ k = 2 ∨ k = 3 ∨ k = 4 ∨ k = 5 ∨ k = 6 ∨ k = 7 by omega) with
rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> simp only [Nat.add_zero, Nat.pow_zero, Nat.pow_succ, Nat.one_mul,
Nat.sub_self, Nat.reduceSub] <;> omega
theorem word8_prefix (input : Slice Std.U8) (a b d : Nat) (hd : d ≤ 8)
(h : word8 input a / 2 ^ (64 - 8 * d) = word8 input b / 2 ^ (64 - 8 * d)) :
∀ k, k < d → input.val[b + k]! = input.val[a + k]! := by
intro k hk
have e : (256 : Nat) ^ (7 - k) = 2 ^ (64 - 8 * d) * 2 ^ (8 * (d - 1 - k)) := by
rw [← pow_add, show (256 : Nat) = 2 ^ 8 by norm_num, ← pow_mul]
congr 1; omega
have key : word8 input a / 256 ^ (7 - k) = word8 input b / 256 ^ (7 - k) := by
rw [e, ← Nat.div_div_eq_div_mul, ← Nat.div_div_eq_div_mul, h]
have ha := word8_digit input a k (by omega)
have hb := word8_digit input b k (by omega)
rw [key] at ha
scalar_tac
theorem Matches.add_prefix {input : Slice Std.U8} {a b l d : Nat} (h : Matches input a b l)
(hd : d ≤ 8)
(hw : word8 input (a + l) / 2 ^ (64 - 8 * d) = word8 input (b + l) / 2 ^ (64 - 8 * d)) :
Matches input a b (l + d) := by
intro k hk
by_cases hkl : k < l
· exact h k hkl
· have := word8_prefix input (a + l) (b + l) d hd hw (k - l) (by omega)
rw [show b + l + (k - l) = b + k by omega, show a + l + (k - l) = a + k by omega] at this
exact this
theorem or_eq_add_of_mod {x t : Nat} (m : Nat) (hx : x % 2 ^ m = 0) (ht : t < 2 ^ m) :
x ||| t = x + t := T1!
theorem shl_byte {x : Nat} (k : Nat) (hx : x < 256) (hk : k ≤ 56) :
x <<< k % U64.size = x * 2 ^ k := T2!
theorem be8_nat {a b c d e f g h : Nat} (ha : a < 256) (hb : b < 256) (hc : c < 256)
(hd : d < 256) (he : e < 256) (hf : f < 256) (hg : g < 256) (hh : h < 256) :
(a <<< 56 % U64.size ||| b <<< 48 % U64.size ||| c <<< 40 % U64.size |||
d <<< 32 % U64.size ||| e <<< 24 % U64.size ||| f <<< 16 % U64.size |||
g <<< 8 % U64.size ||| h) =
a * 2^56 + b * 2^48 + c * 2^40 + d * 2^32 + e * 2^24 + f * 2^16 + g * 2^8 + h := by
rw [shl_byte 56 ha (by norm_num), shl_byte 48 hb (by norm_num), shl_byte 40 hc (by norm_num),
shl_byte 32 hd (by norm_num), shl_byte 24 he (by norm_num), shl_byte 16 hf (by norm_num),
shl_byte 8 hg (by norm_num)]
rw [or_eq_add_of_mod 56 (x := a * 2^56) (t := b * 2^48) (by omega) (by omega)]
rw [or_eq_add_of_mod 48 (x := a * 2^56 + b * 2^48) (t := c * 2^40) (by omega) (by omega)]
rw [or_eq_add_of_mod 40 (x := a * 2^56 + b * 2^48 + c * 2^40) (t := d * 2^32) (by omega)
(by omega)]
rw [or_eq_add_of_mod 32 (x := a * 2^56 + b * 2^48 + c * 2^40 + d * 2^32) (t := e * 2^24)
(by omega) (by omega)]
rw [or_eq_add_of_mod 24 (x := a * 2^56 + b * 2^48 + c * 2^40 + d * 2^32 + e * 2^24)
(t := f * 2^16) (by omega) (by omega)]
rw [or_eq_add_of_mod 16
(x := a * 2^56 + b * 2^48 + c * 2^40 + d * 2^32 + e * 2^24 + f * 2^16)
(t := g * 2^8) (by omega) (by omega)]
rw [or_eq_add_of_mod 8
(x := a * 2^56 + b * 2^48 + c * 2^40 + d * 2^32 + e * 2^24 + f * 2^16 + g * 2^8)
(t := h) (by omega) (by omega)]
@[local step]
theorem be8_spec (s : Slice Std.U8) (i : Std.Usize) (h : i.val + 8 ≤ s.length) :
slot.be8 s i ⦃ fun v => v.val = word8 s i.val ⦄ := by
rw [slot.be8]
step*
simp only [← getElem!_pos] at *
simp_all only [UScalar.val_or, U8.cast_U64_val_eq]
rw [be8_nat (u8_lt _) (u8_lt _) (u8_lt _) (u8_lt _) (u8_lt _) (u8_lt _) (u8_lt _) (u8_lt _)]
simp only [word8]
theorem nat_xor_eq_zero {a b : Nat} (h : a ^^^ b = 0) : a = b := T3!
theorem div_eq_of_xor_lt {x y m : Nat} (hz : x ^^^ y < 2 ^ m) : x / 2 ^ m = y / 2 ^ m := by
have h : (x ^^^ y) >>> m = 0 := by rw [Nat.shiftRight_eq_div_pow]; exact Nat.div_eq_of_lt hz
rw [Nat.shiftRight_xor_distrib] at h
have := nat_xor_eq_zero h
simpa [Nat.shiftRight_eq_div_pow] using this
theorem lt_pow_leadingZeros (z : BitVec 64) :
z.toNat < 2 ^ (64 - 8 * (BitVec.leadingZeros z / 8)) := T4!
theorem leadingZeros_lt_of_ne (z : BitVec 64) (h : z ≠ 0) : BitVec.leadingZeros z < 64 := by
unfold BitVec.leadingZeros
simp only [h, if_false]
omega
@[local step]
theorem lz_spec (x : Std.U64) :
lift (core.num.U64.leading_zeros x) ⦃ fun r => r = core.num.U64.leading_zeros x ∧ r.val ≤ 64 ⦄ := T5!
theorem lz_val (x : Std.U64) :
(core.num.U64.leading_zeros x).val = BitVec.leadingZeros x.bv := T6!
theorem Matches.word_lz {input : Slice Std.U8} {a b k : Nat} {pa pb r k1 : Std.Usize}
{x y z : Std.U64} {lz q : Std.U32}
(h : Matches input a b k) (hpa : pa.val = a + k) (hpb : pb.val = b + k)
(hx : x.val = word8 input pa.val) (hy : y.val = word8 input pb.val)
(hz : z.val = (x ^^^ y).val) (hz0 : ¬z = 0#u64) (hlz : lz = core.num.U64.leading_zeros z)
(hq : q.val = lz.val / 8) (hr : r = UScalar.cast .Usize q) (hk1 : k1.val = k + r.val) :
Matches input a b k1.val ∧ k1.val < k + 8 := by
have hbv : z.bv ≠ 0 := by
intro h0; apply hz0; exact UScalar.eq_of_val_eq (by simp [UScalar.val, h0])
have hlt : BitVec.leadingZeros z.bv < 64 := leadingZeros_lt_of_ne z.bv hbv
have hrv : r.val = BitVec.leadingZeros z.bv / 8 := by
rw [hr, U32.cast_Usize_val_eq, hq, hlz, lz_val]
rw [hpa] at hx; rw [hpb] at hy
refine ⟨?_, by omega⟩
rw [hk1, hrv]
have hle : BitVec.leadingZeros z.bv ≤ 64 := by unfold BitVec.leadingZeros; split <;> omega
apply Matches.add_prefix h (by omega)
rw [← hx, ← hy]
apply div_eq_of_xor_lt
rw [← UScalar.val_xor, ← hz]
exact lt_pow_leadingZeros z.bv
theorem Matches.word_zero {input : Slice Std.U8} {a b k : Nat} {pa pb k1 : Std.Usize}
{x y z : Std.U64}
(h : Matches input a b k) (hpa : pa.val = a + k) (hpb : pb.val = b + k)
(hx : x.val = word8 input pa.val) (hy : y.val = word8 input pb.val)
(hz : z.val = (x ^^^ y).val) (hz0 : z = 0#u64) (hk1 : k1.val = k + 8) :
Matches input a b k1.val := by
have hxy : x.val = y.val := by
apply nat_xor_eq_zero
rw [← UScalar.val_xor, ← hz, hz0]; rfl
rw [hpa] at hx; rw [hpb] at hy
rw [hk1]
apply Matches.add_prefix h (le_refl 8)
rw [← hx, ← hy, hxy]
theorem Matches.byte' {input : Slice Std.U8} {a b l : Nat} {pa pb l1 : Std.Usize}
{x y : Std.U8} (h : Matches input a b l) (hpa : pa.val = a + l) (hpb : pb.val = b + l)
(hpa' : pa.val < input.val.length) (hpb' : pb.val < input.val.length)
(hx : x = input.val[pa.val]) (hy : y = input.val[pb.val]) (hxy : x = y)
(hl1 : l1.val = l + 1) : Matches input a b l1.val := T7!
theorem common_loop0_spec (s : Slice Std.U8) (a b cap k : Std.Usize) (run : Std.U32)
(ha : a.val + cap.val ≤ s.length) (hb : b.val + cap.val ≤ s.length) (hcap : cap.val ≤ 258)
(hk : k.val ≤ cap.val) (hm : Matches s a.val b.val k.val) :
slot.common_loop0 s a b cap k run ⦃ fun r =>
r.1.val ≤ cap.val ∧ Matches s a.val b.val r.1.val ⦄ := by
rw [slot.common_loop0]
have hmax : s.length ≤ Std.Usize.max := Std.Slice.length_ineq sGate report
verifying [internal-path]
workspace: [internal-path]
0 intake ok — 770: parse.rs, Parse.lean
1 policy ok — source prefilters passed
2 static ok — resolved operations: alloc::alloc::Global::{impl}::drop_glue, alloc::vec::Vec::{impl}::drop_glue, alloc::vec::{impl}::deref, alloc::vec::{impl}::len, alloc::vec::{impl}::push, alloc::vec::{impl}::with_capacity, core::num::{impl}::leading_zeros, core::num::{impl}::saturating_add, core::num::{impl}::saturating_sub, core::num::{impl}::wrapping_add, core::num::{impl}::wrapping_mul, core::num::{impl}::wrapping_shl, core::num::{impl}::wrapping_sub, core::slice::{impl}::len
3 extract ok — charon+aeneas re-run by the verifier, no new axioms
4 statement ok — `LZ77.Obligation slot.parse` typechecks (bwrap, 900s, 16384 MB)
5 axioms ok — ['Classical.choice', 'Quot.sound', 'propext']; extraction intact
6 score running…
Corpus: corpus-stage1
file raw incumbent submission
-----------------------------------------------------
binary.db.bin 500000 76338 76368
bundle.min.js.txt 1000000 301618 301383
catalog.xml.txt 500000 62314 61977
compressed.bin 300000 300194 300095
config.yaml.txt 400000 85384 85236
docs.md.txt 800000 226973 227977
dump.sql.txt 150000 20817 18310
genome.fasta 900000 292479 264439
images.bin 250000 223767 224273
lean.txt 1000000 235059 236519
machine-code.bin 500000 167357 165882
metrics.csv.txt 1300000 287282 264575
multibyte.txt 1100000 273630 271132
page.html.txt 600000 103618 103585
prose.txt 1500000 579041 558476
records.json.txt 400000 72255 71265
server.log 300000 29404 27618
source.c.txt 1400000 354325 354523
source.py.txt 600000 132748 131808
source.rs.txt 700000 134069 133349
sourcemap.map.txt 350000 68389 69624
sparse.bin 40000 1234 1193
tiny-app.log 28000 965 913
tiny-config.json.txt 12000 2107 2114
weights-bf16.bin 450000 362200 354317
weights-f16.bin 250000 216274 212660
weights-f32.bin 350000 284747 280829
weights-q8.bin 250000 236246 235572
-----------------------------------------------------
TOTAL 15930000 5130834 5036012
method bytes ratio lz77 encode total slowdown
--------------------------------------------------------------------------------------------------------------
incumbent 5130834 1.00000x 0.625s 0.230s 0.855s 1.00x the incumbent
submission 5036012 0.98152x 0.151s 0.250s 0.402s 0.47x ACCEPTED — 1.848% smaller than the incumbent.
ACCEPTED — 1.848% smaller than the incumbent.
Corpus: corpus-stage2
corpus corpus-stage2 is held out; totals only.
method bytes ratio lz77 encode total slowdown
--------------------------------------------------------------------------------------------------------------
incumbent 5218788 1.00000x 0.629s 0.233s 0.862s 1.00x the incumbent
submission 5131474 0.98327x 0.156s 0.256s 0.411s 0.48x ACCEPTED — 1.673% smaller than the incumbent.
ACCEPTED — 1.673% smaller than the incumbent.