Download rocq/HostSem.v from phanerozoic/threshold-computers: direct link, hf CLI and curl.
- Browser
- Download file 27.3 kB
-
https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/HostSem.v
- Command line
-
hf download hf://phanerozoic/threshold-computers/rocq/HostSem.v
-
curl -L -o HostSem.v https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/HostSem.v
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. | |