library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
use IEEE.std_logic_arith.all;

entity Collatz is
  port (
    sysClk     : in  std_logic := '0';
    resetIn    : in  std_logic := '0';
    onStartIn  : in  std_logic := '0';
    dataIn     : in  std_logic_vector(7 downto 0) := (others => '0'); -- max 255
    tempOut    : out std_logic_vector(15 downto 0) := (others => '0'); -- max 13120 (when dataIn is 255)
    counterOut : out std_logic_vector(7 downto 0) := (others => '0'); -- max 127 (when dataIn is 231, 235)
    stateOut   : out std_logic_vector(1 downto 0) := (others => '0');
    onFinishOut: out std_logic := '0'
  );
end Collatz;

architecture RTL of Collatz is
  signal temp   : std_logic_vector(15 downto 0) := (others => '0');
  signal counter: std_logic_vector(7 downto 0) := (others => '0');
  signal state  : std_logic_vector(1 downto 0) := (others => '0');
  signal isDone : std_logic := '0';

  -- states
  constant IDLING  : std_logic_vector := "00";
  constant ONSTART : std_logic_vector := "01";
  constant RUNNING : std_logic_vector := "11";
  constant ONFINISH: std_logic_vector := "10";

  type vectorArray is array (0 to 255) of std_logic_vector(7 downto 0);
  signal collatzArray   : vectorArray := (others => (others => '0'));

  begin
    process begin
      wait until rising_edge(sysClk);

      if resetIn = '1' then
        state <= IDLING;
      else
        case state(0) is
          when '0' =>
            if onStartIn = '1' then
              state(0) <= '1'; -- IDLING -> ONSTART
            end if;
          when '1' =>
            if (state(1) = '1' and isDone = '1') then
              state(0) <= '0'; -- RUNNING -> ONFINISH
            end if;
          when others => -- never happens
            state(0) <= '0';
        end case;
        state(1) <= state(0); -- ONSTART -> RUNNING, ONFINISH -> IDLING
      end if;

      if state = ONSTART then
        temp <= "00000000" & dataIn;
        counter <= "00000000";
      elsif (state = RUNNING and isDone = '0') then
        if temp < "00000000" & "11111111" and not (collatzArray(conv_integer(temp)) = "00000000") then
          temp <= "0000000000000001";
          counter <= counter + conv_integer(collatzArray(conv_integer(temp)));
        elsif temp = "0000000000000010" then
          temp <= '0' & temp(15 downto 1);
          counter <= counter + 1;
        elsif temp(0) = '0' then
          if temp(1) = '0' then -- temp % 4 = 0: 4n -> n
            temp <= "00" & temp(15 downto 2);
            counter <= counter + 2;
          else -- temp % 4 = 2: 4n + 2 -> 3n + 2
            temp <= temp - ("00" & temp(15 downto 2));
            counter <= counter + 3;
          end if;
        else
          if temp(1) = '0' then -- temp % 4 = 1: 4n + 1 -> 3n + 1
            temp <= temp - ("00" & temp(15 downto 2));
            counter <= counter + 3;
          else -- temp % 4 = 3: 4n + 3 -> 9n + 8
            temp <= temp + temp + ("00" & temp(15 downto 2)) + 2;
            counter <= counter + 4;
          end if;
        end if;
      end if;

      if state = ONFINISH then
        collatzArray(conv_integer(dataIn)) <= counter;
      end if;
    end process;

    onFinishOut <= '1' when state = ONFINISH else '0';
    counterOut <= counter;
    tempOut <= temp;
    stateOut <= state;

    isDone <= '1' when (temp = "0000000000000000" or temp = "0000000000000001") else '0';

  end RTL;