Pinsketch decoder III: address layout, workspace views, readiness predicates and the four stage procedures
DefinitionLinearSetReconciliation327_Main_DecoderProgramThis 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.
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