summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore2
-rw-r--r--camlsim/_tags3
-rw-r--r--camlsim/machine.ml174
-rw-r--r--camlsim/netlist.ml17
-rw-r--r--camlsim/netlist_ast.ml42
-rw-r--r--camlsim/netlist_lexer.mll37
-rw-r--r--camlsim/netlist_parser.mly70
-rw-r--r--camlsim/simulator.ml67
-rw-r--r--camlsim/test/clock_div_sch.net9
-rw-r--r--camlsim/test/cm2_sch.net9
-rw-r--r--camlsim/test/fulladder_sch.net12
-rw-r--r--camlsim/test/nadder_sch.net17
-rw-r--r--camlsim/test/ram_sch.net32
13 files changed, 491 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
index ef1c47c..a9d6766 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
*/_build/*
tp1/*test.byte
tp1/test/*_sch.net
+camlsim/*.byte
+*.swp
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
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 21:44:53 +0000