Home | History | Annotate | Line # | Download | only in lz 
      1 // SPDX-License-Identifier: 0BSD
      2 
      3 ///////////////////////////////////////////////////////////////////////////////
      4 //
      5 /// \file       lz_encoder_hash.h
      6 /// \brief      Hash macros for match finders
      7 //
      8 //  Authors:    Igor Pavlov
      9 //              Lasse Collin
     10 //
     11 ///////////////////////////////////////////////////////////////////////////////
     12 
     13 #ifndef LZMA_LZ_ENCODER_HASH_H
     14 #define LZMA_LZ_ENCODER_HASH_H
     15 
     16 // We need to know if CRC32_GENERIC is defined and we may need the declaration
     17 // of lzma_crc32_table[][].
     18 #include "crc_common.h"
     19 
     20 // If HAVE_SMALL is defined, then lzma_crc32_table[][] exists and
     21 // it's little endian even on big endian systems.
     22 //
     23 // If HAVE_SMALL isn't defined, lzma_crc32_table[][] is in native endian
     24 // but we want a little endian one so that the compressed output won't
     25 // depend on the processor endianness. Big endian systems are less common
     26 // so those get the burden of an extra 1 KiB table.
     27 //
     28 // If HAVE_SMALL isn't defined and CRC32_GENERIC isn't defined either,
     29 // then lzma_crc32_table[][] doesn't exist.
     30 #if defined(HAVE_SMALL) \
     31 		|| (defined(CRC32_GENERIC) && !defined(WORDS_BIGENDIAN))
     32 #	define hash_table lzma_crc32_table[0]
     33 #else
     34 	// lz_encoder.c takes care of including the actual table.
     35 	lzma_attr_visibility_hidden
     36 	extern const uint32_t lzma_lz_hash_table[256];
     37 #	define hash_table lzma_lz_hash_table
     38 #	define LZMA_LZ_HASH_TABLE_IS_NEEDED 1
     39 #endif
     40 
     41 #define HASH_2_SIZE (UINT32_C(1) << 10)
     42 #define HASH_3_SIZE (UINT32_C(1) << 16)
     43 #define HASH_4_SIZE (UINT32_C(1) << 20)
     44 
     45 #define HASH_2_MASK (HASH_2_SIZE - 1)
     46 #define HASH_3_MASK (HASH_3_SIZE - 1)
     47 #define HASH_4_MASK (HASH_4_SIZE - 1)
     48 
     49 #define FIX_3_HASH_SIZE (HASH_2_SIZE)
     50 #define FIX_4_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
     51 #define FIX_5_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE + HASH_4_SIZE)
     52 
     53 // Endianness doesn't matter in hash_2_calc() (no effect on the output).
     54 #ifdef TUKLIB_FAST_UNALIGNED_ACCESS
     55 #	define hash_2_calc() \
     56 		const uint32_t hash_value = read16ne(cur)
     57 #else
     58 #	define hash_2_calc() \
     59 		const uint32_t hash_value \
     60 			= (uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)
     61 #endif
     62 
     63 #define hash_3_calc() \
     64 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
     65 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
     66 	const uint32_t hash_value \
     67 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & mf->hash_mask
     68 
     69 #define hash_4_calc() \
     70 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
     71 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
     72 	const uint32_t hash_3_value \
     73 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
     74 	const uint32_t hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
     75 			^ (hash_table[cur[3]] << 5)) & mf->hash_mask
     76 
     77 
     78 // The following are not currently used.
     79 
     80 #define hash_5_calc() \
     81 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
     82 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
     83 	const uint32_t hash_3_value \
     84 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
     85 	uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
     86 			^ hash_table[cur[3]] << 5); \
     87 	const uint32_t hash_value \
     88 			= (hash_4_value ^ (hash_table[cur[4]] << 3)) \
     89 				& mf->hash_mask; \
     90 	hash_4_value &= HASH_4_MASK
     91 
     92 /*
     93 #define hash_zip_calc() \
     94 	const uint32_t hash_value \
     95 			= (((uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)) \
     96 				^ hash_table[cur[2]]) & 0xFFFF
     97 */
     98 
     99 #define hash_zip_calc() \
    100 	const uint32_t hash_value \
    101 			= (((uint32_t)(cur[2]) | ((uint32_t)(cur[0]) << 8)) \
    102 				^ hash_table[cur[1]]) & 0xFFFF
    103 
    104 #define mt_hash_2_calc() \
    105 	const uint32_t hash_2_value \
    106 			= (hash_table[cur[0]] ^ cur[1]) & HASH_2_MASK
    107 
    108 #define mt_hash_3_calc() \
    109 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
    110 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
    111 	const uint32_t hash_3_value \
    112 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK
    113 
    114 #define mt_hash_4_calc() \
    115 	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
    116 	const uint32_t hash_2_value = temp & HASH_2_MASK; \
    117 	const uint32_t hash_3_value \
    118 			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
    119 	const uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
    120 			(hash_table[cur[3]] << 5)) & HASH_4_MASK
    121 
    122 #endif
    123