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

   1 /*
   2  * lz_hash3.h
   3  *
   4  * 3-byte hashing for Lempel-Ziv matchfinding.
   5  *
   6  * The author dedicates this file to the public domain.
   7  * You can do whatever you want with this file.
   8  */
   9
  10 #ifndef _WIMLIB_LZ_HASH3_H
  11 #define _WIMLIB_LZ_HASH3_H
  12
  13 #include "wimlib/unaligned.h"
  14
  15 /* Constant for the multiplicative hash function.  */
  16 #define LZ_HASH_MULTIPLIER 0x1E35A7BD
  17
  18 static inline u32
  19 loaded_u32_to_u24(u32 v)
  20 {
  21         if (CPU_IS_LITTLE_ENDIAN)
  22                 return v & 0xFFFFFF;
  23         else
  24                 return v >> 8;
  25 }
  26
  27 static inline u32
  28 load_u24_unaligned(const u8 *p)
  29 {
  30         if (UNALIGNED_ACCESS_IS_FAST)
  31                 return loaded_u32_to_u24(load_u32_unaligned(p));
  32         else
  33                 return ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
  34 }
  35
  36 static inline u32
  37 lz_hash_u24(u32 str, unsigned num_bits)
  38 {
  39         return (u32)(str * LZ_HASH_MULTIPLIER) >> (32 - num_bits);
  40 }
  41
  42 /*
  43  * Hash the next 3-byte sequence in the window, producing a hash of length
  44  * 'num_bits' bits.  At least LZ_HASH_REQUIRED_NBYTES must be available at 'p';
  45  * this might be 4 bytes rather than 3 because an unaligned load is faster on
  46  * some architectures.
  47  */
  48 static inline u32
  49 lz_hash(const u8 *p, unsigned num_bits)
  50 {
  51         return lz_hash_u24(load_u24_unaligned(p), num_bits);
  52 }
  53
  54 /* The number of bytes being hashed.  */
  55 #define LZ_HASH_NBYTES 3
  56
  57 /* Number of bytes the hash function actually requires be available, due to the
  58  * possibility of an unaligned load.  */
  59 #define LZ_HASH_REQUIRED_NBYTES (UNALIGNED_ACCESS_IS_FAST ? 4 : 3)
  60
  61 #endif /* _WIMLIB_LZ_HASH3_H */