Pinsketch decoder IV: the shared lemma library of the decoder-stage proofs
DefinitionLinearSetReconciliation327_Main_DecoderLemmaspinsketchset-reconciliationword-ram
This bundle publishes, once, the library of helper lemmas that the four decoder-stage correctness proofs share.
The lemmas fall into four groups:
- Execution layer. One-step and whole-block facts about the instruction set and the small structured statements: how a register move, an indexed load/store, a comparison or a jump updates the RAM state; how
Semcomposes sequentially, under anif, and around a loop; and how a run block's program counter and memory frame evolve. - Memory layer. Frame lemmas saying that a write to a disjoint region leaves an array or a polynomial untouched, and read lemmas saying that a stored array is read back correctly. These are what let each stage state exactly which addresses it may modify.
- Arithmetic layer. Facts about the tabulated field arithmetic and the standard table: the header entries, the address ranges, the encoding/decoding identities
enc/dec, and the field lemmas (characteristic two, Frobenius, Vandermonde) used by the syndrome argument. - Algorithm layer. The invariants of the in-place Euclidean/Padé loop (long division, degree scan, row swap, minimality of the key solution) and of the root-search recursion (trace splitting, candidate emission, soundness).
Every lemma here is proved; the bundle contains no sorry. Its purpose is structural: the stage contracts and the parent reduction import it instead of each carrying a private copy of several hundred helper lemmas, which keeps every individual proof file small and inside the platform's compile budget.
Definition code
import Definitions.Def_LinearSetReconciliation327_Main_Basic
import Definitions.Def_LinearSetReconciliation327_Main_Pinsketch
import Definitions.Def_LinearSetReconciliation327_Main_DecoderModel
import Definitions.Def_LinearSetReconciliation327_Main_DecoderTables
import Definitions.Def_LinearSetReconciliation327_Main_DecoderProgram
/-! Decoder lemmas: the shared helper lemmas of the six decoder-stage proofs, published once so that the stage children and the parent stay small.
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
attribute [local simp] readState expandState
section FieldFacts
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
/-- A field that is a `ZMod 2`-algebra has characteristic two. -/
theorem pinsketch_two_eq_zero : (2 : F) = 0 := by
have h : ((2 : ℕ) : F) = 0 := by
rw [← map_natCast (algebraMap (ZMod 2) F) 2, CharP.cast_eq_zero (ZMod 2) 2, map_zero]
simpa using h
theorem pinsketch_charP : CharP F 2 :=
CharTwo.of_one_ne_zero_of_two_eq_zero one_ne_zero pinsketch_two_eq_zero
/-- In characteristic two, `a + b = 0` forces `a = b`. -/
theorem pinsketch_eq_of_add_eq_zero {a b : F} (h : a + b = 0) : a = b := by
haveI := pinsketch_charP (F := F)
exact CharTwo.add_eq_zero.mp h
/-- The freshman's dream: squaring is additive in characteristic two. -/
theorem pinsketch_sum_sq {α : Type} (s : Finset α) (f : α → F) :
(∑ i ∈ s, f i) ^ 2 = ∑ i ∈ s, f i ^ 2 := by
haveI := pinsketch_charP (F := F)
exact CharTwo.sum_sq s f
/-- The only two elements of `ZMod 2`. -/
theorem zmod2_eq_zero_or_one (z : ZMod 2) : z = 0 ∨ z = 1 := by
have h : ∀ z : ZMod 2, z = 0 ∨ z = 1 := by decide
exact h z
/-- Scalar multiplication by a `ZMod 2`-element is either `0` or the identity. -/
theorem zmod2_smul_eq (z : ZMod 2) (v : F) : z • v = if z = 1 then v else 0 := by
rcases zmod2_eq_zero_or_one z with h | h <;> simp [h]
end FieldFacts
section PowerSums
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
variable {N : ℕ}
/-- `P_a(x)` is the `a`-th power sum of the field elements indexed by the support. -/
theorem pinPower_eq_sum_supp (ι : ℕ → F) (a : ℕ) (x : Fin N → ZMod 2) :
pinPower ι a x = ∑ i ∈ binSupp x, ι i.val ^ a := by
rw [pinPower]
calc ∑ i, x i • ι i.val ^ a
= ∑ i, (if x i = 1 then ι i.val ^ a else 0) := by
exact Finset.sum_congr rfl (fun i _ => zmod2_smul_eq (x i) _)
_ = ∑ i ∈ univ.filter (fun i => x i = 1), ι i.val ^ a :=
(Finset.sum_filter (s := univ) (p := fun i => x i = 1) (f := fun i => ι i.val ^ a)).symm
/-- The power sums are additive: the map `x ↦ P_a(x)` is `F₂`-linear. -/
theorem pinPower_add (ι : ℕ → F) (a : ℕ) (x y : Fin N → ZMod 2) :
pinPower ι a (x + y) = pinPower ι a x + pinPower ι a y := by
simp only [pinPower, Pi.add_apply, add_smul, Finset.sum_add_distrib]
/-- **Frobenius**, as in the paper: in characteristic two, `P_{2a}(x) = P_a(x)^2`. -/
theorem pinPower_frobenius (ι : ℕ → F) (a : ℕ) (x : Fin N → ZMod 2) :
pinPower ι (2 * a) x = (pinPower ι a x) ^ 2 := by
rw [pinPower_eq_sum_supp, pinPower_eq_sum_supp]
calc ∑ i ∈ binSupp x, ι i.val ^ (2 * a)
= ∑ i ∈ binSupp x, (ι i.val ^ a) ^ 2 := by
refine Finset.sum_congr rfl (fun i _ => ?_)
rw [Nat.mul_comm 2 a, pow_mul]
_ = (∑ i ∈ binSupp x, ι i.val ^ a) ^ 2 := (pinsketch_sum_sq _ _).symm
end PowerSums
/-- Packing a `Fin K`-indexed family is the same as the sum of shifted fields. -/
theorem packL_ofFn (w K : ℕ) (f : Fin K → ℕ) :
packL w (List.ofFn f) = ∑ j : Fin K, f j * 2 ^ (j.val * w) := by
induction K with
| zero => simp [packL]
| succ n ih =>
rw [List.ofFn_succ, Fin.sum_univ_succ]
simp only [packL, Fin.val_zero, Nat.zero_mul, Nat.pow_zero, Nat.mul_one, Fin.val_succ]
rw [ih (fun i => f i.succ), Finset.mul_sum]
congr 1
apply Finset.sum_congr rfl
intro j _
have h2 : 2 ^ ((j.val + 1) * w) = 2 ^ w * 2 ^ (j.val * w) := by
rw [Nat.add_mul, Nat.one_mul, Nat.pow_add, Nat.mul_comm]
rw [h2]
ring
/-- Extracting the `k`-th `w`-bit field, in division form. -/
theorem extract_field_div (w : ℕ) (_hw : 0 < w) (l : List ℕ) (hx : ∀ x ∈ l, x < 2 ^ w)
(k : ℕ) : packL w l / 2 ^ (k * w) % 2 ^ w = l.getD k 0 := by
induction k generalizing l with
| zero =>
cases l with
| nil => simp [packL]
| cons x xs =>
have hx' : x < 2 ^ w := hx x (by simp)
simp only [Nat.zero_mul, Nat.pow_zero, Nat.div_one, packL, List.getD_cons_zero]
rw [Nat.add_mul_mod_self_left, Nat.mod_eq_of_lt hx']
| succ k ih =>
cases l with
| nil => simp [packL]
| cons x xs =>
have hx' : x < 2 ^ w := hx x (by simp)
have hpw : 0 < 2 ^ w := Nat.two_pow_pos w
have hsplit : 2 ^ ((k + 1) * w) = 2 ^ w * 2 ^ (k * w) := by
rw [Nat.add_mul, Nat.one_mul, Nat.pow_add, Nat.mul_comm]
have hlow : (x + 2 ^ w * packL w xs) / 2 ^ w = packL w xs := by
rw [Nat.add_comm x (2 ^ w * packL w xs), Nat.mul_add_div hpw,
Nat.div_eq_of_lt hx', Nat.add_zero]
simp only [packL, List.getD_cons_succ, hsplit, ← Nat.div_div_eq_div_mul, hlow]
exact ih xs (fun y hy => hx y (by simp [hy]))
/-- The `k`-th `w`-bit field of a packed word, extracted with `>>>` and `&&&`. -/
theorem extract_field (w : ℕ) (hw : 0 < w) (l : List ℕ) (hx : ∀ x ∈ l, x < 2 ^ w) (k : ℕ) :
(packL w l >>> (k * w)) &&& (2 ^ w - 1) = l.getD k 0 := by
rw [Nat.and_two_pow_sub_one_eq_mod, Nat.shiftRight_eq_div_pow]
exact extract_field_div w hw l hx k
/-- Field extraction in the form used by the sketches: a word whose `j`-th `w`-bit field is
`f j` yields `f k` by shifting and masking. -/
theorem extract_field_sum (w K : ℕ) (hw : 0 < w) (f : Fin K → ℕ) (hf : ∀ j, f j < 2 ^ w)
(k : Fin K) :
((∑ j : Fin K, f j * 2 ^ (j.val * w)) >>> (k.val * w)) &&& (2 ^ w - 1) = f k := by
rw [← packL_ofFn w K f]
rw [extract_field w hw (List.ofFn f) ?_ k.val]
· have hk : k.val < (List.ofFn f).length := by simp only [List.length_ofFn]; exact k.isLt
rw [List.getD_eq_getElem (List.ofFn f) 0 hk]
simp [List.getElem_ofFn]
· intro x hx
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp hx
exact hf j
theorem pdec_X_pow_dvd_eq_zero {F : Type} [Field F] {n : ℕ} {f : F[X]}
(h : X ^ n ∣ f) (hdeg : f.natDegree < n) : f = 0 := by
rw [X_pow_dvd_iff] at h
ext d
simp only [coeff_zero]
by_cases hd : d < n
· exact h d hd
· exact coeff_eq_zero_of_natDegree_lt (by omega)
/-- Cross-multiplied uniqueness of the pair `(σ, ω)` in the key equation `σ S ≡ ω (mod X^{2t})`:
both products `σ ω'` and `σ' ω` have degree `< 2t`, and `X ^ (2t)` divides their difference. -/
theorem key_equation_unique {F : Type} [Field F] (S : F[X]) (t : ℕ) {σ ω σ' ω' : F[X]}
(hσ : σ ≠ 0) (hσ' : σ' ≠ 0)
(hdegσ : σ.natDegree ≤ t) (hdegσ' : σ'.natDegree ≤ t)
(hdegω : ω.natDegree < t) (hdegω' : ω'.natDegree < t)
(h : X ^ (2 * t) ∣ σ * S - ω) (h' : X ^ (2 * t) ∣ σ' * S - ω') :
σ * ω' = σ' * ω := by
obtain ⟨u, hu⟩ := h
obtain ⟨v, hv⟩ := h'
have e1 : σ * S = ω + X ^ (2 * t) * u := by rw [← hu]; ring
have e2 : σ' * S = ω' + X ^ (2 * t) * v := by rw [← hv]; ring
have h4 : σ' * ω + X ^ (2 * t) * (σ' * u) = σ * ω' + X ^ (2 * t) * (σ * v) := by
calc σ' * ω + X ^ (2 * t) * (σ' * u)
= σ' * (ω + X ^ (2 * t) * u) := by ring
_ = σ' * (σ * S) := by rw [e1]
_ = σ * (σ' * S) := by ring
_ = σ * (ω' + X ^ (2 * t) * v) := by rw [e2]
_ = σ * ω' + X ^ (2 * t) * (σ * v) := by ring
have key : σ * ω' - σ' * ω = X ^ (2 * t) * (σ' * u - σ * v) := by
have h6 : σ * ω' - σ' * ω - X ^ (2 * t) * (σ' * u - σ * v) = 0 := by
have hexp : σ * ω' - σ' * ω - X ^ (2 * t) * (σ' * u - σ * v)
= (σ * ω' + X ^ (2 * t) * (σ * v)) - (σ' * ω + X ^ (2 * t) * (σ' * u)) := by
ring
rw [hexp, h4]
ring
exact sub_eq_zero.mp h6
have hdeg : (σ * ω' - σ' * ω).natDegree < 2 * t := by
have h6 : (σ * ω').natDegree ≤ σ.natDegree + ω'.natDegree := natDegree_mul_le
have h7 : (σ' * ω).natDegree ≤ σ'.natDegree + ω.natDegree := natDegree_mul_le
have h8 := natDegree_sub_le (σ * ω') (σ' * ω)
omega
have hdvd : X ^ (2 * t) ∣ σ * ω' - σ' * ω := ⟨σ' * u - σ * v, key⟩
exact sub_eq_zero.mp (pdec_X_pow_dvd_eq_zero hdvd hdeg)
theorem sum_range_two_pow_lt (w : ℕ) : (∑ k ∈ Finset.range w, 2 ^ k) < 2 ^ w := by
induction w with
| zero => simp
| succ w ih =>
rw [Finset.sum_range_succ, Nat.pow_succ]
omega
/-- The coordinates of `payloadField` are the payload bits. -/
theorem payloadField_apply {F : Type} [Field F] [Algebra (ZMod 2) F] {w M : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (y : Fin M → ZMod 2) (j : ℕ) (k : Fin w) :
b.repr (payloadField b y j) k = payloadAt y (j * w + k.val) := by
rw [payloadField, LinearEquiv.apply_symm_apply]
simp only [Finsupp.coe_equivFunOnFinite_symm]
theorem pdec_natDegree_finset_sum_le {α F : Type} [Field F] [DecidableEq F] (s : Finset α)
(f : α → F[X]) (n : ℕ) (h : ∀ i ∈ s, (f i).natDegree ≤ n) :
(∑ i ∈ s, f i).natDegree ≤ n := by
classical
induction s using Finset.induction with
| empty => simp
| insert a s ha ih =>
rw [Finset.sum_insert ha]
refine le_trans (natDegree_add_le _ _) (max_le (h a (Finset.mem_insert_self a s)) ?_)
exact ih (fun i hi => h i (Finset.mem_insert_of_mem hi))
/-- A Euclidean predecessor certifies minimality of a bounded key solution.
The certificate is an identity of polynomials, together with one key congruence;
no assumption about the existence of a decodable support is used. -/
theorem keySolEMin_of_euclidean_certificate
{F : Type} [Field F] (e : ℕ → F) (t : ℕ)
{τ ν σ ω : F[X]}
(hkey : KeySolE e t σ ω)
(hprev : X ^ (2 * t) ∣
τ * (∑ j ∈ Finset.range (2 * t), C (e j) * X ^ j) - ν)
(hdet : ν * σ - τ * ω = X ^ (2 * t)) :
KeySolEMin e t σ ω := by
refine ⟨hkey, ?_⟩
intro σ' ω' hkey'
let S : F[X] := ∑ j ∈ Finset.range (2 * t), C (e j) * X ^ j
let M : F[X] := X ^ (2 * t)
have hcross : σ * ω' = σ' * ω :=
key_equation_unique S t hkey.1 hkey'.1 hkey.2.1 hkey'.2.1
hkey.2.2.1 hkey'.2.2.1 hkey.2.2.2 hkey'.2.2.2
have hdiv : M ∣ ν * σ' - τ * ω' := by
have ha : M ∣ τ * (σ' * S - ω') := dvd_mul_of_dvd_right hkey'.2.2.2 τ
have hb : M ∣ σ' * (τ * S - ν) := dvd_mul_of_dvd_right hprev σ'
have hc := dvd_sub ha hb
convert hc using 1 <;> ring
obtain ⟨q, hq⟩ := hdiv
have hprod : M * σ' = M * (σ * q) := by
calc
M * σ' = (ν * σ - τ * ω) * σ' := by rw [hdet]
_ = ν * (σ * σ') - τ * (σ' * ω) := by ring
_ = ν * (σ * σ') - τ * (σ * ω') := by rw [← hcross]
_ = σ * (ν * σ' - τ * ω') := by ring
_ = σ * (M * q) := by rw [hq]
_ = M * (σ * q) := by ring
have hM : M ≠ 0 := pow_ne_zero _ Polynomial.X_ne_zero
have hfactor : σ' = σ * q := mul_left_cancel₀ hM hprod
exact Polynomial.natDegree_le_of_dvd ⟨q, hfactor⟩ hkey'.1
/-- Initial Euclidean rows: `(M, 0)` and `(S, 1)`. -/
theorem padeBasis_initial {F : Type} [Field F] (S M : F[X]) :
PadeBasis S M 0 M 1 S := by
refine ⟨?_, ?_, ?_⟩
· exact ⟨-1, by ring⟩
· simp
· ring
/-- One quotient update preserves the two congruences and the determinant.
Characteristic two removes the determinant sign when the rows are exchanged. -/
theorem padeBasis_step {F : Type} [Field F] [Algebra (ZMod 2) F]
{S M τ ν σ ω : F[X]} (h : PadeBasis S M τ ν σ ω) (q : F[X]) :
PadeBasis S M σ ω (τ - q * σ) (ν - q * ω) := by
refine ⟨h.2.1, ?_, ?_⟩
· have hd := dvd_sub h.1 (dvd_mul_of_dvd_right h.2.1 q)
convert hd using 1 <;> ring
· calc
ω * (τ - q * σ) - σ * (ν - q * ω) = -(ν * σ - τ * ω) := by ring
_ = -M := by rw [h.2.2]
_ = M := by
haveI : CharP F 2 := pinsketch_charP
haveI : CharP F[X] 2 := inferInstance
exact CharTwo.neg_eq M
/-- The machine's Euclidean invariant provides the minimality certificate
once its terminating row has the required key-equation degree bounds. -/
theorem padeBasis_minimal {F : Type} [Field F] (e : ℕ → F) (t : ℕ)
{τ ν σ ω : F[X]}
(h : PadeBasis (∑ j ∈ Finset.range (2 * t), C (e j) * X ^ j)
(X ^ (2 * t)) τ ν σ ω)
(hσ : σ ≠ 0) (hdegσ : σ.natDegree ≤ t) (hdegω : ω.natDegree < t) :
KeySolEMin e t σ ω :=
keySolEMin_of_euclidean_certificate e t ⟨hσ, hdegσ, hdegω, h.2.1⟩ h.1 h.2.2
theorem syndromePoly_natDegree_lt {F : Type} [Field F] (e : ℕ → F) (t : ℕ)
(ht : 1 ≤ t) : (syndromePoly e t).natDegree < 2 * t := by
classical
have hle : (syndromePoly e t).natDegree ≤ 2 * t - 1 := by
refine pdec_natDegree_finset_sum_le (Finset.range (2 * t))
(fun j => C (e j) * X ^ j) (2 * t - 1) ?_
intro j hj
have hj' := Finset.mem_range.mp hj
exact le_trans (Polynomial.natDegree_C_mul_X_pow_le (e j) j) (by omega)
omega
theorem padeInv_initial {F : Type} [Field F] (e : ℕ → F) (t : ℕ) (ht : 1 ≤ t) :
PadeInv e t (padeInitial e t) := by
refine ⟨padeBasis_initial _ _, ?_, ?_, ?_, ?_, ?_, ?_⟩
· exact pow_ne_zero _ Polynomial.X_ne_zero
· exact one_ne_zero
· simp [padeInitial]
· simp only [padeInitial, Polynomial.natDegree_X_pow]
omega
· simp [padeInitial]
· simpa only [padeInitial, Polynomial.natDegree_X_pow] using
syndromePoly_natDegree_lt e t ht
/-- A quotient step strictly lowers the preceding remainder and preserves
all degree and congruence information. -/
theorem padeInv_next {F : Type} [Field F] [Algebra (ZMod 2) F]
{e : ℕ → F} {t : ℕ} {s : PadeState F} (ht : 1 ≤ t)
(h : PadeInv e t s) (hgo : t ≤ s.rem.natDegree) :
PadeInv e t (padeNext s) := by
let q : F[X] := s.prevR / s.rem
have hrem_ne : s.rem ≠ 0 := by
intro hz
have hd : s.rem.natDegree = 0 := by rw [hz, Polynomial.natDegree_zero]
omega
have hdegree : s.rem.degree ≤ s.prevR.degree := by
rw [Polynomial.degree_eq_natDegree hrem_ne, Polynomial.degree_eq_natDegree h.prev_ne]
exact_mod_cast (le_of_lt h.rem_small)
have hq_ne : q ≠ 0 := by
intro hz
have hlt := (Polynomial.div_eq_zero_iff hrem_ne).mp hz
exact (not_lt_of_ge hdegree) hlt
have hdivdeg : s.rem.natDegree + q.natDegree = s.prevR.natDegree := by
have hd := Polynomial.degree_add_div (p := s.prevR) (q := s.rem) hrem_ne hdegree
rw [Polynomial.degree_eq_natDegree hrem_ne,
Polynomial.degree_eq_natDegree h.prev_ne, Polynomial.degree_eq_natDegree hq_ne] at hd
exact_mod_cast hd
have hq_pos : 0 < q.natDegree := by
have hlt := h.rem_small
omega
have hmuldeg : (q * s.curC).natDegree = q.natDegree + s.curC.natDegree :=
Polynomial.natDegree_mul hq_ne h.cur_ne
have hless : s.prevC.natDegree < (q * s.curC).natDegree := by
rw [hmuldeg]
have hp := h.prev_small
omega
have hnewdeg : (s.prevC - q * s.curC).natDegree = q.natDegree + s.curC.natDegree := by
rw [Polynomial.natDegree_sub_eq_right_of_natDegree_lt hless, hmuldeg]
have hnew_ne : s.prevC - q * s.curC ≠ 0 := by
intro hz
rw [hz, Polynomial.natDegree_zero] at hnewdeg
omega
have hrem_eq : s.prevR - q * s.rem = s.prevR % s.rem := by
dsimp only [q]
linear_combination -(EuclideanDomain.div_add_mod s.prevR s.rem)
have hb := padeBasis_step h.basis q
rw [hrem_eq] at hb
refine ⟨hb, hrem_ne, hnew_ne, ?_, hgo, ?_, ?_⟩
· change s.rem.natDegree + (s.prevC - q * s.curC).natDegree = 2 * t
rw [hnewdeg]
have hbal := h.balance
omega
· change s.curC.natDegree ≤ (s.prevC - q * s.curC).natDegree
rw [hnewdeg]
omega
· change (s.prevR % s.rem).natDegree < s.rem.natDegree
exact Polynomial.natDegree_mod_lt _ (by omega)
/-- Sufficient fuel cannot be exhausted: remainders decrease before each
recursive call, and the degree balance survives every quotient. -/
theorem padeRun_spec {F : Type} [Field F] [Algebra (ZMod 2) F]
(e : ℕ → F) (t : ℕ) (ht : 1 ≤ t) (fuel : ℕ) (s : PadeState F)
(h : PadeInv e t s) (hfuel : s.prevR.natDegree < fuel) :
PadeInv e t (padeRun t fuel s) ∧ (padeRun t fuel s).rem.natDegree < t := by
induction fuel generalizing s with
| zero => omega
| succ fuel ih =>
by_cases hstop : s.rem.natDegree < t
· rw [padeRun, if_pos hstop]
exact ⟨h, hstop⟩
· have hn := padeInv_next ht h (Nat.le_of_not_gt hstop)
have hn_fuel : (padeNext s).prevR.natDegree < fuel := by
change s.rem.natDegree < fuel
have hd := h.rem_small
omega
rw [padeRun, if_neg hstop]
exact ih (padeNext s) hn hn_fuel
/-- The complete abstract key-equation solver: for every syndrome sequence,
including undecodable ones, it returns a minimum-degree bounded solution. -/
theorem padeSolve_minimal {F : Type} [Field F] [Algebra (ZMod 2) F]
(e : ℕ → F) (t : ℕ) (ht : 1 ≤ t) :
KeySolEMin e t (padeSolve e t).curC (padeSolve e t).rem := by
have hfuel : (padeInitial e t).prevR.natDegree < 2 * t + 1 := by
simp [padeInitial]
obtain ⟨h, hstop⟩ := padeRun_spec e t ht (2 * t + 1) (padeInitial e t)
(padeInv_initial e t ht) hfuel
have hdeg : (padeSolve e t).curC.natDegree ≤ t := by
have hbal := h.balance
have hlarge := h.prev_large
change (padeSolve e t).prevR.natDegree + (padeSolve e t).curC.natDegree = 2 * t at hbal
change t ≤ (padeSolve e t).prevR.natDegree at hlarge
omega
exact padeBasis_minimal e t h.basis h.cur_ne hdeg hstop
theorem gcd_eval_iff {F : Type} [Field F] [DecidableEq F]
(f g : F[X]) (u : F) :
(EuclideanDomain.gcd f g).eval u = 0 ↔ f.eval u = 0 ∧ g.eval u = 0 := by
change (EuclideanDomain.gcd f g).IsRoot u ↔ f.IsRoot u ∧ g.IsRoot u
exact Polynomial.isRoot_gcd_iff_isRoot_left_right
theorem gcd_ne_zero_left {F : Type} [Field F] [DecidableEq F]
{f : F[X]} (hf : f ≠ 0) (g : F[X]) : EuclideanDomain.gcd f g ≠ 0 := by
intro hz
have hd := EuclideanDomain.gcd_dvd_left f g
rw [hz] at hd
exact hf (by simpa only [zero_dvd_iff] using hd)
theorem linearRoot_eval_iff {F : Type} [Field F] {f : F[X]}
(hf : f ≠ 0) (hdeg : f.natDegree = 1) (u : F) :
f.eval u = 0 ↔ u = linearRoot f := by
have h1 : f.coeff 1 ≠ 0 := by
simpa only [Polynomial.leadingCoeff, hdeg] using (Polynomial.leadingCoeff_ne_zero.mpr hf)
have hp := Polynomial.eq_X_add_C_of_natDegree_le_one hdeg.le
have heval : f.eval u = f.coeff 1 * u + f.coeff 0 := by
calc
f.eval u = (C (f.coeff 1) * X + C (f.coeff 0)).eval u := congrArg (fun p => p.eval u) hp
_ = f.coeff 1 * u + f.coeff 0 := by simp
rw [heval]
change f.coeff 1 * u + f.coeff 0 = 0 ↔ u = -f.coeff 0 / f.coeff 1
constructor
· intro h
apply (eq_div_iff h1).mpr
linear_combination h
· intro h
have he := (eq_div_iff h1).mp h
linear_combination he
theorem dvd_sub_mod {F : Type} [Field F] (p f : F[X]) : f ∣ p - p % f := by
refine ⟨p / f, ?_⟩
linear_combination -(EuclideanDomain.div_add_mod p f)
theorem traceRemainder_congr {F : Type} [Field F] (a : F) (f : F[X]) (n : ℕ) :
f ∣ tracePolynomial a n - traceRemainder a f n := by
induction n with
| zero => simp [tracePolynomial, traceRemainder]
| succ n ih =>
have hs : f ∣ tracePolynomial a n ^ 2 - traceRemainder a f n ^ 2 := by
have hd := dvd_mul_of_dvd_left ih (tracePolynomial a n + traceRemainder a f n)
convert hd using 1 <;> ring
have hm := dvd_sub_mod (traceRemainder a f n ^ 2 + C a * X) f
have hd := dvd_add hs hm
change f ∣ (tracePolynomial a n ^ 2 + C a * X) -
(traceRemainder a f n ^ 2 + C a * X) % f
convert hd using 1 <;> ring
/-- Equal remainders give literally equal Euclidean gcds. -/
theorem gcd_eq_of_dvd_sub {F : Type} [Field F] [DecidableEq F]
(f p q : F[X]) (h : f ∣ p - q) :
EuclideanDomain.gcd f p = EuclideanDomain.gcd f q := by
rw [EuclideanDomain.gcd_val f p, EuclideanDomain.gcd_val f q,
Polynomial.mod_eq_of_dvd_sub h]
/-- Refinement from low-degree modular computations to the mathematical
splitter specification. -/
theorem traceRootSearch_eq {F : Type} [Field F] [DecidableEq F]
(w : ℕ) (as : List F) (f : F[X]) :
traceRootSearch w as f = rootSearch (as.map (fun a => tracePolynomial a w)) f := by
induction as generalizing f with
| nil => rfl
| cons a as ih =>
by_cases hzero : f.natDegree = 0
· simp only [traceRootSearch, List.map_cons, rootSearch, if_pos hzero]
· have h0 : EuclideanDomain.gcd f (tracePolynomial a w) =
EuclideanDomain.gcd f (traceRemainder a f w) :=
gcd_eq_of_dvd_sub f _ _ (traceRemainder_congr a f w)
have h1 : EuclideanDomain.gcd f (tracePolynomial a w - 1) =
EuclideanDomain.gcd f (traceRemainder a f w - 1) := by
apply gcd_eq_of_dvd_sub
convert traceRemainder_congr a f w using 1 <;> ring
simp only [traceRootSearch, List.map_cons, rootSearch, if_neg hzero]
simp only [ih, h0, h1]
/-- Sibling factors are coprime, since the splitter differs by one. Their
combined degree therefore cannot exceed the parent's degree, even for an
undecodable input polynomial. -/
theorem split_degree_budget {F : Type} [Field F] [DecidableEq F]
(f p : F[X]) (hf : f ≠ 0) :
(EuclideanDomain.gcd f p).natDegree +
(EuclideanDomain.gcd f (p - 1)).natDegree ≤ f.natDegree := by
let g0 := EuclideanDomain.gcd f p
let g1 := EuclideanDomain.gcd f (p - 1)
have h0 : g0 ≠ 0 := gcd_ne_zero_left hf p
have h1 : g1 ≠ 0 := gcd_ne_zero_left hf (p - 1)
have hcop : IsCoprime g0 g1 := by
obtain ⟨u, hu⟩ := EuclideanDomain.gcd_dvd_right f p
obtain ⟨v, hv⟩ := EuclideanDomain.gcd_dvd_right f (p - 1)
refine ⟨u, -v, ?_⟩
change u * EuclideanDomain.gcd f p + -v * EuclideanDomain.gcd f (p - 1) = 1
linear_combination hv - hu
have hd := hcop.mul_dvd (EuclideanDomain.gcd_dvd_left f p)
(EuclideanDomain.gcd_dvd_left f (p - 1))
have hdeg := Polynomial.natDegree_le_of_dvd hd hf
rwa [Polynomial.natDegree_mul h0 h1] at hdeg
@[simp] theorem execInstr_lt (E : RAMEnv) (s : RAMState) (d a b : Fin 16) :
execInstr (.lt d a b) E s = { s with pc := s.pc + 1, regs := Function.update s.regs d ((if (s.regs a) < (s.regs b) then 1 else 0) % 2 ^ E.W) } := rfl
@[simp] theorem execInstr_jz (E : RAMEnv) (s : RAMState) (c : Fin 16) (t : ℕ) :
execInstr (.jz c t) E s = { s with pc := if (s.regs c) = 0 then t else s.pc + 1 } := rfl
@[simp] theorem execInstr_jmp (E : RAMEnv) (s : RAMState) (t : ℕ) :
execInstr (.jmp t) E s = { s with pc := t } := rfl
/-- `step` runs the branch of `execInstr` at the current program counter. -/
theorem step_eq_execInstr (P : Program) (E : RAMEnv) (s : RAMState) (i : Instr)
(h : P[s.pc]? = some i) : step P E s = execInstr i E s := by
unfold step execInstr
rw [h]
cases i <;> rfl
/-- Two machine states with the same program counter, memory and registers are equal. -/
theorem ramState_eq_of (a b : RAMState) (hpc : a.pc = b.pc) (hmem : a.mem = b.mem)
(hregs : ∀ d, a.regs d = b.regs d) : a = b := by
obtain ⟨p1, r1', m1⟩ := a
obtain ⟨p2, r2', m2⟩ := b
simp only at hpc hmem hregs
subst hpc
subst hmem
rw [funext hregs]
/-- A non-branching, non-halting instruction advances the program counter by one. -/
theorem execInstr_pc (i : Instr) (E : RAMEnv) (s : RAMState) (hno : i.NoBranchI) :
(execInstr i E s).pc = s.pc + 1 := by
obtain ⟨h1, h2, h3⟩ := hno
cases i <;> simp_all [execInstr]
@[simp] theorem noBranch_nil : NoBranch ([] : List Instr) ↔ True := by simp [NoBranch]
@[simp] theorem noBranch_cons (i : Instr) (c : List Instr) :
NoBranch (i :: c) ↔ i.NoBranchI ∧ NoBranch c := by simp [NoBranch]
@[simp] theorem noBranchI_imm (d : Fin 16) (v : ℕ) : (iImm d v).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_add (d a b : Fin 16) : (iAdd d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_sub (d a b : Fin 16) : (iSub d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_mul (d a b : Fin 16) : (iMul d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_div (d a b : Fin 16) : (iDiv d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_mod (d a b : Fin 16) : (iMod d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_bor (d a b : Fin 16) : (iBor d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_bxor (d a b : Fin 16) : (iBxor d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_shl (d a b : Fin 16) : (iShl d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_lt (d a b : Fin 16) : (iLt d a b).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_load (d a : Fin 16) : (iLd d a).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_store (a v : Fin 16) : (iSt a v).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem noBranchI_qDet (d a : Fin 16) : (iTbl d a).NoBranchI := by
refine ⟨fun t h => ?_, fun d' t h => ?_, fun h => ?_⟩ <;> cases h
@[simp] theorem runBlock_nil (E : RAMEnv) (s : RAMState) : runBlock [] E s = s := rfl
@[simp] theorem runBlock_cons (i : Instr) (code : List Instr) (E : RAMEnv) (s : RAMState) :
runBlock (i :: code) E s = runBlock code E (execInstr i E s) := by
simp [runBlock, List.foldl_cons]
/-- Concatenation of straight-line blocks. -/
theorem runBlock_append (c₁ c₂ : List Instr) (E : RAMEnv) (s : RAMState) :
runBlock (c₁ ++ c₂) E s = runBlock c₂ E (runBlock c₁ E s) := by
simp [runBlock, List.foldl_append]
/-- A straight-line block advances the program counter by its length. -/
theorem runBlock_pc (code : List Instr) (E : RAMEnv) (s : RAMState) (hno : NoBranch code) :
(runBlock code E s).pc = s.pc + code.length := by
induction code generalizing s with
| nil => simp
| cons i tl ih =>
obtain ⟨hi, ht⟩ := hno
rw [runBlock_cons, ih (s := execInstr i E s) ht, execInstr_pc i E s hi]
simp only [List.length_cons]
omega
/-- Front peeling of iterates: the first step is applied first. -/
theorem iterate_succ_apply_front {α : Type} (f : α → α) (n : ℕ) (x : α) :
f^[n + 1] x = (f^[n]) (f x) := by
rw [Function.iterate_add_apply]
rfl
theorem At.cons {P : Program} {a : ℕ} {i : Instr} {l : List Instr} :
At P a (i :: l) ↔ P[a]? = some i ∧ At P (a + 1) l := by
constructor
· intro h
refine ⟨?_, fun r hr => ?_⟩
· have h0 := h 0 (by simp)
simpa using h0
· have h1 := h (r + 1) (by simpa using hr)
rw [show a + (r + 1) = a + 1 + r from by omega] at h1
simpa using h1
· rintro ⟨h1, h2⟩ r hr
cases r with
| zero => simpa using h1
| succ r =>
have h3 := h2 r (by simpa using hr)
rw [show a + (r + 1) = a + 1 + r from by omega]
simpa using h3
@[simp] theorem At.nil {P : Program} {a : ℕ} : At P a ([] : List Instr) ↔ True := by
unfold At
simp
theorem At.append {P : Program} {a : ℕ} {l₁ l₂ : List Instr} :
At P a (l₁ ++ l₂) ↔ At P a l₁ ∧ At P (a + l₁.length) l₂ := by
constructor
· intro h
refine ⟨fun r hr => ?_, fun r hr => ?_⟩
· have h' := h r (by simp only [List.length_append]; omega)
rwa [List.getElem?_append_left hr] at h'
· have h' := h (l₁.length + r) (by simp only [List.length_append]; omega)
rw [List.getElem?_append_right (by omega : l₁.length ≤ l₁.length + r)] at h'
rw [show l₁.length + r - l₁.length = r from by omega] at h'
rwa [show a + (l₁.length + r) = a + l₁.length + r from by omega] at h'
· intro ⟨h₁, h₂⟩ r hr
by_cases hlt : r < l₁.length
· rw [List.getElem?_append_left hlt]
exact h₁ r hlt
· rw [List.getElem?_append_right (by omega : l₁.length ≤ r)]
have hlen : (l₁ ++ l₂).length = l₁.length + l₂.length := List.length_append ..
rw [hlen] at hr
have h := h₂ (r - l₁.length) (by omega)
rwa [show a + l₁.length + (r - l₁.length) = a + r from by omega] at h
/-- A block found by `At` runs exactly as `runBlock` says. -/
theorem iterate_runBlock_of_at (P : Program) (E : RAMEnv) :
∀ (l : List Instr) (s : RAMState), At P s.pc l → NoBranch l →
(step P E)^[l.length] s = runBlock l E s
| [], s, _, _ => by simp
| i :: tl, s, ha, hno => by
obtain ⟨hi, ht⟩ := hno
have hg : P[s.pc]? = some i := by
have h := ha 0 (by simp)
simpa using h
have hstep : step P E s = execInstr i E s := step_eq_execInstr P E s i hg
have hpc : (execInstr i E s).pc = s.pc + 1 := execInstr_pc i E s hi
have ha' : At P (execInstr i E s).pc tl := by
intro r hr
rw [hpc]
have h := ha (r + 1) (by simpa using hr)
rw [show s.pc + (r + 1) = s.pc + 1 + r from by omega] at h
simpa using h
rw [List.length_cons, iterate_succ_apply_front, hstep, runBlock_cons]
exact iterate_runBlock_of_at P E tl (execInstr i E s) ha' ht
theorem Cond.noBranch_code (c : Cond) : NoBranch c.code := by
cases c with
| neqz r => simp [Cond.code]
| lt d a b => simp [Cond.code]
/-- A test holds exactly when its test register, after the test code, is nonzero. -/
theorem Cond.eval_iff (c : Cond) (E : RAMEnv) (s : RAMState) (hW : 1 < 2 ^ E.W) :
c.eval s ↔ (runBlock c.code E s).regs c.test ≠ 0 := by
cases c with
| neqz r => simp [Cond.eval, Cond.code, Cond.test]
| lt d a b =>
have hcode : Cond.code (Cond.lt d a b) = [iLt d a b] := rfl
have htest : Cond.test (Cond.lt d a b) = d := rfl
have hrun : (runBlock (Cond.code (Cond.lt d a b)) E s).regs (Cond.test (Cond.lt d a b))
= (if s.regs a < s.regs b then 1 else 0) % 2 ^ E.W := by
rw [hcode, htest, runBlock_cons, runBlock_nil, execInstr_lt]
simp
rw [hrun]
by_cases h : s.regs a < s.regs b
· rw [if_pos h, Nat.mod_eq_of_lt hW]
exact ⟨fun _ => one_ne_zero, fun _ => h⟩
· rw [if_neg h]
exact ⟨fun hc => absurd hc h, fun hc => absurd hc (by simp)⟩
theorem Stmt.length_compile (s : Stmt) (base : ℕ) : (s.compile base).length = s.len := by
induction s generalizing base with
| code l => rfl
| seq a b iha ihb =>
simp only [Stmt.compile, Stmt.len, iha, ihb, List.length_append] <;> omega
| ite c a b iha ihb =>
simp only [Stmt.compile, Stmt.len, iha, ihb, List.length_append, List.length_singleton,
List.length_cons, List.length_nil] <;> omega
| loop c b ih =>
simp only [Stmt.compile, Stmt.len, ih, List.length_append, List.length_singleton,
List.length_cons, List.length_nil] <;> omega
theorem at_loop {P : Program} {a : ℕ} {c : Cond} {b : Stmt}
(h : At P a (Stmt.compile (Stmt.loop c b) a)) :
At P a c.code ∧ P[a + c.code.length]? = some (iJz c.test (a + c.code.length + b.len + 2)) ∧
At P (a + c.code.length + 1) (b.compile (a + c.code.length + 1)) ∧
P[a + c.code.length + 1 + b.len]? = some (iJmp a) := by
simpa [Stmt.compile, Stmt.length_compile, At.append, At.cons, At.nil] using h
theorem at_ite {P : Program} {a : ℕ} {c : Cond} {sa sb : Stmt}
(h : At P a (Stmt.compile (Stmt.ite c sa sb) a)) :
At P a c.code ∧
P[a + c.code.length]? = some (iJz c.test (a + c.code.length + sa.len + 2)) ∧
At P (a + c.code.length + 1) (sa.compile (a + c.code.length + 1)) ∧
P[a + c.code.length + 1 + sa.len]? = some (iJmp (a + c.code.length + sa.len + sb.len + 3)) ∧
At P (a + c.code.length + 1 + sa.len + 1) (sb.compile (a + c.code.length + sa.len + 2)) ∧
P[a + c.code.length + 1 + sa.len + 1 + sb.len]? =
some (iJmp (a + c.code.length + sa.len + sb.len + 3)) := by
simpa [Stmt.compile, Stmt.length_compile, At.append, At.cons, At.nil] using h
/-- A block runs exactly as `runBlock` says. -/
theorem Sem.block (P : Program) (E : RAMEnv) (a : ℕ) (l : List Instr) (s : RAMState)
(hAt : At P a l) (hno : NoBranch l) (hpc : s.pc = a) :
Sem P E a (a + l.length) s (fun k s' => k = l.length ∧ s' = runBlock l E s) := by
refine ⟨hpc, l.length, runBlock l E s, ?_, ?_, rfl, rfl⟩
· exact iterate_runBlock_of_at P E l s (hpc.symm ▸ hAt) hno
· rw [runBlock_pc l E s hno, hpc]
/-- One instruction. -/
theorem Sem.exec (P : Program) (E : RAMEnv) (a b : ℕ) (s : RAMState) (i : Instr)
(hAt : P[a]? = some i) (hpc : s.pc = a) (hb : (execInstr i E s).pc = b) :
Sem P E a b s (fun k s' => k = 1 ∧ s' = execInstr i E s) := by
refine ⟨hpc, 1, execInstr i E s, ?_, hb, rfl, rfl⟩
rw [Function.iterate_one, step_eq_execInstr P E s i (by rwa [← hpc] at hAt)]
/-- Weakening the postcondition. -/
theorem Sem.mono {P : Program} {E : RAMEnv} {a b : ℕ} {s : RAMState}
{Q Q' : ℕ → RAMState → Prop} (h : Sem P E a b s Q) (hQ : ∀ k s', Q k s' → Q' k s') :
Sem P E a b s Q' := by
obtain ⟨hpc, k, s', hstep, hb, hQ'⟩ := h
exact ⟨hpc, k, s', hstep, hb, hQ k s' hQ'⟩
/-- A `jz` whose test register is zero takes its target, in one step. -/
theorem Sem.jz_taken (P : Program) (E : RAMEnv) (a t : ℕ) (c : Cond) (s : RAMState)
(hAt : P[a]? = some (iJz c.test t)) (hpc : s.pc = a) (h0 : s.regs c.test = 0) :
Sem P E a t s (fun k s' => k = 1 ∧ s' = { s with pc := t }) := by
refine Sem.mono (Sem.exec P E a t s (iJz c.test t) hAt hpc ?_) ?_
· simp [execInstr_jz, h0]
· intro k s' h
obtain ⟨rfl, rfl⟩ := h
exact ⟨rfl, by simp [execInstr_jz, h0]⟩
/-- A `jz` whose test register is nonzero falls through, in one step. -/
theorem Sem.jz_next (P : Program) (E : RAMEnv) (a t : ℕ) (c : Cond) (s : RAMState)
(hAt : P[a]? = some (iJz c.test t)) (hpc : s.pc = a) (h0 : s.regs c.test ≠ 0) :
Sem P E a (a + 1) s (fun k s' => k = 1 ∧ s' = { s with pc := a + 1 }) := by
refine Sem.mono (Sem.exec P E a (a + 1) s (iJz c.test t) hAt hpc ?_) ?_
· simp [execInstr_jz, h0, hpc]
· intro k s' h
obtain ⟨rfl, rfl⟩ := h
exact ⟨rfl, by simp [execInstr_jz, h0, hpc]⟩
/-- Two exact runs glue, and the costs add. -/
theorem Sem.trans {P : Program} {E : RAMEnv} {a b c : ℕ} {s : RAMState} {n₁ n₂ : ℕ}
{s₁ s₂ : RAMState}
(h₁ : Sem P E a b s (fun k s' => k = n₁ ∧ s' = s₁))
(h₂ : Sem P E b c s₁ (fun k s' => k = n₂ ∧ s' = s₂)) :
Sem P E a c s (fun k s' => k = n₁ + n₂ ∧ s' = s₂) := by
obtain ⟨hpc, k₁, t₁, hs₁, -, hk₁, ht₁⟩ := h₁
obtain ⟨-, k₂, t₂, hs₂, hc, hk₂, ht₂⟩ := h₂
refine ⟨hpc, k₁ + k₂, s₂, ?_, ?_, by omega, rfl⟩
· rw [Nat.add_comm k₁ k₂, Function.iterate_add_apply, hs₁, ht₁, hs₂, ht₂]
· rw [← ht₂]
exact hc
/-- Sequential composition: the second run may depend on the cost and the state of the first. -/
theorem Sem.seq {P : Program} {E : RAMEnv} {a b c : ℕ} {s : RAMState}
{Q₁ : ℕ → RAMState → Prop} {Q₂ : ℕ → ℕ → RAMState → Prop}
(h₁ : Sem P E a b s Q₁)
(h₂ : ∀ (k₁ : ℕ) (s₁ : RAMState), Q₁ k₁ s₁ → Sem P E b c s₁ (Q₂ k₁)) :
Sem P E a c s (fun k s' => ∃ k₁ k₂, k = k₁ + k₂ ∧ Q₂ k₁ k₂ s') := by
obtain ⟨hpc, k₁, s₁, hs₁, -, hQ₁⟩ := h₁
obtain ⟨-, k₂, s₂, hs₂, hc, hQ₂⟩ := h₂ k₁ s₁ hQ₁
refine ⟨hpc, k₁ + k₂, s₂, ?_, hc, k₁, k₂, rfl, hQ₂⟩
rw [Nat.add_comm k₁ k₂, Function.iterate_add_apply, hs₁, hs₂]
/-- Append a `jmp`: the postcondition sees the state with its program counter already moved. -/
theorem Sem.jmp_append {P : Program} {E : RAMEnv} {a b c : ℕ} {s : RAMState}
{Q : ℕ → RAMState → Prop} (hAt : P[b]? = some (iJmp c))
(h : Sem P E a b s (fun t s' => Q (t + 1) { s' with pc := c })) :
Sem P E a c s Q := by
obtain ⟨hpc, k, s', hstep, hpb, hQ⟩ := h
have hstep' : (step P E)^[k + 1] s = { s' with pc := c } := by
rw [show k + 1 = 1 + k from by omega, Function.iterate_add_apply, Function.iterate_one, hstep,
step_eq_execInstr P E s' (iJmp c) (by rw [hpb]; exact hAt), execInstr_jmp]
exact ⟨hpc, k + 1, { s' with pc := c }, hstep', rfl, hQ⟩
/-- A conditional. Both branches run from their own entry address to their trailing `jmp`; the
postcondition sees the cost *plus* the test, the `jz` and the `jmp`, and the state with the program
counter already at the exit. -/
theorem Sem.ite (P : Program) (E : RAMEnv) (a : ℕ) (c : Cond) (sa sb : Stmt) (s : RAMState)
(Q : ℕ → RAMState → Prop) (hAt : At P a (Stmt.compile (Stmt.ite c sa sb) a)) (hW : 1 < 2 ^ E.W)
(hpc : s.pc = a)
(htrue : c.eval s → Sem P E (a + c.code.length + 1) (a + c.code.length + 1 + sa.len)
{ runBlock c.code E s with pc := a + c.code.length + 1 }
(fun t s' => Q (c.code.length + 1 + t + 1) { s' with pc := a + c.code.length + sa.len + sb.len + 3 }))
(hfalse : ¬ c.eval s → Sem P E (a + c.code.length + sa.len + 2)
(a + c.code.length + 1 + sa.len + 1 + sb.len)
{ runBlock c.code E s with pc := a + c.code.length + sa.len + 2 }
(fun t s' => Q (c.code.length + 1 + t + 1) { s' with pc := a + c.code.length + sa.len + sb.len + 3 })) :
Sem P E a (a + c.code.length + sa.len + sb.len + 3) s Q := by
obtain ⟨hcode, hjz, -, hjmpA, -, hjmpB⟩ := at_ite hAt
have htest : Sem P E a (a + c.code.length) s
(fun k s' => k = c.code.length ∧ s' = runBlock c.code E s) :=
Sem.block P E a c.code s hcode (Cond.noBranch_code c) hpc
have hpcT : (runBlock c.code E s).pc = a + c.code.length := by
rw [runBlock_pc c.code E s (Cond.noBranch_code c), hpc]
by_cases hgo : c.eval s
· have hne : (runBlock c.code E s).regs c.test ≠ 0 := (Cond.eval_iff c E s hW).mp hgo
have hstep : Sem P E (a + c.code.length) (a + c.code.length + 1) (runBlock c.code E s)
(fun k s' => k = 1 ∧ s' = { runBlock c.code E s with pc := a + c.code.length + 1 }) :=
Sem.jz_next P E (a + c.code.length) (a + c.code.length + sa.len + 2) c _ hjz hpcT hne
refine Sem.jmp_append hjmpA ?_
refine Sem.mono (Sem.seq (Q₁ := fun k s' => k = c.code.length + 1 ∧
s' = { runBlock c.code E s with pc := a + c.code.length + 1 })
(Q₂ := fun k₁ k₂ s' => k₁ = (c.code.length + 1) ∧
Q ((c.code.length + 1) + k₂ + 1) { s' with pc := a + c.code.length + sa.len + sb.len + 3 })
(Sem.trans htest hstep) ?_) ?_
· intro k₁ s₁ hQ₁
obtain ⟨rfl, rfl⟩ : k₁ = c.code.length + 1 ∧
s₁ = { runBlock c.code E s with pc := a + c.code.length + 1 } := hQ₁
exact Sem.mono (htrue hgo) (fun k s' h => ⟨rfl, h⟩)
· intro k s' h
obtain ⟨k₁, k₂, hk, hQ⟩ := h
have he : (c.code.length + 1) + k₂ + 1 = k + 1 := by omega
rw [he] at hQ
exact hQ.2
· have h0 : (runBlock c.code E s).regs c.test = 0 := by
by_contra hne
exact hgo ((Cond.eval_iff c E s hW).mpr hne)
have hstep : Sem P E (a + c.code.length) (a + c.code.length + sa.len + 2) (runBlock c.code E s)
(fun k s' => k = 1 ∧ s' = { runBlock c.code E s with pc := a + c.code.length + sa.len + 2 }) :=
Sem.jz_taken P E (a + c.code.length) (a + c.code.length + sa.len + 2) c _ hjz hpcT h0
refine Sem.jmp_append hjmpB ?_
refine Sem.mono (Sem.seq (Q₁ := fun k s' => k = c.code.length + 1 ∧
s' = { runBlock c.code E s with pc := a + c.code.length + sa.len + 2 })
(Q₂ := fun k₁ k₂ s' => k₁ = (c.code.length + 1) ∧
Q ((c.code.length + 1) + k₂ + 1) { s' with pc := a + c.code.length + sa.len + sb.len + 3 })
(Sem.trans htest hstep) ?_) ?_
· intro k₁ s₁ hQ₁
obtain ⟨rfl, rfl⟩ : k₁ = c.code.length + 1 ∧
s₁ = { runBlock c.code E s with pc := a + c.code.length + sa.len + 2 } := hQ₁
exact Sem.mono (hfalse hgo) (fun k s' h => ⟨rfl, h⟩)
· intro k s' h
obtain ⟨k₁, k₂, hk, hQ⟩ := h
have he : (c.code.length + 1) + k₂ + 1 = k + 1 := by omega
rw [he] at hQ
exact hQ.2
/-- Leaving the loop: the test fails, the `jz` fires, control lands past the statement. -/
theorem Sem.loopExit (P : Program) (E : RAMEnv) (a : ℕ) (c : Cond) (b : Stmt) (s : RAMState)
(hAt : At P a (Stmt.compile (Stmt.loop c b) a)) (hW : 1 < 2 ^ E.W) (hpc : s.pc = a)
(hstop : ¬ c.eval s) :
Sem P E a (a + c.code.length + b.len + 2) s
(fun k s' => k = c.code.length + 1 ∧
s' = { runBlock c.code E s with pc := a + c.code.length + b.len + 2 }) := by
obtain ⟨hcode, hjz, -, -⟩ := at_loop hAt
have htest : Sem P E a (a + c.code.length) s
(fun k s' => k = c.code.length ∧ s' = runBlock c.code E s) :=
Sem.block P E a c.code s hcode (Cond.noBranch_code c) hpc
have hpcT : (runBlock c.code E s).pc = a + c.code.length := by
rw [runBlock_pc c.code E s (Cond.noBranch_code c), hpc]
have h0 : (runBlock c.code E s).regs c.test = 0 := by
by_contra hne
exact hstop ((Cond.eval_iff c E s hW).mpr hne)
exact Sem.trans htest
(Sem.jz_taken P E (a + c.code.length) (a + c.code.length + b.len + 2) c _ hjz hpcT h0)
/-- One iteration that returns to the head: the test holds, the `jz` falls through, the body runs
from the body entry back to the loop head. -/
theorem Sem.loopStep (P : Program) (E : RAMEnv) (a : ℕ) (c : Cond) (b : Stmt)
(s s' : RAMState) (cost : ℕ) (hAt : At P a (Stmt.compile (Stmt.loop c b) a)) (hW : 1 < 2 ^ E.W)
(hpc : s.pc = a) (hgo : c.eval s)
(hbody : Sem P E (a + c.code.length + 1) a { runBlock c.code E s with pc := a + c.code.length + 1 }
(fun k s'' => k = cost ∧ s'' = s')) :
Sem P E a a s (fun k s'' => k = (c.code.length + 1) + cost ∧ s'' = s') := by
obtain ⟨hcode, hjz, -, -⟩ := at_loop hAt
have htest : Sem P E a (a + c.code.length) s
(fun k s' => k = c.code.length ∧ s' = runBlock c.code E s) :=
Sem.block P E a c.code s hcode (Cond.noBranch_code c) hpc
have hne : (runBlock c.code E s).regs c.test ≠ 0 := (Cond.eval_iff c E s hW).mp hgo
have hpcT : (runBlock c.code E s).pc = a + c.code.length := by
rw [runBlock_pc c.code E s (Cond.noBranch_code c), hpc]
have hfall : Sem P E (a + c.code.length) (a + c.code.length + 1) (runBlock c.code E s)
(fun k s' => k = 1 ∧ s' = { runBlock c.code E s with pc := a + c.code.length + 1 }) :=
Sem.jz_next P E (a + c.code.length) (a + c.code.length + b.len + 2) c _ hjz hpcT hne
exact Sem.trans (Sem.trans htest hfall) hbody
/-- **The loop rule.** `n` iterations from the loop head, then the failing test. The iteration
invariant is an explicit family `s : ℕ → RAMState` of loop-head states, with per-iteration costs
`cost : ℕ → ℕ`; the caller supplies one `Sem` per iteration. -/
theorem Sem.loop (P : Program) (E : RAMEnv) (a : ℕ) (c : Cond) (b : Stmt)
(hAt : At P a (Stmt.compile (Stmt.loop c b) a)) (hW : 1 < 2 ^ E.W) :
∀ (n : ℕ) (s : ℕ → RAMState) (cost : ℕ → ℕ),
(∀ j, (s j).pc = a) →
(∀ j < n, c.eval (s j)) →
(¬ c.eval (s n)) →
(∀ j < n, Sem P E (a + c.code.length + 1) a
{ runBlock c.code E (s j) with pc := a + c.code.length + 1 }
(fun k s' => k = cost j ∧ s' = s (j + 1))) →
Sem P E a (a + c.code.length + b.len + 2) (s 0)
(fun k s' => k ≤ (c.code.length + 1) +
∑ j ∈ Finset.range n, (c.code.length + 1 + cost j) ∧
s' = { runBlock c.code E (s n) with pc := a + c.code.length + b.len + 2 }) := by
intro n
induction n with
| zero =>
intro s cost hpc _ hstop _
refine Sem.mono (Sem.loopExit P E a c b (s 0) hAt hW (hpc 0) hstop) ?_
intro k s' h
obtain ⟨rfl, rfl⟩ := h
exact ⟨by simp, rfl⟩
| succ n ih =>
intro s cost hpc hgo hstop hstep
have hfirst : Sem P E a a (s 0) (fun k s' => k = (c.code.length + 1) + cost 0 ∧ s' = s 1) :=
Sem.loopStep P E a c b (s 0) (s 1) (cost 0) hAt hW (hpc 0) (hgo 0 (by omega))
(hstep 0 (by omega))
have hrest : Sem P E a (a + c.code.length + b.len + 2) (s 1)
(fun k s' => k ≤ (c.code.length + 1) +
∑ j ∈ Finset.range n, (c.code.length + 1 + cost (j + 1)) ∧
s' = { runBlock c.code E (s (n + 1)) with pc := a + c.code.length + b.len + 2 }) :=
ih (fun j => s (j + 1)) (fun j => cost (j + 1)) (fun j => hpc (j + 1))
(fun j hj => hgo (j + 1) (by omega)) (by simpa using hstop)
(fun j hj => hstep (j + 1) (by omega))
refine Sem.mono (Sem.seq (Q₂ := fun k₁ k₂ s' =>
k₁ = (c.code.length + 1) + cost 0 ∧
(k₂ ≤ (c.code.length + 1) +
∑ j ∈ Finset.range n, (c.code.length + 1 + cost (j + 1)) ∧
s' = { runBlock c.code E (s (n + 1)) with pc := a + c.code.length + b.len + 2 })) hfirst ?_) ?_
· intro k₁ s₁ hQ₁
obtain ⟨rfl, rfl⟩ : k₁ = (c.code.length + 1) + cost 0 ∧ s₁ = s 1 := hQ₁
exact Sem.mono hrest (fun k s' h => ⟨rfl, h.1, h.2⟩)
· intro k s' h
obtain ⟨k₁, k₂, hk, h₁, h₂, hstate⟩ := h
rw [Finset.sum_range_succ']
exact ⟨by omega, hstate⟩
section Enc
variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
/-- A bit of the integer spelling is the corresponding basis coordinate. -/
theorem enc_bit (b : Module.Basis (Fin w) (ZMod 2) F) (z : F) (k : Fin w) :
enc b z / 2 ^ (k : ℕ) % 2 = (b.repr z k).val := by
have hf : ∀ j : Fin w, (b.repr z j).val < 2 ^ 1 := by
intro j
have := ZMod.val_lt (b.repr z j)
simpa using this
have h := extract_field_sum 1 w (by norm_num) (fun j : Fin w => (b.repr z j).val) hf k
rw [Nat.and_two_pow_sub_one_eq_mod, Nat.shiftRight_eq_div_pow] at h
simpa [enc, Nat.mul_one] using h
/-- `dec` inverts `enc`. -/
theorem dec_enc (b : Module.Basis (Fin w) (ZMod 2) F) (z : F) : dec b (enc b z) = z := by
have h : ∀ k : Fin w, b.repr (dec b (enc b z)) k = b.repr z k := by
intro k
rw [dec, LinearEquiv.apply_symm_apply]
simp only [Finsupp.coe_equivFunOnFinite_symm]
rw [show (((enc b z / 2 ^ (k : ℕ)) % 2 : ℕ) : ZMod 2) = (((b.repr z k).val : ℕ) : ZMod 2) from by
rw [enc_bit b z k]]
exact ZMod.natCast_zmod_val (b.repr z k)
apply b.repr.injective
ext k
exact h k
/-- The integer spelling of a field element is a `w`-bit number. -/
theorem enc_lt (b : Module.Basis (Fin w) (ZMod 2) F) (z : F) : enc b z < 2 ^ w := by
have h1 : enc b z ≤ ∑ k : Fin w, 2 ^ (k : ℕ) := by
refine Finset.sum_le_sum (fun k _ => ?_)
calc (b.repr z k).val * 2 ^ (k : ℕ) ≤ 1 * 2 ^ (k : ℕ) := by
refine Nat.mul_le_mul_right _ ?_
have := ZMod.val_lt (b.repr z k)
omega
_ = 2 ^ (k : ℕ) := Nat.one_mul _
have h2 : (∑ k : Fin w, 2 ^ (k : ℕ)) = ∑ k ∈ Finset.range w, 2 ^ k :=
Fin.sum_univ_eq_sum_range (fun k => 2 ^ k) w
rw [h2] at h1
exact lt_of_le_of_lt h1 (sum_range_two_pow_lt w)
end Enc
section Tables
variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
@[simp] theorem hdrTab_zero (t N w : ℕ) : hdrTab t N w 0 = t := rfl
@[simp] theorem hdrTab_one (t N w : ℕ) : hdrTab t N w 1 = w := rfl
@[simp] theorem hdrTab_eight (t N w : ℕ) : hdrTab t N w 8 = detInvBase w := rfl
theorem detStd_hdr (t N w : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) {a : ℕ}
(ha : a < 13) : detStd t N b ι a = hdrTab t N w a := by
simp [detStd, ha]
/-- `detSqBase` in explicit form. -/
theorem detSqBase_eq (w : ℕ) : detSqBase w = 64 + 2 ^ (2 * w) := rfl
/-- `detMulBase` in explicit form. -/
theorem detMulBase_eq (w : ℕ) : detMulBase w = 64 := rfl
/-- **The squaring table is at a known address**: `detSqBase w + a` holds `sqTab b a` for every
`w`-bit `a`. -/
theorem detStd_sq (t N w : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) {a : ℕ}
(ha : a < 2 ^ w) : detStd t N b ι (detSqBase w + a) = sqTab b a := by
have hpos : (0 : ℕ) < 2 ^ (2 * w) := Nat.two_pow_pos _
have hwle : (2 : ℕ) ^ w ≤ 2 ^ (2 * w) := Nat.pow_le_pow_right (by norm_num) (by omega)
have h1 : ¬ (detSqBase w + a < 13) := by rw [detSqBase_eq]; omega
have h2 : ¬ (detSqBase w + a < detMulBase w) := by rw [detSqBase_eq, detMulBase_eq]; omega
have h3 : ¬ (detSqBase w + a < detSqBase w) := by omega
have h4 : detSqBase w + a < detInvBase w := by unfold detInvBase; omega
unfold detStd
rw [if_neg h1, if_neg h2, if_neg h3, if_pos h4]
congr 1
omega
end Tables
section ReadInt
/-- Divisions are unchanged by adding a remainder that stays below the divisor. -/
theorem add_div_of_mod_add_lt {A b c : ℕ} (h : A % c + b < c) : (A + b) / c = A / c := by
have hc : 0 < c := by omega
have h1 : c * (A / c) + (A % c + b) = A + b := by
have h2 := Nat.div_add_mod A c
omega
rw [← h1, Nat.mul_add_div hc, Nat.div_eq_of_lt h, Nat.add_zero]
/-- `wordsOf` for a word that holds eight `w`-bit fields: `⌈t/8⌉` words. `as in the paper`, the
payload of `tw` bits occupies `tw / W = ⌈t/8⌉` words of `W = 8w` bits. -/
theorem wordsOf_eight (w t : ℕ) (hw : 0 < w) : wordsOf (8 * w) (t * w) = (t + 7) / 8 := by
unfold wordsOf
have h1 : t * w + 8 * w - 1 = (t + 7) * w + (w - 1) := by
have h2 : t * w + 8 * w = (t + 8) * w := by rw [Nat.add_mul]
have h3 : (t + 8) * w = (t + 7) * w + w := by
rw [show t + 8 = t + 7 + 1 from rfl, Nat.succ_mul]
rw [h2, h3]
omega
rw [h1]
have h4 : (t + 7) * w % (8 * w) + (w - 1) < 8 * w := by
rw [Nat.mul_mod_mul_right w (t + 7) 8]
have h5 : (t + 7) % 8 ≤ 7 := by
have h6 : (t + 7) % 8 < 8 := Nat.mod_lt _ (by norm_num)
omega
have h6 : (t + 7) % 8 * w ≤ 7 * w := Nat.mul_le_mul_right w h5
omega
rw [add_div_of_mod_add_lt h4, Nat.mul_comm (t + 7) w, Nat.mul_comm 8 w,
Nat.mul_div_mul_left (t + 7) 8 hw]
end ReadInt
section ReadLoop
end ReadLoop
section ProgramAt
end ProgramAt
section ReadSpec
end ReadSpec
section ReadStmt
/-- A constant sum over a range. -/
theorem sum_range_const_mul (t c : ℕ) : (∑ j ∈ Finset.range t, c) = c * t := by
induction t with
| zero => simp
| succ n ih =>
rw [Finset.sum_range_succ, ih]
ring
end ReadStmt
section Bounds
/-- `wordsOf (8w) (tw) ≤ t`: the payload never needs more words than it has syndrome coordinates. -/
theorem wordsOf_le (w t : ℕ) (hw1 : 1 ≤ w) : wordsOf (8 * w) (t * w) ≤ t := by
rw [wordsOf_eight w t (by omega)]
omega
/-- The squaring table of `det` starts inside a word: `detSqBase w = 64 + 2^{2w} < 2^{8w}`. -/
theorem detSqBase_lt {w : ℕ} (hw1 : 1 ≤ w) : detSqBase w < 2 ^ (8 * w) := by
by_cases hw4 : w ≤ 3
· unfold detSqBase detMulBase
interval_cases w <;> norm_num
· have hw4' : 3 < w := by omega
have h3 : (64 : ℕ) ≤ 2 ^ (2 * w) := by
have h : (2 : ℕ) ^ 6 ≤ 2 ^ (2 * w) := Nat.pow_le_pow_right (by norm_num) (by omega)
calc (64 : ℕ) = 2 ^ 6 := by norm_num
_ ≤ 2 ^ (2 * w) := h
have h5 : (2 : ℕ) ^ (2 * w) + 2 ^ (2 * w) = 2 ^ (2 * w + 1) := by
rw [Nat.pow_succ]
ring
have h6 : (2 : ℕ) ^ (2 * w + 1) < 2 ^ (8 * w) := Nat.pow_lt_pow_right (by norm_num) (by omega)
have h7 : 64 + 2 ^ (2 * w) ≤ 2 ^ (2 * w) + 2 ^ (2 * w) := by omega
rw [detSqBase, detMulBase]
calc 64 + 2 ^ (2 * w) ≤ 2 ^ (2 * w) + 2 ^ (2 * w) := h7
_ = 2 ^ (2 * w + 1) := h5
_ < 2 ^ (8 * w) := h6
/-- The whole table ends inside a word: `detInvBase w < 2^{8w}`. -/
theorem detInvBase_lt {w : ℕ} (hw1 : 1 ≤ w) : detInvBase w < 2 ^ (8 * w) := by
by_cases hw3 : w ≤ 2
· unfold detInvBase detSqBase detMulBase
interval_cases w <;> norm_num
· have h3 : (64 : ℕ) ≤ 2 ^ (2 * w) := by
have h : (2 : ℕ) ^ 6 ≤ 2 ^ (2 * w) := Nat.pow_le_pow_right (by norm_num) (by omega)
calc (64 : ℕ) = 2 ^ 6 := by norm_num
_ ≤ 2 ^ (2 * w) := h
have hA : (2 : ℕ) ^ (2 * w) + 2 ^ (2 * w) = 2 ^ (2 * w + 1) := by
rw [Nat.pow_succ]
ring
have hB : (2 : ℕ) ^ (2 * w + 1) + 2 ^ (2 * w + 1) = 2 ^ (2 * w + 2) := by
rw [Nat.pow_succ]
ring
have h1 : detInvBase w ≤ 2 ^ (2 * w + 2) := by
unfold detInvBase detSqBase detMulBase
omega
have h2 : (2 : ℕ) ^ (2 * w + 2) < 2 ^ (8 * w) :=
Nat.pow_lt_pow_right (by norm_num) (by omega)
omega
end Bounds
section Prologue
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 successor step, stated with an explicit `Nat.succ` so that the generated `match`
reduces during elaboration. -/
theorem eSeq_succ {w : ℕ} (b : Module.Basis (Fin w) (ZMod 2) F) {M : ℕ} (y : Fin M → ZMod 2) (n : ℕ) :
eSeq b y (Nat.succ n)
= if Even (Nat.succ n) then payloadField b y (Nat.succ n / 2)
else (eSeq b y (Nat.succ n / 2)) ^ 2 := by
rw [eSeq.eq_def]
theorem eSeq_even {w : ℕ} (b : Module.Basis (Fin w) (ZMod 2) F) {M : ℕ} (y : Fin M → ZMod 2) (k : ℕ) :
eSeq b y (2 * k) = payloadField b y k := by
cases k with
| zero => rw [eSeq.eq_def]
| succ j =>
have harg : 2 * (j + 1) = Nat.succ (2 * j + 1) := by omega
rw [harg, eSeq_succ,
if_pos (show Even (Nat.succ (2 * j + 1)) from ⟨j + 1, by omega⟩)]
congr 1
show (2 * j + 2) / 2 = j + 1
omega
theorem eSeq_odd {w : ℕ} (b : Module.Basis (Fin w) (ZMod 2) F) {M : ℕ} (y : Fin M → ZMod 2) (k : ℕ) :
eSeq b y (2 * k + 1) = (eSeq b y k) ^ 2 := by
have harg : 2 * k + 1 = Nat.succ (2 * k) := by omega
rw [harg, eSeq_succ,
if_neg (show ¬ Even (Nat.succ (2 * k)) from by rintro ⟨r, hr⟩; omega)]
rw [show Nat.succ (2 * k) / 2 = k from by
show (2 * k + 1) / 2 = k
omega]
end Expand
section ExpandStd
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end ExpandStd
@[simp] theorem enc_zero {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) : enc b 0 = 0 := by
simp [enc]
theorem enc_injective {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) : Function.Injective (enc b) := by
intro x y h
have hd := congrArg (dec b) h
simpa only [dec_enc] using hd
theorem enc_testBit {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (z : F) (k : ℕ) (hk : k < w) :
(enc b z).testBit k = decide (b.repr z ⟨k, hk⟩ = 1) := by
rw [Nat.testBit_eq_decide_div_mod_eq, enc_bit b z ⟨k, hk⟩]
rcases zmod2_eq_zero_or_one (b.repr z ⟨k, hk⟩) with h | h <;> norm_num [h] <;> decide
/-- Machine XOR is addition in the supplied basis. -/
theorem enc_add_xor {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (x y : F) :
enc b (x + y) = enc b x ^^^ enc b y := by
apply Nat.eq_of_testBit_eq
intro k
rw [Nat.testBit_xor]
by_cases hk : k < w
· rw [enc_testBit b (x + y) k hk, enc_testBit b x k hk, enc_testBit b y k hk]
simp only [map_add, Finsupp.add_apply]
rcases zmod2_eq_zero_or_one (b.repr x ⟨k, hk⟩) with hx | hx <;>
rcases zmod2_eq_zero_or_one (b.repr y ⟨k, hk⟩) with hy | hy <;>
norm_num [hx, hy] <;> decide
· have hpow : (2 : ℕ) ^ w ≤ 2 ^ k := Nat.pow_le_pow_right (by norm_num) (by omega)
have h0 := Nat.testBit_eq_false_of_lt (lt_of_lt_of_le (enc_lt b (x + y)) hpow)
have hx := Nat.testBit_eq_false_of_lt (lt_of_lt_of_le (enc_lt b x) hpow)
have hy := Nat.testBit_eq_false_of_lt (lt_of_lt_of_le (enc_lt b y) hpow)
rw [h0, hx, hy]
rfl
theorem pairIdx_lt (w a c : ℕ) (ha : a < 2 ^ w) (hc : c < 2 ^ w) :
pairIdx w a c < 2 ^ (2 * w) := by
have hexp : 2 ^ (2 * w) = (2 : ℕ) ^ w * 2 ^ w := by
rw [show 2 * w = w + w by omega, Nat.pow_add]
rw [hexp, pairIdx]
calc
a * 2 ^ w + c < a * 2 ^ w + 2 ^ w := Nat.add_lt_add_left hc _
_ = (a + 1) * 2 ^ w := by ring
_ ≤ 2 ^ w * 2 ^ w := Nat.mul_le_mul_right _ (by omega)
theorem detEnd_lt {w : ℕ} (hw : 1 ≤ w) : detEnd w < 2 ^ (8 * w) := by
by_cases hs : w ≤ 3
· unfold detEnd detImgBase detPosBase detInvBase detSqBase detMulBase
interval_cases w <;> norm_num
· have h64 : (64 : ℕ) ≤ 2 ^ (2 * w) := by
have h := Nat.pow_le_pow_right (n := 2) (by norm_num) (by omega : 6 ≤ 2 * w)
exact h
have hq : (2 : ℕ) ^ w ≤ 2 ^ (2 * w) := Nat.pow_le_pow_right (by norm_num) (by omega)
have heq : detEnd w = 64 + 2 * 2 ^ (2 * w) + 3 * 2 ^ w := by
unfold detEnd detImgBase detPosBase detInvBase detSqBase detMulBase
ring
have hsum : detEnd w ≤ 6 * 2 ^ (2 * w) := by rw [heq]; omega
have hpos := Nat.two_pow_pos (2 * w)
have hstrict : 6 * 2 ^ (2 * w) < 8 * 2 ^ (2 * w) := by omega
have hp : (8 : ℕ) * 2 ^ (2 * w) = 2 ^ (2 * w + 3) := by
rw [Nat.pow_add]
norm_num <;> ring
have hupper : (2 : ℕ) ^ (2 * w + 3) ≤ 2 ^ (8 * w) :=
Nat.pow_le_pow_right (by norm_num) (by omega)
omega
theorem detStd_mul {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(t N : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F)
{a c : ℕ} (ha : a < 2 ^ w) (hc : c < 2 ^ w) :
detStd t N b ι (detMulBase w + pairIdx w a c) = mulTab b a c := by
have hi := pairIdx_lt w a c ha hc
have h0 : ¬ detMulBase w + pairIdx w a c < 13 := by unfold detMulBase; omega
have h1 : ¬ detMulBase w + pairIdx w a c < detMulBase w := by omega
have h2 : detMulBase w + pairIdx w a c < detSqBase w := by unfold detSqBase; omega
have hdiv : pairIdx w a c / 2 ^ w = a := by
rw [pairIdx, Nat.mul_comm a (2 ^ w), Nat.mul_add_div (Nat.two_pow_pos w),
Nat.div_eq_of_lt hc, Nat.add_zero]
have hmod : pairIdx w a c % 2 ^ w = c := by
rw [pairIdx, Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hc]
unfold detStd
rw [if_neg h0, if_neg h1, if_pos h2, Nat.add_sub_cancel_left, hdiv, hmod]
theorem detStd_inv {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(t N : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F)
{a : ℕ} (ha : a < 2 ^ w) :
detStd t N b ι (detInvBase w + a) = invTab b a := by
have hpos : 0 < (2 : ℕ) ^ (2 * w) := Nat.two_pow_pos _
have hinv : detInvBase w = 64 + 2 ^ (2 * w) + 2 ^ (2 * w) := rfl
have hsq : detSqBase w = 64 + 2 ^ (2 * w) := rfl
have hmul : detMulBase w = 64 := rfl
have h0 : ¬ detInvBase w + a < 13 := by omega
have h1 : ¬ detInvBase w + a < detMulBase w := by omega
have h2 : ¬ detInvBase w + a < detSqBase w := by omega
have h3 : ¬ detInvBase w + a < detInvBase w := by omega
have h4 : detInvBase w + a < detPosBase w := by unfold detPosBase; omega
unfold detStd
rw [if_neg h0, if_neg h1, if_neg h2, if_neg h3, if_pos h4, Nat.add_sub_cancel_left]
/-- Exact result and scratch-register contents of a multiplication. -/
theorem fieldMulCode_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(E : RAMEnv) (s : RAMState) (x y : F) (hw : 1 ≤ w)
(hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hwreg : s.regs r3 = w) (hx : s.regs r10 = enc b x) (hy : s.regs r11 = enc b y) :
runBlock fieldMulCode E s =
{ s with pc := s.pc + 7, regs := Function.update (Function.update (Function.update s.regs r15 64) r14 (pairIdx w (enc b x) (enc b y) + 64)) r10 (enc b (x * y)) } := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have hi := pairIdx_lt w (enc b x) (enc b y) (enc_lt b x) (enc_lt b y)
have hbase := detSqBase_lt hw
have h64 : (64 : ℕ) < 2 ^ E.W := by rw [hW]; unfold detSqBase detMulBase at hbase; omega
have h1 : (1 : ℕ) < 2 ^ E.W := by omega
have hq : (2 : ℕ) ^ w < 2 ^ E.W := by
rw [hW]
exact Nat.pow_lt_pow_right (by norm_num) (by omega)
have ha : enc b x * 2 ^ w < 2 ^ E.W := by
unfold pairIdx at hi
rw [hW]
unfold detSqBase detMulBase at hbase
omega
have hib : pairIdx w (enc b x) (enc b y) < 2 ^ E.W := by
rw [hW]
unfold detSqBase detMulBase at hbase
omega
have haddr : pairIdx w (enc b x) (enc b y) + 64 < 2 ^ E.W := by
rw [hW]
unfold detSqBase detMulBase at hbase
omega
have htab : E.det (pairIdx w (enc b x) (enc b y) + 64) = enc b (x * y) := by
rw [hdet]
have haeq : pairIdx w (enc b x) (enc b y) + 64 =
detMulBase w + pairIdx w (enc b x) (enc b y) := by unfold detMulBase; omega
rw [haeq, detStd_mul t N b ι (enc_lt b x) (enc_lt b y), mulTab, dec_enc, dec_enc]
have hv : enc b (x * y) < 2 ^ E.W := lt_of_lt_of_le (enc_lt b _) hpow
unfold pairIdx at hi hib haddr htab ⊢
apply ramState_eq_of
· simp only [fieldMulCode, Fin.isValue, runBlock_cons, execInstr, Function.update_self, ne_eq,
Fin.reduceEq, not_false_eq_true, Function.update_of_ne, Nat.mod_mul_mod, one_mul, Function.update_idem,
Nat.mul_mod_mod, Nat.mod_add_mod, Nat.add_mod_mod, runBlock_nil, Nat.add_right_cancel_iff,
Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
fin_cases d <;>
simp only [fieldMulCode, Fin.isValue, runBlock_cons, execInstr, Nat.mod_eq_of_lt h1,
Function.update_self, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne, hwreg, one_mul,
Nat.mod_eq_of_lt hq, Function.update_idem, hx, Nat.mod_eq_of_lt ha, hy, Nat.mod_eq_of_lt hib,
Nat.mod_eq_of_lt h64, Nat.mod_eq_of_lt haddr, htab, Nat.mod_eq_of_lt hv, runBlock_nil, Fin.zero_eta,
Fin.mk_one, Fin.reduceFinMk, Nat.add_left_cancel_iff]
/-- Exact result and scratch-register contents of inversion. -/
theorem fieldInvCode_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(E : RAMEnv) (s : RAMState) (x : F) (hw : 1 ≤ w)
(hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι) (hx : s.regs r10 = enc b x) :
runBlock fieldInvCode E s =
{ s with pc := s.pc + 4, regs := Function.update (Function.update (Function.update s.regs r15 (detInvBase w)) r14 (detInvBase w + enc b x)) r10 (enc b x⁻¹) } := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have hbase : detInvBase w < 2 ^ E.W := by rw [hW]; exact detInvBase_lt hw
have hend : detEnd w < 2 ^ E.W := by rw [hW]; exact detEnd_lt hw
have haddr : detInvBase w + enc b x < 2 ^ E.W := by
have hxlt := enc_lt b x
have hp := Nat.two_pow_pos w
unfold detEnd detImgBase detPosBase at hend
omega
have h8 : (8 : ℕ) < 2 ^ E.W := by
have hbound : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (8 : ℕ) < 2 ^ 8) hbound
have hhdr : E.det 8 = detInvBase w := by
rw [hdet, detStd_hdr t N w b ι (by norm_num : (8 : ℕ) < 13), hdrTab_eight]
have htab : E.det (detInvBase w + enc b x) = enc b x⁻¹ := by
rw [hdet, detStd_inv t N b ι (enc_lt b x), invTab, dec_enc]
have hv : enc b x⁻¹ < 2 ^ E.W := lt_of_lt_of_le (enc_lt b _) hpow
apply ramState_eq_of
· simp [fieldInvCode, runBlock_cons, runBlock_nil, execInstr] <;> omega
· rfl
· intro d
fin_cases d <;>
simp [fieldInvCode, runBlock_cons, runBlock_nil, execInstr, hx, hhdr, htab,
Nat.mod_eq_of_lt h8, Nat.mod_eq_of_lt hbase, Nat.mod_eq_of_lt haddr,
Nat.mod_eq_of_lt hv]
/-- Exact result of one XOR instruction, interpreted as field addition. -/
theorem fieldAddCode_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (s : RAMState) (x y : F)
(hW : w ≤ E.W) (hx : s.regs r10 = enc b x) (hy : s.regs r11 = enc b y) :
runBlock fieldAddCode E s =
{ s with pc := s.pc + 1, regs := Function.update s.regs r10 (enc b (x + y)) } := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := Nat.pow_le_pow_right (by norm_num) hW
have hv : enc b (x + y) < 2 ^ E.W := lt_of_lt_of_le (enc_lt b _) hpow
have hresult : (enc b x ^^^ enc b y) % 2 ^ E.W = enc b (x + y) := by
rw [← enc_add_xor]
exact Nat.mod_eq_of_lt hv
change execInstr (.bxor r10 r10 r11) E s = _
simp only [execInstr, hx, hy, hresult]
theorem writeArray_frame (B : ℕ) (m f : ℕ → ℕ) (n a : ℕ)
(ha : a < B ∨ B + n ≤ a) : writeArray B m f n a = m a := by
induction n with
| zero => rfl
| succ n ih =>
rw [writeArray, Function.update_of_ne (by omega : a ≠ B + n)]
exact ih (by omega)
theorem writeArray_get (B : ℕ) (m f : ℕ → ℕ) (n i : ℕ) (hi : i < n) :
writeArray B m f n (B + i) = f i := by
induction n with
| zero => omega
| succ n ih =>
by_cases h : i = n
· subst i
simp [writeArray]
· rw [writeArray, Function.update_of_ne (by omega : B + i ≠ B + n)]
exact ih (by omega)
/-- One coefficient update, including all machine scratch registers. -/
theorem axpyBody_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(E : RAMEnv) (pc dst src L : ℕ) (a : F) (x y : ℕ → F)
(m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ)
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hj : j < L) (hL : L < 2 ^ E.W)
(hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hx : ∀ i < L, m (src + i) = enc b (x i))
(hy : ∀ i < L, m (dst + i) = enc b (y i)) :
runBlock axpyBody E { runBlock axpyCond.code E (axpyState b pc dst src L a x y m r j) with pc := pc + 2 } =
{ axpyState b pc dst src L a x y m r (j + 1) with pc := pc + 23 } := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have henc (z : F) : enc b z % 2 ^ E.W = enc b z :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (enc_lt b z) hpow)
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := by
apply Nat.mod_eq_of_lt
have hp : (2 : ℕ) ^ 1 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
omega
have hsrcj : (src + j) % 2 ^ E.W = src + j := Nat.mod_eq_of_lt (by omega)
have hdstj : (dst + j) % 2 ^ E.W = dst + j := Nat.mod_eq_of_lt (by omega)
have hj1 : (j + 1) % 2 ^ E.W = j + 1 := Nat.mod_eq_of_lt (by omega)
let f := fun i => enc b (a * x i + y i)
have hmSrc : writeArray dst m f j (src + j) = enc b (x j) := by
rw [writeArray_frame dst m f j (src + j) (by omega), hx j hj]
have hmDst : writeArray dst m f j (dst + j) = enc b (y j) := by
rw [writeArray_frame dst m f j (dst + j) (Or.inr (le_refl _)), hy j hj]
dsimp only [f] at hmSrc hmDst
let entry : RAMState := { runBlock axpyCond.code E (axpyState b pc dst src L a x y m r j) with pc := pc + 2 }
let sA := runBlock axpyPrefix E entry
have hA3 : sA.regs r3 = w := by
simp [sA, entry, axpyPrefix, axpyCond, Cond.code, axpyState,
runBlock_cons, runBlock_nil, execInstr]
have hA10 : sA.regs r10 = enc b a := by
simp [sA, entry, axpyPrefix, axpyCond, Cond.code, axpyState,
runBlock_cons, runBlock_nil, execInstr, henc]
have hA11 : sA.regs r11 = enc b (x j) := by
simp [sA, entry, axpyPrefix, axpyCond, Cond.code, axpyState,
runBlock_cons, runBlock_nil, execInstr, hsrcj, hmSrc, f, henc]
have hMul := fieldMulCode_spec b ι t N E sA a (x j) hw hW hdet hA3 hA10 hA11
let sB := runBlock axpyAfterMul E (runBlock fieldMulCode E sA)
have hB10 : sB.regs r10 = enc b (a * x j) := by
dsimp only [sB]
rw [hMul]
simp only [axpyAfterMul, Fin.isValue, runBlock_cons, execInstr, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, Function.update_self, runBlock_nil]
have hB11 : sB.regs r11 = enc b (y j) := by
dsimp only [sB]
rw [hMul]
simp [axpyAfterMul, sA, entry, axpyPrefix, axpyCond, Cond.code, axpyState,
runBlock_cons, runBlock_nil, execInstr, hdstj, hmDst, f, henc]
have hAdd := fieldAddCode_spec b E sB (a * x j) (y j) (by omega : w ≤ E.W) hB10 hB11
have hfinish : runBlock axpyBody E entry =
runBlock axpyTail E { sB with pc := sB.pc + 1, regs := Function.update sB.regs r10 (enc b (a * x j + y j)) } := by
calc
runBlock axpyBody E entry = runBlock axpyTail E (runBlock fieldAddCode E sB) := by
simp only [axpyBody, runBlock_append] <;> rfl
_ = _ := by rw [hAdd]
change runBlock axpyBody E entry = _
rw [hfinish]
dsimp only [sB]
simp only [hMul]
apply ramState_eq_of
· simp [axpyTail, axpyAfterMul, sA, entry, axpyPrefix, axpyCond, Cond.code,
axpyState, runBlock_cons, runBlock_nil, execInstr] <;> omega
· simp [axpyTail, axpyAfterMul, sA, entry, axpyPrefix, axpyCond, Cond.code,
axpyState, runBlock_cons, runBlock_nil, execInstr, hdstj, writeArray]
· intro d
simp only [axpyTail, axpyAfterMul, sA, entry, axpyPrefix, axpyCond, Cond.code,
axpyState, runBlock_cons, runBlock_nil, execInstr, hj1, Function.update_idem]
fin_cases d <;>
simp [axpyTail, axpyAfterMul, sA, entry, axpyPrefix, axpyCond, Cond.code,
axpyState, runBlock_cons, runBlock_nil, execInstr, hj1]
theorem axpyCond_eval {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 : ℕ) :
axpyCond.eval (axpyState b pc dst src L a x y m r j) ↔ j < L := by
simp [axpyCond, Cond.eval, axpyState]
theorem axpyBodyIter {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (pc dst src L : ℕ) (a : F) (x y : ℕ → F)
(m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ)
(hAt : At P pc (Stmt.compile axpyStmt pc))
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hj : j < L) (hL : L < 2 ^ E.W)
(hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hx : ∀ i < L, m (src + i) = enc b (x i))
(hy : ∀ i < L, m (dst + i) = enc b (y i)) :
Sem P E (pc + axpyCond.code.length + 1) pc
{ runBlock axpyCond.code E (axpyState b pc dst src L a x y m r j) with pc := pc + axpyCond.code.length + 1 }
(fun k s' => k = 22 ∧ s' = axpyState b pc dst src L a x y m r (j + 1)) := by
obtain ⟨_, _, hbody, hjmp⟩ := at_loop hAt
have hbodyAt : At P (pc + 2) axpyBody := hbody
have hjmpAt : P[pc + 23]? = some (iJmp pc) := hjmp
have hrun : Sem P E (pc + 2) (pc + 23)
{ runBlock axpyCond.code E (axpyState b pc dst src L a x y m r j) with pc := pc + 2 }
(fun k s' => k = 21 ∧ s' = { axpyState b pc dst src L a x y m r (j + 1) with pc := pc + 23 }) := by
refine Sem.mono (Sem.block P E (pc + 2) axpyBody _ hbodyAt
(by simp [axpyBody, axpyPrefix, axpyAfterMul, fieldMulCode, fieldAddCode, axpyTail]) rfl) ?_
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨hk, ?_⟩
rw [hs]
exact axpyBody_spec b ι t N E pc dst src L a x y m r j hw hW hdet hj hL hdst hsrc hdisj hx hy
refine Sem.jmp_append (hAt := hjmpAt) (Sem.mono hrun ?_)
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨by omega, ?_⟩
rw [hs]
rfl
theorem axpyCond_exit {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (pc dst src L : ℕ)
(a : F) (x y : ℕ → F) (m : ℕ → ℕ) (r : Fin 16 → ℕ) :
({ runBlock axpyCond.code E (axpyState b pc dst src L a x y m r L) with pc := pc + 24 } : RAMState) =
{ axpyState b pc dst src L a x y m r L with pc := pc + 24 } := by
apply ramState_eq_of
· rfl
· rfl
· intro d
fin_cases d <;> simp [axpyCond, Cond.code, runBlock_cons, runBlock_nil, execInstr, axpyState]
/-- The coefficient loop `dst[i] += a * src[i]`, with an explicit linear
step bound, valid inside any surrounding compiled program. -/
theorem axpyArray_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (pc dst src L : ℕ) (a : F) (x y : ℕ → F)
(m : ℕ → ℕ) (r : Fin 16 → ℕ)
(hAt : At P pc (Stmt.compile axpyStmt pc))
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hL : L < 2 ^ E.W) (hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hx : ∀ i < L, m (src + i) = enc b (x i))
(hy : ∀ i < L, m (dst + i) = enc b (y i)) :
Sem P E pc (pc + 24) (axpyState b pc dst src L a x y m r 0)
(fun k s' => k ≤ 24 * L + 2 ∧ s' = { axpyState b pc dst src L a x y m r L with pc := pc + 24 }) := by
have hW1 : 1 < 2 ^ E.W := by
have hp : (2 : ℕ) ^ 1 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
omega
have h := Sem.loop P E pc axpyCond (.code axpyBody) hAt hW1 L
(fun j => axpyState b pc dst src L a x y m r j) (fun _ => 22)
(fun _ => rfl)
(fun j hj => (axpyCond_eval b pc dst src L a x y m r j).mpr hj)
(fun hf => (Nat.lt_irrefl L) ((axpyCond_eval b pc dst src L a x y m r L).mp hf))
(fun j hj => axpyBodyIter b ι t N P E pc dst src L a x y m r j hAt
hw hW hdet hj hL hdst hsrc hdisj hx hy)
refine Sem.mono h ?_
intro k s' hQ
obtain ⟨hcost, hs⟩ := hQ
refine ⟨?_, ?_⟩
· have hsum : (∑ j ∈ Finset.range L, (axpyCond.code.length + 1 + 22)) = 24 * L := by
change (∑ j ∈ Finset.range L, (24 : ℕ)) = 24 * L
exact sum_range_const_mul L 24
rw [hsum] at hcost
change k ≤ 2 + 24 * L at hcost
omega
· rw [hs]
exact axpyCond_exit b E pc dst src L a x y m r
/-- Even a nonsplitting input yields only distinct genuine roots, and at
most as many outputs as its degree. -/
theorem rootSearch_sound {F : Type} [Field F] [DecidableEq F]
(ps : List F[X]) (f : F[X]) (hf : f ≠ 0) :
(rootSearch ps f).Nodup ∧
(∀ u ∈ rootSearch ps f, f.eval u = 0) ∧
(rootSearch ps f).length ≤ f.natDegree := by
induction ps generalizing f with
| nil =>
by_cases h : f.natDegree = 1
· rw [rootSearch, if_pos h]
refine ⟨by simp, ?_, ?_⟩
· intro u hu
have hu' : u = linearRoot f := List.mem_singleton.mp hu
exact (linearRoot_eval_iff hf h u).mpr hu'
· simp [h]
· rw [rootSearch, if_neg h]
exact ⟨by simp, by simp, by simp⟩
| cons p ps ih =>
by_cases h : f.natDegree = 0
· rw [rootSearch, if_pos h]
exact ⟨by simp, by simp, by simp⟩
· let g0 := EuclideanDomain.gcd f p
let g1 := EuclideanDomain.gcd f (p - 1)
obtain ⟨hnd0, hroot0, hlen0⟩ := ih g0 (gcd_ne_zero_left hf p)
obtain ⟨hnd1, hroot1, hlen1⟩ := ih g1 (gcd_ne_zero_left hf (p - 1))
have hdisj : List.Disjoint (rootSearch ps g0) (rootSearch ps g1) := by
apply List.disjoint_left.mpr
intro u hu0 hu1
have hp0 := ((gcd_eval_iff f p u).mp (hroot0 u hu0)).2
have hp1 := ((gcd_eval_iff f (p - 1) u).mp (hroot1 u hu1)).2
rw [Polynomial.eval_sub, Polynomial.eval_one, sub_eq_zero] at hp1
exact zero_ne_one (hp0.symm.trans hp1)
rw [rootSearch, if_neg h]
refine ⟨List.nodup_append'.mpr ⟨hnd0, hnd1, hdisj⟩, ?_, ?_⟩
· intro u hu
rcases List.mem_append.mp hu with hu | hu
· exact ((gcd_eval_iff f p u).mp (hroot0 u hu)).1
· exact ((gcd_eval_iff f (p - 1) u).mp (hroot1 u hu)).1
· have hbudget := split_degree_budget f p hf
change g0.natDegree + g1.natDegree ≤ f.natDegree at hbudget
change (rootSearch ps g0 ++ rootSearch ps g1).length ≤ f.natDegree
rw [List.length_append]
omega
/-- Unconditional guarantees for the implemented modular root search. -/
theorem rootsByBasis_sound {F : Type} [Field F] [DecidableEq F]
[Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (f : F[X]) (hf : f ≠ 0) :
(rootsByBasis b f).Nodup ∧
(∀ u ∈ rootsByBasis b f, f.eval u = 0) ∧
(rootsByBasis b f).length ≤ f.natDegree := by
rw [rootsByBasis, traceRootSearch_eq]
exact rootSearch_sound _ f hf
theorem degreeScan_le {F : Type} [Field F] [DecidableEq F] (p : F[X]) (n : ℕ) :
degreeScan p n ≤ n := by
induction n with
| zero => simp [degreeScan]
| succ n ih =>
rw [degreeScan]
split <;> omega
@[simp] theorem degreeScan_zero {F : Type} [Field F] [DecidableEq F] (n : ℕ) :
degreeScan (0 : F[X]) n = 0 := by
induction n with
| zero => rfl
| succ n ih => simp [degreeScan, ih]
theorem degreeScan_eq {F : Type} [Field F] [DecidableEq F] (p : F[X]) (hp : p ≠ 0)
(n : ℕ) (hn : p.natDegree < n) : degreeScan p n = p.natDegree + 1 := by
induction n with
| zero => omega
| succ n ih =>
by_cases h : p.natDegree = n
· have hcoeff : p.coeff n ≠ 0 := by
simpa only [Polynomial.leadingCoeff, h] using (Polynomial.leadingCoeff_ne_zero.mpr hp)
rw [degreeScan, if_neg hcoeff, h]
· have hlt : p.natDegree < n := by omega
rw [degreeScan, if_pos (Polynomial.coeff_eq_zero_of_natDegree_lt hlt), ih hlt]
theorem enc_eq_zero_iff {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (z : F) : enc b z = 0 ↔ z = 0 := by
constructor
· intro h
apply enc_injective b
simpa only [enc_zero] using h
· intro h
simp [h]
theorem scanBody_spec {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (pc B L : ℕ)
(p : F[X]) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ)
(hj : j < L) (hW : 1 < 2 ^ E.W) (hwe : w ≤ E.W)
(hL : L < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W) (hp : PolynomialStored b m B L p) :
runBlock scanBody E { runBlock scanCond.code E (scanState b pc B L p m r j) with pc := pc + 2 } =
{ scanState b pc B L p m r (j + 1) with pc := pc + 16 } := by
have haddr : (B + j) % 2 ^ E.W = B + j := Nat.mod_eq_of_lt (by omega)
have hnext : (j + 1) % 2 ^ E.W = j + 1 := Nat.mod_eq_of_lt (by omega)
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt hW
have hacc : degreeScan p j % 2 ^ E.W = degreeScan p j := by
apply Nat.mod_eq_of_lt
have h := degreeScan_le p j
omega
have hval : enc b (p.coeff j) % 2 ^ E.W = enc b (p.coeff j) :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (enc_lt b _) (Nat.pow_le_pow_right (by norm_num) hwe))
have hsub0 : (1 + 2 ^ E.W - 0) % 2 ^ E.W = 1 := by
simp [Nat.add_mod, h1]
have hsub1 : (1 + 2 ^ E.W - 1) % 2 ^ E.W = 0 := by simp
have hm := hp j hj
by_cases hz : p.coeff j = 0
· apply ramState_eq_of
· simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr, ↓reduceIte,
one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne,
Function.update_self, Nat.mul_mod_mod, mul_ite, mul_one, mul_zero, Function.update_idem,
Nat.add_mod_mod, Nat.mod_add_mod, Nat.zero_mod, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr,
↓reduceIte, one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, haddr, Function.update_self, hm, hz, enc_zero, Nat.zero_mod,
lt_self_iff_false, hnext, mul_zero, Function.update_idem, tsub_zero, Nat.add_mod_right, h1,
mul_one, hacc, add_zero, degreeScan]
fin_cases d <;>
simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr,
↓reduceIte, one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, haddr, Function.update_self, hm, hz, enc_zero, Nat.zero_mod,
lt_self_iff_false, hnext, mul_zero, Function.update_idem, tsub_zero, Nat.add_mod_right, h1,
mul_one, hacc, add_zero, Fin.zero_eta, degreeScan, Nat.add_left_cancel_iff, Fin.mk_one,
Fin.reduceFinMk]
· have hpos : 0 < enc b (p.coeff j) := Nat.pos_of_ne_zero (fun h => hz ((enc_eq_zero_iff b _).mp h))
apply ramState_eq_of
· simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr, ↓reduceIte,
one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne,
Function.update_self, Nat.mul_mod_mod, mul_ite, mul_one, mul_zero, Function.update_idem,
Nat.add_mod_mod, Nat.mod_add_mod, Nat.zero_mod, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr,
↓reduceIte, one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, haddr, Function.update_self, hm, hval, hpos, h1, hnext, mul_one,
Function.update_idem, add_tsub_cancel_left, Nat.mod_self, mul_zero, Nat.zero_mod, zero_add,
degreeScan, hz]
fin_cases d <;>
simp only [scanBody, Fin.isValue, Cond.code, scanCond, scanState, runBlock_cons, execInstr,
↓reduceIte, one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, haddr, Function.update_self, hm, hval, hpos, h1, hnext, mul_one,
Function.update_idem, add_tsub_cancel_left, Nat.mod_self, mul_zero, Nat.zero_mod, zero_add,
Fin.zero_eta, degreeScan, hz, Nat.add_left_cancel_iff, Fin.mk_one, Fin.reduceFinMk]
theorem scanCond_eval {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 : ℕ) :
scanCond.eval (scanState b pc B L p m r j) ↔ j < L := by
simp [scanCond, Cond.eval, scanState]
theorem scanBodyIter {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (P : Program) (E : RAMEnv) (pc B L : ℕ)
(p : F[X]) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ)
(hAt : At P pc (Stmt.compile scanStmt pc)) (hj : j < L)
(hW : 1 < 2 ^ E.W) (hwe : w ≤ E.W) (hL : L < 2 ^ E.W)
(hB : B + L ≤ 2 ^ E.W) (hp : PolynomialStored b m B L p) :
Sem P E (pc + scanCond.code.length + 1) pc
{ runBlock scanCond.code E (scanState b pc B L p m r j) with pc := pc + scanCond.code.length + 1 }
(fun k s' => k = 15 ∧ s' = scanState b pc B L p m r (j + 1)) := by
obtain ⟨_, _, hbody, hjmp⟩ := at_loop hAt
have hbodyAt : At P (pc + 2) scanBody := hbody
have hjmpAt : P[pc + 16]? = some (iJmp pc) := hjmp
have hrun : Sem P E (pc + 2) (pc + 16)
{ runBlock scanCond.code E (scanState b pc B L p m r j) with pc := pc + 2 }
(fun k s' => k = 14 ∧ s' = { scanState b pc B L p m r (j + 1) with pc := pc + 16 }) := by
refine Sem.mono (Sem.block P E (pc + 2) scanBody _ hbodyAt
(by simp [scanBody]) rfl) ?_
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨hk, ?_⟩
rw [hs]
exact scanBody_spec b E pc B L p m r j hj hW hwe hL hB hp
refine Sem.jmp_append (hAt := hjmpAt) (Sem.mono hrun ?_)
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨by omega, ?_⟩
rw [hs]
rfl
theorem scanCond_exit {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (pc B L : ℕ) (p : F[X])
(m : ℕ → ℕ) (r : Fin 16 → ℕ) :
({ runBlock scanCond.code E (scanState b pc B L p m r L) with pc := pc + 17 } : RAMState) =
{ scanState b pc B L p m r L with pc := pc + 17 } := by
apply ramState_eq_of
· rfl
· rfl
· intro d
fin_cases d <;> simp [scanCond, Cond.code, runBlock_cons, runBlock_nil, execInstr, scanState]
theorem scanArray_spec {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (P : Program) (E : RAMEnv) (pc B L : ℕ)
(p : F[X]) (m : ℕ → ℕ) (r : Fin 16 → ℕ)
(hAt : At P pc (Stmt.compile scanStmt pc))
(hW : 1 < 2 ^ E.W) (hwe : w ≤ E.W) (hL : L < 2 ^ E.W)
(hB : B + L ≤ 2 ^ E.W) (hp : PolynomialStored b m B L p) :
Sem P E pc (pc + 17) (scanState b pc B L p m r 0)
(fun k s' => k ≤ 17 * L + 2 ∧ s' = { scanState b pc B L p m r L with pc := pc + 17 }) := by
have h := Sem.loop P E pc scanCond (.code scanBody) hAt hW L
(fun j => scanState b pc B L p m r j) (fun _ => 15)
(fun _ => rfl)
(fun j hj => (scanCond_eval b pc B L p m r j).mpr hj)
(fun hf => (Nat.lt_irrefl L) ((scanCond_eval b pc B L p m r L).mp hf))
(fun j hj => scanBodyIter b P E pc B L p m r j hAt hj hW hwe hL hB hp)
refine Sem.mono h ?_
intro k s' hQ
obtain ⟨hcost, hs⟩ := hQ
refine ⟨?_, ?_⟩
· have hsum : (∑ j ∈ Finset.range L, (scanCond.code.length + 1 + 15)) = 17 * L := by
change (∑ j ∈ Finset.range L, (17 : ℕ)) = 17 * L
exact sum_range_const_mul L 17
rw [hsum] at hcost
change k ≤ 2 + 17 * L at hcost
omega
· rw [hs]
exact scanCond_exit b E pc B L p m r
theorem leadingCancel_degree {F : Type} [Field F] (D R : F[X]) (n : ℕ)
(hD : 0 < D.natDegree) (hR : R.natDegree < D.natDegree + (n + 1)) :
(R - leadingCancel D R n * D).natDegree < D.natDegree + n := by
have hDne : D ≠ 0 := by intro hz; simp [hz] at hD
have hT : (leadingCancel D R n).natDegree ≤ n :=
Polynomial.natDegree_C_mul_X_pow_le _ _
have hTD : (leadingCancel D R n * D).natDegree ≤ D.natDegree + n := by
have hm := Polynomial.natDegree_mul_le (p := leadingCancel D R n) (q := D)
omega
have hle : (R - leadingCancel D R n * D).natDegree ≤ D.natDegree + n := by
have hs := Polynomial.natDegree_sub_le R (leadingCancel D R n * D)
omega
have hc : (leadingCancel D R n * D).coeff (D.natDegree + n) = R.coeff (D.natDegree + n) := by
rw [leadingCancel, mul_assoc, Polynomial.coeff_C_mul, Polynomial.coeff_X_pow_mul]
change (R.coeff (D.natDegree + n) / D.leadingCoeff) * D.leadingCoeff = _
exact div_mul_cancel₀ _ (Polynomial.leadingCoeff_ne_zero.mpr hDne)
have hz : (R - leadingCancel D R n * D).coeff (D.natDegree + n) = 0 := by
rw [Polynomial.coeff_sub, hc, sub_self]
rcases lt_or_eq_of_le hle with h | h
· exact h
· have hzero : R - leadingCancel D R n * D = 0 := by
apply Polynomial.leadingCoeff_eq_zero.mp
change (R - leadingCancel D R n * D).coeff (R - leadingCancel D R n * D).natDegree = 0
rw [h]
exact hz
rw [hzero, Polynomial.natDegree_zero] at h
omega
theorem longReduceRows_degree {F : Type} [Field F] (D C : F[X]) (n : ℕ)
(R U : F[X]) (hD : 0 < D.natDegree) (hR : R.natDegree < D.natDegree + n) :
(longReduceRows D C n R U).1.natDegree < D.natDegree := by
induction n generalizing R U with
| zero => simpa only [longReduceRows, Nat.add_zero] using hR
| succ n ih =>
exact ih _ _ (leadingCancel_degree D R n hD hR)
theorem longReduceRows_relation {F : Type} [Field F] (D C : F[X]) (n : ℕ) (R U : F[X]) :
∃ q : F[X], R = D * q + (longReduceRows D C n R U).1 ∧
U = C * q + (longReduceRows D C n R U).2 := by
induction n generalizing R U with
| zero => exact ⟨0, by simp [longReduceRows], by simp [longReduceRows]⟩
| succ n ih =>
let T := leadingCancel D R n
obtain ⟨q, hR, hU⟩ := ih (R - T * D) (U - T * C)
refine ⟨T + q, ?_, ?_⟩
· change R = D * (T + q) + (longReduceRows D C n (R - T * D) (U - T * C)).1
linear_combination hR
· change U = C * (T + q) + (longReduceRows D C n (R - T * D) (U - T * C)).2
linear_combination hU
/-- The coefficient loop computes exactly the quotient/remainder update
used by the already-verified key-equation solver. -/
theorem longReduceRows_eq {F : Type} [Field F] (D C : F[X]) (n : ℕ)
(R U : F[X]) (hD : 0 < D.natDegree) (hR : R.natDegree < D.natDegree + n) :
longReduceRows D C n R U = (R % D, U - (R / D) * C) := by
have hDne : D ≠ 0 := by intro hz; simp [hz] at hD
have hsmall := longReduceRows_degree D C n R U hD hR
obtain ⟨q, hrelR, hrelU⟩ := longReduceRows_relation D C n R U
have hdiv : D ∣ R - (longReduceRows D C n R U).1 := by
refine ⟨q, ?_⟩
linear_combination hrelR
have hmod := Polynomial.mod_eq_of_dvd_sub hdiv
have hself : (longReduceRows D C n R U).1 % D = (longReduceRows D C n R U).1 :=
(Polynomial.mod_eq_self_iff hDne).mpr (Polynomial.degree_lt_degree hsmall)
have hrem : R % D = (longReduceRows D C n R U).1 := hmod.trans hself
have hq : q = R / D := by
apply mul_left_cancel₀ hDne
have he := EuclideanDomain.div_add_mod R D
rw [hrem] at he
linear_combination -hrelR - he
apply Prod.ext
· exact hrem.symm
· rw [hq] at hrelU
linear_combination -hrelU
theorem shifted_coeff_inside {F : Type} [Field F] (q : F[X]) (a : F) (k i : ℕ) :
(C a * X ^ k * q).coeff (k + i) = a * q.coeff i := by
rw [mul_assoc, Polynomial.coeff_C_mul, show k + i = i + k by omega,
Polynomial.coeff_X_pow_mul]
theorem shifted_coeff_outside {F : Type} [Field F] (q : F[X]) (a : F) (k L j : ℕ)
(hq : q.natDegree < L) (hj : j < k ∨ k + L ≤ j) :
(C a * X ^ k * q).coeff j = 0 := by
rw [mul_assoc, Polynomial.coeff_C_mul, Polynomial.coeff_X_pow_mul']
split_ifs with hkj
· have hdeg : q.natDegree < j - k := by omega
rw [Polynomial.coeff_eq_zero_of_natDegree_lt hdeg, mul_zero]
· exact mul_zero a
theorem copyBody_spec (E : RAMEnv) (pc dst src L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ)
(j : ℕ) (hj : j < L) (hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W)
(hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hword : ∀ i < L, m (src + i) < 2 ^ E.W) :
runBlock copyBody E { runBlock copyCond.code E (copyState pc dst src L m r j) with pc := pc + 2 } =
{ copyState pc dst src L m r (j + 1) with pc := pc + 11 } := by
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt hW
have hsj : (src + j) % 2 ^ E.W = src + j := Nat.mod_eq_of_lt (by omega)
have hdj : (dst + j) % 2 ^ E.W = dst + j := Nat.mod_eq_of_lt (by omega)
have hj1 : (j + 1) % 2 ^ E.W = j + 1 := Nat.mod_eq_of_lt (by omega)
have hm : writeArray dst m (fun i => m (src + i)) j (src + j) = m (src + j) :=
writeArray_frame dst m _ j _ (by omega)
have hv : m (src + j) % 2 ^ E.W = m (src + j) := Nat.mod_eq_of_lt (hword j hj)
apply ramState_eq_of
· simp only [copyBody, Fin.isValue, Cond.code, copyCond, copyState, runBlock_cons, execInstr, ↓reduceIte,
one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne,
Function.update_self, Nat.zero_mod, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· simp only [copyBody, Fin.isValue, Cond.code, copyCond, copyState, runBlock_cons, execInstr, ↓reduceIte,
one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne, hsj,
Function.update_self, hm, hv, hdj, Nat.zero_mod, writeArray]
· intro d
fin_cases d <;>
simp only [copyBody, Fin.isValue, Cond.code, copyCond, copyState, runBlock_cons, execInstr, ↓reduceIte,
one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true, Function.update_of_ne,
Function.update_self, hj1, Nat.zero_mod, Fin.zero_eta, Nat.add_left_cancel_iff, Fin.mk_one,
Fin.reduceFinMk]
theorem copyCond_eval (pc dst src L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) :
copyCond.eval (copyState pc dst src L m r j) ↔ j < L := by
simp [copyCond, Cond.eval, copyState]
theorem copyBodyIter (P : Program) (E : RAMEnv) (pc dst src L : ℕ)
(m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) (hj : j < L)
(hAt : At P pc (Stmt.compile copyStmt pc))
(hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W)
(hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hword : ∀ i < L, m (src + i) < 2 ^ E.W) :
Sem P E (pc + copyCond.code.length + 1) pc
{ runBlock copyCond.code E (copyState pc dst src L m r j) with pc := pc + copyCond.code.length + 1 }
(fun k s' => k = 10 ∧ s' = copyState pc dst src L m r (j + 1)) := by
obtain ⟨_, _, hbody, hjmp⟩ := at_loop hAt
have hbodyAt : At P (pc + 2) copyBody := hbody
have hjmpAt : P[pc + 11]? = some (iJmp pc) := hjmp
have hrun : Sem P E (pc + 2) (pc + 11)
{ runBlock copyCond.code E (copyState pc dst src L m r j) with pc := pc + 2 }
(fun k s' => k = 9 ∧ s' = { copyState pc dst src L m r (j + 1) with pc := pc + 11 }) := by
refine Sem.mono (Sem.block P E (pc + 2) copyBody _ hbodyAt (by simp [copyBody]) rfl) ?_
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨hk, ?_⟩
rw [hs]
exact copyBody_spec E pc dst src L m r j hj hW hL hdst hsrc hdisj hword
refine Sem.jmp_append (hAt := hjmpAt) (Sem.mono hrun ?_)
intro k s' h
obtain ⟨hk, hs⟩ := h
refine ⟨by omega, ?_⟩
rw [hs]
rfl
theorem copyCond_exit (E : RAMEnv) (pc dst src L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) :
({ runBlock copyCond.code E (copyState pc dst src L m r L) with pc := pc + 12 } : RAMState) =
{ copyState pc dst src L m r L with pc := pc + 12 } := by
apply ramState_eq_of
· rfl
· rfl
· intro d
fin_cases d <;> simp [copyCond, Cond.code, copyState, runBlock_cons, runBlock_nil, execInstr]
/-- Copy a disjoint word array, preserving every address outside the target. -/
theorem copyArray_spec (P : Program) (E : RAMEnv) (pc dst src L : ℕ)
(m : ℕ → ℕ) (r : Fin 16 → ℕ) (hAt : At P pc (Stmt.compile copyStmt pc))
(hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W)
(hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hword : ∀ i < L, m (src + i) < 2 ^ E.W) :
Sem P E pc (pc + 12) (copyState pc dst src L m r 0)
(fun k s' => k ≤ 12 * L + 2 ∧ s' = { copyState pc dst src L m r L with pc := pc + 12 }) := by
have h := Sem.loop P E pc copyCond (.code copyBody) hAt hW L
(fun j => copyState pc dst src L m r j) (fun _ => 10)
(fun _ => rfl)
(fun j hj => (copyCond_eval pc dst src L m r j).mpr hj)
(fun hf => (Nat.lt_irrefl L) ((copyCond_eval pc dst src L m r L).mp hf))
(fun j hj => copyBodyIter P E pc dst src L m r j hj hAt hW hL hdst hsrc hdisj hword)
refine Sem.mono h ?_
intro k s' hQ
obtain ⟨hcost, hs⟩ := hQ
refine ⟨?_, ?_⟩
· have hsum : (∑ j ∈ Finset.range L, (copyCond.code.length + 1 + 10)) = 12 * L := by
change (∑ j ∈ Finset.range L, (12 : ℕ)) = 12 * L
exact sum_range_const_mul L 12
rw [hsum] at hcost
change k ≤ 2 + 12 * L at hcost
omega
· rw [hs]
exact copyCond_exit E pc dst src L m r
/-- A counted-loop rule for mathematical invariants instead of explicit
families of full machine states. The body returns to the head and decreases
the counter in register 9. This is a derived rule for the existing `Sem`. -/
theorem Sem.loop_invariant (P : Program) (E : RAMEnv) (base : ℕ) (body : Stmt)
(hAt : At P base (Stmt.compile (.loop (.neqz r9) body) base))
(hW : 1 < 2 ^ E.W) (I : ℕ → RAMState → Prop) (B : ℕ)
(hframe : ∀ n s pc, I n s → I n { s with pc := pc })
(hcounter : ∀ n s, I n s → s.regs r9 = n)
(hbody : ∀ n s, I (n + 1) s → s.pc = base →
Sem P E (base + 1) base { s with pc := base + 1 }
(fun k s' => k ≤ B ∧ I n s')) :
∀ n s, I n s → s.pc = base →
Sem P E base (base + body.len + 2) s
(fun k s' => k ≤ (B + 1) * n + 1 ∧ I 0 s') := by
intro n
induction n with
| zero =>
intro s hI hpc
have hstop : ¬ Cond.eval (.neqz r9) s := by
change ¬ s.regs r9 ≠ 0
rw [hcounter 0 s hI]
simp
have he := Sem.loopExit P E base (.neqz r9) body s hAt hW hpc hstop
refine Sem.mono he ?_
intro k s' hQ
obtain ⟨hk, hs⟩ := hQ
refine ⟨?_, ?_⟩
· change k = 1 at hk
omega
· rw [hs]
exact hframe 0 s _ hI
| succ n ih =>
intro s hI hpc
have hgo : Cond.eval (.neqz r9) s := by
change s.regs r9 ≠ 0
rw [hcounter (n + 1) s hI]
omega
obtain ⟨hentry, k, s', hrun, hreturn, hcost, hI'⟩ := hbody n s hI hpc
have hbodyExact : Sem P E (base + 1) base { s with pc := base + 1 }
(fun c z => c = k ∧ z = s') :=
⟨hentry, k, s', hrun, hreturn, rfl, rfl⟩
have hstep := Sem.loopStep P E base (.neqz r9) body s s' k hAt hW hpc hgo hbodyExact
have hrest := ih s' hI' hreturn
have hseq := Sem.seq (Q₁ := fun c z => c = 1 + k ∧ z = s')
(Q₂ := fun c₁ c₂ z => c₁ = 1 + k ∧ c₂ ≤ (B + 1) * n + 1 ∧ I 0 z) hstep
(fun c₁ z hQ => by
obtain ⟨hc, hz⟩ := hQ
subst z
exact Sem.mono hrest (fun _ _ h => ⟨hc, h⟩))
refine Sem.mono hseq ?_
intro c z hQ
obtain ⟨c₁, c₂, hc, hc₁, hc₂, hz⟩ := hQ
refine ⟨?_, hz⟩
rw [Nat.mul_succ]
omega
theorem zeroRegs_spec (E : RAMEnv) (s : RAMState) :
runBlock zeroRegsCode E s = boundaryState (s.pc + 16) s.mem := by
apply ramState_eq_of
· simp only [zeroRegsCode, Fin.isValue, runBlock_cons, execInstr, Nat.zero_mod, runBlock_nil,
boundaryState, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
fin_cases d <;> simp only [zeroRegsCode, Fin.isValue, runBlock_cons, execInstr, Nat.zero_mod,
runBlock_nil, Fin.zero_eta, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, zero_ne_one, Function.update_self, boundaryState, Fin.mk_one,
Fin.reduceFinMk]
/-- Read the two components of a compiled sequence inside a surrounding program. -/
theorem At.seqStmt {P : Program} {base : ℕ} {a b : Stmt}
(h : At P base (Stmt.compile (.seq a b) base)) :
At P base (Stmt.compile a base) ∧
At P (base + a.len) (Stmt.compile b (base + a.len)) := by
simpa only [Stmt.compile, At.append, Stmt.length_compile] using h
theorem axpyArgs_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (pc dst src L : ℕ)
(a : F) (x y : ℕ → F) (m : ℕ → ℕ)
(hwidth : (68 : ℕ) < 2 ^ E.W) (hdst : dst < 2 ^ E.W) (hsrc : src < 2 ^ E.W)
(hL : L < 2 ^ E.W) (hw : w < 2 ^ E.W) (ha : enc b a < 2 ^ E.W)
(hm64 : m 64 = dst) (hm65 : m 65 = src) (hm66 : m 66 = L)
(hm67 : m 67 = w) (hm68 : m 68 = enc b a) :
runBlock axpyArgsCode E (boundaryState pc m) =
axpyState b (pc + 12) dst src L a x y m (fun _ => 0) 0 := by
have hmeta : ∀ k ≤ 68, k % 2 ^ E.W = k := by
intro k hk
exact Nat.mod_eq_of_lt (by omega)
apply ramState_eq_of
· simp only [axpyArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr, Function.update_self,
Nat.zero_mod, runBlock_nil, axpyState, ite_self, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
fin_cases d <;>
simp only [axpyArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr, Nat.reduceLeDiff, hmeta,
Function.update_self, hm64, Nat.mod_eq_of_lt hdst, hm65, Nat.mod_eq_of_lt hsrc, hm66,
Nat.mod_eq_of_lt hL, hm67, Nat.mod_eq_of_lt hw, Std.le_refl, hm68, Nat.mod_eq_of_lt ha,
Nat.one_le_ofNat, zero_le, runBlock_nil, Fin.zero_eta, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, zero_ne_one, axpyState, ite_self, ↓reduceIte, Fin.mk_one, one_ne_zero,
Fin.reduceFinMk]
/-- Calling convention for the row-operation procedure. Registers are zero
at both boundaries; the mathematical memory update is the entire effect. -/
theorem axpyProcedure_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (pc dst src L : ℕ) (a : F) (x y : ℕ → F) (m : ℕ → ℕ)
(hAt : At P pc (Stmt.compile axpyProcedure pc))
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hdstWord : dst < 2 ^ E.W) (hsrcWord : src < 2 ^ E.W)
(hL : L < 2 ^ E.W) (hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src)
(hx : ∀ i < L, m (src + i) = enc b (x i))
(hy : ∀ i < L, m (dst + i) = enc b (y i))
(hm64 : m 64 = dst) (hm65 : m 65 = src) (hm66 : m 66 = L)
(hm67 : m 67 = w) (hm68 : m 68 = enc b a) :
Sem P E pc (pc + 52) (boundaryState pc m)
(fun k s' => k ≤ 24 * L + 30 ∧
s' = boundaryState (pc + 52) (writeArray dst m (fun i => enc b (a * x i + y i)) L)) := by
obtain ⟨hArgsAt, hRestAt⟩ := At.seqStmt hAt
obtain ⟨hLoopAt, hZeroAt⟩ := At.seqStmt hRestAt
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have hwidth : (68 : ℕ) < 2 ^ E.W := by
have hb : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (68 : ℕ) < 2 ^ 8) hb
have hwWord : w < 2 ^ E.W := lt_of_lt_of_le (Nat.lt_two_pow_self (n := w)) hpow
have haWord : enc b a < 2 ^ E.W := lt_of_lt_of_le (enc_lt b a) hpow
have hArgs := Sem.block P E pc axpyArgsCode (boundaryState pc m) hArgsAt
(by simp [axpyArgsCode]) rfl
have hArgs' : Sem P E pc (pc + 12) (boundaryState pc m)
(fun k s' => k = 12 ∧ s' = axpyState b (pc + 12) dst src L a x y m (fun _ => 0) 0) := by
refine Sem.mono hArgs ?_
intro k s' hQ
obtain ⟨hk, hs⟩ := hQ
refine ⟨hk, ?_⟩
rw [hs]
exact axpyArgs_spec b E pc dst src L a x y m hwidth hdstWord hsrcWord hL hwWord haWord
hm64 hm65 hm66 hm67 hm68
have hLoop := axpyArray_spec b ι t N P E (pc + 12) dst src L a x y m (fun _ => 0) hLoopAt
hw hW hdet hL hdst hsrc hdisj hx hy
have hCombined := Sem.seq (Q₂ := fun k₁ k₂ s' => k₁ = 12 ∧ k₂ ≤ 24 * L + 2 ∧
s' = { axpyState b (pc + 12) dst src L a x y m (fun _ => 0) L with pc := pc + 36 })
hArgs' (fun k₁ s₁ hQ => by
obtain ⟨hk, hs⟩ := hQ
rw [hs]
exact Sem.mono hLoop (fun _ _ h => ⟨hk, h⟩))
have hFull := Sem.seq (Q₁ := fun k s' => k ≤ 24 * L + 14 ∧
s' = { axpyState b (pc + 12) dst src L a x y m (fun _ => 0) L with pc := pc + 36 })
(Q₂ := fun k₁ k₂ s' => k₁ ≤ 24 * L + 14 ∧ k₂ = 16 ∧
s' = boundaryState (pc + 52) (writeArray dst m (fun i => enc b (a * x i + y i)) L))
(Sem.mono hCombined (fun k s' hQ => by
obtain ⟨k₁, k₂, hk, h₁, h₂, hs⟩ := hQ
exact ⟨by omega, hs⟩))
(fun k₁ s₁ hQ => by
obtain ⟨hk, hs⟩ := hQ
have hz := Sem.block P E (pc + 36) zeroRegsCode s₁ hZeroAt
(by simp [zeroRegsCode]) (by rw [hs])
refine Sem.mono hz ?_
intro k₂ s₂ hQ₂
obtain ⟨hk₂, hs₂⟩ := hQ₂
refine ⟨hk, hk₂, ?_⟩
rw [hs₂, zeroRegs_spec, hs]
rfl)
refine Sem.mono hFull ?_
intro k s' hQ
obtain ⟨k₁, k₂, hk, h₁, h₂, hs⟩ := hQ
exact ⟨by omega, hs⟩
/-- Unconditional instruction semantics; bounds are discharged by callers. -/
theorem metaRead_spec (E : RAMEnv) (s : RAMState) (d : Fin 16) (addr : ℕ) (hd : d ≠ r15) :
runBlock (metaReadCode d addr) E s =
{ s with pc := s.pc + 3, regs := Function.update (Function.update s.regs d (s.mem (addr % 2 ^ E.W) % 2 ^ E.W)) r15 0 } := by
apply ramState_eq_of
· simp [metaReadCode, runBlock_cons, runBlock_nil, execInstr] <;> omega
· rfl
· intro k
by_cases hk : k = r15
· subst k
simp [metaReadCode, runBlock_cons, runBlock_nil, execInstr]
· by_cases hkd : k = d
· subst k
simp [metaReadCode, runBlock_cons, runBlock_nil, execInstr, hd]
· simp [metaReadCode, runBlock_cons, runBlock_nil, execInstr, hk, hkd]
theorem metaStore_spec (E : RAMEnv) (s : RAMState) (d : Fin 16) (addr : ℕ) (hd : d ≠ r15) :
runBlock (metaStoreCode d addr) E s =
{ s with pc := s.pc + 3, regs := Function.update s.regs r15 0, mem := Function.update s.mem (addr % 2 ^ E.W) (s.regs d) } := by
apply ramState_eq_of
· simp [metaStoreCode, runBlock_cons, runBlock_nil, execInstr] <;> omega
· simp [metaStoreCode, runBlock_cons, runBlock_nil, execInstr, hd]
· intro k
by_cases hk : k = r15
· subst k
simp [metaStoreCode, runBlock_cons, runBlock_nil, execInstr]
· simp [metaStoreCode, runBlock_cons, runBlock_nil, execInstr, hk]
/-- Bounded-cost sequential composition with a state invariant. -/
theorem Sem.seq_bound {P : Program} {E : RAMEnv} {a b c A B : ℕ} {s : RAMState}
{I J : RAMState → Prop}
(h₁ : Sem P E a b s (fun k s' => k ≤ A ∧ I s'))
(h₂ : ∀ s', s'.pc = b → I s' → Sem P E b c s' (fun k s'' => k ≤ B ∧ J s'')) :
Sem P E a c s (fun k s' => k ≤ A + B ∧ J s') := by
obtain ⟨hpc, k₁, s₁, hrun₁, hb, hcost₁, hI⟩ := h₁
obtain ⟨_, k₂, s₂, hrun₂, hc, hcost₂, hJ⟩ := h₂ s₁ hb hI
refine ⟨hpc, k₁ + k₂, s₂, ?_, hc, by omega, hJ⟩
rw [Nat.add_comm k₁ k₂, Function.iterate_add_apply, hrun₁, hrun₂]
/-- Compute the cancellation scalar and prepare the first row operation.
The inverse leading coefficient is cached once per polynomial division. -/
theorem longDivPrepare_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ) (E : RAMEnv)
(s : RAMState) (R D : F[X]) (Rbase Dbase d n L cap : ℕ)
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hAddr : Rbase + n + d < 2 ^ E.W) (hDbase : Dbase < 2 ^ E.W)
(hStep : n + 1 < 2 ^ E.W) (hL : L < 2 ^ E.W) (hcap : d + n < cap)
(hR : PolynomialStored b s.mem Rbase cap R)
(hm72 : s.mem 72 = Rbase) (hm74 : s.mem 74 = Dbase)
(hm71 : s.mem 71 = n + 1) (hm69 : s.mem 69 = d)
(hm70 : s.mem 70 = enc b D.leadingCoeff⁻¹)
(hm77 : s.mem 77 = w) (hm76 : s.mem 76 = L) :
runBlock longDivPrepareCode E s = boundaryState (s.pc + 64)
(rowArguments s.mem (Rbase + n) Dbase L w (enc b (R.coeff (d + n) * D.leadingCoeff⁻¹))) := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have hwidth : (77 : ℕ) < 2 ^ E.W := by
have hb : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (77 : ℕ) < 2 ^ 8) hb
have hmeta : ∀ k ≤ 77, k % 2 ^ E.W = k := by
intro k hk
exact Nat.mod_eq_of_lt (by omega)
have hRword : Rbase % 2 ^ E.W = Rbase := Nat.mod_eq_of_lt (by omega)
have hDword : Dbase % 2 ^ E.W = Dbase := Nat.mod_eq_of_lt hDbase
have hdword : d % 2 ^ E.W = d := Nat.mod_eq_of_lt (by omega)
have hnword : (n + 1) % 2 ^ E.W = n + 1 := Nat.mod_eq_of_lt hStep
have hDstword : (Rbase + n) % 2 ^ E.W = Rbase + n := Nat.mod_eq_of_lt (by omega)
have hAddrword : (Rbase + n + d) % 2 ^ E.W = Rbase + n + d := Nat.mod_eq_of_lt hAddr
have hWword : w % 2 ^ E.W = w :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (Nat.lt_two_pow_self (n := w)) hpow)
have hLword : L % 2 ^ E.W = L := Nat.mod_eq_of_lt hL
have hEnc (z : F) : enc b z % 2 ^ E.W = enc b z :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (enc_lt b z) hpow)
have hSub : (n + 1 + 2 ^ E.W - 1) % 2 ^ E.W = n := by
have heq : n + 1 + 2 ^ E.W - 1 = n + 2 ^ E.W := by omega
rw [heq]
simp [Nat.add_mod, Nat.mod_eq_of_lt (show n < 2 ^ E.W by omega)]
have hmR : s.mem (Rbase + n + d) = enc b (R.coeff (d + n)) := by
rw [show Rbase + n + d = Rbase + (d + n) by omega]
exact hR (d + n) hcap
let sA := runBlock longDivReadCode E s
have hA3 : sA.regs r3 = w := by
simp only [longDivReadCode, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.reduceLeDiff, hmeta, Std.le_refl, hm77, hWword, runBlock_cons,
execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self, Nat.add_mod_mod,
Nat.mod_add_mod, runBlock_nil, sA]
have hA10 : sA.regs r10 = enc b (R.coeff (d + n)) := by
simp only [longDivReadCode, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.reduceLeDiff, hmeta, hm72, hRword, hm74, hDword, hm71, hnword,
hm69, hdword, hm70, hEnc, Std.le_refl, hm77, hWword, runBlock_cons, execInstr, Nat.one_le_ofNat,
Function.update_of_ne, Function.update_self, Nat.succ_add_sub_one, Nat.add_mod_right, Nat.add_mod_mod,
hDstword, hAddrword, hmR, runBlock_nil, sA]
have hA11 : sA.regs r11 = enc b D.leadingCoeff⁻¹ := by
simp only [longDivReadCode, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.reduceLeDiff, hmeta, hm70, hEnc, Std.le_refl, runBlock_cons,
execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self, Nat.add_mod_mod,
Nat.mod_add_mod, runBlock_nil, sA]
have hA2 : sA.regs r2 = Rbase + n := by
simp only [longDivReadCode, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.reduceLeDiff, hmeta, hm72, hRword, hm71, hnword, Std.le_refl,
runBlock_cons, execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self,
Nat.succ_add_sub_one, Nat.add_mod_right, Nat.add_mod_mod, hDstword, runBlock_nil,
Nat.add_left_cancel_iff, sA]
have hA4 : sA.regs r4 = Dbase := by
simp only [longDivReadCode, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.reduceLeDiff, hmeta, hm74, hDword, Std.le_refl, runBlock_cons,
execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self, Nat.add_mod_mod,
Nat.mod_add_mod, runBlock_nil, sA]
have hmA : sA.mem = s.mem := rfl
have hMul := fieldMulCode_spec b ι t N E sA (R.coeff (d + n)) D.leadingCoeff⁻¹
hw hW hdet hA3 hA10 hA11
let sB := runBlock longDivWriteCode E (runBlock fieldMulCode E sA)
have hfinish : runBlock longDivPrepareCode E s = boundaryState (sB.pc + 16) sB.mem := by
calc
runBlock longDivPrepareCode E s = runBlock zeroRegsCode E sB := by
simp only [longDivPrepareCode, runBlock_append] <;> rfl
_ = _ := zeroRegs_spec E sB
have hpc : sB.pc + 16 = s.pc + 64 := by
have hp := runBlock_pc longDivPrepareCode E s (by
simp [longDivPrepareCode, longDivReadCode, longDivWriteCode, metaReadCode,
metaStoreCode, fieldMulCode, zeroRegsCode])
rw [hfinish] at hp
exact hp
have hmem : sB.mem = rowArguments s.mem (Rbase + n) Dbase L w
(enc b (R.coeff (d + n) * D.leadingCoeff⁻¹)) := by
dsimp only [sB]
rw [hMul]
simp only [longDivWriteCode, Fin.isValue, List.append_assoc, hmA, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaStore_spec, Nat.reduceLeDiff, hmeta, Function.update_self, Function.update_idem,
Function.update_of_ne, hA2, hA4, metaRead_spec, Nat.reduceEqDiff, hm76, hLword, hA3, rowArguments]
rw [hfinish, hpc, hmem]
theorem shiftedArguments_spec (E : RAMEnv) (s : RAMState) (dstSlot srcSlot dst src n : ℕ)
(hwidth : (71 : ℕ) < 2 ^ E.W) (hdstSlot : dstSlot < 2 ^ E.W)
(hsrcSlot : srcSlot < 2 ^ E.W) (hdst : dst + n < 2 ^ E.W)
(hsrc : src < 2 ^ E.W) (hn : n + 1 < 2 ^ E.W)
(hmDst : s.mem dstSlot = dst) (hmSrc : s.mem srcSlot = src)
(hmN : s.mem 71 = n + 1) :
runBlock (shiftedArgumentsCode dstSlot srcSlot) E s = boundaryState (s.pc + 34)
(Function.update (Function.update s.mem 64 (dst + n)) 65 src) := by
have hmeta : ∀ k ≤ 71, k % 2 ^ E.W = k := by
intro k hk
exact Nat.mod_eq_of_lt (by omega)
have hdst0 : dst % 2 ^ E.W = dst := Nat.mod_eq_of_lt (by omega)
have hdstn : (dst + n) % 2 ^ E.W = dst + n := Nat.mod_eq_of_lt hdst
have hsrc0 : src % 2 ^ E.W = src := Nat.mod_eq_of_lt hsrc
have hn0 : (n + 1) % 2 ^ E.W = n + 1 := Nat.mod_eq_of_lt hn
have hpred : (n + 1 + 2 ^ E.W - 1) % 2 ^ E.W = n := by
have heq : n + 1 + 2 ^ E.W - 1 = n + 2 ^ E.W := by omega
rw [heq]
simp [Nat.add_mod, Nat.mod_eq_of_lt (show n < 2 ^ E.W by omega)]
have hdstSlot0 : dstSlot % 2 ^ E.W = dstSlot := Nat.mod_eq_of_lt hdstSlot
have hsrcSlot0 : srcSlot % 2 ^ E.W = srcSlot := Nat.mod_eq_of_lt hsrcSlot
have hrun : runBlock (shiftedArgumentsCode dstSlot srcSlot) E s =
runBlock zeroRegsCode E (runBlock (metaStoreCode r4 65) E
(runBlock (metaStoreCode r2 64) E (runBlock
(metaReadCode r2 dstSlot ++ metaReadCode r4 srcSlot ++ metaReadCode r9 71 ++
[iImm r6 1, iSub r9 r9 r6, iAdd r2 r2 r9]) E s))) := by
simp only [shiftedArgumentsCode, runBlock_append] <;> rfl
rw [hrun, zeroRegs_spec]
have hlen : (shiftedArgumentsCode dstSlot srcSlot).length = 34 := rfl
apply ramState_eq_of
· have hp := runBlock_pc (shiftedArgumentsCode dstSlot srcSlot) E s (by
simp [shiftedArgumentsCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [hrun, zeroRegs_spec] at hp
simpa only [hlen, boundaryState] using hp
· simp [runBlock_append, metaRead_spec, metaStore_spec, runBlock_cons, runBlock_nil,
execInstr, hmeta, hdstSlot0, hsrcSlot0, hmDst, hmSrc, hmN,
hdst0, hdstn, hsrc0, hn0, hpred, boundaryState]
· intro _; rfl
theorem longDivTail_spec (E : RAMEnv) (s : RAMState) (n : ℕ)
(hwidth : (71 : ℕ) < 2 ^ E.W) (hn : n + 1 < 2 ^ E.W) (hm : s.mem 71 = n + 1) :
runBlock longDivTailCode E s = rankState (s.pc + 27) (Function.update s.mem 71 n) n := by
have hmeta : ∀ k ≤ 71, k % 2 ^ E.W = k := by
intro k hk
exact Nat.mod_eq_of_lt (by omega)
have hn0 : (n + 1) % 2 ^ E.W = n + 1 := Nat.mod_eq_of_lt hn
have hn1 : n % 2 ^ E.W = n := Nat.mod_eq_of_lt (by omega)
have hpred : (n + 1 + 2 ^ E.W - 1) % 2 ^ E.W = n := by
have heq : n + 1 + 2 ^ E.W - 1 = n + 2 ^ E.W := by omega
rw [heq]
simp [Nat.add_mod, hn1]
apply ramState_eq_of
· have hp := runBlock_pc longDivTailCode E s (by
simp [longDivTailCode, metaReadCode, metaStoreCode, zeroRegsCode])
exact hp
· simp only [longDivTailCode, Fin.isValue, List.append_assoc, List.cons_append, List.nil_append,
runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true, metaRead_spec, Std.le_refl, hmeta, hm, hn0,
runBlock_cons, execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self,
Nat.succ_add_sub_one, Nat.add_mod_right, hn1, metaStore_spec, zeroRegs_spec, boundaryState, rankState]
· intro d
fin_cases d <;> simp only [longDivTailCode, Fin.isValue, List.append_assoc, List.cons_append,
List.nil_append, runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true,
metaRead_spec, Std.le_refl, hmeta, hm, hn0, runBlock_cons, execInstr, Nat.one_le_ofNat,
Function.update_of_ne, Function.update_self, Nat.succ_add_sub_one, Nat.add_mod_right,
hn1, metaStore_spec, zeroRegs_spec, boundaryState, Fin.zero_eta, rankState, Fin.mk_one,
Fin.reduceFinMk]
theorem decoderWorkspace_fits {w t : ℕ} (hw : 1 ≤ w) (ht : t < 2 ^ w) :
decoderWorkspaceEnd t < 2 ^ (8 * w) := by
let q : ℕ := 2 ^ w
change t < q at ht
have hq : 2 ≤ q := by
have h := Nat.pow_le_pow_right (n := 2) (by norm_num) hw
exact h
have ht1 : t + 1 ≤ q := by omega
have hsq : (t + 1) * (t + 1) ≤ q * q := Nat.mul_le_mul ht1 ht1
have hq2 : 2 * q ≤ q * q := Nat.mul_le_mul_right q hq
have hq4 : 4 ≤ q * q := by
simpa using Nat.mul_le_mul hq hq
have hfirst : decoderWorkspaceEnd t ≤ 8 * q * q + 48 * q + 104 := by
unfold decoderWorkspaceEnd
nlinarith only [hsq, ht1]
have hsecond : 8 * q * q + 48 * q + 104 ≤ 58 * q * q := by
nlinarith only [hq2, hq4]
have hthird : 58 * q * q < 64 * q * q := by
have hp : 0 < q * q := Nat.mul_pos (by omega) (by omega)
nlinarith only [hp]
have hpow : 64 * q * q = 2 ^ (w + w + 6) := by
dsimp only [q]
rw [Nat.pow_add, Nat.pow_add]
norm_num <;> ring
have hupper : (2 : ℕ) ^ (w + w + 6) ≤ 2 ^ (8 * w) :=
Nat.pow_le_pow_right (by norm_num) (by omega)
have hlower : decoderWorkspaceEnd t < 64 * q * q :=
lt_of_le_of_lt hfirst (lt_of_le_of_lt hsecond hthird)
rw [hpow] at hlower
exact lt_of_lt_of_le hlower hupper
theorem rowArguments_frame (m : ℕ → ℕ) (dst src L w scalar addr : ℕ)
(ha : addr < 64 ∨ 69 ≤ addr) : rowArguments m dst src L w scalar addr = m addr := by
have h64 : addr ≠ 64 := by omega
have h65 : addr ≠ 65 := by omega
have h66 : addr ≠ 66 := by omega
have h67 : addr ≠ 67 := by omega
have h68 : addr ≠ 68 := by omega
simp [rowArguments, h64, h65, h66, h67, h68]
theorem PolynomialStored.rowArguments {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m : ℕ → ℕ} {B cap : ℕ} {p : F[X]}
(hp : PolynomialStored b m B cap p) (hB : 128 ≤ B) (dst src L dim scalar : ℕ) :
PolynomialStored b (rowArguments m dst src L dim scalar) B cap p := by
intro i hi
rw [rowArguments_frame _ _ _ _ _ _ _ (Or.inr (by omega))]
exact hp i hi
theorem PolynomialStored.meta_update {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m : ℕ → ℕ} {B cap : ℕ} {p : F[X]}
(hp : PolynomialStored b m B cap p) (hB : 128 ≤ B) (slot value : ℕ) (hslot : slot < 128) :
PolynomialStored b (Function.update m slot value) B cap p := by
intro i hi
rw [Function.update_of_ne (by omega : B + i ≠ slot)]
exact hp i hi
theorem PolynomialStored.write_disjoint {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m : ℕ → ℕ} {B cap : ℕ} {p : F[X]}
(hp : PolynomialStored b m B cap p) (dst L : ℕ) (f : ℕ → ℕ)
(hdisj : dst + L ≤ B ∨ B + cap ≤ dst) :
PolynomialStored b (writeArray dst m f L) B cap p := by
intro i hi
rw [writeArray_frame dst m f L (B + i) (by omega)]
exact hp i hi
theorem writeArray_meta (dst : ℕ) (m f : ℕ → ℕ) (L slot : ℕ)
(hdst : 128 ≤ dst) (hslot : slot < 128) : writeArray dst m f L slot = m slot :=
writeArray_frame dst m f L slot (Or.inl (by omega))
/-- Pure memory effect of the shifted coefficient loop. -/
theorem PolynomialStored.shift_write {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m : ℕ → ℕ} {B cap : ℕ} {p : F[X]}
(hp : PolynomialStored b m B cap p) (a : F) (q : F[X]) (k L : ℕ)
(hcap : k + L ≤ cap) (hq : q.natDegree < L) :
PolynomialStored b
(writeArray (B + k) m (fun i => enc b (a * q.coeff i + p.coeff (k + i))) L)
B cap (p + C a * X ^ k * q) := by
intro j hj
by_cases hout : j < k ∨ k + L ≤ j
· rw [writeArray_frame _ _ _ _ (B + j) (by omega), hp j hj]
rw [Polynomial.coeff_add, shifted_coeff_outside q a k L j hq hout, add_zero]
· have hkj : k ≤ j := by omega
have hi : j - k < L := by omega
have haddr : B + j = B + k + (j - k) := by omega
rw [haddr, writeArray_get _ _ _ L (j - k) hi]
congr 1
have hcoeff : (p + C a * X ^ k * q).coeff j =
p.coeff (k + (j - k)) + a * q.coeff (j - k) := by
conv_lhs => rw [show j = k + (j - k) by omega]
rw [Polynomial.coeff_add, shifted_coeff_inside]
rw [hcoeff]
ring
/-- The two destination arrays represent exactly the coupled long-division
step; both divisor arrays remain unchanged. -/
theorem rowIterationMemory_stored {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (RB UB DB CB n L cap : ℕ)
(R U D C : F[X]) (hl : RowsLayout RB UB DB CB cap) (hcap : n + L ≤ cap)
(hD : D.natDegree < L) (hC : C.natDegree < L)
(hRmem : PolynomialStored b m RB cap R) (hUmem : PolynomialStored b m UB cap U)
(hDmem : PolynomialStored b m DB cap D) (hCmem : PolynomialStored b m CB cap C) :
let m' := rowIterationMemory b m RB UB DB CB n L R U D C
PolynomialStored b m' RB cap (R - leadingCancel D R n * D) ∧
PolynomialStored b m' UB cap (U - leadingCancel D R n * C) ∧
PolynomialStored b m' DB cap D ∧ PolynomialStored b m' CB cap C := by
let a := R.coeff (D.natDegree + n) * D.leadingCoeff⁻¹
let m1 := rowArguments m (RB + n) DB L w (enc b a)
let fR := fun i => enc b (a * D.coeff i + R.coeff (n + i))
let m2 := writeArray (RB + n) m1 fR L
let m3 := Function.update (Function.update m2 64 (UB + n)) 65 CB
let fU := fun i => enc b (a * C.coeff i + U.coeff (n + i))
let m4 := writeArray (UB + n) m3 fU L
change PolynomialStored b (Function.update m4 71 n) RB cap (R - leadingCancel D R n * D) ∧
PolynomialStored b (Function.update m4 71 n) UB cap (U - leadingCancel D R n * C) ∧
PolynomialStored b (Function.update m4 71 n) DB cap D ∧ PolynomialStored b (Function.update m4 71 n) CB cap C
have hR1 := hRmem.rowArguments hl.Rlow (RB + n) DB L w (enc b a)
have hU1 := hUmem.rowArguments hl.Ulow (RB + n) DB L w (enc b a)
have hD1 := hDmem.rowArguments hl.Dlow (RB + n) DB L w (enc b a)
have hC1 := hCmem.rowArguments hl.Clow (RB + n) DB L w (enc b a)
have hR2 : PolynomialStored b m2 RB cap (R + Polynomial.C a * X ^ n * D) :=
hR1.shift_write a D n L hcap hD
have hU2 : PolynomialStored b m2 UB cap U :=
hU1.write_disjoint (RB + n) L fR (by have h := hl.RU; omega)
have hD2 : PolynomialStored b m2 DB cap D :=
hD1.write_disjoint (RB + n) L fR (by have h := hl.RD; omega)
have hC2 : PolynomialStored b m2 CB cap C :=
hC1.write_disjoint (RB + n) L fR (by have h := hl.RC; omega)
have hR3 := (hR2.meta_update hl.Rlow 64 (UB + n) (by norm_num)).meta_update hl.Rlow 65 CB (by norm_num)
have hU3 := (hU2.meta_update hl.Ulow 64 (UB + n) (by norm_num)).meta_update hl.Ulow 65 CB (by norm_num)
have hD3 := (hD2.meta_update hl.Dlow 64 (UB + n) (by norm_num)).meta_update hl.Dlow 65 CB (by norm_num)
have hC3 := (hC2.meta_update hl.Clow 64 (UB + n) (by norm_num)).meta_update hl.Clow 65 CB (by norm_num)
have hR4 : PolynomialStored b m4 RB cap (R + Polynomial.C a * X ^ n * D) :=
hR3.write_disjoint (UB + n) L fU (by have h := hl.RU; omega)
have hU4 : PolynomialStored b m4 UB cap (U + Polynomial.C a * X ^ n * C) :=
hU3.shift_write a C n L hcap hC
have hD4 : PolynomialStored b m4 DB cap D :=
hD3.write_disjoint (UB + n) L fU (by have h := hl.UD; omega)
have hC4 : PolynomialStored b m4 CB cap C :=
hC3.write_disjoint (UB + n) L fU (by have h := hl.UC; omega)
have hR5 := hR4.meta_update hl.Rlow 71 n (by norm_num)
have hU5 := hU4.meta_update hl.Ulow 71 n (by norm_num)
have hD5 := hD4.meta_update hl.Dlow 71 n (by norm_num)
have hC5 := hC4.meta_update hl.Clow 71 n (by norm_num)
haveI : CharP F 2 := pinsketch_charP
haveI : CharP F[X] 2 := inferInstance
refine ⟨?_, ?_, hD5, hC5⟩
· simpa only [leadingCancel, div_eq_mul_inv, CharTwo.sub_eq_add, a] using hR5
· simpa only [leadingCancel, div_eq_mul_inv, CharTwo.sub_eq_add, a] using hU5
theorem RowsLayout.swap {R U D C cap : ℕ} (h : RowsLayout R U D C cap) :
RowsLayout D C R U cap :=
⟨h.Dlow, h.Clow, h.Rlow, h.Ulow, h.DC, h.RD.elim Or.inr Or.inl,
h.UD.elim Or.inr Or.inl, h.RC.elim Or.inr Or.inl, h.UC.elim Or.inr Or.inl, h.RU⟩
theorem rowIterationMemory_counter {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]) : rowIterationMemory b m RB UB DB CB n L R U D C 71 = n := by
simp [rowIterationMemory]
theorem rowIterationMemory_meta {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]) (hR : 128 ≤ RB) (hU : 128 ≤ UB) (slot : ℕ)
(hslot : slot < 128) (hlarge : 69 ≤ slot) (hne : slot ≠ 71) :
rowIterationMemory b m RB UB DB CB n L R U D C slot = m slot := by
have hRm (m' f : ℕ → ℕ) : writeArray (RB + n) m' f L slot = m' slot :=
writeArray_meta _ _ _ _ _ (by omega) hslot
have hUm (m' f : ℕ → ℕ) : writeArray (UB + n) m' f L slot = m' slot :=
writeArray_meta _ _ _ _ _ (by omega) hslot
have h64 : slot ≠ 64 := by omega
have h65 : slot ≠ 65 := by omega
have h66 : slot ≠ 66 := by omega
have h67 : slot ≠ 67 := by omega
have h68 : slot ≠ 68 := by omega
simp [rowIterationMemory, rowArguments, Function.update_apply,
hRm, hUm, h64, h65, h66, h67, h68, hne]
/-- The complete machine body performs the two shifted row updates and
returns a canonical state with the decreased loop counter. -/
theorem longDivBody_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (pc RB UB DB CB n L cap : ℕ)
(R U D C : F[X]) (s : RAMState)
(hAt : At P pc (Stmt.compile longDivBodyStmt pc)) (hpc : s.pc = pc)
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hl : RowsLayout RB UB DB CB cap) (hcap : n + L ≤ cap)
(hRword : RB + cap ≤ 2 ^ E.W) (hUword : UB + cap ≤ 2 ^ E.W)
(hDword : DB + cap ≤ 2 ^ E.W) (hCword : CB + cap ≤ 2 ^ E.W)
(hD : D.natDegree < L) (hC : C.natDegree < L)
(hRW : RB + cap ≤ 2 ^ E.W) (hUW : UB + cap ≤ 2 ^ E.W)
(hDW : DB + cap ≤ 2 ^ E.W) (hCW : CB + cap ≤ 2 ^ E.W)
(hRm : PolynomialStored b s.mem RB cap R) (hUm : PolynomialStored b s.mem UB cap U)
(hDm : PolynomialStored b s.mem DB cap D) (hCm : PolynomialStored b s.mem CB cap C)
(hm69 : s.mem 69 = D.natDegree) (hm70 : s.mem 70 = enc b D.leadingCoeff⁻¹)
(hm71 : s.mem 71 = n + 1) (hm72 : s.mem 72 = RB) (hm73 : s.mem 73 = UB)
(hm74 : s.mem 74 = DB) (hm75 : s.mem 75 = CB) (hm76 : s.mem 76 = L)
(hm77 : s.mem 77 = w) :
Sem P E pc (pc + 229) s
(fun k s' => k ≤ 48 * L + 185 ∧
s' = rankState (pc + 229) (rowIterationMemory b s.mem RB UB DB CB n L R U D C) n) := by
let m := s.mem
let a := R.coeff (D.natDegree + n) * D.leadingCoeff⁻¹
let m1 := rowArguments m (RB + n) DB L w (enc b a)
let fR := fun i => enc b (a * D.coeff i + R.coeff (n + i))
let m2 := writeArray (RB + n) m1 fR L
let m3 := Function.update (Function.update m2 64 (UB + n)) 65 CB
let fU := fun i => enc b (a * C.coeff i + U.coeff (n + i))
let m4 := writeArray (UB + n) m3 fU L
have hLcap : L ≤ cap := by omega
have hLpos : 1 ≤ L := by omega
have hLword : L < 2 ^ E.W := by have h := hl.Rlow; omega
have hnword : n + 1 < 2 ^ E.W := by have h := hl.Rlow; omega
have hAddr : RB + n + D.natDegree < 2 ^ E.W := by omega
have hRB : RB + n < 2 ^ E.W := by omega
have hUB : UB + n < 2 ^ E.W := by omega
have hDB : DB < 2 ^ E.W := by omega
have hCB : CB < 2 ^ E.W := by omega
have hWidth : (77 : ℕ) < 2 ^ E.W := by
have hp : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (77 : ℕ) < 2 ^ 8) hp
have hSmall (i : ℕ) (hi : i ≤ 77) : i < 2 ^ E.W := by omega
obtain ⟨hPrepareAt, hRest1⟩ := At.seqStmt hAt
obtain ⟨hAxpy1At, hRest2⟩ := At.seqStmt hRest1
obtain ⟨hSecondAt, hRest3⟩ := At.seqStmt hRest2
obtain ⟨hAxpy2At, hTailAt⟩ := At.seqStmt hRest3
have hPrepareRun : runBlock longDivPrepareCode E s = boundaryState (pc + 64) m1 := by
simpa only [hpc, m1, m, a] using longDivPrepare_spec b ι t N E s R D RB DB D.natDegree n L cap
hw hW hdet hAddr hDB hnword hLword (by omega) hRm hm72 hm74 hm71 hm69 hm70 hm77 hm76
have hPrepare : Sem P E pc (pc + 64) s
(fun k z => k ≤ 64 ∧ z = boundaryState (pc + 64) m1) := by
refine Sem.mono (Sem.block P E pc longDivPrepareCode s hPrepareAt
(by simp [longDivPrepareCode, longDivReadCode, longDivWriteCode, metaReadCode,
metaStoreCode, fieldMulCode, zeroRegsCode]) hpc) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 64 at hk; omega, ?_⟩
rw [hz, hPrepareRun]
have hR1 : PolynomialStored b m1 RB cap R := hRm.rowArguments hl.Rlow _ _ _ _ _
have hU1 : PolynomialStored b m1 UB cap U := hUm.rowArguments hl.Ulow _ _ _ _ _
have hD1 : PolynomialStored b m1 DB cap D := hDm.rowArguments hl.Dlow _ _ _ _ _
have hC1 : PolynomialStored b m1 CB cap C := hCm.rowArguments hl.Clow _ _ _ _ _
have hAxpy1 : Sem P E (pc + 64) (pc + 116) (boundaryState (pc + 64) m1)
(fun k z => k ≤ 24 * L + 30 ∧ z = boundaryState (pc + 116) m2) := by
exact axpyProcedure_spec b ι t N P E (pc + 64) (RB + n) DB L a D.coeff
(fun i => R.coeff (n + i)) m1 hAxpy1At hw hW hdet hRB hDB hLword
(by omega) (by omega) (by have h := hl.RD; omega)
(fun i hi => hD1 i (by omega))
(fun i hi => by simpa only [Nat.add_assoc] using hR1 (n + i) (by omega))
(by simp [m1, rowArguments]) (by simp [m1, rowArguments])
(by simp [m1, rowArguments]) (by simp [m1, rowArguments]) (by simp [m1, rowArguments])
have hMeta2 (slot : ℕ) (hs : slot < 128) : m2 slot = m1 slot :=
writeArray_meta _ _ _ _ _ (by have h := hl.Rlow; omega) hs
have hGlobal2 (slot : ℕ) (hs : slot < 128) (hg : 69 ≤ slot) : m2 slot = m slot := by
rw [hMeta2 slot hs]
exact rowArguments_frame _ _ _ _ _ _ _ (Or.inr hg)
have hSecondRun : runBlock (shiftedArgumentsCode 73 75) E (boundaryState (pc + 116) m2) =
boundaryState (pc + 150) m3 := by
exact shiftedArguments_spec E (boundaryState (pc + 116) m2) 73 75 UB CB n
(hSmall 71 (by norm_num)) (hSmall 73 (by norm_num)) (hSmall 75 (by norm_num))
hUB hCB hnword
(by change m2 73 = UB; rw [hGlobal2 73 (by norm_num) (by norm_num)]; exact hm73)
(by change m2 75 = CB; rw [hGlobal2 75 (by norm_num) (by norm_num)]; exact hm75)
(by change m2 71 = n + 1; rw [hGlobal2 71 (by norm_num) (by norm_num)]; exact hm71)
have hSecond : Sem P E (pc + 116) (pc + 150) (boundaryState (pc + 116) m2)
(fun k z => k ≤ 34 ∧ z = boundaryState (pc + 150) m3) := by
refine Sem.mono (Sem.block P E (pc + 116) (shiftedArgumentsCode 73 75) _ hSecondAt
(by simp [shiftedArgumentsCode, metaReadCode, metaStoreCode, zeroRegsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 34 at hk; omega, ?_⟩
rw [hz, hSecondRun]
have hU2 : PolynomialStored b m2 UB cap U :=
hU1.write_disjoint (RB + n) L fR (by have h := hl.RU; omega)
have hC2 : PolynomialStored b m2 CB cap C :=
hC1.write_disjoint (RB + n) L fR (by have h := hl.RC; omega)
have hU3 : PolynomialStored b m3 UB cap U :=
(hU2.meta_update hl.Ulow 64 (UB + n) (by norm_num)).meta_update hl.Ulow 65 CB (by norm_num)
have hC3 : PolynomialStored b m3 CB cap C :=
(hC2.meta_update hl.Clow 64 (UB + n) (by norm_num)).meta_update hl.Clow 65 CB (by norm_num)
have hArg3 (slot : ℕ) (hslot : slot ≠ 64) (hslot' : slot ≠ 65) : m3 slot = m2 slot := by
simp [m3, hslot, hslot']
have hAxpy2 : Sem P E (pc + 150) (pc + 202) (boundaryState (pc + 150) m3)
(fun k z => k ≤ 24 * L + 30 ∧ z = boundaryState (pc + 202) m4) := by
exact axpyProcedure_spec b ι t N P E (pc + 150) (UB + n) CB L a C.coeff
(fun i => U.coeff (n + i)) m3 hAxpy2At hw hW hdet hUB hCB hLword
(by omega) (by omega) (by have h := hl.UC; omega)
(fun i hi => hC3 i (by omega))
(fun i hi => by simpa only [Nat.add_assoc] using hU3 (n + i) (by omega))
(by simp [m3]) (by simp [m3])
(by rw [hArg3 66 (by norm_num) (by norm_num), hMeta2 66 (by norm_num)]; simp [m1, rowArguments])
(by rw [hArg3 67 (by norm_num) (by norm_num), hMeta2 67 (by norm_num)]; simp [m1, rowArguments])
(by rw [hArg3 68 (by norm_num) (by norm_num), hMeta2 68 (by norm_num)]; simp [m1, rowArguments])
have hTailCounter : m4 71 = n + 1 := by
change writeArray (UB + n) m3 fU L 71 = n + 1
rw [writeArray_meta _ _ _ _ _ (by have h := hl.Ulow; omega) (by norm_num),
hArg3 71 (by norm_num) (by norm_num), hGlobal2 71 (by norm_num) (by norm_num)]
exact hm71
have hTailRun : runBlock longDivTailCode E (boundaryState (pc + 202) m4) =
rankState (pc + 229) (rowIterationMemory b m RB UB DB CB n L R U D C) n := by
exact longDivTail_spec E _ n (hSmall 71 (by norm_num)) hnword hTailCounter
have hTail : Sem P E (pc + 202) (pc + 229) (boundaryState (pc + 202) m4)
(fun k z => k ≤ 27 ∧ z = rankState (pc + 229) (rowIterationMemory b m RB UB DB CB n L R U D C) n) := by
refine Sem.mono (Sem.block P E (pc + 202) longDivTailCode _ hTailAt
(by simp [longDivTailCode, metaReadCode, metaStoreCode, zeroRegsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 27 at hk; omega, ?_⟩
rw [hz, hTailRun]
have h12 := Sem.seq_bound hPrepare (fun z _ hz => by subst z; exact hAxpy1)
have h123 := Sem.seq_bound h12 (fun z _ hz => by subst z; exact hSecond)
have h1234 := Sem.seq_bound h123 (fun z _ hz => by subst z; exact hAxpy2)
have hFull := Sem.seq_bound h1234 (fun z _ hz => by subst z; exact hTail)
refine Sem.mono hFull ?_
intro k z hQ
exact ⟨by have h := hQ.1; omega, hQ.2⟩
theorem MemoryFrame.trans {allowed : ℕ → Prop} {a b c : ℕ → ℕ}
(h₁ : MemoryFrame allowed a b) (h₂ : MemoryFrame allowed b c) : MemoryFrame allowed a c :=
fun addr ha => (h₂ addr ha).trans (h₁ addr ha)
theorem rowIterationMemory_frame {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (RB UB DB CB n L cap : ℕ)
(R U D C : F[X]) (hcap : n + L ≤ cap) :
MemoryFrame (divisionWritable RB UB cap) m (rowIterationMemory b m RB UB DB CB n L R U D C) := by
intro addr ha
change ¬ ((64 ≤ addr ∧ addr ≤ 68) ∨ addr = 71 ∨
(RB ≤ addr ∧ addr < RB + cap) ∨ (UB ≤ addr ∧ addr < UB + cap)) at ha
have harg : addr < 64 ∨ 69 ≤ addr := by omega
have h71 : addr ≠ 71 := by omega
have h64 : addr ≠ 64 := by omega
have h65 : addr ≠ 65 := by omega
have hR : addr < RB + n ∨ RB + n + L ≤ addr := by omega
have hU : addr < UB + n ∨ UB + n + L ≤ addr := by omega
dsimp only [rowIterationMemory]
rw [Function.update_of_ne h71, writeArray_frame _ _ _ _ addr hU,
Function.update_of_ne h65, Function.update_of_ne h64,
writeArray_frame _ _ _ _ addr hR]
exact rowArguments_frame _ _ _ _ _ _ _ harg
theorem RowCache.of_frame {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 n n' : ℕ}
{m m' : ℕ → ℕ} (h : RowCache b D RB UB DB CB L m n)
(hf : ∀ slot, 69 ≤ slot → slot < 128 → slot ≠ 71 → m' slot = m slot)
(hc : m' 71 = n') : RowCache b D RB UB DB CB L m' n' :=
⟨(hf 69 (by norm_num) (by norm_num) (by norm_num)).trans h.degree,
(hf 70 (by norm_num) (by norm_num) (by norm_num)).trans h.inverse, hc,
(hf 72 (by norm_num) (by norm_num) (by norm_num)).trans h.prevR,
(hf 73 (by norm_num) (by norm_num) (by norm_num)).trans h.prevC,
(hf 74 (by norm_num) (by norm_num) (by norm_num)).trans h.curR,
(hf 75 (by norm_num) (by norm_num) (by norm_num)).trans h.curC,
(hf 76 (by norm_num) (by norm_num) (by norm_num)).trans h.length,
(hf 77 (by norm_num) (by norm_num) (by norm_num)).trans h.dim⟩
theorem RowCache.iteration {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 n : ℕ}
{m : ℕ → ℕ} (h : RowCache b D RB UB DB CB L m (n + 1))
(R U C : F[X]) (hR : 128 ≤ RB) (hU : 128 ≤ UB) :
RowCache b D RB UB DB CB L (rowIterationMemory b m RB UB DB CB n L R U D C) n := by
exact h.of_frame
(fun slot hlo hhi hne => rowIterationMemory_meta b m RB UB DB CB n L R U D C hR hU slot hhi hlo hne)
(rowIterationMemory_counter b m RB UB DB CB n L R U D C)
/-- Complete counted RAM division of two polynomial rows. The output is
exactly the abstract quotient/remainder update, and all unrelated memory is
preserved for later decoder stages. -/
theorem longDivLoop_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (base RB UB DB CB L cap n0 : ℕ)
(R0 U0 D C : F[X]) (m : ℕ → ℕ)
(hAt : At P base (Stmt.compile longDivStmt base))
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hl : RowsLayout RB UB DB CB cap) (hcap : n0 + L ≤ cap)
(hRW : RB + cap ≤ 2 ^ E.W) (hUW : UB + cap ≤ 2 ^ E.W)
(hDW : DB + cap ≤ 2 ^ E.W) (hCW : CB + cap ≤ 2 ^ E.W)
(hDpos : 0 < D.natDegree) (hD : D.natDegree < L) (hC : C.natDegree < L)
(hRm : PolynomialStored b m RB cap R0) (hUm : PolynomialStored b m UB cap U0)
(hDm : PolynomialStored b m DB cap D) (hCm : PolynomialStored b m CB cap C)
(hc : RowCache b D RB UB DB CB L m n0) (hBound : R0.natDegree < D.natDegree + n0) :
Sem P E base (base + 231) (rankState base m n0)
(fun k s' => k ≤ (48 * L + 187) * n0 + 1 ∧
s'.regs = (fun _ => 0) ∧ RowCache b D RB UB DB CB L s'.mem 0 ∧
MemoryFrame (divisionWritable RB UB cap) m s'.mem ∧
PolynomialStored b s'.mem RB cap (R0 % D) ∧
PolynomialStored b s'.mem UB cap (U0 - (R0 / D) * C) ∧
PolynomialStored b s'.mem DB cap D ∧ PolynomialStored b s'.mem CB cap C) := by
let I := longDivInvariant b RB UB DB CB L cap n0 R0 U0 D C m
have hW1 : 1 < 2 ^ E.W := by
have hp : (2 : ℕ) ^ 1 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (1 : ℕ) < 2 ^ 1) hp
have hframe : ∀ n s pc, I n s → I n { s with pc := pc } := by
intro n s pc h
simpa only [I, longDivInvariant] using h
have hcounter : ∀ n s, I n s → s.regs r9 = n := by
intro n s h
rw [h.1, Function.update_self]
obtain ⟨_, _, hBodyAt, hJumpAt⟩ := at_loop hAt
have hbody : ∀ n s, I (n + 1) s → s.pc = base →
Sem P E (base + 1) base { s with pc := base + 1 }
(fun k s' => k ≤ 48 * L + 186 ∧ I n s') := by
intro n s hI hpc
obtain ⟨hregs, hcache, hn, hmemFrame, R, U, hRmem, hUmem, hDmem, hCmem, hRbound, hCont⟩ := hI
have hncap : n + L ≤ cap := by omega
have hrun := longDivBody_spec b ι t N P E (base + 1) RB UB DB CB n L cap R U D C
{ s with pc := base + 1 } hBodyAt rfl hw hW hdet hl hncap hRW hUW hDW hCW hD hC
hRW hUW hDW hCW hRmem hUmem hDmem hCmem hcache.degree hcache.inverse hcache.count
hcache.prevR hcache.prevC hcache.curR hcache.curC hcache.length hcache.dim
refine Sem.jmp_append (hAt := hJumpAt) (Sem.mono hrun ?_)
intro k s' hQ
obtain ⟨hcost, hs⟩ := hQ
refine ⟨by omega, ?_⟩
rw [hs]
change longDivInvariant b RB UB DB CB L cap n0 R0 U0 D C m n _
obtain ⟨hRnew, hUnew, hDnew, hCnew⟩ := rowIterationMemory_stored b s.mem RB UB DB CB n L cap
R U D C hl hncap hD hC hRmem hUmem hDmem hCmem
have hcache' := hcache.iteration R U C hl.Rlow hl.Ulow
have hframe' := MemoryFrame.trans hmemFrame
(rowIterationMemory_frame b s.mem RB UB DB CB n L cap R U D C hncap)
refine ⟨rfl, hcache', by omega, hframe',
R - leadingCancel D R n * D, U - leadingCancel D R n * C,
hRnew, hUnew, hDnew, hCnew, leadingCancel_degree D R n hDpos hRbound, ?_⟩
simpa only [longReduceRows] using hCont
have hinit : I n0 (rankState base m n0) := by
refine ⟨rfl, hc, le_rfl, ?_, R0, U0, hRm, hUm, hDm, hCm, hBound, rfl⟩
intro addr _
rfl
have hloop := Sem.loop_invariant P E base longDivBodyStmt hAt hW1 I (48 * L + 186)
hframe hcounter hbody n0 (rankState base m n0) hinit rfl
refine Sem.mono hloop ?_
intro k s' hQ
obtain ⟨hcost, hI⟩ := hQ
obtain ⟨hregs, hcache, _, hmemFrame, R, U, hRmem, hUmem, hDmem, hCmem, _, hCont⟩ := hI
have hrows : (R, U) = (R0 % D, U0 - (R0 / D) * C) := by
rw [longReduceRows_eq D C n0 R0 U0 hDpos hBound] at hCont
exact hCont
have hReq : R = R0 % D := congrArg Prod.fst hrows
have hUeq : U = U0 - (R0 / D) * C := congrArg Prod.snd hrows
rw [hReq] at hRmem
rw [hUeq] at hUmem
refine ⟨hcost, ?_, hcache, hmemFrame, hRmem, hUmem, hDmem, hCmem⟩
rw [hregs]
funext d
simp [Function.update_apply]
/-- Load the counter at a procedure boundary. -/
theorem rankRead_spec (E : RAMEnv) (pc : ℕ) (m : ℕ → ℕ) (n : ℕ)
(haddr : (71 : ℕ) < 2 ^ E.W) (hn : n < 2 ^ E.W) (hm : m 71 = n) :
runBlock (metaReadCode r9 71) E (boundaryState pc m) = rankState (pc + 3) m n := by
rw [metaRead_spec E _ _ _ (by decide)]
apply ramState_eq_of
· rfl
· rfl
· intro d
fin_cases d <;> simp [boundaryState, rankState, hm, Nat.mod_eq_of_lt haddr, Nat.mod_eq_of_lt hn]
/-- Callable RAM quotient/remainder row procedure, returning zero registers.
Its footprint is the two destination buffers and the designated metadata. -/
theorem longDivProcedure_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
(P : Program) (E : RAMEnv) (base RB UB DB CB L cap n0 : ℕ)
(R0 U0 D C : F[X]) (m : ℕ → ℕ)
(hAt : At P base (Stmt.compile longDivProcedure base))
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hl : RowsLayout RB UB DB CB cap) (hcap : n0 + L ≤ cap)
(hRW : RB + cap ≤ 2 ^ E.W) (hUW : UB + cap ≤ 2 ^ E.W)
(hDW : DB + cap ≤ 2 ^ E.W) (hCW : CB + cap ≤ 2 ^ E.W)
(hDpos : 0 < D.natDegree) (hD : D.natDegree < L) (hC : C.natDegree < L)
(hRm : PolynomialStored b m RB cap R0) (hUm : PolynomialStored b m UB cap U0)
(hDm : PolynomialStored b m DB cap D) (hCm : PolynomialStored b m CB cap C)
(hc : RowCache b D RB UB DB CB L m n0) (hBound : R0.natDegree < D.natDegree + n0) :
Sem P E base (base + 234) (boundaryState base m)
(fun k s' => k ≤ (48 * L + 187) * n0 + 4 ∧ ∃ m' : ℕ → ℕ,
s' = boundaryState (base + 234) m' ∧ RowCache b D RB UB DB CB L m' 0 ∧
MemoryFrame (divisionWritable RB UB cap) m m' ∧
PolynomialStored b m' RB cap (R0 % D) ∧
PolynomialStored b m' UB cap (U0 - (R0 / D) * C) ∧
PolynomialStored b m' DB cap D ∧ PolynomialStored b m' CB cap C) := by
obtain ⟨hReadAt, hLoopAt⟩ := At.seqStmt hAt
have hnWord : n0 < 2 ^ E.W := by have h := hl.Rlow; omega
have hAddr : (71 : ℕ) < 2 ^ E.W := by
have hp : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (71 : ℕ) < 2 ^ 8) hp
have hReadRun := rankRead_spec E base m n0 hAddr hnWord hc.count
have hRead : Sem P E base (base + 3) (boundaryState base m)
(fun k s' => k ≤ 3 ∧ s' = rankState (base + 3) m n0) := by
refine Sem.mono (Sem.block P E base (metaReadCode r9 71) _ hReadAt
(by simp [metaReadCode]) rfl) ?_
intro k s' hQ
obtain ⟨hk, hs⟩ := hQ
refine ⟨by change k = 3 at hk; omega, ?_⟩
rw [hs, hReadRun]
have hLoop := longDivLoop_spec b ι t N P E (base + 3) RB UB DB CB L cap n0 R0 U0 D C m
hLoopAt hw hW hdet hl hcap hRW hUW hDW hCW hDpos hD hC hRm hUm hDm hCm hc hBound
have hFull := Sem.seq_bound hRead (fun z _ hz => by subst z; exact hLoop)
obtain ⟨hpc, k, z, hrun, hreturn, hcost, hregs, hcache, hframe, hRout, hUout, hDout, hCout⟩ := hFull
refine ⟨hpc, k, z, hrun, hreturn, ?_, z.mem, ?_, hcache, hframe, hRout, hUout, hDout, hCout⟩
· omega
· apply ramState_eq_of
· exact hreturn
· rfl
· intro d
simpa only [boundaryState] using congrFun hregs d
/-- A straight-line procedure with zero registers at both boundaries. -/
theorem Sem.boundary_block (P : Program) (E : RAMEnv) (base : ℕ)
(code : List Instr) (m m' : ℕ → ℕ) (hAt : At P base code)
(hno : NoBranch code)
(hrun : runBlock code E (boundaryState base m) = boundaryState (base + code.length) m') :
Sem P E base (base + code.length) (boundaryState base m)
(fun k s' => k ≤ code.length ∧ s' = boundaryState (base + code.length) m') := by
refine Sem.mono (Sem.block P E base code _ hAt hno rfl) ?_
intro k s' hQ
obtain ⟨hk, hs⟩ := hQ
exact ⟨by omega, hs.trans hrun⟩
theorem scanArgs_spec {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (E : RAMEnv) (pc B L : ℕ)
(p : F[X]) (m : ℕ → ℕ) (hmeta : (66 : ℕ) < 2 ^ E.W)
(hB : B < 2 ^ E.W) (hL : L < 2 ^ E.W) (hm64 : m 64 = B) (hm66 : m 66 = L) :
runBlock scanArgsCode E (boundaryState pc m) =
scanState b (pc + 6) B L p m (fun _ => 0) 0 := by
have h64 : (64 : ℕ) % 2 ^ E.W = 64 := Nat.mod_eq_of_lt (by omega)
have h66 : (66 : ℕ) % 2 ^ E.W = 66 := Nat.mod_eq_of_lt hmeta
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt (by omega)
apply ramState_eq_of
· simp only [scanArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr, Function.update_self,
Nat.zero_mod, runBlock_nil, scanState, ite_self, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
fin_cases d <;> simp only [scanArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr, h64,
Function.update_self, hm64, Nat.mod_eq_of_lt hB, h66, hm66, Nat.mod_eq_of_lt hL, h1,
Nat.zero_mod, runBlock_nil, Fin.zero_eta, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, zero_ne_one, scanState, degreeScan, ite_self, ↓reduceIte,
Fin.mk_one, one_ne_zero, Fin.reduceFinMk]
theorem scanProcedure_spec {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (P : Program) (E : RAMEnv) (pc B L : ℕ)
(p : F[X]) (m : ℕ → ℕ) (hAt : At P pc (Stmt.compile scanProcedure pc))
(hmeta : (95 : ℕ) < 2 ^ E.W) (hwe : w ≤ E.W)
(hBword : B < 2 ^ E.W) (hL : L < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W)
(hp : PolynomialStored b m B L p) (hm64 : m 64 = B) (hm66 : m 66 = L) :
Sem P E pc (pc + 42) (boundaryState pc m)
(fun k s' => k ≤ 17 * L + 27 ∧
s' = boundaryState (pc + 42) (Function.update m 95 (degreeScan p L))) := by
obtain ⟨hArgsAt, hRestAt⟩ := At.seqStmt hAt
obtain ⟨hScanAt, hReturnAt⟩ := At.seqStmt hRestAt
have hInit : Sem P E pc (pc + 6) (boundaryState pc m)
(fun k z => k ≤ 6 ∧ z = scanState b (pc + 6) B L p m (fun _ => 0) 0) := by
refine Sem.mono (Sem.block P E pc scanArgsCode _ hArgsAt (by simp [scanArgsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 6 at hk; omega, ?_⟩
rw [hz, scanArgs_spec b E pc B L p m (by omega) hBword hL hm64 hm66]
have hScan := scanArray_spec b P E (pc + 6) B L p m (fun _ => 0) hScanAt
(by omega) hwe hL hB hp
have hReturnRun : runBlock scanReturnCode E
{ scanState b (pc + 6) B L p m (fun _ => 0) L with pc := pc + 6 + 17 } =
boundaryState (pc + 42) (Function.update m 95 (degreeScan p L)) := by
rw [scanReturnCode, runBlock_append, zeroRegs_spec, metaStore_spec E _ r2 95 (by decide)]
simp only [scanState, Nat.mod_eq_of_lt hmeta, boundaryState]
rfl
have hReturn : Sem P E (pc + 6 + 17) (pc + 42)
{ scanState b (pc + 6) B L p m (fun _ => 0) L with pc := pc + 6 + 17 }
(fun k z => k ≤ 19 ∧ z = boundaryState (pc + 42) (Function.update m 95 (degreeScan p L))) := by
refine Sem.mono (Sem.block P E _ scanReturnCode _ hReturnAt
(by simp [scanReturnCode, metaStoreCode, zeroRegsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
exact ⟨by change k = 19 at hk; omega, hz.trans hReturnRun⟩
have hFull := Sem.seq_bound hInit (fun z _ hz => by
subst z
exact Sem.seq_bound hScan (fun z _ hz => by subst z; exact hReturn))
exact Sem.mono hFull (fun k z hQ => ⟨by omega, hQ.2⟩)
theorem copyArgs_spec (E : RAMEnv) (pc dst src L : ℕ) (m : ℕ → ℕ)
(hmeta : (66 : ℕ) < 2 ^ E.W) (hdst : dst < 2 ^ E.W) (hsrc : src < 2 ^ E.W)
(hL : L < 2 ^ E.W) (hm64 : m 64 = dst) (hm65 : m 65 = src) (hm66 : m 66 = L) :
runBlock copyArgsCode E (boundaryState pc m) = copyState (pc + 8) dst src L m (fun _ => 0) 0 := by
have hsmall : ∀ i ≤ 66, i % 2 ^ E.W = i := by
intro i hi
exact Nat.mod_eq_of_lt (by omega)
apply ramState_eq_of
· simp only [copyArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr, Function.update_self,
Nat.zero_mod, runBlock_nil, copyState, ite_self, Nat.add_right_cancel_iff, Nat.add_left_cancel_iff] <;> omega
· rfl
· intro d
fin_cases d <;> simp only [copyArgsCode, Fin.isValue, boundaryState, runBlock_cons, execInstr,
Nat.reduceLeDiff, hsmall, Function.update_self, hm64, Nat.mod_eq_of_lt hdst, hm65,
Nat.mod_eq_of_lt hsrc, Std.le_refl, hm66, Nat.mod_eq_of_lt hL, Nat.one_le_ofNat,
zero_le, runBlock_nil, Fin.zero_eta, ne_eq, Fin.reduceEq, not_false_eq_true,
Function.update_of_ne, zero_ne_one, copyState, ite_self, ↓reduceIte, Fin.mk_one,
one_ne_zero, Fin.reduceFinMk]
theorem copyProcedure_spec (P : Program) (E : RAMEnv) (pc dst src L : ℕ)
(m : ℕ → ℕ) (hAt : At P pc (Stmt.compile copyProcedure pc))
(hmeta : (66 : ℕ) < 2 ^ E.W) (hdstWord : dst < 2 ^ E.W) (hsrcWord : src < 2 ^ E.W)
(hL : L < 2 ^ E.W) (hdst : dst + L ≤ 2 ^ E.W) (hsrc : src + L ≤ 2 ^ E.W)
(hdisj : src + L ≤ dst ∨ dst + L ≤ src) (hword : ∀ i < L, m (src + i) < 2 ^ E.W)
(hm64 : m 64 = dst) (hm65 : m 65 = src) (hm66 : m 66 = L) :
Sem P E pc (pc + 36) (boundaryState pc m)
(fun k s' => k ≤ 12 * L + 26 ∧
s' = boundaryState (pc + 36) (writeArray dst m (fun i => m (src + i)) L)) := by
obtain ⟨hArgsAt, hRestAt⟩ := At.seqStmt hAt
obtain ⟨hCopyAt, hReturnAt⟩ := At.seqStmt hRestAt
have hInit : Sem P E pc (pc + 8) (boundaryState pc m)
(fun k z => k ≤ 8 ∧ z = copyState (pc + 8) dst src L m (fun _ => 0) 0) := by
refine Sem.mono (Sem.block P E pc copyArgsCode _ hArgsAt (by simp [copyArgsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
exact ⟨by change k = 8 at hk; omega,
hz.trans (copyArgs_spec E pc dst src L m hmeta hdstWord hsrcWord hL hm64 hm65 hm66)⟩
have hCopy := copyArray_spec P E (pc + 8) dst src L m (fun _ => 0) hCopyAt
(by omega) hL hdst hsrc hdisj hword
have hReturn : Sem P E (pc + 8 + 12) (pc + 36)
{ copyState (pc + 8) dst src L m (fun _ => 0) L with pc := pc + 8 + 12 }
(fun k z => k ≤ 16 ∧
z = boundaryState (pc + 36) (writeArray dst m (fun i => m (src + i)) L)) := by
refine Sem.mono (Sem.block P E _ zeroRegsCode _ hReturnAt (by simp [zeroRegsCode]) rfl) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 16 at hk; omega, ?_⟩
rw [hz, zeroRegs_spec]
rfl
have hFull := Sem.seq_bound hInit (fun z _ hz => by
subst z
exact Sem.seq_bound hCopy (fun z _ hz => by subst z; exact hReturn))
exact Sem.mono hFull (fun k z hQ => ⟨by omega, hQ.2⟩)
theorem scanSetup_spec (E : RAMEnv) (s : RAMState) (slot B cap : ℕ)
(hmeta : (81 : ℕ) < 2 ^ E.W) (hslot : slot < 2 ^ E.W)
(hB : B < 2 ^ E.W) (hcap : cap < 2 ^ E.W) (hmB : s.mem slot = B) (hmcap : s.mem 81 = cap) :
runBlock (scanSetupCode slot) E s = boundaryState (s.pc + 28)
(Function.update (Function.update s.mem 64 B) 66 cap) := by
have hsmall : ∀ i ≤ 81, i % 2 ^ E.W = i := by
intro i hi
exact Nat.mod_eq_of_lt (by omega)
rw [scanSetupCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc (scanSetupCode slot) E s (by
simp [scanSetupCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [scanSetupCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 28 at hp
exact hp
· simp only [boundaryState, Fin.isValue, List.append_assoc, runBlock_append, ne_eq, Fin.reduceEq,
not_false_eq_true, metaRead_spec, Nat.mod_eq_of_lt hslot, hmB, Nat.mod_eq_of_lt hB, Std.le_refl,
hsmall, hmcap, Nat.mod_eq_of_lt hcap, metaStore_spec, Function.update_idem, Nat.reduceLeDiff,
Function.update_of_ne, Function.update_self]
· intro _; rfl
/-- Cache a divisor degree and inverse leading coefficient using the scan.
No field-unit encoding assumption is made. -/
theorem cacheDivisor_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ) (E : RAMEnv)
(s : RAMState) (D : F[X]) (DB cap : ℕ) (hDBlow : 128 ≤ DB)
(hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι)
(hDB : DB + D.natDegree < 2 ^ E.W) (hd : D.natDegree + 1 < 2 ^ E.W)
(hcap : D.natDegree < cap) (hD : PolynomialStored b s.mem DB cap D)
(hm95 : s.mem 95 = D.natDegree + 1) (hm74 : s.mem 74 = DB) (hm77 : s.mem 77 = w) :
runBlock cacheDivisorCode E s = boundaryState (s.pc + 39)
(Function.update (Function.update s.mem 69 D.natDegree) 70 (enc b D.leadingCoeff⁻¹)) := by
have hpow : (2 : ℕ) ^ w ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
have hwidth : (95 : ℕ) < 2 ^ E.W := by
have hp : (2 : ℕ) ^ 8 ≤ 2 ^ E.W := by
rw [hW]
exact Nat.pow_le_pow_right (by norm_num) (by omega)
exact lt_of_lt_of_le (by norm_num : (95 : ℕ) < 2 ^ 8) hp
have hsmall : ∀ i ≤ 95, i % 2 ^ E.W = i := by
intro i hi
exact Nat.mod_eq_of_lt (by omega)
have hDB0 : DB % 2 ^ E.W = DB := Nat.mod_eq_of_lt (by omega)
have hd1 : (D.natDegree + 1) % 2 ^ E.W = D.natDegree + 1 := Nat.mod_eq_of_lt hd
have hpred : (D.natDegree + 1 + 2 ^ E.W - 1) % 2 ^ E.W = D.natDegree := by
rw [show D.natDegree + 1 + 2 ^ E.W - 1 = D.natDegree + 2 ^ E.W by omega]
simp [Nat.add_mod, Nat.mod_eq_of_lt (show D.natDegree < 2 ^ E.W by omega)]
have haddr : (DB + D.natDegree) % 2 ^ E.W = DB + D.natDegree := Nat.mod_eq_of_lt hDB
have hw0 : w % 2 ^ E.W = w :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (Nat.lt_two_pow_self (n := w)) hpow)
have hEnc (z : F) : enc b z % 2 ^ E.W = enc b z :=
Nat.mod_eq_of_lt (lt_of_lt_of_le (enc_lt b z) hpow)
have hd0 : D.natDegree % 2 ^ E.W = D.natDegree := Nat.mod_eq_of_lt (by omega)
have hmlead : s.mem (DB + D.natDegree) = enc b D.leadingCoeff := hD D.natDegree hcap
have hreadne : DB + D.natDegree ≠ 69 := by omega
let sA := runBlock cacheDivisorReadCode E s
have hA10 : sA.regs r10 = enc b D.leadingCoeff := by
simp only [cacheDivisorReadCode, Fin.isValue, List.append_assoc, List.cons_append, List.nil_append,
runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true, metaRead_spec, Std.le_refl, hsmall, hm95, hd1,
runBlock_cons, execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self,
Nat.succ_add_sub_one, Nat.add_mod_right, hd0, metaStore_spec, Nat.reduceLeDiff, Nat.reduceEqDiff, hm74,
hDB0, haddr, hreadne, hmlead, hEnc, hm77, hw0, sA]
have hAm : sA.mem = Function.update s.mem 69 D.natDegree := by
simp only [cacheDivisorReadCode, Fin.isValue, List.append_assoc, List.cons_append, List.nil_append,
runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true, metaRead_spec, Std.le_refl, hsmall, hm95, hd1,
runBlock_cons, execInstr, Nat.one_le_ofNat, Function.update_of_ne, Function.update_self,
Nat.succ_add_sub_one, Nat.add_mod_right, hd0, metaStore_spec, Nat.reduceLeDiff, Nat.reduceEqDiff,
Nat.mod_add_mod, sA]
have hInv := fieldInvCode_spec b ι t N E sA D.leadingCoeff hw hW hdet hA10
have hfinish : runBlock cacheDivisorCode E s =
runBlock zeroRegsCode E (runBlock (metaStoreCode r10 70) E (runBlock fieldInvCode E sA)) := by
simp only [cacheDivisorCode, runBlock_append] <;> rfl
have hmem : (runBlock (metaStoreCode r10 70) E (runBlock fieldInvCode E sA)).mem =
Function.update (Function.update s.mem 69 D.natDegree) 70 (enc b D.leadingCoeff⁻¹) := by
rw [hInv, metaStore_spec E _ r10 70 (by decide)]
simp only [Nat.mod_eq_of_lt (show (70 : ℕ) < 2 ^ E.W by omega), Function.update_self]
exact congrArg (fun m => Function.update m 70 (enc b D.leadingCoeff⁻¹)) hAm
rw [hfinish, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc cacheDivisorCode E s (by
simp [cacheDivisorCode, cacheDivisorReadCode, metaReadCode, metaStoreCode,
fieldInvCode, zeroRegsCode])
rw [hfinish, zeroRegs_spec] at hp
exact hp
· exact hmem
· intro _; rfl
theorem swapRows_spec (E : RAMEnv) (s : RAMState) (RB UB DB CB : ℕ)
(hmeta : (75 : ℕ) < 2 ^ E.W)
(hR : RB < 2 ^ E.W) (hU : UB < 2 ^ E.W) (hD : DB < 2 ^ E.W) (hC : CB < 2 ^ E.W)
(hm72 : s.mem 72 = RB) (hm73 : s.mem 73 = UB) (hm74 : s.mem 74 = DB) (hm75 : s.mem 75 = CB) :
runBlock swapRowsCode E s = boundaryState (s.pc + 40) (swapRowMemory s.mem RB UB DB CB) := by
have hsmall : ∀ i ≤ 75, i % 2 ^ E.W = i := by
intro i hi
exact Nat.mod_eq_of_lt (by omega)
rw [swapRowsCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc swapRowsCode E s (by
simp [swapRowsCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [swapRowsCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 40 at hp
exact hp
· simp [runBlock_append, metaRead_spec, metaStore_spec, swapRowMemory, hsmall,
hm72, hm73, hm74, hm75, Nat.mod_eq_of_lt hR, Nat.mod_eq_of_lt hU,
Nat.mod_eq_of_lt hD, Nat.mod_eq_of_lt hC, boundaryState]
· intro _; rfl
theorem MemoryFrame.mono {A B : ℕ → Prop} {m m' : ℕ → ℕ}
(hf : MemoryFrame A m m') (hab : ∀ addr, A addr → B addr) : MemoryFrame B m m' := by
intro addr hB
exact hf addr (fun hA => hB (hab addr hA))
theorem MemoryFrame.update (m : ℕ → ℕ) (slot value : ℕ) :
MemoryFrame (fun addr => addr = slot) m (Function.update m slot value) := by
intro addr hne
exact Function.update_of_ne hne value m
theorem MemoryFrame.meta_update (m : ℕ → ℕ) (slot value : ℕ) (hslot : slot < 128) :
MemoryFrame (fun addr => addr < 128) m (Function.update m slot value) :=
(MemoryFrame.update m slot value).mono (by intro addr ha; subst addr; exact hslot)
theorem PolynomialStored.of_metaFrame {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m m' : ℕ → ℕ} {B cap : ℕ} {p : F[X]}
(hp : PolynomialStored b m B cap p) (hB : 128 ≤ B)
(hf : MemoryFrame (fun addr => addr < 128) m m') : PolynomialStored b m' B cap p := by
intro i hi
rw [hf (B + i) (by omega)]
exact hp i hi
/-- Arrays and persistent metadata survive a scratch-metadata preparation. -/
theorem PadeRows.of_scratchFrame {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 m' : ℕ → ℕ} {s : PadeState F}
(h : PadeRows b E RB UB DB CB L cap m s)
(hf : MemoryFrame (fun addr => addr < 128) m m')
(hp : ∀ slot, slot = 72 ∨ slot = 73 ∨ slot = 74 ∨ slot = 75 ∨ slot = 76 ∨ slot = 77 ∨ slot = 81 →
m' slot = m slot) : PadeRows b E RB UB DB CB L cap m' s := by
refine ⟨h.layout, h.Rword, h.Uword, h.Dword, h.Cword,
h.prevR.of_metaFrame h.layout.Rlow hf, h.prevC.of_metaFrame h.layout.Ulow hf,
h.rem.of_metaFrame h.layout.Dlow hf, h.curC.of_metaFrame h.layout.Clow hf, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
· exact (hp 72 (by simp)).trans h.ptr72
· exact (hp 73 (by simp)).trans h.ptr73
· exact (hp 74 (by simp)).trans h.ptr74
· exact (hp 75 (by simp)).trans h.ptr75
· exact (hp 76 (by simp)).trans h.length
· exact (hp 77 (by simp)).trans h.dimension
· exact (hp 81 (by simp)).trans h.capacity
theorem MemoryFrame.update_allowed (A : ℕ → Prop) (m : ℕ → ℕ) (slot value : ℕ) (hslot : A slot) :
MemoryFrame A m (Function.update m slot value) :=
(MemoryFrame.update m slot value).mono (by intro addr ha; subst addr; exact hslot)
theorem PadeRows.of_scratch {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 m' : ℕ → ℕ} {s : PadeState F}
(h : PadeRows b E RB UB DB CB L cap m s)
(hf : MemoryFrame padeScratch m m') : PadeRows b E RB UB DB CB L cap m' s := by
apply h.of_scratchFrame (hf.mono (by intro addr ha; dsimp [padeScratch] at ha; omega))
intro slot hs
exact hf slot (by dsimp [padeScratch]; omega)
theorem divisionWritable_le_pade (RB UB DB CB cap addr : ℕ)
(h : divisionWritable RB UB cap addr) : padeWritable RB UB DB CB cap addr := by
rcases h with h | h | h | h
· exact Or.inl (by omega)
· exact Or.inl (by omega)
· exact Or.inr (Or.inr (Or.inl h))
· exact Or.inr (Or.inr (Or.inr (Or.inl h)))
theorem padeWritable_swap (RB UB DB CB cap addr : ℕ) :
padeWritable DB CB RB UB cap addr ↔ padeWritable RB UB DB CB cap addr := by
simp only [padeWritable]
constructor
· rintro (h | h | h | h | h | h)
· exact Or.inl h
· exact Or.inr (Or.inl h)
· exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl h))))
· exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr h))))
· exact Or.inr (Or.inr (Or.inl h))
· exact Or.inr (Or.inr (Or.inr (Or.inl h)))
· rintro (h | h | h | h | h | h)
· exact Or.inl h
· exact Or.inr (Or.inl h)
· exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl h))))
· exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr h))))
· exact Or.inr (Or.inr (Or.inl h))
· exact Or.inr (Or.inr (Or.inr (Or.inl h)))
theorem padeRun_succ_tick {F : Type} [Field F] (t n : ℕ) (s : PadeState F) :
padeRun t n (padeTick t s) = padeRun t (n + 1) s := by
by_cases h : s.rem.natDegree < t
· cases n <;> simp [padeTick, padeRun, h]
· simp [padeTick, padeRun, h]
/-- The scan test is exact even when the current remainder is zero. -/
theorem padeScan_go {F : Type} [Field F] [DecidableEq F] (t cap : ℕ) (D : F[X])
(ht : 1 ≤ t) (hcap : D.natDegree < cap) :
t < degreeScan D cap ↔ t ≤ D.natDegree := by
by_cases hz : D = 0
· simp [hz]; omega
· rw [degreeScan_eq D hz cap hcap]
omega
theorem countdown_spec (E : RAMEnv) (s : RAMState) (slot n : ℕ)
(hslot : slot < 2 ^ E.W) (hn : n + 1 < 2 ^ E.W) (hm : s.mem slot = n + 1) :
runBlock (countdownCode slot) E s = rankState (s.pc + 27) (Function.update s.mem slot n) n := by
have hs : slot % 2 ^ E.W = slot := Nat.mod_eq_of_lt hslot
have hn0 : (n + 1) % 2 ^ E.W = n + 1 := Nat.mod_eq_of_lt hn
have hn1 : n % 2 ^ E.W = n := Nat.mod_eq_of_lt (by omega)
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt (by omega)
have hpred : (n + 1 + 2 ^ E.W - 1) % 2 ^ E.W = n := by
rw [show n + 1 + 2 ^ E.W - 1 = n + 2 ^ E.W by omega]
simp [Nat.add_mod, hn1]
apply ramState_eq_of
· exact runBlock_pc (countdownCode slot) E s (by
simp [countdownCode, metaReadCode, metaStoreCode, zeroRegsCode])
· simp only [countdownCode, Fin.isValue, List.append_assoc, List.cons_append, List.nil_append,
runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true, metaRead_spec, hs, hm, hn0, runBlock_cons,
execInstr, h1, Function.update_of_ne, Function.update_self, Nat.succ_add_sub_one, Nat.add_mod_right,
hn1, metaStore_spec, zeroRegs_spec, boundaryState, rankState]
· intro d
fin_cases d <;> simp only [countdownCode, Fin.isValue, List.append_assoc, List.cons_append,
List.nil_append, runBlock_append, ne_eq, Fin.reduceEq, not_false_eq_true,
metaRead_spec, hs, hm, hn0, runBlock_cons, execInstr, h1, Function.update_of_ne,
Function.update_self, Nat.succ_add_sub_one, Nat.add_mod_right, hn1, metaStore_spec,
zeroRegs_spec, boundaryState, Fin.zero_eta, rankState, Fin.mk_one, Fin.reduceFinMk]
theorem rankReadSlot_spec (E : RAMEnv) (pc : ℕ) (m : ℕ → ℕ) (slot n : ℕ)
(haddr : slot < 2 ^ E.W) (hn : n < 2 ^ E.W) (hm : m slot = n) :
runBlock (metaReadCode r9 slot) E (boundaryState pc m) = rankState (pc + 3) m n := by
rw [metaRead_spec E _ _ _ (by decide)]
apply ramState_eq_of
· rfl
· rfl
· intro d
fin_cases d <;> simp [boundaryState, rankState, hm, Nat.mod_eq_of_lt haddr, Nat.mod_eq_of_lt hn]
theorem arraySetup_spec (E : RAMEnv) (s : RAMState) (dstSlot srcSlot dst src len : ℕ)
(hmeta : (81 : ℕ) < 2 ^ E.W) (hds : dstSlot < 2 ^ E.W) (hss : srcSlot < 2 ^ E.W)
(hdst : dst < 2 ^ E.W) (hsrc : src < 2 ^ E.W) (hlen : len < 2 ^ E.W)
(hmD : s.mem dstSlot = dst) (hmS : s.mem srcSlot = src) (hm81 : s.mem 81 = len) :
runBlock (arraySetupCode dstSlot srcSlot) E s =
boundaryState (s.pc + 34) (arrayArguments s.mem dst src len) := by
have hsmall : ∀ i ≤ 81, i % 2 ^ E.W = i := by
intro i hi
exact Nat.mod_eq_of_lt (by omega)
rw [arraySetupCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc (arraySetupCode dstSlot srcSlot) E s (by
simp [arraySetupCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [arraySetupCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 34 at hp
exact hp
· simp [runBlock_append, metaRead_spec, metaStore_spec, arrayArguments,
hsmall, Nat.mod_eq_of_lt hds, Nat.mod_eq_of_lt hss, hmD, hmS, hm81,
Nat.mod_eq_of_lt hdst, Nat.mod_eq_of_lt hsrc, Nat.mod_eq_of_lt hlen, boundaryState]
· intro _; rfl
theorem arrayArguments_frame (m : ℕ → ℕ) (dst src len : ℕ) :
MemoryFrame (fun addr => addr = 64 ∨ addr = 65 ∨ addr = 66) m (arrayArguments m dst src len) := by
apply MemoryFrame.trans (MemoryFrame.trans
(MemoryFrame.update_allowed _ m 64 dst (by simp))
(MemoryFrame.update_allowed _ _ 65 src (by simp)))
(MemoryFrame.update_allowed _ _ 66 len (by simp))
theorem PolynomialStored.of_frame {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m m' : ℕ → ℕ} {B cap : ℕ} {p : F[X]} {A : ℕ → Prop}
(h : PolynomialStored b m B cap p) (hf : MemoryFrame A m m')
(hout : ∀ i < cap, ¬ A (B + i)) : PolynomialStored b m' B cap p := by
intro i hi
rw [hf (B + i) (hout i hi)]
exact h i hi
theorem posTab_le {F : Type} [Field F] (N : ℕ) (ι : ℕ → F) (v : F) : posTab N ι v ≤ N := by
classical
by_cases h : ∃ i, i < N ∧ ι i = v
· have hi := (Classical.choose_spec h).1
simp only [posTab, dif_pos h]
omega
· simp [posTab, h]
theorem detStd_img {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(t N : ℕ) (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) {i : ℕ} (hi : i < 2 ^ w) :
detStd t N b ι (detImgBase w + i) = enc b (ι i) := by
have hm : detMulBase w = 64 := rfl
have hs : detSqBase w = 64 + 2 ^ (2 * w) := rfl
have hv : detInvBase w = 64 + 2 ^ (2 * w) + 2 ^ (2 * w) := rfl
have hp : detPosBase w = detInvBase w + 2 ^ w := rfl
have hg : detImgBase w = detPosBase w + 2 ^ w := rfl
have he : detEnd w = detImgBase w + 2 ^ w := rfl
have hpow := Nat.two_pow_pos (2 * w)
have h0 : ¬ detImgBase w + i < 13 := by omega
have h1 : ¬ detImgBase w + i < detMulBase w := by omega
have h2 : ¬ detImgBase w + i < detSqBase w := by omega
have h3 : ¬ detImgBase w + i < detInvBase w := by omega
have h4 : ¬ detImgBase w + i < detPosBase w := by omega
have h5 : ¬ detImgBase w + i < detImgBase w := by omega
have h6 : detImgBase w + i < detEnd w := by omega
unfold detStd
rw [if_neg h0, if_neg h1, if_neg h2, if_neg h3, if_neg h4, if_neg h5, if_pos h6, Nat.add_sub_cancel_left]
rfl
/-- Clear registers at a straight-line boundary without changing memory. -/
theorem Sem.zero_block (P : Program) (E : RAMEnv) (pc : ℕ) (s : RAMState)
(hAt : At P pc zeroRegsCode) (hpc : s.pc = pc) :
Sem P E pc (pc + 16) s (fun k z => k ≤ 16 ∧ z = boundaryState (pc + 16) s.mem) := by
refine Sem.mono (Sem.block P E pc zeroRegsCode s hAt (by simp [zeroRegsCode]) hpc) ?_
intro k z hQ
obtain ⟨hk, hz⟩ := hQ
refine ⟨by change k = 16 at hk; omega, ?_⟩
rw [hz, zeroRegs_spec, hpc]
theorem copyMeta_spec (E : RAMEnv) (s : RAMState) (src dst value : ℕ)
(hsrc : src < 2 ^ E.W) (hdst : dst < 2 ^ E.W) (hv : value < 2 ^ E.W) (hm : s.mem src = value) :
runBlock (copyMetaCode src dst) E s = boundaryState (s.pc + 22) (Function.update s.mem dst value) := by
rw [copyMetaCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc (copyMetaCode src dst) E s (by simp [copyMetaCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [copyMetaCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 22 at hp
exact hp
· simp [runBlock_append, metaRead_spec, metaStore_spec, Nat.mod_eq_of_lt hsrc,
Nat.mod_eq_of_lt hdst, Nat.mod_eq_of_lt hv, hm, boundaryState]
· intro _; rfl
theorem setMeta_spec (E : RAMEnv) (s : RAMState) (slot value : ℕ)
(hs : slot < 2 ^ E.W) (hv : value < 2 ^ E.W) :
runBlock (setMetaCode slot value) E s = boundaryState (s.pc + 20) (Function.update s.mem slot value) := by
rw [setMetaCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc (setMetaCode slot value) E s (by simp [setMetaCode, metaStoreCode, zeroRegsCode])
rw [setMetaCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 20 at hp
exact hp
· simp [runBlock_append, metaStore_spec, runBlock_cons, runBlock_nil, execInstr,
Nat.mod_eq_of_lt hs, Nat.mod_eq_of_lt hv, boundaryState]
· intro _; rfl
/-- Coefficient-array copy with dynamic pointers held in fixed metadata. -/
theorem copyFromSlots_spec {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (P : Program) (E : RAMEnv)
(pc dstSlot srcSlot dst src cap : ℕ) (f : F[X]) (m : ℕ → ℕ)
(hAt : At P pc (Stmt.compile (copyFromSlotsProcedure dstSlot srcSlot) pc))
(hmeta : (81 : ℕ) < 2 ^ E.W) (hds : dstSlot < 2 ^ E.W) (hss : srcSlot < 2 ^ E.W)
(hwe : w ≤ E.W) (hcap : 1 ≤ cap) (hdst : 128 ≤ dst) (hsrc : 128 ≤ src)
(hDstWord : dst + cap ≤ 2 ^ E.W) (hSrcWord : src + cap ≤ 2 ^ E.W)
(hdisj : src + cap ≤ dst ∨ dst + cap ≤ src) (hf : PolynomialStored b m src cap f)
(hmd : m dstSlot = dst) (hms : m srcSlot = src) (hm81 : m 81 = cap) :
Sem P E pc (pc + 70) (boundaryState pc m)
(fun k z => k ≤ 12 * cap + 60 ∧ ∃ m', z = boundaryState (pc + 70) m' ∧
PolynomialStored b m' dst cap f ∧ MemoryFrame (copyFromSlotsWritable dst cap) m m') := by
let m1 := arrayArguments m dst src cap
let m2 := writeArray dst m1 (fun i => m1 (src + i)) cap
have hcapWord : cap < 2 ^ E.W :=
lt_of_lt_of_le (Nat.lt_add_of_pos_left (lt_of_lt_of_le (by norm_num : (0 : ℕ) < 128) hdst))
hDstWord
have hdstWord : dst < 2 ^ E.W :=
lt_of_lt_of_le (Nat.lt_add_of_pos_right (lt_of_lt_of_le (by norm_num : (0 : ℕ) < 1) hcap))
hDstWord
have hsrcWord : src < 2 ^ E.W :=
lt_of_lt_of_le (Nat.lt_add_of_pos_right (lt_of_lt_of_le (by norm_num : (0 : ℕ) < 1) hcap))
hSrcWord
have hf1 : PolynomialStored b m1 src cap f := by
intro i hi
change arrayArguments m dst src cap (src + i) = enc b (f.coeff i)
rw [arrayArguments_frame m dst src cap (src + i) (by
have hge : 66 < src + i :=
lt_of_lt_of_le (by norm_num : 66 < 128) (le_trans hsrc (Nat.le_add_right src i))
exact fun h => h.elim (Nat.ne_of_gt (lt_trans (by norm_num : 64 < 66) hge))
(fun h => h.elim (Nat.ne_of_gt (lt_trans (by norm_num : 65 < 66) hge)) (Nat.ne_of_gt hge)))]
exact hf i hi
obtain ⟨hSetupAt, hCopyAt⟩ := At.seqStmt hAt
have hSetup : Sem P E pc (pc + 34) (boundaryState pc m)
(fun k z => k ≤ 34 ∧ z = boundaryState (pc + 34) m1) := by
exact Sem.boundary_block P E _ (arraySetupCode dstSlot srcSlot) m m1 hSetupAt
(by simp [arraySetupCode, metaReadCode, metaStoreCode, zeroRegsCode])
(arraySetup_spec E _ dstSlot srcSlot dst src cap hmeta hds hss hdstWord hsrcWord hcapWord hmd hms hm81)
have hCopy := copyProcedure_spec P E (pc + 34) dst src cap m1 hCopyAt
(lt_trans (by norm_num : (66 : ℕ) < 81) hmeta) hdstWord hsrcWord hcapWord
hDstWord hSrcWord hdisj (fun i hi => by
have hv : m1 (src + i) = enc b (f.coeff i) := hf1 i hi
rw [hv]
exact lt_of_lt_of_le (enc_lt b _) (Nat.pow_le_pow_right (by norm_num) hwe))
(by simp [m1, arrayArguments]) (by simp [m1, arrayArguments]) (by simp [m1, arrayArguments])
have hFull := Sem.seq_bound hSetup (fun z _ hz => by subst z; exact hCopy)
have hf12 : MemoryFrame (fun addr => dst ≤ addr ∧ addr < dst + cap) m1 m2 := by
intro addr ha
exact writeArray_frame dst m1 _ cap addr
(Or.elim (not_and_or.mp ha) (fun h => Or.inl (not_le.mp h)) (fun h => Or.inr (le_of_not_gt h)))
refine Sem.mono hFull ?_
intro k z hQ
refine ⟨le_trans hQ.1 (le_of_eq (by ring)), m2, hQ.2, ?_, ?_⟩
· intro i hi
change writeArray dst m1 (fun j => m1 (src + j)) cap (dst + i) = enc b (f.coeff i)
rw [writeArray_get _ _ _ cap i hi]
exact hf1 i hi
· refine MemoryFrame.trans ((arrayArguments_frame m dst src cap).mono ?_)
(hf12.mono (by intro addr ha; exact Or.inr (Or.inr (Or.inr ha))))
intro addr ha
dsimp [copyFromSlotsWritable]
rcases ha with h | h | h
· exact Or.inl h
· exact Or.inr (Or.inl h)
· exact Or.inr (Or.inr (Or.inl h))
theorem PolynomialStored.after_root_copy {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m m' : ℕ → ℕ} {B dst cap : ℕ} {f : F[X]}
(h : PolynomialStored b m B cap f) (hB : 128 ≤ B) (hdisj : dst + cap ≤ B ∨ B + cap ≤ dst)
(hf : MemoryFrame (copyFromSlotsWritable dst cap) m m') : PolynomialStored b m' B cap f := by
apply h.of_frame hf
intro i hi
dsimp [copyFromSlotsWritable]
omega
theorem root_copy_meta {m m' : ℕ → ℕ} {dst cap slot : ℕ}
(hf : MemoryFrame (copyFromSlotsWritable dst cap) m m') (hdst : 128 ≤ dst)
(hlo : 67 ≤ slot) (hhi : slot < 128) : m' slot = m slot := by
exact hf slot (by dsimp [copyFromSlotsWritable]; omega)
theorem QueueWorkspaceSeparated.readonly {R U D C TB ZB cap QB T : ℕ}
(h : QueueWorkspaceSeparated R U D C TB ZB cap QB T) (hQB : 128 ≤ QB)
(addr : ℕ) (hlo : QB ≤ addr) (hhi : addr < QB + T * cap) :
¬ rootComputeWritable R U D C TB cap addr := by
have hR := h.QR
have hU := h.QU
have hD := h.QD
have hC := h.QC
have hT := h.QT
dsimp [rootComputeWritable, rootComputeMeta]
omega
/-- Nonempty disjoint integer intervals admit one of the two address orders. -/
theorem interval_disjoint_of_readonly (A n B len : ℕ) (hn : 1 ≤ n) (hlen : 1 ≤ len)
(h : ∀ i < n, ¬ (B ≤ A + i ∧ A + i < B + len)) :
A + n ≤ B ∨ B + len ≤ A := by
by_contra hc
have hleft : B < A + n := by omega
have hright : A < B + len := by omega
by_cases hab : A < B
· have hi : B - A < n := by omega
have he : A + (B - A) = B := by omega
exact h (B - A) hi ⟨by omega, by omega⟩
· exact h 0 (by omega) ⟨by omega, by omega⟩
/-- The gcd result stays in the original Euclidean workspace, hence it can
be copied into a separate queue even after an arbitrary number of row swaps. -/
theorem QueueWorkspaceSeparated.gcd_output_disjoint {R U D C TB ZB cap QB T out : ℕ}
(h : QueueWorkspaceSeparated R U D C TB ZB cap QB T) (hQB : 128 ≤ QB)
(hcap : 1 ≤ cap) (hT : 1 ≤ T) (hrange : ∀ i < cap, padeWritable R U D C cap (out + i)) :
out + cap ≤ QB ∨ QB + T * cap ≤ out := by
apply interval_disjoint_of_readonly out cap QB (T * cap) hcap (by
have hm := Nat.mul_le_mul hT hcap
simpa using hm)
intro i hi hIn
have hcomp : rootComputeWritable R U D C TB cap (out + i) := by
have hrow := hrange i hi
dsimp [padeWritable] at hrow
dsimp [rootComputeWritable, rootComputeMeta]
omega
exact h.readonly hQB _ hIn.1 hIn.2 hcomp
theorem incrementMeta_spec (E : RAMEnv) (s : RAMState) (slot n : ℕ)
(hslot : slot < 2 ^ E.W) (hn : n + 1 < 2 ^ E.W) (hm : s.mem slot = n) :
runBlock (incrementMetaCode slot) E s = boundaryState (s.pc + 24) (Function.update s.mem slot (n + 1)) := by
have hs : slot % 2 ^ E.W = slot := Nat.mod_eq_of_lt hslot
have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt (by omega)
rw [incrementMetaCode, runBlock_append, zeroRegs_spec]
apply ramState_eq_of
· have hp := runBlock_pc (incrementMetaCode slot) E s (by
simp [incrementMetaCode, metaReadCode, metaStoreCode, zeroRegsCode])
rw [incrementMetaCode, runBlock_append, zeroRegs_spec] at hp
change _ = s.pc + 24 at hp
exact hp
· simp [runBlock_append, metaRead_spec, metaStore_spec, runBlock_cons, runBlock_nil, execInstr,
hs, h1, hm, Nat.mod_eq_of_lt (show n < 2 ^ E.W by omega), Nat.mod_eq_of_lt hn, boundaryState]
· intro _; rfl
theorem positionValidBit_le (p : ℕ) : positionValidBit p ≤ 1 := by
by_cases hp : 0 < p <;> simp [positionValidBit, hp]
theorem position_index_word (p M : ℕ) (hM : 1 < M) (hp : p < M) :
(p + M - positionValidBit p) % M = p - 1 := by
by_cases hz : p = 0
· subst p
simp [positionValidBit]
· have hp0 : 0 < p := by omega
rw [positionValidBit, if_pos hp0]
have he : p + M - 1 = p - 1 + M := by omega
rw [he, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]
theorem rootPositionFlag_le_one {F : Type} [Field F] (N : ℕ) (ι : ℕ → F) (us : List F) :
rootPositionFlag N ι us ≤ 1 := by
induction us with
| nil => simp [rootPositionFlag]
| cons u us ih =>
change positionValidBit (posTab N ι u⁻¹) * rootPositionFlag N ι us ≤ 1
exact le_trans (Nat.mul_le_mul (positionValidBit_le _) ih) (by norm_num)
theorem FieldArrayStored.of_frame {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
{b : Module.Basis (Fin w) (ZMod 2) F} {m m' : ℕ → ℕ} {B len : ℕ} {v : ℕ → F} {A : ℕ → Prop}
(h : FieldArrayStored b m B len v) (hf : MemoryFrame A m m') (hr : ∀ j < len, ¬ A (B + j)) :
FieldArrayStored b m' B len v := by
intro j hj
rw [hf (B + j) (hr j hj)]
exact h j hj
theorem initializeLoop_spec (E : RAMEnv) (s : RAMState) (index counter source len : ℕ)
(hi : index < 2 ^ E.W) (hc : counter < 2 ^ E.W) (hs : source < 2 ^ E.W)
(hne : source ≠ index) (hlen : len < 2 ^ E.W) (hm : s.mem source = len) :
runBlock (initializeLoopCode index counter source) E s = boundaryState (s.pc + 42)
(Function.update (Function.update s.mem index 0) counter len) := by
rw [initializeLoopCode, runBlock_append, setMeta_spec E s index 0 hi (by omega)]
have hsrc : (boundaryState (s.pc + 20) (Function.update s.mem index 0)).mem source = len := by
simpa [boundaryState, hne] using hm
rw [copyMeta_spec E _ source counter len hs hc hlen hsrc] <;> rfl
theorem initializeLoop_frame (m : ℕ → ℕ) (index counter len : ℕ) :
MemoryFrame (fun addr => addr = index ∨ addr = counter) m (Function.update (Function.update m index 0) counter len) :=
MemoryFrame.trans (MemoryFrame.update_allowed _ m index 0 (Or.inl rfl))
(MemoryFrame.update_allowed _ _ counter len (Or.inr rfl))
theorem decoderAllocEnd_eq (t : ℕ) : decoderAllocEnd t = 8 * t * t + 44 * t + 144 := by
unfold decoderAllocEnd decoderVerifyBase decoderOutputBase decoderQueue1 decoderQueue0 decoderRowBase
decoderSavedBase decoderCapacity decoderLength
ring
theorem decoderAllocEnd_fits (t w : ℕ) (hw : 1 ≤ w) (ht : t < 2 ^ w) : decoderAllocEnd t < 2 ^ (8 * w) := by
have h := decoderWorkspace_fits hw ht
rw [decoderAllocEnd_eq]
dsimp [decoderWorkspaceEnd] at h
omega
theorem decoderCapacity_pos (t : ℕ) : 2 ≤ decoderCapacity t := by unfold decoderCapacity decoderLength; omega
theorem decoderRow_low (t k : ℕ) : 128 ≤ decoderRowBase t k := by
unfold decoderRowBase decoderSavedBase
omega
theorem decoderRow_end_le_queue (t k : ℕ) (hk : k < 8) :
decoderRowBase t k + decoderCapacity t ≤ decoderQueue0 t := by
have hm := Nat.mul_le_mul_right (decoderCapacity t) (show k + 1 ≤ 8 by omega)
have he : (k + 1) * decoderCapacity t = k * decoderCapacity t + decoderCapacity t := by ring
unfold decoderQueue0 decoderRowBase
omega
theorem decoderRow_word (E : RAMEnv) (t k : ℕ) (hk : k < 8) (hword : decoderAllocEnd t ≤ 2 ^ E.W) :
decoderRowBase t k + decoderCapacity t ≤ 2 ^ E.W := by
have hr := decoderRow_end_le_queue t k hk
have hQ : decoderQueue0 t ≤ decoderAllocEnd t := by
unfold decoderAllocEnd decoderVerifyBase decoderOutputBase decoderQueue1
omega
omega
theorem syndromePoly_coeff {F : Type} [Field F] (e : ℕ → F) (t j : ℕ) :
(syndromePoly e t).coeff j = if j < 2 * t then e j else 0 := by
classical
simp [syndromePoly, Polynomial.coeff_C_mul_X_pow, eq_comm]
theorem saved_syndrome_polynomial {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (t : ℕ) (e : ℕ → F) (m : ℕ → ℕ)
(hstored : FieldArrayStored b m (decoderSavedBase t) (2 * t) e)
(htail : ∀ addr, decoderSavedBase t + 2 * t ≤ addr → m addr = 0) :
PolynomialStored b m (decoderSavedBase t) (decoderCapacity t) (syndromePoly e t) := by
intro j hj
rw [syndromePoly_coeff]
by_cases h : j < 2 * t
· rw [if_pos h]
exact hstored j h
· rw [if_neg h, enc_zero]
exact htail _ (by omega)
theorem metadataAssignmentsCode_length (as : List (ℕ × MetadataExpr)) :
(metadataAssignmentsCode as).length = (as.map (fun a => a.2.code.length + 3)).sum := by
induction as with
| nil => rfl
| cons a as ih =>
change (metadataAssignmentCode a ++ metadataAssignmentsCode as).length = _
rw [List.length_append, ih]
simp [metadataAssignmentCode, metaStoreCode]
theorem decoderMetadataCode_length : decoderMetadataCode.length = 248 := by
rw [decoderMetadataCode, List.length_append, List.length_append, metadataAssignmentsCode_length]
norm_num [decoderMetadataAssignments, MetadataExpr.code, zeroRegsCode]
theorem initialPolynomialsCode_length : initialPolynomialsCode.length = 33 := rfl
theorem solverInitializationProcedure_length : solverInitializationProcedure.len = 391 := by
simp only [solverInitializationProcedure, Stmt.len, decoderMetadataCode_length, initialPolynomialsCode_length] <;> rfl
theorem decoderGeometry_spec (E : RAMEnv) (t : ℕ) (hEnd : decoderAllocEnd t < 2 ^ E.W) : DecoderGeometry E t := by
have hEnd' := hEnd
dsimp [decoderAllocEnd, decoderVerifyBase, decoderOutputBase, decoderQueue1, decoderQueue0, decoderRowBase, decoderSavedBase] at hEnd'
constructor <;>
(try dsimp [decoderSavedBase, decoderQueue0, decoderQueue1, decoderOutputBase, decoderVerifyBase, decoderRowBase]) <;> omega
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]
end Slp
end LinearSetReconciliation327.Main
Source
arXiv:2611.11409, Section 2.2 and Appendices C–D (decoder implementation and its correctness lemmas); 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