hash.hpp

//
//  khash.h
//
//  Created by Paul Perekhozhikh on 16.10.13.
//  Copyright (c) 2013 Paul. All rights reserved.
//

#ifndef khash_h
#define khash_h

#include <stdint.h>

namespace kukurudza {
   namespace hashes{
      // Константа, взятая из SunriseDD.
      const size_t DD_SIGNIFICANT_CHARS = 32;
      
      // Функция хэширования, взятая из SunriseDD.
      //
      // --------------------------------------------------------------------------
      // Function:  dd_FNVM_hash_string(string)
      // --------------------------------------------------------------------------
      //
      // Returns the hash value of the null terminated C string <string>  using the
      // FNVM hash algorithm  (Fowler, Noll and Vo hash,  modified by Bret Mulvey).
      // The number of  significant characters  for  which the hash value  will  be
      // calculated   is   limited   to   the   value    returned    by    function
      // dd_significant_chars().
      //
      // Returns 0 if <string> is empty or NULL.
      //
      inline uint32_t
      hash_FNVM(const char *string, size_t string_size) {
         // seed values for FNV hashes
         const uint32_t FNVM_INIT32 = 0x811c9dc5;
         const uint32_t FNVM_PRIME32 = 0x01000193;
         
#ifndef __clang__
         register uint32_t index = 0, hash = FNVM_INIT32;
#else 
         uint32_t index = 0, hash = FNVM_INIT32;
#endif
         
         if (!string_size)
            return 0;
         
         while ((index < string_size) && (index < DD_SIGNIFICANT_CHARS))
         {
            hash = hash ^ string[index];
            hash = hash * FNVM_PRIME32;
            index++;
         } // end while
         
         hash = hash + (hash << 13);
         hash = hash ^ (hash >> 7);
         hash = hash + (hash << 3);
         hash = hash ^ (hash >> 17);
         hash = hash + (hash << 5);
         
         return (hash & 0x7fffffff);
      } // end dd_FNV_hash_string
      
      // Функция хэширования, взятая из SunriseDD.
      //
      // --------------------------------------------------------------------------
      // Function:  dd_ELF_hash_string(string)
      // --------------------------------------------------------------------------
      //
      // Returns the hash value of the null terminated C string <string>  using the
      // ELF hash algorithm  (as used in most Unix systems for passwd hashes).  The
      // number   of  significant characters  for  which  the  hash value  will  be
      // calculated    is    limited   to   the   value   returned   by    function
      // dd_significant_chars().
      //
      // Returns 0 if <string> is empty or NULL.
      //
      inline uint32_t
      hash_ELF(const char *string, size_t string_size) {
#ifndef __clang__
         register uint32_t index = 0, temp = 0, hash = 0;
#else
         uint32_t index = 0, temp = 0, hash = 0;
#endif
         
         if (!string_size)
            return 0;
         
         while ((index < string_size) && (index < DD_SIGNIFICANT_CHARS))
         {
            hash = (hash << 4) + string[index];
            temp = hash & 0xF0000000L;
            if (temp != 0)
               hash = hash ^ (temp >> 24);
            hash = hash & (~temp);
            index++;
         } // end while
         
         return (hash & 0x7fffffff);
      } // end dd_ELF_hash_string
      
      // Функция хэширования, взятая из SunriseDD.
      //
      // --------------------------------------------------------------------------
      // Function:  dd_DJB_hash_string(string)
      // --------------------------------------------------------------------------
      //
      // Returns the hash value of the null terminated C string <string>  using the
      // DJB hash algorithm  (published by D.J.Bernstein on Usenet in comp.lang.c).
      // The number  of  significant characters  for which the  hash value  will be
      // calculated    is    limited   to   the   value   returned   by    function
      // dd_significant_chars().
      //
      // Returns 0 if <string> is empty or NULL.
      //
      inline uint32_t
      hash_DJB(const char *string, size_t string_size) {
         // seed value for DJB hashes
         const uint32_t DJB_INIT = 5381;
#ifndef __clang__
         register uint32_t index = 0, hash = DJB_INIT;
#else
         uint32_t index = 0, hash = DJB_INIT;
#endif
         
         if (!string_size)
            return 0;
         
         while ((index < string_size) && (index < DD_SIGNIFICANT_CHARS)) {
            hash = string[index] + ((hash << 5) + hash);
            index++;
         } // end while
         
         return (hash & 0x7fffffff);
      } // end dd_DJB_hash_string
      
