1 |
2 |
smallcode |
--------------------------------------------------------------------------------
|
2 |
|
|
-- Company:
|
3 |
|
|
-- Engineer:
|
4 |
|
|
-- Create Date: 03:46:54 10/31/05
|
5 |
|
|
-- Design Name:
|
6 |
|
|
-- Module Name: Hash - Behavioral
|
7 |
|
|
-- Project Name: Deflate
|
8 |
|
|
-- Revision:
|
9 |
|
|
-- Revision 0.01 - File Created
|
10 |
|
|
-- Additional Comments:
|
11 |
|
|
--
|
12 |
|
|
--------------------------------------------------------------------------------
|
13 |
|
|
library IEEE;
|
14 |
|
|
use IEEE.STD_LOGIC_1164.ALL;
|
15 |
|
|
use IEEE.STD_LOGIC_ARITH.ALL;
|
16 |
|
|
use IEEE.STD_LOGIC_UNSIGNED.ALL;
|
17 |
|
|
use IEEE.std_logic_unsigned.all;
|
18 |
|
|
---- Uncomment the following library declaration if instantiating
|
19 |
|
|
---- any Xilinx primitives in this code.
|
20 |
|
|
--library UNISIM;
|
21 |
|
|
--use UNISIM.VComponents.all;
|
22 |
|
|
|
23 |
|
|
entity HashChain is
|
24 |
|
|
Port ( Data_in : in std_logic_vector (7 downto 0); -- Data input from byte stream
|
25 |
|
|
Hash_o : out real; -- Hash value of previous data
|
26 |
|
|
Clock, -- Clock
|
27 |
|
|
Reset, -- Reset
|
28 |
|
|
Output_E : in bit -- Output Enable
|
29 |
|
|
);
|
30 |
|
|
end HashChain;
|
31 |
|
|
|
32 |
|
|
|
33 |
|
|
--From Robert Sedgwicks Algorithms in C
|
34 |
|
|
architecture RSHash of HashChain is
|
35 |
|
|
signal mode,
|
36 |
|
|
data : integer;
|
37 |
|
|
|
38 |
|
|
begin
|
39 |
|
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
40 |
|
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
41 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
42 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
43 |
|
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
44 |
|
|
4;
|
45 |
|
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
46 |
|
|
Process (mode)
|
47 |
|
|
variable a, b, hash : real ; -- Variables for calculating the output
|
48 |
|
|
begin
|
49 |
|
|
case mode is
|
50 |
|
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
51 |
|
|
hash := hash * a;
|
52 |
|
|
hash := hash + data;
|
53 |
|
|
a := a * b;
|
54 |
|
|
when 2 =>
|
55 |
|
|
hash := 0.0; -- Reset
|
56 |
|
|
a:=378551.0; -- Reset
|
57 |
|
|
b:=63689.0; -- Reset
|
58 |
|
|
when 3=> -- Need to implement a disable output section
|
59 |
|
|
|
60 |
|
|
when OTHERS => -- Do nothing
|
61 |
|
|
|
62 |
|
|
End case;
|
63 |
|
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
64 |
|
|
end process;
|
65 |
|
|
end RSHash;
|
66 |
|
|
|
67 |
|
|
--An algorithm produced by Professor Daniel J. Bernstein and
|
68 |
|
|
--shown first to the world on the usenet newsgroup comp.lang.c.
|
69 |
|
|
--It is one of the most efficient hash functions ever published
|
70 |
|
|
--Actual function hash(i) = hash(i - 1) * 33 + str[i];
|
71 |
|
|
--Function now implemented using XOR hash(i) = hash(i - 1) * 33 ^ str[i];
|
72 |
|
|
architecture DJB of HashChain is
|
73 |
|
|
signal mode,
|
74 |
|
|
data : integer;
|
75 |
|
|
|
76 |
|
|
begin
|
77 |
|
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
78 |
|
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
79 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
80 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
81 |
|
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
82 |
|
|
4;
|
83 |
|
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
84 |
|
|
Process (mode)
|
85 |
|
|
variable a, b, hash : real ; -- Variables for calculating the output
|
86 |
|
|
begin
|
87 |
|
|
case mode is
|
88 |
|
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
89 |
|
|
a := hash * 33.0;
|
90 |
|
|
hash := a + hash + data;
|
91 |
|
|
when 2 =>
|
92 |
|
|
hash := 5831.0; -- Reset
|
93 |
|
|
when 3=> -- Need to implement a disable output section
|
94 |
|
|
|
95 |
|
|
when OTHERS => -- Do nothing
|
96 |
|
|
|
97 |
|
|
End case;
|
98 |
|
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
99 |
|
|
end process;
|
100 |
|
|
end DJB;
|
101 |
|
|
|
102 |
|
|
|
103 |
|
|
--This algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library.
|
104 |
|
|
--it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits.
|
105 |
|
|
--it also happens to be a good general hashing function with good distribution.
|
106 |
|
|
--the actual function is hash(i) = hash(i - 1) * 65599 + str[i];
|
107 |
|
|
architecture sdbm of HashChain is
|
108 |
|
|
signal mode,
|
109 |
|
|
data : integer;
|
110 |
|
|
|
111 |
|
|
begin
|
112 |
|
|
mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' else -- Active data being latched to output
|
113 |
|
|
1 when clock = '0' and reset = '0' and Output_E = '1' else -- No change to output till thge next clock
|
114 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '1' else -- Reset active
|
115 |
|
|
2 when clock = '1' and reset = '1' and Output_E = '0' else -- Reset active
|
116 |
|
|
3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output
|
117 |
|
|
4;
|
118 |
|
|
--data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic
|
119 |
|
|
Process (mode)
|
120 |
|
|
variable a, b, hash : real ; -- Variables for calculating the output
|
121 |
|
|
begin
|
122 |
|
|
case mode is
|
123 |
|
|
when 0 => --Calculate the hash key of the current input value using the Data on the input vector
|
124 |
|
|
a := hash * 65599.0;
|
125 |
|
|
hash := a + hash + data;
|
126 |
|
|
when 2 =>
|
127 |
|
|
hash := 0.0; -- Reset
|
128 |
|
|
when 3=> -- Need to implement a disable output section
|
129 |
|
|
|
130 |
|
|
when OTHERS => -- Do nothing
|
131 |
|
|
|
132 |
|
|
End case;
|
133 |
|
|
hash_o<= hash; -- Assign the clculated hash value to the output
|
134 |
|
|
end process;
|
135 |
|
|
end sdbm;
|