← Back to branch summary

~ubuntu-branches/debian/wheezy/abyss/wheezy

« back to all changes in this revision

Viewing changes to Common/city.cc

  • Committer: Package Import Robot
  • Author(s): Shaun Jackman
  • Date: 2012-05-31 11:39:13 UTC
  • mfrom: (1.1.5)
  • Revision ID: package-import@ubuntu.com-20120531113913-39atrfritvjevhv6
Tags: 1.3.4-1
* New upstream release.
* debian/copyright: Add CityHash, which has an Expat license.
* debian/control: Bump Standards-Version to 3.9.3.1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Common/city.cc
 
1
// Copyright (c) 2011 Google, Inc.
 
2
//
 
3
// Permission is hereby granted, free of charge, to any person obtaining a copy
 
4
// of this software and associated documentation files (the "Software"), to deal
 
5
// in the Software without restriction, including without limitation the rights
 
6
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 
7
// copies of the Software, and to permit persons to whom the Software is
 
8
// furnished to do so, subject to the following conditions:
 
9
//
 
10
// The above copyright notice and this permission notice shall be included in
 
11
// all copies or substantial portions of the Software.
 
12
//
 
13
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
14
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
15
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 
16
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 
17
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 
18
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 
19
// THE SOFTWARE.
 
20
//
 
21
// CityHash, by Geoff Pike and Jyrki Alakuijala
 
22
//
 
23
// This file provides CityHash64() and related functions.
 
24
//
 
25
// It's probably possible to create even faster hash functions by
 
26
// writing a program that systematically explores some of the space of
 
27
// possible hash functions, by using SIMD instructions, or by
 
28
// compromising on hash quality.
 
29
 
 
30
#include "config.h"
 
31
#include <city.h>
 
32
 
 
33
#include <algorithm>
 
34
#include <string.h>  // for memcpy and memset
 
35
 
 
36
using namespace std;
 
37
 
 
38
static uint64 UNALIGNED_LOAD64(const char *p) {
 
39
  uint64 result;
 
40
  memcpy(&result, p, sizeof(result));
 
41
  return result;
 
42
}
 
43
 
 
44
static uint32 UNALIGNED_LOAD32(const char *p) {
 
45
  uint32 result;
 
46
  memcpy(&result, p, sizeof(result));
 
47
  return result;
 
48
}
 
49
 
 
50
#if !defined(WORDS_BIGENDIAN)
 
51
 
 
52
#define uint32_in_expected_order(x) (x)
 
53
#define uint64_in_expected_order(x) (x)
 
54
 
 
55
#else
 
56
 
 
57
#ifdef _MSC_VER
 
58
#include <stdlib.h>
 
59
#define bswap_32(x) _byteswap_ulong(x)
 
60
#define bswap_64(x) _byteswap_uint64(x)
 
61
 
 
62
#elif defined(__APPLE__)
 
63
// Mac OS X / Darwin features
 
64
#include <libkern/OSByteOrder.h>
 
65
#define bswap_32(x) OSSwapInt32(x)
 
66
#define bswap_64(x) OSSwapInt64(x)
 
67
 
 
68
#else
 
69
#include <byteswap.h>
 
70
#endif
 
71
 
 
72
#define uint32_in_expected_order(x) (bswap_32(x))
 
73
#define uint64_in_expected_order(x) (bswap_64(x))
 
74
 
 
75
#endif  // WORDS_BIGENDIAN
 
76
 
 
77
#if !defined(LIKELY)
 
78
#if HAVE_BUILTIN_EXPECT
 
79
#define LIKELY(x) (__builtin_expect(!!(x), 1))
 
80
#else
 
81
#define LIKELY(x) (x)
 
82
#endif
 
83
#endif
 
84
 
 
85
static uint64 Fetch64(const char *p) {
 
86
  return uint64_in_expected_order(UNALIGNED_LOAD64(p));
 
87
}
 
88
 
 
89
static uint32 Fetch32(const char *p) {
 
90
  return uint32_in_expected_order(UNALIGNED_LOAD32(p));
 
91
}
 
92
 
 
93
// Some primes between 2^63 and 2^64 for various uses.
 
94
static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
 
95
static const uint64 k1 = 0xb492b66fbe98f273ULL;
 
