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/types.h"
  14
  15 /* Constant for the multiplicative hash function.  */
  16 #define LZ_HASH_MULTIPLIER 0x1E35A7BD
  17
  18 /* Hash the next 3-byte sequence in the window, producing a hash of length
  19  * 'num_bits' bits.  4 bytes must be available, since 32-bit unaligned load is
  20  * faster on some architectures.  */
  21 static inline u32
  22 lz_hash(const u8 *p, unsigned int num_bits)
  23 {
  24         u32 str;
  25         u32 hash;
  26
  27 #if defined(__i386__) || defined(__x86_64__)
  28         /* Unaligned access allowed, and little endian CPU.
  29          * Callers ensure that at least 4 (not 3) bytes are remaining.  */
  30         str = *(const u32 *)p & 0xFFFFFF;
  31 #else
  32         str = ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
  33 #endif
  34
  35         hash = str * LZ_HASH_MULTIPLIER;
  36
  37         /* High bits are more random than the low bits.  */
  38         return hash >> (32 - num_bits);
  39 }
  40
  41 /* The number of bytes being hashed.  */
  42 #define LZ_HASH_NBYTES 3
  43
  44 /* Number of bytes the hash function actually requires be available, due to the
  45  * possibility of an unaligned load.  */
  46 #define LZ_HASH_REQUIRED_NBYTES 4
  47
  48 #endif /* _WIMLIB_LZ_HASH3_H */