phanerozoic's picture
Put the organism first and move serialization, sizes and the Rocq map to appendices
5ee1fb5
Raw History Blame Contribute Delete
27.3 kB
(* The host netlist computes one step of SUBLEQ on 2^A words of A bits, from every state, for
every A >= 3 (Proposition 5.9). *)
From Stdlib Require Import List Bool Arith ZArith Lia.
Import ListNotations.
From TH Require Import TwoHead Net Gates PhysSem Host HostWF Adder.
(* ---- the state bits ----------------------------------------------------------------- *)
Lemma length_wbits : forall A v, length (wbits A v) = A.
Proof. intros A v. unfold wbits. rewrite length_map, length_seq. reflexivity. Qed.
Lemma nth_wbits : forall A v t, t < A -> nth t (wbits A v) false = bitof A v t.
Proof.
intros A v t Ht. unfold wbits. rewrite nth_map_d with (d' := 0) by (rewrite length_seq; lia).
rewrite seq_nth by lia. reflexivity.
Qed.
Lemma length_encodeH : forall A s, length (hmem s) = SW A -> length (encodeH A s) = nH A.
Proof.
intros A s H. unfold encodeH, nH. rewrite !length_app, length_wbits. cbn [length].
rewrite (length_concat_const _ _ A).
- rewrite length_map, H. lia.
- apply Forall_forall. intros l Hl. apply in_map_iff in Hl as (v & <- & _). apply length_wbits.
Qed.
Lemma nth_encodeH_pc : forall A s i, i < A -> nth i (encodeH A s) false = bitof A (hpc s) i.
Proof. intros A s i Hi. unfold encodeH. rewrite app_nth1 by (rewrite length_wbits; lia). apply nth_wbits. exact Hi. Qed.
Lemma nth_encodeH_halt : forall A s, nth A (encodeH A s) false = hhalt s.
Proof.
intros A s. unfold encodeH. rewrite app_nth2 by (rewrite length_wbits; lia).
rewrite length_wbits, Nat.sub_diag. reflexivity.
Qed.
Lemma nth_encodeH_mem : forall A s j t, length (hmem s) = SW A -> j < SW A -> t < A ->
nth (A + 1 + j * A + t) (encodeH A s) false = bitof A (memv s j) t.
Proof.
intros A s j t Hl Hj Ht. unfold encodeH. rewrite app_nth2 by (rewrite length_wbits; lia). rewrite length_wbits.
replace (A + 1 + j * A + t - A) with (S (A * j + t)) by lia. cbn [app nth].
rewrite (nth_concat_const _ false (map (wbits A) (hmem s)) A j t).
- rewrite nth_map_d with (d' := 0) by lia. apply nth_wbits. exact Ht.
- apply Forall_forall. intros l Hl'. apply in_map_iff in Hl' as (v & <- & _). apply length_wbits.
- rewrite length_map. lia.
- exact Ht.
Qed.
(* ---- addresses ---------------------------------------------------------------------- *)
Lemma bits_eqb : forall A p j, p < 2 ^ A -> j < 2 ^ A ->
forallb (fun t => Bool.eqb (bitof A p t) (bitof A j t)) (seq 0 A) = Nat.eqb p j.
Proof.
intros A p j Hp Hj. destruct (Nat.eqb_spec p j) as [->|E].
- apply forallb_forall. intros t _. apply eqb_reflx.
- apply Bool.not_true_is_false. intro F. apply E. apply (bits_eq_nat _ _ A Hp Hj).
intros i Hi. rewrite forallb_forall in F. specialize (F (A - 1 - i) ltac:(apply in_seq; lia)).
apply Bool.eqb_prop in F. unfold bitof in F. replace (A - 1 - (A - 1 - i)) with i in F by lia. exact F.
Qed.
Lemma testbits_eqb : forall A x y, x < 2 ^ A -> y < 2 ^ A ->
forallb (fun i => Bool.eqb (Nat.testbit x i) (Nat.testbit y i)) (seq 0 A) = Nat.eqb x y.
Proof.
intros A x y Hx Hy. destruct (Nat.eqb_spec x y) as [->|E].
- apply forallb_forall. intros t _. apply eqb_reflx.
- apply Bool.not_true_is_false. intro F. apply E. apply (bits_eq_nat _ _ A Hx Hy).
intros i Hi. rewrite forallb_forall in F. specialize (F i ltac:(apply in_seq; lia)).
apply Bool.eqb_prop in F. exact F.
Qed.
Lemma lits_fire : forall A (V : sref -> bool) f v w, v < 2 ^ A -> w < 2 ^ A ->
(forall t, t < A -> V (f t) = bitof A w t) -> forallb (litv V) (lits A f v) = Nat.eqb w v.
Proof.
intros A V f v w Hv Hw H. unfold lits. rewrite forallb_map', <- (bits_eqb A w v Hw Hv).
apply forallb_ext_in. intros t Ht. apply in_seq in Ht. unfold litv. cbn [fst snd]. rewrite H by lia. reflexivity.
Qed.
Lemma all_ones : forall A w, w < 2 ^ A -> forallb (bitof A w) (seq 0 A) = Nat.eqb w (2 ^ A - 1).
Proof.
intros A w Hw. rewrite <- (bits_eqb A w (2 ^ A - 1) Hw) by lia.
apply forallb_ext_in. intros t Ht. apply in_seq in Ht.
assert (B : bitof A (2 ^ A - 1) t = true).
{ unfold bitof. replace (2 ^ A - 1) with (Nat.ones A) by (rewrite Nat.ones_equiv; lia).
apply Nat.ones_spec_low. lia. }
rewrite B. destruct (bitof A w t); reflexivity.
Qed.
Lemma existsb_filter_eq : forall (f : nat -> bool) p n, p < n ->
existsb (fun j => Nat.eqb p j) (filter f (seq 0 n)) = f p.
Proof.
intros f p n Hp. assert (E : forall l, existsb (fun j => Nat.eqb p j) (filter f l) = existsb (fun j => Nat.eqb p j && f j) l).
{ induction l as [|a l IH]; [reflexivity|]. cbn [filter existsb]. destruct (f a) eqn:Fa; cbn [existsb];
rewrite IH; destruct (Nat.eqb p a); reflexivity. }
rewrite E, existsb_pick_at. replace ((0 <=? p) && (p <? 0 + n)) with true by (symmetry; apply andb_true_iff; split;
[apply Nat.leb_le | apply Nat.ltb_lt]; lia). reflexivity.
Qed.
Lemma existsb_pick_r : forall (g : nat -> bool) c n, c < n ->
existsb (fun a => g a && Nat.eqb c a) (seq 0 n) = g c.
Proof.
intros g c n Hc. rewrite (existsb_ext_in _ _ (fun a => Nat.eqb c a && g a)) by (intros a _; apply andb_comm).
rewrite existsb_pick_at. replace ((0 <=? c) && (c <? 0 + n)) with true by (symmetry; apply andb_true_iff; split;
[apply Nat.leb_le | apply Nat.ltb_lt]; lia). reflexivity.
Qed.
(* ---- the step, block by block --------------------------------------------------------- *)
Section HSem.
Variables (A : nat) (s : hst).
Hypotheses (HA : 3 <= A) (Hv : hvalid A s).
Let HS : 8 <= SW A := SW_ge A HA.
Definition hp : nat := hpc s.
Definition hh : bool := hhalt s.
Definition mv (j : nat) : nat := memv s j.
Lemma hp_lt : hp < SW A.
Proof. destruct Hv as (H & _ & _). exact H. Qed.
Lemma mv_lt : forall j, j < SW A -> mv j < SW A.
Proof.
destruct Hv as (_ & Hl & Hf). intros j Hj. unfold mv, memv. rewrite Forall_forall in Hf.
apply Hf. apply nth_In. lia.
Qed.
Definition HX (i : nat) : bool := nth i (encodeH A s) false.
Definition HF (x : sref) : bool := run (host_units A) (nH A) HX (idx (nH A) (hblocks A) x).
Lemma HX_pc : forall i, i < A -> HX i = bitof A hp i.
Proof. intros i Hi. apply nth_encodeH_pc. exact Hi. Qed.
Lemma HX_mu : forall j t, j < SW A -> t < A -> HX (A + 1 + j * A + t) = bitof A (mv j) t.
Proof. destruct Hv as (_ & Hl & _). intros j t Hj Ht. apply nth_encodeH_mem; assumption. Qed.
Lemma HF_in : forall i, i < nH A -> HF (SIn i) = HX i.
Proof. intros i H. unfold HF, host_units. apply net_in. exact H. Qed.
Lemma HF_pc : forall i, i < A -> HF (pcb i) = bitof A hp i.
Proof. intros i Hi. unfold pcb. rewrite HF_in by (unfold nH; lia). apply HX_pc. exact Hi. Qed.
Lemma HF_halt : HF (haltb A) = hh.
Proof. unfold haltb. rewrite HF_in by (unfold nH; lia). apply nth_encodeH_halt. Qed.
Lemma HF_mu : forall j t, j < SW A -> t < A -> HF (mu A j t) = bitof A (mv j) t.
Proof. intros j t Hj Ht. unfold mu. rewrite HF_in by (unfold nH; nia). apply HX_mu; assumption. Qed.
Lemma HF_unit : forall b j r, b < length (hblocks A) ->
j < bcount (nth b (hblocks A) blk0) -> r < bsize (nth b (hblocks A) blk0) ->
HF (SRef b j r) = sfire' (sunit (hblocks A) b j r) HF.
Proof.
intros b j r Hb Hj Hr. unfold HF, host_units.
apply net_unit; [apply host_wf; exact HA | exact Hb | exact Hj | exact Hr].
Qed.
(* the units of the blocks before the carry terms, after them, and the carry terms *)
Lemma HF_pre : forall b j r, b < 17 -> j < bcount (nth b (hpre A) blk0) -> r < bsize (nth b (hpre A) blk0) ->
HF (SRef b j r) = sfire' (nth r (bshape (nth b (hpre A) blk0) j) su0) HF.
Proof.
intros b j r Hb Hj Hr. rewrite HF_unit; unfold sunit; rewrite ?nth_hb_pre by exact Hb; try reflexivity; try assumption.
rewrite length_hblocks by lia. unfold tb. lia.
Qed.
Lemma HF_post : forall i j r, i < 15 -> j < bcount (nth i (hpost A) blk0) -> r < bsize (nth i (hpost A) blk0) ->
HF (SRef (tb A + i) j r) = sfire' (nth r (bshape (nth i (hpost A) blk0) j) su0) HF.
Proof.
intros i j r Hi Hj Hr. rewrite HF_unit; unfold sunit; rewrite ?nth_hb_post by lia; try reflexivity; try assumption.
rewrite length_hblocks by lia. lia.
Qed.
Lemma HF_Tu : forall k r, 1 <= k -> k < A -> r < S k ->
HF (SRef (16 + k) 0 r) = sfire' (nth r (bshape (blk_T A k) 0) su0) HF.
Proof.
intros k r H1 H2 H3. rewrite HF_unit; unfold sunit; rewrite ?nth_hb_T by assumption; try reflexivity.
- rewrite length_hblocks by lia. unfold tb. lia.
- cbn [bcount blk_T]. lia.
- cbn [bsize blk_T]. exact H3.
Qed.
Ltac pre_fire b := rewrite (HF_pre b) by (cbn [nth hpre bcount bsize blk_P blk_HP blk_FA blk_Q blk_F blk_PA blk_PB
blk_AC blk_W blk_RX blk_RY blk_KP blk_X blk_Y blk_PR]; nia);
cbn [nth hpre bshape blk_P blk_HP blk_FA blk_Q blk_F blk_PA blk_PB blk_AC blk_W blk_RX blk_RY blk_KP blk_X blk_Y
blk_PR].
Ltac post_fire i := rewrite (HF_post i) by (cbn [nth hpost bcount bsize blk_C blk_AX blk_NX blk_XN blk_EQ blk_R0
blk_H blk_R blk_LEQ blk_TA blk_TB blk_NP blk_HAB blk_WR blk_NM]; nia);
cbn [nth hpost bshape blk_C blk_AX blk_NX blk_XN blk_EQ blk_R0 blk_H blk_R blk_LEQ blk_TA blk_TB blk_NP blk_HAB
blk_WR blk_NM].
(* 0: decode lines of the counter *)
Lemma HF_P : forall j, j < SW A -> HF (SRef 0 j 0) = Nat.eqb hp j.
Proof.
intros j Hj. pre_fire 0. rewrite sAND_fire. apply (lits_fire A HF (pcb) j hp Hj hp_lt).
intros t Ht. apply HF_pc. exact Ht.
Qed.
(* 1 *)
Lemma HF_HP : forall i, i < A -> HF (SRef 1 i 0) = bitof A hp i && hh.
Proof.
intros i Hi. pre_fire 1. rewrite sAND_fire. cbn [forallb]. rewrite !litv_pos, HF_pc, HF_halt by exact Hi.
rewrite andb_true_r. reflexivity.
Qed.
(* 2, 3, 4: the fetch conjunctions *)
Lemma HF_FA : forall o m, o < 3 -> m < A * SW A ->
HF (SRef (2 + o) m 0) = bitof A (mv ((m mod SW A + o) mod SW A)) (m / SW A) && Nat.eqb hp (m mod SW A).
Proof.
intros o m Ho Hm. pose proof (Nat.mod_upper_bound m (SW A) ltac:(lia)).
pose proof (Nat.Div0.div_lt_upper_bound m (SW A) A ltac:(lia)).
assert (E : HF (SRef (2 + o) m 0)
= forallb (litv HF) [(mu A ((m mod SW A + o) mod SW A) (m / SW A), true); (SRef 0 (m mod SW A) 0, true)]).
{ destruct o as [|[|[|o]]]; [pre_fire 2 | pre_fire 3 | pre_fire 4 | lia]; apply sAND_fire. }
rewrite E. cbn [forallb]. rewrite !litv_pos, andb_true_r.
rewrite HF_mu by (try apply Nat.mod_upper_bound; lia). rewrite HF_P by lia. reflexivity.
Qed.
(* 5: the bits of p + 3 *)
Lemma HF_Q : forall i, i < A -> HF (SRef 5 i 0) = bitof A ((hp + 3) mod SW A) i.
Proof.
intros i Hi. pre_fire 5. rewrite sOR_fire, existsb_map'.
rewrite (existsb_ext_in _ _ (fun j => Nat.eqb hp j)).
- apply (existsb_filter_eq (fun j => bitof A ((j + 3) mod SW A) i) hp (SW A) hp_lt).
- intros j Hj. apply filter_In in Hj as [Hj _]. apply in_seq in Hj. rewrite litv_pos. apply HF_P. lia.
Qed.
(* 6: the operands *)
Lemma HF_F : forall m, m < 3 * A -> HF (SRef 6 m 0) = bitof A (mv ((hp + m / A) mod SW A)) (m mod A).
Proof.
intros m Hm. pose proof (Nat.Div0.div_lt_upper_bound m A 3 ltac:(lia)). pose proof (Nat.mod_upper_bound m A ltac:(lia)).
pre_fire 6. rewrite sOR_fire, existsb_map'.
rewrite (existsb_ext_in _ _ (fun j => bitof A (mv ((j + m / A) mod SW A)) (m mod A) && Nat.eqb hp j)).
- apply (existsb_pick_r (fun j => bitof A (mv ((j + m / A) mod SW A)) (m mod A))). exact hp_lt.
- intros j Hj. apply in_seq in Hj. rewrite litv_pos. rewrite HF_FA by (try lia; nia).
replace ((m mod A * SW A + j) mod SW A) with j
by (rewrite (Nat.add_comm (m mod A * SW A) j), Nat.Div0.mod_add, Nat.mod_small by lia; reflexivity).
replace ((m mod A * SW A + j) / SW A) with (m mod A)
by (rewrite (Nat.add_comm (m mod A * SW A) j), Nat.div_add, Nat.div_small by lia; lia).
reflexivity.
Qed.
Definition ha : nat := mv hp.
Definition hb : nat := mv ((hp + 1) mod SW A).
Definition hc : nat := mv ((hp + 2) mod SW A).
Lemma ha_lt : ha < SW A.
Proof. apply mv_lt. exact hp_lt. Qed.
Lemma hb_lt : hb < SW A.
Proof. apply mv_lt. apply Nat.mod_upper_bound. lia. Qed.
Lemma hc_lt : hc < SW A.
Proof. apply mv_lt. apply Nat.mod_upper_bound. lia. Qed.
Lemma HF_opb : forall o t, o < 3 -> t < A -> HF (opb A o t) = bitof A (mv ((hp + o) mod SW A)) t.
Proof.
intros o t Ho Ht. unfold opb. rewrite HF_F by nia.
replace ((o * A + t) / A) with o by (rewrite Nat.add_comm, Nat.div_add, Nat.div_small by lia; lia).
replace ((o * A + t) mod A) with t by (rewrite Nat.add_comm, Nat.Div0.mod_add, Nat.mod_small by lia; reflexivity).
reflexivity.
Qed.
Lemma HF_opa : forall t, t < A -> HF (opb A 0 t) = bitof A ha t.
Proof. intros t Ht. rewrite HF_opb by lia. rewrite Nat.add_0_r, Nat.mod_small by exact hp_lt. reflexivity. Qed.
(* 7, 8: decode lines of A and B *)
Lemma HF_PA : forall j, j < SW A -> HF (SRef 7 j 0) = Nat.eqb ha j.
Proof.
intros j Hj. pre_fire 7. rewrite sAND_fire. apply (lits_fire A HF (opb A 0) j ha Hj ha_lt).
intros t Ht. apply HF_opa. exact Ht.
Qed.
Lemma HF_PB : forall j, j < SW A -> HF (SRef 8 j 0) = Nat.eqb hb j.
Proof.
intros j Hj. pre_fire 8. rewrite sAND_fire. apply (lits_fire A HF (opb A 1) j hb Hj hb_lt).
intros t Ht. rewrite HF_opb by lia. reflexivity.
Qed.
(* 9: C is the halt address *)
Lemma HF_AC : HF (SRef 9 0 0) = Nat.eqb hc (SW A - 1).
Proof.
pre_fire 9. rewrite sAND_fire, forallb_map'. unfold SW. rewrite <- all_ones by exact hc_lt.
apply forallb_ext_in. intros t Ht. apply in_seq in Ht. rewrite litv_pos, HF_opb by lia. reflexivity.
Qed.
(* 10: write enables *)
Lemma HF_W : forall j, j < SW A -> HF (SRef 10 j 0) = negb hh && Nat.eqb hb j.
Proof.
intros j Hj. pre_fire 10. rewrite sAND_fire. cbn [forallb]. rewrite litv_neg, litv_pos, HF_halt, HF_PB by exact Hj.
rewrite andb_true_r. reflexivity.
Qed.
(* 11, 12: read conjunctions *)
Lemma HF_RX : forall m, m < A * SW A ->
HF (SRef 11 m 0) = bitof A (mv (m mod SW A)) (m / SW A) && Nat.eqb ha (m mod SW A).
Proof.
intros m Hm. pose proof (Nat.mod_upper_bound m (SW A) ltac:(lia)).
pose proof (Nat.Div0.div_lt_upper_bound m (SW A) A ltac:(lia)).
pre_fire 11. rewrite sAND_fire. cbn [forallb]. rewrite !litv_pos, HF_mu, HF_PA by lia. rewrite andb_true_r. reflexivity.
Qed.
Lemma HF_RY : forall m, m < A * SW A ->
HF (SRef 12 m 0) = bitof A (mv (m mod SW A)) (m / SW A) && Nat.eqb hb (m mod SW A).
Proof.
intros m Hm. pose proof (Nat.mod_upper_bound m (SW A) ltac:(lia)).
pose proof (Nat.Div0.div_lt_upper_bound m (SW A) A ltac:(lia)).
pre_fire 12. rewrite sAND_fire. cbn [forallb]. rewrite !litv_pos, HF_mu, HF_PB by lia. rewrite andb_true_r. reflexivity.
Qed.
(* 13: the cells kept *)
Lemma HF_KP : forall m, m < SW A * A ->
HF (SRef 13 m 0) = bitof A (mv (m / A)) (m mod A) && negb (negb hh && Nat.eqb hb (m / A)).
Proof.
intros m Hm. pose proof (Nat.mod_upper_bound m A ltac:(lia)).
pose proof (Nat.Div0.div_lt_upper_bound m A (SW A) ltac:(lia)).
pre_fire 13. rewrite sAND_fire. cbn [forallb]. rewrite litv_pos, litv_neg, HF_mu, HF_W by lia.
rewrite andb_true_r. reflexivity.
Qed.
(* 14, 15: x = M[A], y = M[B] *)
Definition hx : nat := mv ha.
Definition hy : nat := mv hb.
Lemma HF_X : forall t, t < A -> HF (SRef 14 t 0) = bitof A hx t.
Proof.
intros t Ht. pre_fire 14. rewrite sOR_fire, existsb_map'.
rewrite (existsb_ext_in _ _ (fun j => bitof A (mv j) t && Nat.eqb ha j)).
- apply (existsb_pick_r (fun j => bitof A (mv j) t)). exact ha_lt.
- intros j Hj. apply in_seq in Hj. rewrite litv_pos, HF_RX by nia.
rewrite (Nat.add_comm (t * SW A) j), Nat.Div0.mod_add, Nat.mod_small by lia.
replace ((j + t * SW A) / SW A) with t by (rewrite Nat.div_add, Nat.div_small by lia; lia).
reflexivity.
Qed.
Lemma HF_Y : forall t, t < A -> HF (SRef 15 t 0) = bitof A hy t.
Proof.
intros t Ht. pre_fire 15. rewrite sOR_fire, existsb_map'.
rewrite (existsb_ext_in _ _ (fun j => bitof A (mv j) t && Nat.eqb hb j)).
- apply (existsb_pick_r (fun j => bitof A (mv j) t)). exact hb_lt.
- intros j Hj. apply in_seq in Hj. rewrite litv_pos, HF_RY by nia.
rewrite (Nat.add_comm (t * SW A) j), Nat.Div0.mod_add, Nat.mod_small by lia.
replace ((j + t * SW A) / SW A) with t by (rewrite Nat.div_add, Nat.div_small by lia; lia).
reflexivity.
Qed.
Lemma HF_xv : forall i, i < A -> HF (xv A i) = Nat.testbit hx i.
Proof. intros i Hi. unfold xv. rewrite HF_X by lia. unfold bitof. f_equal. lia. Qed.
Lemma HF_yv : forall i, i < A -> HF (yv A i) = Nat.testbit hy i.
Proof. intros i Hi. unfold yv. rewrite HF_Y by lia. unfold bitof. f_equal. lia. Qed.
(* 16: propagate signals *)
Lemma HF_PR : forall i, i < A - 1 -> HF (prr i) = pg hx hy i.
Proof.
intros i Hi. unfold prr. pre_fire 16. rewrite sOR_fire. cbn [existsb]. rewrite litv_neg, litv_pos, HF_xv, HF_yv by lia.
rewrite orb_false_r. reflexivity.
Qed.
(* 17 to 15 + A: the carry terms *)
Lemma HF_Tn : forall k, 1 <= k -> k < A -> HF (SRef (16 + k) 0 0) = forallb (pg hx hy) (seq 0 k).
Proof.
intros k H1 H2. rewrite HF_Tu by lia. cbn [bshape blk_T nth]. rewrite sAND_fire, forallb_map'.
apply forallb_ext_in. intros i Hi. apply in_seq in Hi. rewrite litv_pos. apply HF_PR. lia.
Qed.
Lemma HF_Tj : forall k j, 1 <= k -> k < A -> j < k ->
HF (SRef (16 + k) 0 (S j)) = gb hx hy j && forallb (pg hx hy) (seq (S j) (k - S j)).
Proof.
intros k j H1 H2 H3. rewrite HF_Tu by lia. cbn [bshape blk_T nth].
rewrite nth_map_d with (d' := 0) by (rewrite length_seq; lia). rewrite seq_nth by lia.
rewrite sAND_fire. cbn [Nat.add forallb]. rewrite forallb_app. cbn [forallb].
rewrite litv_pos, litv_neg, HF_xv, HF_yv by lia. rewrite andb_true_r, forallb_map'.
rewrite (forallb_ext_in _ _ (pg hx hy)).
- unfold gb, xb, yb. reflexivity.
- intros i Hi. apply in_seq in Hi. rewrite litv_pos. apply HF_PR. lia.
Qed.
(* tb: carries *)
Lemma HF_C : forall m, m < A - 1 -> HF (SRef (tb A) m 0) = carry hx hy (S m).
Proof.
intros m Hm. rewrite <- (Nat.add_0_r (tb A)). post_fire 0. rewrite sOR_fire. cbn [existsb]. rewrite litv_pos.
rewrite HF_Tn by lia. rewrite existsb_map'.
rewrite (existsb_ext_in _ _ (fun j => gb hx hy j && forallb (pg hx hy) (seq (S j) (S m - S j)))).
- rewrite carry_closed. reflexivity.
- intros j Hj. apply in_seq in Hj. rewrite litv_pos. apply HF_Tj; lia.
Qed.
(* tb + 1 to tb + 4: equality *)
Lemma HF_XN : forall i, i < A -> HF (SRef (tb A + 3) i 0) = Bool.eqb (Nat.testbit hx i) (Nat.testbit hy i).
Proof.
intros i Hi. post_fire 3. rewrite sOR_fire. cbn [existsb]. rewrite !litv_pos, orb_false_r.
post_fire 1. post_fire 2. rewrite !sAND_fire. cbn [forallb]. rewrite !litv_pos, !litv_neg, HF_xv, HF_yv by lia.
destruct (Nat.testbit hx i), (Nat.testbit hy i); reflexivity.
Qed.
Lemma HF_EQ : HF (SRef (tb A + 4) 0 0) = Nat.eqb hx hy.
Proof.
post_fire 4. rewrite sAND_fire, forallb_map'. unfold SW in *.
rewrite <- (testbits_eqb A hx hy) by (apply mv_lt; first [exact ha_lt | exact hb_lt]).
apply forallb_ext_in. intros i Hi. apply in_seq in Hi. rewrite litv_pos. apply HF_XN. lia.
Qed.
(* tb + 5 to tb + 7: the sum bits *)
Lemma HF_R0 : HF (SRef (tb A + 5) 0 2) = sumbit hx hy 0.
Proof.
post_fire 5. rewrite sAND_fire. cbn [forallb]. rewrite !litv_pos, andb_true_r.
post_fire 5. post_fire 5. rewrite !sOR_fire. cbn [existsb]. rewrite !litv_pos, !litv_neg, HF_xv, HF_yv by lia.
unfold sumbit, xb, yb. cbn [carry]. destruct (Nat.testbit hx 0), (Nat.testbit hy 0); reflexivity.
Qed.
Definition cnt (k : nat) : nat :=
(if yb hy k then 1 else 0) + (if xb hx k then 0 else 1) + (if carry hx hy k then 1 else 0).
Lemma HF_H : forall m u, m < A - 1 -> u < 3 -> HF (SRef (tb A + 6) m u) = Nat.leb (S u) (cnt (S m)).
Proof.
intros m u Hm Hu. post_fire 6. rewrite nth_map_d with (d' := 0%Z) by (cbn [length]; lia).
unfold sfire'. cbn [sb sin swsum]. rewrite HF_xv, HF_yv by lia. rewrite HF_C by lia.
unfold cnt, xb, yb. destruct u as [|[|[|u]]]; [| | | lia]; cbn [nth];
destruct (Nat.testbit hy (S m)), (Nat.testbit hx (S m)), (carry hx hy (S m)); reflexivity.
Qed.
Lemma HF_R : forall m, m < A - 1 -> HF (SRef (tb A + 7) m 0) = sumbit hx hy (S m).
Proof.
intros m Hm. post_fire 7. unfold sfire'. cbn [sb sin swsum]. rewrite !HF_H by lia.
unfold sumbit, cnt, xb, yb. destruct (Nat.testbit hy (S m)), (Nat.testbit hx (S m)), (carry hx hy (S m)); reflexivity.
Qed.
Lemma HF_rbit : forall k, k < A -> HF (rbit A k) = sumbit hx hy k.
Proof.
intros k Hk. unfold rbit. destruct (Nat.eqb_spec k 0) as [->|E]; [apply HF_R0|].
rewrite HF_R by lia. f_equal. lia.
Qed.
(* the difference and the branch *)
Definition hr : nat := (hy + SW A - hx) mod SW A.
Definition hleq : bool := Nat.eqb hr 0 || Nat.leb (2 ^ (A - 1)) hr.
Lemma hx_lt : hx < 2 ^ A.
Proof. apply mv_lt. exact ha_lt. Qed.
Lemma hy_lt : hy < 2 ^ A.
Proof. apply mv_lt. exact hb_lt. Qed.
Lemma hr_bits : forall k, k < A -> Nat.testbit hr k = sumbit hx hy k.
Proof. intros k Hk. unfold hr, SW. apply sub_bits; [exact hx_lt | exact hy_lt | exact Hk]. Qed.
(* tb + 8: the branch *)
Lemma HF_LEQ : HF (SRef (tb A + 8) 0 0) = hleq.
Proof.
post_fire 8. unfold sfire'. cbn [sb sin swsum]. rewrite !HF_H by lia. rewrite HF_EQ.
replace (S (A - 2)) with (A - 1) by lia.
assert (T : sumbit hx hy (A - 1) = Nat.leb (2 ^ (A - 1)) hr).
{ rewrite <- hr_bits by lia. apply testbit_top; [lia|]. unfold hr, SW. apply Nat.mod_upper_bound, Nat.pow_nonzero.
lia. }
assert (Z : Nat.eqb hx hy = Nat.eqb hr 0).
{ unfold hr, SW. rewrite sub_zero; [reflexivity | exact hx_lt | exact hy_lt]. }
unfold hleq. rewrite <- T, <- Z. unfold sumbit, cnt, xb, yb.
destruct (Nat.testbit hy (A - 1)), (Nat.testbit hx (A - 1)), (carry hx hy (A - 1)), (Nat.eqb hx hy); reflexivity.
Qed.
(* tb + 9 to tb + 11: the next counter *)
Lemma HF_NP : forall i, i < A ->
HF (SRef (tb A + 11) i 0) = (bitof A hp i && hh) || (negb hh && hleq && bitof A hc i)
|| (negb hh && negb hleq && bitof A ((hp + 3) mod SW A) i).
Proof.
intros i Hi. post_fire 11. rewrite sOR_fire. cbn [existsb]. rewrite !litv_pos, orb_false_r.
rewrite HF_HP by exact Hi. post_fire 9. post_fire 10. rewrite !sAND_fire. cbn [forallb].
rewrite !litv_pos, !litv_neg, HF_halt, HF_LEQ, HF_Q by exact Hi. rewrite HF_opb by lia.
rewrite !andb_true_r, !andb_assoc, orb_assoc. reflexivity.
Qed.
(* tb + 12: the halt latch *)
Lemma HF_NH : HF (SRef (tb A + 12) 0 2) =
hh || (negb hh && hleq && Nat.eqb hc (SW A - 1)) || (negb hh && negb hleq && Nat.eqb hp (SW A - 4)).
Proof.
post_fire 12. rewrite sOR_fire. cbn [existsb]. rewrite !litv_pos, orb_false_r, HF_halt.
post_fire 12. post_fire 12. rewrite !sAND_fire. cbn [forallb].
rewrite !litv_pos, !litv_neg, HF_halt, HF_LEQ, HF_AC, HF_P by lia.
rewrite !andb_true_r, !andb_assoc, orb_assoc. reflexivity.
Qed.
(* tb + 13, tb + 14: the next memory *)
Lemma HF_NM : forall m, m < SW A * A ->
HF (SRef (tb A + 14) m 0) =
(bitof A (mv (m / A)) (m mod A) && negb (negb hh && Nat.eqb hb (m / A)))
|| (bitof A hr (m mod A) && (negb hh && Nat.eqb hb (m / A))).
Proof.
intros m Hm. pose proof (Nat.mod_upper_bound m A ltac:(lia)).
pose proof (Nat.Div0.div_lt_upper_bound m A (SW A) ltac:(lia)).
post_fire 14. rewrite sOR_fire. cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite HF_KP by exact Hm.
post_fire 13. rewrite sAND_fire. cbn [forallb]. rewrite !litv_pos, andb_true_r, HF_rbit, HF_W by lia.
rewrite <- hr_bits by lia. unfold bitof. reflexivity.
Qed.
End HSem.
(* ---- the step ------------------------------------------------------------------------ *)
Lemma p3_halt : forall A p, 3 <= A -> p < SW A -> Nat.eqb ((p + 3) mod SW A) (SW A - 1) = Nat.eqb p (SW A - 4).
Proof.
intros A p HA Hp. pose proof (SW_ge A HA).
destruct (Nat.lt_ge_cases (p + 3) (SW A)) as [L|L].
- rewrite Nat.mod_small by exact L. destruct (Nat.eqb_spec (p + 3) (SW A - 1)), (Nat.eqb_spec p (SW A - 4)); lia.
- replace (p + 3) with ((p + 3 - SW A) + 1 * SW A) by lia. rewrite Nat.Div0.mod_add, Nat.mod_small by lia.
destruct (Nat.eqb_spec (p + 3 - SW A) (SW A - 1)), (Nat.eqb_spec p (SW A - 4)); lia.
Qed.
(* the step of the machine in the names of the section *)
Lemma subleq_halted : forall A s, hhalt s = true -> subleq A s = s.
Proof. intros A s H. unfold subleq. rewrite H. reflexivity. Qed.
Lemma subleq_run : forall A s, hhalt s = false ->
subleq A s = mkH (if hleq A s then hc A s else (hp s + 3) mod SW A)
(Nat.eqb (if hleq A s then hc A s else (hp s + 3) mod SW A) (SW A - 1))
(map (fun j => if Nat.eqb j (hb A s) then hr A s else memv s j) (seq 0 (SW A))).
Proof. intros A s H. unfold subleq. rewrite H. reflexivity. Qed.
Lemma memv_run : forall A s j, hhalt s = false -> j < SW A ->
memv (subleq A s) j = if Nat.eqb j (hb A s) then hr A s else memv s j.
Proof.
intros A s j H Hj. rewrite subleq_run by exact H. unfold memv at 1. cbn [hmem].
rewrite nth_map_seq by exact Hj. reflexivity.
Qed.
Theorem host_step : forall A s, 3 <= A -> hvalid A s ->
netstep (nH A) (host_units A) (host_next A) (encodeH A s) = encodeH A (subleq A s).
Proof.
intros A s HA Hv. pose proof (SW_ge A HA) as HS. pose proof Hv as (Hp & Hl & Hf).
assert (Hl' : length (hmem (subleq A s)) = SW A).
{ unfold subleq. destruct (hhalt s); [exact Hl|]. cbn [hmem]. rewrite length_map, length_seq. reflexivity. }
unfold netstep, host_next. rewrite map_map.
apply nth_ext with (d := false) (d' := false).
{ rewrite length_map, length_seq, length_encodeH by exact Hl'. reflexivity. }
intros i Hi. rewrite length_map, length_seq in Hi.
rewrite (nth_map_seq _ (fun i => run (host_units A) (nH A) (fun i0 => nth i0 (encodeH A s) false)
(idx (nH A) (hblocks A) (hout A i))) (nH A) i false Hi).
change (run (host_units A) (nH A) (fun i0 => nth i0 (encodeH A s) false) (idx (nH A) (hblocks A) (hout A i)))
with (HF A s (hout A i)).
unfold hout. destruct (Nat.ltb_spec i A) as [Hi1|Hi1].
- (* the counter *)
rewrite HF_NP by assumption. rewrite nth_encodeH_pc by exact Hi1. unfold hh.
destruct (hhalt s) eqn:Eh.
+ rewrite subleq_halted by exact Eh. cbn [negb andb orb]. rewrite andb_true_r, !orb_false_r. reflexivity.
+ rewrite subleq_run by exact Eh. cbn [hpc negb andb orb]. rewrite andb_false_r, orb_false_l.
destruct (hleq A s); cbn [negb andb orb]; rewrite ?orb_false_r; reflexivity.
- destruct (Nat.eqb_spec i A) as [->|Hi2].
+ (* the halt bit *)
rewrite HF_NH by assumption. rewrite nth_encodeH_halt. unfold hh.
destruct (hhalt s) eqn:Eh.
* rewrite subleq_halted by exact Eh. rewrite Eh. reflexivity.
* rewrite subleq_run by exact Eh. cbn [hhalt negb andb orb].
destruct (hleq A s); cbn [negb andb orb]; [rewrite orb_false_r; reflexivity|].
rewrite p3_halt by (unfold hp; assumption). reflexivity.
+ (* the memory *)
remember (i - A - 1) as m eqn:Em. assert (Hm : m < SW A * A) by (unfold nH in Hi; lia).
pose proof (Nat.mod_upper_bound m A ltac:(lia)). pose proof (Nat.Div0.div_lt_upper_bound m A (SW A) ltac:(lia)).
replace i with (A + 1 + (m / A) * A + m mod A) by (pose proof (Nat.div_mod_eq m A); lia).
rewrite HF_NM by assumption. rewrite nth_encodeH_mem by assumption. unfold hh.
destruct (hhalt s) eqn:Eh.
* rewrite subleq_halted by exact Eh. cbn [negb andb orb]. rewrite andb_true_r, andb_false_r, orb_false_r.
reflexivity.
* rewrite memv_run by assumption. rewrite (Nat.eqb_sym (m / A) (hb A s)).
destruct (Nat.eqb (hb A s) (m / A)); cbn [negb andb orb];
rewrite ?andb_true_r, ?andb_false_r, ?orb_false_r, ?orb_false_l; reflexivity.
Qed.