From a5a4fdfd44ec1b55ebab7800a931c148540a7324 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Sun, 11 Nov 2012 08:27:24 +0100 Subject: [PATCH] zipf: use 64-bit safe hash for zipf/pareto Signed-off-by: Jens Axboe --- hash.h | 7 +++++++ lib/zipf.c | 4 ++-- lib/zipf.h | 2 +- 3 files changed, 10 insertions(+), 3 deletions(-) diff --git a/hash.h b/hash.h index 93dd8318..13600f4e 100644 --- a/hash.h +++ b/hash.h @@ -28,6 +28,8 @@ #error Define GOLDEN_RATIO_PRIME for your wordsize. #endif +#define GR_PRIME_64 0x9e37fffffffc0001UL + static inline unsigned long __hash_long(unsigned long val) { unsigned long hash = val; @@ -60,6 +62,11 @@ static inline unsigned long hash_long(unsigned long val, unsigned int bits) /* High bits are more random, so use them. */ return __hash_long(val) >> (BITS_PER_LONG - bits); } + +static inline uint64_t __hash_u64(uint64_t val) +{ + return val * GR_PRIME_64; +} static inline unsigned long hash_ptr(void *ptr, unsigned int bits) { diff --git a/lib/zipf.c b/lib/zipf.c index 41e20554..9b6ce633 100644 --- a/lib/zipf.c +++ b/lib/zipf.c @@ -69,7 +69,7 @@ unsigned long long zipf_next(struct zipf_state *zs) else val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha)); - return (__hash_long(val - 1) + zs->rand_off) % zs->nranges; + return (__hash_u64(val - 1) + zs->rand_off) % zs->nranges; } void pareto_init(struct zipf_state *zs, unsigned long nranges, double h, @@ -84,5 +84,5 @@ unsigned long long pareto_next(struct zipf_state *zs) double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX; unsigned long long n = zs->nranges - 1; - return (__hash_long(n * pow(rand, zs->pareto_pow)) + zs->rand_off) % zs->nranges; + return (__hash_u64(n * pow(rand, zs->pareto_pow)) + zs->rand_off) % zs->nranges; } diff --git a/lib/zipf.h b/lib/zipf.h index dbcaffb2..f98ad818 100644 --- a/lib/zipf.h +++ b/lib/zipf.h @@ -11,7 +11,7 @@ struct zipf_state { double zetan; double pareto_pow; struct frand_state rand; - unsigned long rand_off; + uint64_t rand_off; }; void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta, unsigned int seed); -- 2.25.1