alu/div: dision in hardwaregerechte art und weise

... trotzdem sind knappe 25% der logic elemente im quartus belegt :(
(zwar fuer ein kleineres fpga, aber das im tilab hat afaik 'nur' doppelt so viele)
immerhin laeuft das design mit 65.70MHz (33MHz muessen wir schaffen), klingt aber auch nicht so toll :/

diff --git a/quartus/project.tcl b/quartus/project.tcl
old mode 100644 (file)
new mode 100755 (executable)
index 5097c58..5b368b7
--- a/quartus/project.tcl
+++ b/quartus/project.tcl
@@ -31,9 +31,10 @@ if {$make_assignments} {
        set_global_assignment -name RESERVE_ALL_UNUSED_PINS "AS INPUT TRI-STATED WITH WEAK PULL-UP"
        set_global_assignment -name RESERVE_ASDO_AFTER_CONFIGURATION "AS INPUT TRI-STATED"
 
-       set_global_assignment -name TOP_LEVEL_ENTITY calc
+       #set_global_assignment -name TOP_LEVEL_ENTITY calc
+       set_global_assignment -name TOP_LEVEL_ENTITY alu
        set_global_assignment -name VHDL_FILE ../../src/gen_pkg.vhd
-       set_global_assignment -name VHDL_FILE ../../src/calc.vhd
+       #set_global_assignment -name VHDL_FILE ../../src/calc.vhd
        set_global_assignment -name VHDL_FILE ../../src/alu.vhd
 
        set_location_assignment PIN_N3 -to sys_clk

diff --git a/src/alu.do b/src/alu.do
index 98ddba09ae57c56ac8b293683004c028b15a6b0d..b6b9c47d19ff757f3c79838aeafb8fb05d870c04 100644 (file)
--- a/src/alu.do
+++ b/src/alu.do
@@ -19,4 +19,3 @@ run -all
 
 #ganz nach links scrollen
 wave seetime 0
-

diff --git a/src/alu.vhd b/src/alu.vhd
index fad995e48a94dcdbbcb17065132137233f6a0fcc..eae611655d3d63dad7f1d9ca963f755a5c0e4b9c 100644 (file)
--- a/src/alu.vhd
+++ b/src/alu.vhd
@@ -18,11 +18,15 @@ entity alu is
 end entity alu;
 
 architecture beh of alu is
-       type ALU_STATE is (SIDLE, SADD, SSUB, SMUL, SDIV, SDONE);
+       type ALU_STATE is (SIDLE, SADD, SSUB, SMUL, SDIV, SDIV_CALC, SDIV_DONE, SDONE);
        signal state, state_next : ALU_STATE;
-       signal done_intern : std_logic;
+       signal done_intern, div_calc_done, div_go_calc : std_logic;
        signal op3_int, op3_next : csigned;
        signal calc_done_int, calc_done_next : std_logic;
+       -- signale fuer division
+       signal dividend_msb, dividend_msb_next, laengediv, laengediv_next : natural;
+       signal quo, quo_next, aktdiv, aktdiv_next, op1_int, op1_next, op2_int, op2_next : csigned;
+       signal sign, sign_next : std_logic;
 begin
        op3 <= op3_int;
        calc_done <= calc_done_int;
@@ -36,11 +40,19 @@ begin
                        state <= state_next;
                        op3_int <= op3_next;
                        calc_done_int <= calc_done_next;
+                       -- div
+                       dividend_msb <= dividend_msb_next;
+                       laengediv <= laengediv_next;
+                       quo <= quo_next;
+                       aktdiv <= aktdiv_next;
+                       op1_int <= op1_next;
+                       op2_int <= op2_next;
+                       sign <= sign_next;
                end if;
        end process;
 
        -- next state
-       process(state, opcode, done_intern, do_calc)
+       process(state, opcode, done_intern, do_calc, div_calc_done, div_go_calc)
        begin
                -- set a default value for next state
                state_next <= state;
@@ -74,6 +86,14 @@ begin
                                        state_next <= SDONE;
                                end if;
                        when SDIV =>
+                               if div_go_calc = '1' then
+                                       state_next <= SDIV_CALC;
+                               end if;
+                       when SDIV_CALC =>
+                               if div_calc_done = '1' then
+                                       state_next <= SDIV_DONE;
+                               end if;
+                       when SDIV_DONE =>
                                if done_intern = '1' then
                                        state_next <= SDONE;
                                end if;
@@ -85,17 +105,30 @@ begin
        end process;
 
        -- output
-       process(state, op1, op2)
-       variable tmperg : csigned;
-       variable multmp : signed(((2*CBITS)-1) downto 0);
+       process(state, op1, op2, dividend_msb, laengediv, quo, aktdiv, sign, op1_int, op2_int)
+               variable tmperg : csigned;
+               variable multmp : signed(((2*CBITS)-1) downto 0);
+               -- vars fuer div
+               variable laengediv_var, dividend_msb_var : natural;
+               variable aktdiv_var, quo_var, op1_var, op2_var : csigned;
        begin
                op3_next <= (others => '0');
                calc_done_next <= '0';
+               div_calc_done <= '0';
+               div_go_calc <= '0';
+               done_intern <= '0';
+               -- default fuer div
+               dividend_msb_next <= 0;
+               laengediv_next <= 0;
+               quo_next <= (others => '0');
+               aktdiv_next <= (others => '0');
+               op1_next <= (others => '0');
+               op2_next <= (others => '0');
+               sign_next <= '0';
 
                case state is
                        when SIDLE =>
                                tmperg := (others => '0');
-                               done_intern <= '0';
                        when SADD =>
                                tmperg := op1 + op2;
                                done_intern <= '1';
@@ -108,7 +141,65 @@ begin
                                tmperg((CBITS-2) downto 0) := multmp((CBITS-2) downto 0);
                                done_intern <= '1';
                        when SDIV =>
-                               tmperg := op1 / op2;
+                               -- division implementiert nach ~hwmod/doc/division.pdf
+                               tmperg := (others => '0');
+                               if op2 = to_signed(0,CBITS) then
+                                       -- TODO: err out signal
+                                       done_intern <= '1';
+                               else
+                                       -- sign check
+                                       op1_var := op1;
+                                       op2_var := op2;
+                                       if op1(CBITS-1) = '1' then
+                                               op1_var := not (op1_var + 1);
+                                       end if;
+                                       if op2(CBITS-1) = '1' then
+                                               op2_var := not (op2_var + 1);
+                                       end if;
+
+                                       dividend_msb_var := find_msb(op1_var)-1;
+                                       laengediv_var := find_msb(op2_var)-1;
+
+                                       aktdiv_next <= op1_var srl (dividend_msb_var - laengediv_var + 1);
+
+                                       div_go_calc <= '1';
+                                       dividend_msb_next <= dividend_msb_var;
+                                       laengediv_next <= laengediv_var;
+                                       quo_next <= (others => '0');
+                                       op1_next <= op1_var;
+                                       op2_next <= op2_var;
+                                       sign_next <= op1(CBITS-1) xor op2(CBITS-1);
+                               end if;
+                       when SDIV_CALC =>
+                               tmperg := (others => '0');
+
+                               if (dividend_msb - laengediv + 1) > 0 then
+                                       aktdiv_var := aktdiv sll 1;
+                                       aktdiv_var(0) := op1_int(dividend_msb - laengediv);
+
+                                       quo_var := quo sll 1;
+                                       if aktdiv_var >= op2_int then
+                                               quo_var(0) := '1';
+                                               aktdiv_var := aktdiv_var - op2_int;
+                                       end if;
+
+                                       quo_next <= quo_var;
+                                       aktdiv_next <= aktdiv_var;
+                                       dividend_msb_next <= dividend_msb;
+                                       laengediv_next <= laengediv + 1;
+                                       op1_next <= op1_int;
+                                       op2_next <= op2_int;
+                                       sign_next <= sign;
+                               else
+                                       if sign = '1' then
+                                               quo_next <= (not quo) + 1;
+                                       else
+                                               quo_next <= quo;
+                                       end if;
+                                       div_calc_done <= '1';
+                               end if;
+                       when SDIV_DONE =>
+                               tmperg := quo;
                                done_intern <= '1';
                        when SDONE =>
                                done_intern <= '1';
@@ -118,3 +209,4 @@ begin
                end case;
        end process;
 end architecture beh;
+

diff --git a/src/alu_tb.vhd b/src/alu_tb.vhd
index 33f4455ca6e38db881f4cc6759be877bf9ded21c..1b0d2f4ab3f3947b543e45c666c62fc7db20d33c 100644 (file)
--- a/src/alu_tb.vhd
+++ b/src/alu_tb.vhd
@@ -62,16 +62,24 @@ begin
                type alu_testv_array is array (natural range 0 to 20) of alu_testv;
 
                variable testmatrix : alu_testv_array :=
-                       ( 0 => (7, ADD, 3, 10),
-                         1 => (7, SUB, 1, 6),
-                         2 => (7, DIV, 1, 7),
-                         3 => (7, DIV, 2, 3),
-                         4 => (7, ADD, 1, 8),
-                         5 => (7, MUL, 3, 21),
-                         6 => (-7, MUL, 3, -21),
-                         7 => (268435456, MUL, -2, -536870912),
-                         8 => (268435456, MUL, 2**5, 0), -- um fuenf nach links shiften
-                         9 => (268435456 + 5, MUL, 2**5, 160), -- = 5 * (2^5)
+                       ( 0 => (-5, DIV, 3, -1),
+                         1 => (7, ADD, 3, 10),
+                         2 => (7, SUB, 1, 6),
+                         3 => (7, DIV, 1, 7),
+                         4 => (7, DIV, 3, 2),
+                         5 => (7, ADD, 1, 8),
+                         6 => (7, MUL, 3, 21),
+                         7 => (-7, MUL, 3, -21),
+                         8 => (268435456, MUL, -2, -536870912),
+                         9 => (268435456, MUL, 2**5, 0), -- um fuenf nach links shiften
+                         10 => (268435456 + 5, MUL, 2**5, 160), -- = 5 * (2^5)
+                         11 => (100, DIV, 10, 10),
+                         12 => (100, DIV, 51, 1),
+                         13 => (100, DIV, 49, 2),
+                         14 => (153156, DIV, 3543, 43),
+                         15 => (-153156, DIV, 3543, -43),
+                         16 => (153156, DIV, -3543, -43),
+                         17 => (-153156, DIV, -3543, 43),
                          others => (0, ADD, 0, 0)
                        );
 

diff --git a/src/gen_pkg.vhd b/src/gen_pkg.vhd
index 37667631f38d6d9da5f79ca1ff8b1b0ec045ef35..6f1ff43d48089bff05b40bd342d988ff68407efa 100644 (file)
--- a/src/gen_pkg.vhd
+++ b/src/gen_pkg.vhd
@@ -8,5 +8,26 @@ package gen_pkg is
        subtype csigned is signed((CBITS-1) downto 0);
        --TODO: bei CBITS-1 gibts einen overflow :/
        subtype cinteger is integer range -(2**(CBITS-2)) to ((2**(CBITS-2))-1);
+       function find_msb(a : csigned) return natural;
 end package gen_pkg;
 
+package body gen_pkg is
+       function find_msb(a : csigned) return natural is
+               variable r : natural := 0;
+               variable count : boolean := true;
+       begin
+               for i in (CBITS-1) downto 0 loop
+                       if count then
+                               if a(i) = '1' then
+                                       count := false;
+                               else
+                                       r := r+1;
+                               end if;
+                       else
+                               null;
+                       end if;
+               end loop;
+               return (CBITS - r);
+       end function find_msb;
+end package body gen_pkg;
+