YugabyteDB (2.13.1.0-b60, 21121d69985fbf76aa6958d8f04a9bfa936293b5)

// Copyright 2011 Google Inc. All Rights Reserved.

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except

// in compliance with the License.  You may obtain a copy of the License at

//

// http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software distributed under the License

// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express

// or implied.  See the License for the specific language governing permissions and limitations

// under the License.

//

// This is the legacy unified hash library implementation. Its components are

// being split up into smaller, dedicated libraries. What remains here are

// things still being migrated.

//

// To find the implementation of the core Bob Jenkins lookup2 hash, look in

// jenkins.cc.

#include "yb/gutil/hash/hash.h"

#include "yb/gutil/integral_types.h"

#include <glog/logging.h>

#include "yb/gutil/hash/jenkins.h"

#include "yb/gutil/hash/jenkins_lookup2.h"

#include "yb/gutil/macros.h"

// For components that ship code externally (notably the Google Search

// Appliance) we want to change the fingerprint function so that

// attackers cannot mount offline attacks to find collisions with

// google.com internal fingerprints (most importantly, for URL

// fingerprints).

#ifdef GOOGLECLIENT

#error Do not compile this into binaries that we deliver to users!

#error Instead, use

#endif

#ifdef EXTERNAL_FP

static const uint32 kFingerprintSeed0 = 0xabc;

static const uint32 kFingerprintSeed1 = 0xdef;

#else

static const uint32 kFingerprintSeed0 = 0;

static const uint32 kFingerprintSeed1 = 102072;

#endif

static inline uint32 char2unsigned(char c) {

  return static_cast<uint32>(static_cast<unsigned char>(c));

}

uint64 FingerprintReferenceImplementation(const char *s, uint32 len) {

  uint32 hi = Hash32StringWithSeed(s, len, kFingerprintSeed0);

  uint32 lo = Hash32StringWithSeed(s, len, kFingerprintSeed1);

  return CombineFingerprintHalves(hi, lo);

}

// This is a faster version of FingerprintReferenceImplementation(),

// making use of the fact that we're hashing the same string twice.

// The code is tedious to read, but it's just two interleaved copies of

// Hash32StringWithSeed().

