packages feed

cityhash (empty) → 0.0.1

raw patch · 9 files changed

+557/−0 lines, 9 filesdep +basedep +bytestringdep +largewordsetup-changed

Dependencies added: base, bytestring, largeword

Files

+ Data/Digest/CityHash.hs view
@@ -0,0 +1,65 @@+{-# LANGUAGE ForeignFunctionInterface #-}+-- |+-- Module      : Data.Digest.CityHash+-- Copyright   : (c) Austin Seipp 2011+-- License     : BSD3+-- +-- Maintainer  : as@hacks.yi.org+-- Stability   : experimental+-- Portability : portable (FFI)+-- +-- This module implements a binding to Google's CityHash family of+-- hashing functions. You can find more information here:+-- <http://code.google.com/p/cityhash/>. It implements both the 64-bit+-- and 128-bit interfaces.+-- +-- Note that CityHash is designed to work on architectures where+-- unaligned reads have a small penalty. In practice it is only used+-- at Google on little-endian Intel/AMD CPUs it seems, and has not+-- been tested on big-endian architectures.+-- +module Data.Digest.CityHash+( -- * Hashing values +  cityHash64  -- :: ByteString -> Word64+, cityHash128 -- :: ByteString -> Word128+) where+import Foreign+import Foreign.C+import Control.Monad (liftM)++import Data.LargeWord++import qualified Data.ByteString as S+import qualified Data.ByteString.Unsafe as U++-- | Hash a value into a 64bit result.+cityHash64 :: S.ByteString -> Word64+cityHash64 bs+  = unsafePerformIO . U.unsafeUseAsCStringLen bs $ \(cstr,clen) -> do+      return $ c_CityHash64 cstr clen+{-# INLINEABLE cityHash64 #-}++-- | Hash a value into a 128bit result. Per the google documentation,+-- this is probably faster for inputs which the length is greater than,+-- say, 200 bytes. It's also used inside google for code that wants to+-- have minimal collisions.+cityHash128 :: S.ByteString -> Word128+cityHash128 bs+  = unsafePerformIO . U.unsafeUseAsCStringLen bs $ \(cstr,clen) ->+      allocaBytes w64s $ \lo -> +        allocaBytes w64s $ \hi -> do+          c_CityHash128 cstr clen lo hi+          lo' <- fromIntegral `liftM` peek lo+          hi' <- fromIntegral `liftM` peek hi+          return $ (hi' `shiftL` 64) .|. lo'+  where w64s = sizeOf (undefined :: Word64)+{-# INLINEABLE cityHash128 #-}++--+-- FFI bindings+-- +foreign import ccall unsafe "hs_city.h hs_CityHash64"+  c_CityHash64 :: CString -> Int -> Word64++foreign import ccall unsafe "hs_city.h hs_CityHash128"+  c_CityHash128 :: CString -> Int -> Ptr Word64 -> Ptr Word64 -> IO ()
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Austin Seipp 2011++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Austin Seipp nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,3 @@+this is a haskell binding to google's cityhash functions.++see http://code.google.com/p/cityhash
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ cbits/city.cc view
@@ -0,0 +1,307 @@+// Copyright (c) 2011 Google, Inc.+//+// Permission is hereby granted, free of charge, to any person obtaining a copy+// of this software and associated documentation files (the "Software"), to deal+// in the Software without restriction, including without limitation the rights+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+// copies of the Software, and to permit persons to whom the Software is+// furnished to do so, subject to the following conditions:+//+// The above copyright notice and this permission notice shall be included in+// all copies or substantial portions of the Software.+//+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+// THE SOFTWARE.+//+// CityHash Version 1, by Geoff Pike and Jyrki Alakuijala+//+// This file provides CityHash64() and related functions.+//+// It's probably possible to create even faster hash functions by+// writing a program that systematically explores some of the space of+// possible hash functions, by using SIMD instructions, or by+// compromising on hash quality.++#include "city.h"++#include <algorithm>++using namespace std;++#define UNALIGNED_LOAD64(p) (*(const uint64*)(p))+#define UNALIGNED_LOAD32(p) (*(const uint32*)(p))++#if !defined(LIKELY)+#if defined(__GNUC__)+#define LIKELY(x) (__builtin_expect(!!(x), 1))+#else+#define LIKELY(x) (x)+#endif+#endif++// Some primes between 2^63 and 2^64 for various uses.+static const uint64 k0 = 0xc3a5c85c97cb3127ULL;+static const uint64 k1 = 0xb492b66fbe98f273ULL;+static const uint64 k2 = 0x9ae16a3b2f90404fULL;+static const uint64 k3 = 0xc949d7c7509e6557ULL;++// Bitwise right rotate.  Normally this will compile to a single+// instruction, especially if the shift is a manifest constant.+static uint64 Rotate(uint64 val, int shift) {+  // Avoid shifting by 64: doing so yields an undefined result.+  return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));+}++// Equivalent to Rotate(), but requires the second arg to be non-zero.+// On x86-64, and probably others, it's possible for this to compile+// to a single instruction if both args are already in registers.+static uint64 RotateByAtLeast1(uint64 val, int shift) {+  return (val >> shift) | (val << (64 - shift));+}++static uint64 ShiftMix(uint64 val) {+  return val ^ (val >> 47);+}++static uint64 HashLen16(uint64 u, uint64 v) {+  return Hash128to64(uint128(u, v));+}++static uint64 HashLen0to16(const char *s, size_t len) {+  if (len > 8) {+    uint64 a = UNALIGNED_LOAD64(s);+    uint64 b = UNALIGNED_LOAD64(s + len - 8);+    return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b;+  }+  if (len >= 4) {+    uint64 a = UNALIGNED_LOAD32(s);+    return HashLen16(len + (a << 3), UNALIGNED_LOAD32(s + len - 4));+  }+  if (len > 0) {+    uint8 a = s[0];+    uint8 b = s[len >> 1];+    uint8 c = s[len - 1];+    uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);+    uint32 z = len + (static_cast<uint32>(c) << 2);+    return ShiftMix(y * k2 ^ z * k3) * k2;+  }+  return k2;+}++// This probably works well for 16-byte strings as well, but it may be overkill+// in that case.+static uint64 HashLen17to32(const char *s, size_t len) {+  uint64 a = UNALIGNED_LOAD64(s) * k1;+  uint64 b = UNALIGNED_LOAD64(s + 8);+  uint64 c = UNALIGNED_LOAD64(s + len - 8) * k2;+  uint64 d = UNALIGNED_LOAD64(s + len - 16) * k0;+  return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,+                   a + Rotate(b ^ k3, 20) - c + len);+}++// Return a 16-byte hash for 48 bytes.  Quick and dirty.+// Callers do best to use "random-looking" values for a and b.+static pair<uint64, uint64> WeakHashLen32WithSeeds(+    uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {+  a += w;+  b = Rotate(b + a + z, 21);+  uint64 c = a;+  a += x;+  a += y;+  b += Rotate(a, 44);+  return make_pair(a + z, b + c);+}++// Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.+static pair<uint64, uint64> WeakHashLen32WithSeeds(+    const char* s, uint64 a, uint64 b) {+  return WeakHashLen32WithSeeds(UNALIGNED_LOAD64(s),+                                UNALIGNED_LOAD64(s + 8),+                                UNALIGNED_LOAD64(s + 16),+                                UNALIGNED_LOAD64(s + 24),+                                a,+                                b);+}++// Return an 8-byte hash for 33 to 64 bytes.+static uint64 HashLen33to64(const char *s, size_t len) {+  uint64 z = UNALIGNED_LOAD64(s + 24);+  uint64 a = UNALIGNED_LOAD64(s) + (len + UNALIGNED_LOAD64(s + len - 16)) * k0;+  uint64 b = Rotate(a + z, 52);+  uint64 c = Rotate(a, 37);+  a += UNALIGNED_LOAD64(s + 8);+  c += Rotate(a, 7);+  a += UNALIGNED_LOAD64(s + 16);+  uint64 vf = a + z;+  uint64 vs = b + Rotate(a, 31) + c;+  a = UNALIGNED_LOAD64(s + 16) + UNALIGNED_LOAD64(s + len - 32);+  z = UNALIGNED_LOAD64(s + len - 8);+  b = Rotate(a + z, 52);+  c = Rotate(a, 37);+  a += UNALIGNED_LOAD64(s + len - 24);+  c += Rotate(a, 7);+  a += UNALIGNED_LOAD64(s + len - 16);+  uint64 wf = a + z;+  uint64 ws = b + Rotate(a, 31) + c;+  uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);+  return ShiftMix(r * k0 + vs) * k2;+}++uint64 CityHash64(const char *s, size_t len) {+  if (len <= 32) {+    if (len <= 16) {+      return HashLen0to16(s, len);+    } else {+      return HashLen17to32(s, len);+    }+  } else if (len <= 64) {+    return HashLen33to64(s, len);+  }++  // For strings over 64 bytes we hash the end first, and then as we+  // loop we keep 56 bytes of state: v, w, x, y, and z.+  uint64 x = UNALIGNED_LOAD64(s);+  uint64 y = UNALIGNED_LOAD64(s + len - 16) ^ k1;+  uint64 z = UNALIGNED_LOAD64(s + len - 56) ^ k0;+  pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, y);+  pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, len * k1, k0);+  z += ShiftMix(v.second) * k1;+  x = Rotate(z + x, 39) * k1;+  y = Rotate(y, 33) * k1;++  // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.+  len = (len - 1) & ~static_cast<size_t>(63);+  do {+    x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;+    y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;+    x ^= w.second;+    y ^= v.first;+    z = Rotate(z ^ w.first, 33);+    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);+    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);+    std::swap(z, x);+    s += 64;+    len -= 64;+  } while (len != 0);+  return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,+                   HashLen16(v.second, w.second) + x);+}++uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) {+  return CityHash64WithSeeds(s, len, k2, seed);+}++uint64 CityHash64WithSeeds(const char *s, size_t len,+                           uint64 seed0, uint64 seed1) {+  return HashLen16(CityHash64(s, len) - seed0, seed1);+}++// A subroutine for CityHash128().  Returns a decent 128-bit hash for strings+// of any length representable in ssize_t.  Based on City and Murmur.+static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {+  uint64 a = Uint128Low64(seed);+  uint64 b = Uint128High64(seed);+  uint64 c = 0;+  uint64 d = 0;+  ssize_t l = len - 16;+  if (l <= 0) {  // len <= 16+    c = b * k1 + HashLen0to16(s, len);+    d = Rotate(a + (len >= 8 ? UNALIGNED_LOAD64(s) : c), 32);+  } else {  // len > 16+    c = HashLen16(UNALIGNED_LOAD64(s + len - 8) + k1, a);+    d = HashLen16(b + len, c + UNALIGNED_LOAD64(s + len - 16));+    a += d;+    do {+      a ^= ShiftMix(UNALIGNED_LOAD64(s) * k1) * k1;+      a *= k1;+      b ^= a;+      c ^= ShiftMix(UNALIGNED_LOAD64(s + 8) * k1) * k1;+      c *= k1;+      d ^= c;+      s += 16;+      l -= 16;+    } while (l > 0);+  }+  a = HashLen16(a, c);+  b = HashLen16(d, b);+  return uint128(a ^ b, HashLen16(b, a));+}++uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {+  if (len < 128) {+    return CityMurmur(s, len, seed);+  }++  // We expect len >= 128 to be the common case.  Keep 56 bytes of state:+  // v, w, x, y, and z.+  pair<uint64, uint64> v, w;+  uint64 x = Uint128Low64(seed);+  uint64 y = Uint128High64(seed);+  uint64 z = len * k1;+  v.first = Rotate(y ^ k1, 49) * k1 + UNALIGNED_LOAD64(s);+  v.second = Rotate(v.first, 42) * k1 + UNALIGNED_LOAD64(s + 8);+  w.first = Rotate(y + z, 35) * k1 + x;+  w.second = Rotate(x + UNALIGNED_LOAD64(s + 88), 53) * k1;++  // This is the same inner loop as CityHash64(), manually unrolled.+  do {+    x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;+    y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;+    x ^= w.second;+    y ^= v.first;+    z = Rotate(z ^ w.first, 33);+    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);+    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);+    std::swap(z, x);+    s += 64;+    x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;+    y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;+    x ^= w.second;+    y ^= v.first;+    z = Rotate(z ^ w.first, 33);+    v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);+    w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);+    std::swap(z, x);+    s += 64;+    len -= 128;+  } while (LIKELY(len >= 128));+  y += Rotate(w.first, 37) * k0 + z;+  x += Rotate(v.first + z, 49) * k0;+  // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.+  for (size_t tail_done = 0; tail_done < len; ) {+    tail_done += 32;+    y = Rotate(y - x, 42) * k0 + v.second;+    w.first += UNALIGNED_LOAD64(s + len - tail_done + 16);+    x = Rotate(x, 49) * k0 + w.first;+    w.first += v.first;+    v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second);+  }+  // At this point our 48 bytes of state should contain more than+  // enough information for a strong 128-bit hash.  We use two+  // different 48-byte-to-8-byte hashes to get a 16-byte final result.+  x = HashLen16(x, v.first);+  y = HashLen16(y, w.first);+  return uint128(HashLen16(x + v.second, w.second) + y,+                 HashLen16(x + w.second, y + v.second));+}++uint128 CityHash128(const char *s, size_t len) {+  if (len >= 16) {+    return CityHash128WithSeed(s + 16,+                               len - 16,+                               uint128(UNALIGNED_LOAD64(s) ^ k3,+                                       UNALIGNED_LOAD64(s + 8)));+  } else if (len >= 8) {+    return CityHash128WithSeed(NULL,+                               0,+                               uint128(UNALIGNED_LOAD64(s) ^ (len * k0),+                                       UNALIGNED_LOAD64(s + len - 8) ^ k1));+  } else {+    return CityHash128WithSeed(s, len, uint128(k0, k1));+  }+}
+ cbits/city.h view
@@ -0,0 +1,90 @@+// Copyright (c) 2011 Google, Inc.+//+// Permission is hereby granted, free of charge, to any person obtaining a copy+// of this software and associated documentation files (the "Software"), to deal+// in the Software without restriction, including without limitation the rights+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+// copies of the Software, and to permit persons to whom the Software is+// furnished to do so, subject to the following conditions:+//+// The above copyright notice and this permission notice shall be included in+// all copies or substantial portions of the Software.+//+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+// THE SOFTWARE.+//+// CityHash Version 1, by Geoff Pike and Jyrki Alakuijala+//+// This file provides a few functions for hashing strings. On x86-64+// hardware in 2011, CityHash64() is faster than other high-quality+// hash functions, such as Murmur.  This is largely due to higher+// instruction-level parallelism.  CityHash64() and CityHash128() also perform+// well on hash-quality tests.+//+// CityHash128() is optimized for relatively long strings and returns+// a 128-bit hash.  For strings more than about 2000 bytes it can be+// faster than CityHash64().+//+// Functions in the CityHash family are not suitable for cryptography.+//+// WARNING: This code has not been tested on big-endian platforms!+// It is known to work well on little-endian platforms that have a small penalty+// for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs.+//+// By the way, for some hash functions, given strings a and b, the hash+// of a+b is easily derived from the hashes of a and b.  This property+// doesn't hold for any hash functions in this file.++#ifndef CITY_HASH_H_+#define CITY_HASH_H_++#include <stdlib.h>  // for size_t.+#include <stdint.h>+#include <utility>++typedef uint8_t uint8;+typedef uint32_t uint32;+typedef uint64_t uint64;+typedef std::pair<uint64, uint64> uint128;++inline uint64 Uint128Low64(const uint128& x) { return x.first; }+inline uint64 Uint128High64(const uint128& x) { return x.second; }++// Hash function for a byte array.+uint64 CityHash64(const char *buf, size_t len);++// Hash function for a byte array.  For convenience, a 64-bit seed is also+// hashed into the result.+uint64 CityHash64WithSeed(const char *buf, size_t len, uint64 seed);++// Hash function for a byte array.  For convenience, two seeds are also+// hashed into the result.+uint64 CityHash64WithSeeds(const char *buf, size_t len,+                           uint64 seed0, uint64 seed1);++// Hash function for a byte array.+uint128 CityHash128(const char *s, size_t len);++// Hash function for a byte array.  For convenience, a 128-bit seed is also+// hashed into the result.+uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed);++// Hash 128 input bits down to 64 bits of output.+// This is intended to be a reasonably good hash function.+inline uint64 Hash128to64(const uint128& x) {+  // Murmur-inspired hashing.+  const uint64 kMul = 0x9ddfea08eb382d69ULL;+  uint64 a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;+  a ^= (a >> 47);+  uint64 b = (Uint128High64(x) ^ a) * kMul;+  b ^= (b >> 47);+  b *= kMul;+  return b;+}++#endif  // CITY_HASH_H_
+ cbits/hs_city.cc view
@@ -0,0 +1,12 @@+#include "city.h"+#include "hs_city.h"++uint64_t hs_CityHash64(const char* buf, size_t len) {+  return CityHash64(buf,len);+}++void hs_CityHash128(const char* buf, size_t len, uint64_t* lo, uint64_t* hi) {+  uint128 res = CityHash128(buf,len);+  *lo = Uint128Low64(res);+  *hi = Uint128High64(res);+}
+ cbits/hs_city.h view
@@ -0,0 +1,11 @@+#ifndef _HS_CITY_H_+#define _HS_CITY_H_++extern "C" {++uint64_t hs_CityHash64(const char* buf, size_t len);+void hs_CityHash128(const char* buf, size_t len, uint64_t* lo, uint64_t* hi);++}++#endif
+ cityhash.cabal view
@@ -0,0 +1,37 @@+name:                cityhash+version:             0.0.1+synopsis:            bindings to Google CityHash+description:+  This package implements a binding to the google CityHash family of hashing functions.+  See <http://code.google.com/p/cityhash/> for more information.+homepage:            http://github.com/thoughtpolice/hs-cityhash+bug-reports:         https://github.com/thoughtpolice/hs-cityhash/issues+license:             BSD3+license-file:        LICENSE+author:              Austin Seipp+maintainer:          as@hacks.yi.org+category:            Codec+build-type:          Simple+cabal-version:       >=1.10++extra-source-files:+  cbits/city.cc, cbits/city.h,+  cbits/hs_city.cc, cbits/hs_city.h,+  README.md++source-repository head+  type: git+  location: https://github.com/thoughtpolice/hs-cityhash.git++library+  exposed-modules: Data.Digest.CityHash+  build-depends:+    base    >= 3 && < 5,+    bytestring == 0.9.*,+    largeword  >= 1.0.0+  c-sources:       cbits/city.cc, cbits/hs_city.cc+  include-dirs:    cbits+  extra-libraries: stdc++++  ghc-options:      -Wall -O2 -fwarn-tabs+  default-language: Haskell98