lib/ecoli_murmurhash.c

   1 /*
   2  * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdint.h>
  29
  30 #include <ecoli_murmurhash.h>
  31
  32 uint32_t ec_murmurhash3(const void *key, int len, uint32_t seed)
  33 {
  34         const uint8_t *data = (const uint8_t *)key;
  35         const uint8_t *tail;
  36         const int nblocks = len / 4;
  37         uint32_t h1 = seed;
  38         uint32_t k1;
  39         const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
  40         int i;
  41
  42         for (i = -nblocks; i; i++) {
  43                 k1 = blocks[i];
  44
  45                 h1 = ec_murmurhash3_add32(h1, k1);
  46                 h1 = ec_murmurhash3_mix32(h1);
  47         }
  48
  49         tail = (const uint8_t *)(data + nblocks * 4);
  50         k1 = 0;
  51
  52         switch(len & 3) {
  53         case 3: k1 ^= tail[2] << 16;
  54         case 2: k1 ^= tail[1] << 8;
  55         case 1: k1 ^= tail[0];
  56                 h1 = ec_murmurhash3_add32(h1, k1);
  57         };
  58
  59         /* finalization */
  60         h1 ^= len;
  61         h1 = ec_murmurhash3_fmix32(h1);
  62         return h1;
  63 }