OpenCores
URL https://opencores.org/ocsvn/deflatecore/deflatecore/trunk

Subversion Repositories deflatecore

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /
    from Rev 13 to Rev 14
    ↔ Reverse comparison
  •

Rev 13 → Rev 14

/trunk/search.vhd
9,9 → 9,9
-- Revision:
-- Revision 0.01 - File Created
-- Additional Comments:
-- 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
-- A wrapper for the DJB2 algorithm has a 3 byte buffer to generate 4 byte hash keys
--
--
--------------------------------------------------------------------------------
library IEEE;
use IEEE.std_logic_1164.all;
47,7 → 47,6
--End of the package
 
 
 
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
55,86 → 54,142
use work.mat.all;
use work.all;
 
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
entity hash_table is
--generic definitions, data bus widths.
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 hash_table;
 
architecture genhash of hash_table is
component HashChain
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
);
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 value of previous data
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
Hash_Generated: out bit;
Clock, -- Clock
Reset, -- Reset
Output_E : in bit -- Output Enable
Busy, -- Busy
Done: out bit; -- Key generated
Clock, -- Clock
Reset, -- Reset
Start, -- Start the hash key generation
O_E : in bit -- Output Enable
);
end component;
--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;
 
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;
 
begin
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
);
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;
 
--End of the hash chain
--Control for the hash chain
--Has to do the following
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;
 
--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;
--Common Clock
Algo_clk <= Clock;
 
-- Reset the hash algorithm when reset
Algo_rst <= '1' when mode = 0 or mode = 1else
'0';
 
--State machine using the above states
Process (mode, Clock)
--Sync signals
busy <= '1' when mode > 1 else
'0';
 
end case;
end process;
end one_to_one;
--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';
 
--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;
 
-- Procesed bytes counter
processed_counter: process (mode)
begin
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
end if;
end if;
end process mealy_mach;
end genhash;

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.