← Back to branch summary

~ubuntu-branches/ubuntu/wily/openvswitch/wily

« back to all changes in this revision

Viewing changes to lib/hash.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2015-08-10 11:35:15 UTC
  • mfrom: (1.1.30)
  • Revision ID: package-import@ubuntu.com-20150810113515-575vj06oq29emxsn
Tags: 2.4.0~git20150810.97bab95-0ubuntu1
* New upstream snapshot from 2.4 branch:
  - d/*: Align any relevant packaging changes with upstream.
* d/*: wrap-and-sort.
* d/openvswitch-{common,vswitch}.install: Correct install location for
  bash completion files.
* d/tests/openflow.py: Explicitly use ovs-testcontroller as provided
  by 2.4.0 release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/hash.c
1
1
/*
2
 
 * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
 
2
 * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc.
3
3
 *
4
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
5
 * you may not use this file except in compliance with the License.
22
22
uint32_t
23
23
hash_3words(uint32_t a, uint32_t b, uint32_t c)
24
24
{
25
 
    return mhash_finish(mhash_add(mhash_add(mhash_add(a, 0), b), c), 12);
 
25
    return hash_finish(hash_add(hash_add(hash_add(a, 0), b), c), 12);
26
26
}
27
27
 
28
28
/* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */
35
35
 
36
36
    hash = basis;
37
37
    while (n >= 4) {
38
 
        hash = mhash_add(hash, get_unaligned_u32(p));
 
38
        hash = hash_add(hash, get_unaligned_u32(p));
39
39
        n -= 4;
40
40
        p += 1;
41
41
    }
44
44
        uint32_t tmp = 0;
45
45
 
46
46
        memcpy(&tmp, p, n);
47
 
        hash = mhash_add__(hash, tmp);
48
 
    }
49
 
 
50
 
    return mhash_finish(hash, orig_n);
51
 
}
52
 
 
53
 
/* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
54
 
 * 'p' must be properly aligned. */
55
 
uint32_t
56
 
hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
57
 
{
58
 
    uint32_t hash;
59
 
    size_t i;
60
 
 
61
 
    hash = basis;
62
 
    for (i = 0; i < n_words; i++) {
63
 
        hash = mhash_add(hash, p[i]);
64
 
    }
65
 
    return mhash_finish(hash, n_words * 4);
 
47
        hash = hash_add(hash, tmp);
 
48
    }
 
49
 
 
50
    return hash_finish(hash, orig_n);
66
51
}
67
52
 
68
53
uint32_t
74
59
    memcpy(value, &x, sizeof value);
75
60
    return hash_3words(value[0], value[1], basis);
76
61
}
 
62
 
 
63
uint32_t
 
64
hash_words__(const uint32_t p[], size_t n_words, uint32_t basis)
 
65
{
 
66
    return hash_words_inline(p, n_words, basis);
 
67
}
 
68
 
 
69
uint32_t
 
70
hash_words64__(const uint64_t p[], size_t n_words, uint32_t basis)
 
71
{
 
72
    return hash_words64_inline(p, n_words, basis);
 
73
}
 
74
 
 
75
#if !(defined(__x86_64__))
 
76
void
 
77
hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
 
