diff options
Diffstat (limited to 'intern/cycles/util/hash.h')
| -rw-r--r-- | intern/cycles/util/hash.h | 143 |
1 files changed, 139 insertions, 4 deletions
diff --git a/intern/cycles/util/hash.h b/intern/cycles/util/hash.h index 081b33025d8..4f83f331229 100644 --- a/intern/cycles/util/hash.h +++ b/intern/cycles/util/hash.h @@ -4,10 +4,28 @@ #ifndef __UTIL_HASH_H__ #define __UTIL_HASH_H__ +#include "util/math.h" #include "util/types.h" CCL_NAMESPACE_BEGIN +/* [0, uint_max] -> [0.0, 1.0) */ +ccl_device_forceinline float uint_to_float_excl(uint n) +{ + // Note: we divide by 4294967808 instead of 2^32 because the latter + // leads to a [0.0, 1.0] mapping instead of [0.0, 1.0) due to floating + // point rounding error. 4294967808 unfortunately leaves (precisely) + // one unused ulp between the max number this outputs and 1.0, but + // that's the best you can do with this construction. + return (float)n * (1.0f / 4294967808.0f); +} + +/* [0, uint_max] -> [0.0, 1.0] */ +ccl_device_forceinline float uint_to_float_incl(uint n) +{ + return (float)n * (1.0f / (float)0xFFFFFFFFu); +} + /* ***** Jenkins Lookup3 Hash Functions ***** */ /* Source: http://burtleburtle.net/bob/c/lookup3.c */ @@ -116,22 +134,22 @@ ccl_device_inline uint hash_uint4(uint kx, uint ky, uint kz, uint kw) ccl_device_inline float hash_uint_to_float(uint kx) { - return (float)hash_uint(kx) / (float)0xFFFFFFFFu; + return uint_to_float_incl(hash_uint(kx)); } ccl_device_inline float hash_uint2_to_float(uint kx, uint ky) { - return (float)hash_uint2(kx, ky) / (float)0xFFFFFFFFu; + return uint_to_float_incl(hash_uint2(kx, ky)); } ccl_device_inline float hash_uint3_to_float(uint kx, uint ky, uint kz) { - return (float)hash_uint3(kx, ky, kz) / (float)0xFFFFFFFFu; + return uint_to_float_incl(hash_uint3(kx, ky, kz)); } ccl_device_inline float hash_uint4_to_float(uint kx, uint ky, uint kz, uint kw) { - return (float)hash_uint4(kx, ky, kz, kw) / (float)0xFFFFFFFFu; + return uint_to_float_incl(hash_uint4(kx, ky, kz, kw)); } /* Hashing float or float[234] into a float in the range [0, 1]. */ @@ -359,6 +377,123 @@ ccl_device_inline avxi hash_avxi4(avxi kx, avxi ky, avxi kz, avxi kw) #endif +/* ***** Hash Prospector Hash Functions ***** + * + * These are based on the high-quality 32-bit hash/mixing functions from + * https://github.com/skeeto/hash-prospector + */ + +ccl_device_inline uint hash_hp_uint(uint i) +{ + // The actual mixing function from Hash Prospector. + i ^= i >> 16; + i *= 0x21f0aaad; + i ^= i >> 15; + i *= 0xd35a2d97; + i ^= i >> 15; + + // The xor is just to make input zero not map to output zero. + // The number is randomly selected and isn't special. + return i ^ 0xe6fe3beb; +} + +/* Seedable version of hash_hp_uint() above. */ +ccl_device_inline uint hash_hp_seeded_uint(uint i, uint seed) +{ + // Manipulate the seed so it doesn't interact poorly with n when they + // are both e.g. incrementing. This isn't fool-proof, but is good + // enough for practical use. + seed ^= seed << 19; + + return hash_hp_uint(i ^ seed); +} + +/* Outputs [0.0, 1.0). */ +ccl_device_inline float hash_hp_float(uint i) +{ + return uint_to_float_excl(hash_hp_uint(i)); +} + +/* Outputs [0.0, 1.0). */ +ccl_device_inline float hash_hp_seeded_float(uint i, uint seed) +{ + return uint_to_float_excl(hash_hp_seeded_uint(i, seed)); +} + +/* ***** Modified Wang Hash Functions ***** + * + * These are based on a bespoke modified version of the Wang hash, and + * can serve as a faster hash when quality isn't critical. + * + * The original Wang hash is documented here: + * https://www.burtleburtle.net/bob/hash/integer.html + */ + +ccl_device_inline uint hash_wang_seeded_uint(uint i, uint seed) +{ + i = (i ^ 61) ^ seed; + i += i << 3; + i ^= i >> 4; + i *= 0x27d4eb2d; + return i; +} + +/* Outputs [0.0, 1.0). */ +ccl_device_inline float hash_wang_seeded_float(uint i, uint seed) +{ + return uint_to_float_excl(hash_wang_seeded_uint(i, seed)); +} + +/* ***** Index Shuffling Hash Function ***** + * + * This function takes an index, the length of the thing the index points + * into, and returns a shuffled index. For example, if you pass indices + * 0 through 19 to this function with a length parameter of 20, it will + * return the indices in a shuffled order with no repeats. Indices + * larger than the length parameter will simply repeat the same shuffled + * pattern over and over. + * + * This is useful for iterating over an array in random shuffled order + * without having to shuffle the array itself. + * + * Passing different seeds results in different random shuffles. + * + * This function runs in average O(1) time. + * + * See https://andrew-helmer.github.io/permute/ for details on how this + * works. + */ +ccl_device_inline uint hash_shuffle_uint(uint i, uint length, uint seed) +{ + i = i % length; + uint mask = (1 << (32 - count_leading_zeros(length - 1))) - 1; + + do { + i ^= seed; + i *= 0xe170893d; + i ^= seed >> 16; + i ^= (i & mask) >> 4; + i ^= seed >> 8; + i *= 0x0929eb3f; + i ^= seed >> 23; + i ^= (i & mask) >> 1; + i *= 1 | seed >> 27; + i *= 0x6935fa69; + i ^= (i & mask) >> 11; + i *= 0x74dcb303; + i ^= (i & mask) >> 2; + i *= 0x9e501cc3; + i ^= (i & mask) >> 2; + i *= 0xc860a3df; + i &= mask; + i ^= i >> 5; + } while (i >= length); + + return i; +} + +/* ********** */ + #ifndef __KERNEL_GPU__ static inline uint hash_string(const char *str) { |