Home | History | Annotate | Download | only in loader 
      1 
      2 /**
      3  * `murmurhash.h' - murmurhash
      4  *
      5  * copyright (c) 2014 joseph werle <joseph.werle (at) gmail.com>
      6  * Copyright (c) 2015-2016 The Khronos Group Inc.
      7  * Copyright (c) 2015-2016 Valve Corporation
      8  * Copyright (c) 2015-2016 LunarG, Inc.
      9  *
     10  * Permission is hereby granted, free of charge, to any person obtaining a copy
     11  * of this software and/or associated documentation files (the "Materials"), to
     12  * deal in the Materials without restriction, including without limitation the
     13  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
     14  * sell copies of the Materials, and to permit persons to whom the Materials are
     15  * furnished to do so, subject to the following conditions:
     16  *
     17  * The above copyright notice(s) and this permission notice shall be included in
     18  * all copies or substantial portions of the Materials.
     19  *
     20  * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     21  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     22  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
     23  *
     24  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
     25  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
     26  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR THE
     27  * USE OR OTHER DEALINGS IN THE MATERIALS.
     28  */
     29 
     30 #include <stdlib.h>
     31 #include <stdio.h>
     32 #include <stdint.h>
     33 #include "murmurhash.h"
     34 
     35 uint32_t murmurhash(const char *key, size_t len, uint32_t seed) {
     36     uint32_t c1 = 0xcc9e2d51;
     37     uint32_t c2 = 0x1b873593;
     38     uint32_t r1 = 15;
     39     uint32_t r2 = 13;
     40     uint32_t m = 5;
     41     uint32_t n = 0xe6546b64;
     42     uint32_t h = 0;
     43     uint32_t k = 0;
     44     uint8_t *d = (uint8_t *)key;  // 32 bit extract from `key'
     45     const uint32_t *chunks = NULL;
     46     const uint8_t *tail = NULL;  // tail - last 8 bytes
     47     int i = 0;
     48     int l = (int)len / 4;  // chunk length
     49 
     50     h = seed;
     51 
     52     chunks = (const uint32_t *)(d + l * 4);  // body
     53     tail = (const uint8_t *)(d + l * 4);     // last 8 byte chunk of `key'
     54 
     55     // for each 4 byte chunk of `key'
     56     for (i = -l; i != 0; ++i) {
     57         // next 4 byte chunk of `key'
     58         k = chunks[i];
     59 
     60         // encode next 4 byte chunk of `key'
     61         k *= c1;
     62         k = (k << r1) | (k >> (32 - r1));
     63         k *= c2;
     64 
     65         // append to hash
     66         h ^= k;
     67         h = (h << r2) | (h >> (32 - r2));
     68         h = h * m + n;
     69     }
     70 
     71     k = 0;
     72 
     73     // remainder
     74     switch (len & 3) {  // `len % 4'
     75         case 3:
     76             k ^= (tail[2] << 16);
     77         case 2:
     78             k ^= (tail[1] << 8);
     79 
     80         case 1:
     81             k ^= tail[0];
     82             k *= c1;
     83             k = (k << r1) | (k >> (32 - r1));
     84             k *= c2;
     85             h ^= k;
     86     }
     87 
     88     h ^= len;
     89 
     90     h ^= (h >> 16);
     91     h *= 0x85ebca6b;
     92     h ^= (h >> 13);
     93     h *= 0xc2b2ae35;
     94     h ^= (h >> 16);
     95 
     96     return h;
     97 }
     98