Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Pinsketch decoder III: address layout, workspace views, readiness predicates and the four stage procedures

Definition
LinearSetReconciliation327_Main_DecoderProgram

by djwj233 · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

pinsketchset-reconciliationword-ram

This bundle contains the concrete word-RAM program that decodes a Pinsketch syndrome, together with the layout and the intermediate assertions needed to specify it.

The address layout is fixed by decoderLength, decoderCapacity, decoderSavedBase, the row bases decoderRowBase, the two queue regions, the output region, the verification base and the allocation end. On top of it are defined the workspace views (PadeRows, RowsLayout, RootConstants, RootWorkspace), the stage-exit predicates KeyReady and CandidateReady, and the writable-address sets solverInitWritable and rootSearchWritable; the latter two say exactly which memory a stage is allowed to touch.

The program consists of four procedures, each compiled from a structured statement by Stmt.compile: the reader inputSavedProcedure, the key solver keySolverProcedure, the root search rootSearchProcedure and the verifier verificationFinalProcedure. The bundle also defines the step budgets rootPhaseBudget and positiveDecoderBudget, the accept/reject postcondition decoderPost (a nonzero flag carries a light support consistent with the syndrome, and a zero flag asserts that no such support exists), and the entry point pinsketchDecoderProgram with its initial state decoderStart.

Definition code
import Definitions.Def_LinearSetReconciliation327_Main_DecoderTables
import Definitions.Def_LinearSetReconciliation327_Main_Pinsketch
import Definitions.Def_LinearSetReconciliation327_Main_WordRAM
/-! Decoder program: address layout, workspace views, readiness predicates, budgets, procedures, `decoderPost`, `pinsketchDecoderProgram`.

Generated by `p21opt/gen/emit.py` by skeleton subtraction from
`Solutions/_p21_opt3.lean` (Stage-2 declaration spans). -/

set_option autoImplicit false

open scoped ENNReal
open Finset Polynomial

namespace LinearSetReconciliation327.Main

section FieldFacts

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

end FieldFacts

section PowerSums

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

variable {N : ℕ}

end PowerSums

/-- Bit `p` of the payload `y`, as a natural number. -/
def payloadBit {M : ℕ} (y : Fin M → ZMod 2) (p : ℕ) : ℕ := (payloadAt y p).val

/-- The **dual locator** of a support: `∏_{v ∈ D} (1 − v X)`.  Its roots are the inverses `v⁻¹`,
which is why the machine inverts a root before looking up its position (`detInvBase`). -/
noncomputable def locDual {F : Type} [Field F] (D : Finset F) : F[X] :=
  ∏ v ∈ D, (1 - C v * X)

/-- The numerator of the partial-fraction form, `Σ_{v∈D} v·∏_{w ∈ D.erase v} (1 − wX)`; it has
degree `< #D`. -/
noncomputable def omegaD {F : Type} [Field F] [DecidableEq F] (D : Finset F) : F[X] :=
  ∑ v ∈ D, C v * ∏ w ∈ D.erase v, (1 - C w * X)

/-- `S = Σ_{j<N} s_j X^j` with `s_j = P_{j+1}`: the syndrome polynomial of the support `D`,
truncated at `N` coefficients.  Coefficient `0` is `P_1`, so no power sum of index `0` is involved. -/
noncomputable def synP {F : Type} [Field F] (D : Finset F) (N : ℕ) : F[X] :=
  ∑ j ∈ Finset.range N, C (∑ v ∈ D, v ^ (j + 1)) * X ^ j

/-- **A solution of the key equation**: `σ S ≡ ω (mod X^(2t))` with `deg σ ≤ t`, `deg ω < t`. -/
def KeySol {F : Type} [Field F] (D : Finset F) (t : ℕ) (σ ω : F[X]) : Prop :=
  σ ≠ 0 ∧ σ.natDegree ≤ t ∧ ω.natDegree < t ∧ X ^ (2 * t) ∣ σ * synP D (2 * t) - ω

/-- The same key equation, stated against the stored power sums `e j = s_j = P_{j+1}` instead of a
support: this is the form in which the machine's Berlekamp–Massey output is verified. -/
def KeySolE {F : Type} [Field F] (e : ℕ → F) (t : ℕ) (σ ω : F[X]) : Prop :=
  σ ≠ 0 ∧ σ.natDegree ≤ t ∧ ω.natDegree < t ∧
    X ^ (2 * t) ∣ σ * (∑ j ∈ Finset.range (2 * t), C (e j) * X ^ j) - ω

/-- The binary vector whose support is the candidate set `D`. -/
noncomputable def vecOf {F : Type} [Field F] [DecidableEq F] (N : ℕ) (ι : ℕ → F)
    (D : Finset F) : Fin N → ZMod 2 :=
  fun i => if ι i.val ∈ D then 1 else 0

/-- A **minimum-degree** solution of the key equation: Berlekamp–Massey's defining property, and
what makes the *reject* branch complete (`decoder_reject`).  Note that the *accept* branch does not
need it: the verification test itself certifies the answer. -/
def KeySolEMin {F : Type} [Field F] (e : ℕ → F) (t : ℕ) (σ ω : F[X]) : Prop :=
  KeySolE e t σ ω ∧ ∀ σ' ω' : F[X], KeySolE e t σ' ω' → σ.natDegree ≤ σ'.natDegree

/-- The algebraic part of a two-row Euclidean state.  Bounds on degrees and
machine storage are proved separately from this invariant. -/
def PadeBasis {F : Type} [Field F] (S M τ ν σ ω : F[X]) : Prop :=
  M ∣ τ * S - ν ∧ M ∣ σ * S - ω ∧ ν * σ - τ * ω = M

/-- Two consecutive rows of the extended Euclidean algorithm. -/
structure PadeState (F : Type) [Field F] where
  prevR : F[X]
  prevC : F[X]
  rem : F[X]
  curC : F[X]

noncomputable def padeInitial {F : Type} [Field F] (e : ℕ → F) (t : ℕ) : PadeState F :=
  ⟨X ^ (2 * t), 0, syndromePoly e t, 1⟩

noncomputable def padeNext {F : Type} [Field F] (s : PadeState F) : PadeState F :=
  let q := s.prevR / s.rem
  ⟨s.rem, s.curC, s.prevR % s.rem, s.prevC - q * s.curC⟩

/-- Fuel bounds only the number of quotient iterations; each quotient is
implemented by a separate coefficient loop in the machine refinement. -/
noncomputable def padeRun {F : Type} [Field F] (t : ℕ) : ℕ → PadeState F → PadeState F
  | 0, s => s
  | fuel + 1, s =>
      if s.rem.natDegree < t then s else padeRun t fuel (padeNext s)

/-- The degree balance complements the two-row congruence certificate. -/
structure PadeInv {F : Type} [Field F] (e : ℕ → F) (t : ℕ) (s : PadeState F) : Prop where
  basis : PadeBasis (syndromePoly e t) (X ^ (2 * t)) s.prevC s.prevR s.curC s.rem
  prev_ne : s.prevR ≠ 0
  cur_ne : s.curC ≠ 0
  balance : s.prevR.natDegree + s.curC.natDegree = 2 * t
  prev_large : t ≤ s.prevR.natDegree
  prev_small : s.prevC.natDegree ≤ s.curC.natDegree
  rem_small : s.rem.natDegree < s.prevR.natDegree

noncomputable def padeSolve {F : Type} [Field F] (e : ℕ → F) (t : ℕ) : PadeState F :=
  padeRun t (2 * t + 1) (padeInitial e t)

/-- Absolute-trace evaluation by repeated squaring, without enumeration. -/
def traceValue {F : Type} [Field F] : ℕ → F → F
  | 0, _ => 0
  | n + 1, z => traceValue n z ^ 2 + z

noncomputable def linearRoot {F : Type} [Field F] (f : F[X]) : F :=
  -f.coeff 0 / f.coeff 1

/-- A list of bit-valued splitters separates the roots of `f`. -/
def SeparatesRoots {F : Type} [Field F] (ps : List F[X]) (f : F[X]) : Prop :=
  ∀ u v : F, f.eval u = 0 → f.eval v = 0 → u ≠ v →
    ∃ p ∈ ps, p.eval u ≠ p.eval v

/-- Descend only through nonconstant factors.  At each level the two branches
are gcds with a bit-valued splitter and with that splitter minus one. -/
noncomputable def rootSearch {F : Type} [Field F] [DecidableEq F] :
    List F[X] → F[X] → List F
  | [], f => if f.natDegree = 1 then [linearRoot f] else []
  | p :: ps, f =>
      if f.natDegree = 0 then []
      else rootSearch ps (EuclideanDomain.gcd f p) ++
        rootSearch ps (EuclideanDomain.gcd f (p - 1))

/-- The actual splitter list uses only `w` basis vectors. -/
noncomputable def traceSplitters {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) : List F[X] :=
  List.ofFn (fun j : Fin w => tracePolynomial (b j) w)

/-- Evaluate the trace polynomial modulo the current factor, retaining only
coefficients below its degree after every squaring. -/
noncomputable def traceRemainder {F : Type} [Field F] (a : F) (f : F[X]) : ℕ → F[X]
  | 0 => 0
  | n + 1 => (traceRemainder a f n ^ 2 + C a * X) % f

/-- The computational root search builds no polynomial of degree `2^w`.
There are exactly `w` modular squarings per splitter evaluation. -/
noncomputable def traceRootSearch {F : Type} [Field F] [DecidableEq F] (w : ℕ) :
    List F → F[X] → List F
  | [], f => if f.natDegree = 1 then [linearRoot f] else []
  | a :: as, f =>
      if f.natDegree = 0 then [] else
      let p := traceRemainder a f w
      traceRootSearch w as (EuclideanDomain.gcd f p) ++
        traceRootSearch w as (EuclideanDomain.gcd f (p - 1))

/-- The polynomial-time root algorithm, instantiated by the basis. -/
noncomputable def rootsByBasis {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (f : F[X]) : List F :=
  traceRootSearch w (List.ofFn b) f

/-- The actual root-to-support conversion: roots must be inverted. -/
noncomputable def supportCandidate {F : Type} [Field F] [DecidableEq F]
    [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (σ : F[X]) : Finset F :=
  ((rootsByBasis b σ).map (fun u => u⁻¹)).toFinset

/-- The verifier checks the cardinality, legal positions, and all expanded
power sums.  Every check ranges over the candidate, never over the universe. -/
def CandidateVerified {F : Type} [Field F] (N t : ℕ) (ι : ℕ → F)
    (e : ℕ → F) (D : Finset F) : Prop :=
  D.card ≤ t ∧ (∀ v ∈ D, ∃ i : Fin N, ι i.val = v) ∧
    ∀ a ∈ Finset.Icc 1 (2 * t), ∑ v ∈ D, v ^ a = e (a - 1)

/-- The mathematical meaning of a test. -/
def Cond.eval : Cond → RAMState → Prop
  | .neqz r, s => s.regs r ≠ 0
  | .lt _ a b, s => s.regs a < s.regs b

section Enc

variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}

end Enc

section Tables

variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}

end Tables

section ReadInt

/-- The integer the machine reads out of the packed payload for coordinate `j`: the `w` bits of the
payload starting at position `j * w`, little-endian. -/
noncomputable def syndromeInt (w : ℕ) {M : ℕ} (y : Fin M → ZMod 2) (j : ℕ) : ℕ :=
  ∑ k ∈ Finset.range w, payloadBit y (j * w + k) * 2 ^ k

end ReadInt

section ReadLoop

