1272906Sgnn/*- 2272906Sgnn * Copyright (c) 2014 Dag-Erling Sm��rgrav 3272906Sgnn * All rights reserved. 4272906Sgnn * 5272906Sgnn * Redistribution and use in source and binary forms, with or without 6272906Sgnn * modification, are permitted provided that the following conditions 7272906Sgnn * are met: 8272906Sgnn * 1. Redistributions of source code must retain the above copyright 9272906Sgnn * notice, this list of conditions and the following disclaimer. 10272906Sgnn * 2. Redistributions in binary form must reproduce the above copyright 11272906Sgnn * notice, this list of conditions and the following disclaimer in the 12272906Sgnn * documentation and/or other materials provided with the distribution. 13272906Sgnn * 14272906Sgnn * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15272906Sgnn * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16272906Sgnn * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17272906Sgnn * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18272906Sgnn * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19272906Sgnn * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20272906Sgnn * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21272906Sgnn * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22272906Sgnn * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23272906Sgnn * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24272906Sgnn * SUCH DAMAGE. 25272906Sgnn */ 26272906Sgnn 27272906Sgnn#include <sys/hash.h> 28272906Sgnn#include <sys/endian.h> 29272906Sgnn#include <sys/stdint.h> 30272906Sgnn#include <sys/types.h> 31272906Sgnn 32272906Sgnn#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n))) 33272906Sgnn 34272906Sgnn/* 35272906Sgnn * $FreeBSD$ 36272906Sgnn * Simple implementation of the Murmur3-32 hash function optimized for 37272906Sgnn * aligned sequences of 32-bit words. If len is not a multiple of 4, it 38272906Sgnn * will be rounded down, droping trailer bytes. 39272906Sgnn */ 40272906Sgnnuint32_t 41272906Sgnnmurmur3_aligned_32(const void *data, size_t len, uint32_t seed) 42272906Sgnn{ 43272906Sgnn const uint32_t *data32; 44272906Sgnn uint32_t hash, k; 45272906Sgnn size_t res; 46272906Sgnn 47272906Sgnn /* initialize */ 48272906Sgnn len -= len % sizeof(*data32); 49272906Sgnn res = len; 50272906Sgnn data32 = data; 51272906Sgnn hash = seed; 52272906Sgnn 53272906Sgnn /* iterate */ 54272906Sgnn for (res = 0; res < len; res += sizeof(*data32), data32++) { 55272906Sgnn k = le32toh(*data32); 56272906Sgnn k *= 0xcc9e2d51; 57272906Sgnn k = rol32(k, 15); 58272906Sgnn k *= 0x1b873593; 59272906Sgnn hash ^= k; 60272906Sgnn hash = rol32(hash, 13); 61272906Sgnn hash *= 5; 62272906Sgnn hash += 0xe6546b64; 63272906Sgnn } 64272906Sgnn 65272906Sgnn /* finalize */ 66272906Sgnn hash ^= (uint32_t)len; 67272906Sgnn hash ^= hash >> 16; 68272906Sgnn hash *= 0x85ebca6b; 69272906Sgnn hash ^= hash >> 13; 70272906Sgnn hash *= 0xc2b2ae35; 71272906Sgnn hash ^= hash >> 16; 72272906Sgnn return (hash); 73272906Sgnn} 74272906Sgnn 75