Subversion Repositories Kolibri OS

// Definition of _Hash_bytes. -*- C++ -*-

// Copyright (C) 2010-2015 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

// This file defines Hash_bytes, a primitive used for defining hash

// functions. Based on public domain MurmurHashUnaligned2, by Austin

// Appleby.  http://murmurhash.googlepages.com/

// This file also defines _Fnv_hash_bytes, another primitive with

// exactly the same interface but using a different hash algorithm,

// Fowler / Noll / Vo (FNV) Hash (type FNV-1a). The Murmur hash

// function apears to be better in both speed and hash quality, and

// FNV is provided primarily for backward compatibility.

#include 

namespace

{

  inline std::size_t

  unaligned_load(const char* p)

  {

    std::size_t result;

    __builtin_memcpy(&result, p, sizeof(result));

    return result;

  }

#if __SIZEOF_SIZE_T__ == 8

  // Loads n bytes, where 1 <= n < 8.

  inline std::size_t

  load_bytes(const char* p, int n)

  {

    std::size_t result = 0;

    --n;

    do

      result = (result << 8) + static_cast(p[n]);

    while (--n >= 0);

    return result;

  }

  inline std::size_t

  shift_mix(std::size_t v)

  { return v ^ (v >> 47);}

#endif

}

namespace std

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if __SIZEOF_SIZE_T__ == 4

  // Implementation of Murmur hash for 32-bit size_t.

  size_t

  _Hash_bytes(const void* ptr, size_t len, size_t seed)

  {

    const size_t m = 0x5bd1e995;

    size_t hash = seed ^ len;

    const char* buf = static_cast(ptr);

    // Mix 4 bytes at a time into the hash.

    while(len >= 4)

      {

	size_t k = unaligned_load(buf);

	k *= m;

	k ^= k >> 24;

	k *= m;

	hash *= m;

	hash ^= k;

	buf += 4;

	len -= 4;

      }

    // Handle the last few bytes of the input array.

    switch(len)

      {

      case 3:

	hash ^= static_cast(buf[2]) << 16;

      case 2:

	hash ^= static_cast(buf[1]) << 8;

      case 1:

	hash ^= static_cast(buf[0]);

	hash *= m;

      };

    // Do a few final mixes of the hash.

    hash ^= hash >> 13;

    hash *= m;

    hash ^= hash >> 15;

    return hash;

  }

  // Implementation of FNV hash for 32-bit size_t.

  size_t

  _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)

  {

    const char* cptr = static_cast(ptr);

    for (; len; --len)

      {

	hash ^= static_cast(*cptr++);

	hash *= static_cast(16777619UL);

      }

    return hash;

  }

#elif __SIZEOF_SIZE_T__ == 8

  // Implementation of Murmur hash for 64-bit size_t.

  size_t

  _Hash_bytes(const void* ptr, size_t len, size_t seed)

  {

    static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL)

			      + (size_t) 0x5bd1e995UL;

    const char* const buf = static_cast(ptr);

    // Remove the bytes not divisible by the sizeof(size_t).  This

    // allows the main loop to process the data as 64-bit integers.

    const int len_aligned = len & ~0x7;

    const char* const end = buf + len_aligned;

    size_t hash = seed ^ (len * mul);

    for (const char* p = buf; p != end; p += 8)

      {

	const size_t data = shift_mix(unaligned_load(p) * mul) * mul;

	hash ^= data;

	hash *= mul;

      }

    if ((len & 0x7) != 0)

      {

	const size_t data = load_bytes(end, len & 0x7);

	hash ^= data;

	hash *= mul;

      }

    hash = shift_mix(hash) * mul;

    hash = shift_mix(hash);

    return hash;

  }

  // Implementation of FNV hash for 64-bit size_t.

  size_t

  _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)

  {

    const char* cptr = static_cast(ptr);

    for (; len; --len)

      {

	hash ^= static_cast(*cptr++);

	hash *= static_cast(1099511628211ULL);

      }

    return hash;

  }

#else

  // Dummy hash implementation for unusual sizeof(size_t).

  size_t

  _Hash_bytes(const void* ptr, size_t len, size_t seed)

  {

    size_t hash = seed;

    const char* cptr = reinterpret_cast(ptr);

    for (; len; --len)

      hash = (hash * 131) + *cptr++;

    return hash;

  }

  size_t

  _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed)

  { return _Hash_bytes(ptr, len, seed); }

#endif /* __SIZEOF_SIZE_T__ */

_GLIBCXX_END_NAMESPACE_VERSION

} // namespace