(* The SUBLEQ host H_A as a netlist of ternary threshold units, block by block in the order of the generator, for words of A bits (Construction 5.8), and the machine it computes. *) From Stdlib Require Import List Bool Arith ZArith Lia. Import ListNotations. From TH Require Import TwoHead Net Gates. Section Host. Variable A : nat. (* the words of memory, and the state bits: the counter, the halt bit, the memory *) Definition SW : nat := 2 ^ A. Definition nH : nat := A + 1 + SW * A. (* bit t of an A-bit value, most significant first *) Definition bitof (v t : nat) : bool := Nat.testbit v (A - 1 - t). Definition pcb (i : nat) : sref := SIn i. Definition haltb : sref := SIn A. Definition mu (j t : nat) : sref := SIn (A + 1 + j * A + t). (* the literals asserting that the bits f 0 .. f (A - 1), most significant first, spell v *) Definition lits (f : nat -> sref) (v : nat) : list lit := map (fun t => (f t, bitof v t)) (seq 0 A). Definition opb (o t : nat) : sref := SRef 6 (o * A + t) 0. Definition xv (i : nat) : sref := SRef 14 (A - 1 - i) 0. Definition yv (i : nat) : sref := SRef 15 (A - 1 - i) 0. Definition prr (i : nat) : sref := SRef 16 i 0. Definition tb : nat := 16 + A. (* 0 to 16: decode, fetch, operands, reads, propagate signals *) Definition blk_P : block := Blk SW 1 (fun j => [sAND (lits pcb j)]). Definition blk_HP : block := Blk A 1 (fun i => [sAND [(pcb i, true); (haltb, true)]]). Definition blk_FA (o : nat) : block := Blk (A * SW) 1 (fun m => [sAND [(mu ((m mod SW + o) mod SW) (m / SW), true); (SRef 0 (m mod SW) 0, true)]]). Definition blk_Q : block := Blk A 1 (fun i => [sOR (map (fun j => (SRef 0 j 0, true)) (filter (fun j => bitof ((j + 3) mod SW) i) (seq 0 SW)))]). Definition blk_F : block := Blk (3 * A) 1 (fun m => [sOR (map (fun j => (SRef (2 + m / A) ((m mod A) * SW + j) 0, true)) (seq 0 SW))]). Definition blk_PA : block := Blk SW 1 (fun j => [sAND (lits (opb 0) j)]). Definition blk_PB : block := Blk SW 1 (fun j => [sAND (lits (opb 1) j)]). Definition blk_AC : block := Blk 1 1 (fun _ => [sAND (map (fun t => (opb 2 t, true)) (seq 0 A))]). Definition blk_W : block := Blk SW 1 (fun j => [sAND [(haltb, false); (SRef 8 j 0, true)]]). Definition blk_RX : block := Blk (A * SW) 1 (fun m => [sAND [(mu (m mod SW) (m / SW), true); (SRef 7 (m mod SW) 0, true)]]). Definition blk_RY : block := Blk (A * SW) 1 (fun m => [sAND [(mu (m mod SW) (m / SW), true); (SRef 8 (m mod SW) 0, true)]]). Definition blk_KP : block := Blk (SW * A) 1 (fun m => [sAND [(mu (m / A) (m mod A), true); (SRef 10 (m / A) 0, false)]]). Definition blk_X : block := Blk A 1 (fun t => [sOR (map (fun j => (SRef 11 (t * SW + j) 0, true)) (seq 0 SW))]). Definition blk_Y : block := Blk A 1 (fun t => [sOR (map (fun j => (SRef 12 (t * SW + j) 0, true)) (seq 0 SW))]). Definition blk_PR : block := Blk (A - 1) 1 (fun i => [sOR [(xv i, false); (yv i, true)]]). (* 17 to 15 + A: the carry terms into bit k, for k = 1 .. A - 1 *) Definition blk_T (k : nat) : block := Blk 1 (S k) (fun _ => sAND (map (fun i => (prr i, true)) (seq 0 k)) :: map (fun j => sAND ([(yv j, true); (xv j, false)] ++ map (fun i => (prr i, true)) (seq (S j) (k - S j)))) (seq 0 k)). (* tb to tb + 14: carries, equality, sum bits, branch, next counter, halt latch, next memory *) Definition blk_C : block := Blk (A - 1) 1 (fun m => [sOR ((SRef (16 + S m) 0 0, true) :: map (fun j => (SRef (16 + S m) 0 (S j), true)) (seq 0 (S m)))]). Definition blk_AX : block := Blk A 1 (fun i => [sAND [(xv i, true); (yv i, true)]]). Definition blk_NX : block := Blk A 1 (fun i => [sAND [(xv i, false); (yv i, false)]]). Definition blk_XN : block := Blk A 1 (fun i => [sOR [(SRef (tb + 1) i 0, true); (SRef (tb + 2) i 0, true)]]). Definition blk_EQ : block := Blk 1 1 (fun _ => [sAND (map (fun i => (SRef (tb + 3) i 0, true)) (seq 0 A))]). Definition blk_R0 : block := Blk 1 3 (fun _ => [sOR [(yv 0, true); (xv 0, true)]; sOR [(yv 0, false); (xv 0, false)]; sAND [(SRef (tb + 5) 0 0, true); (SRef (tb + 5) 0 1, true)]]). Definition blk_H : block := Blk (A - 1) 3 (fun m => map (fun b => SU b [(yv (S m), 1%Z); (xv (S m), (-1)%Z); (SRef tb m 0, 1%Z)]) [0%Z; (-1)%Z; (-2)%Z]). Definition blk_R : block := Blk (A - 1) 1 (fun m => [SU (-1) [(SRef (tb + 6) m 0, 1%Z); (SRef (tb + 6) m 1, (-1)%Z); (SRef (tb + 6) m 2, 1%Z)]]). Definition blk_LEQ : block := Blk 1 1 (fun _ => [SU (-1) [(SRef (tb + 6) (A - 2) 0, 1%Z); (SRef (tb + 6) (A - 2) 1, (-1)%Z); (SRef (tb + 6) (A - 2) 2, 1%Z); (SRef (tb + 4) 0 0, 1%Z)]]). Definition rbit (k : nat) : sref := if Nat.eqb k 0 then SRef (tb + 5) 0 2 else SRef (tb + 7) (k - 1) 0. Definition blk_TA : block := Blk A 1 (fun i => [sAND [(haltb, false); (SRef (tb + 8) 0 0, true); (opb 2 i, true)]]). Definition blk_TB : block := Blk A 1 (fun i => [sAND [(haltb, false); (SRef (tb + 8) 0 0, false); (SRef 5 i 0, true)]]). Definition blk_NP : block := Blk A 1 (fun i => [sOR [(SRef 1 i 0, true); (SRef (tb + 9) i 0, true); (SRef (tb + 10) i 0, true)]]). Definition blk_HAB : block := Blk 1 3 (fun _ => [sAND [(haltb, false); (SRef (tb + 8) 0 0, true); (SRef 9 0 0, true)]; sAND [(haltb, false); (SRef (tb + 8) 0 0, false); (SRef 0 (SW - 4) 0, true)]; sOR [(haltb, true); (SRef (tb + 12) 0 0, true); (SRef (tb + 12) 0 1, true)]]). Definition blk_WR : block := Blk (SW * A) 1 (fun m => [sAND [(rbit (A - 1 - m mod A), true); (SRef 10 (m / A) 0, true)]]). Definition blk_NM : block := Blk (SW * A) 1 (fun m => [sOR [(SRef 13 m 0, true); (SRef (tb + 13) m 0, true)]]). Definition hpre : list block := [blk_P; blk_HP; blk_FA 0; blk_FA 1; blk_FA 2; blk_Q; blk_F; blk_PA; blk_PB; blk_AC; blk_W; blk_RX; blk_RY; blk_KP; blk_X; blk_Y; blk_PR]. Definition hpost : list block := [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]. Definition hblocks : list block := hpre ++ map blk_T (seq 1 (A - 1)) ++ hpost. (* the unit computing the next value of each state bit *) Definition hout (i : nat) : sref := if i idx nH hblocks (hout i)) (seq 0 nH). (* ---- the machine: SUBLEQ on 2^A words of A bits, Definition 5.2 ------------------------ *) Record hst := mkH { hpc : nat; hhalt : bool; hmem : list nat }. Definition memv (s : hst) (j : nat) : nat := nth j (hmem s) 0. Definition subleq (s : hst) : hst := if hhalt s then s else let p := hpc s in let a := memv s p in let b := memv s ((p + 1) mod SW) in let c := memv s ((p + 2) mod SW) in let r := (memv s b + SW - memv s a) mod SW in let leq := Nat.eqb r 0 || Nat.leb (2 ^ (A - 1)) r in let p' := if leq then c else (p + 3) mod SW in mkH p' (Nat.eqb p' (SW - 1)) (map (fun j => if Nat.eqb j b then r else memv s j) (seq 0 SW)). (* the state bits: the counter and each word most significant bit first *) Definition wbits (v : nat) : list bool := map (bitof v) (seq 0 A). Definition encodeH (s : hst) : list bool := wbits (hpc s) ++ [hhalt s] ++ concat (map wbits (hmem s)). Definition hvalid (s : hst) : Prop := hpc s < SW /\ length (hmem s) = SW /\ Forall (fun v => v < SW) (hmem s). End Host.