Simulator started.

12 files changed, 489 insertions, 0 deletions

diff --git a/camlsim/_tags b/camlsim/_tags
new file mode 100644
index 0000000..503ce62
--- /dev/null
+++ b/camlsim/_tags
@@ -0,0 +1,3 @@
+true: use_menhir
+<*.ml>: debug
+<*.byte>: use_unix, debug
\ No newline at end of file
diff --git a/camlsim/machine.ml b/camlsim/machine.ml
new file mode 100644
index 0000000..232cb08
--- /dev/null
+++ b/camlsim/machine.ml
@@ -0,0 +1,174 @@
+(* 
+	Système Digital, cours de J.Vuillemin, 2013-2013
+	Alex AUVOLAT, ENS INFO 2013
+
+	Circuit Simulator, machine simulator
+
+	ASSUMPTIONS:
+	- Only one ROM chip
+*)
+
+open Netlist_ast
+
+exception Error of string
+exception Is_not_modified
+
+let load_rom filename =
+	() (* TODO *)
+
+
+type ram_prop = int * int		(* addr size ; word size *)
+type machine = {
+	p				: program;
+	mutable vars	: value Env.t;
+	mutable regs	: value Env.t;
+	ram_chips		: ram_prop array;
+	ram				: value array array;
+}
+
+let rec two_to_the = function
+	| 0 -> 1
+	| n -> let k = (two_to_the (n/2)) in
+		if n mod 2 = 1 then 2 * k else k
+
+let create p =
+	let ram_chips = Array.of_list
+		(List.fold_left
+			(fun x (_, v) -> match v with
+			| Eram (a, w, _, _, _, _) ->
+				(a, w)::x
+			| _ -> x)
+			[]
+			p.p_eqs) in
+	let vars = Env.fold
+			(fun k v x -> 
+				Env.add k
+					(match v with
+						| TBit -> VBit(false)
+						| TBitArray(n) -> VBitArray(Array.make n false))
+					x)
+			p.p_vars
+			Env.empty in
+	{ 
+		p = p;
+		vars = vars;
+		regs = Env.empty;	(* no use putting anything at the moment *)
+		ram_chips = ram_chips;
+		ram = Array.map
+			(fun (a, w) -> Array.make (two_to_the a) (VBitArray (Array.make w false)))
+			ram_chips;
+	}
+
+let read_inputs m f =
+	List.iter
+		(fun n ->
+			m.vars <- Env.add n (f (n, Env.find n m.p.p_vars)) m.vars)
+		m.p.p_inputs
+
+let step m =
+	let get = function
+	| Avar(x) -> 
+		begin match Env.find x m.vars with
+		| VBit(x) -> VBit(x)
+		| VBitArray(u) as s ->
+			if Array.length u = 1 then VBit(u.(0)) else s
+		end
+	| Aconst(x) -> x
+	in
+	(* Load register values into dest variables *)
+	Env.iter
+		(fun k v ->
+			m.vars <- Env.add k v m.vars)
+		m.regs;
+	(* Do all the logic *)
+	List.iter
+		(fun (varname, exp) ->
+			let evaluate = function
+			| Earg(k) -> get k
+			| Ereg(_) -> raise Is_not_modified	(* do nothing, registers are handled somewhere else *)
+			| Enot(k) -> 
+				begin match get k with
+				| VBit(u) -> VBit (not u)
+				| VBitArray(u) -> VBitArray(Array.map (fun x -> not x) u)
+				end
+			| Ebinop(op, k1, k2) ->
+				let f = begin match op with
+				| Or -> (fun x y -> x || y)
+				| Xor -> (fun x y -> (x || y) && (not (x && y)))
+				| And -> (fun x y -> x && y)
+				| Nand -> (fun x y -> not (x && y))
+				end in
+				begin match get k1, get k2 with
+				| VBit(u), VBit(v) -> VBit(f u v)
+				| VBitArray(u), VBitArray(v) when Array.length u = Array.length v ->
+					let r = Array.make (Array.length u) false in
+					for i = 0 to Array.length u - 1 do
+						r.(i) <- (f u.(i) v.(i))
+					done; VBitArray(r)
+				| VBit(u), VBitArray(v) -> VBit(f u v.(0))
+				| VBitArray(u), VBit(v) -> VBit(f u.(0) v)
+				| _ -> raise (Error "Incompatible data types.")
+				end
+			| Emux (control, in0, in1) ->
+				begin match get control, get in0, get in1 with
+				| VBit(u), x, y ->
+					if u then y else x
+				| VBitArray(u), VBitArray(a), VBitArray(b)
+					when Array.length a = Array.length b
+					&& Array.length u = Array.length a ->
+					let r = Array.make (Array.length u) false in
+					for i = 0 to Array.length u - 1 do
+						r.(i) <- (if u.(i) then b.(i) else a.(i))
+					done;
+					VBitArray(r)
+				| _ -> raise (Error "Invalid data size in mux")
+				end
+			| Erom(_, w, _) -> VBitArray(Array.make w false) (* TODO *)
+			| Eram(_, _, _,_, _, _) -> raise Is_not_modified (* TODO *)
+			| Econcat(k1, k2) ->
+				let a1 = match get k1 with
+				| VBit(u) -> [|u|]
+				| VBitArray(u) -> u
+				in
+				let a2 = match get k2 with
+				| VBit(u) -> [|u|]
+				| VBitArray(u) -> u
+				in
+				VBitArray(Array.append a1 a2)
+			| Eslice (first, last, k) ->
+				begin match get k with
+				| VBit(u) when first = 0 && last = 0 -> VBit(u)
+				| VBitArray(u) ->
+					let r = Array.make (last - first) false in
+					for i = first to last - 1 do
+						r.(i - first) <- u.(i)
+					done;
+					VBitArray(u)
+				| _ -> raise (Error "Invalid slicing parameters")
+				end
+			| Eselect(id, k) ->
+				begin match get k with
+				| VBit(u) when id = 0 -> VBit(u)
+				| VBitArray(u) -> VBit(u.(id))
+				| _ -> raise (Error "Invalid select parameters")
+				end
+			in
+			try
+				m.vars <- Env.add varname (evaluate exp) m.vars
+			with Is_not_modified -> ())
+		m.p.p_eqs;
+	(* Saves register values *)
+	m.regs <- List.fold_left
+		(fun x (k, v) ->
+			match v with
+			| Ereg(n) -> Env.add k (Env.find n m.vars) x
+			| _ -> x)
+		Env.empty
+		m.p.p_eqs
+
+let print_outputs m f =
+	List.iter
+		(fun n ->
+			f (n, Env.find n m.vars))
+		m.p.p_outputs
+
diff --git a/camlsim/netlist.ml b/camlsim/netlist.ml
new file mode 100644
index 0000000..b1d7932
--- /dev/null
+++ b/camlsim/netlist.ml
@@ -0,0 +1,17 @@
+exception Parse_error of string
+
+let find_file filename =
+  try
+    open_in filename
+  with
+    | _ -> raise (Parse_error "No such file '%s'")
+
+let read_file filename =
+  let ic = find_file filename in
+  let lexbuf = Lexing.from_channel ic in
+  lexbuf.Lexing.lex_curr_p <- { lexbuf.Lexing.lex_curr_p with Lexing.pos_fname = filename };
+  try
+    Netlist_parser.program Netlist_lexer.token lexbuf
+  with
+    | e -> raise (Parse_error ("Syntax error (exception: "^(Printexc.to_string e)^")"))
+
diff --git a/camlsim/netlist_ast.ml b/camlsim/netlist_ast.ml
new file mode 100644
index 0000000..ae16888
--- /dev/null
+++ b/camlsim/netlist_ast.ml
@@ -0,0 +1,42 @@
+type ident = string
+
+module Env = struct
+  include Map.Make(struct
+    type t = ident
+    let compare = compare
+  end)
+
+  let of_list l =
+    List.fold_left (fun env (x, ty) -> add x ty env) empty l
+end
+
+type ty = TBit | TBitArray of int
+type value = VBit of bool | VBitArray of bool array
+
+type binop = Or | Xor | And | Nand
+
+type arg =
+    | Avar of ident
+    | Aconst of value
+
+type exp =
+    | Earg of arg
+    | Ereg of ident
+    | Enot of arg
+    | Ebinop of binop * arg * arg
+    | Emux of arg * arg * arg
+    | Erom of int (*addr size*) * int (*word size*) * arg (*read_addr*)
+    | Eram of int (*addr size*) * int (*word size*)
+        * arg (*read_addr*) * arg (*write_enable*)
+        * arg (*write_addr*) * arg (*data*)
+    | Econcat of arg * arg
+    | Eslice of int * int * arg
+    | Eselect of int * arg
+
+type equation = ident * exp
+
+type program =
+    { p_eqs : equation list;
+      p_inputs : ident list;
+      p_outputs : ident list;
+      p_vars : ty Env.t; }
diff --git a/camlsim/netlist_lexer.mll b/camlsim/netlist_lexer.mll
new file mode 100644
index 0000000..78b0410
--- /dev/null
+++ b/camlsim/netlist_lexer.mll
@@ -0,0 +1,37 @@
+{
+open Netlist_parser
+exception Eof
+
+let keyword_list =
+[
+  "AND", AND;
+  "CONCAT", CONCAT;
+  "IN", IN;
+  "INPUT", INPUT;
+  "MUX", MUX;
+  "NAND", NAND;
+  "NOT", NOT;
+  "OR", OR;
+  "OUTPUT", OUTPUT;
+  "RAM", RAM;
+  "REG", REG;
+  "ROM", ROM;
+  "SELECT", SELECT;
+  "SLICE", SLICE;
+  "VAR", VAR;
+  "XOR", XOR;
+]
+
+}
+
+rule token = parse
+    [' ' '\t' '\n']     { token lexbuf }     (* skip blanks *)
+  | "="            { EQUAL }
+  | ":"            { COLON }
+  | ","            { COMMA }
+  | ['0'-'9']+ as lxm { INT(int_of_string lxm) }
+  | ('_' ? ['A'-'Z' 'a'-'z']('_' ? ['A'-'Z' 'a'-'z' ''' '0'-'9']) * as id)
+      { let s = Lexing.lexeme lexbuf in
+        try List.assoc s keyword_list
+        with Not_found -> NAME id }
+  | eof            { EOF }
diff --git a/camlsim/netlist_parser.mly b/camlsim/netlist_parser.mly
new file mode 100644
index 0000000..0908703
--- /dev/null
+++ b/camlsim/netlist_parser.mly
@@ -0,0 +1,70 @@
+%{
+ open Netlist_ast
+
+ let value_of_int n =
+   let rec aux n =
+     let b =
+       match n mod 10 with
+         | 0 -> false
+         | 1 -> true
+         | i -> Format.eprintf "Unexpected: %d@." i; raise Parsing.Parse_error
+     in
+     if n < 10 then
+       [b]
+     else
+       b::(aux (n / 10))
+   in
+   match aux n with
+     | [] -> Format.eprintf "Empty list@."; raise Parsing.Parse_error
+     | [b] -> VBit b
+     | bl -> VBitArray (Array.of_list (List.rev bl))
+%}
+
+%token <int> INT
+%token <string> NAME
+%token AND MUX NAND OR RAM ROM XOR REG NOT
+%token CONCAT SELECT SLICE
+%token COLON EQUAL COMMA VAR IN INPUT OUTPUT
+%token EOF
+
+%start program             /* the entry point */
+%type <Netlist_ast.program> program
+
+%%
+program:
+  INPUT inp=separated_list(COMMA, NAME)
+    OUTPUT out=separated_list(COMMA, NAME)
+    VAR vars=separated_list(COMMA, var) IN eqs=list(equ) EOF
+    { { p_eqs = eqs; p_vars = Env.of_list vars; p_inputs = inp; p_outputs = out; } }
+
+equ:
+  x=NAME EQUAL e=exp { (x, e) }
+
+exp:
+  | a=arg { Earg a }
+  | NOT x=arg { Enot x }
+  | REG x=NAME { Ereg x }
+  | AND x=arg y=arg { Ebinop(And, x, y) }
+  | OR x=arg y=arg { Ebinop(Or, x, y) }
+  | NAND x=arg y=arg { Ebinop(Nand, x, y) }
+  | XOR x=arg y=arg { Ebinop(Xor, x, y) }
+  | MUX x=arg y=arg z=arg { Emux(x, y, z) }
+  | ROM addr=INT word=INT ra=arg
+    { Erom(addr, word, ra) }
+  | RAM addr=INT word=INT ra=arg we=arg wa=arg data=arg
+    { Eram(addr, word, ra, we, wa, data) }
+  | CONCAT x=arg y=arg
+     { Econcat(x, y) }
+  | SELECT idx=INT x=arg
+     { Eselect (idx, x) }
+  | SLICE min=INT max=INT x=arg
+     { Eslice (min, max, x) }
+
+arg:
+  | n=INT { Aconst (value_of_int n) }
+  | id=NAME { Avar id }
+
+var: x=NAME ty=ty_exp { (x, ty) }
+ty_exp:
+  | /*empty*/ { TBit }
+  | COLON n=INT { TBitArray n }
diff --git a/camlsim/simulator.ml b/camlsim/simulator.ml
new file mode 100644
index 0000000..fbb831a
--- /dev/null
+++ b/camlsim/simulator.ml
@@ -0,0 +1,67 @@
+(* 
+	Système Digital, cours de J.Vuillemin, 2013-2013
+	Alex AUVOLAT, ENS INFO 2013
+
+	Circuit Simulator, main file
+*)
+
+open Netlist_ast
+
+let num_steps = ref (-1)
+let step = ref 0
+
+let read_input = function
+	| (s, TBit) -> Format.printf "%s (1 bit) : @?" s;
+		let k = ref (read_line()) in
+		while String.length !k < 1 do
+			Format.printf "Too short. Retry : ";
+			k := read_line();
+		done;
+		VBit ((!k).[0] = '1')
+	| (s, TBitArray(n)) -> Format.printf "%s (%d bits) : @?" s n;
+		let k = ref (read_line()) in
+		while String.length !k < 1 do
+			Format.printf "Too short. Retry : ";
+			k := read_line();
+		done;
+		let r = Array.make n false in
+		for i = 0 to n-1 do
+			r.(i) <- ((!k).[i] = '1')
+		done;
+		VBitArray(r)
+
+let print_output = function
+	| (n, VBit (b)) ->
+		Format.printf "%s\t: %d@." n (if b then 1 else 0)
+	| (n, VBitArray (a)) ->
+		Format.printf "%s\t: " n;
+		for i = 0 to Array.length a - 1 do
+			Format.printf "%d" (if a.(i) then 1 else 0)
+		done;
+		Format.printf "@."
+
+let loadrun filename =
+	let p = Netlist.read_file filename in
+
+	let machine = Machine.create p in
+
+	while !num_steps > !step || !num_steps == -1 do
+		step := !step + 1;
+		Format.printf "Step #%d@." !step;
+
+		Machine.read_inputs machine read_input;
+		Machine.step machine;
+		Machine.print_outputs machine print_output
+	done
+
+let () =
+	try
+		Arg.parse
+			["-rom", Arg.String(Machine.load_rom), "Load one ROM file into the simulator (will be used by all ROM chips).";
+			 "-n", Arg.Set_int num_steps, "Number of steps to simulate"]
+			 loadrun
+			 ""
+	with
+	| Netlist.Parse_error s -> Format.eprintf "An error occurred: %s@." s; exit 2
+	| Machine.Error s -> Format.eprintf "An error occurred: %s@." s; exit 2
+		
diff --git a/camlsim/test/clock_div_sch.net b/camlsim/test/clock_div_sch.net
new file mode 100644
index 0000000..0ae5cd9
--- /dev/null
+++ b/camlsim/test/clock_div_sch.net
@@ -0,0 +1,9 @@
+INPUT 
+OUTPUT o
+VAR
+  _l_2, c, o
+IN
+_l_2 = REG o
+o = REG c
+c = NOT _l_2
+
diff --git a/camlsim/test/cm2_sch.net b/camlsim/test/cm2_sch.net
new file mode 100644
index 0000000..e9900d5
--- /dev/null
+++ b/camlsim/test/cm2_sch.net
@@ -0,0 +1,9 @@
+INPUT x
+OUTPUT s, r
+VAR
+  _l_1, r, s, x
+IN
+s = REG _l_1
+_l_1 = XOR x s
+r = AND x s
+
diff --git a/camlsim/test/fulladder_sch.net b/camlsim/test/fulladder_sch.net
new file mode 100644
index 0000000..96fc154
--- /dev/null
+++ b/camlsim/test/fulladder_sch.net
@@ -0,0 +1,12 @@
+INPUT a, b, c
+OUTPUT s, r
+VAR
+  _l_1, _l_3, _l_4, _l_5, a, b, c, r, s
+IN
+_l_4 = XOR a b
+_l_5 = AND _l_4 c
+_l_3 = AND a b
+_l_1 = XOR a b
+s = XOR _l_1 c
+r = OR _l_3 _l_5
+
diff --git a/camlsim/test/nadder_sch.net b/camlsim/test/nadder_sch.net
new file mode 100644
index 0000000..5602eb4
--- /dev/null
+++ b/camlsim/test/nadder_sch.net
@@ -0,0 +1,17 @@
+INPUT a, b
+OUTPUT o, c
+VAR
+  _l_10_50, _l_11_49, _l_16_22, _l_17_21, _l_7_52, _l_9_51, a, b, c, 
+  c_n1_27, o, s_n_26
+IN
+_l_17_21 = SELECT 0 b
+_l_16_22 = SELECT 0 a
+c_n1_27 = 0
+_l_10_50 = XOR _l_16_22 _l_17_21
+_l_11_49 = AND _l_10_50 c_n1_27
+_l_9_51 = AND _l_16_22 _l_17_21
+_l_7_52 = XOR _l_16_22 _l_17_21
+s_n_26 = XOR _l_7_52 c_n1_27
+c = OR _l_9_51 _l_11_49
+o = s_n_26
+
diff --git a/camlsim/test/ram_sch.net b/camlsim/test/ram_sch.net
new file mode 100644
index 0000000..56dda0e
--- /dev/null
+++ b/camlsim/test/ram_sch.net
@@ -0,0 +1,32 @@
+INPUT ra, we, wa, c
+OUTPUT o
+VAR
+  _l_10_22, _l_10_35, _l_10_48, _l_10_61, _l_11_21, _l_11_34, _l_11_47, 
+  _l_11_60, _l_12_20 : 3, _l_12_33 : 2, _l_12_46 : 1, _l_13_19 : 3, _l_13_32 : 2, 
+  _l_13_45 : 1, _l_14_18 : 3, _l_14_31 : 2, _l_14_44 : 1, _l_16 : 4, 
+  _l_9_23, _l_9_36, _l_9_49, _l_9_62, c : 4, o : 4, ra : 2, wa : 2, we
+IN
+_l_13_19 = SLICE 1 3 c
+_l_13_32 = SLICE 1 2 _l_13_19
+_l_13_45 = SLICE 1 1 _l_13_32
+_l_10_61 = SELECT 0 _l_13_45
+o = RAM 2 4 ra we wa _l_16
+_l_12_20 = SLICE 1 3 o
+_l_12_33 = SLICE 1 2 _l_12_20
+_l_12_46 = SLICE 1 1 _l_12_33
+_l_9_62 = SELECT 0 _l_12_46
+_l_11_60 = AND _l_9_62 _l_10_61
+_l_14_44 = _l_11_60
+_l_10_48 = SELECT 0 _l_13_32
+_l_9_49 = SELECT 0 _l_12_33
+_l_11_47 = AND _l_9_49 _l_10_48
+_l_14_31 = CONCAT _l_11_47 _l_14_44
+_l_10_35 = SELECT 0 _l_13_19
+_l_9_36 = SELECT 0 _l_12_20
+_l_11_34 = AND _l_9_36 _l_10_35
+_l_14_18 = CONCAT _l_11_34 _l_14_31
+_l_10_22 = SELECT 0 c
+_l_9_23 = SELECT 0 o
+_l_11_21 = AND _l_9_23 _l_10_22
+_l_16 = CONCAT _l_11_21 _l_14_18
+