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/types.h"
15 /* Constant for the multiplicative hash function. */
16 #define LZ_HASH_MULTIPLIER 0x1E35A7BD
18 /* Hash the next 3-byte sequence in the window, producing a hash of length
19 * 'num_bits' bits. 4 bytes must be available, since 32-bit unaligned load is
20 * faster on some architectures. */
22 lz_hash(const u8 *p, unsigned int num_bits)
27 #if defined(__i386__) || defined(__x86_64__)
28 /* Unaligned access allowed, and little endian CPU.
29 * Callers ensure that at least 4 (not 3) bytes are remaining. */
30 str = *(const u32 *)p & 0xFFFFFF;
32 str = ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
35 hash = str * LZ_HASH_MULTIPLIER;
37 /* High bits are more random than the low bits. */
38 return hash >> (32 - num_bits);
41 /* The number of bytes being hashed. */
42 #define LZ_HASH_NBYTES 3
44 /* Number of bytes the hash function actually requires be available, due to the
45 * possibility of an unaligned load. */
46 #define LZ_HASH_REQUIRED_NBYTES 4
48 #endif /* _WIMLIB_LZ_HASH3_H */