      // Функция хэширования, взятая из SunriseDD.
      //
      // --------------------------------------------------------------------------
      // function:  dd_SDBM_hash_string(string)
      // --------------------------------------------------------------------------
      //
      // Returns the hash value of the null terminated C string <string>  using the
      // SDBM hash algorithm.  The number  of significant characters  for which the
      // hash  value  will  be  calculated  is limited to  the  value  returned  by
      // function dd_significant_chars().
      inline uint32_t
      hash_SDBM(const char *string, size_t string_size) {
#ifndef __clang__
         register uint32_t len = (uint32_t)string_size, index, hash = 0;
         register char ch;
#else
         uint32_t len = (uint32_t)string_size, index, hash = 0;
         char ch;
#endif
         
         if (len > DD_SIGNIFICANT_CHARS) {
            len = DD_SIGNIFICANT_CHARS;
         } // end if
         
         // PUBLIC DOMAIN ALGORITHM FOLLOWS
         for (index = 0; index < len; index++) {
            ch = string[index];
            hash = ch + (hash << 6) + (hash << 16) - hash;
         } // end for
         
         return (hash & 0x7FFFFFFF);
      } // end dd_SDBM_hash_string
      
      // Функция хэширования, взятая из SunriseDD.
      //
      // --------------------------------------------------------------------------
      // Function:  dd_HSIEH_hash_string(string)
      // --------------------------------------------------------------------------
      //
      // Returns the hash value of the null terminated C string <string>  using the
      // HSIEH hash algorithm (developed by Paul Hsieh).  The number of significant
      // characters for which the hash value will be calculated  is limited  to the
      // value returned by function dd_significant_chars().
      //
      // Returns 0 if <string> is empty or NULL.
      //
      inline uint32_t
      hash_HSIEH( const char *string, size_t string_size ) {
#define _UINT32(v) ((uint32_t)(v))
         
         if (!string_size)
            return 0;
#ifndef __clang__
         register uint32_t temp, hash;
         register size_t rem, len;
         register size_t index = (string_size < DD_SIGNIFICANT_CHARS) ? string_size : DD_SIGNIFICANT_CHARS;
#else
         uint32_t temp, hash;
         size_t rem, len;
         size_t index = (string_size < DD_SIGNIFICANT_CHARS) ? string_size : DD_SIGNIFICANT_CHARS;
#endif
         
         hash = _UINT32(index); // initial value for hash
         
         // our main loop handles 4 chars at every iteration
         // so we need to exclude any chars at the end which
         // don't fit into a multiple of 4 sized buffer
         // those chars will be processed separately
         rem = index & 3; // number of remaining chars
         len = index - rem; // number of chars in buffer
         
         index = 0;
         // processing chars in buffer
         while (index < len) {
            hash = hash + (_UINT32(string[index]) << 8); index++;
            hash = hash + (_UINT32(string[index])); index++;
            temp = (_UINT32(string[index]) << 8); index ++;
            temp = ((temp + (_UINT32(string[index]))) << 11) ^ hash;
            hash = ((hash << 16) ^ temp) >> 11;
            index++;
         } // end while
         
         // processing remaining chars
         switch (rem) {
            case 3:
               hash = hash + (_UINT32(string[index]) << 8); index++;
               hash = hash + (_UINT32(string[index])); index++;
               hash = hash ^ (hash << 16);
               hash = hash ^ ((_UINT32(string[index])) << 18);
               hash = hash + (hash >> 11);
               break;
            case 2:
               hash = hash + (_UINT32(string[index]) << 8); index++;
               hash = hash + (_UINT32(string[index]));
               hash = hash ^ (hash << 11);
               hash = hash + (hash >> 17);
               break;
            case 1:
               hash = hash + (_UINT32(string[index]) << 8);
               hash = hash ^ (hash << 10);
               hash = hash + (hash >> 1);
         } // end switch
         
         // mishmash least significant 127 bits
         hash = hash ^ (hash << 3);
         hash = hash + (hash >> 5);
         hash = hash ^ (hash << 4);
         hash = hash + (hash >> 17);
         hash = hash ^ (hash << 25);
         hash = hash + (hash >> 6);
         
         return (hash & 0x7fffffff);
      }

      class KHashHelper{
      public:
         template<typename T>
         static T FNVM(const std::string &content){
            return (T)hash_FNVM(content.c_str(), content.length());
         }
         
         template<typename T>
         static T ELF(const std::string &content){
            return (T)hash_ELF(content.c_str(), content.length());
         }
         
         template<typename T>
         static T DJB(const std::string &content){
            return (T)hash_DJB(content.c_str(), content.length());
         }
         
         template<typename T>
         static T SDBM(const std::string &content){
            return (T)hash_SDBM(content.c_str(), content.length());
         }
      };
   }
}

#endif