title: Implementing a VHDL binary search on a std_logic_vector [vhdl]
body: <p>I'm attempting to create synthesizable VHDL (function or procedure) for an ASIC (it must be part of the ASIC) that will look for the first '1' in a standard_logic_vector and output which vector position that '1' was in.  For example, I have an 8-bit slv of "10001000" (a '1' in position 3 and 7).  If I use this slv, the output should be 4 (the output is 1 based).</p>
  
  <p>The actual VHDL will be searching a large slv, up to 512 bits in length.  I tried implementing a binary search function but I get synthesis errors that states <strong>"Could not synthesize non-constant range values.  [CDFG-231] [elaborate] 
   The non-constant range values are in file '...' on line 61"</strong> I indicated in the code below where it complains.  I'm not sure how to implement a binary search algorithm without having non-constant range values.  How would I modify this code so it's synthesizable?</p>
  
  <p>I have attempted to search for binary search algorithms for HDL for potential code to look at and for my error, but I didn't find anything.</p>
  
  <pre><code>library ieee;
  use ieee.std_logic_1164.all;
  use ieee.numeric_std.all;
  use ieee.std_logic_misc.all;
  
  entity bin_search is
      generic (
          constant NREGS  : positive  := 16               -- number of registers
      );
      port (
          clk_i   : in    std_logic;                      -- clock
          bin_i   : in    unsigned( NREGS-1 downto 0 );   -- input
          en_i    : in    std_logic;                      -- input enable
          addr_o  : out   natural range 0 to NREGS        -- first binary location
      );
  end bin_search;
  
  architecture rtl of bin_search   is
  
    function f_bin_search( input: unsigned; nob: positive ) return natural is
          constant nbits  : positive                      := 2**nob;
          variable lower  : natural   range 0 to 1        := 0;
          variable upper  : natural   range 0 to 1        := 0;
          variable idx    : natural   range 0 to nob      := 4;
          variable cnt    : natural   range 0 to nbits    := 0;
          variable mid    : positive  range 1 to nbits    := nbits/2; --
          variable ll     : natural   range 0 to nbits    := 0;
          variable ul     : positive  range 1 to nbits    := nbits;   -- 
      begin
          if input = 0 then
              cnt := 0;
              return cnt;
          else
              loop1: while ( idx &gt; 0 ) loop
                  if ( input( mid-1 downto ll ) &gt; 0 ) then --  &lt;===WHERE SYNTH COMPLAINS
                      lower   := 1;
                  else
                      lower   := 0;
                  end if;
                  if ( input( ul-1 downto mid ) &gt; 0 ) then
                      upper   := 1;
                  else
                      upper   := 0;
                  end if;
                  if ( idx = 1 ) then
                      if ( lower = 1 ) then
                          cnt := mid;
                      else
                          cnt := ul;
                      end if;
                  elsif ( lower = 1 ) then
                      ul  := mid;
                      mid := ( ( ll+ul )/2 );
                  elsif ( upper = 1 ) then
                      ll  := mid;
                      mid := ( ll+ul )/2;
                  else
                      cnt := 0;
                      exit loop1;
                  end if;
                  idx := idx-1;
              end loop loop1;
              return cnt;
          end if;
      end f_bin_search;
  
  begin
  
      test_proc: process ( clk_i )
      begin
          if rising_edge( clk_i ) then
              if en_i = '1' then
                  addr_o  &lt;= f_bin_search( bin_i, 4 );
              end if;
          end if;
      end process test_proc;
  end rtl;
  </code></pre>
  
  <p>Here's a simple test bench where the input is inc'd by '1'.  The addr_o should be the location (1 based) of the input lsb with a '1'.</p>
  
  <pre><code>library ieee;
  use ieee.std_logic_1164.all;
  use ieee.std_logic_misc.all;
  use ieee.numeric_std.all;
  
  entity bin_search_tb is
  end bin_search_tb;
  
  architecture behavior of bin_search_tb is
  
      constant    NREGS   : positive  := 16;
  
      signal      clk     : std_logic;
      signal      input   : unsigned( NREGS-1 downto 0 );
      signal      start   : std_logic;
      signal      addr    : natural range 0 to NREGS;
  
      constant    clk_per : time  := 1 ns;
      signal      row     : natural range 0 to 2**NREGS-1;
  
  begin
  
      bin_search_inst: entity work.bin_search( rtl )
      generic map (
          NREGS   =&gt; NREGS
      )
      port map (
          clk_i   =&gt; clk,     -- master clock
          bin_i   =&gt; input,   -- captured events
          en_i    =&gt; start,   -- start binary search
          addr_o  =&gt; addr     -- addr where the first '1' appears
      );
  
      -- master clock process
      clk_proc: process
      begin
          clk &lt;= '0';
          wait for clk_per / 2;
          clk &lt;= '1';
          wait for clk_per / 2;
      end process clk_proc;
  
      -- 
      stim1_proc: process
      begin
          input   &lt;= ( others =&gt; '0' );
          start   &lt;= '0';
          row     &lt;= 1;   
          wait until clk'event and clk = '1';
          loop
              wait until clk'event and clk = '1';
              input   &lt;= to_unsigned( row, input'length );
              start   &lt;= '1';
              wait until clk'event and clk = '1';
              start   &lt;= '0';
              wait for 4*clk_per;
              row &lt;= row+1;
          end loop;   
      end process stim1_proc;
  
  end architecture behavior;
  </code></pre>
  
  <p>Thanks for your assistance!
  -Jason</p>
  
  <p>Edited code and added a testbench </p>