96
static const uint64 k2 = 0x9ae16a3b2f90404fULL;
 
97
static const uint64 k3 = 0xc949d7c7509e6557ULL;
 
98
 
 
99
// Bitwise right rotate.  Normally this will compile to a single
 
100
// instruction, especially if the shift is a manifest constant.
 
101
static uint64 Rotate(uint64 val, int shift) {
 
102
  // Avoid shifting by 64: doing so yields an undefined result.
 
103
  return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
 
104
}
 
105
 
 
106
// Equivalent to Rotate(), but requires the second arg to be non-zero.
 
107
// On x86-64, and probably others, it's possible for this to compile
 
108
// to a single instruction if both args are already in registers.
 
109
static uint64 RotateByAtLeast1(uint64 val, int shift) {
 
110
  return (val >> shift) | (val << (64 - shift));
 
111
}
 
112
 
 
113
static uint64 ShiftMix(uint64 val) {
 
114
  return val ^ (val >> 47);
 
115
}
 
116
 
 
117
static uint64 HashLen16(uint64 u, uint64 v) {
 
118
  return Hash128to64(uint128(u, v));
 
119
}
 
120
 
 
121
static uint64 HashLen0to16(const char *s, size_t len) {
 
122
  if (len > 8) {
 
123
    uint64 a = Fetch64(s);
 
124
    uint64 b = Fetch64(s + len - 8);
 
125
    return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b;
 
126
  }
 
127
  if (len >= 4) {
 
128
    uint64 a = Fetch32(s);
 
129
    return HashLen16(len + (a << 3), Fetch32(s + len - 4));
 
130
  }
 
131
  if (len > 0) {
 
132
    uint8 a = s[0];
 
133
    uint8 b = s[len >> 1];
 
134
    uint8 c = s[len - 1];
 
135
    uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
 
136
    uint32 z = len + (static_cast<uint32>(c) << 2);
 
137
    return ShiftMix(y * k2 ^ z * k3) * k2;
 
138
  }
 
139
  return k2;
 
140
}
 
141
 
 
142
// This probably works well for 16-byte strings as well, but it may be overkill
 
143
// in that case.
 
144
static uint64 HashLen17to32(const char *s, size_t len) {
 
145
  uint64 a = Fetch64(s) * k1;
 
146
  uint64 b = Fetch64(s + 8);
 
147
  uint64 c = Fetch64(s + len - 8) * k2;
 
148
  uint64 d = Fetch64(s + len - 16) * k0;
 
149
  return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,
 
150
                   a + Rotate(b ^ k3, 20) - c + len);
 
151
}
 
152
 
 
153
// Return a 16-byte hash for 48 bytes.  Quick and dirty.
 
154
// Callers do best to use "random-looking" values for a and b.
 
155
static pair<uint64, uint64> WeakHashLen32WithSeeds(
 
156
    uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {
 
157
  a += w;
 
158
  b = Rotate(b + a + z, 21);
 
159
  uint64 c = a;
 
160
  a += x;
 
161
  a += y;
 
162
  b += Rotate(a, 44);
 
163
  return make_pair(a + z, b + c);
 
164
}
 
165
 
 
166
// Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
 
167
static pair<uint64, uint64> WeakHashLen32WithSeeds(
 
168
    const char* s, uint64 a, uint64 b) {
 
169
  return WeakHashLen32WithSeeds(Fetch64(s),
 
170
                                Fetch64(s + 8),
 
171
                                Fetch64(s + 16),
 
172
                                Fetch64(s + 24),
 
173
                                a,
 
174
                                b);
 
175
}
 
176
 
 
177
// Return an 8-byte hash for 33 to 64 bytes.
 
178
static uint64 HashLen33to64(const char *s, size_t len) {
 
179
  uint64 z = Fetch64(s + 24);
 
180
  uint64 a = Fetch64(s) + (len + Fetch64(s + len - 16)) * k0;
 
181
  uint64 b = Rotate(a + z, 52);
 
182
  uint64 c = Rotate(a, 37);
 
183
  a += Fetch64(s + 8);
 
184
  c += Rotate(a, 7);
 
185
  a += Fetch64(s + 16);
 
186
  uint64 vf = a + z;
 
187
  uint64 vs = b + Rotate(a, 31) + c;
 
188
  a = Fetch64(s + 16) + Fetch64(s + len - 32);
 
189
  z = Fetch64(s + len - 8);
 
190
  b = Rotate(a + z, 52);
 
191
  c = Rotate(a, 37);
 
192
  a += Fetch64(s + len - 24);
 
193
  c += Rotate(a, 7);
 
194
  a += Fetch64(s + len - 16);
 
195
  uint64 wf = a + z;
 
196
  uint64 ws = b + Rotate(a, 31) + c;
 
197
  uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);
 
198
  return ShiftMix(r * k0 + vs) * k2;
 
199
}
 
