/*

 * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Library General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, 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

 * Library General Public License for more details.

 *

 * You should have received a copy of the GNU Library General Public License

 * along with this library; see the file COPYING.LIB.  If not, write to

 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

 * Boston, MA 02110-1301, USA.

 *

 */

#ifndef WTF_StringHashFunctions_h

#define WTF_StringHashFunctions_h

#include <wtf/unicode/Unicode.h>

namespace WTF {

// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's

static const unsigned stringHashingStartValue = 0x9e3779b9U;

// stringHash methods based on Paul Hsieh's SuperFastHash.

// http://www.azillionmonkeys.com/qed/hash.html

// char* data is interpreted as latin-encoded (zero extended to 16 bits).

inline unsigned stringHash(const UChar* data, unsigned length)

{

    unsigned hash = WTF::stringHashingStartValue;

    unsigned rem = length & 1;

    length >>= 1;

    // Main loop

    for (; length > 0; length--) {

        hash += data[0];

        unsigned tmp = (data[1] << 11) ^ hash;

        hash = (hash << 16) ^ tmp;

        data += 2;

        hash += hash >> 11;

    }

    // Handle end case

    if (rem) {

        hash += data[0];

        hash ^= hash << 11;

        hash += hash >> 17;

    }

    // Force "avalanching" of final 127 bits

    hash ^= hash << 3;

    hash += hash >> 5;

    hash ^= hash << 2;

    hash += hash >> 15;

    hash ^= hash << 10;

    hash &= 0x7fffffff;

    // this avoids ever returning a hash code of 0, since that is used to

    // signal "hash not computed yet", using a value that is likely to be

    // effectively the same as 0 when the low bits are masked

    if (hash == 0)

        hash = 0x40000000;

    return hash;

}

inline unsigned stringHash(const char* data, unsigned length)

{

    unsigned hash = WTF::stringHashingStartValue;

    unsigned rem = length & 1;

    length >>= 1;

    // Main loop

    for (; length > 0; length--) {

        hash += static_cast<unsigned char>(data[0]);

        unsigned tmp = (static_cast<unsigned char>(data[1]) << 11) ^ hash;

        hash = (hash << 16) ^ tmp;

        data += 2;

        hash += hash >> 11;

    }

    // Handle end case

    if (rem) {

        hash += static_cast<unsigned char>(data[0]);

        hash ^= hash << 11;

        hash += hash >> 17;

    }

    // Force "avalanching" of final 127 bits

    hash ^= hash << 3;

    hash += hash >> 5;

    hash ^= hash << 2;

    hash += hash >> 15;

    hash ^= hash << 10;

    hash &= 0x7fffffff;

    // this avoids ever returning a hash code of 0, since that is used to

    // signal "hash not computed yet", using a value that is likely to be

    // effectively the same as 0 when the low bits are masked

    if (hash == 0)

        hash = 0x40000000;

    return hash;

}

inline unsigned stringHash(const char* data)

{

    unsigned hash = WTF::stringHashingStartValue;

    // Main loop

    for (;;) {

        unsigned char b0 = data[0];

        if (!b0)

            break;

        unsigned char b1 = data[1];

        if (!b1) {

            hash += b0;

            hash ^= hash << 11;

            hash += hash >> 17;

            break;

        }

        hash += b0;

        unsigned tmp = (b1 << 11) ^ hash;

        hash = (hash << 16) ^ tmp;

        data += 2;

        hash += hash >> 11;

    }

    // Force "avalanching" of final 127 bits.

    hash ^= hash << 3;

    hash += hash >> 5;

    hash ^= hash << 2;

    hash += hash >> 15;

    hash ^= hash << 10;

    hash &= 0x7fffffff;

    // This avoids ever returning a hash code of 0, since that is used to

    // signal "hash not computed yet", using a value that is likely to be

    // effectively the same as 0 when the low bits are masked.

    if (hash == 0)

        hash = 0x40000000;

    return hash;

}

} // namespace WTF

#endif // WTF_StringHashFunctions_h