From 55cda8d5b6399cf16610753c31004162c0d605bc Mon Sep 17 00:00:00 2001
From: Bernhard Urban <lewurm@gmail.com>
Date: Fri, 21 May 2010 04:50:32 +0200
Subject: [PATCH] alu: bessere find_msb, von 1295 auf 1054 logic cells (fuer
 alu)

---
 src/alu.vhd     | 16 +++++++-------
 src/gen_pkg.vhd | 55 +++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 54 insertions(+), 17 deletions(-)

diff --git a/src/alu.vhd b/src/alu.vhd
index 3a8f54c..9abd7da 100644
--- a/src/alu.vhd
+++ b/src/alu.vhd
@@ -50,8 +50,8 @@ begin
 			calc_done_int <= '0';
 			calc_error_int <= '0';
 			--div
-			dividend_msb_int <= 0;
-			laengediv_int <= 0;
+			dividend_msb_int <= (others => '0');
+			laengediv_int <= (others => '0');
 			quo_int <= (others => '0');
 			aktdiv_int <= (others => '0');
 			op1_int <= (others => '0');
@@ -143,8 +143,8 @@ begin
 		done_intern <= '0';
 		error_intern <= '0';
 		-- default fuer div
-		dividend_msb_next <= 0;
-		laengediv_next <= 0;
+		dividend_msb_next <= (others => '0');
+		laengediv_next <= (others => '0');
 		quo_next <= (others => '0');
 		aktdiv_int_next <= aktdiv_int;
 		op1_next <= (others => '0');
@@ -210,10 +210,10 @@ begin
 						op2_var := (not op2_var) + 1;
 					end if;
 
-					dividend_msb_var := find_msb(op1_var)-1;
-					laengediv_var := find_msb(op2_var)-1;
+					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 (dividend_msb_var - laengediv_var + 1);
+					aktdiv_int_next <= op1_var srl to_integer(dividend_msb_var - laengediv_var + 1);
 
 					-- anmerkung: xst (xilinx) kann folgende zeile nicht uebersetzen
 					-- > if op1 = to_signed(-2147483648, CBITS) then
@@ -242,7 +242,7 @@ begin
 
 				if divtmp > 0 then
 					aktdiv_int_var := aktdiv_int sll 1;
-					aktdiv_int_var(0) := op1_int(divtmp - 1);
+					aktdiv_int_var(0) := op1_int(to_integer(divtmp) - 1);
 
 					quo_var := quo_int sll 1;
 					if aktdiv_int_var >= op2_int then
diff --git a/src/gen_pkg.vhd b/src/gen_pkg.vhd
index 9e27eae..c990f1b 100644
--- a/src/gen_pkg.vhd
+++ b/src/gen_pkg.vhd
@@ -14,7 +14,7 @@ package gen_pkg is
 
 	constant CBITS : integer := 32;
 	subtype csigned is signed((CBITS-1) downto 0);
-	subtype divinteger is integer range -33 to 33;
+	subtype divinteger is unsigned(4 downto 0);
 	-- integer ist 32bit (31bit + sign)
 	subtype cinteger is integer;
 
@@ -27,7 +27,7 @@ package gen_pkg is
 	subtype hstring is string(1 to 72);
 	subtype hstr_int is integer range 0 to 72;
 
-	function find_msb(a : csigned) return divinteger;
+	function find_msb(a : std_logic_vector) return std_logic_vector;
 	procedure icwait(signal clk_i : IN std_logic; cycles: natural);
 
 	-- http://www.marjorie.de/ps2/scancode-set2.htm
@@ -53,15 +53,52 @@ package gen_pkg is
 end package gen_pkg;
 
 package body gen_pkg is
-	function find_msb(a : csigned) return divinteger is
-		variable r : divinteger := 0;
+	-- 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
-		for i in (CBITS-1) downto 0 loop
-			exit when a(i) = '1';
-			r := r+1;
-		end loop;
-		return (CBITS - r);
+		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);
 
 	procedure icwait(signal clk_i : IN std_logic; cycles: Natural) is
 	begin
-- 
2.25.1