phanerozoic's picture
Replace the two-bank machine with a K-bank ring, prove its reproduction in Rocq, and revise the paper
a9ea017
Raw History Blame Contribute Delete
70.5 kB
(* What each block of the netlist computes, from a state of the ring machine. *) From Stdlib Require Import List Bool Arith ZArith Lia. Import ListNotations. From TH Require Import TwoHead Net Gates Phys PhysWF. (* ---- the state bits of a machine state, in the order of the netlist ------------------------- *) Definition onehot (n p : nat) : list bool := map (fun x => Nat.eqb x p) (seq 0 n). Definition bankbits (al S0 : nat) (q : bank) : list bool := bq q ++ onehot S0 (bs q) ++ onehot (recw al) (bj q). Definition tapebits (L : nat) (t : tape) : list bool := td t ++ onehot L (th t). Definition encode (al K S0 L : nat) (s : st) : list bool := map (fun c => wget (win s) (c + 4)) (seq 0 (nw al)) ++ onehot K (kap s) ++ concat (map (fun k => bankbits al S0 (nth k (banks s) bank0)) (seq 0 K)) ++ concat (map (fun k => tapebits L (nth k (tapes s) tape0)) (seq 0 K)). Lemma length_onehot : forall n p, length (onehot n p) = n. Proof. intros. unfold onehot. rewrite length_map, length_seq. reflexivity. Qed. Lemma nth_onehot : forall n p x, x < n -> nth x (onehot n p) false = Nat.eqb x p. Proof. intros n p x H. unfold onehot. apply (nth_map_seq _ (fun x => Nat.eqb x p) n x false H). Qed. Lemma length_bankbits : forall al S0 q, length (bq q) = S0 * recw al -> length (bankbits al S0 q) = bsz al S0. Proof. intros. unfold bankbits, bsz, N, B. rewrite !length_app, !length_onehot. lia. Qed. Lemma length_tapebits : forall L t, length (td t) = L -> length (tapebits L t) = 2 * L. Proof. intros. unfold tapebits. rewrite length_app, length_onehot. lia. Qed. Lemma nth_concat_map_seq : forall (f : nat -> list bool) K sz k x, (forall k', k' < K -> length (f k') = sz) -> k < K -> x < sz -> nth (k * sz + x) (concat (map f (seq 0 K))) false = nth x (f k) false. Proof. intros f K sz k x Hl Hk Hx. rewrite Nat.mul_comm. rewrite (nth_concat_const _ false (map f (seq 0 K)) sz k x). - rewrite (nth_map_seq _ f K k [] Hk). reflexivity. - apply Forall_forall. intros l Hin. apply in_map_iff in Hin as (k' & <- & Hk'). apply in_seq in Hk'. apply Hl. lia. - rewrite length_map, length_seq. exact Hk. - exact Hx. Qed. Lemma length_concat_map_seq : forall (f : nat -> list bool) K sz, (forall k', k' < K -> length (f k') = sz) -> length (concat (map f (seq 0 K))) = K * sz. Proof. intros f K sz Hl. rewrite (length_concat_const _ _ sz). - rewrite length_map, length_seq. reflexivity. - apply Forall_forall. intros l Hin. apply in_map_iff in Hin as (k' & <- & Hk'). apply in_seq in Hk'. apply Hl. lia. Qed. Section Encode. Variables al K S0 L : nat. Variable s : st. Hypothesis Hv : fits al K S0 L s. Let bk k := nth k (banks s) bank0. Let tp k := nth k (tapes s) tape0. Lemma length_win : length (win s) = W al. Proof. destruct Hv as (H & _). exact H. Qed. Lemma bank_ok : forall k, k < K -> length (bq (bk k)) = S0 * recw al /\ bs (bk k) < S0 /\ bj (bk k) < recw al. Proof. intros k Hk. destruct Hv as (_ & _ & _ & _ & H & _). apply H. exact Hk. Qed. Lemma tape_ok : forall k, k < K -> length (td (tp k)) = L /\ th (tp k) < L. Proof. intros k Hk. destruct Hv as (_ & _ & _ & _ & _ & H). apply H. exact Hk. Qed. Lemma len_banks : length (concat (map (fun k => bankbits al S0 (nth k (banks s) bank0)) (seq 0 K))) = K * bsz al S0. Proof. apply length_concat_map_seq. intros k Hk. apply length_bankbits. apply (bank_ok k Hk). Qed. Lemma len_tapes : length (concat (map (fun k => tapebits L (nth k (tapes s) tape0)) (seq 0 K))) = K * (2 * L). Proof. apply length_concat_map_seq. intros k Hk. apply length_tapebits. apply (tape_ok k Hk). Qed. Lemma length_encode : length (encode al K S0 L s) = nst al K S0 L. Proof. unfold encode, nst. rewrite !length_app, length_map, length_seq, length_onehot, len_banks, len_tapes. lia. Qed. Lemma X_win : forall c, c < nw al -> nth c (encode al K S0 L s) false = wget (win s) (c + 4). Proof. intros c Hc. unfold encode. rewrite app_nth1 by (rewrite length_map, length_seq; exact Hc). exact (nth_map_seq _ (fun c => wget (win s) (c + 4)) (nw al) c false Hc). Qed. Lemma X_kap : forall k, k < K -> nth (okap al + k) (encode al K S0 L s) false = Nat.eqb k (kap s). Proof. intros k Hk. unfold encode, okap. rewrite app_nth2 by (rewrite length_map, length_seq; lia). rewrite length_map, length_seq. rewrite app_nth1 by (rewrite length_onehot; lia). replace (nw al + k - nw al) with k by lia. apply nth_onehot. exact Hk. Qed. Lemma X_bank : forall k, k < K -> (forall p, p < N al S0 -> nth (obank al K S0 k + p) (encode al K S0 L s) false = nth p (bq (bk k)) false) /\ (forall x, x < S0 -> nth (obank al K S0 k + N al S0 + x) (encode al K S0 L s) false = Nat.eqb x (bs (bk k))) /\ (forall x, x < B al -> nth (obank al K S0 k + N al S0 + S0 + x) (encode al K S0 L s) false = Nat.eqb x (bj (bk k))). Proof. intros k Hk. destruct (bank_ok k Hk) as (Hq & _ & _). assert (G : forall x, x < bsz al S0 -> nth (obank al K S0 k + x) (encode al K S0 L s) false = nth x (bankbits al S0 (bk k)) false). { intros x Hx. unfold encode, obank. rewrite app_nth2 by (rewrite length_map, length_seq; lia). rewrite length_map, length_seq. rewrite app_nth2 by (rewrite length_onehot; lia). rewrite length_onehot. assert (Hb : k * bsz al S0 + bsz al S0 <= K * bsz al S0) by nia. rewrite app_nth1 by (rewrite len_banks; lia). replace (nw al + K + k * bsz al S0 + x - nw al - K) with (k * bsz al S0 + x) by lia. apply (nth_concat_map_seq (fun k => bankbits al S0 (nth k (banks s) bank0)) K (bsz al S0) k x); auto. intros k' Hk'. apply length_bankbits. apply (bank_ok k' Hk'). } unfold bsz, N, B in *. repeat split. - intros p Hp. rewrite G by lia. unfold bankbits. rewrite app_nth1 by lia. reflexivity. - intros x Hx. replace (obank al K S0 k + S0 * recw al + x) with (obank al K S0 k + (S0 * recw al + x)) by lia. rewrite G by lia. unfold bankbits. rewrite app_nth2 by lia. rewrite app_nth1 by (rewrite length_onehot; lia). rewrite Hq. replace (S0 * recw al + x - S0 * recw al) with x by lia. apply nth_onehot. exact Hx. - intros x Hx. replace (obank al K S0 k + S0 * recw al + S0 + x) with (obank al K S0 k + (S0 * recw al + S0 + x)) by lia. rewrite G by lia. unfold bankbits. rewrite app_nth2 by lia. rewrite app_nth2 by (rewrite Hq, length_onehot; lia). rewrite Hq, length_onehot. replace (S0 * recw al + S0 + x - S0 * recw al - S0) with x by lia. apply nth_onehot. exact Hx. Qed. Lemma X_tape : forall k, k < K -> (forall i, i < L -> nth (otape al K S0 L k + i) (encode al K S0 L s) false = nth i (td (tp k)) false) /\ (forall i, i < L -> nth (otape al K S0 L k + L + i) (encode al K S0 L s) false = Nat.eqb i (th (tp k))). Proof. intros k Hk. destruct (tape_ok k Hk) as (Hd & _). assert (G : forall x, x < 2 * L -> nth (otape al K S0 L k + x) (encode al K S0 L s) false = nth x (tapebits L (tp k)) false). { intros x Hx. unfold encode, otape. rewrite app_nth2 by (rewrite length_map, length_seq; lia). rewrite length_map, length_seq. rewrite app_nth2 by (rewrite length_onehot; lia). rewrite length_onehot. rewrite app_nth2 by (rewrite len_banks; lia). rewrite len_banks. replace (nw al + K + K * bsz al S0 + k * (2 * L) + x - nw al - K - K * bsz al S0) with (k * (2 * L) + x) by lia. apply (nth_concat_map_seq (fun k => tapebits L (nth k (tapes s) tape0)) K (2 * L) k x); auto. intros k' Hk'. apply length_tapebits. apply (tape_ok k' Hk'). } split. - intros i Hi. rewrite G by lia. unfold tapebits. rewrite app_nth1 by lia. reflexivity. - intros i Hi. replace (otape al K S0 L k + L + i) with (otape al K S0 L k + (L + i)) by lia. rewrite G by lia. unfold tapebits. rewrite app_nth2 by lia. rewrite Hd. replace (L + i - L) with i by lia. apply nth_onehot. exact Hi. Qed. End Encode. (* ---- arithmetic of the rings ------------------------------------------------------------ *) Lemma succ_mod_lt : forall n x, 1 <= n -> x < n -> succ_mod n x < n. Proof. intros n x Hn Hx. unfold succ_mod. destruct (Nat.eqb_spec (S x) n); lia. Qed. (* the cell before x on a ring of n cells holds pos exactly when x is the cell after pos *) Lemma prev_eq : forall n x pos, x < n -> pos < n -> Nat.eqb ((x + n - 1) mod n) pos = Nat.eqb x (succ_mod n pos). Proof. intros n x pos Hx Hp. unfold succ_mod. destruct x as [|x]. - rewrite Nat.add_0_l, Nat.mod_small by lia. destruct (Nat.eqb_spec (n - 1) pos), (Nat.eqb_spec (S pos) n); cbn; try reflexivity; lia. - replace (S x + n - 1) with (x + 1 * n) by lia. rewrite Nat.Div0.mod_add, Nat.mod_small by lia. destruct (Nat.eqb_spec x pos), (Nat.eqb_spec (S pos) n), (Nat.eqb_spec (S x) (S pos)); cbn; try reflexivity; try lia. Qed. (* the one-hot pick: a disjunction over a track holding one 1 *) Lemma existsb_pick : forall (g : nat -> bool) c n, existsb (fun a => Nat.eqb a c && g a) (seq 0 n) = if c <? n then g c else false. Proof. intros g c n. assert (G : forall m, existsb (fun a => Nat.eqb a c && g a) (seq m n) = if (m <=? c) && (c <? m + n) then g c else false). { induction n as [|n IH]; intro m; cbn [seq existsb]. - destruct (Nat.leb_spec m c), (Nat.ltb_spec c (m + 0)); cbn [andb]; try reflexivity; lia. - rewrite IH. destruct (Nat.eqb_spec m c) as [E|E]. + subst m. rewrite Nat.leb_refl. replace (c <? c + S n) with true by (symmetry; apply Nat.ltb_lt; lia). replace (S c <=? c) with false by (symmetry; apply Nat.leb_gt; lia). cbn [andb orb]. destruct (g c); reflexivity. + cbn [andb orb]. destruct (Nat.leb_spec m c), (Nat.leb_spec (S m) c), (Nat.ltb_spec c (S m + n)), (Nat.ltb_spec c (m + S n)); cbn [andb]; try reflexivity; lia. } rewrite G, Nat.add_0_l. reflexivity. Qed. Lemma existsb_ext_seq : forall (f g : nat -> bool) n, (forall a, a < n -> f a = g a) -> existsb f (seq 0 n) = existsb g (seq 0 n). Proof. intros f g n H. assert (G : forall m, (forall a, m <= a < m + n -> f a = g a) -> existsb f (seq m n) = existsb g (seq m n)). { clear H. induction n as [|n IH]; intros m Hm; [reflexivity|]. cbn [seq existsb]. rewrite Hm by lia. rewrite IH by (intros a Ha; apply Hm; lia). reflexivity. } apply G. intros a Ha. apply H. lia. Qed. Lemma existsb_pick_at : forall (g : nat -> bool) c n m, existsb (fun a => Nat.eqb c a && g a) (seq m n) = if (m <=? c) && (c <? m + n) then g c else false. Proof. intros g c n. induction n as [|n IH]; intro m; cbn [seq existsb]. - destruct (Nat.leb_spec m c), (Nat.ltb_spec c (m + 0)); cbn [andb]; try reflexivity; lia. - rewrite IH. destruct (Nat.eqb_spec c m) as [E|E]. + subst c. rewrite Nat.leb_refl. replace (m <? m + S n) with true by (symmetry; apply Nat.ltb_lt; lia). replace (S m <=? m) with false by (symmetry; apply Nat.leb_gt; lia). cbn [andb orb]. destruct (g m); reflexivity. + cbn [andb orb]. destruct (Nat.leb_spec m c), (Nat.leb_spec (S m) c), (Nat.ltb_spec c (S m + n)), (Nat.ltb_spec c (m + S n)); cbn [andb]; try reflexivity; lia. Qed. Lemma existsb_ext_in : forall (A : Type) (f g : A -> bool) l, (forall x, In x l -> f x = g x) -> existsb f l = existsb g l. Proof. intros A f g l H. induction l as [|x l IH]; [reflexivity|]. cbn [existsb]. rewrite H, IH; [reflexivity| |left; reflexivity]. intros y Hy. apply H. right. exact Hy. Qed. Lemma existsb_map' : forall (A B : Type) (f : B -> bool) (g : A -> B) l, existsb f (map g l) = existsb (fun x => f (g x)) l. Proof. intros A B f g l. induction l as [|x l IH]; [reflexivity|]. cbn [map existsb]. rewrite IH. reflexivity. Qed. Lemma forallb_map' : forall (A B : Type) (f : B -> bool) (g : A -> B) l, forallb f (map g l) = forallb (fun x => f (g x)) l. Proof. intros A B f g l. induction l as [|x l IH]; [reflexivity|]. cbn [map forallb]. rewrite IH. reflexivity. Qed. Lemma forallb_ext_in : forall (A : Type) (f g : A -> bool) l, (forall x, In x l -> f x = g x) -> forallb f l = forallb g l. Proof. intros A f g l H. induction l as [|x l IH]; [reflexivity|]. cbn [forallb]. rewrite H, IH; [reflexivity| |left; reflexivity]. intros y Hy. apply H. right. exact Hy. Qed. Lemma divmod_pair : forall k x n, x < n -> (k * n + x) / n = k /\ (k * n + x) mod n = x. Proof. intros k x n Hx. split. - rewrite Nat.div_add_l by lia. rewrite Nat.div_small by exact Hx. lia. - rewrite Nat.add_comm, Nat.Div0.mod_add. apply Nat.mod_small. exact Hx. Qed. (* ---- addresses of al bits, most significant first ---------------------------------- *) Lemma bits2nat_acc_eq : forall l acc, bits2nat_acc acc l = acc * 2 ^ length l + bits2nat l. Proof. unfold bits2nat. induction l as [|b l IH]; intro acc; cbn [bits2nat_acc length Nat.pow]. - lia. - rewrite (IH (2 * acc + (if b then 1 else 0))), (IH (2 * 0 + (if b then 1 else 0))). destruct b; nia. Qed. Lemma bits2nat_cons : forall b l, bits2nat (b :: l) = (if b then 2 ^ length l else 0) + bits2nat l. Proof. intros b l. unfold bits2nat at 1. cbn [bits2nat_acc]. rewrite bits2nat_acc_eq. destruct b; lia. Qed. Lemma bits2nat_lt : forall l, bits2nat l < 2 ^ length l. Proof. induction l as [|b l IH]; [cbn; lia|]. rewrite bits2nat_cons. cbn [length Nat.pow]. destruct b; lia. Qed. Lemma testbit_bits2nat : forall l t, t < length l -> Nat.testbit (bits2nat l) (length l - 1 - t) = nth t l false. Proof. induction l as [|b l IH]; intros t Ht; cbn [length] in Ht; [lia|]. rewrite bits2nat_cons. cbn [length]. pose proof (bits2nat_lt l) as Hlt. destruct t as [|t]. - cbn [nth]. replace (S (length l) - 1 - 0) with (length l) by lia. apply Nat.b2n_inj. rewrite Nat.testbit_spec'. destruct b. + replace (2 ^ length l + bits2nat l) with (1 * 2 ^ length l + bits2nat l) by lia. rewrite Nat.div_add_l by (apply Nat.pow_nonzero; lia). rewrite Nat.div_small by exact Hlt. reflexivity. + rewrite Nat.add_0_l, Nat.div_small by exact Hlt. reflexivity. - cbn [nth]. replace (S (length l) - 1 - S t) with (length l - 1 - t) by lia. rewrite <- (Nat.mod_pow2_bits_low _ (length l)) by lia. replace ((if b then 2 ^ length l else 0) + bits2nat l) with (bits2nat l + (if b then 1 else 0) * 2 ^ length l) by (destruct b; lia). rewrite Nat.Div0.mod_add, Nat.mod_small by exact Hlt. apply IH. lia. Qed. Lemma bits_eq_nat : forall x y w, x < 2 ^ w -> y < 2 ^ w -> (forall i, i < w -> Nat.testbit x i = Nat.testbit y i) -> x = y. Proof. intros x y w Hx Hy H. apply Nat.bits_inj. intro n. destruct (Nat.lt_ge_cases n w) as [Hn|Hn]; [apply H; exact Hn|]. assert (Z0 : forall z, z < 2 ^ w -> Nat.testbit z n = false). { intros z Hz. apply Bool.not_true_is_false. intro E. pose proof (Nat.testbit_spec' z n) as S. rewrite E in S. cbn [Nat.b2n] in S. rewrite Nat.div_small in S; [cbn in S; discriminate|]. pose proof (Nat.pow_le_mono_r 2 w n ltac:(lia) Hn). lia. } rewrite !Z0 by assumption. reflexivity. Qed. Lemma dec_okA : forall al f a, length f = al -> a < 2 ^ al -> forallb (fun t => Bool.eqb (nth t f false) (bitsof al a t)) (seq 0 al) = Nat.eqb (bits2nat f) a. Proof. intros al f a Hf Ha. unfold bitsof. destruct (forallb (fun t => Bool.eqb (nth t f false) (Nat.testbit a (al - 1 - t))) (seq 0 al)) eqn:E; symmetry. - apply Nat.eqb_eq. apply (bits_eq_nat _ _ al); [rewrite <- Hf; apply bits2nat_lt | exact Ha |]. intros i Hi. rewrite forallb_forall in E. specialize (E (al - 1 - i) ltac:(apply in_seq; lia)). apply Bool.eqb_prop in E. replace (al - 1 - (al - 1 - i)) with i in E by lia. rewrite <- E. pose proof (testbit_bits2nat f (al - 1 - i) ltac:(lia)) as T. rewrite Hf in T. replace (al - 1 - (al - 1 - i)) with i in T by lia. exact T. - apply Nat.eqb_neq. intro Eq. subst a. assert (Et : forallb (fun t => Bool.eqb (nth t f false) (Nat.testbit (bits2nat f) (al - 1 - t))) (seq 0 al) = true). { apply forallb_forall. intros t Ht. apply in_seq in Ht. pose proof (testbit_bits2nat f t ltac:(lia)) as T. rewrite Hf in T. rewrite T. apply eqb_reflx. } congruence. Qed. (* ---- the counts and sizes of the blocks ------------------------------------------------------ *) Definition cnts (al K S0 L b : nat) : nat := match b with | 0 => 1 | 1 => K * B al | 2 => B al | 3 => K | 4 => K | 5 => 3 | 6 | 7 | 8 | 9 | 11 => W al | 10 | 12 => 1 | 13 | 14 | 15 | 16 => 2 | 17 => 5 | 18 | 19 => 1 | 20 => 5 | 21 => 1 | 22 => nw al | 23 | 24 => K | 25 => K * N al S0 | 26 => K | 27 => K * S0 | 28 => K * B al | 29 => K | _ => K * L end. Definition sizes (al K S0 L b : nat) : nat := match b with | 0 => 1 | 1 => S0 + 1 | 2 => K + 1 | 3 => L + 1 | 4 => B al + 1 | 5 => K + 1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 => 1 | 18 => 4 | 19 => 5 | 20 | 21 => 1 | 22 | 23 => 3 | 24 => 2 | 25 | 26 | 27 | 28 => 4 | 29 => 8 | _ => 4 end. Lemma blk_cs : forall al K S0 L b, b < 32 -> bcount (nth b (phys_blocks al K S0 L) blk0) = cnts al K S0 L b /\ bsize (nth b (phys_blocks al K S0 L) blk0) = sizes al K S0 L b. Proof. intros al K S0 L b Hb. do 32 (destruct b as [|b]; [split; reflexivity|]). lia. Qed. (* ---- the netlist on a state of the machine ---------------------------------------------------- *) Section Sem. Variables (al K S0 L : nat) (s : st). Hypotheses (Hal : 4 <= al) (HK : 2 <= K) (HS : 1 <= S0) (HL : 1 <= L) (Hv : fits al K S0 L s). Let HW : 16 <= W al := W_ge al Hal. Let HB : 8 <= B al := ltac:(unfold B, recw; lia). Definition X (i : nat) : bool := nth i (encode al K S0 L s) false. Definition F (x : sref) : bool := run (phys_units al K S0 L) (nst al K S0 L) X (idx (nst al K S0 L) (phys_blocks al K S0 L) x). Lemma F_in : forall i, i < nst al K S0 L -> F (SIn i) = X i. Proof. intros i H. unfold F, phys_units. apply net_in. exact H. Qed. Lemma F_unit : forall b j r, b < 32 -> j < cnts al K S0 L b -> r < sizes al K S0 L b -> F (SRef b j r) = sfire' (sunit (phys_blocks al K S0 L) b j r) F. Proof. intros b j r Hb Hj Hr. destruct (blk_cs al K S0 L b Hb) as [Hc Hz]. unfold F, phys_units. apply net_unit. - apply phys_wf; lia. - rewrite phys_length. exact Hb. - rewrite Hc. exact Hj. - rewrite Hz. exact Hr. Qed. Lemma F_and : forall b j r ls, b < 32 -> j < cnts al K S0 L b -> r < sizes al K S0 L b -> sunit (phys_blocks al K S0 L) b j r = sAND ls -> F (SRef b j r) = forallb (litv F) ls. Proof. intros b j r ls Hb Hj Hr E. rewrite F_unit, E by assumption. apply sAND_fire. Qed. Lemma F_or : forall b j r ls, b < 32 -> j < cnts al K S0 L b -> r < sizes al K S0 L b -> sunit (phys_blocks al K S0 L) b j r = sOR ls -> F (SRef b j r) = existsb (litv F) ls. Proof. intros b j r ls Hb Hj Hr E. rewrite F_unit, E by assumption. apply sOR_fire. Qed. Lemma F_mux : forall b j r0 sel a c, b < 32 -> j < cnts al K S0 L b -> S (S r0) < sizes al K S0 L b -> sunit (phys_blocks al K S0 L) b j r0 = sAND [(sel, true); (a, true)] -> sunit (phys_blocks al K S0 L) b j (S r0) = sAND [(sel, false); (c, true)] -> sunit (phys_blocks al K S0 L) b j (S (S r0)) = sOR [(SRef b j r0, true); (SRef b j (S r0), true)] -> F (SRef b j (S (S r0))) = if F sel then F a else F c. Proof. intros b j r0 sel a c Hb Hj Hr E0 E1 E2. rewrite (F_or b j (S (S r0)) _ Hb Hj Hr E2). cbn [existsb]. rewrite !litv_pos. rewrite (F_and b j r0 _ Hb Hj ltac:(lia) E0), (F_and b j (S r0) _ Hb Hj ltac:(lia) E1). cbn [forallb]. rewrite !litv_pos, litv_neg. destruct (F sel), (F a), (F c); reflexivity. Qed. (* ---- the state bits ----------------------------------------------------------------------- *) Definition kk : nat := kap s. Definition ii : nat := succ_mod K kk. Definition bnk (k : nat) : bank := nth k (banks s) bank0. Definition tpe (k : nat) : tape := nth k (tapes s) tape0. Lemma kk_lt : kk < K. Proof. destruct Hv as (_ & H & _). exact H. Qed. Lemma ii_lt : ii < K. Proof. apply succ_mod_lt; [lia | exact kk_lt]. Qed. Lemma ii_kk : ii <> kk. Proof. pose proof kk_lt. unfold ii, succ_mod. destruct (Nat.eqb_spec (S kk) K); lia. Qed. Lemma bnk_ok : forall k, k < K -> length (bq (bnk k)) = N al S0 /\ bs (bnk k) < S0 /\ bj (bnk k) < B al. Proof. intros k Hk. exact (bank_ok al K S0 L s Hv k Hk). Qed. Lemma tpe_ok : forall k, k < K -> length (td (tpe k)) = L /\ th (tpe k) < L. Proof. intros k Hk. exact (tape_ok al K S0 L s Hv k Hk). Qed. Lemma F_act : forall k, k < K -> F (act al K k) = Nat.eqb k kk. Proof. intros k Hk. unfold act. rewrite Nat.mod_small by exact Hk. rewrite F_in by (apply (refs_lt al K S0 L k 0 Hk)). unfold X. rewrite X_kap by assumption. reflexivity. Qed. Lemma F_idl : forall k, k < K -> F (idl al K k) = Nat.eqb k ii. Proof. intros k Hk. unfold idl. pose proof (Nat.mod_upper_bound (k + K - 1) K ltac:(lia)) as Hm. rewrite F_in by (apply (refs_lt al K S0 L _ 0 Hm)). unfold X. rewrite X_kap by assumption. apply prev_eq; [exact Hk | exact kk_lt]. Qed. Lemma F_q : forall k p, k < K -> p < N al S0 -> F (qref al K S0 k p) = nth p (bq (bnk k)) false. Proof. intros k p Hk Hp. unfold qref. rewrite F_in by (apply (refs_lt al K S0 L k p Hk); exact Hp). unfold X. destruct (X_bank al K S0 L s Hv k Hk) as (H & _). apply H. exact Hp. Qed. Lemma F_h : forall k x, k < K -> x < S0 -> F (href al K S0 k x) = Nat.eqb x (bs (bnk k)). Proof. intros k x Hk Hx. unfold href. rewrite F_in by (apply (refs_lt al K S0 L k x Hk); exact Hx). unfold X. destruct (X_bank al K S0 L s Hv k Hk) as (_ & H & _). apply H. exact Hx. Qed. Lemma F_j : forall k x, k < K -> x < B al -> F (jref al K S0 k x) = Nat.eqb x (bj (bnk k)). Proof. intros k x Hk Hx. unfold jref. rewrite F_in by (apply (refs_lt al K S0 L k x Hk); exact Hx). unfold X. destruct (X_bank al K S0 L s Hv k Hk) as (_ & _ & H). apply H. exact Hx. Qed. Lemma F_d : forall k i, k < K -> i < L -> F (dref al K S0 L k i) = nth i (td (tpe k)) false. Proof. intros k i Hk Hi. unfold dref. rewrite F_in by (apply (refs_lt al K S0 L k i Hk); exact Hi). unfold X. destruct (X_tape al K S0 L s Hv k Hk) as (H & _). apply H. exact Hi. Qed. Lemma F_t : forall k i, k < K -> i < L -> F (tref al K S0 L k i) = Nat.eqb i (th (tpe k)). Proof. intros k i Hk Hi. unfold tref. rewrite F_in by (apply (refs_lt al K S0 L k i Hk); exact Hi). unfold X. destruct (X_tape al K S0 L s Hv k Hk) as (_ & H). apply H. exact Hi. Qed. Lemma F_w : forall c, c < nw al -> F (SIn c) = wget (win s) (c + 4). Proof. intros c Hc. rewrite F_in by (unfold nst; lia). unfold X. apply X_win; assumption. Qed. (* ---- blocks 0 to 5: the record at the active head and the cells under the heads --------------- *) Lemma F_zero : F (zero) = false. Proof. unfold zero. rewrite (F_or 0 0 0 []) by (reflexivity || (cbn; lia)). reflexivity. Qed. Lemma F_rec : forall k j, k < K -> j < B al -> F (SRef 1 (k * B al + j) S0) = nth (bs (bnk k) * B al + j) (bq (bnk k)) false. Proof. intros k j Hk Hj. destruct (divmod_pair k j (B al) Hj) as [Dq Dm]. destruct (bnk_ok k Hk) as (Hq & Hs & _). rewrite (F_or 1 (k * B al + j) S0 (map (fun s0 => (SRef 1 (k * B al + j) s0, true)) (seq 0 S0))) by first [lia | cbn [cnts sizes]; nia | apply (nth_map_seq_last (fun s0 => sAND [(href al K S0 ((k * B al + j) / B al) s0, true); (qref al K S0 ((k * B al + j) / B al) (s0 * B al + (k * B al + j) mod B al), true)]))]. rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun s0 => Nat.eqb s0 (bs (bnk k)) && nth (s0 * B al + j) (bq (bnk k)) false)). - rewrite existsb_pick. replace (bs (bnk k) <? S0) with true by (symmetry; apply Nat.ltb_lt; exact Hs). reflexivity. - intros a Ha. rewrite litv_pos. rewrite (F_and 1 (k * B al + j) a [(href al K S0 ((k * B al + j) / B al) a, true); (qref al K S0 ((k * B al + j) / B al) (a * B al + (k * B al + j) mod B al), true)]) by first [lia | cbn [cnts sizes]; nia | apply (nth_map_seq_app (fun s0 => sAND [(href al K S0 ((k * B al + j) / B al) s0, true); (qref al K S0 ((k * B al + j) / B al) (s0 * B al + (k * B al + j) mod B al), true)])); exact Ha]. cbn [forallb]. rewrite !litv_pos, andb_true_r. rewrite Dq, Dm. rewrite F_h, F_q by (try exact Hk; try exact Ha; unfold N; nia). reflexivity. Qed. Definition qa : list bool := slot al (bnk kk). Lemma length_qa : length qa = B al. Proof. destruct (bnk_ok kk kk_lt) as (Hq & Hs & _). unfold qa, slot. rewrite length_firstn, length_skipn, Hq. unfold N, B in *. nia. Qed. Lemma nth_qa : forall j, j < B al -> nth j qa false = nth (bs (bnk kk) * B al + j) (bq (bnk kk)) false. Proof. intros j Hj. unfold qa, slot. rewrite nth_firstn. fold (B al). destruct (Nat.ltb_spec j (B al)); [|lia]. rewrite nth_skipn. rewrite Nat.add_comm. reflexivity. Qed. Lemma F_fld : forall j, j < B al -> F (fld K j) = nth j qa false. Proof. intros j Hj. unfold fld. pose proof kk_lt as Hkk. rewrite (F_or 2 j K (map (fun k => (SRef 2 j k, true)) (seq 0 K))) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_last (fun k => sAND [(act al K k, true); (SRef 1 (k * B al + j) S0, true)]))]. rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun k => Nat.eqb k kk && nth (bs (bnk k) * B al + j) (bq (bnk k)) false)). - rewrite existsb_pick. replace (kk <? K) with true by (symmetry; apply Nat.ltb_lt; exact Hkk). rewrite nth_qa by exact Hj. reflexivity. - intros k Hk. rewrite litv_pos. rewrite (F_and 2 j k [(act al K k, true); (SRef 1 (k * B al + j) S0, true)]) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_app (fun k => sAND [(act al K k, true); (SRef 1 (k * B al + j) S0, true)])); exact Hk]. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_act, F_rec by assumption. reflexivity. Qed. Lemma F_tc : forall k, k < K -> F (SRef 3 k L) = tget (tpe k). Proof. intros k Hk. destruct (tpe_ok k Hk) as (Hd & Ht). rewrite (F_or 3 k L (map (fun i => (SRef 3 k i, true)) (seq 0 L))) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_last (fun i => sAND [(tref al K S0 L k i, true); (dref al K S0 L k i, true)]))]. rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun i => Nat.eqb i (th (tpe k)) && nth i (td (tpe k)) false)). - rewrite existsb_pick. replace (th (tpe k) <? L) with true by (symmetry; apply Nat.ltb_lt; exact Ht). reflexivity. - intros i Hi. rewrite litv_pos. rewrite (F_and 3 k i [(tref al K S0 L k i, true); (dref al K S0 L k i, true)]) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_app (fun i => sAND [(tref al K S0 L k i, true); (dref al K S0 L k i, true)])); exact Hi]. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_t, F_d by assumption. reflexivity. Qed. Lemma F_ac : forall k, k < K -> F (SRef 4 k (B al)) = bget al (bnk k). Proof. intros k Hk. destruct (bnk_ok k Hk) as (Hq & Hs & Hj). rewrite (F_or 4 k (B al) (map (fun j => (SRef 4 k j, true)) (seq 0 (B al)))) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_last (fun j => sAND [(jref al K S0 k j, true); (SRef 1 (k * B al + j) S0, true)]))]. rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun j => Nat.eqb j (bj (bnk k)) && nth (bs (bnk k) * B al + j) (bq (bnk k)) false)). - rewrite existsb_pick. replace (bj (bnk k) <? B al) with true by (symmetry; apply Nat.ltb_lt; exact Hj). reflexivity. - intros j Hj'. rewrite litv_pos. rewrite (F_and 4 k j [(jref al K S0 k j, true); (SRef 1 (k * B al + j) S0, true)]) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_app (fun j => sAND [(jref al K S0 k j, true); (SRef 1 (k * B al + j) S0, true)])); exact Hj']. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_j, F_rec by assumption. reflexivity. Qed. Lemma F_head : F (SRef 5 0 K) = tget (tpe kk) /\ F (SRef 5 1 K) = bget al (bnk ii) /\ F (SRef 5 2 K) = tget (tpe ii). Proof. pose proof kk_lt as Hkk. pose proof ii_lt as Hii. assert (G : forall m (sel : nat -> sref) (val : nat -> bool) c, m < 3 -> c < K -> (forall k, k < K -> headsel al K L m k = sAND [(sel k, true); (SRef (if Nat.eqb m 1 then 4 else 3) k (if Nat.eqb m 1 then B al else L), true)]) -> (forall k, k < K -> F (sel k) = Nat.eqb k c) -> (forall k, k < K -> F (SRef (if Nat.eqb m 1 then 4 else 3) k (if Nat.eqb m 1 then B al else L)) = val k) -> F (SRef 5 m K) = val c). { intros m sel val c Hm Hc Hsel Hs Hval. rewrite (F_or 5 m K (map (fun k => (SRef 5 m k, true)) (seq 0 K))) by first [lia | cbn [cnts sizes]; lia | apply (nth_map_seq_last (headsel al K L m))]. rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun k => Nat.eqb k c && val k)). - rewrite existsb_pick. replace (c <? K) with true by (symmetry; apply Nat.ltb_lt; exact Hc). reflexivity. - intros k Hk. rewrite litv_pos. rewrite (F_and 5 m k _ ltac:(lia) ltac:(cbn [cnts]; lia) ltac:(cbn [sizes]; lia) ltac:(unfold sunit; change (bshape (nth 5 (phys_blocks al K S0 L) blk0) m) with (map (headsel al K L m) (seq 0 K) ++ [sOR (map (fun k => (SRef 5 m k, true)) (seq 0 K))]); rewrite nth_map_seq_app by exact Hk; apply Hsel; exact Hk)). cbn [forallb]. rewrite !litv_pos, andb_true_r, Hs, Hval by exact Hk. reflexivity. } split; [|split]. - apply (G 0 (act al K) (fun k => tget (tpe k)) kk); try lia. + intros k Hk. reflexivity. + exact F_act. + intros k Hk. cbn [Nat.eqb]. apply F_tc. exact Hk. - apply (G 1 (idl al K) (fun k => bget al (bnk k)) ii); try lia. + intros k Hk. reflexivity. + exact F_idl. + intros k Hk. cbn [Nat.eqb]. apply F_ac. exact Hk. - apply (G 2 (idl al K) (fun k => tget (tpe k)) ii); try lia. + intros k Hk. reflexivity. + exact F_idl. + intros k Hk. cbn [Nat.eqb]. apply F_tc. exact Hk. Qed. (* ---- blocks 6 to 12: the three addresses and the two operands --------------------------------- *) Definition field (o : nat) : list bool := firstn al (skipn o qa). Lemma length_field : forall o, o + al <= B al -> length (field o) = al. Proof. intros o Ho. unfold field. rewrite length_firstn, length_skipn, length_qa. lia. Qed. Lemma nth_field : forall o t, t < al -> nth t (field o) false = nth (o + t) qa false. Proof. intros o t Ht. unfold field. rewrite nth_firstn. destruct (Nat.ltb_spec t al); [|lia]. apply nth_skipn. Qed. Lemma F_dec : forall b o a, (b = 6 /\ o = 8) \/ (b = 7 /\ o = 8 + al) \/ (b = 8 /\ o = 8 + 2 * al) -> a < W al -> F (SRef b a 0) = Nat.eqb (bits2nat (field o)) a. Proof. intros b o a Hbo Ha. assert (Hs : sunit (phys_blocks al K S0 L) b a 0 = sAND (map (fun t => (fld K (o + t), bitsof al a t)) (seq 0 al))) by (destruct Hbo as [[-> ->]|[[-> ->]|[-> ->]]]; reflexivity). assert (Hb : b < 32 /\ a < cnts al K S0 L b /\ 0 < sizes al K S0 L b) by (destruct Hbo as [[-> ->]|[[-> ->]|[-> ->]]]; cbn [cnts sizes]; lia). destruct Hb as (Hb1 & Hb2 & Hb3). rewrite (F_and b a 0 _ Hb1 Hb2 Hb3 Hs). rewrite forallb_map'. rewrite <- (dec_okA al (field o) a) by (try apply length_field; destruct Hbo as [[-> ->]|[[-> ->]|[-> ->]]]; unfold W, B, recw in *; lia). apply forallb_ext_in. intros t Ht. apply in_seq in Ht. unfold litv. cbn [fst snd]. rewrite F_fld by (destruct Hbo as [[-> ->]|[[-> ->]|[-> ->]]]; unfold B, recw; lia). rewrite nth_field by lia. reflexivity. Qed. Lemma F_cellref : forall a, a < W al -> F (cellref K a) = cellof al K s a. Proof. intros a Ha. destruct F_head as (H1 & H2 & H3). unfold cellref, cellof. fold kk. fold ii. destruct (Nat.eqb_spec a 0) as [->|E0]; [exact F_zero|]. destruct (Nat.eqb_spec a 1) as [->|E1]; [exact H1|]. destruct (Nat.eqb_spec a 2) as [->|E2]; [exact H2|]. destruct (Nat.eqb_spec a 3) as [->|E3]; [exact H3|]. cbn [orb]. rewrite F_w by (unfold nw; lia). unfold SINK, RD, ARM, CPY. rewrite (proj2 (Nat.eqb_neq a 0) E0), (proj2 (Nat.eqb_neq a 1) E1), (proj2 (Nat.eqb_neq a 2) E2), (proj2 (Nat.eqb_neq a 3) E3). f_equal. lia. Qed. Definition fa (o : nat) : nat := bits2nat (field o). Lemma fa_lt : forall o, o + al <= B al -> fa o < W al. Proof. intros o Ho. unfold fa, W. rewrite <- (length_field o Ho). apply bits2nat_lt. Qed. Lemma F_xs : forall i, i < 2 -> F (xsref i) = cellof al K s (fa (8 + al * i)). Proof. intros i Hi. assert (G : forall bt bd bdec o, (bt = 10 /\ bd = 9 /\ bdec = 6 /\ o = 8) \/ (bt = 12 /\ bd = 11 /\ bdec = 7 /\ o = 8 + al) -> F (SRef bt 0 0) = cellof al K s (fa o)). { intros bt bd bdec o Hsel. assert (Hlt : fa o < W al) by (apply fa_lt; destruct Hsel as [(_ & _ & _ & ->)|(_ & _ & _ & ->)]; unfold B, recw; lia). rewrite (F_or bt 0 0 (map (fun a => (SRef bd a 0, true)) (seq 0 (W al)))) by (destruct Hsel as [(-> & -> & _)|(-> & -> & _)]; first [lia | cbn [cnts sizes]; lia | reflexivity]). rewrite existsb_map'. rewrite (existsb_ext_seq _ (fun a => Nat.eqb a (fa o) && cellof al K s a)). - rewrite existsb_pick. replace (fa o <? W al) with true by (symmetry; apply Nat.ltb_lt; exact Hlt). reflexivity. - intros a Ha. rewrite litv_pos. assert (Hd : F (SRef bdec a 0) = Nat.eqb (fa o) a). { apply F_dec; [destruct Hsel as [(_ & _ & -> & ->)|(_ & _ & -> & ->)]; [left|right; left]; split; reflexivity | exact Ha]. } rewrite (F_and bd a 0 [(SRef bdec a 0, true); (cellref K a, true)]) by (destruct Hsel as [(-> & -> & -> & _)|(-> & -> & -> & _)]; first [lia | cbn [cnts sizes]; lia | reflexivity]). cbn [forallb]. rewrite !litv_pos, andb_true_r, Hd, F_cellref by exact Ha. rewrite Nat.eqb_sym. reflexivity. } unfold xsref. destruct (Nat.eqb_spec i 0) as [->|E]. - rewrite Nat.mul_0_r, Nat.add_0_r. apply (G 10 9 6 8). left. repeat split. - replace i with 1 by lia. rewrite Nat.mul_1_r. apply (G 12 11 7 (8 + al)). right. repeat split. Qed. (* ---- blocks 13 to 21: the weights, the bias and the threshold ------------------------------------ *) Definition fb (j : nat) : bool := nth j qa false. Definition beta4 (b3 b2 b1 b0 : bool) : Z := let braw := Z.of_nat (bits2nat [b3; b2; b1; b0]) in if Z.leb 8 braw then (braw - 16)%Z else braw. (* the threshold as its units compute it, on the ten bits it reads *) Definition vnet (f0 f1 f2 f3 f4 f5 f6 f7 y0 y1 : bool) : bool := let mt0 := negb f0 && f1 && y0 in let mt1 := negb f2 && f3 && y1 in let nt0 := f0 && negb f1 && y0 in let nt1 := f2 && negb f3 && y1 in let pge (c : Z) := Z.leb 0 (- c + b2z mt0 + b2z mt1 - b2z nt0 - b2z nt1)%Z in let bge0 := negb f4 in let bge1 := negb f4 && (f5 || f6 || f7) in let bge2 := negb f4 && (f5 || f6) in let bgem1 := negb f4 || (f5 && f6 && f7) in let bgem2 := negb f4 || (f5 && f6) in (pge (-2)%Z && bge2) || (pge (-1)%Z && bge1) || (pge 0%Z && bge0) || (pge 1%Z && bgem1) || (pge 2%Z && bgem2). Lemma vnet_ok : forall f0 f1 f2 f3 f4 f5 f6 f7 y0 y1, vnet f0 f1 f2 f3 f4 f5 f6 f7 y0 y1 = Z.leb 0 (wcode f0 f1 * b2z y0 + wcode f2 f3 * b2z y1 + beta4 f4 f5 f6 f7)%Z. Proof. intros. destruct f0, f1, f2, f3, f4, f5, f6, f7, y0, y1; reflexivity. Qed. Lemma F_fb : forall j, j < B al -> F (fld K j) = fb j. Proof. exact F_fld. Qed. Lemma F_v : F vref = vnet (fb 0) (fb 1) (fb 2) (fb 3) (fb 4) (fb 5) (fb 6) (fb 7) (F (xsref 0)) (F (xsref 1)). Proof. unfold vref. rewrite (F_or 21 0 0 (map (fun i => (SRef 20 i 0, true)) (seq 0 5))) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [map seq existsb]. rewrite !litv_pos, orb_false_r. assert (Hvand : forall i, i < 5 -> F (SRef 20 i 0) = F (SRef 17 i 0) && F (SRef 19 0 (vand_bge i))). { intros i Hi. rewrite (F_and 20 i 0 [(SRef 17 i 0, true); (SRef 19 0 (vand_bge i), true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r. reflexivity. } rewrite !Hvand by lia. cbn [vand_bge]. assert (HB8 : 8 <= B al) by exact HB. assert (Hb4 : F (SRef 18 0 0) = fb 5 || fb 6 || fb 7 /\ F (SRef 18 0 1) = fb 5 || fb 6 /\ F (SRef 18 0 2) = fb 5 && fb 6 && fb 7 /\ F (SRef 18 0 3) = fb 5 && fb 6). { repeat split; first [ rewrite F_or with (ls := [(fld K 5, true); (fld K 6, true); (fld K 7, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity] | rewrite F_or with (ls := [(fld K 5, true); (fld K 6, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity] | rewrite F_and with (ls := [(fld K 5, true); (fld K 6, true); (fld K 7, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity] | rewrite F_and with (ls := [(fld K 5, true); (fld K 6, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity] ]; cbn [forallb existsb]; rewrite !litv_pos, !F_fb by lia; rewrite ?orb_false_r, ?andb_true_r, ?orb_assoc, ?andb_assoc; reflexivity. } destruct Hb4 as (B0 & B1 & B2 & B3). rewrite (F_and 19 0 0 [(fld K 4, false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_and 19 0 1 [(fld K 4, false); (SRef 18 0 0, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_and 19 0 2 [(fld K 4, false); (SRef 18 0 1, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_or 19 0 3 [(fld K 4, false); (SRef 18 0 2, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_or 19 0 4 [(fld K 4, false); (SRef 18 0 3, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb existsb]. rewrite ?litv_pos, ?litv_neg, B0, B1, B2, B3, !F_fb by lia. assert (Hp : forall i, i < 5 -> F (SRef 17 i 0) = Z.leb 0 (2 - Z.of_nat i + (1 * b2z (F (SRef 15 0 0)) + (1 * b2z (F (SRef 15 1 0)) + (-1 * b2z (F (SRef 16 0 0)) + (-1 * b2z (F (SRef 16 1 0)) + 0)))))%Z). { intros i Hi. rewrite F_unit by (cbn [cnts sizes]; lia). reflexivity. } rewrite !Hp by lia. assert (Hm : forall i, i < 2 -> F (SRef 15 i 0) = negb (fb (2 * i)) && fb (2 * i + 1) && F (xsref i) /\ F (SRef 16 i 0) = fb (2 * i) && negb (fb (2 * i + 1)) && F (xsref i)). { intros i Hi. split. - rewrite (F_and 15 i 0 [(SRef 13 i 0, true); (xsref i, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r. rewrite (F_and 13 i 0 [(fld K (2 * i), false); (fld K (2 * i + 1), true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !F_fb by lia. rewrite !andb_true_r. reflexivity. - rewrite (F_and 16 i 0 [(SRef 14 i 0, true); (xsref i, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r. rewrite (F_and 14 i 0 [(fld K (2 * i), true); (fld K (2 * i + 1), false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !F_fb by lia. rewrite !andb_true_r. reflexivity. } destruct (Hm 0 ltac:(lia)) as [M0 N0]. destruct (Hm 1 ltac:(lia)) as [M1 N1]. cbn [Nat.mul Nat.add] in M0, N0, M1, N1. rewrite M0, N0, M1, N1. unfold vnet. generalize (fb 0) (fb 1) (fb 2) (fb 3) (fb 4) (fb 5) (fb 6) (fb 7) (F (xsref 0)) (F (xsref 1)). intros f0 f1 f2 f3 f4 f5 f6 f7 y0 y1. destruct f0, f1, f2, f3, f4, f5, f6, f7, y0, y1; reflexivity. Qed. (* ---- block 22: the window after the write, and the requests ---------------------------------------- *) Definition vsem : bool := vnet (fb 0) (fb 1) (fb 2) (fb 3) (fb 4) (fb 5) (fb 6) (fb 7) (cellof al K s (fa 8)) (cellof al K s (fa (8 + al))). Definition aosem : nat := fa (8 + 2 * al). Lemma F_vsem : F vref = vsem. Proof. rewrite F_v, (F_xs 0), (F_xs 1) by lia. rewrite Nat.mul_0_r, Nat.add_0_r, Nat.mul_1_r. reflexivity. Qed. Lemma F_lo : forall a, a < W al -> F (SRef 8 a 0) = Nat.eqb aosem a. Proof. intros a Ha. apply F_dec; [right; right; split; reflexivity | exact Ha]. Qed. Lemma aosem_lt : aosem < W al. Proof. apply fa_lt. unfold B, recw. lia. Qed. Lemma F_xhat : forall c, c < nw al -> F (SRef 22 c 2) = if Nat.eqb aosem (c + 4) then vsem else wget (win s) (c + 4). Proof. intros c Hc. rewrite (F_mux 22 c 0 (SRef 8 (c + 4) 0) vref (SIn c)) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite F_lo by (unfold nw in *; lia). rewrite F_vsem, F_w by exact Hc. reflexivity. Qed. (* the request cells after the write *) Definition rq (c : nat) : bool := if Nat.eqb aosem c then vsem else wget (win s) c. Lemma F_req : forall c, AR <= c <= HO -> F (req c) = rq c. Proof. intros c Hc. unfold req, AR, HO in *. rewrite F_xhat by (unfold nw; lia). replace (c - 4 + 4) with c by lia. reflexivity. Qed. (* ---- block 23: kappa after the hand-over ------------------------------------------------------- *) Lemma F_kapn : forall k, k < K -> F (SRef 23 k 2) = if rq HO then Nat.eqb k ii else Nat.eqb k kk. Proof. intros k Hk. rewrite (F_mux 23 k 0 (req HO) (idl al K k) (act al K k)) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite F_req by (unfold AR, HO; lia). rewrite F_idl, F_act by exact Hk. reflexivity. Qed. (* ---- blocks 24 and 25: the banks ---------------------------------------------------------------- *) Lemma F_bw : forall k, k < K -> F (SRef 24 k 0) = Nat.eqb k ii && Nat.eqb aosem ARM /\ F (SRef 24 k 1) = Nat.eqb k ii && rq CB. Proof. intros k Hk. split. - rewrite (F_and 24 k 0 [(idl al K k, true); (SRef 8 ARM 0, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_idl, F_lo by (unfold ARM; lia). reflexivity. - rewrite (F_and 24 k 1 [(idl al K k, true); (req CB, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_idl, F_req by (unfold AR, CB, HO; lia). reflexivity. Qed. Lemma pos_eq : forall p s0 j0 b, j0 < b -> Nat.eqb (p / b) s0 && Nat.eqb (p mod b) j0 = Nat.eqb p (s0 * b + j0). Proof. intros p s0 j0 b Hj. pose proof (Nat.div_mod p b ltac:(lia)) as Dm. pose proof (Nat.mod_upper_bound p b ltac:(lia)). destruct (Nat.eqb_spec (p / b) s0), (Nat.eqb_spec (p mod b) j0), (Nat.eqb_spec p (s0 * b + j0)); cbn [andb]; try reflexivity; try (exfalso; nia). Qed. Lemma F_qn : forall k p, k < K -> p < N al S0 -> F (SRef 25 (k * N al S0 + p) 3) = if Nat.eqb k ii then (if rq CB then false else if Nat.eqb aosem ARM && Nat.eqb p (apos al (bnk k)) then vsem else nth p (bq (bnk k)) false) else nth p (bq (bnk k)) false. Proof. intros k p Hk Hp. destruct (divmod_pair k p (N al S0) Hp) as [Dq Dm]. destruct (bnk_ok k Hk) as (Hq & Hs & Hj). set (m := k * N al S0 + p). assert (Hm : m < K * N al S0) by (unfold m; nia). destruct (F_bw k Hk) as [W0 W1]. assert (He : F (SRef 25 m 0) = (Nat.eqb k ii && Nat.eqb aosem ARM) && Nat.eqb p (apos al (bnk k))). { rewrite (F_and 25 m 0 [(SRef 24 (m / N al S0) 0, true); (href al K S0 (m / N al S0) (m mod N al S0 / B al), true); (jref al K S0 (m / N al S0) (m mod N al S0 mod B al), true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. unfold m in *. rewrite Dq, Dm. cbn [forallb]. rewrite !litv_pos, andb_true_r, W0. assert (Hpb : p / B al < S0) by (apply Nat.Div0.div_lt_upper_bound; unfold N in *; nia). assert (Hpm : p mod B al < B al) by (apply Nat.mod_upper_bound; lia). rewrite F_h, F_j by assumption. unfold apos. change (recw al) with (B al). rewrite <- (pos_eq p (bs (bnk k)) (bj (bnk k)) (B al) Hj), !andb_assoc. reflexivity. } rewrite (F_or 25 m 3 [(SRef 25 m 1, true); (SRef 25 m 2, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite (F_and 25 m 1 [(SRef 25 m 0, true); (vref, true); (SRef 24 (m / N al S0) 1, false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_and 25 m 2 [(SRef 25 m 0, false); (qref al K S0 (m / N al S0) (m mod N al S0), true); (SRef 24 (m / N al S0) 1, false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. unfold m in *. rewrite Dq, Dm. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !andb_true_r. rewrite He, F_vsem, W1, F_q by assumption. destruct (Nat.eqb k ii), (rq CB), (Nat.eqb aosem ARM), (Nat.eqb p (apos al (bnk k))), vsem, (nth p (bq (bnk k)) false); reflexivity. Qed. (* ---- blocks 26 to 28: the heads of the banks ------------------------------------------------------ *) Definition rwA (k : nat) : bool := Nat.eqb k ii && rq RA. Definition aaA (k : nat) : bool := Nat.eqb k ii && negb (rq RA) && rq AA. Definition wrapA (k : nat) : bool := aaA k && Nat.eqb (B al - 1) (bj (bnk k)). Definition sadv (k : nat) : bool := Nat.eqb k kk || wrapA k. Lemma F_hq : forall k, k < K -> F (SRef 26 k 0) = rwA k /\ F (SRef 26 k 1) = aaA k /\ F (SRef 26 k 2) = wrapA k /\ F (SRef 26 k 3) = sadv k. Proof. intros k Hk. assert (R0 : F (SRef 26 k 0) = rwA k). { rewrite (F_and 26 k 0 [(idl al K k, true); (req RA, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r, F_idl, F_req by (unfold AR, RA, HO; lia). reflexivity. } assert (R1 : F (SRef 26 k 1) = aaA k). { rewrite (F_and 26 k 1 [(idl al K k, true); (req RA, false); (req AA, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, andb_true_r, F_idl, !F_req by (unfold AR, RA, AA, HO; lia). unfold aaA. rewrite andb_assoc. reflexivity. } assert (R2 : F (SRef 26 k 2) = wrapA k). { rewrite (F_and 26 k 2 [(SRef 26 k 1, true); (jref al K S0 k (B al - 1), true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [forallb]. rewrite !litv_pos, andb_true_r, R1, F_j by lia. reflexivity. } split; [exact R0|]. split; [exact R1|]. split; [exact R2|]. rewrite (F_or 26 k 3 [(act al K k, true); (SRef 26 k 2, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [existsb]. rewrite !litv_pos, orb_false_r, F_act, R2 by exact Hk. reflexivity. Qed. (* the next bit of a one-hot track *) Lemma F_track : forall bk m n adv rew cur prev, bk < 32 -> m < cnts al K S0 L bk -> sizes al K S0 L bk = 4 -> (forall r, r < 4 -> sunit (phys_blocks al K S0 L) bk m r = nth r (track bk m n adv rew cur prev) su0) -> F (SRef bk m 3) = (F adv && F prev) || (negb (F rew) && negb (F adv) && F cur) || (Nat.eqb (m mod n) 0 && F rew). Proof. intros bk m n adv rew cur prev Hb Hm Hz Hu. rewrite (F_or bk m 3 [(SRef bk m 0, true); (SRef bk m 1, true); (SRef bk m 2, true)]) by first [lia | rewrite Hu by lia; reflexivity]. cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite (F_and bk m 0 [(adv, true); (prev, true)]) by first [lia | rewrite Hu by lia; reflexivity]. rewrite (F_and bk m 1 [(rew, false); (adv, false); (cur, true)]) by first [lia | rewrite Hu by lia; reflexivity]. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !andb_true_r. destruct (Nat.eqb (m mod n) 0) eqn:E0. - rewrite (F_and bk m 2 [(rew, true)]) by first [lia | rewrite Hu by lia; cbn [nth track]; rewrite E0; reflexivity]. cbn [forallb]. rewrite litv_pos. destruct (F adv), (F prev), (F rew), (F cur); reflexivity. - rewrite (F_and bk m 2 [(rew, true); (zero, true)]) by first [lia | rewrite Hu by lia; cbn [nth track]; rewrite E0; reflexivity]. cbn [forallb]. rewrite !litv_pos, F_zero. destruct (F adv), (F prev), (F rew), (F cur); reflexivity. Qed. Lemma track_val : forall n x pos adv rew, x < n -> pos < n -> adv && rew = false -> (adv && Nat.eqb ((x + n - 1) mod n) pos) || (negb rew && negb adv && Nat.eqb x pos) || (Nat.eqb x 0 && rew) = Nat.eqb x (if rew then 0 else if adv then succ_mod n pos else pos). Proof. intros n x pos adv rew Hx Hp H. rewrite prev_eq by assumption. destruct adv, rew; cbn [andb orb negb] in *; try discriminate; rewrite ?andb_false_r, ?andb_true_r, ?orb_false_r; reflexivity. Qed. Definition snew (k : nat) : nat := if Nat.eqb k kk then succ_mod S0 (bs (bnk k)) else if rwA k then 0 else if wrapA k then succ_mod S0 (bs (bnk k)) else bs (bnk k). Lemma F_hs : forall k x, k < K -> x < S0 -> F (SRef 27 (k * S0 + x) 3) = Nat.eqb x (snew k). Proof. intros k x Hk Hx. destruct (divmod_pair k x S0 Hx) as [Dq Dm]. destruct (bnk_ok k Hk) as (_ & Hs & _). destruct (F_hq k Hk) as (R0 & _ & _ & R3). rewrite (F_track 27 (k * S0 + x) S0 (SRef 26 ((k * S0 + x) / S0) 3) (SRef 26 ((k * S0 + x) / S0) 0) (href al K S0 ((k * S0 + x) / S0) ((k * S0 + x) mod S0)) (href al K S0 ((k * S0 + x) / S0) (((k * S0 + x) mod S0 + S0 - 1) mod S0))) by first [lia | cbn [cnts]; nia | reflexivity | intros r Hr; reflexivity]. rewrite Dq, Dm, R0, R3. rewrite !F_h by (try exact Hk; try exact Hx; apply Nat.mod_upper_bound; lia). assert (Hx' : (x + S0 - 1) mod S0 < S0) by (apply Nat.mod_upper_bound; lia). rewrite (track_val S0 x (bs (bnk k)) (sadv k) (rwA k) Hx Hs). - unfold snew, sadv. pose proof ii_kk. destruct (Nat.eqb_spec k kk) as [->|E]. + unfold rwA. rewrite (proj2 (Nat.eqb_neq kk ii) ltac:(lia)). reflexivity. + reflexivity. - unfold sadv, rwA, wrapA, aaA. pose proof ii_kk. generalize (rq RA) (rq AA) (Nat.eqb (B al - 1) (bj (bnk k))). intros b1 b2 b3. destruct (Nat.eqb_spec k kk), (Nat.eqb_spec k ii); subst; try lia; destruct b1, b2, b3; reflexivity. Qed. Definition jnew (k : nat) : nat := if rwA k then 0 else if aaA k then succ_mod (B al) (bj (bnk k)) else bj (bnk k). Lemma F_hj : forall k x, k < K -> x < B al -> F (SRef 28 (k * B al + x) 3) = Nat.eqb x (jnew k). Proof. intros k x Hk Hx. destruct (divmod_pair k x (B al) Hx) as [Dq Dm]. destruct (bnk_ok k Hk) as (_ & _ & Hj). destruct (F_hq k Hk) as (R0 & R1 & _). rewrite (F_track 28 (k * B al + x) (B al) (SRef 26 ((k * B al + x) / B al) 1) (SRef 26 ((k * B al + x) / B al) 0) (jref al K S0 ((k * B al + x) / B al) ((k * B al + x) mod B al)) (jref al K S0 ((k * B al + x) / B al) (((k * B al + x) mod B al + B al - 1) mod B al))) by first [lia | cbn [cnts]; nia | reflexivity | intros r Hr; reflexivity]. rewrite Dq, Dm, R0, R1. rewrite !F_j by (try exact Hk; try exact Hx; apply Nat.mod_upper_bound; lia). rewrite (track_val (B al) x (bj (bnk k)) (aaA k) (rwA k) Hx Hj). - reflexivity. - unfold aaA, rwA. destruct (Nat.eqb k ii), (rq RA), (rq AA); reflexivity. Qed. (* ---- blocks 29 to 31: the tapes ------------------------------------------------------------------- *) Definition rwT (k : nat) : bool := (Nat.eqb k kk && rq RR) || (Nat.eqb k ii && rq RC). Definition advT (k : nat) : bool := (Nat.eqb k kk && negb (rq RR) && rq AR) || (Nat.eqb k ii && negb (rq RC) && rq AC). Lemma F_tw : forall k, k < K -> F (SRef 29 k 0) = Nat.eqb k ii && Nat.eqb aosem CPY /\ F (SRef 29 k 1) = Nat.eqb k ii && rq CT /\ F (SRef 29 k 4) = rwT k /\ F (SRef 29 k 7) = advT k. Proof. intros k Hk. assert (G : forall r ls, r < 8 -> sunit (phys_blocks al K S0 L) 29 k r = sAND ls -> F (SRef 29 k r) = forallb (litv F) ls) by (intros r ls Hr E; apply (F_and 29 k r ls); [lia | cbn [cnts]; lia | cbn [sizes]; lia | exact E]). assert (G' : forall r ls, r < 8 -> sunit (phys_blocks al K S0 L) 29 k r = sOR ls -> F (SRef 29 k r) = existsb (litv F) ls) by (intros r ls Hr E; apply (F_or 29 k r ls); [lia | cbn [cnts]; lia | cbn [sizes]; lia | exact E]). repeat split. - rewrite (G 0 [(idl al K k, true); (SRef 8 CPY 0, true)] ltac:(lia) eq_refl). cbn [forallb]. rewrite !litv_pos, andb_true_r, F_idl, F_lo by (unfold CPY; lia). reflexivity. - rewrite (G 1 [(idl al K k, true); (req CT, true)] ltac:(lia) eq_refl). cbn [forallb]. rewrite !litv_pos, andb_true_r, F_idl, F_req by (unfold AR, CT, HO; lia). reflexivity. - rewrite (G' 4 [(SRef 29 k 2, true); (SRef 29 k 3, true)] ltac:(lia) eq_refl). cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite (G 2 [(act al K k, true); (req RR, true)] ltac:(lia) eq_refl). rewrite (G 3 [(idl al K k, true); (req RC, true)] ltac:(lia) eq_refl). cbn [forallb]. rewrite !litv_pos, !andb_true_r, F_act, F_idl, !F_req by (unfold AR, RR, RC, HO; lia). reflexivity. - rewrite (G' 7 [(SRef 29 k 5, true); (SRef 29 k 6, true)] ltac:(lia) eq_refl). cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite (G 5 [(act al K k, true); (req RR, false); (req AR, true)] ltac:(lia) eq_refl). rewrite (G 6 [(idl al K k, true); (req RC, false); (req AC, true)] ltac:(lia) eq_refl). cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !andb_true_r, F_act, F_idl, !F_req by (unfold AR, RR, RC, AC, HO; lia). unfold advT. rewrite !andb_assoc. reflexivity. Qed. Lemma F_dn : forall k i, k < K -> i < L -> F (SRef 30 (k * L + i) 3) = if Nat.eqb k ii then (if rq CT then false else if Nat.eqb aosem CPY && Nat.eqb i (th (tpe k)) then vsem else nth i (td (tpe k)) false) else nth i (td (tpe k)) false. Proof. intros k i Hk Hi. destruct (divmod_pair k i L Hi) as [Dq Dm]. set (m := k * L + i). assert (Hm : m < K * L) by (unfold m; nia). destruct (F_tw k Hk) as (T0 & T1 & _). assert (He : F (SRef 30 m 0) = (Nat.eqb k ii && Nat.eqb aosem CPY) && Nat.eqb i (th (tpe k))). { rewrite (F_and 30 m 0 [(SRef 29 (m / L) 0, true); (tref al K S0 L (m / L) (m mod L), true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. unfold m in *. rewrite Dq, Dm. cbn [forallb]. rewrite !litv_pos, andb_true_r, T0, F_t by assumption. reflexivity. } rewrite (F_or 30 m 3 [(SRef 30 m 1, true); (SRef 30 m 2, true)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. cbn [existsb]. rewrite !litv_pos, orb_false_r. rewrite (F_and 30 m 1 [(SRef 30 m 0, true); (vref, true); (SRef 29 (m / L) 1, false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. rewrite (F_and 30 m 2 [(SRef 30 m 0, false); (dref al K S0 L (m / L) (m mod L), true); (SRef 29 (m / L) 1, false)]) by first [lia | cbn [cnts sizes]; lia | reflexivity]. unfold m in *. rewrite Dq, Dm. cbn [forallb]. rewrite ?litv_pos, ?litv_neg, !andb_true_r. rewrite He, F_vsem, T1, F_d by assumption. destruct (Nat.eqb k ii), (rq CT), (Nat.eqb aosem CPY), (Nat.eqb i (th (tpe k))), vsem, (nth i (td (tpe k)) false); reflexivity. Qed. Definition tnew (k : nat) : nat := if rwT k then 0 else if advT k then succ_mod L (th (tpe k)) else th (tpe k). Lemma F_tn : forall k i, k < K -> i < L -> F (SRef 31 (k * L + i) 3) = Nat.eqb i (tnew k). Proof. intros k i Hk Hi. destruct (divmod_pair k i L Hi) as [Dq Dm]. destruct (tpe_ok k Hk) as (_ & Ht). destruct (F_tw k Hk) as (_ & _ & T4 & T7). rewrite (F_track 31 (k * L + i) L (SRef 29 ((k * L + i) / L) 7) (SRef 29 ((k * L + i) / L) 4) (tref al K S0 L ((k * L + i) / L) ((k * L + i) mod L)) (tref al K S0 L ((k * L + i) / L) (((k * L + i) mod L + L - 1) mod L))) by first [lia | cbn [cnts]; nia | reflexivity | intros r Hr; reflexivity]. rewrite Dq, Dm, T4, T7. rewrite !F_t by (try exact Hk; try exact Hi; apply Nat.mod_upper_bound; lia). rewrite (track_val L i (th (tpe k)) (advT k) (rwT k) Hi Ht). - reflexivity. - unfold advT, rwT. pose proof ii_kk. destruct (Nat.eqb_spec k kk), (Nat.eqb_spec k ii); subst; cbn [andb orb negb]; try lia; destruct (rq RR), (rq RC), (rq AR), (rq AC); reflexivity. Qed. (* ---- the step of the machine in the same terms ---------------------------------------------- *) Lemma firstn4_skipn4 : forall (l : list bool), 8 <= length l -> firstn 4 (skipn 4 l) = [nth 4 l false; nth 5 l false; nth 6 l false; nth 7 l false]. Proof. intros l H. destruct l as [|x0 [|x1 [|x2 [|x3 [|x4 [|x5 [|x6 [|x7 l]]]]]]]]; cbn [length] in H; try lia. reflexivity. Qed. Lemma decode_qa : decodeA al qa = Rec (fa 8) (wcode (fb 0) (fb 1)) (fa (8 + al)) (wcode (fb 2) (fb 3)) (beta4 (fb 4) (fb 5) (fb 6) (fb 7)) (fa (8 + 2 * al)). Proof. unfold decodeA. cbv zeta. unfold fa, field, fb, beta4. rewrite firstn4_skipn4 by (rewrite length_qa; unfold B, recw; lia). reflexivity. Qed. Lemma step_eq : step al K S0 L s = stepres al K S0 L s aosem vsem. Proof. unfold step. change (slot al (nth (kap s) (banks s) bank0)) with qa. rewrite decode_qa. unfold vsem. rewrite vnet_ok. reflexivity. Qed. Lemma upd_length : forall l i v, length (upd l i v) = length l. Proof. induction l as [|x l IH]; intros [|i] v; cbn; auto. Qed. Lemma nth_upd : forall l i j v, j < length l -> nth j (upd l i v) false = if Nat.eqb j i then v else nth j l false. Proof. induction l as [|x l IH]; intros i j v Hj; cbn [length] in Hj; [lia|]. destruct i as [|i], j as [|j]; cbn [upd nth Nat.eqb]; try reflexivity. apply IH. lia. Qed. Lemma wget_upd : forall w i v x, wget (upd w i v) x = if Nat.eqb x i && Nat.ltb i (length w) then v else wget w x. Proof. unfold wget. induction w as [|y w IH]; intros i v x. - cbn. rewrite andb_false_r. destruct x; reflexivity. - destruct i as [|i], x as [|x]; cbn; try reflexivity; rewrite IH; reflexivity. Qed. Definition wn : list bool := wnext (win s) aosem vsem. Lemma rq_wn : forall c, CPY < c -> c < W al -> rq c = wget wn c. Proof. intros c H1 H2. unfold rq, wn, wnext. pose proof aosem_lt as Ha. destruct (Nat.leb_spec aosem CPY) as [E|E]. - rewrite (proj2 (Nat.eqb_neq aosem c) ltac:(lia)). reflexivity. - rewrite wget_upd, (length_win al K S0 L s Hv). rewrite Nat.eqb_sym. replace (aosem <? W al) with true by (symmetry; apply Nat.ltb_lt; exact Ha). rewrite andb_true_r. reflexivity. Qed. Lemma wget_clearq : forall w c, length w = W al -> wget (clearq w) c = if (AR <=? c) && (c <=? HO) then false else wget w c. Proof. intros w c Hw. unfold clearq. rewrite !wget_upd, !upd_length, Hw. assert (Hl : forall x, x <= HO -> (x <? W al) = true) by (intros x Hx; apply Nat.ltb_lt; unfold HO in *; lia). rewrite !Hl by (unfold AR, AA, AC, RR, RA, RC, CB, CT, HO; lia). rewrite !andb_true_r. unfold AR, AA, AC, RR, RA, RC, CB, CT, HO. destruct (Nat.eqb_spec c 12); [subst; reflexivity|]. destruct (Nat.eqb_spec c 11); [subst; reflexivity|]. destruct (Nat.eqb_spec c 10); [subst; reflexivity|]. destruct (Nat.eqb_spec c 9); [subst; reflexivity|]. destruct (Nat.eqb_spec c 8); [subst; reflexivity|]. destruct (Nat.eqb_spec c 7); [subst; reflexivity|]. destruct (Nat.eqb_spec c 6); [subst; reflexivity|]. destruct (Nat.eqb_spec c 5); [subst; reflexivity|]. destruct (Nat.eqb_spec c 4); [subst; reflexivity|]. destruct (Nat.leb_spec 4 c), (Nat.leb_spec c 12); cbn [andb]; try reflexivity; lia. Qed. Lemma length_wn : length wn = W al. Proof. unfold wn, wnext. destruct (Nat.leb aosem CPY); [|rewrite upd_length]; apply (length_win al K S0 L s Hv). Qed. (* the banks and the tapes after the step *) Lemma bank_next : forall k, k < K -> nth k (banks (step al K S0 L s)) bank0 = if Nat.eqb k kk then mkB (bq (bnk k)) (succ_mod S0 (bs (bnk k))) (bj (bnk k)) else if Nat.eqb k ii then (let I1 := if Nat.eqb aosem ARM then mkB (upd (bq (bnk k)) (apos al (bnk k)) vsem) (bs (bnk k)) (bj (bnk k)) else bnk k in let I1' := mkB (if wget wn CB then repeat false (S0 * recw al) else bq I1) (bs I1) (bj I1) in if wget wn RA then mkB (bq I1') 0 0 else if wget wn AA then advb S0 (recw al) I1' else I1') else bnk k. Proof. intros k Hk. rewrite step_eq. unfold stepres. cbv zeta. cbn [banks]. fold kk. fold ii. fold wn. rewrite (nth_map_seq _ _ K k bank0 Hk). destruct (Nat.eqb_spec k kk) as [->|E]; [reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; reflexivity. Qed. Lemma tape_next : forall k, k < K -> nth k (tapes (step al K S0 L s)) tape0 = if Nat.eqb k kk then mkT (td (tpe k)) (if wget wn RR then 0 else if wget wn AR then succ_mod L (th (tpe k)) else th (tpe k)) else if Nat.eqb k ii then mkT (if wget wn CT then repeat false L else if Nat.eqb aosem CPY then upd (td (tpe k)) (th (tpe k)) vsem else td (tpe k)) (if wget wn RC then 0 else if wget wn AC then succ_mod L (th (tpe k)) else th (tpe k)) else tpe k. Proof. intros k Hk. rewrite step_eq. unfold stepres. cbv zeta. cbn [tapes]. fold kk. fold ii. fold wn. rewrite (nth_map_seq _ _ K k tape0 Hk). destruct (Nat.eqb_spec k kk) as [->|E]; [reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; [|reflexivity]. destruct (Nat.eqb aosem CPY); reflexivity. Qed. Lemma step_win : win (step al K S0 L s) = clearq wn. Proof. rewrite step_eq. reflexivity. Qed. Lemma step_kap : kap (step al K S0 L s) = if wget wn HO then ii else kk. Proof. rewrite step_eq. reflexivity. Qed. Lemma bq_advb : forall S1 b q, bq (advb S1 b q) = bq q. Proof. intros S1 b q. unfold advb. destruct (Nat.eqb (S (bj q)) b); reflexivity. Qed. Lemma advb_ok : forall q, bs q < S0 -> bj q < B al -> bs (advb S0 (recw al) q) < S0 /\ bj (advb S0 (recw al) q) < B al /\ bq (advb S0 (recw al) q) = bq q. Proof. intros q H1 H2. unfold advb. fold (B al). destruct (Nat.eqb_spec (S (bj q)) (B al)); cbn [bs bj bq]. - split; [apply succ_mod_lt; lia | split; [lia | reflexivity]]. - split; [lia | split; [lia | reflexivity]]. Qed. Lemma step_fits : fits al K S0 L (step al K S0 L s). Proof. pose proof kk_lt. pose proof ii_lt. unfold fits. refine (conj _ (conj _ (conj _ (conj _ (conj _ _))))). - rewrite step_win. unfold clearq. rewrite !upd_length. apply length_wn. - rewrite step_kap. destruct (wget wn HO); assumption. - rewrite step_eq. unfold stepres. cbv zeta. cbn [banks]. rewrite length_map, length_seq. reflexivity. - rewrite step_eq. unfold stepres. cbv zeta. cbn [tapes]. rewrite length_map, length_seq. reflexivity. - intros x Hx. rewrite bank_next by exact Hx. destruct (bnk_ok x Hx) as (Hq & Hs & Hj). destruct (Nat.eqb_spec x kk); [cbn [bq bs bj]; split; [exact Hq | split; [apply succ_mod_lt; lia | exact Hj]]|]. destruct (Nat.eqb_spec x ii); [|exact (bnk_ok x Hx)]. cbv zeta. set (I1 := if Nat.eqb aosem ARM then mkB (upd (bq (bnk x)) (apos al (bnk x)) vsem) (bs (bnk x)) (bj (bnk x)) else bnk x). assert (HI : length (bq I1) = N al S0 /\ bs I1 < S0 /\ bj I1 < B al). { unfold I1. destruct (Nat.eqb aosem ARM); cbn [bq bs bj]; [rewrite upd_length|]; auto. } destruct HI as (Hq1 & Hs1 & Hj1). assert (Hq1' : length (if wget wn CB then repeat false (S0 * recw al) else bq I1) = S0 * recw al) by (destruct (wget wn CB); [apply repeat_length | exact Hq1]). destruct (wget wn RA); cbn [bq bs bj]; [split; [exact Hq1' | unfold B, recw in *; lia]|]. destruct (wget wn AA). + destruct (advb_ok (mkB (if wget wn CB then repeat false (S0 * recw al) else bq I1) (bs I1) (bj I1)) Hs1 Hj1) as (A1 & A2 & A3). rewrite A3. cbn [bq]. split; [exact Hq1' | split; assumption]. + cbn [bq bs bj]. split; [exact Hq1' | split; assumption]. - intros x Hx. rewrite tape_next by exact Hx. destruct (tpe_ok x Hx) as (Hd & Ht). destruct (Nat.eqb_spec x kk); cbn [td th]. + split; [exact Hd|]. destruct (wget wn RR); [lia|]. destruct (wget wn AR); [apply succ_mod_lt; lia | exact Ht]. + destruct (Nat.eqb_spec x ii); cbn [td th]; [|exact (tpe_ok x Hx)]. split. * destruct (wget wn CT); [apply repeat_length|]. destruct (Nat.eqb aosem CPY); [rewrite upd_length|]; exact Hd. * destruct (wget wn RC); [lia|]. destruct (wget wn AC); [apply succ_mod_lt; lia | exact Ht]. Qed. (* every state bit after the step is the value of its unit *) Lemma F_out : forall i, i < nst al K S0 L -> F (out_ref al K S0 L i) = nth i (encode al K S0 L (step al K S0 L s)) false. Proof. intros i Hi. pose proof kk_lt as Hkk. pose proof ii_lt as Hii. pose proof ii_kk as Hik. pose proof step_fits as Hf. unfold out_ref. destruct (Nat.ltb_spec i (nw al)) as [Hw|Hw]. { (* the window *) rewrite (X_win al K S0 L _ i Hw), step_win, wget_clearq by apply length_wn. replace (AR <=? i + 4) with true by (symmetry; apply Nat.leb_le; unfold AR; lia). rewrite andb_true_l. destruct (Nat.leb_spec (i + 4) HO) as [Hr|Hr]; cbv beta iota. - exact F_zero. - rewrite F_xhat by exact Hw. rewrite <- rq_wn by (unfold CPY, HO, nw in *; lia). unfold rq. rewrite Nat.eqb_sym. reflexivity. } destruct (Nat.ltb_spec i (nw al + K)) as [Hk|Hk]. { (* kappa *) replace i with (okap al + (i - nw al)) at 2 by (unfold okap; lia). rewrite (X_kap al K S0 L _ (i - nw al) ltac:(lia)), F_kapn by lia. rewrite step_kap, rq_wn by (unfold CPY, HO; pose proof (W_ge al Hal); lia). destruct (wget wn HO); reflexivity. } assert (Hbsz : bsz al S0 = N al S0 + S0 + B al) by reflexivity. destruct (Nat.ltb_spec i (nw al + K + K * bsz al S0)) as [Hb|Hb]. { (* a bank *) set (r := i - (nw al + K)). set (k := r / bsz al S0). set (p := r mod bsz al S0). assert (Hk' : k < K) by (unfold k, r; apply Nat.Div0.div_lt_upper_bound; lia). assert (Hp : p < bsz al S0) by (unfold p; apply Nat.mod_upper_bound; unfold bsz, N, B, recw; nia). assert (Hi' : i = obank al K S0 k + p). { unfold obank, k, p, r. pose proof (Nat.div_mod (i - (nw al + K)) (bsz al S0) ltac:(unfold bsz, N, B, recw; nia)). lia. } destruct (X_bank al K S0 L _ Hf k Hk') as (Xq & Xs & Xj). rewrite bank_next in Xq, Xs, Xj by exact Hk'. destruct (Nat.ltb_spec p (N al S0)) as [H1|H1]. { rewrite Hi', Xq by exact H1. rewrite F_qn by assumption. destruct (Nat.eqb_spec k kk) as [->|E]; [rewrite (proj2 (Nat.eqb_neq kk ii) ltac:(lia)); reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; [|reflexivity]. destruct (bnk_ok ii Hii) as (Hq & _ & _). cbv zeta. assert (Hbq : forall (q : bank) (b1 b2 : bool), bq (if b1 then mkB (bq q) 0 0 else if b2 then advb S0 (recw al) q else q) = bq q) by (intros q b1 b2; destruct b1, b2; cbn [bq]; try reflexivity; apply bq_advb). rewrite Hbq. cbn [bq]. rewrite <- (rq_wn CB) by (unfold CPY, CB; pose proof (W_ge al Hal); lia). destruct (rq CB); [rewrite nth_repeat; reflexivity|]. destruct (Nat.eqb aosem ARM); cbn [bq andb]; [|reflexivity]. rewrite nth_upd by (rewrite Hq; exact H1). destruct (Nat.eqb p (apos al (bnk ii))); reflexivity. } destruct (Nat.ltb_spec p (N al S0 + S0)) as [H2|H2]. { replace i with (obank al K S0 k + N al S0 + (p - N al S0)) by lia. rewrite Xs by lia. replace (k * S0 + (p - N al S0)) with (k * S0 + (p - N al S0)) by reflexivity. rewrite F_hs by lia. f_equal. unfold snew. destruct (Nat.eqb_spec k kk) as [->|E]; [reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; [|unfold rwA, wrapA, aaA; rewrite (proj2 (Nat.eqb_neq k ii) E'); reflexivity]. unfold rwA, wrapA, aaA. rewrite Nat.eqb_refl, !andb_true_l. cbv zeta. rewrite !rq_wn by (unfold CPY, RA, AA; pose proof (W_ge al Hal); lia). destruct (bnk_ok ii Hii) as (_ & Hs & Hj). generalize (wget wn RA) (wget wn AA). intros b1 b2. destruct (Nat.eqb aosem ARM), b1, b2; cbn [bs bj negb andb]; try reflexivity; unfold advb; cbn [bs bj]; fold (B al); destruct (Nat.eqb_spec (S (bj (bnk ii))) (B al)), (Nat.eqb_spec (B al - 1) (bj (bnk ii))); cbn [bs]; try reflexivity; lia. } { replace i with (obank al K S0 k + N al S0 + S0 + (p - N al S0 - S0)) by lia. rewrite Xj by (unfold bsz in Hp; lia). rewrite F_hj by (unfold bsz in Hp; lia). f_equal. unfold jnew. destruct (Nat.eqb_spec k kk) as [->|E]; [unfold rwA, aaA; rewrite (proj2 (Nat.eqb_neq kk ii) ltac:(lia)); reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; [|unfold rwA, aaA; rewrite (proj2 (Nat.eqb_neq k ii) E'); reflexivity]. unfold rwA, aaA. rewrite Nat.eqb_refl, !andb_true_l. cbv zeta. rewrite !rq_wn by (unfold CPY, RA, AA; pose proof (W_ge al Hal); lia). generalize (wget wn RA) (wget wn AA). intros b1 b2. destruct (Nat.eqb aosem ARM), b1, b2; cbn [bs bj negb andb]; try reflexivity; unfold advb, succ_mod; cbn [bs bj]; fold (B al); destruct (Nat.eqb (S (bj (bnk ii))) (B al)); reflexivity. } } { (* a tape *) set (r := i - (nw al + K + K * bsz al S0)). set (k := r / (2 * L)). set (p := r mod (2 * L)). assert (Hr : r < K * (2 * L)) by (unfold r, nst in *; lia). assert (Hk' : k < K) by (unfold k; apply Nat.Div0.div_lt_upper_bound; lia). assert (Hp : p < 2 * L) by (unfold p; apply Nat.mod_upper_bound; lia). assert (Hi' : i = otape al K S0 L k + p). { unfold otape, k, p. pose proof (Nat.div_mod r (2 * L) ltac:(lia)). unfold r in *. lia. } destruct (X_tape al K S0 L _ Hf k Hk') as (Xd & Xt). rewrite tape_next in Xd, Xt by exact Hk'. destruct (Nat.ltb_spec p L) as [H1|H1]. { rewrite Hi', Xd by exact H1. rewrite F_dn by assumption. destruct (Nat.eqb_spec k kk) as [->|E]; [rewrite (proj2 (Nat.eqb_neq kk ii) ltac:(lia)); reflexivity|]. destruct (Nat.eqb_spec k ii) as [->|E']; [|reflexivity]. destruct (tpe_ok ii Hii) as (Hd & _). cbn [td]. rewrite <- rq_wn by (unfold CPY, CT; lia). destruct (rq CT); [rewrite nth_repeat; reflexivity|]. destruct (Nat.eqb aosem CPY); cbn [andb]; [|reflexivity]. rewrite nth_upd by (rewrite Hd; exact H1). destruct (Nat.eqb p (th (tpe ii))); reflexivity. } { replace i with (otape al K S0 L k + L + (p - L)) by lia. rewrite Xt by lia. rewrite F_tn by lia. f_equal. unfold tnew, rwT, advT. rewrite !rq_wn by (unfold CPY, RR, AR, RC, AC; pose proof (W_ge al Hal); lia). generalize (wget wn RR) (wget wn AR) (wget wn RC) (wget wn AC). intros b1 b2 b3 b4. destruct (Nat.eqb_spec k kk) as [->|E]. - rewrite (proj2 (Nat.eqb_neq kk ii) ltac:(lia)). cbn [th]. destruct b1, b2, b3, b4; reflexivity. - destruct (Nat.eqb_spec k ii) as [->|E']; cbn [th]; [|reflexivity]. destruct b1, b2, b3, b4; reflexivity. } } Qed. (* one step of the netlist on the encoded state is the encoded next state *) Theorem netlist_step : netstep (nst al K S0 L) (phys_units al K S0 L) (phys_next al K S0 L) (encode al K S0 L s) = encode al K S0 L (step al K S0 L s). Proof. unfold netstep, phys_next. rewrite map_map. apply nth_ext with (d := false) (d' := false). { rewrite length_map, length_seq, (length_encode al K S0 L _ step_fits). reflexivity. } intros i Hi. rewrite length_map, length_seq in Hi. rewrite (nth_map_seq _ (fun i => run (phys_units al K S0 L) (nst al K S0 L) (fun i0 => nth i0 (encode al K S0 L s) false) (idx (nst al K S0 L) (phys_blocks al K S0 L) (out_ref al K S0 L i))) (nst al K S0 L) i false Hi). exact (F_out i Hi). Qed. End Sem.
(* What each block of the netlist computes, from a state of the ring machine. *)
From Stdlib Require Import List Bool Arith ZArith Lia.
Import ListNotations.
From TH Require Import TwoHead Net Gates Phys PhysWF.
(* ---- the state bits of a machine state, in the order of the netlist ------------------------- *)
Definition onehot (n p : nat) : list bool := map (fun x => Nat.eqb x p) (seq 0 n).
Definition bankbits (al S0 : nat) (q : bank) : list bool := bq q ++ onehot S0 (bs q) ++ onehot (recw al) (bj q).
Definition tapebits (L : nat) (t : tape) : list bool := td t ++ onehot L (th t).
Definition encode (al K S0 L : nat) (s : st) : list bool :=
map (fun c => wget (win s) (c + 4)) (seq 0 (nw al))
++ onehot K (kap s)
++ concat (map (fun k => bankbits al S0 (nth k (banks s) bank0)) (seq 0 K))
++ concat (map (fun k => tapebits L (nth k (tapes s) tape0)) (seq 0 K)).
Lemma length_onehot : forall n p, length (onehot n p) = n.
Proof. intros. unfold onehot. rewrite length_map, length_seq. reflexivity. Qed.
Lemma nth_onehot : forall n p x, x < n -> nth x (onehot n p) false = Nat.eqb x p.
Proof. intros n p x H. unfold onehot. apply (nth_map_seq _ (fun x => Nat.eqb x p) n x false H). Qed.
Lemma length_bankbits : forall al S0 q, length (bq q) = S0 * recw al ->
length (bankbits al S0 q) = bsz al S0.
Proof. intros. unfold bankbits, bsz, N, B. rewrite !length_app, !length_onehot. lia. Qed.
Lemma length_tapebits : forall L t, length (td t) = L -> length (tapebits L t) = 2 * L.
Proof. intros. unfold tapebits. rewrite length_app, length_onehot. lia. Qed.
Lemma nth_concat_map_seq : forall (f : nat -> list bool) K sz k x,
(forall k', k' < K -> length (f k') = sz) -> k < K -> x < sz ->
nth (k * sz + x) (concat (map f (seq 0 K))) false = nth x (f k) false.
Proof.
intros f K sz k x Hl Hk Hx. rewrite Nat.mul_comm.
rewrite (nth_concat_const _ false (map f (seq 0 K)) sz k x).
- rewrite (nth_map_seq _ f K k [] Hk). reflexivity.
- apply Forall_forall. intros l Hin. apply in_map_iff in Hin as (k' & <- & Hk'). apply in_seq in Hk'.
apply Hl. lia.
- rewrite length_map, length_seq. exact Hk.
- exact Hx.
Qed.
Lemma length_concat_map_seq : forall (f : nat -> list bool) K sz,
(forall k', k' < K -> length (f k') = sz) -> length (concat (map f (seq 0 K))) = K * sz.
Proof.
intros f K sz Hl. rewrite (length_concat_const _ _ sz).
- rewrite length_map, length_seq. reflexivity.
- apply Forall_forall. intros l Hin. apply in_map_iff in Hin as (k' & <- & Hk'). apply in_seq in Hk'.
apply Hl. lia.
Qed.
Section Encode.
Variables al K S0 L : nat.
Variable s : st.
Hypothesis Hv : fits al K S0 L s.
Let bk k := nth k (banks s) bank0.
Let tp k := nth k (tapes s) tape0.
Lemma length_win : length (win s) = W al.
Proof. destruct Hv as (H & _). exact H. Qed.
Lemma bank_ok : forall k, k < K -> length (bq (bk k)) = S0 * recw al /\ bs (bk k) < S0 /\ bj (bk k) < recw al.
Proof. intros k Hk. destruct Hv as (_ & _ & _ & _ & H & _). apply H. exact Hk. Qed.
Lemma tape_ok : forall k, k < K -> length (td (tp k)) = L /\ th (tp k) < L.
Proof. intros k Hk. destruct Hv as (_ & _ & _ & _ & _ & H). apply H. exact Hk. Qed.
Lemma len_banks : length (concat (map (fun k => bankbits al S0 (nth k (banks s) bank0)) (seq 0 K))) = K * bsz al S0.
Proof. apply length_concat_map_seq. intros k Hk. apply length_bankbits. apply (bank_ok k Hk). Qed.
Lemma len_tapes : length (concat (map (fun k => tapebits L (nth k (tapes s) tape0)) (seq 0 K))) = K * (2 * L).
Proof. apply length_concat_map_seq. intros k Hk. apply length_tapebits. apply (tape_ok k Hk). Qed.
Lemma length_encode : length (encode al K S0 L s) = nst al K S0 L.
Proof.
unfold encode, nst. rewrite !length_app, length_map, length_seq, length_onehot, len_banks, len_tapes. lia.
Qed.
Lemma X_win : forall c, c < nw al -> nth c (encode al K S0 L s) false = wget (win s) (c + 4).
Proof.
intros c Hc. unfold encode. rewrite app_nth1 by (rewrite length_map, length_seq; exact Hc).
exact (nth_map_seq _ (fun c => wget (win s) (c + 4)) (nw al) c false Hc).
Qed.
Lemma X_kap : forall k, k < K -> nth (okap al + k) (encode al K S0 L s) false = Nat.eqb k (kap s).
Proof.
intros k Hk. unfold encode, okap. rewrite app_nth2 by (rewrite length_map, length_seq; lia).
rewrite length_map, length_seq. rewrite app_nth1 by (rewrite length_onehot; lia).
replace (nw al + k - nw al) with k by lia. apply nth_onehot. exact Hk.
Qed.
Lemma X_bank : forall k, k < K ->
(forall p, p < N al S0 -> nth (obank al K S0 k + p) (encode al K S0 L s) false = nth p (bq (bk k)) false)
/\ (forall x, x < S0 -> nth (obank al K S0 k + N al S0 + x) (encode al K S0 L s) false = Nat.eqb x (bs (bk k)))
/\ (forall x, x < B al -> nth (obank al K S0 k + N al S0 + S0 + x) (encode al K S0 L s) false
= Nat.eqb x (bj (bk k))).
Proof.
intros k Hk. destruct (bank_ok k Hk) as (Hq & _ & _).