78
{
 
79
    const uint32_t c1 = 0x239b961b;
 
80
    const uint32_t c2 = 0xab0e9789;
 
81
    const uint32_t c3 = 0x38b34ae5;
 
82
    const uint32_t c4 = 0xa1e38b93;
 
83
    const uint8_t *tail, *data = (const uint8_t *)p_;
 
84
    const uint32_t *blocks = (const uint32_t *)p_;
 
85
    const int nblocks = len / 16;
 
86
    uint32_t h1 = basis;
 
87
    uint32_t h2 = basis;
 
88
    uint32_t h3 = basis;
 
89
    uint32_t h4 = basis;
 
90
    uint32_t k1, k2, k3, k4;
 
91
 
 
92
    /* Body */
 
93
    for (int i = 0; i < nblocks; i++) {
 
94
        uint32_t k1 = get_unaligned_u32(&blocks[i * 4 + 0]);
 
95
        uint32_t k2 = get_unaligned_u32(&blocks[i * 4 + 1]);
 
96
        uint32_t k3 = get_unaligned_u32(&blocks[i * 4 + 2]);
 
97
        uint32_t k4 = get_unaligned_u32(&blocks[i * 4 + 3]);
 
98
 
 
99
        k1 *= c1;
 
100
        k1 = hash_rot(k1, 15);
 
101
        k1 *= c2;
 
102
        h1 ^= k1;
 
103
 
 
104
        h1 = hash_rot(h1, 19);
 
105
        h1 += h2;
 
106
        h1 = h1 * 5 + 0x561ccd1b;
 
107
 
 
108
        k2 *= c2;
 
109
        k2 = hash_rot(k2, 16);
 
110
        k2 *= c3;
 
111
        h2 ^= k2;
 
112
 
 
113
        h2 = hash_rot(h2, 17);
 
114
        h2 += h3;
 
115
        h2 = h2 * 5 + 0x0bcaa747;
 
116
 
 
117
        k3 *= c3;
 
118
        k3 = hash_rot(k3, 17);
 
119
        k3 *= c4;
 
120
        h3 ^= k3;
 
121
 
 
122
        h3 = hash_rot(h3, 15);
 
123
        h3 += h4;
 
124
        h3 = h3 * 5 + 0x96cd1c35;
 
125
 
 
126
        k4 *= c4;
 
127
        k4 = hash_rot(k4, 18);
 
128
        k4 *= c1;
 
129
        h4 ^= k4;
 
130
 
 
131
        h4 = hash_rot(h4, 13);
 
132
        h4 += h1;
 
133
        h4 = h4 * 5 + 0x32ac3b17;
 
134
    }
 
135
 
 
136
    /* Tail */
 
137
    k1 = k2 = k3 = k4 = 0;
 
138
    tail = data + nblocks * 16;
 
139
    switch (len & 15) {
 
140
    case 15:
 
141
        k4 ^= tail[14] << 16;
 
142
    case 14:
 
143
        k4 ^= tail[13] << 8;
 
144
    case 13:
 
145
        k4 ^= tail[12] << 0;
 
146
        k4 *= c4;
 
147
        k4 = hash_rot(k4, 18);
 
148
        k4 *= c1;
 
149
        h4 ^= k4;
 
150
 
 
151
    case 12:
 
152
        k3 ^= tail[11] << 24;
 
153
    case 11:
 
154
        k3 ^= tail[10] << 16;
 
155
    case 10:
 
156
        k3 ^= tail[9] << 8;
 
157
    case 9:
 
158
        k3 ^= tail[8] << 0;
 
159
        k3 *= c3;
 
160
        k3 = hash_rot(k3, 17);
 
161
        k3 *= c4;
 
162
        h3 ^= k3;
 
163
 
 
164
    case 8:
 
165
        k2 ^= tail[7] << 24;
 
166
    case 7:
 
167
        k2 ^= tail[6] << 16;
 
168
    case 6:
 
169
        k2 ^= tail[5] << 8;
 
170
    case 5:
 
171
        k2 ^= tail[4] << 0;
 
172
        k2 *= c2;
 
173
        k2 = hash_rot(k2, 16);
 
174
        k2 *= c3;
 
175
        h2 ^= k2;
 
176
 
 
177
    case 4:
 
178
        k1 ^= tail[3] << 24;
 
179
    case 3:
 
180
        k1 ^= tail[2] << 16;
 
181
    case 2:
 
182
        k1 ^= tail[1] << 8;
 
183
    case 1:
 
184
        k1 ^= tail[0] << 0;
 
185
        k1 *= c1;
 
186
        k1 = hash_rot(k1, 15);
 
187
        k1 *= c2;
 
188
        h1 ^= k1;
 
189
    };
 
190
 
 
191
    /* Finalization */
 
192
    h1 ^= len;
 
193
    h2 ^= len;
 
194
    h3 ^= len;
 
195
    h4 ^= len;
 
196
 
 
197
    h1 += h2;
 
198
    h1 += h3;
 
199
    h1 += h4;
 
200
    h2 += h1;
 
201
    h3 += h1;
 
202
    h4 += h1;
 
203
 
 
204
    h1 = mhash_finish(h1);
 
205
    h2 = mhash_finish(h2);
 
206
    h3 = mhash_finish(h3);
 
207
    h4 = mhash_finish(h4);
 
208
 
 
209
    h1 += h2;
 
210
    h1 += h3;
 
211
    h1 += h4;
 
212
    h2 += h1;
 
213
    h3 += h1;
 
214
    h4 += h1;
 
215
 
 
216
    out->u32[0] = h1;
 
217
    out->u32[1] = h2;
 
218
    out->u32[2] = h3;
 
219
    out->u32[3] = h4;
 
220
}
 
221
 
 
222
#else /* __x86_64__ */
 
223
 
 
224
static inline uint64_t
 
225
hash_rot64(uint64_t x, int8_t r)
 
226
{
 
227
    return (x << r) | (x >> (64 - r));
 
228
}
 
