murmur3_32.c revision 273268
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. 25273268Sdes * 26273268Sdes * $FreeBSD: head/sys/libkern/murmur3_32.c 273268 2014-10-18 22:15:11Z des $ 27272906Sgnn */ 28272906Sgnn 29272906Sgnn#include <sys/hash.h> 30272906Sgnn#include <sys/endian.h> 31272906Sgnn#include <sys/stdint.h> 32272906Sgnn#include <sys/types.h> 33272906Sgnn 34272906Sgnn#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n))) 35272906Sgnn 36272906Sgnn/* 37273268Sdes * Simple implementation of the Murmur3-32 hash function. 38273268Sdes * 39273268Sdes * This implementation is slow but safe. It can be made significantly 40273268Sdes * faster if the caller guarantees that the input is correctly aligned for 41273268Sdes * 32-bit reads, and slightly faster yet if the caller guarantees that the 42273268Sdes * length of the input is always a multiple of 4 bytes. 43272906Sgnn */ 44272906Sgnnuint32_t 45273268Sdesmurmur3_32_hash(const void *data, size_t len, uint32_t seed) 46272906Sgnn{ 47273268Sdes const uint8_t *bytes; 48272906Sgnn uint32_t hash, k; 49272906Sgnn size_t res; 50272906Sgnn 51273268Sdes /* initialization */ 52273268Sdes bytes = data; 53272906Sgnn res = len; 54272906Sgnn hash = seed; 55272906Sgnn 56273268Sdes /* main loop */ 57273268Sdes while (res >= 4) { 58273268Sdes /* replace with le32toh() if input is aligned */ 59273268Sdes k = le32dec(bytes); 60273268Sdes bytes += 4; 61273268Sdes res -= 4; 62272906Sgnn k *= 0xcc9e2d51; 63272906Sgnn k = rol32(k, 15); 64272906Sgnn k *= 0x1b873593; 65272906Sgnn hash ^= k; 66272906Sgnn hash = rol32(hash, 13); 67272906Sgnn hash *= 5; 68272906Sgnn hash += 0xe6546b64; 69272906Sgnn } 70272906Sgnn 71273268Sdes /* remainder */ 72273268Sdes /* remove if input length is a multiple of 4 */ 73273268Sdes if (res > 0) { 74273268Sdes k = 0; 75273268Sdes switch (res) { 76273268Sdes case 3: 77273268Sdes k |= bytes[2] << 16; 78273268Sdes case 2: 79273268Sdes k |= bytes[1] << 8; 80273268Sdes case 1: 81273268Sdes k |= bytes[0]; 82273268Sdes k *= 0xcc9e2d51; 83273268Sdes k = rol32(k, 15); 84273268Sdes k *= 0x1b873593; 85273268Sdes hash ^= k; 86273268Sdes break; 87273268Sdes } 88273268Sdes } 89273268Sdes 90272906Sgnn /* finalize */ 91272906Sgnn hash ^= (uint32_t)len; 92272906Sgnn hash ^= hash >> 16; 93272906Sgnn hash *= 0x85ebca6b; 94272906Sgnn hash ^= hash >> 13; 95272906Sgnn hash *= 0xc2b2ae35; 96272906Sgnn hash ^= hash >> 16; 97272906Sgnn return (hash); 98272906Sgnn} 99272906Sgnn 100273268Sdes/* 101273268Sdes * Simplified version of the above optimized for aligned sequences of 102273268Sdes * 32-bit words. The count argument is the number of words, not the 103273268Sdes * length in bytes. 104273268Sdes */ 105273268Sdesuint32_t 106273268Sdesmurmur3_32_hash32(const uint32_t *data, size_t count, uint32_t seed) 107273268Sdes{ 108273268Sdes uint32_t hash, k; 109273268Sdes size_t res; 110273268Sdes 111273268Sdes /* iterate */ 112273268Sdes for (res = count, hash = seed; res > 0; res--, data++) { 113273268Sdes k = le32toh(*data); 114273268Sdes k *= 0xcc9e2d51; 115273268Sdes k = rol32(k, 15); 116273268Sdes k *= 0x1b873593; 117273268Sdes hash ^= k; 118273268Sdes hash = rol32(hash, 13); 119273268Sdes hash *= 5; 120273268Sdes hash += 0xe6546b64; 121273268Sdes } 122273268Sdes 123273268Sdes /* finalize */ 124273268Sdes hash ^= (uint32_t)count; 125273268Sdes hash ^= hash >> 16; 126273268Sdes hash *= 0x85ebca6b; 127273268Sdes hash ^= hash >> 13; 128273268Sdes hash *= 0xc2b2ae35; 129273268Sdes hash ^= hash >> 16; 130273268Sdes return (hash); 131273268Sdes} 132273268Sdes 133