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