Kako ukrasti jos jedan takt?

-- Given algorithm: Find given element's index by
-- Binary Search.

-- Unmodified algorithm:
-- ---------------------------
-- while (left =< right)
-- {
--   middle = (left+right)/2;
--   if x[middle] = key then
--     return key;
--   if x[middle] > key then
--     right = middle - 1;
--   if x[middle] < key then
--     left = middle + 1;
-- }
-- return not_found;

-- Modified algorithm:
-- ---------------------------

-- state: idle
-- ready <= 1
-- if start = 1 ...
-- op: if left < right or left = right then
--   -- state: new_middle
--   middle = (left + right) >> 1
--   if x(middle) == key_i then
--     el_found_o = 1
--     pos_o = middle

--     GOTO idle -- one process done, do it again.
--   else
--     -- state: update_lr
--     if x(middle) > key_i then
--       right = middle - 1
--     else
--       left = middle + 1
--     end if;
--     GOTO op
--   end if;

-- else
--   GOTO idle -- not_found, unsuccessfull cycle, do it again
-- end if;

-- not_found:
-- found:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.util_pkg.all;

entity binary_search_array is
  generic (
    WIDTH    : integer := 8;
    ARR_SIZE : integer := 30
    );
  port (
    --------------- Clocking and reset interface ---------------
    clk   : in std_logic;
    reset : in std_logic;

    -- Array memory interface
    addr_o : out std_logic_vector(7 downto 0);
    ------------------- Output data interface -------------------
    data_o : out std_logic_vector(WIDTH-1 downto 0);
    ------------------- Input data interface -------------------
    data_i : in  std_logic_vector(WIDTH-1 downto 0);

    -- element to look for its index
    key_i : in  std_logic_vector(WIDTH-1 downto 0);
    -- element's index
    pos_o : out std_logic_vector(WIDTH-1 downto 0);

    left_i     : in  std_logic_vector(WIDTH-1 downto 0);
    right_i    : in  std_logic_vector(WIDTH-1 downto 0);
    rw_o       : out std_logic;
    el_found_o : out std_logic;

    --------------------- Command interface --------------------
    start : in  std_logic;
    --------------------- Status interface ---------------------
    ready : out std_logic
    );
end entity;

architecture behavioral of binary_search_array is
  type state_type is (idle, op, check); --add, rdrop, ldrop);
  signal state_reg, state_next : state_type;

  -- one bit more, because of left+right
  signal middle_reg, middle_next : unsigned(WIDTH downto 0) := (others => '0');
  signal left_reg, left_next     : unsigned(WIDTH-1 downto 0);
  signal right_reg, right_next   : unsigned(WIDTH-1 downto 0);

  -- signal p1_addr_i_s : std_logic_vector(7 downto 0);
  -- signal p1_data_i_s : std_logic_vector(WIDTH-1 downto 0);
  -- signal p1_data_o_s : std_logic_vector(WIDTH-1 downto 0);
  -- signal p1_wr_i_s   : std_logic;

