/*
- * lz_hash.h
+ * lz_hash.h - hashing for Lempel-Ziv matchfinding
*
- * Hashing for Lempel-Ziv matchfinding.
+ * The following copying information applies to this specific source code file:
*
- * Author: Eric Biggers
- * Year: 2014, 2015
+ * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
*
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * To the extent possible under law, the author(s) have dedicated all copyright
+ * and related and neighboring rights to this software to the public domain
+ * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
+ * Dedication (the "CC0").
+ *
+ * This software is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
+ *
+ * You should have received a copy of the CC0 along with this software; if not
+ * see <http://creativecommons.org/publicdomain/zero/1.0/>.
*/
-#ifndef _WIMLIB_LZ_HASH_H
-#define _WIMLIB_LZ_HASH_H
-
-#include "wimlib/unaligned.h"
-
-/* Constant for the multiplicative hash function. */
-#define LZ_HASH_MULTIPLIER 0x1E35A7BD
-
-static inline u32
-loaded_u32_to_u24(u32 v)
-{
- if (CPU_IS_LITTLE_ENDIAN)
- return v & 0xFFFFFF;
- else
- return v >> 8;
-}
-
-static inline u32
-load_u24_unaligned(const u8 *p)
-{
- if (UNALIGNED_ACCESS_IS_FAST)
- return loaded_u32_to_u24(load_u32_unaligned(p));
- else
- return ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
-}
+#ifndef _LZ_HASH_H
+#define _LZ_HASH_H
-static inline u32
-lz_hash(u32 str, unsigned num_bits)
-{
- return (u32)(str * LZ_HASH_MULTIPLIER) >> (32 - num_bits);
-}
+#include "wimlib/types.h"
/*
- * Hash the next 3-byte sequence in the window, producing a hash of length
- * 'num_bits' bits. At least LZ_HASH_REQUIRED_NBYTES must be available at 'p';
- * this might be 4 bytes rather than 3 because an unaligned load is faster on
- * some architectures.
+ * The hash function: given a sequence prefix held in the low-order bits of a
+ * 32-bit value, multiply by a carefully-chosen large constant. Discard any
+ * bits of the product that don't fit in a 32-bit value, but take the
+ * next-highest @num_bits bits of the product as the hash value, as those have
+ * the most randomness.
*/
static inline u32
-lz_hash_3_bytes(const u8 *p, unsigned num_bits)
+lz_hash(u32 seq, unsigned num_bits)
{
- return lz_hash(load_u24_unaligned(p), num_bits);
+ return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
}
-/* Number of bytes the hash function actually requires be available, due to the
- * possibility of an unaligned load. */
-#define LZ_HASH_REQUIRED_NBYTES (UNALIGNED_ACCESS_IS_FAST ? 4 : 3)
-
-#endif /* _WIMLIB_LZ_HASH_H */
+#endif /* _LZ_HASH_H */
git://wimlib.net / wimlib / blobdiff