Download rocq/Host.v from phanerozoic/threshold-computers: direct link, hf CLI and curl.
- Browser
- Download file 7.64 kB
-
https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Host.v
- Command line
-
hf download hf://phanerozoic/threshold-computers/rocq/Host.v
-
curl -L -o Host.v https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Host.v
7.64 kB
| (* 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 <? A then SRef (tb + 11) i 0 | |
| else if Nat.eqb i A then SRef (tb + 12) 0 2 | |
| else SRef (tb + 14) (i - A - 1) 0. | |
| Definition host_units : list tu := compile nH hblocks. | |
| Definition host_next : list nat := map (fun 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. | |