200
 
 
201
uint64 CityHash64(const char *s, size_t len) {
 
202
  if (len <= 32) {
 
203
    if (len <= 16) {
 
204
      return HashLen0to16(s, len);
 
205
    } else {
 
206
      return HashLen17to32(s, len);
 
207
    }
 
208
  } else if (len <= 64) {
 
209
    return HashLen33to64(s, len);
 
210
  }
 
211
 
 
212
  // For strings over 64 bytes we hash the end first, and then as we
 
213
  // loop we keep 56 bytes of state: v, w, x, y, and z.
 
214
  uint64 x = Fetch64(s + len - 40);
 
215
  uint64 y = Fetch64(s + len - 16) + Fetch64(s + len - 56);
 
216
  uint64 z = HashLen16(Fetch64(s + len - 48) + len, Fetch64(s + len - 24));
 
217
  pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, z);
 
218
  pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, y + k1, x);
 
219
  x = x * k1 + Fetch64(s);
 
220
 
 
221
  // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
 
222
  len = (len - 1) & ~static_cast<size_t>(63);
 
223
  do {
 
224
    x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
 
225
    y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
 
226
    x ^= w.second;
 
227
    y += v.first + Fetch64(s + 40);
 
228
    z = Rotate(z + w.first, 33) * k1;
 
229
    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 
230
    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
 
231
    std::swap(z, x);
 
232
    s += 64;
 
233
    len -= 64;
 
234
  } while (len != 0);
 
235
  return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
 
236
                   HashLen16(v.second, w.second) + x);
 
237
}
 
238
 
 
239
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) {
 
240
  return CityHash64WithSeeds(s, len, k2, seed);
 
241
}
 
242
 
 
243
uint64 CityHash64WithSeeds(const char *s, size_t len,
 
244
                           uint64 seed0, uint64 seed1) {
 
245
  return HashLen16(CityHash64(s, len) - seed0, seed1);
 
246
}
 
247
 
 
248
// A subroutine for CityHash128().  Returns a decent 128-bit hash for strings
 
249
// of any length representable in signed long.  Based on City and Murmur.
 
250
static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {
 
251
  uint64 a = Uint128Low64(seed);
 
252
  uint64 b = Uint128High64(seed);
 
253
  uint64 c = 0;
 
254
  uint64 d = 0;
 
255
  signed long l = len - 16;
 
256
  if (l <= 0) {  // len <= 16
 
257
    a = ShiftMix(a * k1) * k1;
 
258
    c = b * k1 + HashLen0to16(s, len);
 
259
    d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c));
 
260
  } else {  // len > 16
 
261
    c = HashLen16(Fetch64(s + len - 8) + k1, a);
 
262
    d = HashLen16(b + len, c + Fetch64(s + len - 16));
 
263
    a += d;
 
264
    do {
 
265
      a ^= ShiftMix(Fetch64(s) * k1) * k1;
 
266
      a *= k1;
 
267
      b ^= a;
 
268
      c ^= ShiftMix(Fetch64(s + 8) * k1) * k1;
 
269
      c *= k1;
 
270
      d ^= c;
 
271
      s += 16;
 
272
      l -= 16;
 
273
    } while (l > 0);
 
274
  }
 
275
  a = HashLen16(a, c);
 
276
  b = HashLen16(d, b);
 
277
  return uint128(a ^ b, HashLen16(b, a));
 
278
}
 