/-- The memory during the read loop: the packed payload below `S0`, the syndrome entries at
`S0 + 2i` for `i < k`, and `0` elsewhere. -/
noncomputable def readMem {M : ℕ} (S0 w : ℕ) (y : Fin M → ZMod 2) (k : ℕ) : ℕ → ℕ :=
  fun addr =>
    if addr < S0 then packMem (8 * w) y addr
    else if (addr - S0) % 2 = 0 ∧ (addr - S0) / 2 < k then syndromeInt w y ((addr - S0) / 2)
    else 0

/-- The loop-head state of the read loop after `k` coordinates: the loop counter holds `k`, the
constants sit in their registers, and the scratch registers are clear. -/
noncomputable def readState (base S0 w t : ℕ) (y : Fin (t * w) → ZMod 2) (k : ℕ) : RAMState where
  pc := base
  regs := ![t, w, S0, 2 ^ w - 1, detSqBase w, k, 0, 0, 1, 0, 0, 0, 0, 0, 0, 8 * w]
  mem := readMem S0 w y k

/-- The body of the read loop: read coordinate `k` out of the packed payload, store `P_{2k+1}` at
`S0 + 2k`, advance the counter, and clear the scratch registers. -/
def readBody : List Instr :=
  mulR r7 r5 r1 ++ divR r9 r7 r15 ++ modR r10 r7 r15 ++ ld r11 r9 ++ shrR r11 r11 r10 ++
  bandR r11 r11 r3 ++ addR r6 r5 r5 ++ addR r6 r6 r2 ++ st r6 r11 ++ addR r5 r5 r8 ++
  movI r6 0 ++ movI r7 0 ++ movI r9 0 ++ movI r10 0 ++ movI r11 0 ++ movI r14 0

/-- The read loop, placed at address `base`: while `j < t`, read coordinate `j`. -/
def readLoopAt (base : ℕ) : List Instr := [iLt r14 r5 r0, iJz r14 (base + 19)] ++ readBody ++ [iJmp base]

end ReadLoop

section ProgramAt

end ProgramAt

section ReadSpec

end ReadSpec

section ReadStmt

/-- The test of the read loop: `j < t`.  An `abbrev`, so that `Cond.code.length` really is `1`. -/
abbrev readCond : Cond := Cond.lt r14 r5 r0

/-- The read loop as a statement: while `j < t`, read coordinate `j`. -/
abbrev readLoopStmt : Stmt := Stmt.loop readCond (Stmt.code readBody)

/-- The state at the entry of the loop body: the test has run, so `r14 = 1` and `pc = base + 2`. -/
noncomputable def readBodyIn (base S0 w t : ℕ) (y : Fin (t * w) → ZMod 2) (k : ℕ) : RAMState where
  pc := base + 2
  regs := Function.update (readState base S0 w t y k).regs r14 1
  mem := readMem S0 w y k

end ReadStmt

section Bounds

end Bounds

section Prologue

/-- The parameter block: `r0 = t`, `r1 = w`, `r2 = S0` (the syndrome base), `r3 = 2^w - 1` (the
field mask), `r4 = detSqBase w` (the squaring table), `r15 = 8w` (the word width), and the scratch
registers cleared. -/
def paramBody : List Instr :=
  movI r14 0 ++ tbl r0 r14 ++ movI r14 1 ++ tbl r1 r14 ++ movI r14 4 ++ tbl r2 r14 ++
  movI r14 5 ++ tbl r3 r14 ++ movI r14 6 ++ tbl r4 r14 ++ movI r14 12 ++ tbl r15 r14 ++
  movI r14 0 ++ movI r8 1

end Prologue

section ReadAssembly

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

end ReadAssembly

section Expand

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

/-- The memory during the expansion loop: the packed payload below `S0`, `enc (eSeq 2i)` at `S0+2i`
for `i < t` (the read loop's output), `enc (eSeq (2i+1))` at `S0+2i+1` for `i < k`, and `0`
elsewhere. -/
noncomputable def expandMem {w : ℕ} (S0 : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) {M : ℕ}
    (y : Fin M → ZMod 2) (t k : ℕ) : ℕ → ℕ :=
  fun addr =>
    if addr < S0 then packMem (8 * w) y addr
    else if (addr - S0) % 2 = 0 then
      if (addr - S0) / 2 < t then syndromeInt w y ((addr - S0) / 2) else 0
    else if (addr - S0) / 2 < k then enc b (eSeq b y (2 * ((addr - S0) / 2) + 1)) else 0

/-- The loop-head state of the expansion loop after `k` iterations.  Its registers are exactly the
read loop's; only the memory differs. -/
noncomputable def expandState (base S0 w t : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F)
    (y : Fin (t * w) → ZMod 2) (k : ℕ) : RAMState where
  pc := base
  regs := ![t, w, S0, 2 ^ w - 1, detSqBase w, k, 0, 0, 1, 0, 0, 0, 0, 0, 0, 8 * w]
  mem := expandMem S0 b y t k

/-- The body of the expansion loop. -/
def expandBody : List Instr :=
  addR r6 r2 r5 ++ ld r7 r6 ++ addR r9 r4 r7 ++ tbl r10 r9 ++ addR r11 r5 r5 ++
  addR r11 r11 r2 ++ addR r12 r11 r8 ++ st r12 r10 ++ addR r5 r5 r8 ++
  movI r6 0 ++ movI r7 0 ++ movI r9 0 ++ movI r10 0 ++ movI r11 0 ++ movI r12 0 ++ movI r14 0

/-- The expansion loop, placed at address `base`: while `j < t`, set `e[2j+1] = e[j]²`. -/
def expandLoopAt (base : ℕ) : List Instr := [iLt r14 r5 r0, iJz r14 (base + 19)] ++ expandBody ++ [iJmp base]

/-- The expansion loop as a statement. -/
abbrev expandLoopStmt : Stmt := Stmt.loop readCond (Stmt.code expandBody)

/-- The state at the entry of the expansion body. -/
noncomputable def expandBodyIn (base S0 w t : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F)
    (y : Fin (t * w) → ZMod 2) (k : ℕ) : RAMState where
  pc := base + 2
  regs := Function.update (expandState base S0 w t b y k).regs r14 1
  mem := expandMem S0 b y t k

end Expand

section ExpandStd

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

end ExpandStd

/-- Pair-table address offset.  This definition was missing from the extracted
base file, although it was present in the older decoder library. -/
def pairIdx (w a c : ℕ) : ℕ := a * 2 ^ w + c

/-- Field operands use registers 10 and 11; 14 and 15 are scratch registers.
Register 3 holds the field dimension. -/
def fieldMulCode : List Instr :=
  [iImm r15 1, iShl r15 r15 r3, iMul r14 r10 r15, iAdd r14 r14 r11,
    iImm r15 64, iAdd r14 r14 r15, iTbl r10 r14]

def fieldInvCode : List Instr :=
  [iImm r15 8, iTbl r15 r15, iAdd r14 r15 r10, iTbl r10 r14]

def fieldAddCode : List Instr := [iBxor r10 r10 r11]

/-- Memory after clearing exactly the first `n` words of an array. -/
def clearMem (B : ℕ) (m : ℕ → ℕ) : ℕ → ℕ → ℕ
  | 0 => m
  | n + 1 => Function.update (clearMem B m n) (B + n) 0

/-- Canonical loop-head state.  Other registers are preserved verbatim. -/
def clearState (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) : RAMState where
  pc := pc
  mem := clearMem B m j
  regs := fun d =>
    if d = r0 then j else if d = r1 then L else if d = r2 then B else
      if d = r3 then 1 else if d = r4 then 0 else
        if d = r14 then 0 else if d = r15 then 0 else r d

def clearCond : Cond := .lt r15 r0 r1

def clearBody : List Instr :=
  [iAdd r14 r2 r0, iSt r14 r4, iAdd r0 r0 r3, iImm r14 0, iImm r15 0]

def clearStmt : Stmt := .loop clearCond (.code clearBody)

/-- The reusable interface: the statement is embedded in a surrounding
program, and its entry program counter is set to the embedding address. -/
def StatementSpec (body : Stmt) (E : RAMEnv) (start : RAMState) (T : ℝ)
    (Post : RAMState → Prop) : Prop :=
  ∀ (P : Program) (base : ℕ), At P base (Stmt.compile body base) →
    Sem P E base (base + body.len) { start with pc := base }
      (fun k s' => (k : ℝ) + 1 ≤ T ∧ Post s')

/-- Compile once at zero and append the unique terminal halt. -/
def programOfStatement (body : Stmt) : Program := Stmt.compile body 0 ++ [iHalt]

/-- Zero capacity has a unique empty syndrome and is handled directly. -/
def emptyDecoderStmt : Stmt := .code [iImm r0 0, iImm r1 0, iImm r2 1]

/-- Write a prefix of an array, preserving every other address. -/
def writeArray (B : ℕ) (m : ℕ → ℕ) (f : ℕ → ℕ) : ℕ → ℕ → ℕ
  | 0 => m
  | n + 1 => Function.update (writeArray B m f n) (B + n) (f n)

noncomputable def axpyState {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (pc dst src L : ℕ) (a : F)
    (x y : ℕ → F) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) : RAMState where
  pc := pc
  mem := writeArray dst m (fun i => enc b (a * x i + y i)) j
  regs := fun d =>
    if d = r0 then j else if d = r1 then L else if d = r2 then dst else
      if d = r3 then w else if d = r4 then src else if d = r5 then enc b a else
        if d = r6 then 1 else if d = r10 then 0 else if d = r11 then 0 else
          if d = r12 then 0 else if d = r13 then 0 else
            if d = r14 then 0 else if d = r15 then 0 else r d

def axpyPrefix : List Instr := [iAdd r13 r4 r0, iLd r11 r13, iBor r10 r5 r5]

def axpyAfterMul : List Instr := [iAdd r12 r2 r0, iLd r11 r12]

def axpyTail : List Instr :=
  [iSt r12 r10, iAdd r0 r0 r6, iImm r10 0, iImm r11 0,
    iImm r12 0, iImm r13 0, iImm r14 0, iImm r15 0]

def axpyBody : List Instr := axpyPrefix ++ fieldMulCode ++ axpyAfterMul ++ fieldAddCode ++ axpyTail

def axpyCond : Cond := .lt r15 r0 r1

def axpyStmt : Stmt := .loop axpyCond (.code axpyBody)

noncomputable def degreeScan {F : Type} [Field F] [DecidableEq F] (p : F[X]) : ℕ → ℕ
  | 0 => 0
  | n + 1 => if p.coeff n = 0 then degreeScan p n else n + 1

noncomputable def scanState {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (pc B L : ℕ) (p : F[X])
    (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) : RAMState where
  pc := pc
  mem := m
  regs := fun d =>
    if d = r0 then j else if d = r1 then L else if d = r2 then degreeScan p j else
      if d = r3 then B else if d = r4 then 1 else if d = r5 then 0 else
        if d = r10 then 0 else if d = r11 then 0 else if d = r12 then 0 else
          if d = r14 then 0 else if d = r15 then 0 else r d

/-- Branch-free update: select either the old degree or `j+1` using a 0/1
flag.  All products are bounded by the array length. -/
def scanBody : List Instr :=
  [iAdd r14 r3 r0, iLd r10 r14, iLt r11 r5 r10,
    iAdd r12 r0 r4, iMul r12 r12 r11, iSub r11 r4 r11,
    iMul r2 r2 r11, iAdd r2 r2 r12, iAdd r0 r0 r4,
    iImm r10 0, iImm r11 0, iImm r12 0, iImm r14 0, iImm r15 0]

def scanCond : Cond := .lt r15 r0 r1

def scanStmt : Stmt := .loop scanCond (.code scanBody)

/-- One shifted scalar multiple cancels coefficient `deg(D)+n`. -/
noncomputable def leadingCancel {F : Type} [Field F] (D R : F[X]) (n : ℕ) : F[X] :=
  C (R.coeff (D.natDegree + n) / D.leadingCoeff) * X ^ n

/-- Coupled row reduction: the same scalar/shift is applied to a remainder
row and its extended-Euclidean coefficient row.  No polynomial product of two
variable rows is needed in the RAM implementation. -/
noncomputable def longReduceRows {F : Type} [Field F] (D C : F[X]) :
    ℕ → F[X] → F[X] → F[X] × F[X]
  | 0, R, U => (R, U)
  | n + 1, R, U =>
      let T := leadingCancel D R n
      longReduceRows D C n (R - T * D) (U - T * C)

def copyState (pc dst src L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) : RAMState where
  pc := pc
  mem := writeArray dst m (fun i => m (src + i)) j
  regs := fun d =>
    if d = r0 then j else if d = r1 then L else if d = r2 then dst else
      if d = r3 then src else if d = r4 then 1 else if d = r10 then 0 else
        if d = r12 then 0 else if d = r13 then 0 else if d = r15 then 0 else r d

def copyCond : Cond := .lt r15 r0 r1

def copyBody : List Instr :=
  [iAdd r13 r3 r0, iLd r10 r13, iAdd r12 r2 r0, iSt r12 r10,
    iAdd r0 r0 r4, iImm r10 0, iImm r12 0, iImm r13 0, iImm r15 0]

def copyStmt : Stmt := .loop copyCond (.code copyBody)

def zeroRegsCode : List Instr :=
  [iImm r0 0, iImm r1 0, iImm r2 0, iImm r3 0, iImm r4 0, iImm r5 0, iImm r6 0, iImm r7 0, iImm r8 0, iImm r9 0, iImm r10 0, iImm r11 0, iImm r12 0, iImm r13 0, iImm r14 0, iImm r15 0]

/-- Fixed argument slots 64..68: destination, source, length, dimension,
and field scalar.  Array workspaces are kept above these slots. -/
def axpyArgsCode : List Instr :=
  [iImm r15 64, iLd r2 r15, iImm r15 65, iLd r4 r15,
    iImm r15 66, iLd r1 r15, iImm r15 67, iLd r3 r15,
    iImm r15 68, iLd r5 r15, iImm r6 1, iImm r15 0]

def axpyProcedure : Stmt := .seq (.code axpyArgsCode) (.seq axpyStmt (.code zeroRegsCode))

def metaReadCode (d : Fin 16) (addr : ℕ) : List Instr :=
  [iImm r15 addr, iLd d r15, iImm r15 0]

def metaStoreCode (d : Fin 16) (addr : ℕ) : List Instr :=
  [iImm r15 addr, iSt r15 d, iImm r15 0]

/-- Arguments shared by array procedures.  Slots 69 and above belong to the
caller and are unaffected by this argument preparation. -/
def rowArguments (m : ℕ → ℕ) (dst src L w scalar : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update
    (Function.update m 68 scalar) 64 dst) 65 src) 66 L) 67 w

