boost/hash2/fnv1a.hpp

0001 #ifndef BOOST_HASH2_FNV1A_HPP_INCLUDED
0002 #define BOOST_HASH2_FNV1A_HPP_INCLUDED
0003
0004 // Copyright 2017, 2018 Peter Dimov.
0005 // Distributed under the Boost Software License, Version 1.0.
0006 // https://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // FNV-1a
0009 //
0010 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
0011
0012 #include <boost/hash2/detail/write.hpp>
0013 #include <boost/assert.hpp>
0014 #include <boost/config.hpp>
0015 #include <cstdint>
0016 #include <cstddef>
0017
0018 namespace boost
0019 {
0020 namespace hash2
0021 {
0022
0023 namespace detail
0024 {
0025
0026 template<class T> struct fnv1a_const;
0027
0028 template<> struct fnv1a_const<std::uint32_t>
0029 {
0030     static constexpr std::uint32_t basis = 0x811C9DC5ul;
0031     static constexpr std::uint32_t prime = 0x01000193ul;
0032 };
0033
0034 template<> struct fnv1a_const<std::uint64_t>
0035 {
0036     static constexpr std::uint64_t basis = 0xCBF29CE484222325ull;
0037     static constexpr std::uint64_t prime = 0x00000100000001B3ull;
0038 };
0039
0040 template<class T> class fnv1a
0041 {
0042 private:
0043
0044     T st_ = fnv1a_const<T>::basis;
0045
0046 public:
0047
0048     typedef T result_type;
0049
0050     constexpr fnv1a() = default;
0051
0052     BOOST_CXX14_CONSTEXPR explicit fnv1a( std::uint64_t seed )
0053     {
0054         if( seed )
0055         {
0056             unsigned char tmp[ 8 ] = {};
0057             detail::write64le( tmp, seed );
0058             update( tmp, 8 );
0059         }
0060     }
0061
0062     BOOST_CXX14_CONSTEXPR fnv1a( unsigned char const * p, std::size_t n )
0063     {
0064         if( n != 0 )
0065         {
0066             update( p, n );
0067
0068             unsigned char tmp[ 4 ] = {};
0069             detail::write32le( tmp, static_cast<std::uint32_t>( n ) );
0070             update( tmp, 4 );
0071         }
0072     }
0073
0074     fnv1a( void const * p, std::size_t n ): fnv1a( static_cast<unsigned char const*>( p ), n )
0075     {
0076     }
0077
0078     BOOST_CXX14_CONSTEXPR void update( unsigned char const * p, std::size_t n )
0079     {
0080         T h = st_;
0081
0082         for( std::size_t i = 0; i < n; ++i )
0083         {
0084             h ^= static_cast<T>( p[i] );
0085             h *= fnv1a_const<T>::prime;
0086         }
0087
0088         st_ = h;
0089     }
0090
0091     void update( void const * pv, std::size_t n )
0092     {
0093         unsigned char const* p = static_cast<unsigned char const*>( pv );
0094         update( p, n );
0095     }
0096
0097     BOOST_CXX14_CONSTEXPR T result()
0098     {
0099         T r = st_;
0100
0101         // advance as if by update( "\xFF", 1 ), to allow
0102         // multiple result() calls to generate a sequence
0103         // of distinct values
0104
0105         st_ = ( st_ ^ 0xFF ) * fnv1a_const<T>::prime;
0106
0107         return r;
0108     }
0109 };
0110
0111 } // namespace detail
0112
0113 class fnv1a_32: public detail::fnv1a<std::uint32_t>
0114 {
0115 public:
0116
0117     constexpr fnv1a_32() = default;
0118
0119     BOOST_CXX14_CONSTEXPR explicit fnv1a_32( std::uint64_t seed ): detail::fnv1a<std::uint32_t>( seed )
0120     {
0121     }
0122
0123     BOOST_CXX14_CONSTEXPR fnv1a_32( unsigned char const * p, std::size_t n ): detail::fnv1a<std::uint32_t>( p, n )
0124     {
0125     }
0126
0127     fnv1a_32( void const * p, std::size_t n ): detail::fnv1a<std::uint32_t>( p, n )
0128     {
0129     }
0130 };
0131
0132 class fnv1a_64: public detail::fnv1a<std::uint64_t>
0133 {
0134 public:
0135
0136     constexpr fnv1a_64() = default;
0137
0138     BOOST_CXX14_CONSTEXPR explicit fnv1a_64( std::uint64_t seed ): detail::fnv1a<std::uint64_t>( seed )
0139     {
0140     }
0141
0142     BOOST_CXX14_CONSTEXPR fnv1a_64( unsigned char const * p, std::size_t n ): detail::fnv1a<std::uint64_t>( p, n )
0143     {
0144     }
0145
0146     fnv1a_64( void const * p, std::size_t n ): detail::fnv1a<std::uint64_t>( p, n )
0147     {
0148     }
0149 };
0150
0151 } // namespace hash2
0152 } // namespace boost
0153
0154 #endif // #ifndef BOOST_HASH2_FNV1A_HPP_INCLUDED