projects / mirror_ovs.git / blame
| Commit | Line | Data |
|---|---|---|
| 064af421 BP |
1 | /* |
| 2 | * Copyright (c) 2008, 2009 Nicira Networks. | |
| 3 | * | |
| 4 | * Permission to use, copy, modify, and/or distribute this software for any | |
| 5 | * purpose with or without fee is hereby granted, provided that the above | |
| 6 | * copyright notice and this permission notice appear in all copies. | |
| 7 | * | |
| 8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
| 9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
| 10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
| 11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
| 12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
| 13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
| 14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
| 15 | */ | |
| 16 | #ifndef HASH_H | |
| 17 | #define HASH_H 1 | |
| 18 | ||
| 19 | #include <stddef.h> | |
| 20 | #include <stdint.h> | |
| 21 | #include <string.h> | |
| 22 | ||
| 23 | /* This is the public domain lookup3 hash by Bob Jenkins from | |
| 24 | * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ | |
| 25 | ||
| 26 | #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) | |
| 27 | ||
| 28 | #define HASH_MIX(a, b, c) \ | |
| 29 | do { \ | |
| 30 | a -= c; a ^= HASH_ROT(c, 4); c += b; \ | |
| 31 | b -= a; b ^= HASH_ROT(a, 6); a += c; \ | |
| 32 | c -= b; c ^= HASH_ROT(b, 8); b += a; \ | |
| 33 | a -= c; a ^= HASH_ROT(c, 16); c += b; \ | |
| 34 | b -= a; b ^= HASH_ROT(a, 19); a += c; \ | |
| 35 | c -= b; c ^= HASH_ROT(b, 4); b += a; \ | |
| 36 | } while (0) | |
| 37 | ||
| 38 | #define HASH_FINAL(a, b, c) \ | |
| 39 | do { \ | |
| 40 | c ^= b; c -= HASH_ROT(b, 14); \ | |
| 41 | a ^= c; a -= HASH_ROT(c, 11); \ | |
| 42 | b ^= a; b -= HASH_ROT(a, 25); \ | |
| 43 | c ^= b; c -= HASH_ROT(b, 16); \ | |
| 44 | a ^= c; a -= HASH_ROT(c, 4); \ | |
| 45 | b ^= a; b -= HASH_ROT(a, 14); \ | |
| 46 | c ^= b; c -= HASH_ROT(b, 24); \ | |
| 47 | } while (0) | |
| 48 | ||
| 49 | uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis); | |
| 50 | uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); | |
| 51 | ||
| 52 | static inline uint32_t hash_string(const char *s, uint32_t basis) | |
| 53 | { | |
| 54 | return hash_bytes(s, strlen(s), basis); | |
| 55 | } | |
| 56 | ||
| 57 | /* This is Bob Jenkins' integer hash from | |
| 58 | * http://burtleburtle.net/bob/hash/integer.html, modified for style. */ | |
| 59 | static inline uint32_t hash_int(uint32_t x, uint32_t basis) | |
| 60 | { | |
| 61 | x -= x << 6; | |
| 62 | x ^= x >> 17; | |
| 63 | x -= x << 9; | |
| 64 | x ^= x << 4; | |
| 65 | x -= x << 3; | |
| 66 | x ^= x << 10; | |
| 67 | x ^= x >> 15; | |
| 68 | return x + basis; | |
| 69 | } | |
| 70 | ||
| 71 | #endif /* hash.h */ |