xxHash  0.8.0
Extremely fast non-cryptographic hash function
Macros | Typedefs | Functions | Variables
XXH3 implementation

Macros

#define XXH_RESTRICT   /* disable */
 
#define XXH_likely(x)   (x)
 
#define XXH_unlikely(x)   (x)
 
#define XXH_SEC_ALIGN   XXH_ACC_ALIGN
 
#define XXH_SPLIT_IN_PLACE(in, outLo, outHi)
 
#define XXH_VSX_BE   0
 
#define XXH_PREFETCH(ptr)   (void)(ptr) /* disabled */
 
#define XXH_SECRET_DEFAULT_SIZE   192 /* minimum XXH3_SECRET_SIZE_MIN */
 
#define XXH3_MIDSIZE_MAX   240
 
#define XXH_STRIPE_LEN   64
 
#define XXH_SECRET_CONSUME_RATE   8 /* nb of secret bytes consumed at each accumulation */
 
#define XXH_ACC_NB   (XXH_STRIPE_LEN / sizeof(xxh_u64))
 
#define XXH3_accumulate_512   XXH3_accumulate_512_avx512
 
#define XXH3_scrambleAcc   XXH3_scrambleAcc_avx512
 
#define XXH3_initCustomSecret   XXH3_initCustomSecret_avx512
 
#define XXH_PREFETCH_DIST   512
 
#define XXH3_INIT_ACC
 
#define XXH3_STREAM_USE_STACK   1
 
#define XXH_MIN(x, y)   (((x) > (y)) ? (y) : (x))
 

Typedefs

typedef __vector unsigned long long xxh_u64x2
 
typedef __vector unsigned char xxh_u8x16
 
typedef __vector unsigned xxh_u32x4
 
typedef long long xxh_i64
 
typedef void(* XXH3_f_accumulate_512) (void *restrict, const void *, const void *)
 
typedef void(* XXH3_f_scrambleAcc) (void *restrict, const void *)
 
typedef void(* XXH3_f_initCustomSecret) (void *restrict, xxh_u64)
 
typedef XXH64_hash_t(* XXH3_hashLong64_f) (const void *restrict, size_t, XXH64_hash_t, const xxh_u8 *restrict, size_t)
 
typedef XXH128_hash_t(* XXH3_hashLong128_f) (const void *restrict, size_t, XXH64_hash_t, const void *restrict, size_t)
 

Functions

static xxh_u64x2 XXH_vec_loadu (const void *ptr)
 
static xxh_u64x2 XXH_vec_mulo (xxh_u32x4 a, xxh_u32x4 b)
 
static xxh_u64x2 XXH_vec_mule (xxh_u32x4 a, xxh_u32x4 b)
 
static xxh_u64 XXH_mult32to64 (xxh_u64 x, xxh_u64 y)
 Calculates a 32-bit to 64-bit long multiply. More...
 
static XXH128_hash_t XXH_mult64to128 (xxh_u64 lhs, xxh_u64 rhs)
 Calculates a 64->128-bit long multiply. More...
 
static xxh_u64 XXH3_mul128_fold64 (xxh_u64 lhs, xxh_u64 rhs)
 Calculates a 64-bit to 128-bit multiply, then XOR folds it. More...
 
static xxh_u64 XXH_xorshift64 (xxh_u64 v64, int shift)
 
static XXH64_hash_t XXH3_avalanche (xxh_u64 h64)
 
static XXH64_hash_t XXH3_rrmxmx (xxh_u64 h64, xxh_u64 len)
 
static XXH64_hash_t XXH3_len_1to3_64b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH64_hash_t XXH3_len_4to8_64b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH64_hash_t XXH3_len_9to16_64b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH64_hash_t XXH3_len_0to16_64b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static xxh_u64 XXH3_mix16B (const xxh_u8 *restrict input, const xxh_u8 *restrict secret, xxh_u64 seed64)
 
static XXH64_hash_t XXH3_len_17to128_64b (const xxh_u8 *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH64_hash_t seed)
 
static XXH64_hash_t XXH3_len_129to240_64b (const xxh_u8 *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH64_hash_t seed)
 
static void XXH_writeLE64 (void *dst, xxh_u64 v64)
 
