// Copyright (c) 2011 The LevelDB Authors. All rights reserved.

// Use of this source code is governed by a BSD-style license that can be

// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "util/hash.h"

#include <string.h>

#include "util/coding.h"

namespace leveldb {

uint32_t Hash(const char* data, size_t n, uint32_t seed) {

  // Similar to murmur hash

  const uint32_t m = 0xc6a4a793;

  const uint32_t r = 24;

  const char* limit = data + n;

  uint32_t h = seed ^ (n * m);

  // Pick up four bytes at a time

  while (limit - data >= 4) {

  Branch (21:10): [True: 53.2M, False: 25.3M]

    uint32_t w = DecodeFixed32(data);

    data += 4;

    h += w;

    h *= m;

    h ^= (h >> 16);

  }

  // Pick up remaining bytes

  switch (limit - data) {

  Branch (30:11): [True: 6.72M, False: 18.6M]

    case 3:

  Branch (31:5): [True: 116k, False: 25.2M]

      h += static_cast<uint8_t>(data[2]) << 16;

      [[fallthrough]];

    case 2:

  Branch (34:5): [True: 2.48M, False: 22.8M]

      h += static_cast<uint8_t>(data[1]) << 8;

      [[fallthrough]];

    case 1:

  Branch (37:5): [True: 16.0M, False: 9.32M]

      h += static_cast<uint8_t>(data[0]);

      h *= m;

      h ^= (h >> r);

      break;

  }

  return h;

}

}  // namespace leveldb