hash_fnv.h

Go to the documentation of this file.

/****************************************************************************
**  FougTools
**  Copyright Fougue (1 Mar. 2011)
**  contact@fougue.pro
**
** This software is a computer program whose purpose is to provide utility
** tools for the C++ language and the Qt toolkit.
**
** This software is governed by the CeCILL-C license under French law and
** abiding by the rules of distribution of free software.  You can  use,
** modify and/ or redistribute the software under the terms of the CeCILL-C
** license as circulated by CEA, CNRS and INRIA at the following URL
** "http://www.cecill.info".
****************************************************************************/

#pragma once

#include <cstddef>
#include <cstdint>

namespace cpp {

template<unsigned N>
struct hash_fnv_1a_traits
{ };

template<>
struct hash_fnv_1a_traits<32>
{
    typedef std::uint32_t uint_type;
    static const uint_type offsetBasis = 2166136261U;
    static const uint_type prime = 16777619U;
};

template<>
struct hash_fnv_1a_traits<64>
{
    typedef std::uint64_t uint_type;
    static const uint_type offsetBasis = 14695981039346656037ULL;
    static const uint_type prime = 1099511628211ULL;
};

template<unsigned SIZE = sizeof(std::size_t)*8> // Target arch bit size by default
struct hash_fnv_1a
{
    static_assert(SIZE == 32 || SIZE == 64, "Bit size must be 32 or 64");

private:
    typedef hash_fnv_1a_traits<SIZE> traits_t;

public:
    typedef typename traits_t::uint_type uint_type;

    template<typename BYTE>
    uint_type operator()(const BYTE* byteSeq, std::size_t len) const
    {
        auto hash = traits_t::offsetBasis;
        for (std::size_t i = 0; i < len; ++i)
            hashStep(hash, *(byteSeq + i));
        return hash;
    }

    template<typename BYTE>
    uint_type operator()(const BYTE* byteSeq) const
    {
        auto hash = traits_t::offsetBasis;
        for (; *byteSeq != 0; ++byteSeq)
            hashStep(hash, *byteSeq);
        return hash;
    }

    template<typename ITERATOR>
    uint_type operator()(ITERATOR begin, ITERATOR end) const
    {
        auto hash = traits_t::offsetBasis;
        for (; begin != end; ++begin)
            hashStep(hash, *begin);
        return hash;
    }

private:
    template<typename BYTE>
    static inline void hashStep(uint_type& hash, BYTE byte)
    {
        static_assert(sizeof(BYTE) == 1, "valid BYTE type");
        hash ^= static_cast<uint_type>(byte); // XOR on the low order byte of hash
        hash *= traits_t::prime;
    }
};

typedef hash_fnv_1a<32> hash32_fnv_1a;
typedef hash_fnv_1a<64> hash64_fnv_1a;

} // namespace cpp