murmur3_32.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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: releng/10.2/sys/libkern/murmur3_32.c 274486 2014-11-13 21:58:42Z gnn $
   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

Cache object: e8a982b29f022d708013d3b9a28e55b2

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/libkern/murmur3_32.c

FreeBSD/Linux Kernel Cross Reference
sys/libkern/murmur3_32.c