diff options
Diffstat (limited to 'tp1')
-rw-r--r-- | tp1/_tags | 3 | ||||
-rw-r--r-- | tp1/graph.ml | 61 | ||||
-rw-r--r-- | tp1/graph_test.ml | 28 | ||||
-rw-r--r-- | tp1/netlist.ml | 17 | ||||
-rw-r--r-- | tp1/netlist_ast.ml | 42 | ||||
-rw-r--r-- | tp1/netlist_lexer.mll | 37 | ||||
-rw-r--r-- | tp1/netlist_parser.mly | 70 | ||||
-rw-r--r-- | tp1/netlist_printer.ml | 82 | ||||
-rwxr-xr-x | tp1/netlist_simulator.byte | bin | 190274 -> 0 bytes | |||
-rw-r--r-- | tp1/scheduler.ml | 52 | ||||
-rw-r--r-- | tp1/scheduler_test.ml | 41 | ||||
-rw-r--r-- | tp1/test/clock_div.mj | 4 | ||||
-rw-r--r-- | tp1/test/clock_div.net | 9 | ||||
-rw-r--r-- | tp1/test/cm2.mj | 4 | ||||
-rw-r--r-- | tp1/test/cm2.net | 9 | ||||
-rw-r--r-- | tp1/test/fulladder.mj | 4 | ||||
-rw-r--r-- | tp1/test/fulladder.net | 12 | ||||
-rw-r--r-- | tp1/test/nadder.mj | 19 | ||||
-rw-r--r-- | tp1/test/nadder.net | 17 | ||||
-rw-r--r-- | tp1/test/ram.mj | 15 | ||||
-rw-r--r-- | tp1/test/ram.net | 32 |
21 files changed, 0 insertions, 558 deletions
diff --git a/tp1/_tags b/tp1/_tags deleted file mode 100644 index 503ce62..0000000 --- a/tp1/_tags +++ /dev/null @@ -1,3 +0,0 @@ -true: use_menhir -<*.ml>: debug -<*.byte>: use_unix, debug
\ No newline at end of file diff --git a/tp1/graph.ml b/tp1/graph.ml deleted file mode 100644 index 54128ff..0000000 --- a/tp1/graph.ml +++ /dev/null @@ -1,61 +0,0 @@ -exception Cycle -type mark = NotVisited | InProgress | Visited - -type 'a graph = - { mutable g_nodes : 'a node list } -and 'a node = { - n_label : 'a; - mutable n_mark : mark; - mutable n_link_to : 'a node list; - mutable n_linked_by : 'a node list; -} - -let mk_graph () = { g_nodes = [] } - -let add_node g x = - let n = { n_label = x; n_mark = NotVisited; n_link_to = []; n_linked_by = [] } in - g.g_nodes <- n::g.g_nodes - -let node_for_label g x = - List.find (fun n -> n.n_label = x) g.g_nodes - -let add_edge g id1 id2 = - let n1 = node_for_label g id1 in - let n2 = node_for_label g id2 in - n1.n_link_to <- n2::n1.n_link_to; - n2.n_linked_by <- n1::n2.n_linked_by - -let clear_marks g = - List.iter (fun n -> n.n_mark <- NotVisited) g.g_nodes - -let find_roots g = - List.filter (fun n -> n.n_linked_by = []) g.g_nodes - -let has_cycle g = - clear_marks g; - let rec visit n = - match n.n_mark with - | InProgress -> true - | Visited -> false - | NotVisited -> - n.n_mark <- InProgress; - let ret = List.fold_left (fun x n -> x || (visit n)) false n.n_link_to in - n.n_mark <- Visited; - ret - in - let ret = List.fold_left (fun x n -> x || (if n.n_mark = Visited then false else visit n)) false g.g_nodes - in clear_marks g; ret;; - -let topological g = - clear_marks g; - let rec aux acc n = - if n.n_mark = Visited - then acc - else begin - n.n_mark <- Visited; - n.n_label :: (List.fold_left (fun x n -> aux x n) acc n.n_linked_by) - end - in - let ret = List.fold_left (fun x n -> aux x n) [] g.g_nodes - in clear_marks g; List.rev ret;; - diff --git a/tp1/graph_test.ml b/tp1/graph_test.ml deleted file mode 100644 index ac31677..0000000 --- a/tp1/graph_test.ml +++ /dev/null @@ -1,28 +0,0 @@ -open Graph - -let rec check l = match l with - | [] | [_] -> true - | s1::s2::l -> (String.length s1 <= String.length s2) && (check (s2::l)) - -let test_good () = - let g = mk_graph () in - add_node g "1"; add_node g "21"; add_node g "22"; add_node g "333"; - add_edge g "1" "21"; add_edge g "1" "22"; - add_edge g "21" "333"; add_edge g "22" "333"; - let l = topological g in - print_string "Test: Tri topologique --> "; - if check l then print_endline "OK" else print_endline "FAIL"; - List.iter print_endline l; - print_newline () - -let test_cycle () = - let g = mk_graph () in - add_node g "1"; add_node g "2"; add_node g "3"; - add_edge g "1" "2"; add_edge g "2" "3"; add_edge g "3" "1"; - print_string "Test: Detection de cycle --> "; - if has_cycle g then print_endline "OK" else print_endline "FAIL" -;; - -test_cycle ();; -test_good ();; - diff --git a/tp1/netlist.ml b/tp1/netlist.ml deleted file mode 100644 index b1d7932..0000000 --- a/tp1/netlist.ml +++ /dev/null @@ -1,17 +0,0 @@ -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/tp1/netlist_ast.ml b/tp1/netlist_ast.ml deleted file mode 100644 index ae16888..0000000 --- a/tp1/netlist_ast.ml +++ /dev/null @@ -1,42 +0,0 @@ -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/tp1/netlist_lexer.mll b/tp1/netlist_lexer.mll deleted file mode 100644 index 78b0410..0000000 --- a/tp1/netlist_lexer.mll +++ /dev/null @@ -1,37 +0,0 @@ -{ -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/tp1/netlist_parser.mly b/tp1/netlist_parser.mly deleted file mode 100644 index 0908703..0000000 --- a/tp1/netlist_parser.mly +++ /dev/null @@ -1,70 +0,0 @@ -%{ - 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/tp1/netlist_printer.ml b/tp1/netlist_printer.ml deleted file mode 100644 index d513137..0000000 --- a/tp1/netlist_printer.ml +++ /dev/null @@ -1,82 +0,0 @@ -open Netlist_ast -open Format - -let rec print_env print lp sep rp ff env = - let first = ref true in - fprintf ff "%s" lp; - Env.iter - (fun x ty -> - if !first then - (first := false; fprintf ff "%a" print (x, ty)) - else - fprintf ff "%s%a" sep print (x, ty)) env; - fprintf ff "%s" rp - -let rec print_list print lp sep rp ff = function - | [] -> () - | x :: l -> - fprintf ff "%s%a" lp print x; - List.iter (fprintf ff "%s %a" sep print) l; - fprintf ff "%s" rp - -let print_ty ff ty = match ty with - | TBit -> () - | TBitArray n -> fprintf ff " : %d" n - -let print_bool ff b = - if b then - fprintf ff "1" - else - fprintf ff "0" - -let print_value ff v = match v with - | VBit b -> print_bool ff b - | VBitArray a -> Array.iter (print_bool ff) a - -let print_arg ff arg = match arg with - | Aconst v -> print_value ff v - | Avar id -> fprintf ff "%s" id - -let print_op ff op = match op with - | And -> fprintf ff "AND" - | Nand -> fprintf ff "NAND" - | Or -> fprintf ff "OR" - | Xor -> fprintf ff "XOR" - -let print_exp ff e = match e with - | Earg a -> print_arg ff a - | Ereg x -> fprintf ff "REG %s" x - | Enot x -> fprintf ff "NOT %a" print_arg x - | Ebinop(op, x, y) -> fprintf ff "%a %a %a" print_op op print_arg x print_arg y - | Emux (c, x, y) -> fprintf ff "MUX %a %a %a " print_arg c print_arg x print_arg y - | Erom (addr, word, ra) -> fprintf ff "ROM %d %d %a" addr word print_arg ra - | Eram (addr, word, ra, we, wa, data) -> - fprintf ff "RAM %d %d %a %a %a %a" addr word - print_arg ra print_arg we - print_arg wa print_arg data - | Eselect (idx, x) -> fprintf ff "SELECT %d %a" idx print_arg x - | Econcat (x, y) -> fprintf ff "CONCAT %a %a" print_arg x print_arg y - | Eslice (min, max, x) -> fprintf ff "SLICE %d %d %a" min max print_arg x - -let print_eq ff (x, e) = - fprintf ff "%s = %a@." x print_exp e - -let print_var ff (x, ty) = - fprintf ff "@[%s%a@]" x print_ty ty - -let print_vars ff env = - fprintf ff "@[<v 2>VAR@,%a@]@.IN@," - (print_env print_var "" ", " "") env - -let print_idents ff ids = - let print_ident ff s = fprintf ff "%s" s in - print_list print_ident """,""" ff ids - -let print_program oc p = - let ff = formatter_of_out_channel oc in - fprintf ff "INPUT %a@." print_idents p.p_inputs; - fprintf ff "OUTPUT %a@." print_idents p.p_outputs; - print_vars ff p.p_vars; - List.iter (print_eq ff) p.p_eqs; - (* flush *) - fprintf ff "@." diff --git a/tp1/netlist_simulator.byte b/tp1/netlist_simulator.byte Binary files differdeleted file mode 100755 index 155d39a..0000000 --- a/tp1/netlist_simulator.byte +++ /dev/null diff --git a/tp1/scheduler.ml b/tp1/scheduler.ml deleted file mode 100644 index 130164b..0000000 --- a/tp1/scheduler.ml +++ /dev/null @@ -1,52 +0,0 @@ -open Netlist_ast - -module Smap = Map.Make(String) - -exception Combinational_cycle - -let read_exp eq = - let add_arg x l = match x with - | Avar(f) -> f::l - | Aconst(_) -> l - in - let aux = function - | Earg(x) -> add_arg x [] - | Ereg(i) -> [] - | Enot(x) -> add_arg x [] - | Ebinop(_, x, y) -> add_arg x (add_arg y []) - | Emux(a, b, c) -> add_arg a (add_arg b (add_arg c [])) - | Erom(_, _, a) -> add_arg a [] - | Eram(_, _, a, b, c, d) -> [] - | Econcat(u, v) -> add_arg u (add_arg v []) - | Eslice(_, _, a) -> add_arg a [] - | Eselect(_, a) -> add_arg a [] - in - aux eq;; - -let schedule p = - let graph = Graph.mk_graph() in - let eq_map = List.fold_left (fun x (vn, eqn) -> Smap.add vn eqn x) Smap.empty p.p_eqs in - (* Add variables as graph nodes *) - List.iter (fun (k, _) -> Graph.add_node graph k) p.p_eqs; - (* Add dependencies as graph edges *) - List.iter - (fun (n, e) -> List.iter - (fun m -> if Smap.mem m eq_map then Graph.add_edge graph m n else ()) - (read_exp e)) - p.p_eqs; - (* Verify there are no cycles *) - if Graph.has_cycle graph then raise Combinational_cycle; - (* Topological sort of graph nodes *) - let topo_vars = Graph.topological graph in - (* Construct new program with sorted expression list *) - { - p_eqs = List.fold_right - (fun n x -> if Smap.mem n eq_map then (n, Smap.find n eq_map)::x else x) topo_vars []; - p_inputs = p.p_inputs; - p_outputs = p.p_outputs; - p_vars = p.p_vars; - } - ;; - - - diff --git a/tp1/scheduler_test.ml b/tp1/scheduler_test.ml deleted file mode 100644 index 20c20f5..0000000 --- a/tp1/scheduler_test.ml +++ /dev/null @@ -1,41 +0,0 @@ -let print_only = ref false -let number_steps = ref (-1) - -let compile filename = - try - let p = Netlist.read_file filename in - let out_name = (Filename.chop_suffix filename ".net") ^ "_sch.net" in - let out = open_out out_name in - let close_all () = - close_out out - in - begin try - let p = Scheduler.schedule p in - Netlist_printer.print_program out p; - with - | Scheduler.Combinational_cycle -> - Format.eprintf "The netlist has a combinatory cycle.@."; - close_all (); exit 2 - end; - close_all (); - if not !print_only then ( - let simulator = - if !number_steps = -1 then - "./netlist_simulator.byte" - else - "./netlist_simulator.byte -n "^(string_of_int !number_steps) - in - ignore (Unix.system (simulator^" "^out_name)) - ) - with - | Netlist.Parse_error s -> Format.eprintf "An error accurred: %s@." s; exit 2 - -let main () = - Arg.parse - ["-print", Arg.Set print_only, "Only print the result of scheduling"; - "-n", Arg.Set_int number_steps, "Number of steps to simulate"] - compile - "" -;; - -main () diff --git a/tp1/test/clock_div.mj b/tp1/test/clock_div.mj deleted file mode 100644 index ad1e919..0000000 --- a/tp1/test/clock_div.mj +++ /dev/null @@ -1,4 +0,0 @@ -main() = (o) where - o = reg(c); - c = not (reg (o)) -end where
\ No newline at end of file diff --git a/tp1/test/clock_div.net b/tp1/test/clock_div.net deleted file mode 100644 index 9a17fc7..0000000 --- a/tp1/test/clock_div.net +++ /dev/null @@ -1,9 +0,0 @@ -INPUT -OUTPUT o -VAR - _l_2, c, o -IN -c = NOT _l_2 -o = REG c -_l_2 = REG o - diff --git a/tp1/test/cm2.mj b/tp1/test/cm2.mj deleted file mode 100644 index 8863bf1..0000000 --- a/tp1/test/cm2.mj +++ /dev/null @@ -1,4 +0,0 @@ -main(x) = (s, r) where - s = reg (x xor s); - r = x and s -end where
\ No newline at end of file diff --git a/tp1/test/cm2.net b/tp1/test/cm2.net deleted file mode 100644 index e296b96..0000000 --- a/tp1/test/cm2.net +++ /dev/null @@ -1,9 +0,0 @@ -INPUT x -OUTPUT s, r -VAR - _l_1, r, s, x -IN -r = AND x s -s = REG _l_1 -_l_1 = XOR x s - diff --git a/tp1/test/fulladder.mj b/tp1/test/fulladder.mj deleted file mode 100644 index c4b6b0e..0000000 --- a/tp1/test/fulladder.mj +++ /dev/null @@ -1,4 +0,0 @@ -main(a,b,c) = (s, r) where - s = (a xor b) xor c; - r = (a and b) or ((a xor b) and c); -end where
\ No newline at end of file diff --git a/tp1/test/fulladder.net b/tp1/test/fulladder.net deleted file mode 100644 index b2271c2..0000000 --- a/tp1/test/fulladder.net +++ /dev/null @@ -1,12 +0,0 @@ -INPUT a, b, c -OUTPUT s, r -VAR - _l_1, _l_3, _l_4, _l_5, a, b, c, r, s -IN -r = OR _l_3 _l_5 -s = XOR _l_1 c -_l_1 = XOR a b -_l_3 = AND a b -_l_4 = XOR a b -_l_5 = AND _l_4 c - diff --git a/tp1/test/nadder.mj b/tp1/test/nadder.mj deleted file mode 100644 index 0c95386..0000000 --- a/tp1/test/nadder.mj +++ /dev/null @@ -1,19 +0,0 @@ -fulladder(a,b,c) = (s, r) where - s = (a ^ b) ^ c; - r = (a & b) + ((a ^ b) & c); -end where - -adder<n>(a:[n], b:[n], c_in) = (o:[n], c_out) where - if n = 0 then - o = []; - c_out = 0 - else - (s_n1, c_n1) = adder<n-1>(a[1..], b[1..], c_in); - (s_n, c_out) = fulladder(a[0], b[0], c_n1); - o = s_n . s_n1 - end if -end where - -main(a, b) = (o, c) where - (o, c) = adder<1>(a,b,0) -end where
\ No newline at end of file diff --git a/tp1/test/nadder.net b/tp1/test/nadder.net deleted file mode 100644 index bf87051..0000000 --- a/tp1/test/nadder.net +++ /dev/null @@ -1,17 +0,0 @@ -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 -o = s_n_26 -c = OR _l_9_51 _l_11_49 -s_n_26 = XOR _l_7_52 c_n1_27 -_l_7_52 = XOR _l_16_22 _l_17_21 -_l_9_51 = AND _l_16_22 _l_17_21 -_l_10_50 = XOR _l_16_22 _l_17_21 -_l_11_49 = AND _l_10_50 c_n1_27 -c_n1_27 = 0 -_l_16_22 = SELECT 0 a -_l_17_21 = SELECT 0 b - diff --git a/tp1/test/ram.mj b/tp1/test/ram.mj deleted file mode 100644 index 7c4d1ed..0000000 --- a/tp1/test/ram.mj +++ /dev/null @@ -1,15 +0,0 @@ -const addr = 2 -const word = 4 - -or_n<n>(a:[n],b:[n]) = (o:[n]) where - if n = 0 then - o = [] - else - o = (a[0] and b[0]).(or_n<n-1>(a[1..], b[1..])) - end if -end where - -main(ra:[addr], we, wa:[addr], c:[word]) = (o:[word]) where - o = ram<addr, word>(ra, we, wa, or_n<word>(o, c)) -end where - diff --git a/tp1/test/ram.net b/tp1/test/ram.net deleted file mode 100644 index ee4570a..0000000 --- a/tp1/test/ram.net +++ /dev/null @@ -1,32 +0,0 @@ -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 -o = RAM 2 4 ra we wa _l_16 -_l_16 = CONCAT _l_11_21 _l_14_18 -_l_9_23 = SELECT 0 o -_l_10_22 = SELECT 0 c -_l_11_21 = AND _l_9_23 _l_10_22 -_l_12_20 = SLICE 1 3 o -_l_13_19 = SLICE 1 3 c -_l_14_18 = CONCAT _l_11_34 _l_14_31 -_l_9_36 = SELECT 0 _l_12_20 -_l_10_35 = SELECT 0 _l_13_19 -_l_11_34 = AND _l_9_36 _l_10_35 -_l_12_33 = SLICE 1 2 _l_12_20 -_l_13_32 = SLICE 1 2 _l_13_19 -_l_14_31 = CONCAT _l_11_47 _l_14_44 -_l_9_49 = SELECT 0 _l_12_33 -_l_10_48 = SELECT 0 _l_13_32 -_l_11_47 = AND _l_9_49 _l_10_48 -_l_12_46 = SLICE 1 1 _l_12_33 -_l_13_45 = SLICE 1 1 _l_13_32 -_l_14_44 = _l_11_60 -_l_9_62 = SELECT 0 _l_12_46 -_l_10_61 = SELECT 0 _l_13_45 -_l_11_60 = AND _l_9_62 _l_10_61 - |