Skipping the flipped entries of an out-block
ProvedDirKECC1549.Asm.dsSkip_specStarting at raw position of the out-block of , the skip loop advances to the first non-flipped entry (or the end of the block) at raw position with the same translated cursor, within time proportional to the number of skipped flipped entries plus a constant.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
import Definitions.Def_DirKECC1549_Impl_L1Step
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}theorem DirKECC1549.Asm.dsSkip_spec (E : Env) (mm orig : Memory w) (B : Fin m → Fin n × Fin n) (perm : Equiv.Perm (Fin m))
(CFb INb IPb SV LEN OFF PRM INO HO TO : ℕ) (F : Finset (Fin m))
(hF : FRep B (fun x => its B x) CFb INb IPb F mm) (hL : FLay B (fun x => its B x) CFb INb IPb)
(hI : ImgAt orig mm SV LEN) (hB : BImg B orig OFF PRM INO HO TO perm)
(hlen : PRM + m ≤ LEN ∧ HO + 2 * m ≤ LEN ∧ INO + n < LEN) (x : Fin n) (r0 : ℕ)
(h2 : (mm 2).toNat = ots B x + r0) (h3 : (mm 3).toNat = ots B (x + 1))
(h17 : (mm 17).toNat = CFb) (h18 : (mm 18).toNat = INb) (h19 : (mm 19).toNat = IPb)
(h21 : (mm 21).toNat = PRM) (h22 : (mm 22).toNat = INO) (h23 : (mm 23).toNat = HO) (h27 : (mm 27).toNat = SV)
(hSV : 28 ≤ SV) (hIN : 28 ≤ INb) (hCF : 28 ≤ CFb) (hIP : 28 ≤ IPb) (hr0 : ots B x + r0 ≤ 2 * m)
(hw : SV + LEN + INb + IPb + CFb + 4 * m + n + 100 < 2 ^ w.bits) :
Run E dsSkip mm (fun t mm' => ∃ r1, r0 ≤ r1 ∧ (r0 < r1 → r1 ≤ (outL B perm x).length) ∧
curOf B perm F x r1 = curOf B perm F x r0 ∧
(∀ h : r1 < (outL B perm x).length, (outL B perm x)[r1] ∉ F) ∧
(mm' 2).toNat = ots B x + r1 ∧ t ≤ 50 * (r1 - r0) + 70 ∧
∀ a, a ≠ 0 → a ≠ 1 → a ≠ 2 → a ≠ 4 → a ≠ 7 → a ≠ 11 → a ≠ 12 → mm' a = mm a) := by sorry