2 * lz_hash.h - hashing for Lempel-Ziv matchfinding
4 * Copyright 2022 Eric Biggers
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
31 #include "wimlib/types.h"
34 * The hash function: given a sequence prefix held in the low-order bits of a
35 * 32-bit value, multiply by a carefully-chosen large constant. Discard any
36 * bits of the product that don't fit in a 32-bit value, but take the
37 * next-highest @num_bits bits of the product as the hash value, as those have
38 * the most randomness.
40 static forceinline u32
41 lz_hash(u32 seq, unsigned num_bits)
43 return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
46 #endif /* _LZ_HASH_H */