head 1.8; access; symbols arelease:1.1.1.1 avendor:1.1.1; locks; strict; comment @# @; 1.8 date 2006.05.24.02.03.30; author smallcode; state Exp; branches; next 1.7; commitid 35b64473bef14567; 1.7 date 2006.05.15.04.13.55; author smallcode; state Exp; branches; next 1.6; commitid 1ea8446800004567; 1.6 date 2006.04.02.21.25.18; author smallcode; state Exp; branches; next 1.5; commitid 49a4443041244567; 1.5 date 2006.04.02.08.30.05; author smallcode; state Exp; branches; next 1.4; commitid 26b2442f8b6f4567; 1.4 date 2006.03.28.00.45.04; author smallcode; state Exp; branches; next 1.3; commitid 6ffe4428870e4567; 1.3 date 2005.11.15.16.08.11; author smallcode; state Exp; branches; next 1.2; commitid 6d92437a07e54567; 1.2 date 2005.11.09.15.38.49; author smallcode; state Exp; branches; next 1.1; commitid 794e437217f84567; 1.1 date 2005.11.07.08.56.45; author smallcode; state Exp; branches 1.1.1.1; next ; commitid 66c0436f16cb4567; 1.1.1.1 date 2005.11.07.08.56.45; author smallcode; state Exp; branches; next ; commitid 66c0436f16cb4567; desc @@ 1.8 log @Hash key generating algorithm working, uses les resources and resource usage is Number of Slices: 1 Number of 4 input LUTs: 1 Number of bonded IOBs: 46 If synthesised in a process the number of slices and LUT's used increases but the number of IOB's decreases by 2 to 44 @ text @-------------------------------------------------------------------------------- -- Create Date: 03:46:54 10/31/05 -- Design Name: -- Module Name: Hash - Behavioral -- Project Name: Deflate -- Revision: -- Revision 0.25 - Only one hash algorithm -- Additional Comments: -- The remarked comments for synchronous reser result in the use of more 192 slices witn a maximum frequency of 129 Mhz -- But if the code is commented as it is now the number of slices utlised is 5 without a known clock , need to specifiy that as a compile time constraint. -- TO DO: -- Wishbone interface -- Concurrent Hashkey generation -------------------------------------------------------------------------------- library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity HashChain is 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 ); Port ( Hash_O : inout std_logic_vector (Hash_Width - 1 downto 0); -- Hash value of previous data Data_in : in std_logic_vector (Data_Width-1 downto 0); -- Data input from byte stream Clock, -- Clock Reset, Start, -- Reset O_E : in bit ; -- Output Enable Busy, Done : out bit -- Enabled when the hash key has been generated ); end HashChain; --An algorithm produced by Professor Daniel J. Bernstein and --shown first to the world on the usenet newsgroup comp.lang.c. --It is one of the most efficient hash functions ever published --Actual function hash(i) = hash(i - 1) * 33 + str[i]; --Function now implemented using XOR hash(i) = hash(i - 1) * 33 ^ str[i]; architecture DJB2 of HashChain is signal mode: integer := 0; signal tempval, hash:std_logic_vector (Hash_Width - 1 downto 0):= X"00000000" ; signal multiplier:std_logic_vector (39 downto 0):= X"0000000000" ; begin mealymachine: process (Clock) begin if Reset = '1' and Clock = '1' then -- Reset mode <= 0; elsif start = '1' and Clock = '1' then -- Start mode <= 1; -- Multiply previous key by 33 ( Clock = 1 ) elsif mode = 1 then mode <= 2; -- Ex-OR input with existing key ( Clock = 0 ) elsif mode = 2 then mode <= 3; -- Latch output ( Clock = 1 ) else mode <= 4; end if; end process mealymachine; hash <= X"000016c7" when mode = 0 else --initialise the hash key to 5831 multiplier(31 downto 0) xor tempval when mode = 2 else --Ex or with the current input hash; --keep current value multiplier <= hash * X"21" when mode = 1 else --Multiply by 33 X"0000000000"; tempval <= X"00000000" when mode /= 1 else --Temporary value to be able to Exor the input with the hash key tempval+ Data_in; busy <= '1' when mode > 0 and mode < 3 else --Indicates that the key is being generated '0' ; Hash_O <= hash when mode = 3 and O_E = '1' else --Output buffer Hash_O; --Hash op bufffer done <= '1' when mode = 3 else --1 after hash key has been calculated '0'; end DJB2; Configuration djb2_hash of hashchain is for djb2 end for; end djb2_hash; @ 1.7 log @Working combinitarioal hash key generator, improved speed and effiency @ text @d19 1 a19 2 use IEEE.std_logic_unsigned.all; d26 1 a26 1 Port ( Hash_O : inout std_logic_vector (Hash_Width - 1 downto 0); -- Hash value of previous data d30 1 a30 1 Star_t, -- Reset d43 7 a49 2 signal mode: integer; signal tempval, hash :std_logic_vector (Hash_Width - 1 downto 0); d51 16 d68 2 a69 11 mode <= 0 when (Reset = '1' or mode > 4) and clock = '1' else -- Rezet 1 when Star_t = '1' and (mode = 0 or mode < 5) and clock ='1' else -- Start key generation 2 when mode = 1 and clock = '0' else -- Just the rest of the statemachine 3 when mode = 2 and clock = '1' else 4 when mode = 3 and clock = '0' and O_E = '1' else 5 ; hash <= X"16c7" when mode = 0 else --hash sll 5 when mode = 1 else hash xor tempval when mode =3 else hash; d71 1 a71 1 tempval <= X"0000" when mode /= 2 else d74 3 a76 2 busy <= '1' when mode > 0 and mode <3 else '0'; d78 3 a80 3 Hash_O <= hash when mode =3 else Hash_O when (mode = 4 or mode = 5) and O_E = '1' else X"0000"; d82 1 a82 1 done <= '1' when mode = 3 else @ 1.6 log @No changes @ text @d27 1 a27 1 Port ( Hash_o : out std_logic_vector (Hash_Width - 1 downto 0); -- Hash value of previous data d30 5 a34 3 Reset, -- Reset Output_E : in bit ; -- Output Enable Hash_Generated : out bit -- Enabled when the hash key has been generated d45 1 a45 1 signal tempval:std_logic_vector (Hash_Width - 1 downto 0); d48 26 a73 32 mode <= 0 when clock = '1' and reset = '0' and Output_E = '1' and mode = 4 else -- Active data being latched to output 1 when clock = '0' and reset = '0' and Output_E = '1' and mode = 0 else -- No change to output till thge next clock 2 when clock = '1' and reset = '0' and Output_E = '1' and mode = 1 else -- Reset active 3 when clock = '0' and reset = '0' and Output_E = '1' and mode = 2 else -- Reset active 4 when clock = '1' and reset = '0' and Output_E = '1' and mode = 3 else -- Disable output -- Synchronous reset -- Remove remark and semi colon from 8 but it results in greater resource utilisation 8 when clock ='1' and reset ='1'; Hash_Generated <= '0' when mode <4 or mode = 8 else '1'; Process (clock) variable a, b, hash :std_logic_vector (Hash_Width - 1 downto 0); -- Variables for calculating the output variable hashg:bit; begin case mode is when 0 => --Calculate the hash key of the current input value using the Data on the input vector b := b + Data_in; --Store the input value into a variable when 1 => a := hash * X"21"; --Multiply the hash value by 33 when 2 => tempval <= a+hash; when 3 => -- hash := tempval xor b; --Xor the above value to the previous hashkey to generate the new hash key when 4 => b := X"00000000"; when others=> hash := X"16c7"; --Reset initial hash value to 5831 End case; hash_o<= hash; -- Latch the clculated hash value to the output end process; a74 12 --Configuration: --Assign the name of the algorithm as the configuration. --Configuration rs_hash of hashchain is --for rshash --end for; --end rs_hash; --Configuration djb_hash of hashchain is --for djb --end for; --end djb_hash; a79 6 --Configuration sdbm_hash of hashchain is --for sdbm --end for; --end sdbm_hash; @ 1.5 log @Reduced resource usage, but while compiling using default constraints the xilinx ise is unable to recognise the clock signal. Uses 5 slices and 8 flipflops @ text @d53 1 a53 1 8 ;-- when clock ='1' and reset ='1'; @ 1.4 log @Using only the DJB2 algorithm, uses a 112 slices with a max clock frequency of 37 Mhz @ text @d7 1 a7 1 -- Revision 0.02 - File Created d9 2 a10 1 -- 3 Hashing algorithms with the same interface. d31 3 a33 2 Output_E : in bit -- Output Enable ); a44 6 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 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 3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output 4; d46 13 a58 1 Process (mode) d60 1 d64 2 d67 5 d73 2 a74 9 b := b + Data_in; tempval <= a+hash; hash := tempval xor b; --Add the above value to the previous hash and add the input data when 2 => --Reset hash := X"16c7"; --Reset initial hash value to 5831 when 3=> -- Need to implement a disable output section when OTHERS => -- Do nothing @ 1.3 log @A few chages made to improve readability @ text @d33 1 a33 67 --From Robert Sedgwicks Algorithms in C architecture RSHash of HashChain is signal mode: integer; begin 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 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 3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output 4; Process (mode) variable a, b, hash : std_logic_vector (Hash_Width -1 downto 0); -- Variables for calculating the output begin case mode is when 0 => --Calculate the hash key of the current input value using the input data hash := hash * a; hash := hash + Data_in; a := a * b; when 2 => hash := X"0000_0000"; -- Reset hash value to 0 a:=X"0005_C6B7"; -- Reset a to 378551 b:=X"0000_F8C9"; -- Reset b to 63689 when 3=> -- Need to implement a disable output section when OTHERS => -- Do nothing End case; hash_o<= hash; -- Latch the calculated hash value to the output end process; end RSHash; --An algorithm produced by Professor Daniel J. Bernstein and --shown first to the world on the usenet newsgroup comp.lang.c. --It is one of the most efficient hash functions ever published --Actual function hash(i) = hash(i - 1) * 33 + str[i]; architecture DJB of HashChain is signal mode: integer; begin 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 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 3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output 4; Process (mode) variable a, b, hash :std_logic_vector (Hash_Width - 1 downto 0); -- Variables for calculating the output begin case mode is when 0 => --Calculate the hash key of the current input value using the Data on the input vector a := hash * X"21"; --Multiply the hash value by 33 hash := a + hash + Data_in; --Add the above value to the previous hash and add the input data when 2 => --Reset hash := X"16c7"; --Reset initial hash value to 5831 when 3=> -- Need to implement a disable output section when OTHERS => -- Do nothing End case; hash_o<= hash; -- Latch the clculated hash value to the output end process; end DJB; d41 1 a41 1 d56 4 a59 1 hash := (a + hash) xor Data_in; --Add the above value to the previous hash and add the input data a69 33 --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 also happens to be a good general hashing function with good distribution. --the actual function is hash(i) = hash(i - 1) * 65599 + str[i]; architecture sdbm of HashChain is signal mode: integer; begin 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 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 3 when clock = '1' and reset = '0' and Output_E = '0' else -- Disable output 4; Process (mode) variable a, b, hash : std_logic_vector (Hash_Width - 1 downto 0); -- Variables for calculating the output begin case mode is when 0 => --Calculate the hash key of the current input value using the Data on the input vector a := hash * X"1003f"; --Multiply the previous hash with 65599 hash := a + hash + Data_in; --Add the above result to theprevious hash and add the input data when 2 => hash := X"0"; -- Reset when 3=> -- Need to implement a disable output section when OTHERS => -- Do nothing End case; hash_o<= hash; -- Assign the clculated hash value to the output end process; end sdbm; d73 9 a81 9 Configuration rs_hash of hashchain is for rshash end for; end rs_hash; Configuration djb_hash of hashchain is for djb end for; end djb_hash; d88 4 a91 4 Configuration sdbm_hash of hashchain is for sdbm end for; end sdbm_hash; @ 1.2 log @Modified to remove unused declarations to use std logic @ text @a70 1 --Function now implemented using XOR hash(i) = hash(i - 1) * 33 ^ str[i]; d100 7 d108 25 d164 25 a188 1 end sdbm;@ 1.1 log @Initial revision @ text @a1 2 -- Company: -- Engineer: d7 1 a7 1 -- Revision 0.01 - File Created d9 4 a12 1 -- d18 1 a18 5 use IEEE.std_logic_unsigned.all; ---- Uncomment the following library declaration if instantiating ---- any Xilinx primitives in this code. --library UNISIM; --use UNISIM.VComponents.all; d21 10 a30 5 Port ( Data_in : in std_logic_vector (7 downto 0); -- Data input from byte stream Hash_o : out real; -- Hash value of previous data Clock, -- Clock Reset, -- Reset Output_E : in bit -- Output Enable d37 1 a37 3 signal mode, data : integer; d45 1 a45 1 --data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic d47 1 a47 1 variable a, b, hash : real ; -- Variables for calculating the output d50 1 a50 1 when 0 => --Calculate the hash key of the current input value using the Data on the input vector d52 1 a52 1 hash := hash + data; d55 4 a58 4 hash := 0.0; -- Reset a:=378551.0; -- Reset b:=63689.0; -- Reset when 3=> -- Need to implement a disable output section d60 1 a60 1 when OTHERS => -- Do nothing d63 1 a63 1 hash_o<= hash; -- Assign the clculated hash value to the output d73 1 a73 2 signal mode, data : integer; d82 1 a82 1 --data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic d84 1 a84 1 variable a, b, hash : real ; -- Variables for calculating the output d87 6 a92 6 when 0 => --Calculate the hash key of the current input value using the Data on the input vector a := hash * 33.0; hash := a + hash + data; when 2 => hash := 5831.0; -- Reset when 3=> -- Need to implement a disable output section d94 1 a94 1 when OTHERS => -- Do nothing d97 1 a97 1 hash_o<= hash; -- Assign the clculated hash value to the output d107 1 a107 2 signal mode, data : integer; d116 1 a116 1 --data <= Data_in; --Need to convert the input standard logic input to a form that can be processed using arthimetic d118 1 a118 1 variable a, b, hash : real ; -- Variables for calculating the output d121 3 a123 3 when 0 => --Calculate the hash key of the current input value using the Data on the input vector a := hash * 65599.0; hash := a + hash + data; d125 2 a126 2 hash := 0.0; -- Reset when 3=> -- Need to implement a disable output section d128 1 a128 1 when OTHERS => -- Do nothing d131 1 a131 1 hash_o<= hash; -- Assign the clculated hash value to the output @ 1.1.1.1 log @Hashing algorithms DJB and SDBM @ text @@