464c01af2c29e9a84a57a8b97195854417572a22
[wimlib] / include / wimlib / lz_hash.h
1 /*
2  * lz_hash.h
3  *
4  * Hashing for Lempel-Ziv matchfinding.
5  *
6  * Author:      Eric Biggers
7  * Year:        2014, 2015
8  *
9  * The author dedicates this file to the public domain.
10  * You can do whatever you want with this file.
11  */
12
13 #ifndef _LZ_HASH_H
14 #define _LZ_HASH_H
15
16 #include "wimlib/types.h"
17
18 /*
19  * The hash function: given a sequence prefix held in the low-order bits of a
20  * 32-bit value, multiply by a carefully-chosen large constant.  Discard any
21  * bits of the product that don't fit in a 32-bit value, but take the
22  * next-highest @num_bits bits of the product as the hash value, as those have
23  * the most randomness.
24  */
25 static inline u32
26 lz_hash(u32 seq, unsigned num_bits)
27 {
28         return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
29 }
30
31 #endif /* _LZ_HASH_H */