Prepared scalars and spill words before the array-initialization loop
DefinitionDirKECC1549_Main_ReverseSearchArrayInitPreThis predicate describes the input to the fixed reverse-search program's array-initialization loop. It is parameterized by n, m, root r, original memory M, and current state s. Put B=n+2m+3 and S=16B+64.
The state is running at counter 57. Registers 1, 3, 4, 5, 6, 7, and 8 contain n, m, B, r, 6B, 8B+64, and 10B+64, respectively. Register 2 contains S and the initialization counter in register 11 is zero.
The spill words preserve the original register words:
All original words strictly above address 16 and below 6B are unchanged. No condition is imposed on the parent array, visited array, queue contents, or other scratch memory. In particular, the predicate does not assume the array initialization that the following loop must perform.
This is a pure precondition definition, containing no theorem that the prologue establishes it. It separates the straight scalar/spill prologue from the repeated parent-writing and visited-clearing instructions at counters 57–63.
import Definitions.Def_DirKECC1549_Main_ReverseSearchRootSetupPre
set_option autoImplicit false
open WordRAM
namespace DirKECC1549.Main
/-- Scalar and spill preparation for the array-initialization loop at counter 57.
The loop counter is zero; the parent and visited arrays may contain arbitrary words. -/
structure ReverseSearchArrayInitPre (n m : ℕ) (r : Fin n) {w : Width}
(initial : Memory w) (s : State w) : Prop where
pc_eq : s.pc = 57
running : s.halted = false
registers :
(s.mem 1).toNat = n ∧ (s.mem 3).toNat = m ∧ (s.mem 4).toNat = blk n m ∧
(s.mem 5).toNat = r ∧ (s.mem 6).toNat = 6 * blk n m ∧
(s.mem 7).toNat = 8 * blk n m + 64 ∧ (s.mem 8).toNat = 10 * blk n m + 64
spill_pointer : (s.mem 2).toNat = 16 * blk n m + 64
saved_zero : s.mem (16 * blk n m + 64 + 16) = initial 0
saved_registers : ∀ a : ℕ, 1 ≤ a → a ≤ 16 →
s.mem (16 * blk n m + 64 + a - 1) = initial a
input_frame : ∀ a : ℕ, 16 < a → a < 6 * blk n m → s.mem a = initial a
counter_zero : (s.mem 11).toNat = 0
end DirKECC1549.Main