def longDivReadCode : List Instr :=
  metaReadCode r2 72 ++ metaReadCode r4 74 ++ metaReadCode r9 71 ++
    metaReadCode r12 69 ++ metaReadCode r11 70 ++ metaReadCode r3 77 ++
    [iImm r6 1, iSub r9 r9 r6, iAdd r2 r2 r9, iAdd r13 r2 r12, iLd r10 r13]

def longDivWriteCode : List Instr :=
  metaStoreCode r10 68 ++ metaStoreCode r2 64 ++ metaStoreCode r4 65 ++
    metaReadCode r1 76 ++ metaStoreCode r1 66 ++ metaStoreCode r3 67

def longDivPrepareCode : List Instr :=
  longDivReadCode ++ fieldMulCode ++ longDivWriteCode ++ zeroRegsCode

def shiftedArgumentsCode (dstSlot srcSlot : ℕ) : List Instr :=
  metaReadCode r2 dstSlot ++ metaReadCode r4 srcSlot ++ metaReadCode r9 71 ++
    [iImm r6 1, iSub r9 r9 r6, iAdd r2 r2 r9] ++
    metaStoreCode r2 64 ++ metaStoreCode r4 65 ++ zeroRegsCode

def rankState (pc : ℕ) (m : ℕ → ℕ) (n : ℕ) : RAMState :=
  { boundaryState pc m with regs := Function.update (fun _ => 0) r9 n }

def longDivTailCode : List Instr :=
  metaReadCode r9 71 ++ [iImm r6 1, iSub r9 r9 r6] ++ metaStoreCode r9 71 ++
    zeroRegsCode ++ metaReadCode r9 71

def longDivBodyStmt : Stmt :=
  .seq (.code longDivPrepareCode) (.seq axpyProcedure
    (.seq (.code (shiftedArgumentsCode 73 75)) (.seq axpyProcedure (.code longDivTailCode))))

def longDivStmt : Stmt := .loop (.neqz r9) longDivBodyStmt

/-- Budget for the saved syndrome, polynomial rows, two root queues, and
verification/output buffers.  All metadata lives below address 128. -/
def decoderWorkspaceEnd (t : ℕ) : ℕ := 8 * t * t + 64 * t + 160

/-- Separation of the four Euclidean row buffers from metadata and from one
another.  The pointers may be exchanged between Euclidean iterations. -/
structure RowsLayout (R U D C cap : ℕ) : Prop where
  Rlow : 128 ≤ R
  Ulow : 128 ≤ U
  Dlow : 128 ≤ D
  Clow : 128 ≤ C
  RU : R + cap ≤ U ∨ U + cap ≤ R
  RD : R + cap ≤ D ∨ D + cap ≤ R
  RC : R + cap ≤ C ∨ C + cap ≤ R
  UD : U + cap ≤ D ∨ D + cap ≤ U
  UC : U + cap ≤ C ∨ C + cap ≤ U
  DC : D + cap ≤ C ∨ C + cap ≤ D

