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

   1 /*
   2  * lz_hash.h - hashing for Lempel-Ziv matchfinding
   3  *
   4  * Copyright 2022 Eric Biggers
   5  *
   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
  13  * conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  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.
  26  */
  27
  28 #ifndef _LZ_HASH_H
  29 #define _LZ_HASH_H
  30
  31 #include "wimlib/types.h"
  32
  33 /*
  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.
  39  */
  40 static forceinline u32
  41 lz_hash(u32 seq, unsigned num_bits)
  42 {
  43         return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
  44 }
  45
  46 #endif /* _LZ_HASH_H */