sys/libkern/murmur3_32.c

   1 /*-
   2  * Copyright (c) 2014 Dag-Erling Smørgrav
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <sys/hash.h>
  28 #include <sys/endian.h>
  29 #include <sys/stdint.h>
  30 #include <sys/types.h>
  31
  32 #define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n)))
  33
  34 /*
  35  * $FreeBSD$
  36  * Simple implementation of the Murmur3-32 hash function optimized for
  37  * aligned sequences of 32-bit words.  If len is not a multiple of 4, it
  38  * will be rounded down, droping trailer bytes.
  39  */
  40 uint32_t
  41 murmur3_aligned_32(const void *data, size_t len, uint32_t seed)
  42 {
  43         const uint32_t *data32;
  44         uint32_t hash, k;
  45         size_t res;
  46
  47         /* initialize */
  48         len -= len % sizeof(*data32);
  49         res = len;
  50         data32 = data;
  51         hash = seed;
  52
  53         /* iterate */
  54         for (res = 0; res < len; res += sizeof(*data32), data32++) {
  55                 k = le32toh(*data32);
  56                 k *= 0xcc9e2d51;
  57                 k = rol32(k, 15);
  58                 k *= 0x1b873593;
  59                 hash ^= k;
  60                 hash = rol32(hash, 13);
  61                 hash *= 5;
  62                 hash += 0xe6546b64;
  63         }
  64
  65         /* finalize */
  66         hash ^= (uint32_t)len;
  67         hash ^= hash >> 16;
  68         hash *= 0x85ebca6b;
  69         hash ^= hash >> 13;
  70         hash *= 0xc2b2ae35;
  71         hash ^= hash >> 16;
  72         return (hash);
  73 }
  74