wimlib.net Git - wimlib/blob - 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/unaligned.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 /*
  32  * Hash the 2-byte sequence beginning at @p, producing a hash of length
  33  * @num_bits bits.  At least 2 bytes of data must be available at @p.
  34  */
  35 static inline u32
  36 lz_hash_2_bytes(const u8 *p, unsigned num_bits)
  37 {
  38         u32 seq = load_u16_unaligned(p);
  39         if (num_bits >= 16)
  40                 return seq;
  41         return lz_hash(seq, num_bits);
  42 }
  43
  44 /*
  45  * Hash the 3-byte sequence beginning at @p, producing a hash of length
  46  * @num_bits bits.  At least LZ_HASH3_REQUIRED_NBYTES bytes of data must be
  47  * available at @p; note that this may be more than 3.
  48  */
  49 static inline u32
  50 lz_hash_3_bytes(const u8 *p, unsigned num_bits)
  51 {
  52         u32 seq = load_u24_unaligned(p);
  53         if (num_bits >= 24)
  54                 return seq;
  55         return lz_hash(seq, num_bits);
  56 }
  57
  58 #define LZ_HASH3_REQUIRED_NBYTES LOAD_U24_REQUIRED_NBYTES
  59
  60 #endif /* _LZ_HASH_H */