(* 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 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 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.