From ffe6e387ff1d029e5502291b8ba4ece75c2583cf Mon Sep 17 00:00:00 2001 From: Bernhard Urban Date: Mon, 24 May 2010 19:34:20 +0200 Subject: [PATCH] alu: weniger logic elemente dafuer mehr taktzyklen noetig (= egal) logic elements: 3002 -> 2715 --- src/alu.vhd | 186 +++++++++++++++++++------------------------- src/beh_alu_tb.do | 5 -- src/beh_alu_tb.vhd | 2 + src/post_alu_tb.vhd | 2 + 4 files changed, 83 insertions(+), 112 deletions(-) diff --git a/src/alu.vhd b/src/alu.vhd index b6211ba..09097e5 100644 --- a/src/alu.vhd +++ b/src/alu.vhd @@ -4,8 +4,7 @@ use ieee.numeric_std.all; use work.gen_pkg.all; entity alu is - port - ( + port ( sys_clk : in std_logic; sys_res_n : in std_logic; opcode : in alu_ops; @@ -20,14 +19,15 @@ entity alu is end entity alu; architecture beh of alu is - type ALU_STATE is (SIDLE, SADD, SSUB, SMUL, SDIV, SDIV_CALC, SDONE, SERROR); + type ALU_STATE is (SIDLE, SADD, SSUB, SMUL, SDIV, SDIV_SHIFT_TO_MSB, + SDIV_CALC, SDIV_DONE, SDONE, SERROR); signal state_int, state_next : ALU_STATE; signal op3_int, op3_next, opM_int, opM_next : csigned; signal calc_done_int, calc_done_next : std_logic; signal calc_error_int, calc_error_next : std_logic; -- signale fuer division - signal dividend_msb_int, dividend_msb_next, laengediv_int, laengediv_next : divinteger; - signal quo_int, quo_next, aktdiv_int, aktdiv_int_next, op1_int, op1_next, op2_int, op2_next : csigned; + signal laengediv_int, laengediv_next : divinteger; + signal quo_int, quo_next, op1_int, op1_next, op2_int, op2_next : csigned; signal sign_int, sign_next : std_logic; begin op3 <= op3_int; @@ -45,10 +45,8 @@ begin calc_done_int <= '0'; calc_error_int <= '0'; --div - dividend_msb_int <= (others => '0'); laengediv_int <= (others => '0'); quo_int <= (others => '0'); - aktdiv_int <= (others => '0'); op1_int <= (others => '0'); op2_int <= (others => '0'); sign_int <= '0'; @@ -59,10 +57,8 @@ begin calc_done_int <= calc_done_next; calc_error_int <= calc_error_next; -- div - dividend_msb_int <= dividend_msb_next; laengediv_int <= laengediv_next; quo_int <= quo_next; - aktdiv_int <= aktdiv_int_next; op1_int <= op1_next; op2_int <= op2_next; sign_int <= sign_next; @@ -70,82 +66,36 @@ begin end process; -- next state & out - process(opcode, do_calc, state_int, op1, op2, dividend_msb_int, - laengediv_int, quo_int, aktdiv_int, sign_int, op1_int, op2_int, - op3_int, opM_int) - -- http://www.velocityreviews.com/forums/showpost.php?p=137148&postcount=5 - function find_msb(a : std_logic_vector) return std_logic_vector is - function bits_to_fit(n : positive) return natural is - variable nn, bits : natural := 0; - begin - nn := n; - while nn > 0 loop - bits := bits + 1; - nn := nn/2; - end loop; - return bits; - end; - - function or_all(p : std_logic_vector) return std_logic is - variable r : std_logic; - begin - r := '0'; - for i in p'range loop - r := r or p(i); - end loop; - return r; - end; - - constant wN : positive := bits_to_fit(a'length - 1); - constant wP : positive := 2 ** wN; - variable pv : std_logic_vector(wP-1 downto 0); - variable n : std_logic_vector(wN downto 1); - begin - if a'length <= 2 then - n(n'right) := a(a'left); - else - pv(a'length-1 downto 0) := a; - if or_all(pv(wP-1 downto wP/2)) = '1' then - n := '1' & find_msb((pv(wP-1 downto wP/2))); - else - n := '0' & find_msb((pv(wP/2-1 downto 0))); - end if; - end if; - return n; - end function find_msb; - -- -- alternativ: eleganter, braucht aber mehr logic cells - -- for i in (CBITS-1) downto 0 loop - -- exit when a(i) = '1'; - -- r := r+1; - -- end loop; - -- return (CBITS - r); - + process(opcode, do_calc, state_int, op1, op2, laengediv_int, quo_int, + sign_int, op1_int, op2_int, op3_int, opM_int) variable multmp : signed(((2*CBITS)-1) downto 0); variable mulsign : std_logic; variable tmp : csigned; -- vars fuer div - variable laengediv_var, dividend_msb_var, divtmp : divinteger; - variable aktdiv_int_var, quo_var, op1_var, op2_var : csigned; + variable laengediv_var, divtmp : divinteger; + variable aktdiv_int_var, op1_var, op2_var : csigned; + variable quobit : std_logic; begin calc_done_next <= '0'; calc_error_next <= '0'; -- default fuer div - dividend_msb_next <= (others => '0'); - laengediv_next <= (others => '0'); - quo_next <= (others => '0'); - aktdiv_int_next <= aktdiv_int; - op1_next <= (others => '0'); - op2_next <= (others => '0'); - sign_next <= '0'; + laengediv_next <= laengediv_int; + quo_next <= quo_int; + op1_next <= op1_int; + op2_next <= op2_int; + sign_next <= sign_int; op3_next <= op3_int; opM_next <= opM_int; + -- set a default value for next state state_next <= state_int; -- next state berechnen case state_int is when SIDLE => - aktdiv_int_next <= (others => '0'); - -- opM_next <= (others => '0'); + sign_next <= '0'; + op1_next <= (others => '0'); + op2_next <= (others => '0'); + opM_next <= (others => '0'); if do_calc = '1' then case opcode is @@ -189,8 +139,10 @@ begin state_next <= SERROR; end if; when SDIV => - -- division implementiert nach ~hwmod/doc/division.pdf - if ((op1 = x"80000000" and op2 = to_signed(-1, CBITS)) or op2 = to_signed(0, CBITS)) then + -- modifizierte binaere division nach ~hwmod/doc/division.pdf + + -- division durch 0 checken + if op2 = to_signed(0, CBITS) then state_next <= SERROR; else -- sign check @@ -203,61 +155,81 @@ begin op2_var := (not op2_var) + 1; end if; - dividend_msb_var := divinteger(find_msb(std_logic_vector(op1_var)))-1; - laengediv_var := divinteger(find_msb(std_logic_vector(op2_var)))-1; - - aktdiv_int_next <= op1_var srl to_integer(dividend_msb_var - laengediv_var + 1); - + state_next <= SDONE; -- anmerkung: xst (xilinx) kann folgende zeile nicht uebersetzen -- > if op1 = to_signed(-2147483648, CBITS) then -- darum folgende schreibweise -> - state_next <= SDONE; if op1 = x"80000000" then - -- so ziemlich das boeseste was passieren kann - op3_next <= to_signed(-214748364,CBITS); - opM_next <= to_signed(8,CBITS); + if op2 = to_signed(10,CBITS) then + -- so ziemlich das boeseste was passieren kann + -- deswegen, weil divisor und dividend in positive + -- zahlen umgewandelt werden. + -- daher: hardcodiertes ergebnis fuer division durch 10 (fuer parser) + op3_next <= to_signed(-214748364,CBITS); + opM_next <= to_signed(8,CBITS); + else + -- sonst fehler.. + state_next <= SERROR; + end if; elsif (op1_var < op2_var) then + -- => man braucht nix grossartiges rechnen op3_next <= to_signed(0,CBITS); opM_next <= op1_var; else - state_next <= SDIV_CALC; - dividend_msb_next <= dividend_msb_var; - laengediv_next <= laengediv_var; + -- spannend! signale initialisieren fuer den naechsten schritt + state_next <= SDIV_SHIFT_TO_MSB; + laengediv_next <= (others => '0'); quo_next <= (others => '0'); op1_next <= op1_var; op2_next <= op2_var; sign_next <= op1(CBITS-1) xor op2(CBITS-1); end if; end if; + when SDIV_SHIFT_TO_MSB => + -- shifte divisor so lange nach links, bis MSB = '1' ist + if op2_int(CBITS-1) = '1' then + state_next <= SDIV_CALC; + else + -- und mitzaehlen wie oft geshiftet wurde + laengediv_next <= laengediv_int + 1; + op2_next <= op2_int sll 1; + end if; when SDIV_CALC => - divtmp := dividend_msb_int - laengediv_int + 1; + multmp := (others => '0'); + multmp(CBITS downto 0) := signed('0' & std_logic_vector(op1_int)) - signed('0' & std_logic_vector(op2_int)); - if divtmp > 0 then - aktdiv_int_var := aktdiv_int sll 1; - aktdiv_int_var(0) := op1_int(to_integer(divtmp) - 1); + -- beim sign bit sieht man ob sich op2_int in op1_int ausging oder nicht + -- es muss daher negiert werden + quobit := not multmp(CBITS); - quo_var := quo_int sll 1; - if aktdiv_int_var >= op2_int then - quo_var(0) := '1'; - aktdiv_int_var := aktdiv_int_var - op2_int; - end if; + -- ergebnis dieser runde uebernehmen + quo_next <= quo_int(CBITS-2 downto 0) & quobit; - quo_next <= quo_var; - aktdiv_int_next <= aktdiv_int_var; - dividend_msb_next <= dividend_msb_int; - laengediv_next <= laengediv_int + 1; - op1_next <= op1_int; - op2_next <= op2_int; - sign_next <= sign_int; + -- wenn es sich ausging, soll neuer dividend uebernommen werden + if quobit = '1' then + op1_next <= multmp(CBITS-1 downto 0); + end if; + + laengediv_next <= laengediv_int - 1; + -- divisor nach rechts shiften + op2_next <= op2_int srl 1; + + -- wenn laengediv_int in *dieser* runde =0 ist dann ist man + -- fertig, weil man braucht (runden zum shiften + 1) runden zum + -- berechnen des eregbnisses + if laengediv_int = 0 then + state_next <= SDIV_DONE; + end if; + when SDIV_DONE => + if sign_int = '1' then + op3_next <= (not quo_int) + 1; else - if sign_int = '1' then - op3_next <= (not quo_int) + 1; - else - op3_next <= quo_int; - end if; - opM_next <= aktdiv_int; - state_next <= SDONE; + op3_next <= quo_int; end if; + -- wichtig: rest nur fuer postive paare gueltig! + -- (fuer unsere zwecke ausreichend) + opM_next <= op1_int; + state_next <= SDONE; when SDONE | SERROR => calc_done_next <= '1'; if state_int = SERROR then diff --git a/src/beh_alu_tb.do b/src/beh_alu_tb.do index a3a70ed..37e98cd 100644 --- a/src/beh_alu_tb.do +++ b/src/beh_alu_tb.do @@ -30,11 +30,6 @@ delete wave /beh_alu_tb/inst/quo_int delete wave /beh_alu_tb/inst/quo_next add wave -radix decimal inst/quo_int -delete wave /beh_alu_tb/inst/aktdiv_int -delete wave /beh_alu_tb/inst/aktdiv_int_next -add wave -radix decimal inst/aktdiv_int - - #rauszoomen wave zoomout 500.0 diff --git a/src/beh_alu_tb.vhd b/src/beh_alu_tb.vhd index 15bb002..f6c6d5b 100644 --- a/src/beh_alu_tb.vhd +++ b/src/beh_alu_tb.vhd @@ -119,6 +119,8 @@ begin 61 => (-2147483647, ALU_SUB, 1, 0, -2147483648, false), 62 => (-2147483647, ALU_ADD, -1, 0, -2147483648, false), 63 => (-2147483648, ALU_DIV, 10, 8, -214748364, false), + 64 => (-214748364, ALU_DIV, 10, 4, -21474836, false), + 65 => (1, ALU_DIV, -2147483648, 1, 0, false), others => (0, ALU_ADD, 0, 0, 0, false) ); variable checkall : boolean := true; diff --git a/src/post_alu_tb.vhd b/src/post_alu_tb.vhd index cf1da2d..ce4bcc3 100644 --- a/src/post_alu_tb.vhd +++ b/src/post_alu_tb.vhd @@ -136,6 +136,8 @@ begin 61 => (-2147483647, ALU_SUB, 1, 0, -2147483648, false), 62 => (-2147483647, ALU_ADD, -1, 0, -2147483648, false), 63 => (-2147483648, ALU_DIV, 10, 8, -214748364, false), + 64 => (-214748364, ALU_DIV, 10, 4, -21474836, false), + 65 => (1, ALU_DIV, -2147483648, 1, 0, false), others => (0, ALU_ADD, 0, 0, 0, false) ); variable checkall : boolean := true; -- 2.25.1