uint64 FingerprintInterleavedImplementation(const char *s, uint32 len) {

  uint32 a, b, c = kFingerprintSeed0, d, e, f = kFingerprintSeed1;

  uint32 keylen;

  a = b = d = e = 0x9e3779b9UL;   // the golden ratio; an arbitrary value

  keylen = len;

  if (keylen >= 4 * sizeof(a)) {

    uint32 word32AtOffset0 = Google1At(s);

    do {

      a += word32AtOffset0;

      d += word32AtOffset0;

      b += Google1At(s + sizeof(a));

      e += Google1At(s + sizeof(a));

      c += Google1At(s + sizeof(a) * 2);

      f += Google1At(s + sizeof(a) * 2);

      s += 3 * sizeof(a);

      word32AtOffset0 = Google1At(s);

      mix(a, b, c);

      mix(d, e, f);

      keylen -= 3 * static_cast<uint32>(sizeof(a));

    } while (keylen >= 4 * sizeof(a));

    if (keylen >= 3 * sizeof(a)) {

      a += word32AtOffset0;

      d += word32AtOffset0;

      b += Google1At(s + sizeof(a));

      e += Google1At(s + sizeof(a));

      c += Google1At(s + sizeof(a) * 2);

      f += Google1At(s + sizeof(a) * 2);

      s += 3 * sizeof(a);

      mix(a, b, c);

      mix(d, e, f);

      keylen -= 3 * static_cast<uint32>(sizeof(a));

      DCHECK_LT(keylen, sizeof(a));

      c += len;

      f += len;

      switch ( keylen ) {           // deal with rest.  Cases fall through

        case 3 :

          a += char2unsigned(s[2]) << 16;

          d += char2unsigned(s[2]) << 16;

          FALLTHROUGH_INTENDED;

        case 2 :

          a += char2unsigned(s[1]) << 8;

          d += char2unsigned(s[1]) << 8;

          FALLTHROUGH_INTENDED;

        case 1 :

          a += char2unsigned(s[0]);

          d += char2unsigned(s[0]);

      }

    } else {

      DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a));

      c += len;

      f += len;

      switch ( keylen ) {           // deal with rest.  Cases fall through

        case 11:

          c += char2unsigned(s[10]) << 24;

          f += char2unsigned(s[10]) << 24;

          FALLTHROUGH_INTENDED;

        case 10:

          c += char2unsigned(s[9]) << 16;

          f += char2unsigned(s[9]) << 16;

          FALLTHROUGH_INTENDED;

        case 9 :

          c += char2unsigned(s[8]) << 8;

          f += char2unsigned(s[8]) << 8;

          FALLTHROUGH_INTENDED;

        case 8 :

          b += Google1At(s+4);  a += word32AtOffset0;

          e += Google1At(s+4);  d += word32AtOffset0;

          break;

        case 7 :

          b += char2unsigned(s[6]) << 16;

          e += char2unsigned(s[6]) << 16;

          FALLTHROUGH_INTENDED;

        case 6 :

          b += char2unsigned(s[5]) << 8;

          e += char2unsigned(s[5]) << 8;

          FALLTHROUGH_INTENDED;

        case 5 :

          b += char2unsigned(s[4]);

          e += char2unsigned(s[4]);

          FALLTHROUGH_INTENDED;

        case 4 :

          a += word32AtOffset0;

          d += word32AtOffset0;

      }

    }

  } else {

    if (keylen >= 3 * sizeof(a)) {

      a += Google1At(s);

      d += Google1At(s);

      b += Google1At(s + sizeof(a));

      e += Google1At(s + sizeof(a));

      c += Google1At(s + sizeof(a) * 2);

      f += Google1At(s + sizeof(a) * 2);

      s += 3 * sizeof(a);

      mix(a, b, c);

      mix(d, e, f);

      keylen -= 3 * static_cast<uint32>(sizeof(a));

    }

    c += len;

    f += len;

    switch ( keylen ) {           // deal with rest.  Cases fall through

      case 11:

        c += char2unsigned(s[10]) << 24;

        f += char2unsigned(s[10]) << 24;

        FALLTHROUGH_INTENDED;

      case 10:

        c += char2unsigned(s[9]) << 16;

        f += char2unsigned(s[9]) << 16;

        FALLTHROUGH_INTENDED;

      case 9 :

        c += char2unsigned(s[8]) << 8;

        f += char2unsigned(s[8]) << 8;

        FALLTHROUGH_INTENDED;

      case 8 :

        b += Google1At(s+4);  a += Google1At(s);

        e += Google1At(s+4);  d += Google1At(s);

        break;

      case 7 :

        b += char2unsigned(s[6]) << 16;

        e += char2unsigned(s[6]) << 16;

        FALLTHROUGH_INTENDED;

      case 6 :

        b += char2unsigned(s[5]) << 8;

        e += char2unsigned(s[5]) << 8;

        FALLTHROUGH_INTENDED;

      case 5 :

        b += char2unsigned(s[4]);

        e += char2unsigned(s[4]);

        FALLTHROUGH_INTENDED;

      case 4 :

        a += Google1At(s);

        d += Google1At(s);

        break;

      case 3 :

        a += char2unsigned(s[2]) << 16;

        d += char2unsigned(s[2]) << 16;

        FALLTHROUGH_INTENDED;

      case 2 :

        a += char2unsigned(s[1]) << 8;

        d += char2unsigned(s[1]) << 8;

        FALLTHROUGH_INTENDED;

      case 1 :

        a += char2unsigned(s[0]);

        d += char2unsigned(s[0]);

    }

  }

  mix(a, b, c);

  mix(d, e, f);

  return CombineFingerprintHalves(c, f);

}

// Extern template definitions.