1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file       lz_encoder_hash.h
4 /// \brief      Hash macros for match finders
5 //
6 //  Author:     Igor Pavlov
7 //
8 //  This file has been put into the public domain.
9 //  You can do whatever you want with this file.
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12 
13 #ifndef LZMA_LZ_ENCODER_HASH_H
14 #define LZMA_LZ_ENCODER_HASH_H
15 
16 #if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
17 	// This is to make liblzma produce the same output on big endian
18 	// systems that it does on little endian systems. lz_encoder.c
19 	// takes care of including the actual table.
20 	extern const uint32_t lzma_lz_hash_table[256];
21 #	define hash_table lzma_lz_hash_table
22 #else
23 #	include "check.h"
24 #	define hash_table lzma_crc32_table[0]
25 #endif
26 
27 #define HASH_2_SIZE (UINT32_C(1) << 10)
28 #define HASH_3_SIZE (UINT32_C(1) << 16)
29 #define HASH_4_SIZE (UINT32_C(1) << 20)
30 
31 #define HASH_2_MASK (HASH_2_SIZE - 1)
32 #define HASH_3_MASK (HASH_3_SIZE - 1)
33 #define HASH_4_MASK (HASH_4_SIZE - 1)
34 
35 #define FIX_3_HASH_SIZE (HASH_2_SIZE)
36 #define FIX_4_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
37 #define FIX_5_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE + HASH_4_SIZE)
38 
39 // Endianness doesn't matter in hash_2_calc() (no effect on the output).
40 #ifdef TUKLIB_FAST_UNALIGNED_ACCESS
41 #	define hash_2_calc() \
42 		const uint32_t hash_value = *(const uint16_t *)(cur);
43 #else
44 #	define hash_2_calc() \
45 		const uint32_t hash_value \
46 			= (uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)
47 #endif
48 
49 #define hash_3_calc() \
50 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
51 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
52 	const uint32_t hash_value \
53 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & mf->hash_mask
54 
55 #define hash_4_calc() \
56 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
57 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
58 	const uint32_t hash_3_value \
59 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
60 	const uint32_t hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
61 			^ (hash_table[cur[3]] << 5)) & mf->hash_mask
62 
63 
64 // The following are not currently used.
65 
66 #define hash_5_calc() \
67 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
68 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
69 	const uint32_t hash_3_value \
70 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
71 	uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
72 			^ hash_table[cur[3]] << 5); \
73 	const uint32_t hash_value \
74 			= (hash_4_value ^ (hash_table[cur[4]] << 3)) \
75 				& mf->hash_mask; \
76 	hash_4_value &= HASH_4_MASK
77 
78 /*
79 #define hash_zip_calc() \
80 	const uint32_t hash_value \
81 			= (((uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)) \
82 				^ hash_table[cur[2]]) & 0xFFFF
83 */
84 
85 #define hash_zip_calc() \
86 	const uint32_t hash_value \
87 			= (((uint32_t)(cur[2]) | ((uint32_t)(cur[0]) << 8)) \
88 				^ hash_table[cur[1]]) & 0xFFFF
89 
90 #define mt_hash_2_calc() \
91 	const uint32_t hash_2_value \
92 			= (hash_table[cur[0]] ^ cur[1]) & HASH_2_MASK
93 
94 #define mt_hash_3_calc() \
95 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
96 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
97 	const uint32_t hash_3_value \
98 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK
99 
100 #define mt_hash_4_calc() \
101 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
102 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
103 	const uint32_t hash_3_value \
104 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
105 	const uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
106 			(hash_table[cur[3]] << 5)) & HASH_4_MASK
107 
108 #endif
109