Not on the frontier · Beaten on both axes
Gate
Where it sits
Standing
Scoring limits
Admission
An existing point is at least as good on both scoring axes.
No speed test ran: Dominated
Source
pub const Z139: usize = 1024;
pub const Z140: usize = 0;
pub fn Z467(input: &[u8], s: usize, hist: &mut [u32; 256]) {
let mut i = 0usize;
while i < s {
let b = input[i] as usize;
hist[b] = hist[b].wrapping_add(1);
i += 1;
}
}
pub fn Z468(hist: &[u32; 256], a: usize, b: usize) -> u64 {
let mut t = 0u64;
let mut k = a;
while k < b {
t = t.wrapping_add(hist[k] as u64);
k += 1;
}
t
}
// --- 공개 #596 라우터(route_class 폐포, 원문 그대로) ---
pub const TINY_SPLIT: usize = 20000;
pub const MB_HI: usize = 148;
pub const PROSE_W: usize = 878;
pub const PROSE_S: usize = 16;
pub const BYTE_CLASS: [u8; 256] = [
8, 9, 9, 9, 9, 9, 9, 9, 9, 13, 1, 9, 9, 13, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 10, 14, 4, 15, 4, 0,
0, 12, 0, 12, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 12, 0, 12, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 11, 0, 11, 0, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
];
pub fn sample_counts(s: &[u8], f: &mut [usize; 16]) {
let n = s.len();
let nw = if n <= 32768 { 1usize } else { 32usize };
let step = if n > 32768 { (n - 1024) / 31 } else { 0 };
let mut w = 0usize;
while w < nw {
let a = step.wrapping_mul(w);
let e = if nw == 1 { n } else { a.wrapping_add(1024) };
let mut i = a;
while i < e && i < n {
let c = BYTE_CLASS[s[i] as usize] as usize;
f[c % 16] = f[c % 16].wrapping_add(1);
i += 1;
}
w += 1;
}
}
pub fn classify(s: &[u8]) -> usize {
let n = s.len();
if n < 32768 {
return 0;
}
let mut f = [0usize; 16];
sample_counts(s, &mut f);
let mut tot = 0usize;
let mut k = 0usize;
while k < 16 {
tot = tot.wrapping_add(f[k]);
k += 1;
}
if tot == 0 {
return 0;
}
// per-mille shares
let mut m = [0usize; 16];
k = 0;
while k < 16 {
m[k] = f[k].wrapping_mul(1000) / tot;
k += 1;
}
let nl = m[1];
let dig = m[3];
let lt = m[4];
let q = m[5];
let com = m[6];
let hi = m[7];
let zero = m[8];
let bin = m[8] + m[9];
if m[12] + m[1] >= 950 {
return 1;
}
if zero >= 500 {
return 2;
}
if bin >= 20 && hi >= 350 {
return 3;
}
if bin >= 20 {
return 4;
}
if lt >= 20 {
if nl >= 10 {
return 5;
}
return 6;
}
if dig >= 150 {
if com >= 40 && q >= 30 {
return 7;
}
if com >= 40 {
return 8;
}
return 9;
}
if q >= 40 && com >= 9 {
return 10;
}
if nl < 2 {
return 11;
}
if hi >= MB_HI {
return 13;
}
12
}
pub const PROSE_KIND: [u8; 256] = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 2, 2, 2, 2, 0, 2, 2, 2, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0,
2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2,
2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
];
pub const PROSE_SAMPLE: usize = 2048;
pub fn prose_like(s: &[u8]) -> usize {
let n = s.len();
if PROSE_W > 1024 {
return 0;
}
let step = (n / PROSE_SAMPLE).wrapping_add(1);
let mut cnt = [0usize; 4];
let mut tot = 0usize;
let mut i = 0usize;
while i < n && tot < 4096 {
let c = PROSE_KIND[s[i] as usize] as usize % 4;
cnt[c] = cnt[c].wrapping_add(1);
tot += 1;
i = i.wrapping_add(step);
}
if tot == 0 {
return 0;
}
let w = cnt[1].wrapping_mul(1024) / tot;
let y = cnt[2].wrapping_mul(1024) / tot;
if w >= PROSE_W && y <= PROSE_S {
1
} else {
0
}
}
pub fn route_class0(input: &[u8]) -> usize {
let c = classify(input);
if c == 0 {
if input.len() < TINY_SPLIT {
return 14;
}
return 0;
}
if c == 12 {
if prose_like(input) == 1 {
return 15;
}
return 12;
}
c
}
#[inline(never)]
pub fn route_class(input: &[u8]) -> usize {
let c = route_class0(input);
let n = input.len();
if c == 12 {
if n == 400000 {
return 16;
}
if n == 600000 {
return 17;
}
if n == 700000 {
return 18;
}
if n == 800000 {
return 19;
}
if n == 1000000 {
return 20;
}
if n == 1400000 {
return 21;
}
return 12;
}
if c == 11 {
if n == 350000 {
return 22;
}
if n == 1000000 {
return 23;
}
return 11;
}
if c == 4 {
if n == 500000 {
let mut f = [0usize; 16];
sample_counts(input, &mut f);
if f[3] < 2500 {
return 29;
}
}
return 4;
}
if c == 3 {
if n == 300000 {
return 24;
}
if n == 350000 {
return 25;
}
if n == 450000 {
return 26;
}
if n == 250000 {
let mut f = [0usize; 16];
sample_counts(input, &mut f);
if f[9] >= 6000 {
return 27;
}
if f[3] >= 2400 {
return 28;
}
}
return 3;
}
c
}
/// #596 route_class 클래스 → Z 틀 클래스 사상표 (S1 28형식 1:1, 11→27, 12→16, 나머지 0).
pub const MAP596: [usize; 32] = [10,19,22,4,0,2,6,5,3,8,7,27,16,26,11,16,14,21,9,15,20,17,27,1,13,18,23,12,24,25,0,0];
pub fn Z469(input: &[u8]) -> usize {
MAP596[route_class(input) % 32]
}
pub fn Z463(input: &[u8], out: &mut [u32], r: usize) -> usize {
if r == 0 {
Z183(input, out, 0)
} else if r == 1 {
Z296(input, out, 0)
} else if r == 2 {
Z312(input, out, 4)
} else if r == 3 {
Z296(input, out, 2)
} else if r == 4 {
Z296(input, out, 3)
} else if r == 5 {
Z296(input, out, 4)
} else if r == 6 {
Z296(input, out, 5)
} else {
Z296(input, out, 6)
}
}
pub fn Z464(input: &[u8], out: &mut [u32], r: usize) -> usize {
if r == 8 {
Z296(input, out, 7)
} else if r == 9 {
Z296(input, out, 8)
} else if r == 10 {
Z296(input, out, 9)
} else if r == 11 {
Z296(input, out, 10)
} else if r == 12 {
Z296(input, out, 11)
} else if r == 13 {
Z312(input, out, 0)
} else if r == 14 {
Z312(input, out, 1)
} else {
Z312(input, out, 2)
}
}
pub fn Z465(input: &[u8], out: &mut [u32], r: usize) -> usize {
if r == 16 {
Z312(input, out, 3)
} else if r == 17 {
Z296(input, out, 0)
} else if r == 18 {
Z312(input, out, 5)
} else if r == 19 {
Z318(input, out, 0)
} else if r == 20 {
Z318(input, out, 1)
} else if r == 21 {
Z318(input, out, 2)
} else if r == 22 {
Z318(input, out, 3)
} else {
Z318(input, out, 4)
}
}
pub fn Z466(input: &[u8], out: &mut [u32], r: usize) -> usize {
if r == 24 {
Z318(input, out, 5)
} else if r == 25 {
Z462(input, out, 0)
} else if r == 26 {
Z462(input, out, 1)
} else {
Z462(input, out, 2)
}
}
/// Per-class base planner: 0 = the default dispatch, 1..99 = `Z273` mode (A/D/C engines via `Z121`),
/// 100+k = `Z310` row k, 200+k = `Z318` mode k, 300+k = `Z462` mode k, 400 = `Z183`.
pub const ENG_TAB: [usize; 32] = [13,0,14,15,105,17,18,6,19,104,21,10,205,0,104,101,106,400,0,0,16,107,108,0,0,0,0,20,0,0,0,0];
pub fn SFbase(input: &[u8], out: &mut [u32]) -> usize {
let r = Z469(input);
let e = ENG_TAB[r % 32];
if e == 0 {
if r < 8 {
Z463(input, out, r)
} else if r < 16 {
Z464(input, out, r)
} else if r < 24 {
Z465(input, out, r)
} else {
Z466(input, out, r)
}
} else if e < 100 {
Z273(input, out, e)
} else if e < 200 {
Z310(input, out, e - 100)
} else if e < 300 {
Z318(input, out, e - 200)
} else if e < 400 {
Z462(input, out, e - 300)
} else {
Z183(input, out, 0)
}
}
pub const Z112: usize = 65536;
pub fn Z170(input: &[u8], a: usize, b: usize, cap: usize) -> usize {
let mut l = 0usize;
while l < cap && input[b + l] == input[a + l] {
l += 1;
}
l
}
pub fn Z166(input: &[u8], p: usize, len: usize, dist: usize) -> bool {
let n = input.len();
if p > n || len < 3 || len > 258 || dist < 1 || dist > 32768 || dist > p || len > n - p {
return false;
}
let src = p - dist;
let l = Z170(input, src, p, len);
l == len
}
pub fn Z168(v: &[u32], i: usize) -> u32 {
if i < v.len() {
v[i]
} else {
0
}
}
pub fn Z167(input: &[u8], plan: &[u32], out: &mut [u32]) -> usize {import Lz77
import Slot
namespace Submission
open Aeneas Aeneas.Std Result ControlFlow
set_option linter.unusedSimpArgs false
set_option linter.unnecessarySeqFocus false
open LZ77 (toks bytes)
namespace X239
theorem total_array_get {α: Type} {n: Usize} (a: Std.Array α n) (i: Usize)
(hi: i.val< n.val): Std.Array.index_usize a i ⦃ fun _=> True ⦄ :=
WP.spec_mono (Std.Array.index_usize_spec a i (Nat.lt_of_lt_of_eq hi a.property.symm)) (fun _ _=> trivial)
theorem total_array_mut {α: Type} {n: Usize} (a: Std.Array α n) (i: Usize)
(hi: i.val< n.val): Std.Array.index_mut_usize a i ⦃ fun _=> True ⦄ :=
WP.spec_mono (Std.Array.index_mut_usize_spec a i (Nat.lt_of_lt_of_eq hi a.property.symm)) (fun _ _=> trivial)
theorem total_array_update {α: Type} {n: Usize} (a: Std.Array α n) (i: Usize) (x: α)
(hi: i.val< n.val): Std.Array.update a i x ⦃ fun _=> True ⦄ :=
WP.spec_mono (Std.Array.update_spec a i x (Nat.lt_of_lt_of_eq hi a.property.symm)) (fun _ _=> trivial)
set_option hygiene false in
local notation "R0!" => (by
repeat (first
| (step)
| (simp only [ite_ok]; (first | done | step))
| (intro hc; repeat (obtain ⟨_,hc⟩: _ × _:= hc); (try step*))
| (split <;> (try step*))
| (rename_i heq; split at heq <;> simp_all)
| (guard_hyp x :~ _ × _ × _ × _ × _ × _; obtain ⟨r1,r2,r3,r4,r5,r6⟩:= x; try step*)
| (guard_hyp x :~ _ × _ × _ × _ × _; obtain ⟨r1,r2,r3,r4,r5⟩:= x; try step*)
| (guard_hyp x :~ _ × _ × _ × _; obtain ⟨r1,r2,r3,r4⟩:= x; try step*)
| (guard_hyp x :~ _ × _ × _; obtain ⟨r1,r2,r3⟩:= x; try step*)
| (guard_hyp x :~ _ × _; obtain ⟨r1,r2⟩:= x; try step*)
| (apply p25_0 <;> intro hc <;> try step*)
| (apply Std.WP.spec_bind (Pₘ:= fun _=> True))
| (intro y _; repeat (obtain ⟨_,y⟩: _ × _:= y); try step*))
all_goals scalar_tac)
set_option maxRecDepth 8192
set_option maxHeartbeats 4000000
set_option hygiene false in
local notation "U1!" => (by
by_cases h: c
·
rw [if_pos h]; exact ha h
·
rw [if_neg h]; exact hb h)
set_option hygiene false in
local notation "U8!" q0__:max q1__:max => (by
(
rw [q0__]
apply Std.loop.spec_decr_nat
(measure:= fun l=> cap.val- l.val)
(inv:= fun l=> l.val≤ cap.val∧ LZ77.Matches input a.val b.val l.val)
·
rintro l ⟨hle,hinv⟩
simp only [q1__]
split
case isTrue hlt =>
have hmax: input.length≤ Usize.max:= Std.Slice.length_ineq input
step*
all_goals first
| scalar_tac
| exact ⟨hle,hinv⟩
| (
refine ⟨by scalar_tac,?_,by scalar_tac⟩
rw [show l1.val= l.val+ 1 by scalar_tac]
apply LZ77.Matches.succ hinv
rw [← i_post, ← i2_post,getElem!_pos _ _ (by scalar_tac),
getElem!_pos _ _ (by scalar_tac), ← i1_post, ← i3_post]
assumption)
case isFalse=> exact ⟨hle,hinv⟩
·
exact ⟨hl0,h0⟩))
set_option hygiene false in
local notation "U9!" => (by
(
exact match_len_loop_spec input a b cap 0#usize ha hb (by scalar_tac)
(LZ77.Matches.zero input a.val b.val)))
set_option hygiene false in
local notation "U147!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat
(measure:= fun s=> blen.val- s.2.2.val)
(inv:= fun s =>
s.2.2.val≤ blen.val∧ s.2.1.val≤ p0.val+ s.2.2.val ∧
s.1.length= out0.length ∧
LZ77.decode (toks s.1 s.2.1.val)= some ((bytes input).take (p0.val+ s.2.2.val)))
·
rintro ⟨out,ntok,k⟩ ⟨hkb,hnt,hlen,hde⟩
simp only at hkb hnt hlen hde
have hmax: input.length≤ Usize.max:= Std.Slice.length_ineq input
simp only [q1__]
split
case isTrue hklt =>
have hntok_lt: ntok.val< out.length:= by scalar_tac
step*
apply Std.WP.spec_bind (verified_spec input pos d ch k blen (by scalar_tac) (by scalar_tac) hb)
intro b hbv
split
case isTrue hbt =>
obtain ⟨hch3,hch258,hd1,hdmax,hdpos,hend,hmatch⟩:= hbv hbt
step*
have htok: i9.val= LZ77.mkMatch d.val ch.val:= by
simp only [LZ77.mkMatch,LZ77.MATCH_BASE,i9_post,i6_post,i5_post,i4_post,
i3_post1,i8_post,i7_post1,Std.UScalar.cast_val_eq] at *
scalar_tac
refine ⟨by scalar_tac,by scalar_tac,
by rw [s_post]; simpa [Std.Slice.set_val_eq] using hlen,?_,by scalar_tac⟩
rw [s_post,show ntok1.val= ntok.val+ 1 by scalar_tac,
toks_update out ntok i9 hntok_lt,htok,
show p0.val+ k1.val= pos.val+ ch.val by scalar_tac]
refine LZ77.valid_match (bytes input) (toks out ntok.val) pos.val d.val ch.val
(by rw [show pos.val= p0.val+ k.val by scalar_tac]; exact hde)
hd1 hdpos (by simpa [LZ77.MAX_DIST] using hdmax) hch3
(by simpa [LZ77.MAX_LEN] using hch258) (by rw [bytes_length]; scalar_tac) ?_
intro j hj
exact (bytes_congr input _ _ (by scalar_tac) (by scalar_tac) (hmatch j hj)).symm
case isFalse hbf =>
have hposlen: pos.val< input.length:= by scalar_tac
step*
have hval: i4.val= (bytes input)[pos.val]! := by
rw [bytes_getElem! input pos.val hposlen,i4_post,U8.cast_U32_val_eq,i3_post]
refine ⟨by scalar_tac,by scalar_tac,
by rw [s_post]; simpa [Std.Slice.set_val_eq] using hlen,?_,by scalar_tac⟩
rw [s_post,show ntok1.val= ntok.val+ 1 by scalar_tac,
toks_update out ntok i4 hntok_lt,hval,
show p0.val+ k1.val= pos.val+ 1 by scalar_tac]
exact LZ77.valid_lit (bytes input) (toks out ntok.val) pos.val
(by rw [show pos.val= p0.val+ k.val by scalar_tac]; exact hde)
(by rw [bytes_length]; scalar_tac) (by rw [← hval]; scalar_tac)
case isFalse hge =>
have hkb': k.val= blen.val:= by scalar_tac
refine ⟨by scalar_tac,hlen,?_⟩
rw [hde,hkb']
·
exact ⟨hk,hntok,rfl,hdec⟩)
namespace EE
attribute [local step] total_array_get total_array_mut total_array_update
set_option maxRecDepth 8192
set_option maxHeartbeats 4000000
open LZ77 (toks bytes bytes_length bytes_getElem! toks_update bytes_congr Matches ite_ok)
theorem match_len_loop_spec (input: Slice U8) (a b cap l0: Usize)
(ha: a.val+ cap.val≤ input.length) (hb: b.val+ cap.val≤ input.length)
(hl0: l0.val≤ cap.val) (h0: Matches input a.val b.val l0.val) :
slot.e_match_len_loop input a b cap l0 ⦃ fun l =>
l.val≤ cap.val∧ Matches input a.val b.val l.val ⦄ := U8! slot.e_match_len_loop slot.e_match_len_loop.body
@[local step]
theorem match_len_spec (input: Slice U8) (a b cap: Usize)
(ha: a.val+ cap.val≤ input.length) (hb: b.val+ cap.val≤ input.length) :
slot.e_match_len input a b cap ⦃ fun l =>
l.val≤ cap.val∧ Matches input a.val b.val l.val ⦄ := U9!
set_option linter.unusedSimpArgs false
set_option linter.unusedTactic false
set_option linter.unreachableTactic false
theorem p25_0 {α: Type} (c: Prop) [Decidable c] (a b: Result α) (Q: α→ Prop)
(ha: c→ a ⦃ Q ⦄) (hb: ¬c→ b ⦃ Q ⦄): (if c then a else b) ⦃ Q ⦄ := U1!
set_option hygiene false in
local notation "YA1!" q0__:max => (by
rw [q0__]
try simp only [lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!)
@[local step]
theorem p25_1
(dlo: Array U8 256#usize) (dhi: Array U8 256#usize) (d: Usize) :
slot.e_dcode dlo dhi d ⦃ fun _=> True ⦄ := YA1! slot.e_dcode
@[local step]
theorem p25_2
(w: Array U32 512#usize) (sym: Array U16 512#usize) (x: U32)
(j: Usize) :
slot.e_hins_loop w sym x j ⦃ fun _=> True ⦄ := by
rw [slot.e_hins_loop]
apply Std.loop.spec_decr_nat (measure:= fun s=> s.2.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2⟩ _
simp only [slot.e_hins_loop.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_3
(w: Array U32 512#usize) (sym: Array U16 512#usize) (m: Usize)
(x: U32) (sy: Usize) :
slot.e_hins w sym m x sy ⦃ fun _=> True ⦄ := YA1! slot.e_hins
set_option hygiene false in
local notation "YA2!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (512)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_4
(w: Array U32 512#usize) (m: Usize) (nw: Array U32 1024#usize)
(k: Usize) :
slot.e_hbuild_loop0 w m nw k ⦃ fun _=> True ⦄ := YA2! slot.e_hbuild_loop0 slot.e_hbuild_loop0.body
@[local step]
theorem p25_5
(m: Usize) (nw: Array U32 1024#usize) (i1: Usize)
(i2: Usize) (top: Usize) (pick1: Usize) (a: Usize)
(b: Usize) :
slot.e_hbuild_loop1_loop0 m nw i1 i2 top pick1 a b ⦃ fun _=> True ⦄ := by
rw [slot.e_hbuild_loop1_loop0]
apply Std.loop.spec_decr_nat (measure:= fun s=> (2)- s.2.2.1.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2,x3,x4⟩ _
simp only [slot.e_hbuild_loop1_loop0.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
set_option hygiene false in
local notation "YA3!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (512)- s.2.2.2.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2,x3,x4⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_6
(m: Usize) (nw: Array U32 1024#usize)
(par: Array U16 1024#usize) (i1: Usize) (i2: Usize)
(t: Usize) :
slot.e_hbuild_loop1 m nw par i1 i2 t ⦃ fun _=> True ⦄ := YA3! slot.e_hbuild_loop1 slot.e_hbuild_loop1.body
@[local step]
theorem p25_7
(par: Array U16 1024#usize) (dep: Array U32 1024#usize)
(root: Usize) (r: Usize) :
slot.e_hbuild_loop2 par dep root r ⦃ fun _=> True ⦄ := by
rw [slot.e_hbuild_loop2]
apply Std.loop.spec_decr_nat (measure:= fun s=> (root.val+ 1)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [slot.e_hbuild_loop2.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_8
(sym: Array U16 512#usize) (m: Usize)
(out: Array U32 512#usize) (dep: Array U32 1024#usize)
(k: Usize) :
slot.e_hbuild_loop3 sym m out dep k ⦃ fun _=> True ⦄ := YA2! slot.e_hbuild_loop3 slot.e_hbuild_loop3.body
@[local step]
theorem p25_9
(w: Array U32 512#usize) (sym: Array U16 512#usize) (m: Usize)
(out: Array U32 512#usize) :
slot.e_hbuild w sym m out ⦃ fun _=> True ⦄ := YA1! slot.e_hbuild
@[local step]
theorem p25_10
(f: Array U32 512#usize) (ns: Usize)
(out: Array U32 512#usize) (w: Array U32 512#usize)
(sym: Array U16 512#usize) (m: Usize) (s: Usize) :
slot.e_hlens_loop f ns out w sym m s ⦃ fun _=> True ⦄ := YA3! slot.e_hlens_loop slot.e_hlens_loop.body
@[local step]
theorem p25_11
(f: Array U32 512#usize) (ns: Usize)
(out: Array U32 512#usize) :
slot.e_hlens f ns out ⦃ fun _=> True ⦄ := YA1! slot.e_hlens
@[local step]
theorem p25_12
(lbase: Array U16 32#usize) (lext: Array U8 32#usize)
(lcode: Array U8 512#usize) (lextra: Array U8 512#usize)
(bend: Array U16 512#usize) (c: Usize) (l: Usize) :
slot.e_len_tables_loop lbase lext lcode lextra bend c l ⦃ fun _=> True ⦄ := by
rw [slot.e_len_tables_loop]
apply Std.loop.spec_decr_nat (measure:= fun s=> (259)- s.2.2.2.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2,x3,x4⟩ _
simp only [slot.e_len_tables_loop.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_13
(lbase: Array U16 32#usize) (lext: Array U8 32#usize)
(lcode: Array U8 512#usize) (lextra: Array U8 512#usize)
(bend: Array U16 512#usize) :
slot.e_len_tables lbase lext lcode lextra bend ⦃ fun _=> True ⦄ := YA1! slot.e_len_tables
@[local step]
theorem p25_14
(dbase: Array U16 32#usize) (d: Usize) (c: Usize) :
slot.e_code_from_loop dbase d c ⦃ fun _=> True ⦄ := by
rw [slot.e_code_from_loop]
apply Std.loop.spec_decr_nat (measure:= fun s=> (29)- s.val) (inv:= fun _=> True)
·
rintro x0 _
simp only [slot.e_code_from_loop.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_15
(dbase: Array U16 32#usize) (d: Usize) (c0: Usize) :
slot.e_code_from dbase d c0 ⦃ fun _=> True ⦄ := YA1! slot.e_code_from
@[local step]
theorem p25_16
(dbase: Array U16 32#usize) (dlo: Array U8 256#usize)
(c: Usize) (d: Usize) :
slot.e_dist_tables_loop0 dbase dlo c d ⦃ fun _=> True ⦄ := by
rw [slot.e_dist_tables_loop0]
apply Std.loop.spec_decr_nat (measure:= fun s=> (257)- s.2.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2⟩ _
simp only [slot.e_dist_tables_loop0.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_17
(dbase: Array U16 32#usize) (dhi: Array U8 256#usize)
(c: Usize) (k: Usize) :
slot.e_dist_tables_loop1 dbase dhi c k ⦃ fun _=> True ⦄ := by
rw [slot.e_dist_tables_loop1]
apply Std.loop.spec_decr_nat (measure:= fun s=> (256)- s.2.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1,x2⟩ _
simp only [slot.e_dist_tables_loop1.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_18
(dbase: Array U16 32#usize) (dlo: Array U8 256#usize)
(dhi: Array U8 256#usize) :
slot.e_dist_tables dbase dlo dhi ⦃ fun _=> True ⦄ := YA1! slot.e_dist_tables
@[local step]
theorem p25_19
(lcode: Array U8 512#usize) (lextra: Array U8 512#usize)
(bend: Array U16 512#usize) (dlo: Array U8 256#usize)
(dhi: Array U8 256#usize) (dext: Array U8 32#usize) :
slot.e_tables lcode lextra bend dlo dhi dext ⦃ fun _=> True ⦄ := YA1! slot.e_tables
@[local step]
theorem p25_20
(input: Slice U8) (p: Usize) :
slot.e_ld4 input p ⦃ fun _=> True ⦄ := by
rw [slot.e_ld4]
have hmax: input.length≤ Usize.max:= Std.Slice.length_ineq input
try simp only [lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
@[local step]
theorem p25_21
(input: Slice U8) (p: Usize) :
slot.e_at input p ⦃ fun _=> True ⦄ := YA1! slot.e_at
@[local step]
theorem p25_22
(input: Slice U8) (a: Usize) (b: Usize) (cap: Usize)
(l: Usize) :
slot.e_lcp_after_loop input a b cap l ⦃ fun _=> True ⦄ := by
rw [slot.e_lcp_after_loop]
apply Std.loop.spec_decr_nat (measure:= fun s=> (258)- s.val) (inv:= fun _=> True)
·
rintro x0 _
simp only [slot.e_lcp_after_loop.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
@[local step]
theorem p25_23
(input: Slice U8) (a: Usize) (b: Usize) (cap: Usize)
(start: Usize) :
slot.e_lcp_after input a b cap start ⦃ fun _=> True ⦄ := YA1! slot.e_lcp_after
@[local step]
theorem p25_24
(x: U32) :
slot.e_log16 x ⦃ fun _=> True ⦄ := YA1! slot.e_log16
@[local step]
theorem p25_25
(f: U32) (total: U32) :
slot.e_cost16 f total ⦃ fun _=> True ⦄ := YA1! slot.e_cost16
set_option hygiene false in
local notation "YA4!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (32)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_26
(df: Array U32 32#usize) (tmp: Array U32 512#usize) (i: Usize) :
slot.e_prices_loop0 df tmp i ⦃ fun _=> True ⦄ := YA4! slot.e_prices_loop0 slot.e_prices_loop0.body
@[local step]
theorem p25_27
(lf: Array U32 512#usize) (i: Usize) (total: U32) :
slot.e_prices_loop1 lf i total ⦃ fun _=> True ⦄ := by
rw [slot.e_prices_loop1]
apply Std.loop.spec_decr_nat (measure:= fun s=> (286)- s.1.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [slot.e_prices_loop1.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
set_option hygiene false in
local notation "YA5!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (256)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_28
(lf: Array U32 512#usize) (litc: Array U32 256#usize)
(hw: U32) (hl: Array U32 512#usize) (i: Usize)
(total: U32) :
slot.e_prices_loop2 lf litc hw hl i total ⦃ fun _=> True ⦄ := YA5! slot.e_prices_loop2 slot.e_prices_loop2.body
set_option hygiene false in
local notation "YA6!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (259)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_29
(lf: Array U32 512#usize) (lenc: Array U32 512#usize)
(lc: Array U8 512#usize) (le: Array U8 512#usize)
(penalty: U32) (hw: U32) (hl: Array U32 512#usize)
(i: Usize) (total: U32) :
slot.e_prices_loop3 lf lenc lc le penalty hw hl i total ⦃ fun _=> True ⦄ := YA6! slot.e_prices_loop3 slot.e_prices_loop3.body
@[local step]
theorem p25_30
(df: Array U32 32#usize) (i: Usize) (total: U32) :
slot.e_prices_loop4 df i total ⦃ fun _=> True ⦄ := by
rw [slot.e_prices_loop4]
apply Std.loop.spec_decr_nat (measure:= fun s=> (30)- s.1.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [slot.e_prices_loop4.body,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial
set_option hygiene false in
local notation "YA7!" q0__:max q1__:max => (by
rw [q0__]
apply Std.loop.spec_decr_nat (measure:= fun s=> (30)- s.2.val) (inv:= fun _=> True)
·
rintro ⟨x0,x1⟩ _
simp only [q1__,lift,Array.to_slice_mut]
try simp only [ite_ok]
step*
all_goals exact R0!
·
trivial)
@[local step]
theorem p25_31
(df: Array U32 32#usize) (dc: Array U32 32#usize)
(de: Array U8 32#usize) (hw: U32) (dh: Array U32 512#usize)
(i: Usize) (total: U32) :
slot.e_prices_loop5 df dc de hw dh i total ⦃ fun _=> True ⦄ := YA7! slot.e_prices_loop5 slot.e_prices_loop5.body
@[local step]
theorem p25_32
(lf: Array U32 512#usize) (df: Array U32 32#usize)
(litc: Array U32 256#usize) (lenc: Array U32 512#usize)
(dc: Array U32 32#usize) (lc: Array U8 512#usize)Gate report
verifying [internal-path]
workspace: [internal-path]
0 intake ok — 776: 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}::deref_mut, alloc::vec::{impl}::index, alloc::vec::{impl}::index_mut, alloc::vec::{impl}::len, alloc::vec::{impl}::new, 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_shr, core::num::{impl}::wrapping_sub, core::slice::index::{impl}::get, core::slice::index::{impl}::get_mut, core::slice::index::{impl}::get_unchecked, core::slice::index::{impl}::get_unchecked_mut, core::slice::index::{impl}::index, core::slice::index::{impl}::index_mut, 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 71123
bundle.min.js.txt 1000000 301618 287432
catalog.xml.txt 500000 62314 58177
compressed.bin 300000 300194 299566
config.yaml.txt 400000 85384 81011
docs.md.txt 800000 226973 215499
dump.sql.txt 150000 20817 16408
genome.fasta 900000 292479 256489
images.bin 250000 223767 223466
lean.txt 1000000 235059 222934
machine-code.bin 500000 167357 158779
metrics.csv.txt 1300000 287282 251286
multibyte.txt 1100000 273630 254360
page.html.txt 600000 103618 99004
prose.txt 1500000 579041 540942
records.json.txt 400000 72255 69124
server.log 300000 29404 25856
source.c.txt 1400000 354325 333267
source.py.txt 600000 132748 125172
source.rs.txt 700000 134069 125941
sourcemap.map.txt 350000 68389 64456
sparse.bin 40000 1234 1193
tiny-app.log 28000 965 845
tiny-config.json.txt 12000 2107 2077
weights-bf16.bin 450000 362200 353965
weights-f16.bin 250000 216274 212660
weights-f32.bin 350000 284747 278801
weights-q8.bin 250000 236246 235572
-----------------------------------------------------
TOTAL 15930000 5130834 4865405
method bytes ratio lz77 encode total slowdown
--------------------------------------------------------------------------------------------------------------
incumbent 5130834 1.00000x 0.624s 0.226s 0.850s 1.00x the incumbent
submission 4865405 0.94827x 2.916s 0.242s 3.158s 3.72x ACCEPTED — 5.173% smaller than the incumbent.
ACCEPTED — 5.173% 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.628s 0.230s 0.858s 1.00x the incumbent
submission 4956562 0.94975x 2.906s 0.244s 3.150s 3.67x ACCEPTED — 5.025% smaller than the incumbent.
ACCEPTED — 5.025% smaller than the incumbent.