diff options
Diffstat (limited to 'sched')
33 files changed, 868 insertions, 0 deletions
diff --git a/sched/_tags b/sched/_tags new file mode 100644 index 0000000..503ce62 --- /dev/null +++ b/sched/_tags @@ -0,0 +1,3 @@ +true: use_menhir +<*.ml>: debug +<*.byte>: use_unix, debug
\ No newline at end of file diff --git a/sched/graph.ml b/sched/graph.ml new file mode 100644 index 0000000..54128ff --- /dev/null +++ b/sched/graph.ml @@ -0,0 +1,61 @@ +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/sched/graph_test.byte b/sched/graph_test.byte new file mode 120000 index 0000000..1ec2e64 --- /dev/null +++ b/sched/graph_test.byte @@ -0,0 +1 @@ +/home/katchup/Core/ENS/Info/SystDigit-Projet/tp1/_build/graph_test.byte
\ No newline at end of file diff --git a/sched/graph_test.ml b/sched/graph_test.ml new file mode 100644 index 0000000..ac31677 --- /dev/null +++ b/sched/graph_test.ml @@ -0,0 +1,28 @@ +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/sched/main.byte b/sched/main.byte new file mode 120000 index 0000000..0571503 --- /dev/null +++ b/sched/main.byte @@ -0,0 +1 @@ +/home/katchup/Core/ENS/Info/SystDigit-Projet/sched/_build/main.byte
\ No newline at end of file diff --git a/sched/main.ml b/sched/main.ml new file mode 100644 index 0000000..988d1ec --- /dev/null +++ b/sched/main.ml @@ -0,0 +1,50 @@ +let simulate = ref false +let number_steps = ref (-1) +let sim_path = ref "./netlist_simulator.byte" +let dumb_down = ref false + +let compile filename = + try + let p = Netlist.read_file filename in + let out_name = (Filename.chop_suffix filename ".net") ^ "_sch.net" in + let dumb_out_name = (Filename.chop_suffix filename ".net") ^ ".dumb" in + let q = ref p in + + begin try + q := Scheduler.schedule p + with + | Scheduler.Combinational_cycle -> + Format.eprintf "The netlist has a combinatory cycle.@."; + exit 2; + end; + + let out = open_out out_name in + Netlist_printer.print_program out !q; + close_out out; + let dumb_out = open_out dumb_out_name in + Netlist_printer.print_dumb_program dumb_out !q; + close_out dumb_out; + + if !simulate then ( + let simulator = + if !number_steps = -1 then + !sim_path + else + !sim_path ^ " -n " ^ (string_of_int !number_steps) + in + ignore (Unix.system (simulator^" "^(if !dumb_down then dumb_out_name else out_name))) + ) + with + | Netlist.Parse_error s -> Format.eprintf "An error accurred: %s@." s; exit 2 + +let main () = + Arg.parse + ["-s", Arg.Set simulate, "Launch the simulator"; + "-sim", Arg.Set_string sim_path, "Path to the circuit simulator"; + "-d", Arg.Set dumb_down, "Pass the dumbed-down netlist to the simulator (for the C simulator)"; + "-n", Arg.Set_int number_steps, "Number of steps to simulate"] + compile + "" +;; + +main () diff --git a/sched/netlist.ml b/sched/netlist.ml new file mode 100644 index 0000000..b1d7932 --- /dev/null +++ b/sched/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/sched/netlist_ast.ml b/sched/netlist_ast.ml new file mode 100644 index 0000000..ae16888 --- /dev/null +++ b/sched/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/sched/netlist_lexer.mll b/sched/netlist_lexer.mll new file mode 100644 index 0000000..78b0410 --- /dev/null +++ b/sched/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/sched/netlist_parser.mly b/sched/netlist_parser.mly new file mode 100644 index 0000000..0908703 --- /dev/null +++ b/sched/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/sched/netlist_printer.ml b/sched/netlist_printer.ml new file mode 100644 index 0000000..fbd432a --- /dev/null +++ b/sched/netlist_printer.ml @@ -0,0 +1,180 @@ +open Netlist_ast +open Format + +(* GENERAL PRINTER *) + +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 "@." + + +(* PRINTER FOR DUMBED-DOWN NETLIST (variables are identified by numbers) *) + +(* constants *) +let c_arg = 0 +let c_reg = 1 +let c_not = 2 +let c_binop = 3 +let c_mux = 4 +let c_rom = 5 +let c_ram = 6 +let c_concat = 7 +let c_slice = 8 +let c_select = 9 + +let binop_i = function + | Or -> 0 + | Xor -> 1 + | And -> 2 + | Nand -> 3 + +let print_dumb_program oc p = + let ff = formatter_of_out_channel oc in + (* associate numbers to variables *) + let n_vars = Env.fold (fun _ _ n -> n+1) p.p_vars 0 in + let n = ref 0 in + let var_id = Hashtbl.create n_vars in + fprintf ff "%d\n" n_vars; + Env.iter + (fun k v -> + Hashtbl.add var_id k !n; + fprintf ff "%d %s\n" + (match v with + | TBit -> 1 + | TBitArray(n) -> n) + k; + n := !n + 1) + p.p_vars; + (* write input vars *) + fprintf ff "%d" (List.length p.p_inputs); + List.iter (fun k -> fprintf ff " %d" (Hashtbl.find var_id k)) p.p_inputs; + fprintf ff "\n"; + (* write output vars *) + fprintf ff "%d" (List.length p.p_outputs); + List.iter (fun k -> fprintf ff " %d" (Hashtbl.find var_id k)) p.p_outputs; + fprintf ff "\n"; + (* write equations *) + fprintf ff "%d\n" (List.length p.p_eqs); + (* write equations *) + let print_arg = function + | Avar(k) -> fprintf ff " %d" (Hashtbl.find var_id k) + | Aconst(n) -> fprintf ff " $"; + begin match n with + | VBit(x) -> fprintf ff "%d" (if x then 1 else 0) + | VBitArray(a) -> + let k = ref 0 in + for i = 0 to Array.length a - 1 do + k := 2 * !k + (if a.(i) then 1 else 0) + done; + fprintf ff "%d" !k + end + in + List.iter + (fun (k, eqn) -> + fprintf ff "%d " (Hashtbl.find var_id k); + begin match eqn with + | Earg(a) -> fprintf ff "%d" c_arg; + print_arg a + | Ereg(i) -> fprintf ff "%d %d" c_reg (Hashtbl.find var_id i) + | Enot(a) -> fprintf ff "%d" c_not; + print_arg a + | Ebinop(o, a, b) -> fprintf ff "%d %d" c_binop (binop_i o); + print_arg a; + print_arg b + | Emux(a, b, c) -> fprintf ff "%d" c_mux; + print_arg a; print_arg b; print_arg c + | Erom(u, v, a) -> fprintf ff "%d %d %d" c_rom u v; + print_arg a + | Eram (u, v, a, b, c, d) -> fprintf ff "%d %d %d" c_ram u v; + print_arg a; print_arg b; print_arg c; print_arg d + | Econcat(a, b) -> fprintf ff "%d" c_concat; + print_arg a; print_arg b + | Eslice(u, v, a) -> fprintf ff "%d %d %d" c_slice u v; + print_arg a + | Eselect(i, a) -> fprintf ff "%d %d" c_select i; + print_arg a + end; + fprintf ff "\n") + p.p_eqs; + (* flush *) + fprintf ff "@." + + + + diff --git a/sched/netlist_simulator.byte b/sched/netlist_simulator.byte Binary files differnew file mode 100755 index 0000000..155d39a --- /dev/null +++ b/sched/netlist_simulator.byte diff --git a/sched/scheduler.ml b/sched/scheduler.ml new file mode 100644 index 0000000..130164b --- /dev/null +++ b/sched/scheduler.ml @@ -0,0 +1,52 @@ +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/sched/test/clock_div.dumb b/sched/test/clock_div.dumb new file mode 100644 index 0000000..bcb07d0 --- /dev/null +++ b/sched/test/clock_div.dumb @@ -0,0 +1,11 @@ +3 +1 _l_2 +1 c +1 o +0 +1 2 +3 +0 1 2 +2 1 1 +1 2 0 + diff --git a/sched/test/clock_div.mj b/sched/test/clock_div.mj new file mode 100644 index 0000000..ad1e919 --- /dev/null +++ b/sched/test/clock_div.mj @@ -0,0 +1,4 @@ +main() = (o) where + o = reg(c); + c = not (reg (o)) +end where
\ No newline at end of file diff --git a/sched/test/clock_div.net b/sched/test/clock_div.net new file mode 100644 index 0000000..9a17fc7 --- /dev/null +++ b/sched/test/clock_div.net @@ -0,0 +1,9 @@ +INPUT +OUTPUT o +VAR + _l_2, c, o +IN +c = NOT _l_2 +o = REG c +_l_2 = REG o + diff --git a/sched/test/clock_div_sch.net b/sched/test/clock_div_sch.net new file mode 100644 index 0000000..0ae5cd9 --- /dev/null +++ b/sched/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/sched/test/cm2.dumb b/sched/test/cm2.dumb new file mode 100644 index 0000000..632c6ea --- /dev/null +++ b/sched/test/cm2.dumb @@ -0,0 +1,9 @@ +4 +1 _l_1 +1 r +1 s +1 x +1 3 +2 2 1 +3 + diff --git a/sched/test/cm2.mj b/sched/test/cm2.mj new file mode 100644 index 0000000..8863bf1 --- /dev/null +++ b/sched/test/cm2.mj @@ -0,0 +1,4 @@ +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/sched/test/cm2.net b/sched/test/cm2.net new file mode 100644 index 0000000..e296b96 --- /dev/null +++ b/sched/test/cm2.net @@ -0,0 +1,9 @@ +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/sched/test/cm2_sch.net b/sched/test/cm2_sch.net new file mode 100644 index 0000000..e9900d5 --- /dev/null +++ b/sched/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/sched/test/fulladder.dumb b/sched/test/fulladder.dumb new file mode 100644 index 0000000..480d04d --- /dev/null +++ b/sched/test/fulladder.dumb @@ -0,0 +1,20 @@ +9 +1 _l_1 +1 _l_3 +1 _l_4 +1 _l_5 +1 a +1 b +1 c +1 r +1 s +3 4 5 6 +2 8 7 +6 +2 3 1 4 5 +3 3 2 2 6 +1 3 2 4 5 +0 3 1 4 5 +8 3 1 0 6 +7 3 0 1 3 + diff --git a/sched/test/fulladder.mj b/sched/test/fulladder.mj new file mode 100644 index 0000000..c4b6b0e --- /dev/null +++ b/sched/test/fulladder.mj @@ -0,0 +1,4 @@ +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/sched/test/fulladder.net b/sched/test/fulladder.net new file mode 100644 index 0000000..b2271c2 --- /dev/null +++ b/sched/test/fulladder.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 +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/sched/test/fulladder_sch.net b/sched/test/fulladder_sch.net new file mode 100644 index 0000000..96fc154 --- /dev/null +++ b/sched/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/sched/test/nadder.dumb b/sched/test/nadder.dumb new file mode 100644 index 0000000..469984d --- /dev/null +++ b/sched/test/nadder.dumb @@ -0,0 +1,27 @@ +12 +1 _l_10_50 +1 _l_11_49 +1 _l_16_22 +1 _l_17_21 +1 _l_7_52 +1 _l_9_51 +1 a +1 b +1 c +1 c_n1_27 +1 o +1 s_n_26 +2 6 7 +2 10 8 +10 +3 9 0 7 +2 9 0 6 +9 0 $0 +0 3 1 2 3 +1 3 2 0 9 +5 3 2 2 3 +4 3 1 2 3 +11 3 1 4 9 +8 3 0 5 1 +10 0 11 + diff --git a/sched/test/nadder.mj b/sched/test/nadder.mj new file mode 100644 index 0000000..0c95386 --- /dev/null +++ b/sched/test/nadder.mj @@ -0,0 +1,19 @@ +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/sched/test/nadder.net b/sched/test/nadder.net new file mode 100644 index 0000000..bf87051 --- /dev/null +++ b/sched/test/nadder.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 +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/sched/test/nadder_sch.net b/sched/test/nadder_sch.net new file mode 100644 index 0000000..5602eb4 --- /dev/null +++ b/sched/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/sched/test/ram.dumb b/sched/test/ram.dumb new file mode 100644 index 0000000..74cf168 --- /dev/null +++ b/sched/test/ram.dumb @@ -0,0 +1,55 @@ +27 +1 _l_10_22 +1 _l_10_35 +1 _l_10_48 +1 _l_10_61 +1 _l_11_21 +1 _l_11_34 +1 _l_11_47 +1 _l_11_60 +3 _l_12_20 +2 _l_12_33 +1 _l_12_46 +3 _l_13_19 +2 _l_13_32 +1 _l_13_45 +3 _l_14_18 +2 _l_14_31 +1 _l_14_44 +4 _l_16 +1 _l_9_23 +1 _l_9_36 +1 _l_9_49 +1 _l_9_62 +4 c +4 o +2 ra +2 wa +1 we +4 24 26 25 22 +1 23 +23 +11 8 1 3 22 +12 8 1 2 11 +13 8 1 1 12 +3 9 0 13 +23 6 2 4 24 26 25 17 +8 8 1 3 23 +9 8 1 2 8 +10 8 1 1 9 +21 9 0 10 +7 3 2 21 3 +16 0 7 +2 9 0 12 +20 9 0 9 +6 3 2 20 2 +15 7 6 16 +1 9 0 11 +19 9 0 8 +5 3 2 19 1 +14 7 5 15 +0 9 0 22 +18 9 0 23 +4 3 2 18 0 +17 7 4 14 + diff --git a/sched/test/ram.mj b/sched/test/ram.mj new file mode 100644 index 0000000..7c4d1ed --- /dev/null +++ b/sched/test/ram.mj @@ -0,0 +1,15 @@ +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/sched/test/ram.net b/sched/test/ram.net new file mode 100644 index 0000000..ee4570a --- /dev/null +++ b/sched/test/ram.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 +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 + diff --git a/sched/test/ram_sch.net b/sched/test/ram_sch.net new file mode 100644 index 0000000..56dda0e --- /dev/null +++ b/sched/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 + |