static XXH_TARGET_AVX512 void XXH3_accumulate_512_avx512 (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static XXH_TARGET_AVX512 void XXH3_scrambleAcc_avx512 (void *restrict acc, const void *restrict secret)
 
static XXH_TARGET_AVX512 void XXH3_initCustomSecret_avx512 (void *restrict customSecret, xxh_u64 seed64)
 
static XXH_TARGET_AVX2 void XXH3_accumulate_512_avx2 (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static XXH_TARGET_AVX2 void XXH3_scrambleAcc_avx2 (void *restrict acc, const void *restrict secret)
 
static XXH_TARGET_AVX2 void XXH3_initCustomSecret_avx2 (void *restrict customSecret, xxh_u64 seed64)
 
static XXH_TARGET_SSE2 void XXH3_accumulate_512_sse2 (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static XXH_TARGET_SSE2 void XXH3_scrambleAcc_sse2 (void *restrict acc, const void *restrict secret)
 
static XXH_TARGET_SSE2 void XXH3_initCustomSecret_sse2 (void *restrict customSecret, xxh_u64 seed64)
 
static void XXH3_accumulate_512_neon (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static void XXH3_scrambleAcc_neon (void *restrict acc, const void *restrict secret)
 
static void XXH3_accumulate_512_vsx (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static void XXH3_scrambleAcc_vsx (void *restrict acc, const void *restrict secret)
 
static void XXH3_accumulate_512_scalar (void *restrict acc, const void *restrict input, const void *restrict secret)
 
static void XXH3_scrambleAcc_scalar (void *restrict acc, const void *restrict secret)
 
static void XXH3_initCustomSecret_scalar (void *restrict customSecret, xxh_u64 seed64)
 
static void XXH3_accumulate (xxh_u64 *restrict acc, const xxh_u8 *restrict input, const xxh_u8 *restrict secret, size_t nbStripes, XXH3_f_accumulate_512 f_acc512)
 
static void XXH3_hashLong_internal_loop (xxh_u64 *restrict acc, const xxh_u8 *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble)
 
static xxh_u64 XXH3_mix2Accs (const xxh_u64 *restrict acc, const xxh_u8 *restrict secret)
 
static XXH64_hash_t XXH3_mergeAccs (const xxh_u64 *restrict acc, const xxh_u8 *restrict secret, xxh_u64 start)
 
static XXH64_hash_t XXH3_hashLong_64b_internal (const void *restrict input, size_t len, const void *restrict secret, size_t secretSize, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble)
 
static XXH64_hash_t XXH3_hashLong_64b_withSecret (const void *restrict input, size_t len, XXH64_hash_t seed64, const xxh_u8 *restrict secret, size_t secretLen)
 
static XXH64_hash_t XXH3_hashLong_64b_default (const void *restrict input, size_t len, XXH64_hash_t seed64, const xxh_u8 *restrict secret, size_t secretLen)
 
static XXH64_hash_t XXH3_hashLong_64b_withSeed_internal (const void *input, size_t len, XXH64_hash_t seed, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble, XXH3_f_initCustomSecret f_initSec)
 
static XXH64_hash_t XXH3_hashLong_64b_withSeed (const void *input, size_t len, XXH64_hash_t seed, const xxh_u8 *secret, size_t secretLen)
 
static XXH64_hash_t XXH3_64bits_internal (const void *restrict input, size_t len, XXH64_hash_t seed64, const void *restrict secret, size_t secretLen, XXH3_hashLong64_f f_hashLong)
 
XXH64_hash_t XXH3_64bits_withSecretandSeed (const void *data, size_t len, const void *secret, size_t secretSize, XXH64_hash_t seed)
 
static void * XXH_alignedMalloc (size_t s, size_t align)
 
static void XXH_alignedFree (void *p)
 
static void XXH3_reset_internal (XXH3_state_t *statePtr, XXH64_hash_t seed, const void *secret, size_t secretSize)
 
static void XXH3_consumeStripes (xxh_u64 *restrict acc, size_t *restrict nbStripesSoFarPtr, size_t nbStripesPerBlock, const xxh_u8 *restrict input, size_t nbStripes, const xxh_u8 *restrict secret, size_t secretLimit, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble)
 
static XXH_errorcode XXH3_update (XXH3_state_t *restrict const state, const xxh_u8 *restrict input, size_t len, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble)
 
static void XXH3_digest_long (XXH64_hash_t *acc, const XXH3_state_t *state, const unsigned char *secret)
 
static XXH128_hash_t XXH3_len_1to3_128b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_len_4to8_128b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_len_9to16_128b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_len_0to16_128b (const xxh_u8 *input, size_t len, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH128_hash_t XXH128_mix32B (XXH128_hash_t acc, const xxh_u8 *input_1, const xxh_u8 *input_2, const xxh_u8 *secret, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_len_17to128_128b (const xxh_u8 *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_len_129to240_128b (const xxh_u8 *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH64_hash_t seed)
 
static XXH128_hash_t XXH3_hashLong_128b_internal (const void *restrict input, size_t len, const xxh_u8 *restrict secret, size_t secretSize, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble)
 
static XXH128_hash_t XXH3_hashLong_128b_default (const void *restrict input, size_t len, XXH64_hash_t seed64, const void *restrict secret, size_t secretLen)
 
static XXH128_hash_t XXH3_hashLong_128b_withSecret (const void *restrict input, size_t len, XXH64_hash_t seed64, const void *restrict secret, size_t secretLen)
 
static XXH128_hash_t XXH3_hashLong_128b_withSeed_internal (const void *restrict input, size_t len, XXH64_hash_t seed64, XXH3_f_accumulate_512 f_acc512, XXH3_f_scrambleAcc f_scramble, XXH3_f_initCustomSecret f_initSec)
 
static XXH128_hash_t XXH3_hashLong_128b_withSeed (const void *input, size_t len, XXH64_hash_t seed64, const void *restrict secret, size_t secretLen)
 
static XXH128_hash_t XXH3_128bits_internal (const void *input, size_t len, XXH64_hash_t seed64, const void *restrict secret, size_t secretLen, XXH3_hashLong128_f f_hl128)
 
static void XXH3_combine16 (void *dst, XXH128_hash_t h128)
 

Variables

static const xxh_u8 XXH3_kSecret [XXH_SECRET_DEFAULT_SIZE]
 

Detailed Description

Macro Definition Documentation

◆ XXH_SPLIT_IN_PLACE

#define XXH_SPLIT_IN_PLACE (   in,
  outLo,
  outHi 
)
Value:
do { \
(outLo) = vmovn_u64 (in); \
(outHi) = vshrn_n_u64 ((in), 32); \
} while (0)

Function-like macro: void XXH_SPLIT_IN_PLACE(uint64x2_t &in, uint32x2_t &outLo, uint32x2_t &outHi) { outLo = (uint32x2_t)(in & 0xFFFFFFFF); outHi = (uint32x2_t)(in >> 32); in = UNDEFINED; }

◆ XXH3_INIT_ACC

#define XXH3_INIT_ACC
Value:
#define XXH_PRIME32_2
Definition: xxhash.h:1890
#define XXH_PRIME32_1
Definition: xxhash.h:1889
#define XXH_PRIME32_3
Definition: xxhash.h:1891
#define XXH_PRIME64_1
Definition: xxhash.h:2418
#define XXH_PRIME64_2
Definition: xxhash.h:2419
#define XXH_PRIME64_3
Definition: xxhash.h:2420
#define XXH_PRIME64_5
Definition: xxhash.h:2422

Function Documentation

◆ XXH_vec_loadu()

static xxh_u64x2 XXH_vec_loadu ( const void *  ptr)
inlinestatic

Performs an unaligned vector load and byte swaps it on big endian.

◆ XXH_mult32to64()

static xxh_u64 XXH_mult32to64 ( xxh_u64  x,
xxh_u64  y 
)
inlinestatic

Calculates a 32-bit to 64-bit long multiply.

Implemented as a macro.

Wraps __emulu on MSVC x86 because it tends to call __allmul when it doesn't need to (but it shouldn't need to anyways, it is about 7 instructions to do a 64x64 multiply...). Since we know that this will always emit MULL, we use that instead of the normal method.

If you are compiling for platforms like Thumb-1 and don't have a better option, you may also want to write your own long multiply routine here.

Parameters
x,yNumbers to be multiplied
Returns
64-bit product of the low 32 bits of x and y.

◆ XXH_mult64to128()

static XXH128_hash_t XXH_mult64to128 ( xxh_u64  lhs,
xxh_u64  rhs 
)
static

Calculates a 64->128-bit long multiply.

Uses __uint128_t and _umul128 if available, otherwise uses a scalar version.

Parameters
lhs,rhsThe 64-bit integers to be multiplied
Returns
The 128-bit result represented in an XXH128_hash_t.

◆ XXH3_mul128_fold64()

static xxh_u64 XXH3_mul128_fold64 ( xxh_u64  lhs,
xxh_u64  rhs 
)
static

Calculates a 64-bit to 128-bit multiply, then XOR folds it.

The reason for the separate function is to prevent passing too many structs around by value. This will hopefully inline the multiply, but we don't force it.

Parameters
lhs,rhsThe 64-bit integers to multiply
Returns
The low 64 bits of the product XOR'd by the high 64 bits.
See also
XXH_mult64to128()

◆ XXH_xorshift64()

static xxh_u64 XXH_xorshift64 ( xxh_u64  v64,
int  shift 
)
inlinestatic

Seems to produce slightly better code on GCC for some reason.

Variable Documentation

◆ XXH3_kSecret

const xxh_u8 XXH3_kSecret[XXH_SECRET_DEFAULT_SIZE]
static
Initial value:
= {
0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
}

Pseudorandom secret taken directly from FARSH.