4 * 3-byte hashing for Lempel-Ziv matchfinding.
6 * The author dedicates this file to the public domain.
7 * You can do whatever you want with this file.
10 #ifndef _WIMLIB_LZ_HASH3_H
11 #define _WIMLIB_LZ_HASH3_H
13 #include "wimlib/unaligned.h"
15 /* Constant for the multiplicative hash function. */
16 #define LZ_HASH_MULTIPLIER 0x1E35A7BD
19 loaded_u32_to_u24(u32 v)
21 if (CPU_IS_LITTLE_ENDIAN)
28 load_u24_unaligned(const u8 *p)
30 if (UNALIGNED_ACCESS_IS_FAST)
31 return loaded_u32_to_u24(load_u32_unaligned(p));
33 return ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
37 lz_hash_u24(u32 str, unsigned num_bits)
39 return (u32)(str * LZ_HASH_MULTIPLIER) >> (32 - num_bits);
43 * Hash the next 3-byte sequence in the window, producing a hash of length
44 * 'num_bits' bits. At least LZ_HASH_REQUIRED_NBYTES must be available at 'p';
45 * this might be 4 bytes rather than 3 because an unaligned load is faster on
49 lz_hash(const u8 *p, unsigned num_bits)
51 return lz_hash_u24(load_u24_unaligned(p), num_bits);
54 /* The number of bytes being hashed. */
55 #define LZ_HASH_NBYTES 3
57 /* Number of bytes the hash function actually requires be available, due to the
58 * possibility of an unaligned load. */
59 #define LZ_HASH_REQUIRED_NBYTES 4
61 #endif /* _WIMLIB_LZ_HASH3_H */