wimlib.net Git - wimlib/blob - include/wimlib/lz_hash.h

   1 /*
   2  * lz_hash.h - hashing for Lempel-Ziv matchfinding
   3  *
   4  * The following copying information applies to this specific source code file:
   5  *
   6  * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
   7  *
   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").
  12  *
  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.
  16  *
  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/>.
  19  */
  20
  21 #ifndef _LZ_HASH_H
  22 #define _LZ_HASH_H
  23
  24 #include "wimlib/types.h"
  25
  26 /*
  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.
  32  */
  33 static inline u32
  34 lz_hash(u32 seq, unsigned num_bits)
  35 {
  36         return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
  37 }
  38
  39 #endif /* _LZ_HASH_H */