murmur3.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2014 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_MURMUR3__
00032 #define __ETL_MURMUR3__
00033 
00034 #include <stdint.h>
00035 
00036 #include "platform.h "
00037 #include "ihash.h "
00038 #include "binary.h "
00039 #include "error_handler.h "
00040 
00041 #if defined(ETL_COMPILER_KEIL)
00042 #pragma diag_suppress 1300
00043 #endif
00044 
00045 ///\defgroup murmur3 Murmur3 hash calculations
00046 ///\ingroup maths
00047 
00048 namespace etl
00049 {
00050   //***************************************************************************
00051   /// Calculates the murmur3 hash.
00052   /// See https://en.wikipedia.org/wiki/MurmurHash for more details.
00053   ///\ingroup murmur3
00054   //***************************************************************************
00055   template <typename THash>
00056   class murmur3
00057   {
00058   public:
00059 
00060     STATIC_ASSERT((etl::is_same<THash, uint32_t>::value || etl::is_same<THash, uint64_t>::value), "Only 32 & 64 bit types supported");
00061 
00062     typedef THash value_type;
00063 
00064     //*************************************************************************
00065     /// Default constructor.
00066     /// \param seed The seed value. Default = 0.
00067     //*************************************************************************
00068     murmur3(value_type seed_ = 0)
00069       : seed(seed_)
00070     {
00071       reset();
00072     }
00073 
00074     //*************************************************************************
00075     /// Constructor from range.
00076     /// \param begin Start of the range.
00077     /// \param end   End of the range.
00078     /// \param seed  The seed value. Default = 0.
00079     //*************************************************************************
00080     template<typename TIterator>
00081     murmur3(TIterator begin, const TIterator end, value_type seed_ = 0)
00082       : seed(seed_)
00083     {
00084       STATIC_ASSERT(sizeof(typename std::iterator_traits<TIterator>::value_type) == 1, "Incompatible type");
00085 
00086       reset();
00087       while (begin != end)
00088       {
00089         block |= (*begin++) << (block_fill_count * 8);
00090 
00091         if (++block_fill_count == FULL_BLOCK)
00092         {
00093           add_block();
00094           block_fill_count = 0;
00095           block = 0;
00096         }
00097 
00098         ++char_count;
00099       }
00100     }
00101 
00102     //*************************************************************************
00103     /// Resets the hash to the initial state.
00104     //*************************************************************************
00105     void reset()
00106     {
00107       hash             = seed;
00108       char_count       = 0;
00109       block            = 0;
00110       block_fill_count = 0;
00111       is_finalised     = false;
00112     }
00113 
00114     //*************************************************************************
00115     /// Adds a range.
00116     /// \param begin
00117     /// \param end
00118     //*************************************************************************
00119     template<typename TIterator>
00120     void add(TIterator begin, const TIterator end)
00121     {
00122       STATIC_ASSERT(sizeof(typename std::iterator_traits<TIterator>::value_type) == 1, "Incompatible type");
00123       ETL_ASSERT(!is_finalised, ETL_ERROR(hash_finalised));
00124 
00125       while (begin != end)
00126       {
00127         block |= (*begin++) << (block_fill_count * 8);
00128 
00129         if (++block_fill_count == FULL_BLOCK)
00130         {
00131           add_block();
00132           block_fill_count = 0;
00133           block = 0;
00134         }
00135 
00136         ++char_count;
00137       }
00138     }
00139 
00140     //*************************************************************************
00141     /// Adds a uint8_t value.
00142     /// If the hash has already been finalised then a 'hash_finalised' error will be emitted.
00143     /// \param value The char to add to the hash.
00144     //*************************************************************************
00145     void add(uint8_t value_)
00146     {
00147       // We can't add to a finalised hash!
00148       ETL_ASSERT(!is_finalised, ETL_ERROR(hash_finalised));
00149 
00150       block |= value_ << (block_fill_count * 8);
00151 
00152       if (++block_fill_count == FULL_BLOCK)
00153       {
00154         add_block();
00155         block_fill_count = 0;
00156         block = 0;
00157       }
00158 
00159       ++char_count;
00160     }
00161 
00162     //*************************************************************************
00163     /// Gets the hash value.
00164     //*************************************************************************
00165     value_type value()
00166     {
00167       finalise();
00168       return hash;
00169     }
00170 
00171     //*************************************************************************
00172     /// Conversion operator to value_type.
00173     //*************************************************************************
00174     operator value_type ()
00175     {
00176       return value();
00177     }
00178 
00179   private:
00180 
00181     //*************************************************************************
00182     /// Adds a filled block to the hash.
00183     //*************************************************************************
00184     void add_block()
00185     {
00186       block *= CONSTANT1;
00187       block = rotate_left(block, SHIFT1);
00188       block *= CONSTANT2;
00189 
00190       hash ^= block;
00191       hash = rotate_left(hash, SHIFT2);
00192       hash = (hash * MULTIPLY) + ADD;
00193     }
00194 
00195     //*************************************************************************
00196     /// Finalises the hash.
00197     //*************************************************************************
00198     void finalise()
00199     {
00200       if (!is_finalised)
00201       {
00202         block *= CONSTANT1;
00203         block = rotate_left(block, SHIFT1);
00204         block *= CONSTANT2;
00205 
00206         hash ^= block;
00207         hash ^= char_count;
00208         hash ^= (hash >> 16);
00209         hash *= 0x85EBCA6B;
00210         hash ^= (hash >> 13);
00211         hash *= 0xC2B2AE35;
00212         hash ^= (hash >> 16);
00213 
00214         is_finalised = true;
00215       }
00216     }
00217 
00218     bool       is_finalised;
00219     uint8_t    block_fill_count;
00220     size_t     char_count;
00221     value_type block;
00222     value_type hash;
00223     value_type seed;
00224 
00225     static const uint8_t    FULL_BLOCK = 4;
00226     static const value_type CONSTANT1  = 0xCC9E2D51;
00227     static const value_type CONSTANT2  = 0x1B873593;
00228     static const value_type SHIFT1     = 15;
00229     static const value_type SHIFT2     = 13;
00230     static const value_type MULTIPLY   = 5;
00231     static const value_type ADD        = 0xE6546B64;
00232   };
00233 }
00234 
00235 #endif
00236