/-- Concrete memory transformation of one paired row update. -/
noncomputable def rowIterationMemory {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (RB UB DB CB n L : ℕ)
    (R U D C : F[X]) : ℕ → ℕ :=
  let a := R.coeff (D.natDegree + n) * D.leadingCoeff⁻¹
  let m1 := rowArguments m (RB + n) DB L w (enc b a)
  let m2 := writeArray (RB + n) m1 (fun i => enc b (a * D.coeff i + R.coeff (n + i))) L
  let m3 := Function.update (Function.update m2 64 (UB + n)) 65 CB
  let m4 := writeArray (UB + n) m3 (fun i => enc b (a * C.coeff i + U.coeff (n + i))) L
  Function.update m4 71 n

/-- Addresses which the paired division procedure may overwrite. -/
def divisionWritable (RB UB cap addr : ℕ) : Prop :=
  (64 ≤ addr ∧ addr ≤ 68) ∨ addr = 71 ∨
    (RB ≤ addr ∧ addr < RB + cap) ∨ (UB ≤ addr ∧ addr < UB + cap)

/-- Persistent metadata for one polynomial division. -/
structure RowCache {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (D : F[X]) (RB UB DB CB L : ℕ)
    (m : ℕ → ℕ) (n : ℕ) : Prop where
  degree : m 69 = D.natDegree
  inverse : m 70 = enc b D.leadingCoeff⁻¹
  count : m 71 = n
  prevR : m 72 = RB
  prevC : m 73 = UB
  curR : m 74 = DB
  curC : m 75 = CB
  length : m 76 = L
  dim : m 77 = w

/-- The remaining mathematical computation is constant throughout the loop.
Every memory update is tied to a real polynomial row update. -/
def longDivInvariant {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (RB UB DB CB L cap n0 : ℕ)
    (R0 U0 D C : F[X]) (initial : ℕ → ℕ) (n : ℕ) (s : RAMState) : Prop :=
  s.regs = Function.update (fun _ => 0) r9 n ∧
  RowCache b D RB UB DB CB L s.mem n ∧ n ≤ n0 ∧
  MemoryFrame (divisionWritable RB UB cap) initial s.mem ∧
  ∃ R U : F[X], PolynomialStored b s.mem RB cap R ∧ PolynomialStored b s.mem UB cap U ∧
    PolynomialStored b s.mem DB cap D ∧ PolynomialStored b s.mem CB cap C ∧
    R.natDegree < D.natDegree + n ∧ longReduceRows D C n R U = longReduceRows D C n0 R0 U0

def longDivProcedure : Stmt := .seq (.code (metaReadCode r9 71)) longDivStmt

/-- Degree scanning reads the array pointer from slot 64 and length from 66.
The result at 95 is zero for a zero polynomial, and degree+1 otherwise. -/
def scanArgsCode : List Instr :=
  [iImm r15 64, iLd r3 r15, iImm r15 66, iLd r1 r15, iImm r4 1, iImm r15 0]

def scanReturnCode : List Instr := metaStoreCode r2 95 ++ zeroRegsCode

def scanProcedure : Stmt := .seq (.code scanArgsCode) (.seq scanStmt (.code scanReturnCode))

/-- Copying uses the common argument slots and returns without register data. -/
def copyArgsCode : List Instr :=
  [iImm r15 64, iLd r2 r15, iImm r15 65, iLd r3 r15,
    iImm r15 66, iLd r1 r15, iImm r4 1, iImm r15 0]

def copyProcedure : Stmt := .seq (.code copyArgsCode) (.seq copyStmt (.code zeroRegsCode))

/-- Select one of the Euclidean row pointers for a full coefficient scan. -/
def scanSetupCode (slot : ℕ) : List Instr :=
  metaReadCode r2 slot ++ metaReadCode r1 81 ++
    metaStoreCode r2 64 ++ metaStoreCode r1 66 ++ zeroRegsCode

def cacheDivisorReadCode : List Instr :=
  metaReadCode r0 95 ++ [iImm r6 1, iSub r0 r0 r6] ++ metaStoreCode r0 69 ++
    metaReadCode r2 74 ++ [iAdd r2 r2 r0, iLd r10 r2] ++ metaReadCode r3 77

def cacheDivisorCode : List Instr :=
  cacheDivisorReadCode ++ fieldInvCode ++ metaStoreCode r10 70 ++ zeroRegsCode

def divisionCountCode : List Instr :=
  metaReadCode r9 95 ++ metaReadCode r0 69 ++ [iSub r9 r9 r0] ++
    metaStoreCode r9 71 ++ zeroRegsCode

/-- Exchange consecutive Euclidean rows without moving array contents. -/
def swapRowMemory (m : ℕ → ℕ) (RB UB DB CB : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update m 72 DB) 73 CB) 74 RB) 75 UB

def swapRowsCode : List Instr :=
  metaReadCode r0 72 ++ metaReadCode r1 73 ++ metaReadCode r2 74 ++ metaReadCode r3 75 ++
    metaStoreCode r2 72 ++ metaStoreCode r3 73 ++ metaStoreCode r0 74 ++ metaStoreCode r1 75 ++
      zeroRegsCode

/-- Row locations and the persistent arguments of the Euclidean solver. -/
structure PadeRows {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv)
    (RB UB DB CB L cap : ℕ) (m : ℕ → ℕ) (s : PadeState F) : Prop where
  layout : RowsLayout RB UB DB CB cap
  Rword : RB + cap ≤ 2 ^ E.W
  Uword : UB + cap ≤ 2 ^ E.W
  Dword : DB + cap ≤ 2 ^ E.W
  Cword : CB + cap ≤ 2 ^ E.W
  prevR : PolynomialStored b m RB cap s.prevR
  prevC : PolynomialStored b m UB cap s.prevC
  rem : PolynomialStored b m DB cap s.rem
  curC : PolynomialStored b m CB cap s.curC
  ptr72 : m 72 = RB
  ptr73 : m 73 = UB
  ptr74 : m 74 = DB
  ptr75 : m 75 = CB
  length : m 76 = L
  dimension : m 77 = w
  capacity : m 81 = cap

/-- Scratch slots of a single quotient calculation, excluding row pointers. -/
def padeScratch (addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 66 ∨ addr = 69 ∨ addr = 70 ∨ addr = 71 ∨ addr = 95

/-- Fixed metadata or one of the four polynomial rows may change. -/
def padeWritable (RB UB DB CB cap addr : ℕ) : Prop := (64 ≤ addr ∧ addr ≤ 75) ∨ addr = 95 ∨
  (RB ≤ addr ∧ addr < RB + cap) ∨ (UB ≤ addr ∧ addr < UB + cap) ∨
  (DB ≤ addr ∧ addr < DB + cap) ∨ (CB ≤ addr ∧ addr < CB + cap)

/-- One positive-degree Euclidean quotient step.  The current row has
already been scanned when this procedure is called. -/
def padeQuotientProcedure : Stmt :=
  .seq (.code cacheDivisorCode) (.seq (.code (scanSetupCode 72))
    (.seq scanProcedure (.seq (.code divisionCountCode)
      (.seq longDivProcedure (.code swapRowsCode)))))

noncomputable def padeTick {F : Type} [Field F] (t : ℕ) (s : PadeState F) : PadeState F :=
  if s.rem.natDegree < t then s else padeNext s

def padeTestLoadCode : List Instr := metaReadCode r0 80 ++ metaReadCode r1 95

def padeTestState (pc : ℕ) (m : ℕ → ℕ) (t d : ℕ) : RAMState :=
  { boundaryState pc m with regs := Function.update (Function.update (fun _ => 0) r0 t) r1 d }

def padeSelectStmt : Stmt := .seq (.code padeTestLoadCode)
  (.ite (.lt r15 r0 r1) (.seq (.code zeroRegsCode) padeQuotientProcedure) (.code zeroRegsCode))

/-- Semantic result shared by the two branches of a padded Euclidean step. -/
def PadeAdvance {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv)
    (RB UB DB CB L cap : ℕ) (before after : ℕ → ℕ) (s : PadeState F) : Prop :=
  ∃ RB' UB' DB' CB', PadeRows b E RB' UB' DB' CB' L cap after s ∧
    MemoryFrame (padeWritable RB UB DB CB cap) before after ∧
    ∀ addr, padeWritable RB' UB' DB' CB' cap addr ↔ padeWritable RB UB DB CB cap addr

/-- A padded Euclidean iteration first scans the current remainder. -/
def padeStepProcedure : Stmt := .seq (.code (scanSetupCode 74)) (.seq scanProcedure padeSelectStmt)

/-- A general counted-procedure tail. -/
def countdownCode (slot : ℕ) : List Instr :=
  metaReadCode r9 slot ++ [iImm r6 1, iSub r9 r9 r6] ++ metaStoreCode r9 slot ++
    zeroRegsCode ++ metaReadCode r9 slot

def padeLoopWritable (RB UB DB CB cap addr : ℕ) : Prop :=
  addr = 94 ∨ padeWritable RB UB DB CB cap addr

/-- A whole Euclidean iteration followed by a decreasing outer counter. -/
def padeLoopBody : Stmt :=
  .seq (.code zeroRegsCode) (.seq padeStepProcedure (.code (countdownCode 94)))

def padeLoopStmt : Stmt := .loop (.neqz r9) padeLoopBody

/-- The remaining abstract computation stays fixed during all RAM iterations. -/
def padeLoopInvariant {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv)
    (RB UB DB CB L cap : ℕ) (e : ℕ → F) (t : ℕ)
    (target : PadeState F) (initial : ℕ → ℕ) (n : ℕ) (z : RAMState) : Prop :=
  z.regs = Function.update (fun _ => 0) r9 n ∧ z.mem 94 = n ∧ z.mem 80 = t ∧
  MemoryFrame (padeLoopWritable RB UB DB CB cap) initial z.mem ∧
  ∃ RB' UB' DB' CB' s, PadeRows b E RB' UB' DB' CB' L cap z.mem s ∧ PadeInv e t s ∧
    padeRun t n s = target ∧
    ∀ addr, padeWritable RB' UB' DB' CB' cap addr ↔ padeWritable RB UB DB CB cap addr

def padeSolveProcedure : Stmt := .seq (.code (metaReadCode r9 94)) padeLoopStmt

noncomputable def squareState {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (pc dst src cap : ℕ) (p : F[X])
    (m : ℕ → ℕ) (r : Fin 16 → ℕ) (k : ℕ) : RAMState where
  pc := pc
  mem := writeArray dst m (fun i => enc b ((p ^ 2).coeff i)) k
  regs := fun d =>
    if d = r0 then k else if d = r1 then cap else if d = r2 then dst else
      if d = r3 then src else if d = r4 then 1 else if d = r5 then 2 else
        if d = r6 then detSqBase w else if d = r10 then 0 else if d = r11 then 0 else
          if d = r12 then 0 else if d = r15 then 0 else r d

def squareCond : Cond := .lt r15 r0 r1

/-- Read coefficient k/2, square it in the field table, and mask odd positions. -/
def squareBody : List Instr :=
  [iDiv r11 r0 r5, iAdd r12 r3 r11, iLd r10 r12, iAdd r12 r6 r10,
    iTbl r10 r12, iMod r11 r0 r5, iSub r11 r4 r11, iMul r10 r10 r11,
    iAdd r12 r2 r0, iSt r12 r10, iAdd r0 r0 r4,
    iImm r10 0, iImm r11 0, iImm r12 0, iImm r15 0]

def squareStmt : Stmt := .loop squareCond (.code squareBody)

def squareArgsCode : List Instr :=
  [iImm r15 64, iLd r2 r15, iImm r15 65, iLd r3 r15, iImm r15 66, iLd r1 r15,
    iImm r4 1, iImm r5 2, iImm r15 6, iTbl r6 r15, iImm r15 0]

def squareProcedure : Stmt := .seq (.code squareArgsCode) (.seq squareStmt (.code zeroRegsCode))

/-- Use a uniform coefficient bound as division fuel.  This also covers a
zero or lower-degree dividend without unsigned-subtraction corner cases. -/
def divisionFullFuelCode : List Instr :=
  metaReadCode r9 76 ++ metaStoreCode r9 71 ++ zeroRegsCode

def polynomialModuloProcedure : Stmt :=
  .seq (.code cacheDivisorCode) (.seq (.code divisionFullFuelCode) longDivProcedure)

noncomputable def reducedPadeRows {F : Type} [Field F] (s : PadeState F) : PadeState F :=
  ⟨s.prevR % s.rem, s.prevC - (s.prevR / s.rem) * s.curC, s.rem, s.curC⟩

/-- Add `a X` to a freshly squared polynomial by filling its odd slot 1. -/
def traceAddXCode : List Instr :=
  metaReadCode r2 64 ++ [iImm r6 1, iAdd r2 r2 r6] ++ metaReadCode r10 96 ++
    [iSt r2 r10] ++ zeroRegsCode

def traceSquareProcedure : Stmt := .seq squareProcedure (.code traceAddXCode)

def gcdQuotientProcedure : Stmt := .seq polynomialModuloProcedure (.code swapRowsCode)

/-- At a constant remainder, Euclidean gcd needs no further division. -/
noncomputable def gcdFinish {F : Type} [Field F] [DecidableEq F] (s : PadeState F) : F[X] :=
  if s.rem = 0 then s.prevR else s.rem

def GcdInv {F : Type} [Field F] (L : ℕ) (s : PadeState F) : Prop :=
  s.prevR.natDegree < L ∧ s.rem.natDegree < L ∧ s.prevC = 0 ∧ s.curC = 0

def gcdTestLoadCode : List Instr := metaReadCode r1 95 ++ [iImm r0 1]

def gcdSelectStmt : Stmt := .seq (.code gcdTestLoadCode)
  (.ite (.lt r15 r0 r1) (.seq (.code zeroRegsCode) gcdQuotientProcedure) (.code zeroRegsCode))

def gcdStepProcedure : Stmt := .seq (.code (scanSetupCode 74)) (.seq scanProcedure gcdSelectStmt)

def gcdLoopWritable (RB UB DB CB cap addr : ℕ) : Prop := addr = 93 ∨ padeWritable RB UB DB CB cap addr

def gcdLoopBody : Stmt := .seq (.code zeroRegsCode) (.seq gcdStepProcedure (.code (countdownCode 93)))

def gcdLoopStmt : Stmt := .loop (.neqz r9) gcdLoopBody

def gcdLoopInvariant {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (RB UB DB CB L cap : ℕ)
    (target : PadeState F) (initial : ℕ → ℕ) (n : ℕ) (z : RAMState) : Prop :=
  z.regs = Function.update (fun _ => 0) r9 n ∧ z.mem 93 = n ∧
  MemoryFrame (gcdLoopWritable RB UB DB CB cap) initial z.mem ∧
  ∃ RB' UB' DB' CB' s, PadeRows b E RB' UB' DB' CB' L cap z.mem s ∧ GcdInv L s ∧
    padeRun 1 n s = target ∧
    ∀ addr, padeWritable RB' UB' DB' CB' cap addr ↔ padeWritable RB UB DB CB cap addr

def gcdSolveProcedure : Stmt := .seq (.code (metaReadCode r9 93)) gcdLoopStmt

/-- The final scan is either 0 (return previous row) or 1 (return the constant
current row).  Return its pointer at slot 97. -/
def gcdReturnCode : List Instr :=
  metaReadCode r2 72 ++ metaReadCode r3 74 ++ metaReadCode r0 95 ++
    [iImm r6 1, iSub r1 r6 r0, iMul r2 r2 r1, iMul r3 r3 r0, iAdd r2 r2 r3] ++
    metaStoreCode r2 97 ++ zeroRegsCode

def gcdReturnProcedure : Stmt :=
  .seq (.code (scanSetupCode 74)) (.seq scanProcedure (.code gcdReturnCode))

def gcdProcedureWritable (RB UB DB CB cap addr : ℕ) : Prop := addr = 97 ∨ gcdLoopWritable RB UB DB CB cap addr

def gcdProcedure : Stmt := .seq gcdSolveProcedure gcdReturnProcedure

def arrayArguments (m : ℕ → ℕ) (dst src len : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update m 64 dst) 65 src) 66 len

def arraySetupCode (dstSlot srcSlot : ℕ) : List Instr :=
  metaReadCode r2 dstSlot ++ metaReadCode r3 srcSlot ++ metaReadCode r1 81 ++
    metaStoreCode r2 64 ++ metaStoreCode r3 65 ++ metaStoreCode r1 66 ++ zeroRegsCode

def traceWritable (RB UB DB CB TB cap addr : ℕ) : Prop :=
  padeWritable RB UB DB CB cap addr ∨ (TB ≤ addr ∧ addr < TB + cap)

def traceStepProcedure : Stmt :=
  .seq (.code (arraySetupCode 72 98)) (.seq traceSquareProcedure
    (.seq polynomialModuloProcedure (.seq (.code (arraySetupCode 98 72)) copyProcedure)))

def traceLoopWritable (RB UB DB CB TB cap addr : ℕ) : Prop := addr = 92 ∨ traceWritable RB UB DB CB TB cap addr

def traceLoopBody : Stmt := .seq (.code zeroRegsCode) (.seq traceStepProcedure (.code (countdownCode 92)))

def traceLoopStmt : Stmt := .loop (.neqz r9) traceLoopBody

def traceProcedure : Stmt := .seq (.code (metaReadCode r9 92)) traceLoopStmt

/-- Only positive-degree factors occupy slots in a root frontier. -/
noncomputable def keepFactor {F : Type} [Field F] (f : F[X]) : List F[X] :=
  if f.natDegree = 0 then [] else [f]

noncomputable def splitFrontier {F : Type} [Field F] [DecidableEq F] (w : ℕ) (a : F) : List F[X] → List F[X]
  | [] => []
  | f :: fs => if f.natDegree = 0 then splitFrontier w a fs else
      (keepFactor (EuclideanDomain.gcd f (traceRemainder a f w)) ++
        keepFactor (EuclideanDomain.gcd f (traceRemainder a f w - 1))) ++ splitFrontier w a fs

noncomputable def rootForest {F : Type} [Field F] [DecidableEq F] (w : ℕ) (as : List F) (fs : List F[X]) : List F :=
  fs.flatMap (traceRootSearch w as)

def frontierMass {F : Type} [Field F] : List F[X] → ℕ
  | [] => 0
  | f :: fs => f.natDegree + frontierMass fs

/-- Basis vector j has the machine spelling 2^j, independent of the basis. -/
def basisScalarCode : List Instr :=
  metaReadCode r3 88 ++ [iImm r10 1, iShl r10 r10 r3] ++ metaStoreCode r10 96 ++ zeroRegsCode

def imageZeroCode : List Instr := [iImm r15 10, iTbl r14 r15, iTbl r10 r14]

/-- Obtain the encoded field unit from a known nonzero image element.
The natural number 1 need not encode the field unit in the supplied basis. -/
def cacheUnitCode : List Instr :=
  metaReadCode r3 77 ++ imageZeroCode ++ fieldInvCode ++ [iBor r11 r10 r10] ++
    imageZeroCode ++ fieldMulCode ++ metaStoreCode r10 78 ++ zeroRegsCode

/-- Conditional call after scanning a polynomial.  Constants and zero rows
skip the call; only positive-degree rows invoke the body. -/
def degreeBranch (body : Stmt) : Stmt := .seq (Stmt.code gcdTestLoadCode)
  (.ite (.lt r15 r0 r1) (Stmt.seq (Stmt.code zeroRegsCode) body) (Stmt.code zeroRegsCode))

/-- Consecutive fixed-capacity coefficient arrays for the frontier factors. -/
def FrontierStored {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (B cap : ℕ) (fs : List F[X]) : Prop :=
  ∀ j < fs.length, PolynomialStored b m (B + j * cap) cap (fs.getD j 0)

/-- Queue count, queue base, polynomial capacity and source pointer are read
from 90, 84, 81 and 97. -/
def queueAppendArgsCode : List Instr :=
  metaReadCode r2 84 ++ metaReadCode r0 90 ++ metaReadCode r1 81 ++
    [iMul r0 r0 r1, iAdd r2 r2 r0] ++ metaReadCode r3 97 ++
    metaStoreCode r2 64 ++ metaStoreCode r3 65 ++ metaStoreCode r1 66 ++ zeroRegsCode

def queueIncrementCode : List Instr :=
  metaReadCode r9 90 ++ [iImm r6 1, iAdd r9 r9 r6] ++ metaStoreCode r9 90 ++ zeroRegsCode

def queueAppendProcedure : Stmt :=
  .seq (.code queueAppendArgsCode) (.seq copyProcedure (.code queueIncrementCode))

def queueAppendWritable (B n cap addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 65 ∨ addr = 66 ∨ addr = 90 ∨ (B + n * cap ≤ addr ∧ addr < B + n * cap + cap)

/-- Scan a computed factor, drop constants, and append positive-degree factors. -/
def queueKeepProcedure : Stmt :=
  .seq (.code (scanSetupCode 97)) (.seq scanProcedure (degreeBranch queueAppendProcedure))

def queueKeepWritable (B n cap degree addr : ℕ) : Prop :=
  addr = 95 ∨ addr = 64 ∨ addr = 65 ∨ addr = 66 ∨ addr = 90 ∨
    (0 < degree ∧ B + n * cap ≤ addr ∧ addr < B + n * cap + cap)

def copyMetaCode (src dst : ℕ) : List Instr :=
  metaReadCode r0 src ++ metaStoreCode r0 dst ++ zeroRegsCode

def setMetaCode (slot value : ℕ) : List Instr := [iImm r0 value] ++ metaStoreCode r0 slot ++ zeroRegsCode

def copyFromSlotsProcedure (dstSlot srcSlot : ℕ) : Stmt :=
  .seq (.code (arraySetupCode dstSlot srcSlot)) copyProcedure

def copyFromSlotsWritable (dst cap addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 65 ∨ addr = 66 ∨ (dst ≤ addr ∧ addr < dst + cap)

/-- Restore the fixed root-workspace row pointers from slots 102..105.
Slots 102/103 are the polynomial rows and 104/105 the zero coefficient rows. -/
def resetRootRowsCode : List Instr :=
  metaReadCode r0 102 ++ metaReadCode r1 104 ++ metaReadCode r2 103 ++ metaReadCode r3 105 ++
    metaStoreCode r0 72 ++ metaStoreCode r1 73 ++ metaStoreCode r2 74 ++ metaStoreCode r3 75 ++ zeroRegsCode

/-- The root routines use four Euclidean rows, a trace buffer, and an
independent zero buffer.  The zero buffer is never a destination. -/
structure RootWorkspace (R U D C TB ZB cap : ℕ) : Prop where
  rows : RowsLayout R U D C cap
  Tlow : 128 ≤ TB
  Zlow : 128 ≤ ZB
  TR : TB + cap ≤ R ∨ R + cap ≤ TB
  TU : TB + cap ≤ U ∨ U + cap ≤ TB
  TD : TB + cap ≤ D ∨ D + cap ≤ TB
  TC : TB + cap ≤ C ∨ C + cap ≤ TB
  ZR : ZB + cap ≤ R ∨ R + cap ≤ ZB
  ZU : ZB + cap ≤ U ∨ U + cap ≤ ZB
  ZD : ZB + cap ≤ D ∨ D + cap ≤ ZB
  ZC : ZB + cap ≤ C ∨ C + cap ≤ ZB
  ZT : ZB + cap ≤ TB ∨ TB + cap ≤ ZB

def rootComputeMeta (addr : ℕ) : Prop :=
  (64 ≤ addr ∧ addr ≤ 75) ∨ addr = 92 ∨ addr = 93 ∨ addr = 95 ∨ addr = 97 ∨ addr = 98

def rootComputeWritable (R U D C TB cap addr : ℕ) : Prop := rootComputeMeta addr ∨
  (R ≤ addr ∧ addr < R + cap) ∨ (U ≤ addr ∧ addr < U + cap) ∨
  (D ≤ addr ∧ addr < D + cap) ∨ (C ≤ addr ∧ addr < C + cap) ∨ (TB ≤ addr ∧ addr < TB + cap)

def rootNodeMeta (addr : ℕ) : Prop := addr = 90 ∨ rootComputeMeta addr

def rootNodeWritable (R U D C TB cap QB T addr : ℕ) : Prop :=
  addr = 90 ∨ rootComputeWritable R U D C TB cap addr ∨ (QB ≤ addr ∧ addr < QB + T * cap)

/-- Immutable arguments shared by both gcd branches of a root node. -/
structure RootPersistent {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (R U D C TB ZB cap L src : ℕ)
    (f : F[X]) (a : F) (m : ℕ → ℕ) : Prop where
  length : m 76 = L
  dimension : m 77 = w
  unit : m 78 = enc b 1
  capacity : m 81 = cap
  scalar : m 96 = enc b a
  source : m 99 = src
  fixedR : m 102 = R
  fixedD : m 103 = D
  fixedU : m 104 = U
  fixedC : m 105 = C
  fixedT : m 106 = TB
  fixedZ : m 108 = ZB
  factor : PolynomialStored b m src cap f
  zero : PolynomialStored b m ZB cap 0

def resetRootMemory (m : ℕ → ℕ) (R U D C : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update m 72 R) 73 U) 74 D) 75 C

structure RootWords (E : RAMEnv) (R U D C TB ZB cap : ℕ) : Prop where
  Rword : R + cap ≤ 2 ^ E.W
  Uword : U + cap ≤ 2 ^ E.W
  Dword : D + cap ≤ 2 ^ E.W
  Cword : C + cap ≤ 2 ^ E.W
  Tword : TB + cap ≤ 2 ^ E.W
  Zword : ZB + cap ≤ 2 ^ E.W

structure RootSourceSeparated (R U D C TB cap src : ℕ) : Prop where
  SR : src + cap ≤ R ∨ R + cap ≤ src
  SU : src + cap ≤ U ∨ U + cap ≤ src
  SD : src + cap ≤ D ∨ D + cap ≤ src
  SC : src + cap ≤ C ∨ C + cap ≤ src
  ST : src + cap ≤ TB ∨ TB + cap ≤ src

/-- Prepare all work arrays from the old queue and the permanent zero row.
No polynomial data is assumed to survive an earlier gcd call. -/
def rootPrepareProcedure : Stmt :=
  .seq (.code resetRootRowsCode)
    (.seq (copyFromSlotsProcedure 103 99)
      (.seq (copyFromSlotsProcedure 102 108)
        (.seq (copyFromSlotsProcedure 104 108)
          (.seq (copyFromSlotsProcedure 105 108)
            (.seq (copyFromSlotsProcedure 106 108)
              (.seq (.code (copyMetaCode 106 98))
                (.seq (.code (scanSetupCode 74))
                  (.seq scanProcedure (.code (copyMetaCode 77 92))))))))))

def rootTraceProcedure : Stmt := .seq rootPrepareProcedure traceProcedure

def rootFirstGcdProcedure : Stmt :=
  .seq (.code swapRowsCode) (.seq (.code (copyMetaCode 76 93)) gcdProcedure)

def toggleReadCode (slot : ℕ) : List Instr :=
  metaReadCode r2 slot ++ [iLd r10 r2] ++ metaReadCode r11 78

def toggleConstantCode (slot : ℕ) : List Instr :=
  toggleReadCode slot ++ [iBxor r10 r10 r11, iSt r2 r10] ++ zeroRegsCode

def rootSecondPrepareProcedure : Stmt :=
  .seq (.code resetRootRowsCode)
    (.seq (copyFromSlotsProcedure 102 99)
      (.seq (copyFromSlotsProcedure 103 106)
        (.seq (copyFromSlotsProcedure 104 108)
          (.seq (copyFromSlotsProcedure 105 108) (.code (toggleConstantCode 103))))))

def rootSecondGcdProcedure : Stmt :=
  .seq rootSecondPrepareProcedure (.seq (.code (copyMetaCode 76 93)) gcdProcedure)

structure QueueWorkspaceSeparated (R U D C TB ZB cap QB T : ℕ) : Prop where
  QR : QB + T * cap ≤ R ∨ R + cap ≤ QB
  QU : QB + T * cap ≤ U ∨ U + cap ≤ QB
  QD : QB + T * cap ≤ D ∨ D + cap ≤ QB
  QC : QB + T * cap ≤ C ∨ C + cap ≤ QB
  QT : QB + T * cap ≤ TB ∨ TB + cap ≤ QB
  QZ : QB + T * cap ≤ ZB ∨ ZB + cap ≤ QB

def wholeQueueWritable (QB T cap addr : ℕ) : Prop :=
  addr = 95 ∨ addr = 64 ∨ addr = 65 ∨ addr = 66 ∨ addr = 90 ∨ (QB ≤ addr ∧ addr < QB + T * cap)

def rootNodeProcedure : Stmt := .seq rootTraceProcedure
  (.seq rootFirstGcdProcedure (.seq queueKeepProcedure (.seq rootSecondGcdProcedure queueKeepProcedure)))

/-- Arguments independent of which old-queue factor is currently processed. -/
structure RootEnvironment {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (R U D C TB ZB cap L : ℕ) (a : F) (m : ℕ → ℕ) : Prop where
  length : m 76 = L
  dimension : m 77 = w
  unit : m 78 = enc b 1
  capacity : m 81 = cap
  scalar : m 96 = enc b a
  fixedR : m 102 = R
  fixedD : m 103 = D
  fixedU : m 104 = U
  fixedC : m 105 = C
  fixedT : m 106 = TB
  fixedZ : m 108 = ZB
  zero : PolynomialStored b m ZB cap 0

def rootLevelMeta (addr : ℕ) : Prop := addr = 91 ∨ addr = 99 ∨ addr = 111 ∨ rootNodeMeta addr

def rootLevelWritable (R U D C TB cap QB T addr : ℕ) : Prop :=
  addr = 91 ∨ addr = 99 ∨ addr = 111 ∨ rootNodeWritable R U D C TB cap QB T addr

def queueReadPointerCode : List Instr :=
  metaReadCode r2 83 ++ metaReadCode r0 91 ++ metaReadCode r1 81 ++
    [iMul r0 r0 r1, iAdd r2 r2 r0] ++ metaStoreCode r2 99 ++ zeroRegsCode

def incrementMetaCode (slot : ℕ) : List Instr :=
  metaReadCode r9 slot ++ [iImm r6 1, iAdd r9 r9 r6] ++ metaStoreCode r9 slot ++ zeroRegsCode

def rootLevelTailCode : List Instr := incrementMetaCode 91 ++ countdownCode 111

def rootNodeBudget (cap L w : ℕ) : ℕ :=
  (30 * cap + (48 * L + 187) * L + 258) * w +
    2 * ((17 * cap + (48 * L + 187) * L + 228) * L) + 217 * cap + 1350

/-- The two queues and counters at an inner frontier-loop boundary. -/
structure RootLevelView {F : Type} [Field F] [Algebra (ZMod 2) F] [DecidableEq F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (R U D C TB ZB cap L BQ QB : ℕ)
    (a : F) (fs done pending : List F[X]) (m : ℕ → ℕ) : Prop where
  environment : RootEnvironment b R U D C TB ZB cap L a m
  oldQueue : FrontierStored b m BQ cap fs
  newQueue : FrontierStored b m QB cap (splitFrontier w a done)
  oldBase : m 83 = BQ
  newBase : m 84 = QB
  oldCount : m 89 = fs.length
  newCount : m 90 = (splitFrontier w a done).length
  index : m 91 = done.length
  remaining : m 111 = pending.length

def rootLevelBody : Stmt := .seq (.code queueReadPointerCode)
  (.seq rootNodeProcedure (.code rootLevelTailCode))

def rootLevelLoop : Stmt := .loop (.neqz r9) rootLevelBody

def rootLevelProcedure : Stmt := .seq (.code (metaReadCode r9 111)) rootLevelLoop

/-- Scalar-free root arguments survive changes of the basis splitter. -/
structure RootConstants {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (R U D C TB ZB cap L : ℕ) (m : ℕ → ℕ) : Prop where
  length : m 76 = L
  dimension : m 77 = w
  unit : m 78 = enc b 1
  capacity : m 81 = cap
  fixedR : m 102 = R
  fixedD : m 103 = D
  fixedU : m 104 = U
  fixedC : m 105 = C
  fixedT : m 106 = TB
  fixedZ : m 108 = ZB
  zero : PolynomialStored b m ZB cap 0

def rootBasisMeta (addr : ℕ) : Prop :=
  addr = 83 ∨ addr = 84 ∨ addr = 88 ∨ addr = 89 ∨ addr = 96 ∨ addr = 112 ∨ rootLevelMeta addr

def rootBasisWritable (R U D C TB cap Q0 Q1 T addr : ℕ) : Prop := rootBasisMeta addr ∨
  rootComputeWritable R U D C TB cap addr ∨
  (Q0 ≤ addr ∧ addr < Q0 + T * cap) ∨ (Q1 ≤ addr ∧ addr < Q1 + T * cap)

def rootPrepareMeta (addr : ℕ) : Prop := addr = 96 ∨ addr = 111 ∨ addr = 90 ∨ addr = 91

/-- Prepare the scalar and the complete inner-level entry counters. -/
def rootBasisPrepareCode : List Instr := basisScalarCode ++ copyMetaCode 89 111 ++ setMetaCode 90 0 ++ setMetaCode 91 0

noncomputable def rootBasisPrepareMemory {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (j : Fin w) (count : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update m 96 (enc b (b j))) 111 count) 90 0) 91 0

def swapMetaCode (left right : ℕ) : List Instr :=
  metaReadCode r0 left ++ metaReadCode r1 right ++ metaStoreCode r0 right ++ metaStoreCode r1 left ++ zeroRegsCode

def rootBasisTailCode : List Instr := swapMetaCode 83 84 ++ copyMetaCode 90 89 ++ incrementMetaCode 88 ++ countdownCode 112

def rootBasisTailMemory (m : ℕ → ℕ) (BQ QB count j n : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update (Function.update m 84 BQ) 83 QB) 89 count) 88 (j + 1)) 112 n

structure RootBasisView {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (R U D C TB ZB cap L BQ QB : ℕ)
    (fs : List F[X]) (j n : ℕ) (m : ℕ → ℕ) : Prop where
  constants : RootConstants b R U D C TB ZB cap L m
  queue : FrontierStored b m BQ cap fs
  oldBase : m 83 = BQ
  newBase : m 84 = QB
  count : m 89 = fs.length
  index : m 88 = j
  remaining : m 112 = n

def rootBasisBody : Stmt := .seq (.code rootBasisPrepareCode)
  (.seq rootLevelProcedure (.code rootBasisTailCode))

def rootBasisLoop : Stmt := .loop (.neqz r9) rootBasisBody

def rootBasisProcedure : Stmt := .seq (.code (metaReadCode r9 112)) rootBasisLoop

/-- Decode one field element through the inverse position table. -/
def fieldPositionCode : List Instr := [iImm r15 9, iTbl r15 r15, iAdd r14 r15 r10, iTbl r10 r14]

/-- The coefficient-one and dimension reads before a linear-root calculation. -/
def leafCoefficientOneCode : List Instr := metaReadCode r2 99 ++
  [iImm r6 1, iAdd r2 r2 r6, iLd r10 r2] ++ metaReadCode r3 77

def leafCoefficientZeroCode : List Instr := metaReadCode r2 99 ++ [iLd r10 r2]

/-- A locator root is first calculated as c0/c1 in characteristic two,
then inverted before its universe position is looked up. -/
def leafPositionCode : List Instr := leafCoefficientOneCode ++ fieldInvCode ++ [iBor r11 r10 r10] ++
  leafCoefficientZeroCode ++ fieldMulCode ++ fieldInvCode ++ fieldPositionCode

/-- The natural-valued output array, before installing the final registers. -/
def OutputStored (m : ℕ → ℕ) (B : ℕ) (xs : List ℕ) : Prop :=
  ∀ j < xs.length, m (B + j) = xs.getD j 0

def positionValidBit (p : ℕ) : ℕ := if 0 < p then 1 else 0

def positionFlagCode : List Instr := [iImm r0 0, iLt r11 r0 r10] ++ metaReadCode r1 100 ++
  [iMul r1 r1 r11] ++ metaStoreCode r1 100 ++ [iSub r10 r10 r11]

def positionAppendCode : List Instr := metaReadCode r2 85 ++ metaReadCode r9 101 ++
  [iAdd r2 r2 r9, iSt r2 r10, iImm r6 1, iAdd r9 r9 r6] ++ metaStoreCode r9 101 ++ zeroRegsCode

def emitPositionCode : List Instr := positionFlagCode ++ positionAppendCode

def emitPositionMemory (m : ℕ → ℕ) (B n p flag : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update m 100 (flag * positionValidBit p)) (B + n) (p - 1)) 101 (n + 1)

def degreeBelowLoadCode (threshold : ℕ) : List Instr := metaReadCode r1 95 ++ [iImm r0 threshold]

/-- Invoke a body when the scanned degree marker is below a fixed threshold. -/
def degreeBelowBranch (threshold : ℕ) (body : Stmt) : Stmt := .seq (Stmt.code (degreeBelowLoadCode threshold))
  (.ite (.lt r15 r1 r0) (Stmt.seq (Stmt.code zeroRegsCode) body) (Stmt.code zeroRegsCode))

noncomputable def rootPositionList {F : Type} [Field F] (N : ℕ) (ι : ℕ → F) (us : List F) : List ℕ :=
  us.map (fun u => posTab N ι u⁻¹ - 1)

noncomputable def rootPositionFlag {F : Type} [Field F] (N : ℕ) (ι : ℕ → F) (us : List F) : ℕ :=
  (us.map (fun u => positionValidBit (posTab N ι u⁻¹))).prod

def leafEmissionProcedure : Stmt := .code (leafPositionCode ++ emitPositionCode)

def leafKeepProcedure : Stmt := .seq (.code (scanSetupCode 99))
  (.seq scanProcedure (degreeBelowBranch 3 leafEmissionProcedure))

def leafKeepWritable (B n degree addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 66 ∨ addr = 95 ∨ addr = 100 ∨ addr = 101 ∨ (degree = 1 ∧ addr = B + n)

def rootEmissionMeta (addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 66 ∨ addr = 95 ∨ addr = 99 ∨ addr = 91 ∨ addr = 111 ∨ addr = 100 ∨ addr = 101

def rootEmissionWritable (B T addr : ℕ) : Prop := rootEmissionMeta addr ∨ (B ≤ addr ∧ addr < B + T)

structure RootEmissionView {F : Type} [Field F] [Algebra (ZMod 2) F] [DecidableEq F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (N : ℕ) (ι : ℕ → F) (BQ cap B : ℕ)
    (fs done pending : List F[X]) (m : ℕ → ℕ) : Prop where
  queue : FrontierStored b m BQ cap fs
  output : OutputStored m B (rootPositionList N ι (rootForest w [] done))
  queueBase : m 83 = BQ
  outputBase : m 85 = B
  dimension : m 77 = w
  capacity : m 81 = cap
  queueCount : m 89 = fs.length
  index : m 91 = done.length
  remaining : m 111 = pending.length
  flag : m 100 = rootPositionFlag N ι (rootForest w [] done)
  count : m 101 = (rootForest w [] done).length

def rootEmissionBody : Stmt := .seq (.code queueReadPointerCode)
  (.seq leafKeepProcedure (.code rootLevelTailCode))

def rootEmissionLoop : Stmt := .loop (.neqz r9) rootEmissionBody

def rootEmissionProcedure : Stmt := .seq (.code (metaReadCode r9 111)) rootEmissionLoop

def listPowerSums {F : Type} [Field F] (ι : ℕ → F) (xs : List ℕ) (j : ℕ) : F :=
  (xs.map (fun i => ι i ^ (j + 1))).sum

/-- During the inner loop, the first k exponents include the current element. -/
def powerPrefix {F : Type} [Field F] (v : ℕ → F) (a : F) (k j : ℕ) : F :=
  v j + if j < k then a ^ (j + 1) else 0

def fieldImageCode : List Instr := [iImm r15 10, iTbl r15 r15, iAdd r14 r15 r10, iTbl r10 r14]

def advanceCounterCode (index counter : ℕ) : List Instr := incrementMetaCode index ++ countdownCode counter

def powerAccumulateCode : List Instr := metaReadCode r2 86 ++ metaReadCode r0 113 ++
  [iAdd r2 r2 r0, iLd r10 r2] ++ metaReadCode r11 115 ++ [iBxor r10 r10 r11, iSt r2 r10]

def powerMultiplyCode : List Instr := metaReadCode r10 115 ++ metaReadCode r11 116 ++ metaReadCode r3 77 ++
  fieldMulCode ++ metaStoreCode r10 115

def powerStepCode : List Instr := powerAccumulateCode ++ powerMultiplyCode

def powerLoopBodyCode : List Instr := powerStepCode ++ advanceCounterCode 113 114

def powerLoopWritable (B len addr : ℕ) : Prop :=
  addr = 113 ∨ addr = 114 ∨ addr = 115 ∨ (B ≤ addr ∧ addr < B + len)

def powerLoopStmt : Stmt := .loop (.neqz r9) (.code powerLoopBodyCode)

def powerProcedure : Stmt := .seq (.code (metaReadCode r9 114)) powerLoopStmt

def candidateReadCode : List Instr := metaReadCode r2 85 ++ metaReadCode r0 117 ++ [iAdd r2 r2 r0, iLd r10 r2]

def powerPrepareCode : List Instr := candidateReadCode ++ fieldImageCode ++ metaStoreCode r10 115 ++ metaStoreCode r10 116 ++
  setMetaCode 113 0 ++ copyMetaCode 121 114

noncomputable def powerPrepareMemory {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (a : F) (len : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update m 115 (enc b a)) 116 (enc b a)) 113 0) 114 len

def powerOuterMeta (addr : ℕ) : Prop :=
  addr = 113 ∨ addr = 114 ∨ addr = 115 ∨ addr = 116 ∨ addr = 117 ∨ addr = 118

def powerOuterWritable (V len addr : ℕ) : Prop := powerOuterMeta addr ∨ (V ≤ addr ∧ addr < V + len)

structure PowerOuterView {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (BP V len : ℕ)
    (xs done pending : List ℕ) (m : ℕ → ℕ) : Prop where
  positions : OutputStored m BP xs
  powers : FieldArrayStored b m V len (listPowerSums ι done)
  positionsBase : m 85 = BP
  powersBase : m 86 = V
  dimension : m 77 = w
  length : m 121 = len
  count : m 101 = xs.length
  index : m 117 = done.length
  remaining : m 118 = pending.length

def powerOuterBody : Stmt := .seq (.code powerPrepareCode)
  (.seq powerProcedure (.code (advanceCounterCode 117 118)))

def powerOuterLoop : Stmt := .loop (.neqz r9) powerOuterBody

def powerOuterProcedure : Stmt := .seq (.code (metaReadCode r9 118)) powerOuterLoop

def equalBit {α : Type} [DecidableEq α] (x y : α) : ℕ := if x = y then 1 else 0

def equalPrefix {α : Type} [DecidableEq α] (u v : ℕ → α) : ℕ → ℕ
  | 0 => 1
  | k + 1 => equalPrefix u v k * equalBit (u k) (v k)

def equalityTestCode : List Instr :=
  [iLt r0 r10 r11, iLt r1 r11 r10, iAdd r0 r0 r1, iImm r6 1, iSub r0 r6 r0]

def matchFlagCode : List Instr := equalityTestCode ++ metaReadCode r1 100 ++ [iMul r1 r1 r0] ++ metaStoreCode r1 100

def comparisonReadCode : List Instr := metaReadCode r2 79 ++ metaReadCode r0 119 ++
  [iAdd r2 r2 r0, iLd r10 r2] ++ metaReadCode r2 86 ++ [iAdd r2 r2 r0, iLd r11 r2]

def comparisonStepCode : List Instr := comparisonReadCode ++ matchFlagCode

structure ComparisonView {F : Type} [Field F] [Algebra (ZMod 2) F] [DecidableEq F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (EB V len : ℕ) (e v : ℕ → F) (flag j n : ℕ) (m : ℕ → ℕ) : Prop where
  expected : FieldArrayStored b m EB len e
  actual : FieldArrayStored b m V len v
  expectedBase : m 79 = EB
  actualBase : m 86 = V
  index : m 119 = j
  remaining : m 120 = n
  flag : m 100 = flag * equalPrefix e v j

def comparisonLoopBodyCode : List Instr := comparisonStepCode ++ advanceCounterCode 119 120

def comparisonWritable (addr : ℕ) : Prop := addr = 100 ∨ addr = 119 ∨ addr = 120

def comparisonLoopStmt : Stmt := .loop (.neqz r9) (.code comparisonLoopBodyCode)

def comparisonProcedure : Stmt := .seq (.code (metaReadCode r9 120)) comparisonLoopStmt

def verifierClearArgsCode : List Instr := metaReadCode r2 86 ++ metaReadCode r1 121 ++ [iImm r3 1]

def verifierClearProcedure : Stmt := .seq (.code verifierClearArgsCode) (.seq clearStmt (.code zeroRegsCode))

def verifierLengthCode : List Instr := metaReadCode r0 80 ++ [iAdd r0 r0 r0] ++ metaStoreCode r0 121 ++ zeroRegsCode

def initializeLoopCode (index counter source : ℕ) : List Instr := setMetaCode index 0 ++ copyMetaCode source counter

def verifierCoreWritable (V len addr : ℕ) : Prop := (113 ≤ addr ∧ addr ≤ 121) ∨ (V ≤ addr ∧ addr < V + len)

def verifierWritable (V len addr : ℕ) : Prop := addr = 100 ∨ verifierCoreWritable V len addr

def verifierPrepareProcedure : Stmt := .seq (.code verifierLengthCode)
  (.seq verifierClearProcedure (.code (initializeLoopCode 117 118 101)))

def verifierPowerProcedure : Stmt := .seq verifierPrepareProcedure powerOuterProcedure

def verifierProcedure : Stmt := .seq verifierPowerProcedure
  (.seq (.code (initializeLoopCode 119 120 121)) comparisonProcedure)

def rootFactorProcedure : Stmt := .seq (.code (initializeLoopCode 88 112 77)) rootBasisProcedure

def rootEmitInitializeCode : List Instr := initializeLoopCode 91 111 89 ++ setMetaCode 100 1 ++ setMetaCode 101 0

def rootEmitInitializeMemory (m : ℕ → ℕ) (count : ℕ) : ℕ → ℕ :=
  Function.update (Function.update (Function.update (Function.update m 91 0) 111 count) 100 1) 101 0

def rootOutputProcedure : Stmt := .seq (.code rootEmitInitializeCode) rootEmissionProcedure

def rootSeedProcedure : Stmt := .seq (.code (copyMetaCode 75 97))
  (.seq (.code (copyMetaCode 83 84)) (.seq (.code (setMetaCode 90 0))
    (.seq queueKeepProcedure (.seq (.code (copyMetaCode 90 89)) (.code (copyMetaCode 107 84))))))

def rootSeedMeta (addr : ℕ) : Prop :=
  addr = 64 ∨ addr = 65 ∨ addr = 66 ∨ addr = 84 ∨ addr = 89 ∨ addr = 90 ∨ addr = 95 ∨ addr = 97

def rootSeedWritable (Q0 cap t addr : ℕ) : Prop := rootSeedMeta addr ∨ (Q0 ≤ addr ∧ addr < Q0 + t * cap)

def rootCandidate {F : Type} [Field F] [DecidableEq F] (us : List F) : Finset F :=
  (us.map (fun u => u⁻¹)).toFinset

def rootSearchProcedure : Stmt := .seq rootSeedProcedure (.seq rootFactorProcedure rootOutputProcedure)

def rootSearchWritable (R U D C TB cap Q0 Q1 B t addr : ℕ) : Prop :=
  rootBasisWritable R U D C TB cap Q0 Q1 t addr ∨ rootEmissionWritable B t addr

def inputReadStmt : Stmt := .seq (.code paramBody) readLoopStmt

def inputFrontStmt : Stmt := .seq inputReadStmt
  (.seq (.code [iImm r5 0]) (.seq expandLoopStmt (.code zeroRegsCode)))

def decoderLength (t : ℕ) : ℕ := 2 * t + 1

def decoderCapacity (t : ℕ) : ℕ := 2 * decoderLength t

def decoderSavedBase (t : ℕ) : ℕ := 128 + 3 * t

def decoderRowBase (t k : ℕ) : ℕ := decoderSavedBase t + 2 * t + k * decoderCapacity t

def decoderQueue0 (t : ℕ) : ℕ := decoderRowBase t 8

def decoderQueue1 (t : ℕ) : ℕ := decoderQueue0 t + t * decoderCapacity t

def decoderOutputBase (t : ℕ) : ℕ := decoderQueue1 t + t * decoderCapacity t

def decoderVerifyBase (t : ℕ) : ℕ := decoderOutputBase t + t

def decoderAllocEnd (t : ℕ) : ℕ := decoderVerifyBase t + 2 * t

def saveHeaderCode : List Instr := [iImm r14 0, iTbl r1 r14, iAdd r1 r1 r1, iImm r14 4, iTbl r3 r14]

def saveDestinationCode : List Instr :=
  [iImm r14 0, iTbl r2 r14, iImm r14 3, iMul r2 r2 r14, iImm r14 128, iAdd r2 r2 r14, iImm r4 1, iImm r14 0]

def saveArgsCode : List Instr := saveHeaderCode ++ saveDestinationCode

def saveSyndromeProcedure : Stmt := .seq (.code saveArgsCode) (.seq copyStmt (.code zeroRegsCode))

def inputSavedProcedure : Stmt := .seq inputFrontStmt saveSyndromeProcedure

inductive MetadataExpr where
  | poly (a b c : ℕ)
  | header (slot : ℕ)

def MetadataExpr.value (E : RAMEnv) (t : ℕ) : MetadataExpr → ℕ
  | .poly a b c => a * t * t + b * t + c
  | .header slot => E.det slot % 2 ^ E.W

def MetadataExpr.code : MetadataExpr → List Instr
  | .poly a b c => [iImm r10 a, iMul r10 r10 r0, iMul r10 r10 r0, iImm r11 b,
      iMul r11 r11 r0, iAdd r10 r10 r11, iImm r11 c, iAdd r10 r10 r11]
  | .header slot => [iImm r15 slot, iTbl r10 r15]

def MetadataExpr.fits (E : RAMEnv) (t : ℕ) : MetadataExpr → Prop
  | .poly a b c => a < 2 ^ E.W ∧ b < 2 ^ E.W ∧ c < 2 ^ E.W ∧ a * t * t + b * t + c < 2 ^ E.W
  | .header slot => slot < 2 ^ E.W

def metadataAssignmentCode (a : ℕ × MetadataExpr) : List Instr := a.2.code ++ metaStoreCode r10 a.1

def metadataAssignmentsCode (as : List (ℕ × MetadataExpr)) : List Instr := as.flatMap metadataAssignmentCode

def metadataAssignmentsMemory (E : RAMEnv) (t : ℕ) (m : ℕ → ℕ) (as : List (ℕ × MetadataExpr)) : ℕ → ℕ :=
  as.foldl (fun mem a => Function.update mem a.1 (a.2.value E t)) m

def decoderMetadataAssignments : List (ℕ × MetadataExpr) :=
  [(72, .poly 0 5 128), (73, .poly 0 9 130), (74, .poly 0 13 132), (75, .poly 0 17 134),
   (76, .poly 0 2 1), (77, .header 1), (79, .poly 0 3 128), (80, .poly 0 1 0),
   (81, .poly 0 4 2), (82, .header 2), (83, .poly 0 37 144), (84, .poly 4 39 144),
   (85, .poly 8 41 144), (86, .poly 8 42 144), (94, .poly 0 2 1),
   (102, .poly 0 5 128), (103, .poly 0 9 130), (104, .poly 0 29 140),
   (105, .poly 0 33 142), (106, .poly 0 21 136), (107, .poly 4 39 144), (108, .poly 0 25 138)]

def metadataAssignmentFits (E : RAMEnv) (t : ℕ) (a : ℕ × MetadataExpr) : Prop := a.1 < 2 ^ E.W ∧ a.2.fits E t

structure DecoderMetadata (t w N : ℕ) (m : ℕ → ℕ) : Prop where
  rowR : m 72 = decoderRowBase t 0
  rowU : m 73 = decoderRowBase t 1
  rowD : m 74 = decoderRowBase t 2
  rowC : m 75 = decoderRowBase t 3
  length : m 76 = decoderLength t
  dimension : m 77 = w
  saved : m 79 = decoderSavedBase t
  capacityParameter : m 80 = t
  capacity : m 81 = decoderCapacity t
  universeSize : m 82 = N
  firstQueue : m 83 = decoderQueue0 t
  secondQueue : m 84 = decoderQueue1 t
  output : m 85 = decoderOutputBase t
  verification : m 86 = decoderVerifyBase t
  padeCounter : m 94 = decoderLength t
  fixedR : m 102 = decoderRowBase t 0
  fixedD : m 103 = decoderRowBase t 1
  fixedU : m 104 = decoderRowBase t 6
  fixedC : m 105 = decoderRowBase t 7
  fixedT : m 106 = decoderRowBase t 4
  fixedQ1 : m 107 = decoderQueue1 t
  fixedZ : m 108 = decoderRowBase t 5

def decoderMetadataSlots (slot : ℕ) : Prop :=
  (72 ≤ slot ∧ slot ≤ 77) ∨ (79 ≤ slot ∧ slot ≤ 86) ∨ slot = 94 ∨ (102 ≤ slot ∧ slot ≤ 108)

def decoderMetadataMemory (E : RAMEnv) (t : ℕ) (m : ℕ → ℕ) : ℕ → ℕ :=
  metadataAssignmentsMemory E t m decoderMetadataAssignments

def decoderMetadataCode : List Instr := [iImm r15 0, iTbl r0 r15] ++ metadataAssignmentsCode decoderMetadataAssignments ++ zeroRegsCode

def initialRowOffsetCode : List Instr := metaReadCode r2 72 ++ metaReadCode r0 76 ++
  [iImm r6 1, iSub r0 r0 r6, iAdd r2 r2 r0]

def initialPolynomialsCode : List Instr := initialRowOffsetCode ++ metaReadCode r10 78 ++ [iSt r2 r10] ++
  metaReadCode r2 75 ++ [iSt r2 r10] ++ zeroRegsCode

def solverInitializationProcedure : Stmt := .seq (.code decoderMetadataCode)
  (.seq (.code cacheUnitCode) (.seq (copyFromSlotsProcedure 74 79) (.code initialPolynomialsCode)))

def solverInitWritable (t addr : ℕ) : Prop := addr < 128 ∨
  (decoderRowBase t 0 ≤ addr ∧ addr < decoderRowBase t 4)

structure KeyReady {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (t N : ℕ) (e : ℕ → F) (m : ℕ → ℕ) : Prop where
  root : RootConstants b (decoderRowBase t 0) (decoderRowBase t 6) (decoderRowBase t 1) (decoderRowBase t 7)
    (decoderRowBase t 4) (decoderRowBase t 5) (decoderCapacity t) (decoderLength t) m
  saved : FieldArrayStored b m (decoderSavedBase t) (2 * t) e
  savedBase : m 79 = decoderSavedBase t
  tValue : m 80 = t
  universeSize : m 82 = N
  firstQueue : m 83 = decoderQueue0 t
  output : m 85 = decoderOutputBase t
  verification : m 86 = decoderVerifyBase t
  fixedQ1 : m 107 = decoderQueue1 t
  sigma : ∃ src, m 75 = src ∧ 128 ≤ src ∧ src + decoderCapacity t ≤ 2 ^ E.W ∧
    PolynomialStored b m src (decoderCapacity t) (padeSolve e t).curC ∧
    (src + decoderCapacity t ≤ decoderQueue0 t ∨ decoderQueue0 t + t * decoderCapacity t ≤ src)

def keySolverProcedure : Stmt := .seq solverInitializationProcedure padeSolveProcedure

structure DecoderGeometry (E : RAMEnv) (t : ℕ) : Prop where
  metadata : 128 < 2 ^ E.W
  savedLow : 128 ≤ decoderSavedBase t
  firstLow : 128 ≤ decoderQueue0 t
  secondLow : 128 ≤ decoderQueue1 t
  outputLow : 128 ≤ decoderOutputBase t
  verifyLow : 128 ≤ decoderVerifyBase t
  firstWord : decoderQueue0 t + t * decoderCapacity t ≤ 2 ^ E.W
  secondWord : decoderQueue1 t + t * decoderCapacity t ≤ 2 ^ E.W
  outputWord : decoderOutputBase t + t ≤ 2 ^ E.W
  verifyWord : decoderVerifyBase t + 2 * t ≤ 2 ^ E.W
  verifyFits : decoderVerifyBase t < 2 ^ E.W
  savedWord : decoderSavedBase t + 2 * t ≤ 2 ^ E.W
  queues : decoderQueue0 t + t * decoderCapacity t ≤ decoderQueue1 t
  firstOutput : decoderQueue0 t + t * decoderCapacity t ≤ decoderOutputBase t
  secondOutput : decoderQueue1 t + t * decoderCapacity t ≤ decoderOutputBase t
  outputVerify : decoderOutputBase t + t ≤ decoderVerifyBase t
  savedVerify : decoderSavedBase t + 2 * t ≤ decoderVerifyBase t

def rootPhaseBudget (t w : ℕ) : ℕ :=
  ((rootNodeBudget (decoderCapacity t) (decoderLength t) w + 83) * t + 193) * w +
    (17 * decoderCapacity t + 233) * t + 29 * decoderCapacity t + 407

structure CandidateReady {F : Type} [Field F] [Algebra (ZMod 2) F] [DecidableEq F] {w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ) (e : ℕ → F) (m : ℕ → ℕ) : Prop where
  saved : FieldArrayStored b m (decoderSavedBase t) (2 * t) e
  positions : OutputStored m (decoderOutputBase t) (rootPositionList N ι (rootsByBasis b (padeSolve e t).curC))
  savedBase : m 79 = decoderSavedBase t
  dimension : m 77 = w
  tValue : m 80 = t
  output : m 85 = decoderOutputBase t
  verification : m 86 = decoderVerifyBase t
  flag : m 100 = rootPositionFlag N ι (rootsByBasis b (padeSolve e t).curC)
  count : m 101 = (rootsByBasis b (padeSolve e t).curC).length

def decoderPost {F : Type} [Field F] [Algebra (ZMod 2) F] {N t w : ℕ}
    (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (y : Fin (t * w) → ZMod 2) (s : RAMState) : Prop :=
  (s.regs r2 ≠ 0 → ∃ x : Fin N → ZMod 2, (binSupp x).card ≤ t ∧ pinBits b (pin ι t x) = y ∧ OutputsSupport s x) ∧
  (s.regs r2 = 0 → ¬ ∃ x : Fin N → ZMod 2, (binSupp x).card ≤ t ∧ pinBits b (pin ι t x) = y)

def finishOutputCode : List Instr := metaReadCode r0 85 ++ metaReadCode r1 101 ++ metaReadCode r2 100

def verificationFinalProcedure : Stmt := .seq verifierProcedure (.code finishOutputCode)

def positiveDecoderStmt : Stmt := .seq inputSavedProcedure
  (.seq keySolverProcedure (.seq rootSearchProcedure verificationFinalProcedure))

def positiveDecoderBudget (t w : ℕ) : ℕ :=
  (62 * t + 66) +
  ((34 * decoderCapacity t + (48 * decoderLength t + 187) * decoderLength t + 289) * decoderLength t + 12 * decoderCapacity t + 385) +
  rootPhaseBudget t w + ((170 * t + 117) * t + 172 * t + 149)

def testedDecoderStart (W : ℕ) {M : ℕ} (y : Fin M → ZMod 2) (pc t : ℕ) : RAMState :=
  { decoderStart W y [] with pc := pc, regs := Function.update (decoderStart W y []).regs r14 t }

def positiveEntryStmt : Stmt := .seq (.code [iImm r14 0]) positiveDecoderStmt

def decoderStmt : Stmt := .seq (.code [iImm r14 0, iTbl r14 r14])
  (.ite (.neqz r14) positiveEntryStmt emptyDecoderStmt)

def pinsketchDecoderProgram : Program := programOfStatement decoderStmt

section PinBits

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

end PinBits

section Uniqueness

variable {F : Type} [Field F] [Algebra (ZMod 2) F]

end Uniqueness

section Slp

variable {F : Type} [Field F]

/-- The value produced by one SLP instruction on the current list of values. -/
def opVal (vals : List F) (o : Bool × ℕ × ℕ) : F :=
  if o.1 then vals.getD o.2.1 0 * vals.getD o.2.2 0
  else vals.getD o.2.1 0 + vals.getD o.2.2 0

/-- The list of instructions after `n` rounds of the update chain, and the position of the last
computed odd power `a^{2n+1}`. -/
def slpAux (t : ℕ) : ℕ → List (Bool × ℕ × ℕ) × ℕ
  | 0 => ([(true, 0, 0)], 0)
  | n + 1 =>
      let p := slpAux t n
      (p.1 ++ [(false, n + 1, p.2), (true, t + 1, p.2)], t + 3 + 2 * n)

/-- The instruction list of the first `n` rounds. -/
def opN (t n : ℕ) : List (Bool × ℕ × ℕ) := (slpAux t n).1

/-- The index of `a^{2n+1}` in the value list after `n` rounds. -/
def pwN (t n : ℕ) : ℕ := (slpAux t n).2

/-- The invariant maintained by the chain: the running list has the right length, its input part is
unchanged, it holds `a²` and `a^{2n+1}`, and all earlier outputs are correct. -/
def SlpInv (t : ℕ) (a : F) (s : Fin t → F) (n : ℕ) (vals : List F) : Prop :=
  vals.length = t + 2 + 2 * n ∧
  (∀ m : Fin t, vals.getD ((m : ℕ) + 1) 0 = s m) ∧
  vals.getD (t + 1) 0 = a ^ 2 ∧
  vals.getD (pwN t n) 0 = a ^ (2 * n + 1) ∧
  (∀ j : Fin t, (j : ℕ) < n →
    vals.getD (t + 2 + 2 * (j : ℕ)) 0 = s j + a ^ (2 * (j : ℕ) + 1))

end Slp

end LinearSetReconciliation327.Main
Source
arXiv:2611.11409, Section 2.2 (Pinsketch decoder) and Appendix C (word-RAM implementation); Dodis, Ostrovsky, Reyzin, Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, SIAM J. Comput. 38(1), 2008, Section 6.3

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me