head 1.5; access; symbols; locks; strict; comment @# @; 1.5 date 2006.06.05.01.31.23; author smallcode; state Exp; branches; next 1.4; commitid 29214483896a4567; 1.4 date 2006.05.24.02.06.23; author smallcode; state Exp; branches; next 1.3; commitid 37364473bf9e4567; 1.3 date 2006.05.01.23.39.25; author smallcode; state Exp; branches; next 1.2; commitid 138444569c2b4567; 1.2 date 2006.03.28.00.46.35; author smallcode; state Exp; branches; next 1.1; commitid 705a442887694567; 1.1 date 2005.11.15.16.07.16; author smallcode; state Exp; branches; next ; commitid 6d13437a07ab4567; desc @@ 1.5 log @The integration is half completed and the coding is 50% completed for the search and sorting, the memory buffer is implemented as a fixed 32k FIFO sliding window. @ text @-------------------------------------------------------------------------------- -- Create Date: Open source, from 12c core hosted at www.opencores.org -- Design Name: -- Module Name: Log function base 2 -- Project Name: Deflate -- Target Device: -- Dependencies: -- -- Revision: NA -- Additional Comments: -- Use this to convert the memeory lengths to the 2^x values -- to dynamically assign the widths of the address -- -------------------------------------------------------------------------------- library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all; --Function to find the log of a number --Is used to convert the addresses package mat is function log2(v: in natural) return natural; end package mat; --Function definition library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all; package body mat is function log2(v: in natural) return natural is variable n: natural; variable logn: natural; begin n := 1; for i in 0 to 128 loop logn := i; exit when (n>=v); n := n * 2; end loop; return logn; end function log2; end package body mat; --End of the package -------------------------------------------------------------------------------- -- Create Date: 17:24:38 20/05/2006 -- Design Name: -- Module Name: -- Project Name: Deflate -- Target Device: -- Dependencies: hahskey.vhdl -- -- Revision: -- Revision 0.50 - Works but not optimised -- Additional Comments: -- This componenet controls the data input and stores the data alongwith -- the source in 32k buffers , -- It recieves the data directly and then on finding a minimum match -- Drives its match output high along with the match address on the address output -- and the current offset on the next clock cycle -- waits for the next +ve edge on the Active data input -- to go high before resuming, the output/ input is +ve edge triggered -- -------------------------------------------------------------------------------- library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; use work.mat.all; entity input_process is Generic ( -- Number of bits in the key Hash_Width : natural := 32; -- Data bus width Data_Width : natural := 8; -- Buffer allocated to the hash table and the source buffer = 32k tables -- The key buffer has to be equal to the Hash_Width above and -- the source buffer of Dat width -- Start address for the memory bank at which the hash keys need to be stored -- The end address is calculated by adding the length of the table to that address Length_of_Table : natural := 32768 ); Port ( --Outputs to read/write the key values. hash_tbl_dat : inout std_logic_vector ( Hash_Width - 1 downto 0); --Port to read/write data values source_buff_dat : inout std_logic_vector ( Data_Width - 1 downto 0); -- Matching 4 bytes fond for the last 4 inputs Match, -- Ready for crunching Ready, -- The sync signals to the memory, read write operations -- done simultaneously on both memry banks -- The design will currently work with SRAM and will need a wrapper to -- work with DRAM -- Active data on output Act_data_out, --Read or write operation 0 = read, 1 = write RW : out bit ; -- Current address in buffers Curr_addres : out std_logic_vector (log2 ( Length_of_Table ) - 1 downto 0); --****** --Input signals --Data in source_dat : inout std_logic_vector ( Data_Width - 1 downto 0); -- Input Data Clock Act_dat, -- Clock Src_clk, -- Reset Reset : in bit ); end input_process; architecture mealy_machine of input_process is component hash_key is generic ( hash_width: natural := 32; data_width: natural := 8); port ( data_in: in std_logic_vector(data_width -1 downto 0); hash_out: out std_logic_vector (hash_width -1 downto 0); Clock, reset, start : in bit; ready, busy: out bit); end component; -- Buffer address start for the key table Signal key_address, buffer_address: std_logic_vector (log2 ( Length_of_Table ) - 1 downto 0); -- Accept a 32 bit hash input signal hg1: std_logic_vector ( (Hash_Width -1) downto 0); -- 8 bit io buffer signal Buffer_1 : std_logic_vector (Data_Width-1 downto 0); --Component signals from the key algorithm signal Algo_start, Algo_clk, Algo_rst, Algo_op, Algo_bsy, -- Algorithm sync aignals Search_done, Busy, red_rst, red_opr, val_match: bit := '0'; --Internal sync sgnals signal mode, store_count :integer; begin --Unlike the sub components this module has a slightly complex reset cycle --It resets the offset counters to 0, uses the next 7 clock cyces to read the --start addresses for the data and key buffer resetter: process (Src_Clk) variable tmp: integer; variable red: bit :='0'; Begin if Src_Clk'event and Src_Clk = '1' then if mode /= 0 then red_rst <= '0'; tmp := 0; else case tmp is when 0 => buffer_address (7 downto 0) <= source_dat; when 1 => buffer_address (14 downto 8) <= source_dat (6 downto 0); when 2 => key_address (7 downto 0) <= source_dat; when 3 => key_address (14 downto 8) <= source_dat (6 downto 0); when 4 => red_rst <= '1'; when others => red_rst <= '0'; end case; end if; end if; end process resetter; --The main input mealy machine is defined below -- It has 6 states of operation -- Mode 0 : Reset -- Mode 1 : Wait -- Mode 2 : Active data input generationg a key for it and the last 3 bytes -- Mode 3 : Storing the key and the input data -- Mode 4 : Searching the hash buffer for a 4 byte match -- Mode 5 : Match found, on the next clock cycle output current buffer offet -- and on the second clock cycle output the match offset input_control : process (Act_dat, Src_Clk, Reset ) begin --+ Ve edge triggered if Src_Clk'event and Src_Clk = '1' then -- Mealy machine If Reset = '1' or ( mode = 0 and red_rst ='0' ) then mode <= 0; elsif mode < 2 and Act_dat = '1' then mode <= 2; elsif mode = 2 and Algo_bsy = '0' and store_count < 3 then mode <= 3; elsif mode = 2 and Algo_bsy = '0' then mode <= 4; elsif mode = 4 and Search_done = '1' and val_match = '1' then mode <= 5; elsif mode = 4 and Search_done = '1' then mode <= 3; elsif ( mode = 5 or mode = 3 ) and Busy = '0' then mode <= 1; else mode <= mode; end if; end if; end process input_control; --************************************************ -- Algorithm component addition Key_Gen: hash_key port map ( data_in => Buffer_1, hash_out => hg1, Clock => Algo_clk, reset => Algo_rst, start => Algo_start, ready => Algo_op, busy => Algo_bsy ); -- ************************************************ Ready <= red_rst or red_opr; end mealy_machine;@ 1.4 log @4 byte buffer wrapper fr the hashing algorithm hash_table working The search and store functions should be online in a day or two @ text @d2 1 a2 1 -- Create Date: 15:24:38 11/10/05 d4 1 a4 1 -- Module Name: search - Behavioral d7 1 a7 1 -- Dependencies: Hashchain.vhdl d9 1 a9 2 -- Revision: -- Revision 0.01 - File Created d11 2 a12 2 -- A wrapper for the DJB2 algorithm has a 3 byte buffer to generate 4 byte hash keys -- d15 1 d50 23 a77 1 use work.all; d79 50 a128 2 entity hash_table is --generic definitions, data bus widths. a141 18 end hash_table; architecture genhash of hash_table is component HashChain Generic ( Data_Width : natural := 8; -- Data Bus width Hash_Width : natural := 32 -- Width of the hash key generated ); Port( Hash_o : out std_logic_vector (Hash_Width - 1 downto 0); -- Hash key Data_in : in std_logic_vector (Data_Width -1 downto 0); -- Data input from byte stream Busy, -- Busy Done: out bit; -- Key generated Clock, -- Clock Reset, -- Reset Start, -- Start the hash key generation O_E : in bit -- Output Enable ); d143 20 a162 5 signal hg1: std_logic_vector ( (Hash_Width -1) downto 0); -- Accept a 32 bit hash input signal Datain, Buffer_1, Buffer_2, Buffer_3 : std_logic_vector (Data_Width-1 downto 0); -- 8 bit io buffers signal Algo_start, Algo_clk,Algo_rst,Algo_op, Algo_bsy, Key_done: bit; -- Algorithm interface aignals signal mode, buff_count, proc_count :integer; a164 51 glink:HashChain port map (Hash_O => hg1, Data_in => Datain, Clock => Algo_clk, Reset => Algo_rst, Start => Algo_start, O_E => Algo_op, Busy => Algo_bsy, Done => Key_done); -- 3 byte input buffer -- Stores the last 3 bytes used to generate a hash key to keep the hash keys current -- The hash algorightm is reset after every 4 byte key is generated -- to ensure that the matches are of 4 byte lengths Buffer_1 <= X"00" when mode = 0 else Buffer_2 when mode = 2 else Buffer_1; Buffer_2 <= X"00" when mode = 0 else Buffer_3 when mode = 2 else Buffer_2; Buffer_3 <= X"00" when mode = 0 else Data_in when mode = 2 else Buffer_3; --Common Clock Algo_clk <= Clock; -- Reset the hash algorithm when reset Algo_rst <= '1' when mode = 0 or mode = 1else '0'; --Sync signals busy <= '1' when mode > 1 else '0'; --Send a start for every input byte. Algo_start <= '1' when mode = 2 and buff_count = 3 else -- the 3 byte buffer is empty '1' when mode = 4 else -- 3 byte buffer is full and one byte has been processed '0'; -- 4 bytes sent one after the other to the hashing algorithm Datain <= X"00" when mode = 0 or mode = 1 else Buffer_1 when mode = 2 and buff_count = 3 else Buffer_1 when mode = 4 and buff_count = 3 and proc_count = 1 else Buffer_2 when mode = 4 and buff_count = 3 and proc_count = 2 else Buffer_3 when mode = 4 and buff_count = 3 and proc_count = 3 else X"00"; -- Enabling hash algo output Algo_op <= '1' when proc_count > 2 else '0'; d166 30 a195 11 --Buffer counter buffer_counter: process (mode) begin if mode = 0 then buff_count <= 0; -- Reset elsif mode = 2 and buff_count < 3 then buff_count <= buff_count + 1; -- 1 byte added to buffer else buff_count <= buff_count; -- BUffer is full keep the buffered values and the count end if; end process buffer_counter; d197 11 a207 2 -- Procesed bytes counter processed_counter: process (mode) d209 19 a227 27 if (mode = 2 and buff_count = 3) or mode = 4 then proc_count <= proc_count + 1 ; elsif mode = 3 then proc_count <= proc_count; else proc_count <= 0; end if; end process processed_counter; -- mealy machine, sends 4 bytes sequentially to the hashing algorithm -- Waits for the buffer to get filled, on the first +ve clock edge afer the start input -- is made 1 it sends the bytes to the DJB algorithm. mealy_mach: process (Clock, Reset, Start) Begin if Clock'event and Clock = '1' then -- +ve clock if Reset = '1' then -- Reset mode <= 0; elsif Start = '1' and mode < 2 then --Start either fill the buffer or Process the first byte in buffer mode <= 2; elsif (mode = 2 and buff_count = 3) or (mode > 1 and Algo_bsy = '1') then -- Buffer is fll processing first byte mode <= 3; -- wait while algorithm finishes generating hash elsif mode = 3 and proc_count < 4 then mode <= 4; -- To hash the next 3 bytes else mode <= 1; -- Wait d230 16 a245 2 end process mealy_mach; end genhash;@ 1.3 log @no message @ text @d12 3 a14 3 -- Slightly modified approach to use a hash search -- Instead of searching a chain of hash keys in a table of the hashes generated by the -- minimum length chains is maintained a49 1 d57 18 a74 22 entity stream_hash is Generic (Length_of_Table : natural := 32768; -- Number of locations in the hash table default = 32k table Hash_Width : natural := 32; -- Number of bits in the hash Data_Width : natural := 8 -- Data bus width ) ); Port ( Table_Start : in std_logic_vector ( log2(Length_of_Table) downto 0); -- Starting Address of the data table Hash_inout : inout std_logic_vector ( (Data_Width -1) downto 0); -- Hash key read/write to be stored Datain : in std_logic_vector ( (Data_Width -1) downto 0); -- Data input from byte stream Clock, -- Clock input Output_E : in bit; -- Enable/~Tristate output Match , -- when 1 hash key generated matches hash from table Write_Hash : out bit -- no match read the next byte from memory ); end stream_hash; --The search is a one to one search of the table --The hash keys are stored FIFO unsorted in the table. --Very inefficent as it searches the entire table from start to finishto see if the hash value is present --it is the easiest method and needs to be changed to a sorted store-search. architecture one_to_one of stream_hash is d76 4 a79 4 Generic ( -- Data bus width currently set at 8 Data_Width : natural := 8; -- Width of the hash key generated now at 32 bits Hash_Width : natural := 32 ); d81 1 a81 1 Hash_o : out std_logic_vector (Hash_Width - 1 downto 0); -- Hash value of previous data d83 6 a88 4 Hash_Generated: out bit; Clock, -- Clock Reset, -- Reset Output_E : in bit -- Output Enable a90 7 --hg1 is used for the last generated hash key --hg2 and hg3 are used for storing the previous hash keys --hg4 is used while matcching longer lenths and also uses the second hash key generator signal hg1,hg2,hg3,hg4 : std_logic_vector ( (Hash_Width -1) downto 0); -- Accept a 32 bit hash input signal hashink : std_logic_vector (Data_Width-1 downto 0); signal clk,rst,ope, match1, read, ist, hashr, hashr2 : bit; signal mode:integer; d92 72 d165 31 a195 38 glink:HashChain port map (Hash_o => hg1, Data_in => Datain, Hash_Generated =>hashr, Clock=>clk, -- Clock Reset=>rst, -- Reset Output_E =>ope -- Output Enable ); --Second hash generator to concurrently search hash values longer than 4 glink1:HashChain port map (Hash_o => hg4, Data_in => hg1, Hash_Generated => hashr2, Clock=>clk, -- Clock Reset=>rst, -- Reset Output_E =>ope -- Output Enable ); --End of the hash chain --Control for the hash chain --Has to do the following --0. Reset mode <= 0 when ist ='0' else --1. If its the first hash value to be generated, store the first hash value into memory 1 when match1 ='0' and read ='0' else --2. Read the next hash value and compare it to the values in memory 2 when match1 ='0' and read ='1' else --3. If its a match then output the location of the hash value 3 when match1 ='1' else 4; --State machine using the above states Process (mode, Clock) end case; end process; end one_to_one; @ 1.2 log @Using only the DJB2 algorithm, currently working on search and match for the data stream @ text @d13 1 a13 1 -- Instead of searching a chain of hashes a table of the hashes generated by the a66 2 Table_End : in std_logic_vector ( log2(Length_of_Table) downto 0); -- Ending address of the table Hash_key : in std_logic_vector ( (Hash_Width -1) downto 0); -- Accept a 32 bit hash input a70 1 Table_Match : out std_logic_vector ( log2(Length_of_Table) downto 0); -- Address at which the match was found d77 1 d88 1 d94 3 d99 1 a99 1 signal clk,rst,ope, match1, read, ist : bit; d105 1 d111 1 a111 1 glink1:HashChain port map (Hash_o => hg2, d113 1 d133 2 a136 8 begin case mode is when 0 => match1 <='0'; read <='1'; when 1 => when others => @ 1.1 log @Block for comparing hash cahins and finding matches @ text @d56 1 d58 1 a58 1 entity stream_search is d62 1 a62 1 Data_Width : natural := 8 -- Data bus width ) d70 1 a70 1 Data_in : in std_logic_vector ( (Data_Width -1) downto 0); -- Data input from byte stream d73 1 a73 1 Table_Match : in std_logic_vector ( log2(Length_of_Table) downto 0); -- Address at which the match was found d77 1 a77 1 end stream_search; d81 7 a87 3 architecture one_to_one of stream_search is component Hash1 Port ( d89 1 a89 1 Data_in : in std_logic_vector (Data_Width-1 downto 0); -- Data input from byte stream d95 24 d120 11 d132 5 d138 1 d140 2 @