begin

  -- -- Array memory
  -- array_mem : entity work.dp_memory(beh)
  --   generic map (
  --     WIDTH => DATA_WIDTH_c,
  --     SIZE  => 256
  --     )
  --   port map (
  --     clk       => clk,
  --     reset     => reset,
  --     p1_addr_i => p1_addr_i_s,         --addr_o,
  --     p1_data_i => p1_data_i_s,         --data_i,
  --     p1_data_o => p1_data_o_s,         --data_o,
  --     p1_wr_i   => p1_wr_i_s,           --rw_o,
  --     p2_addr_i => (others => '0'),
  --     p2_data_i => (others );

  -- MEM : process (clk) is
  -- begin
  --   -- write
  --   if p1_wr_i_s = '1' then

  --   else

  --   end if;

  -- end process;

-- State and data registers
  SEQ : process (clk, reset)
  begin
    if reset = '1' then
      state_reg  <= idle;
      left_reg   <= unsigned(left_i);
      right_reg  <= unsigned(right_i);
      middle_reg <= (others => '0');
    elsif (clk'event and clk = '1') then
      state_reg  <= state_next;
      left_reg   <= left_next;
      right_reg  <= right_next;
      middle_reg <= middle_next;
    end if;
  end process;

-- Combinatorial circuits
  COMB : process (state_reg, start, data_i, key_i, left_i, right_i,
                  left_reg, left_next, right_reg, right_next, middle_reg, middle_next
                  )
  begin
    -- Default assignments
    el_found_o <= '0';
    pos_o      <= (others => '0');
    data_o     <= (others => '0');
    rw_o       <= '0';                  -- read

    -- Default variable values
    left_next   <= left_reg;
    right_next  <= right_reg;
    middle_next <= middle_reg;
    ready       <= '0';

    case state_reg is
      when idle =>
        ready <= '1';
        if start = '1' then
          -- state_next <= add;
          -- assign new middle element based on new left and right elements
          middle_next <= resize(right_next + left_next, middle_next'length);
          state_next  <= op;

        else
          state_next <= idle;
        end if;

      when op =>

        if left_next < right_next or left_next = right_next then
          state_next <= check;
          addr_o <= std_logic_vector(
            to_unsigned(to_integer(unsigned(middle_reg)), addr_o'length));
        else
          state_next <= idle;
        end if;
        middle_next <= '0' & middle_reg(WIDTH downto 1);

      when check =>
        -- NOTE: x(middle) comes from memory
        if data_i = key_i then
          el_found_o <= '1';
          pos_o <= std_logic_vector(
            to_unsigned(to_integer(unsigned(middle_next)), pos_o'length));
          state_next <= idle;
        else
          if (data_i > key_i) then
            -- drop right
            right_next <= resize(middle_reg - 1, right_next'length);
            middle_next <= resize(right_next + left_next, middle_next'length);
            state_next  <= op;
          else
            -- drop left
            left_next  <= middle_reg(WIDTH-1 downto 0) + 1;
            middle_next <= resize(right_next + left_next, middle_next'length);
            state_next  <= op;
          end if;
        end if;
    end case;

    -- case state_reg is
    --   when idle =>
    --     middle_next <= resize(right_next + left_next, middle_next'length);
    --     ready <= '1';
    --     if start = '1' then
    --       middle_next <= '0' & middle_reg(WIDTH downto 1);
    --       -- middle_next <= resize(right_next + left_next, middle_next'length);
    --       -- left_next   <= unsigned(left_i);
    --       -- right_next  <= unsigned(right_i);
    --       state_next  <= op;
    --     else
    --       state_next <= idle;
    --     end if;
    --   when op =>
    --     -- assign new middle element based on new left and right elements
    --     middle_next <= resize(right_next + left_next, middle_next'length);

    --     if left_next < right_next or left_next = right_next then
    --       state_next <= shrncheck;
    --       addr_o <= std_logic_vector(
    --         to_unsigned(to_integer(unsigned(middle_reg)), addr_o'length));
    --     else
    --       state_next <= idle;
    --     end if;

    --   when shrncheck =>
    --     -- shift right by one place
    --     middle_next <= '0' & middle_reg(WIDTH downto 1);
    --     -- middle_reg <= '0' & middle_next(WIDTH downto 1);
    --     -- NOTE: x(middle) comes from memory
    --     if data_i = key_i then
    --       el_found_o <= '1';
    --       pos_o <= std_logic_vector(
    --         to_unsigned(to_integer(unsigned(middle_next)), middle_next'length));
    --       state_next <= idle;
    --     else
    --       if (data_i > key_i) then
    --         state_next <= rdrop;
    --       else
    --         state_next <= ldrop;
    --       end if;
    --     end if;

  --   when rdrop =>
  --     right_next <= resize(middle_reg - 1, right_next'length);
  --     state_next <= op;
  --   when ldrop =>
  --     left_next  <= middle_reg(WIDTH-1 downto 0) + 1;
  --     state_next <= op;
  -- end case;
  end process;
end behavioral;