intern/cycles/util/util_murmurhash.cpp

   1 /*
   2  * Copyright 2018 Blender Foundation
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /* This is taken from alShaders/Cryptomatte/MurmurHash3.h:
  18  *
  19  * MurmurHash3 was written by Austin Appleby, and is placed in the public
  20  * domain. The author hereby disclaims copyright to this source code.
  21  *
  22  */
  23
  24 #include "util/util_algorithm.h"
  25 #include "util/util_murmurhash.h"
  26
  27 #if defined(_MSC_VER)
  28 #  include <stdlib.h>
  29 #  define ROTL32(x,y)   _rotl(x,y)
  30 #  define ROTL64(x,y)   _rotl64(x,y)
  31 #  define BIG_CONSTANT(x) (x)
  32 #else
  33 ccl_device_inline uint32_t rotl32(uint32_t x, int8_t r)
  34 {
  35         return (x << r) | (x >> (32 - r));
  36 }
  37 #  define       ROTL32(x,y)     rotl32(x,y)
  38 #  define BIG_CONSTANT(x) (x##LLU)
  39 #endif
  40
  41 CCL_NAMESPACE_BEGIN
  42
  43 /* Block read - if your platform needs to do endian-swapping or can only
  44  * handle aligned reads, do the conversion here. */
  45 ccl_device_inline uint32_t mm_hash_getblock32(const uint32_t *p, int i)
  46 {
  47         return p[i];
  48 }
  49
  50 /* Finalization mix - force all bits of a hash block to avalanche */
  51 ccl_device_inline uint32_t mm_hash_fmix32 ( uint32_t h )
  52 {
  53         h ^= h >> 16;
  54         h *= 0x85ebca6b;
  55         h ^= h >> 13;
  56         h *= 0xc2b2ae35;
  57         h ^= h >> 16;
  58         return h;
  59 }
  60
  61 uint32_t util_murmur_hash3(const void *key, int len, uint32_t seed)
  62 {
  63         const uint8_t * data = (const uint8_t*)key;
  64         const int nblocks = len / 4;
  65
  66         uint32_t h1 = seed;
  67
  68         const uint32_t c1 = 0xcc9e2d51;
  69         const uint32_t c2 = 0x1b873593;
  70
  71         const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
  72
  73         for(int i = -nblocks; i; i++) {
  74                 uint32_t k1 = mm_hash_getblock32(blocks,i);
  75
  76                 k1 *= c1;
  77                 k1 = ROTL32(k1,15);
  78                 k1 *= c2;
  79
  80                 h1 ^= k1;
  81                 h1 = ROTL32(h1,13);
  82                 h1 = h1 * 5 + 0xe6546b64;
  83         }
  84
  85         const uint8_t *tail = (const uint8_t*)(data + nblocks*4);
  86
  87         uint32_t k1 = 0;
  88
  89         switch(len & 3) {
  90                 case 3:
  91                         k1 ^= tail[2] << 16;
  92                         ATTR_FALLTHROUGH;
  93                 case 2:
  94                         k1 ^= tail[1] << 8;
  95                         ATTR_FALLTHROUGH;
  96                 case 1:
  97                         k1 ^= tail[0];
  98                         k1 *= c1;
  99                         k1 = ROTL32(k1,15);
 100                         k1 *= c2;
 101                         h1 ^= k1;
 102         }
 103
 104         h1 ^= len;
 105         h1 = mm_hash_fmix32(h1);
 106         return h1;
 107 }
 108
 109 /* This is taken from the cryptomatte specification 1.0 */
 110 float util_hash_to_float(uint32_t hash)
 111 {
 112         uint32_t mantissa = hash & (( 1 << 23) - 1);
 113         uint32_t exponent = (hash >> 23) & ((1 << 8) - 1);
 114         exponent = max(exponent, (uint32_t) 1);
 115         exponent = min(exponent, (uint32_t) 254);
 116         exponent = exponent << 23;
 117         uint32_t sign = (hash >> 31);
 118         sign = sign << 31;
 119         uint32_t float_bits = sign | exponent | mantissa;
 120         float f;
 121         memcpy(&f, &float_bits, sizeof(uint32_t));
 122         return f;
 123 }
 124
 125 CCL_NAMESPACE_END