Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2012 Nicira, Inc.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : #include <config.h>
18 : : #include "jhash.h"
19 : : #include <string.h>
20 : : #include "unaligned.h"
21 : :
22 : : /* This is the public domain lookup3 hash by Bob Jenkins from
23 : : * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */
24 : :
25 : : static inline uint32_t
26 : 267426853 : jhash_rot(uint32_t x, int k)
27 : : {
28 : 267426853 : return (x << k) | (x >> (32 - k));
29 : : }
30 : :
31 : : static inline void
32 : 3801118 : jhash_mix(uint32_t *a, uint32_t *b, uint32_t *c)
33 : : {
34 : 3801118 : *a -= *c; *a ^= jhash_rot(*c, 4); *c += *b;
35 : 3801118 : *b -= *a; *b ^= jhash_rot(*a, 6); *a += *c;
36 : 3801118 : *c -= *b; *c ^= jhash_rot(*b, 8); *b += *a;
37 : 3801118 : *a -= *c; *a ^= jhash_rot(*c, 16); *c += *b;
38 : 3801118 : *b -= *a; *b ^= jhash_rot(*a, 19); *a += *c;
39 : 3801118 : *c -= *b; *c ^= jhash_rot(*b, 4); *b += *a;
40 : 3801118 : }
41 : :
42 : : static inline void
43 : 34945735 : jhash_final(uint32_t *a, uint32_t *b, uint32_t *c)
44 : : {
45 : 34945735 : *c ^= *b; *c -= jhash_rot(*b, 14);
46 : 34945735 : *a ^= *c; *a -= jhash_rot(*c, 11);
47 : 34945735 : *b ^= *a; *b -= jhash_rot(*a, 25);
48 : 34945735 : *c ^= *b; *c -= jhash_rot(*b, 16);
49 : 34945735 : *a ^= *c; *a -= jhash_rot(*c, 4);
50 : 34945735 : *b ^= *a; *b -= jhash_rot(*a, 14);
51 : 34945735 : *c ^= *b; *c -= jhash_rot(*b, 24);
52 : 34945735 : }
53 : :
54 : : /* Returns the Jenkins hash of the 'n' 32-bit words at 'p', starting from
55 : : * 'basis'. 'p' must be properly aligned.
56 : : *
57 : : * Use hash_words() instead, unless you're computing a hash function whose
58 : : * value is exposed "on the wire" so we don't want to change it. */
59 : : uint32_t
60 : 15024 : jhash_words(const uint32_t *p, size_t n, uint32_t basis)
61 : : {
62 : : uint32_t a, b, c;
63 : :
64 : 15024 : a = b = c = 0xdeadbeef + (((uint32_t) n) << 2) + basis;
65 : :
66 [ - + ]: 15024 : while (n > 3) {
67 : 0 : a += p[0];
68 : 0 : b += p[1];
69 : 0 : c += p[2];
70 : 0 : jhash_mix(&a, &b, &c);
71 : 0 : n -= 3;
72 : 0 : p += 3;
73 : : }
74 : :
75 [ + - + - : 15024 : switch (n) {
- ]
76 : : case 3:
77 : 13968 : c += p[2];
78 : : /* fall through */
79 : : case 2:
80 : 13968 : b += p[1];
81 : : /* fall through */
82 : : case 1:
83 : 15024 : a += p[0];
84 : 15024 : jhash_final(&a, &b, &c);
85 : : /* fall through */
86 : : case 0:
87 : 15024 : break;
88 : : }
89 : 15024 : return c;
90 : : }
91 : :
92 : : /* Returns the Jenkins hash of the 'n' bytes at 'p', starting from 'basis'.
93 : : *
94 : : * Use hash_bytes() instead, unless you're computing a hash function whose
95 : : * value is exposed "on the wire" so we don't want to change it. */
96 : : uint32_t
97 : 34930711 : jhash_bytes(const void *p_, size_t n, uint32_t basis)
98 : : {
99 : 34930711 : const uint32_t *p = p_;
100 : : uint32_t a, b, c;
101 : :
102 : 34930711 : a = b = c = 0xdeadbeef + n + basis;
103 : :
104 [ + + ]: 38731829 : while (n >= 12) {
105 : 3801118 : a += get_unaligned_u32(p);
106 : 3801118 : b += get_unaligned_u32(p + 1);
107 : 3801118 : c += get_unaligned_u32(p + 2);
108 : 3801118 : jhash_mix(&a, &b, &c);
109 : 3801118 : n -= 12;
110 : 3801118 : p += 3;
111 : : }
112 : :
113 [ + - ]: 34930711 : if (n) {
114 : : uint32_t tmp[3];
115 : :
116 : 34930711 : tmp[0] = tmp[1] = tmp[2] = 0;
117 : 34930711 : memcpy(tmp, p, n);
118 : 34930711 : a += tmp[0];
119 : 34930711 : b += tmp[1];
120 : 34930711 : c += tmp[2];
121 : 34930711 : jhash_final(&a, &b, &c);
122 : : }
123 : :
124 : 34930711 : return c;
125 : : }
|
