----------------------------------------------
-- VHDL of Lempel-Ziv LZ77 Data Compression
-- Author: LZ77 Group, ECE of UMass (Copyright)
-- March 20, 1998
----------------------------------------------
-- Code word:
--		pointer + maxLen + lastSymbol
----------------------------------------------

Library IEEE;
Use IEEE.std_logic_1164.all;
use ieee.std_logic_arith.all;
--Use IEEE.std_logic_unsigned.all;


Entity lz77 is
	port(
		clk, reset: in std_logic;
		din: in std_logic_vector(7 downto 0);
		code: out std_logic_vector(7 downto 0);
		ready_in, ready_out: out std_logic);
end lz77;

Architecture arch_lz77 of lz77 is

	--constant L_LOOK : integer := 63;
	--constant L_LOOK : integer := 15;
	constant L_LOOK : integer := 7;
	--constant L_WIN : integer := 127;
	--constant L_WIN : integer := 31;
	constant L_WIN : integer := 7;
	--constant LENG : integer := 192; -- additional 1-byte to in case of all matching
	--constant LENG : integer := 48; -- additional 1-byte to in case of all matching
	constant LENG : integer := 16; -- additional 1-byte to in case of all matching

	TYPE BYTE is ARRAY( 0 to LENG) of std_logic_vector(7 downto 0);
	signal x: BYTE; 
	signal pointer, maxLen, lastSymbol: std_logic_vector( 7 downto 0);
	TYPE STATE_TYP is (IDLE, INIT, COMPARE, READ);
	signal present_state, next_state: STATE_TYP;

begin

	-- Initialize the sliding window and look-ahead buffer
	PutItAll: process
		variable i, j: integer range 0 to 255;
		variable tmpMaxLen : std_logic_vector(7 downto 0);
		variable t_maxLen, t_pointer, t_lastSymbol: std_logic_vector(7 downto 0);
	begin
	    wait until clk'event and clk = '1';
	    --wait until ( clk'event and clk = '1' ) or (reset'event and reset = '1');
	    if(reset = '1') then
			for i in 0 to LENG loop
				x(i) <= "00000000";
			end loop;
			pointer <= "00000000";
			maxLen <= "00000000";
			lastSymbol <= "00000000";
			present_state <= INIT;
			ready_in <= '0';
	    else
		-- StateMachine: process
	    	-- wait until ( clk'event and clk = '1' ) or (reset'event and reset = '1');
	    	-- wait until clk'event and clk = '1';
	    	case present_state is
	    	when INIT =>
			ready_in <= '1';
			for i in 0 to L_LOOK+1 loop
				wait until clk'EVENT and clk = '1';
				x(LENG) <= din;			-- read data from outside
					for j in 1 to L_LOOK+1 loop
					x(L_WIN+j) <= x(L_WIN+j+1);	-- left-shift 1-bit
				end loop;
			end loop;
			wait until clk'event and clk = '1';
			ready_in <= '0';
			present_state <= COMPARE;

	   	----- compare and get the maxium matching -------------	
	   	when COMPARE =>
			t_maxLen := "00000000";
			t_pointer := "00000000";
			t_lastSymbol := "00000000";
			for i in 0 to L_WIN loop
				-- add wait at the beginning of the loop
				wait until clk'event and clk = '1';
				tmpMaxLen := "00000000";
				for j in 0 to L_LOOK loop
					wait until clk'event and clk = '1';
					if x(i+j) = x(L_WIN+1+j) then 
						tmpMaxLen := tmpMaxLen + "00000001";
					else 
						exit;
					end if;
				end loop;
				-- synchronization at the end of loop
				wait until clk'event and clk = '1';

				-- if( all matching )
				if tmpMaxLen = to_stdlogicvector( L_LOOK, 8) then
					t_maxLen := tmpMaxLen;
					t_pointer := to_stdlogicvector(i,8);
					t_lastSymbol := x(LENG);	-- last byte of x()
					exit;
				elsif (tmpMaxLen >= t_maxLen) then
					t_maxLen := tmpMaxLen;
					t_pointer := to_stdlogicvector(i,8);
					t_lastSymbol := x(L_WIN+to_integer(maxLen)+1);
				end if;		
			end loop;
			-- synchronization after loop	
			wait until clk'event and clk = '1';

			maxLen <= t_maxLen;
			pointer <= t_pointer;
			lastSymbol <= t_lastSymbol;
			present_state <= READ;

		----- Read date from outside ---------------------------
		----- Flush the sliding-window & look-ahead buffer -----
	    	when READ =>
			ready_in <= '1';
			for i in 0 to to_integer(maxLen) loop
				wait until clk'event and clk = '1';
				x(LENG) <= din;	-- read data 
				for j in 0 to (LENG-1) loop
					x(j) <= x(j+1);
				end loop;
			end loop;
			wait until clk = '1' and clk'event;
			ready_in <= '0';
			present_state <= COMPARE;
	    	when others => 
			present_state <= INIT;
	    	end case;
	   end if;
	end process PutItAll;


--	StateMachine: process(clk, reset)
--	begin
--		if( reset = '1' ) then
--			present_state <= IDLE;
--	    	elsif( clk'event and clk = '1') then
--			present_state <= next_state;	-- State assignment
--		end if;
--	end process StateMachine;
					
	------ Output compressed codeword ---------------------
	OutputCode: process
	begin
		wait until clk'event and clk = '0';
		if( reset = '1') then
			ready_out <= '0';
		elsif( present_state = READ ) then
			ready_out <= '1';				-- Signal out ...
			wait until clk'event and clk = '0';		-- Falling edge
			code <= pointer;				-- 1st: pointer
			wait until clk'event and clk = '0';	
			code <= maxLen;					-- 2nd: match length
			wait until  clk'event and clk = '0';
			code <= lastSymbol;				-- 3rd: Last symbol
			wait until clk'event and clk = '0';
			ready_out <= '0';
		end if;
		
		while( present_state = READ) loop
			wait until clk'event and clk = '0';
		end loop;
	end process OutputCode;
	
	-- synchronization for read data
--	process( next_state, reset )
--	begin
--		if( reset = '1' ) then
--			ready_in <= '0';
--		elsif( next_state = READ or next_state = INIT) then
--			ready_in <= '1';
--		elsif
--			ready_in <= '0';
--		end if;
--	end process;

end arch_lz77;