// Copyright 2010-2020, Google Inc.
// 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 Google Inc. nor the names of its
// 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.

#include "base/hash.h"

#include "base/port.h"

namespace mozc {
namespace {

const uint32 kFingerPrint32Seed = 0xfd12deff;
const uint32 kFingerPrintSeed0 = 0x6d6f;
const uint32 kFingerPrintSeed1 = 0x7a63;

}  // namespace

#define Mix(a, b, c) \
  {                  \
    a -= b;          \
    a -= c;          \
    a ^= (c >> 13);  \
    b -= c;          \
    b -= a;          \
    b ^= (a << 8);   \
    c -= a;          \
    c -= b;          \
    c ^= (b >> 13);  \
    a -= b;          \
    a -= c;          \
    a ^= (c >> 12);  \
    b -= c;          \
    b -= a;          \
    b ^= (a << 16);  \
    c -= a;          \
    c -= b;          \
    c ^= (b >> 5);   \
    a -= b;          \
    a -= c;          \
    a ^= (c >> 3);   \
    b -= c;          \
    b -= a;          \
    b ^= (a << 10);  \
    c -= a;          \
    c -= b;          \
    c ^= (b >> 15);  \
  }

uint32 Hash::Fingerprint32(absl::string_view str) {
  return Fingerprint32WithSeed(str, kFingerPrint32Seed);
}

uint32 Hash::Fingerprint32WithSeed(absl::string_view str, uint32 seed) {
#define U32(x) static_cast<uint32>(x)
#define ToUint32(a, b, c, d) \
  (U32(a) + (U32(b) << 8) + (U32(c) << 16) + (U32(d) << 24))

  const uint32 str_len = U32(str.size());
  uint32 a = 0x9e3779b9;
  uint32 b = a;
  uint32 c = seed;

  while (str.size() >= 12) {
    a += ToUint32(str[0], str[1], str[2], str[3]);
    b += ToUint32(str[4], str[5], str[6], str[7]);
    c += ToUint32(str[8], str[9], str[10], str[11]);
    Mix(a, b, c);
    str.remove_prefix(12);
  }

  c += U32(str_len);
  switch (str.size()) {
    case 11:
      c += U32(str[10]) << 24;
      ABSL_FALLTHROUGH_INTENDED;
    case 10:
      c += U32(str[9]) << 16;
      ABSL_FALLTHROUGH_INTENDED;
    case 9:
      c += U32(str[8]) << 8;
      ABSL_FALLTHROUGH_INTENDED;
    case 8:
      b += U32(str[7]) << 24;
      ABSL_FALLTHROUGH_INTENDED;
    case 7:
      b += U32(str[6]) << 16;
      ABSL_FALLTHROUGH_INTENDED;
    case 6:
      b += U32(str[5]) << 8;
      ABSL_FALLTHROUGH_INTENDED;
    case 5:
      b += U32(str[4]);
      ABSL_FALLTHROUGH_INTENDED;
    case 4:
      a += U32(str[3]) << 24;
      ABSL_FALLTHROUGH_INTENDED;
    case 3:
      a += U32(str[2]) << 16;
      ABSL_FALLTHROUGH_INTENDED;
    case 2:
      a += U32(str[1]) << 8;
      ABSL_FALLTHROUGH_INTENDED;
    case 1:
      a += U32(str[0]);
      break;
  }
  Mix(a, b, c);

  return c;
#undef ToUint32
#undef U32
}

uint64 Hash::Fingerprint(absl::string_view str) {
  return FingerprintWithSeed(str, kFingerPrintSeed0);
}

uint64 Hash::FingerprintWithSeed(absl::string_view str, uint32 seed) {
  const uint32 hi = Fingerprint32WithSeed(str, seed);
  const uint32 lo = Fingerprint32WithSeed(str, kFingerPrintSeed1);
  uint64 result = static_cast<uint64>(hi) << 32 | static_cast<uint64>(lo);
  if ((hi == 0) && (lo < 2)) {
    result ^= 0x130f9bef94a0a928uLL;
  }
  return result;
}

}  // namespace mozc