be/src/gutil/hash/jenkins.cc

// Copyright 2011 Google Inc. All Rights Reserved.
//
// Contains the legacy Bob Jenkins Lookup2-based hashing routines. These need to
// always return the same results as their values have been recorded in various
// places and cannot easily be updated.
//
// Original Author: Sanjay Ghemawat
//
// This is based on Bob Jenkins newhash function
// see: http://burtleburtle.net/bob/hash/evahash.html
// According to http://burtleburtle.net/bob/c/lookup2.c,
// his implementation is public domain.
//
// The implementation here is backwards compatible with the google1
// implementation.  The google1 implementation used a 'signed char *'
// to load words from memory a byte at a time.  See gwshash.cc for an
// implementation that is compatible with Bob Jenkins' lookup2.c.

#include "gutil/hash/jenkins.h"

#include "common/logging.h"

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

static inline uint32 char2unsigned(char c) {
    return static_cast<uint32>(static_cast<unsigned char>(c));
}

static inline uint64 char2unsigned64(char c) {
    return static_cast<uint64>(static_cast<unsigned char>(c));
}

uint32 Hash32StringWithSeedReferenceImplementation(const char* s, uint32 len, uint32 c) {
    uint32 a, b;
    uint32 keylen;

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

    for (keylen = len; keylen >= 3 * sizeof(a);
         keylen -= static_cast<uint32>(3 * sizeof(a)), s += 3 * sizeof(a)) {
        a += Google1At(s);
        b += Google1At(s + sizeof(a));
        c += Google1At(s + sizeof(a) * 2);
        mix(a, b, c);
    }

    c += len;
    switch (keylen) { // deal with rest.  Cases fall through
    case 11:
        c += char2unsigned(s[10]) << 24;
    case 10:
        c += char2unsigned(s[9]) << 16;
    case 9:
        c += char2unsigned(s[8]) << 8;
        // the first byte of c is reserved for the length
    case 8:
        b += Google1At(s + 4);
        a += Google1At(s);
        break;
    case 7:
        b += char2unsigned(s[6]) << 16;
    case 6:
        b += char2unsigned(s[5]) << 8;
    case 5:
        b += char2unsigned(s[4]);
    case 4:
        a += Google1At(s);
        break;
    case 3:
        a += char2unsigned(s[2]) << 16;
    case 2:
        a += char2unsigned(s[1]) << 8;
    case 1:
        a += char2unsigned(s[0]);
        // case 0 : nothing left to add
    }
    mix(a, b, c);
    return c;
}

