[recursive solution to find-the-topmost-1-bit]
I'm very interested, indeed. I think your solution looks interesting,
it's going to be interesting to see if it requires less space on the
device than my brute force method or not.
Targeting Spartan-2 and using a well-known FPGA synthesis tool,
the LUT count is as follows:
number of number of
input bits LUTs
4 2
8 6
16 16
32 35
64 78
128 167
so you can see that, for reasonable-size input, the area
is remarkably close to proportional to the number of inputs.
Dunno how that compares with yours.
Absolutely no promises that this code is 100% correct,
and no promises that it compiles with all possible tools -
for example, Synopsys DC chokes on the "while" loop in
function bits_to_fit, even though that function is used
only to compute constants.
All the important work happens in function "topbit".
At the end there's a very simple example of how you
might use that function in a design.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library ieee;
use ieee.std_logic_1164.all;
package topbit_pkg is
function topbit (p : std_logic_vector) return std_logic_vector;
end;
package body topbit_pkg is
--------------------------- Internal functions ---
-- bits_to_fit:
-- one of many possible ways to compute the number of bits
-- required to represent N as an unsigned integer
--
function bits_to_fit(n: positive) return natural is
variable nn: natural;
variable bits: natural;
begin
nn := n;
bits := 0;
while nn > 0 loop
bits := bits+1;
nn := nn/2;
end loop;
return bits;
end;
-- or_all:
-- given a std_logic_vector, OR all its bits together
-- and return the single-bit result
--
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;
------------------------------- Public functions ---
-- topbit:
-- return the bit number of the most significant bit that is
-- set in a std_logic_vector. Note that the bits are ALWAYS
-- numbered so that the LSB is bit 0 and the MSB is bit n-1,
-- regardless of the bit numbering scheme in your original vector.
-- Note also that this function will return the result 0 in two
-- different cases: when the LSB only is set, and when no bits
-- at all are set. To disambiguate these two cases, you need to
-- concatenate one extra bit on the LSB end of the input vector.
--
function topbit (p : std_logic_vector) return std_logic_vector is
-- Number of bits required to represent the result
constant wN: positive := bits_to_fit(p'length-1);
-- Number of input bits, rounded up to an exact power of 2
constant wP: positive := 2**wN;
-- Input vector, widened to have wP bits, bit numbers normalised
variable pv: std_logic_vector(wP-1 downto 0);
-- Temporary variable for the result
variable n: std_logic_vector(wN downto 1);
begin
if p'length <= 2 then
-- Degenerate case of only 2 input bits: easy
n(n'right) := p(p'left);
else -- p'length > 2, we must divide it into pieces
-- Make a normalised version of the input
pv := (others => '0');
pv(p'length-1 downto 0) := p;
-- If any bits at all are set in the top half...
if or_all(pv(wP-1 downto wP/2)) = '1' then
-- MSB of result is '1', LSBs determined by upper half
n := '1' & topbit(pv(wP-1 downto wP/2));
else -- no bits in the top half are set
-- MSB of result is '0', LSBs determined by lower half
n := '0' & topbit(pv(wP/2-1 downto 0));
end if;
end if;
return n;
end;
end;
-------------------- Example entity that uses the function
library ieee;
use ieee.std_logic_1164.all;
use work.topbit_pkg.all;
entity nbits_e is
port (
p: in std_logic_vector(31 downto 0);
q: out std_logic_vector(4 downto 0)
);
end;
architecture a of nbits_e is
begin
q <= topbit(p);
end;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Hope this helps
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services
Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:
[email protected]
Fax: +44 (0)1425 471573 Web:
http://www.doulos.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
