pearson.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_PEARSON__
00032 #define __ETL_PEARSON__
00033 
00034 #include <stdint.h>
00035 
00036 #include "platform.h "
00037 #include "static_assert.h"
00038 #include "type_traits.h "
00039 #include "ihash.h "
00040 #include "array.h "
00041 #include "container.h "
00042 
00043 STATIC_ASSERT(ETL_8BIT_SUPPORT, "This file does not currently support targets with no 8bit type");
00044 
00045 #if defined(ETL_COMPILER_KEIL)
00046 #pragma diag_suppress 1300
00047 #endif
00048 
00049 ///\defgroup pearson Pearson hash calculation
00050 ///\ingroup pearson
00051 
00052 namespace etl
00053 {
00054   //***************************************************************************
00055   /// Pearson lookup table
00056   /// \ingroup pearson
00057   //***************************************************************************
00058   extern const uint8_t PEARSON_LOOKUP[];
00059 
00060   //***************************************************************************
00061   /// Calculates a Pearson hash
00062   ///\tparam HASH_LENGTH The number of elements in the hash.
00063   /// \ingroup pearson
00064   //***************************************************************************
00065   template <const size_t HASH_LENGTH>
00066   class pearson
00067   {
00068   public:
00069 
00070     typedef etl::array<uint8_t, HASH_LENGTH>  value_type ;
00071 
00072     //*************************************************************************
00073     /// Default constructor.
00074     //*************************************************************************
00075     pearson()
00076       : first(true)
00077     {
00078       reset();
00079     }
00080 
00081     //*************************************************************************
00082     /// Constructor from range.
00083     /// \param begin Start of the range.
00084     /// \param end   End of the range.
00085     //*************************************************************************
00086     template<typename TIterator>
00087     pearson(TIterator begin, const TIterator end)
00088       : first(true)
00089     {
00090       STATIC_ASSERT(sizeof(typename std::iterator_traits<TIterator>::value_type) == 1, "Type not supported");
00091 
00092       reset();
00093       add(begin, end);
00094     }
00095 
00096     //*************************************************************************
00097     /// Resets the hash to the initial state.
00098     //*************************************************************************
00099     void reset()
00100     {
00101       hash.fill(0);
00102     }
00103 
00104     //*************************************************************************
00105     /// Adds a range.
00106     /// \param begin
00107     /// \param end
00108     //*************************************************************************
00109     template<typename TIterator>
00110     void add(TIterator begin, const TIterator end)
00111     {
00112       STATIC_ASSERT(sizeof(typename std::iterator_traits<TIterator>::value_type) == 1, "Type not supported");
00113 
00114       while (begin != end)
00115       {
00116         add(*begin++);
00117       }
00118     }
00119 
00120     //*************************************************************************
00121     /// \param value The char to add to the hash.
00122     //*************************************************************************
00123     void add(uint8_t value_)
00124     {
00125       if (first)
00126       {
00127         for (size_t i = 0; i < HASH_LENGTH; ++i)
00128         {
00129           hash[i] = PEARSON_LOOKUP[(uint32_t(value_) + i) % 256];
00130         }
00131 
00132         first = false;
00133       }
00134       else
00135       {
00136         for (size_t i = 0; i < HASH_LENGTH; ++i)
00137         {
00138           hash[i] = PEARSON_LOOKUP[hash[i] ^ value_];
00139         }
00140       }
00141     }
00142 
00143     //*************************************************************************
00144     /// Gets the hash value.
00145     //*************************************************************************
00146     value_type  value() const
00147     {
00148       return hash;
00149     }
00150 
00151     //*************************************************************************
00152     /// Conversion operator to value_type.
00153     //*************************************************************************
00154     operator value_type () const
00155     {
00156       return value();
00157     }
00158 
00159   private:
00160 
00161     bool first;
00162     value_type hash;
00163   };
00164 }
00165 
00166 #endif
00167