X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fhash.h;h=5a9e2894131f552932bd455aee39e14634fa9829;hb=003ce655b7116d18c86a74c50391e54990346931;hp=39894d9af1b348d922d36ed167c6d5e848863640;hpb=064af42167bf4fc9aaea2702d80ce08074b889c0;p=sliver-openvswitch.git diff --git a/lib/hash.h b/lib/hash.h index 39894d9af..5a9e28941 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -1,71 +1,137 @@ /* - * Copyright (c) 2008, 2009 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc. * - * Permission to use, copy, modify, and/or distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. */ #ifndef HASH_H #define HASH_H 1 +#include #include #include #include +#include "util.h" + +#ifdef __cplusplus +extern "C" { +#endif + +static inline uint32_t +hash_rot(uint32_t x, int k) +{ + return (x << k) | (x >> (32 - k)); +} -/* This is the public domain lookup3 hash by Bob Jenkins from - * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ - -#define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) - -#define HASH_MIX(a, b, c) \ - do { \ - a -= c; a ^= HASH_ROT(c, 4); c += b; \ - b -= a; b ^= HASH_ROT(a, 6); a += c; \ - c -= b; c ^= HASH_ROT(b, 8); b += a; \ - a -= c; a ^= HASH_ROT(c, 16); c += b; \ - b -= a; b ^= HASH_ROT(a, 19); a += c; \ - c -= b; c ^= HASH_ROT(b, 4); b += a; \ - } while (0) - -#define HASH_FINAL(a, b, c) \ - do { \ - c ^= b; c -= HASH_ROT(b, 14); \ - a ^= c; a -= HASH_ROT(c, 11); \ - b ^= a; b -= HASH_ROT(a, 25); \ - c ^= b; c -= HASH_ROT(b, 16); \ - a ^= c; a -= HASH_ROT(c, 4); \ - b ^= a; b -= HASH_ROT(a, 14); \ - c ^= b; c -= HASH_ROT(b, 24); \ - } while (0) - -uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis); +uint32_t hash_words(const uint32_t data[], size_t n_words, uint32_t basis); uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); +static inline uint32_t hash_int(uint32_t x, uint32_t basis); +static inline uint32_t hash_2words(uint32_t, uint32_t); +static inline uint32_t hash_uint64(uint64_t); +static inline uint32_t hash_uint64_basis(uint64_t x, uint32_t basis); +uint32_t hash_3words(uint32_t, uint32_t, uint32_t); + +static inline uint32_t hash_boolean(bool x, uint32_t basis); +uint32_t hash_double(double, uint32_t basis); + +static inline uint32_t hash_pointer(const void *, uint32_t basis); +static inline uint32_t hash_string(const char *, uint32_t basis); + +/* Murmurhash by Austin Appleby, + * from http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp. + * + * The upstream license there says: + * + * // MurmurHash3 was written by Austin Appleby, and is placed in the public + * // domain. The author hereby disclaims copyright to this source code. + * + * See hash_words() for sample usage. */ + +static inline uint32_t mhash_add__(uint32_t hash, uint32_t data) +{ + data *= 0xcc9e2d51; + data = hash_rot(data, 15); + data *= 0x1b873593; + return hash ^ data; +} + +static inline uint32_t mhash_add(uint32_t hash, uint32_t data) +{ + hash = mhash_add__(hash, data); + hash = hash_rot(hash, 13); + return hash * 5 + 0xe6546b64; +} + +static inline uint32_t mhash_finish(uint32_t hash, size_t n_bytes) +{ + hash ^= n_bytes; + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + return hash; +} + static inline uint32_t hash_string(const char *s, uint32_t basis) { return hash_bytes(s, strlen(s), basis); } -/* This is Bob Jenkins' integer hash from - * http://burtleburtle.net/bob/hash/integer.html, modified for style. */ static inline uint32_t hash_int(uint32_t x, uint32_t basis) { - x -= x << 6; - x ^= x >> 17; - x -= x << 9; - x ^= x << 4; - x -= x << 3; - x ^= x << 10; - x ^= x >> 15; - return x + basis; + return hash_2words(x, basis); +} + +/* An attempt at a useful 1-bit hash function. Has not been analyzed for + * quality. */ +static inline uint32_t hash_boolean(bool x, uint32_t basis) +{ + const uint32_t P0 = 0xc2b73583; /* This is hash_int(1, 0). */ + const uint32_t P1 = 0xe90f1258; /* This is hash_int(2, 0). */ + return (x ? P0 : P1) ^ hash_rot(basis, 1); +} + +static inline uint32_t hash_pointer(const void *p, uint32_t basis) +{ + /* Often pointers are hashed simply by casting to integer type, but that + * has pitfalls since the lower bits of a pointer are often all 0 for + * alignment reasons. It's hard to guess where the entropy really is, so + * we give up here and just use a high-quality hash function. + * + * The double cast suppresses a warning on 64-bit systems about casting to + * an integer to different size. That's OK in this case, since most of the + * entropy in the pointer is almost certainly in the lower 32 bits. */ + return hash_int((uint32_t) (uintptr_t) p, basis); +} + +static inline uint32_t hash_2words(uint32_t x, uint32_t y) +{ + return mhash_finish(mhash_add(mhash_add(x, 0), y), 8); +} + +static inline uint32_t hash_uint64(const uint64_t x) +{ + return hash_2words((uint32_t)(x >> 32), (uint32_t)x); +} + +static inline uint32_t hash_uint64_basis(const uint64_t x, + const uint32_t basis) +{ + return hash_3words((uint32_t)(x >> 32), (uint32_t)x, basis); +} +#ifdef __cplusplus } +#endif #endif /* hash.h */