--------------------------------------------------------------------------------
|
--------------------------------------------------------------------------------
|
-- Company:
|
-- Company:
|
-- Engineer:
|
-- Engineer:
|
-- Create Date: 03:46:54 10/31/05
|
-- Create Date: 03:46:54 10/31/05
|
-- Design Name:
|
-- Design Name:
|
-- Module Name: Hash - Behavioral
|
-- Module Name: Hash - Behavioral
|
-- Project Name: Deflate
|
-- Project Name: Deflate
|
-- Revision:
|
-- Revision:
|
-- Revision 0.01 - File Created
|
-- Revision 0.01 - File Created
|
-- Additional Comments:
|
-- Additional Comments:
|
--
|
--
|
--------------------------------------------------------------------------------
|
--------------------------------------------------------------------------------
|
library IEEE;
|
library IEEE;
|
use IEEE.STD_LOGIC_1164.ALL;
|
use IEEE.STD_LOGIC_1164.ALL;
|
use IEEE.STD_LOGIC_ARITH.ALL;
|
use IEEE.STD_LOGIC_ARITH.ALL;
|
use IEEE.STD_LOGIC_UNSIGNED.ALL;
|
use IEEE.STD_LOGIC_UNSIGNED.ALL;
|
use IEEE.std_logic_unsigned.all;
|
use IEEE.std_logic_unsigned.all;
|
---- Uncomment the following library declaration if instantiating
|
---- Uncomment the following library declaration if instantiating
|
---- any Xilinx primitives in this code.
|
---- any Xilinx primitives in this code.
|
--library UNISIM;
|
--library UNISIM;
|
--use UNISIM.VComponents.all;
|
--use UNISIM.VComponents.all;
|
|
|
entity HashChain is
|
entity HashChain is
|
Port ( Data_in : in std_logic_vector (7 downto 0); -- Data input from byte stream
|
Port ( Data_in : in std_logic_vector (7 downto 0); -- Data input from byte stream
|
Hash_o : out real; -- Hash value of previous data
|
Hash_o : out real; -- Hash value of previous data
|
Clock, -- Clock
|
Clock, -- Clock
|
Reset, -- Reset
|
Reset, -- Reset
|
Output_E : in bit -- Output Enable
|
Output_E : in bit -- Output Enable
|
);
|
);
|
end HashChain;
|
end HashChain;
|
|
|
|
|
--From Robert Sedgwicks Algorithms in C
|
--From Robert Sedgwicks Algorithms in C
|
architecture RSHash of HashChain is
|
architecture RSHash of HashChain is
|
signal mode,
|
signal mode,
|
data : integer;
|
data : integer;
|
|
|
begin
|
begin
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
4;
|
4;
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
Process (mode)
|
Process (mode)
|
variable a, b, hash : real ; -- Variables for calculating the output
|
variable a, b, hash : real ; -- Variables for calculating the output
|
begin
|
begin
|
case mode is
|
case mode is
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
hash := hash * a;
|
hash := hash * a;
|
hash := hash + data;
|
hash := hash + data;
|
a := a * b;
|
a := a * b;
|
when 2 =>
|
when 2 =>
|
hash := 0.0; -- Reset
|
hash := 0.0; -- Reset
|
a:=378551.0; -- Reset
|
a:=378551.0; -- Reset
|
b:=63689.0; -- Reset
|
b:=63689.0; -- Reset
|
when 3=> -- Need to implement a disable output section
|
when 3=> -- Need to implement a disable output section
|
|
|
when OTHERS => -- Do nothing
|
when OTHERS => -- Do nothing
|
|
|
End case;
|
End case;
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
end process;
|
end process;
|
end RSHash;
|
end RSHash;
|
|
|
--An algorithm produced by Professor Daniel J. Bernstein and
|
--An algorithm produced by Professor Daniel J. Bernstein and
|
--shown first to the world on the usenet newsgroup comp.lang.c.
|
--shown first to the world on the usenet newsgroup comp.lang.c.
|
--It is one of the most efficient hash functions ever published
|
--It is one of the most efficient hash functions ever published
|
--Actual function hash(i) = hash(i - 1) * 33 + str[i];
|
--Actual function hash(i) = hash(i - 1) * 33 + str[i];
|
--Function now implemented using XOR hash(i) = hash(i - 1) * 33 ^ str[i];
|
--Function now implemented using XOR hash(i) = hash(i - 1) * 33 ^ str[i];
|
architecture DJB of HashChain is
|
architecture DJB of HashChain is
|
signal mode,
|
signal mode,
|
data : integer;
|
data : integer;
|
|
|
begin
|
begin
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
4;
|
4;
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
Process (mode)
|
Process (mode)
|
variable a, b, hash : real ; -- Variables for calculating the output
|
variable a, b, hash : real ; -- Variables for calculating the output
|
begin
|
begin
|
case mode is
|
case mode is
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
a := hash * 33.0;
|
a := hash * 33.0;
|
hash := a + hash + data;
|
hash := a + hash + data;
|
when 2 =>
|
when 2 =>
|
hash := 5831.0; -- Reset
|
hash := 5831.0; -- Reset
|
when 3=> -- Need to implement a disable output section
|
when 3=> -- Need to implement a disable output section
|
|
|
when OTHERS => -- Do nothing
|
when OTHERS => -- Do nothing
|
|
|
End case;
|
End case;
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
end process;
|
end process;
|
end DJB;
|
end DJB;
|
|
|
|
|
--This algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library.
|
--This algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library.
|
--it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits.
|
--it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits.
|
--it also happens to be a good general hashing function with good distribution.
|
--it also happens to be a good general hashing function with good distribution.
|
--the actual function is hash(i) = hash(i - 1) * 65599 + str[i];
|
--the actual function is hash(i) = hash(i - 1) * 65599 + str[i];
|
architecture sdbm of HashChain is
|
architecture sdbm of HashChain is
|
signal mode,
|
signal mode,
|
data : integer;
|
data : integer;
|
|
|
begin
|
begin
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
4;
|
4;
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
Process (mode)
|
Process (mode)
|
variable a, b, hash : real ; -- Variables for calculating the output
|
variable a, b, hash : real ; -- Variables for calculating the output
|
begin
|
begin
|
case mode is
|
case mode is
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
a := hash * 65599.0;
|
a := hash * 65599.0;
|
hash := a + hash + data;
|
hash := a + hash + data;
|
when 2 =>
|
when 2 =>
|
hash := 0.0; -- Reset
|
hash := 0.0; -- Reset
|
when 3=> -- Need to implement a disable output section
|
when 3=> -- Need to implement a disable output section
|
|
|
when OTHERS => -- Do nothing
|
when OTHERS => -- Do nothing
|
|
|
End case;
|
End case;
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
end process;
|
end process;
|
|
|