279
 
 
280
uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {
 
281
  if (len < 128) {
 
282
    return CityMurmur(s, len, seed);
 
283
  }
 
284
 
 
285
  // We expect len >= 128 to be the common case.  Keep 56 bytes of state:
 
286
  // v, w, x, y, and z.
 
287
  pair<uint64, uint64> v, w;
 
288
  uint64 x = Uint128Low64(seed);
 
289
  uint64 y = Uint128High64(seed);
 
290
  uint64 z = len * k1;
 
291
  v.first = Rotate(y ^ k1, 49) * k1 + Fetch64(s);
 
292
  v.second = Rotate(v.first, 42) * k1 + Fetch64(s + 8);
 
293
  w.first = Rotate(y + z, 35) * k1 + x;
 
294
  w.second = Rotate(x + Fetch64(s + 88), 53) * k1;
 
295
 
 
296
  // This is the same inner loop as CityHash64(), manually unrolled.
 
297
  do {
 
298
    x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
 
299
    y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
 
300
    x ^= w.second;
 
301
    y += v.first + Fetch64(s + 40);
 
302
    z = Rotate(z + w.first, 33) * k1;
 
303
    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 
304
    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
 
305
    std::swap(z, x);
 
306
    s += 64;
 
307
    x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
 
308
    y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
 
309
    x ^= w.second;
 
310
    y += v.first + Fetch64(s + 40);
 
311
    z = Rotate(z + w.first, 33) * k1;
 
312
    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 
313
    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
 
314
    std::swap(z, x);
 
315
    s += 64;
 
316
    len -= 128;
 
317
  } while (LIKELY(len >= 128));
 
318
  x += Rotate(v.first + z, 49) * k0;
 
319
  z += Rotate(w.first, 37) * k0;
 
320
  // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
 
321
  for (size_t tail_done = 0; tail_done < len; ) {
 
322
    tail_done += 32;
 
323
    y = Rotate(x + y, 42) * k0 + v.second;
 
324
    w.first += Fetch64(s + len - tail_done + 16);
 
325
    x = x * k0 + w.first;
 
326
    z += w.second + Fetch64(s + len - tail_done);
 
327
    w.second += v.first;
 
328
    v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second);
 
329
  }
 
330
  // At this point our 56 bytes of state should contain more than
 
331
  // enough information for a strong 128-bit hash.  We use two
 
332
  // different 56-byte-to-8-byte hashes to get a 16-byte final result.
 
333
  x = HashLen16(x, v.first);
 
334
  y = HashLen16(y + z, w.first);
 
335
  return uint128(HashLen16(x + v.second, w.second) + y,
 
336
                 HashLen16(x + w.second, y + v.second));
 
337
}
 
338
 
 
339
uint128 CityHash128(const char *s, size_t len) {
 
340
  if (len >= 16) {
 
341
    return CityHash128WithSeed(s + 16,
 
342
                               len - 16,
 
343
                               uint128(Fetch64(s) ^ k3,
 
344
                                       Fetch64(s + 8)));
 
345
  } else if (len >= 8) {
 
346
    return CityHash128WithSeed(NULL,
 
347
                               0,
 
348
                               uint128(Fetch64(s) ^ (len * k0),
 
349
                                       Fetch64(s + len - 8) ^ k1));
 
350
  } else {
 
351
    return CityHash128WithSeed(s, len, uint128(k0, k1));
 
352
  }
 
353
}
 
354
 
 
355
#if 0 // #ifdef __SSE4_2__
 
356
#include <citycrc.h>
 
357
#include <nmmintrin.h>
 
358
 
 
359
// Requires len >= 240.
 