uint32 Hash32StringWithSeed(const char* s, uint32 len, uint32 c) {
    uint32 a, b;
    uint32 keylen;

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

    keylen = len;
    if (keylen >= 4 * sizeof(a)) {
        uint32 word32AtOffset0 = Google1At(s);
        do {
            a += word32AtOffset0;
            b += Google1At(s + sizeof(a));
            c += Google1At(s + sizeof(a) * 2);
            s += 3 * sizeof(a);
            word32AtOffset0 = Google1At(s);
            mix(a, b, c);
            keylen -= 3 * static_cast<uint32>(sizeof(a));
        } while (keylen >= 4 * sizeof(a));
        if (keylen >= 3 * sizeof(a)) {
            a += word32AtOffset0;
            b += Google1At(s + sizeof(a));
            c += Google1At(s + sizeof(a) * 2);
            s += 3 * sizeof(a);
            mix(a, b, c);
            keylen -= 3 * static_cast<uint32>(sizeof(a));
            DCHECK_LT(keylen, sizeof(a));
            c += len;
            switch (keylen) { // deal with rest.  Cases fall through
            case 3:
                a += char2unsigned(s[2]) << 16;
            case 2:
                a += char2unsigned(s[1]) << 8;
            case 1:
                a += char2unsigned(s[0]);
            }
        } else {
            DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a));
            c += len;
            switch (keylen) { // deal with rest.  Cases fall through
            case 11:
                c += char2unsigned(s[10]) << 24;
            case 10:
                c += char2unsigned(s[9]) << 16;
            case 9:
                c += char2unsigned(s[8]) << 8;
            case 8:
                b += Google1At(s + 4);
                a += word32AtOffset0;
                break;
            case 7:
                b += char2unsigned(s[6]) << 16;
            case 6:
                b += char2unsigned(s[5]) << 8;
            case 5:
                b += char2unsigned(s[4]);
            case 4:
                a += word32AtOffset0;
                break;
            }
        }
    } else {
        if (keylen >= 3 * sizeof(a)) {
            a += Google1At(s);
            b += Google1At(s + sizeof(a));
            c += Google1At(s + sizeof(a) * 2);
            s += 3 * sizeof(a);
            mix(a, b, c);
            keylen -= 3 * static_cast<uint32>(sizeof(a));
        }
        c += len;
        switch (keylen) { // deal with rest.  Cases fall through
        case 11:
            c += char2unsigned(s[10]) << 24;
        case 10:
            c += char2unsigned(s[9]) << 16;
        case 9:
            c += char2unsigned(s[8]) << 8;
        case 8:
            b += Google1At(s + 4);
            a += Google1At(s);
            break;
        case 7:
            b += char2unsigned(s[6]) << 16;
        case 6:
            b += char2unsigned(s[5]) << 8;
        case 5:
            b += char2unsigned(s[4]);
        case 4:
            a += Google1At(s);
            break;
        case 3:
            a += char2unsigned(s[2]) << 16;
        case 2:
            a += char2unsigned(s[1]) << 8;
        case 1:
            a += char2unsigned(s[0]);
        }
    }
    mix(a, b, c);
    return c;
}

uint64 Hash64StringWithSeed(const char* s, uint32 len, uint64 c) {
    uint64 a, b;
    uint32 keylen;

    a = b = GG_ULONGLONG(0xe08c1d668b756f82); // the golden ratio; an arbitrary value

    for (keylen = len; keylen >= 3 * sizeof(a);
         keylen -= 3 * static_cast<uint32>(sizeof(a)), s += 3 * sizeof(a)) {
        a += Word64At(s);
        b += Word64At(s + sizeof(a));
        c += Word64At(s + sizeof(a) * 2);
        mix(a, b, c);
    }

    c += len;
    switch (keylen) { // deal with rest.  Cases fall through
    case 23:
        c += char2unsigned64(s[22]) << 56;
    case 22:
        c += char2unsigned64(s[21]) << 48;
    case 21:
        c += char2unsigned64(s[20]) << 40;
    case 20:
        c += char2unsigned64(s[19]) << 32;
    case 19:
        c += char2unsigned64(s[18]) << 24;
    case 18:
        c += char2unsigned64(s[17]) << 16;
    case 17:
        c += char2unsigned64(s[16]) << 8;
        // the first byte of c is reserved for the length
    case 16:
        b += Word64At(s + 8);
        a += Word64At(s);
        break;
    case 15:
        b += char2unsigned64(s[14]) << 48;
    case 14:
        b += char2unsigned64(s[13]) << 40;
    case 13:
        b += char2unsigned64(s[12]) << 32;
    case 12:
        b += char2unsigned64(s[11]) << 24;
    case 11:
        b += char2unsigned64(s[10]) << 16;
    case 10:
        b += char2unsigned64(s[9]) << 8;
    case 9:
        b += char2unsigned64(s[8]);
    case 8:
        a += Word64At(s);
        break;
    case 7:
        a += char2unsigned64(s[6]) << 48;
    case 6:
        a += char2unsigned64(s[5]) << 40;
    case 5:
        a += char2unsigned64(s[4]) << 32;
    case 4:
        a += char2unsigned64(s[3]) << 24;
    case 3:
        a += char2unsigned64(s[2]) << 16;
    case 2:
        a += char2unsigned64(s[1]) << 8;
    case 1:
        a += char2unsigned64(s[0]);
        // case 0: nothing left to add
    }
    mix(a, b, c);
    return c;
}