2 * lz_hash.h - hashing for Lempel-Ziv matchfinding
4 * The following copying information applies to this specific source code file:
6 * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
8 * To the extent possible under law, the author(s) have dedicated all copyright
9 * and related and neighboring rights to this software to the public domain
10 * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
11 * Dedication (the "CC0").
13 * This software is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
17 * You should have received a copy of the CC0 along with this software; if not
18 * see <http://creativecommons.org/publicdomain/zero/1.0/>.
24 #include "wimlib/types.h"
27 * The hash function: given a sequence prefix held in the low-order bits of a
28 * 32-bit value, multiply by a carefully-chosen large constant. Discard any
29 * bits of the product that don't fit in a 32-bit value, but take the
30 * next-highest @num_bits bits of the product as the hash value, as those have
31 * the most randomness.
33 static forceinline u32
34 lz_hash(u32 seq, unsigned num_bits)
36 return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
39 #endif /* _LZ_HASH_H */