Blender  V3.3
murmurhash.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Copyright 2018-2022 Blender Foundation */
3 
4 /* This is taken from alShaders/Cryptomatte/MurmurHash3.h:
5  *
6  * MurmurHash3 was written by Austin Appleby, and is placed in the public
7  * domain. The author hereby disclaims copyright to this source code.
8  */
9 
10 #include <stdlib.h>
11 #include <string.h>
12 
13 #include "util/math.h"
14 #include "util/murmurhash.h"
15 
16 #if defined(_MSC_VER)
17 # define ROTL32(x, y) _rotl(x, y)
18 # define ROTL64(x, y) _rotl64(x, y)
19 # define BIG_CONSTANT(x) (x)
20 #else
22 {
23  return (x << r) | (x >> (32 - r));
24 }
25 # define ROTL32(x, y) rotl32(x, y)
26 # define BIG_CONSTANT(x) (x##LLU)
27 #endif
28 
30 
31 /* Block read - if your platform needs to do endian-swapping or can only
32  * handle aligned reads, do the conversion here. */
34 {
35  return p[i];
36 }
37 
38 /* Finalization mix - force all bits of a hash block to avalanche */
40 {
41  h ^= h >> 16;
42  h *= 0x85ebca6b;
43  h ^= h >> 13;
44  h *= 0xc2b2ae35;
45  h ^= h >> 16;
46  return h;
47 }
48 
49 uint32_t util_murmur_hash3(const void *key, int len, uint32_t seed)
50 {
51  const uint8_t *data = (const uint8_t *)key;
52  const int nblocks = len / 4;
53 
54  uint32_t h1 = seed;
55 
56  const uint32_t c1 = 0xcc9e2d51;
57  const uint32_t c2 = 0x1b873593;
58 
59  const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
60 
61  for (int i = -nblocks; i; i++) {
62  uint32_t k1 = mm_hash_getblock32(blocks, i);
63 
64  k1 *= c1;
65  k1 = ROTL32(k1, 15);
66  k1 *= c2;
67 
68  h1 ^= k1;
69  h1 = ROTL32(h1, 13);
70  h1 = h1 * 5 + 0xe6546b64;
71  }
72 
73  const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
74 
75  uint32_t k1 = 0;
76 
77  switch (len & 3) {
78  case 3:
79  k1 ^= tail[2] << 16;
81  case 2:
82  k1 ^= tail[1] << 8;
84  case 1:
85  k1 ^= tail[0];
86  k1 *= c1;
87  k1 = ROTL32(k1, 15);
88  k1 *= c2;
89  h1 ^= k1;
90  }
91 
92  h1 ^= len;
93  h1 = mm_hash_fmix32(h1);
94  return h1;
95 }
96 
97 /* This is taken from the cryptomatte specification 1.0 */
99 {
100  uint32_t mantissa = hash & ((1 << 23) - 1);
101  uint32_t exponent = (hash >> 23) & ((1 << 8) - 1);
102  exponent = max(exponent, (uint32_t)1);
103  exponent = min(exponent, (uint32_t)254);
104  exponent = exponent << 23;
105  uint32_t sign = (hash >> 31);
106  sign = sign << 31;
107  uint32_t float_bits = sign | exponent | mantissa;
108  float f;
109  memcpy(&f, &float_bits, sizeof(uint32_t));
110  return f;
111 }
112 
#define ATTR_FALLTHROUGH
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
static unsigned long seed
Definition: btSoftBody.h:39
#define ccl_device_inline
Definition: cuda/compat.h:34
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
int len
Definition: draw_manager.c:108
float util_hash_to_float(uint32_t hash)
Definition: murmurhash.cpp:98
uint32_t util_murmur_hash3(const void *key, int len, uint32_t seed)
Definition: murmurhash.cpp:49
ccl_device_inline uint32_t rotl32(uint32_t x, int8_t r)
Definition: murmurhash.cpp:21
CCL_NAMESPACE_BEGIN ccl_device_inline uint32_t mm_hash_getblock32(const uint32_t *p, int i)
Definition: murmurhash.cpp:33
#define ROTL32(x, y)
Definition: murmurhash.cpp:25
ccl_device_inline uint32_t mm_hash_fmix32(uint32_t h)
Definition: murmurhash.cpp:39
double sign(double arg)
Definition: utility.h:250
#define hash
Definition: noise.c:153
#define min(a, b)
Definition: sort.c:35
unsigned int uint32_t
Definition: stdint.h:80
unsigned char uint8_t
Definition: stdint.h:78
signed char int8_t
Definition: stdint.h:75
float max