229
 
 
230
static inline uint64_t
 
231
fmix64(uint64_t k)
 
232
{
 
233
    k ^= k >> 33;
 
234
    k *= 0xff51afd7ed558ccdULL;
 
235
    k ^= k >> 33;
 
236
    k *= 0xc4ceb9fe1a85ec53ULL;
 
237
    k ^= k >> 33;
 
238
 
 
239
    return k;
 
240
}
 
241
 
 
242
void
 
243
hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
 
244
{
 
245
    const uint64_t c1 = 0x87c37b91114253d5ULL;
 
246
    const uint64_t c2 = 0x4cf5ad432745937fULL;
 
247
    const uint8_t *tail, *data = (const uint8_t *)p_;
 
248
    const uint64_t *blocks = (const uint64_t *)p_;
 
249
    const int nblocks = len / 16;
 
250
    uint64_t h1 = basis;
 
251
    uint64_t h2 = basis;
 
252
    uint64_t k1, k2;
 
253
 
 
254
    /* Body */
 
255
    for (int i = 0; i < nblocks; i++) {
 
256
        k1 = get_unaligned_u64(&blocks[i * 2 + 0]);
 
257
        k2 = get_unaligned_u64(&blocks[i * 2 + 1]);
 
258
 
 
259
        k1 *= c1;
 
260
        k1 = hash_rot64(k1, 31);
 
261
        k1 *= c2;
 
262
        h1 ^= k1;
 
263
 
 
264
        h1 = hash_rot64(h1, 27);
 
265
        h1 += h2;
 
266
        h1 = h1 * 5 + 0x52dce729;
 
267
 
 
268
        k2 *= c2;
 
269
        k2 = hash_rot64(k2, 33);
 
270
        k2 *= c1;
 
271
        h2 ^= k2;
 
272
 
 
273
        h2 = hash_rot64(h2, 31);
 
274
        h2 += h1;
 
275
        h2 = h2 * 5 + 0x38495ab5;
 
276
    }
 
277
 
 
278
    /* Tail */
 
279
    k1 = 0;
 
280
    k2 = 0;
 
281
    tail = data + nblocks * 16;
 
282
    switch (len & 15) {
 
283
    case 15:
 
284
        k2 ^= ((uint64_t) tail[14]) << 48;
 
285
    case 14:
 
286
        k2 ^= ((uint64_t) tail[13]) << 40;
 
287
    case 13:
 
288
        k2 ^= ((uint64_t) tail[12]) << 32;
 
289
    case 12:
 
290
        k2 ^= ((uint64_t) tail[11]) << 24;
 
291
    case 11:
 
292
        k2 ^= ((uint64_t) tail[10]) << 16;
 
293
    case 10:
 
294
        k2 ^= ((uint64_t) tail[9]) << 8;
 
295
    case 9:
 
296
        k2 ^= ((uint64_t) tail[8]) << 0;
 
297
        k2 *= c2;
 
298
        k2 = hash_rot64(k2, 33);
 
299
        k2 *= c1;
 
300
        h2 ^= k2;
 
301
 
 
302
    case 8:
 
303
        k1 ^= ((uint64_t) tail[7]) << 56;
 
304
    case 7:
 
305
        k1 ^= ((uint64_t) tail[6]) << 48;
 
306
    case 6:
 
307
        k1 ^= ((uint64_t) tail[5]) << 40;
 
308
    case 5:
 
309
        k1 ^= ((uint64_t) tail[4]) << 32;
 
310
    case 4:
 
311
        k1 ^= ((uint64_t) tail[3]) << 24;
 
312
    case 3:
 
313
        k1 ^= ((uint64_t) tail[2]) << 16;
 
314
    case 2:
 
315
        k1 ^= ((uint64_t) tail[1]) << 8;
 
316
    case 1:
 
317
        k1 ^= ((uint64_t) tail[0]) << 0;
 
318
        k1 *= c1;
 
319
        k1 = hash_rot64(k1, 31);
 
320
        k1 *= c2;
 
321
        h1 ^= k1;
 
322
    };
 
323
 
 
324
    /* Finalization */
 
325
    h1 ^= len;
 
326
    h2 ^= len;
 
327
    h1 += h2;
 
328
    h2 += h1;
 
329
    h1 = fmix64(h1);
 
330
    h2 = fmix64(h2);
 
331
    h1 += h2;
 
332
    h2 += h1;
 
333
 
 
334
    out->u64.lo = h1;
 
335
    out->u64.hi = h2;
 
336
}
 
337
#endif /* __x86_64__ */