360
static void CityHashCrc256Long(const char *s, size_t len,
 
361
                               uint32 seed, uint64 *result) {
 
362
  uint64 a = Fetch64(s + 56) + k0;
 
363
  uint64 b = Fetch64(s + 96) + k0;
 
364
  uint64 c = result[0] = HashLen16(b, len);
 
365
  uint64 d = result[1] = Fetch64(s + 120) * k0 + len;
 
366
  uint64 e = Fetch64(s + 184) + seed;
 
367
  uint64 f = seed;
 
368
  uint64 g = 0;
 
369
  uint64 h = 0;
 
370
  uint64 i = 0;
 
371
  uint64 j = 0;
 
372
  uint64 t = c + d;
 
373
 
 
374
  // 240 bytes of input per iter.
 
375
  size_t iters = len / 240;
 
376
  len -= iters * 240;
 
377
  do {
 
378
#define CHUNK(multiplier, z)                                    \
 
379
    {                                                           \
 
380
      uint64 old_a = a;                                         \
 
381
      a = Rotate(b, 41 ^ z) * multiplier + Fetch64(s);          \
 
382
      b = Rotate(c, 27 ^ z) * multiplier + Fetch64(s + 8);      \
 
383
      c = Rotate(d, 41 ^ z) * multiplier + Fetch64(s + 16);     \
 
384
      d = Rotate(e, 33 ^ z) * multiplier + Fetch64(s + 24);     \
 
385
      e = Rotate(t, 25 ^ z) * multiplier + Fetch64(s + 32);     \
 
386
      t = old_a;                                                \
 
387
    }                                                           \
 
388
    f = _mm_crc32_u64(f, a);                                    \
 
389
    g = _mm_crc32_u64(g, b);                                    \
 
390
    h = _mm_crc32_u64(h, c);                                    \
 
391
    i = _mm_crc32_u64(i, d);                                    \
 
392
    j = _mm_crc32_u64(j, e);                                    \
 
393
    s += 40
 
394
 
 
395
    CHUNK(1, 1); CHUNK(k0, 0);
 
396
    CHUNK(1, 1); CHUNK(k0, 0);
 
397
    CHUNK(1, 1); CHUNK(k0, 0);
 
398
  } while (--iters > 0);
 
399
 
 
400
  while (len >= 40) {
 
401
    CHUNK(k0, 0);
 
402
    len -= 40;
 
403
  }
 
404
  if (len > 0) {
 
405
    s = s + len - 40;
 
406
    CHUNK(k0, 0);
 
407
  }
 
408
  j += i << 32;
 
409
  a = HashLen16(a, j);
 
410
  h += g << 32;
 
411
  b += h;
 
412
  c = HashLen16(c, f) + i;
 
413
  d = HashLen16(d, e + result[0]);
 
414
  j += e;
 
415
  i += HashLen16(h, t);
 
416
  e = HashLen16(a, d) + j;
 
417
  f = HashLen16(b, c) + a;
 
418
  g = HashLen16(j, i) + c;
 
419
  result[0] = e + f + g + h;
 
420
  a = ShiftMix((a + g) * k0) * k0 + b;
 
421
  result[1] += a + result[0];
 
422
  a = ShiftMix(a * k0) * k0 + c;
 
423
  result[2] = a + result[1];
 
424
  a = ShiftMix((a + e) * k0) * k0;
 
425
  result[3] = a + result[2];
 
426
}
 
427
 
 
428
// Requires len < 240.
 
429
static void CityHashCrc256Short(const char *s, size_t len, uint64 *result) {
 
430
  char buf[240];
 
431
  memcpy(buf, s, len);
 
432
  memset(buf + len, 0, 240 - len);
 
433
  CityHashCrc256Long(buf, 240, ~static_cast<uint32>(len), result);
 
434
}
 
435
 
 
436
void CityHashCrc256(const char *s, size_t len, uint64 *result) {
 
437
  if (LIKELY(len >= 240)) {
 
438
    CityHashCrc256Long(s, len, 0, result);
 
439
  } else {
 
440
    CityHashCrc256Short(s, len, result);
 
441
  }
 
442
}
 
443
 
 
444
uint128 CityHashCrc128WithSeed(const char *s, size_t len, uint128 seed) {
 
445
  if (len <= 900) {
 
446
    return CityHash128WithSeed(s, len, seed);
 
447
  } else {
 
448
    uint64 result[4];
 
449
    CityHashCrc256(s, len, result);
 
450
    uint64 u = Uint128High64(seed) + result[0];
 
451
    uint64 v = Uint128Low64(seed) + result[1];
 
452
    return uint128(HashLen16(u, v + result[2]),
 
453
                   HashLen16(Rotate(v, 32), u * k0 + result[3]));
 
454
  }
 
455
}
 
456
 
 
457
uint128 CityHashCrc128(const char *s, size_t len) {
 
458
  if (len <= 900) {
 
459
    return CityHash128(s, len);
 
460
  } else {
 
461
    uint64 result[4];
 
462
    CityHashCrc256(s, len, result);
 
463
    return uint128(result[2], result[3]);
 
464
  }
 
465
}
 
466
 
 
467
#endif