---

more/math/hash.h

Go to the documentation of this file.

//  Copyright (C) 2001--2002  Petter Urkedal
//
//  This file is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This file is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: hash.h,v 1.2 2002/08/24 13:52:14 petter_urkedal Exp $


#ifndef MORE_MATH_HASH_H

#include <more/lang/stdint.h>
#include <more/io/syncstream.h>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <cstdlib>
#include <assert.h>


namespace more {
namespace math {

  ///\if bits
  namespace bits {
    using lang::uint_least32_t;
    using lang::uint_least64_t;

    template<unsigned int WordWidth>
      struct hash_base {};

    template<>
      struct hash_base<192>
      {
          typedef uint_least64_t word_type;
          static std::size_t const word_width = 64;
          static std::size_t const word_count = 3;
          typedef word_type* word_iterator;
          typedef word_type const* word_const_iterator;

          hash_base() {}
          hash_base(word_type init)
              : m_n_free(16)
          {
              m_st[0] = init;
              m_st[1] = m_st[2] = 0x9e3779b97f4a7c13LL;
          }

          void insert_impl(unsigned char const* it,
                           unsigned char const* it_end);

          word_iterator word_begin() { return m_st; }
          word_iterator word_end() { return m_st + 3; }
          word_const_iterator word_begin() const { return m_st; }
          word_const_iterator word_end() const { return m_st + 3; }

          bool operator==(hash_base const& rhs) const
          {
              return m_st[0] == rhs.m_st[0]
                  && m_st[1] == rhs.m_st[1]
                  && m_st[2] == rhs.m_st[2];
          }

          bool operator<(hash_base const& rhs) const
          {
              if (m_st[0] < rhs.m_st[0]) return true;
              if (m_st[0] > rhs.m_st[0]) return false;
              if (m_st[1] < rhs.m_st[1]) return true;
              if (m_st[1] > rhs.m_st[1]) return false;
              return m_st[2] < rhs.m_st[2];
          }

        protected:
          uint_least64_t m_st[3];
          std::size_t m_n_free;
      };

    template<>
      struct hash_base<160> : hash_base<192>
      {
          hash_base() {}
          hash_base(word_type init)
              : hash_base<192>(init) {}
      };

    template<>
      struct hash_base<128> : hash_base<192>
      {
          static std::size_t const word_count = 2;

          hash_base() {}
          hash_base(word_type init)
              : hash_base<192>(init) {}

          word_iterator word_end() { return m_st + 2; }
          word_const_iterator word_end() const { return m_st + 2; }

          bool operator==(hash_base const& rhs) const
          {
              return m_st[0] == rhs.m_st[0]
                  && m_st[1] == rhs.m_st[1];
          }

          bool operator<(hash_base const& rhs) const
          {
              if (m_st[0] < rhs.m_st[0]) return true;
              if (m_st[0] > rhs.m_st[0]) return false;
              return m_st[1] < rhs.m_st[1];
          }
      };

    template<>
      struct hash_base<96>
      {
          typedef uint_least32_t word_type;
          static std::size_t const word_width = 32;
          static std::size_t const word_count = 3;
          typedef word_type* word_iterator;
          typedef word_type const* word_const_iterator;

          hash_base() {}
          hash_base(word_type init)
              : m_n_free(8)
          {
              m_st[0] = init;
              m_st[1] = m_st[2] = 0x9e3779b9;
          }

          void insert_impl(unsigned char const* it,
                           unsigned char const* it_end);
//XXX     void insert_impl(word_type const* it, word_type const* it_end)

          word_iterator word_begin() { return m_st; }
          word_iterator word_end() { return m_st + 3; }
          word_const_iterator word_begin() const { return m_st; }
          word_const_iterator word_end() const { return m_st + 3; }

          bool operator==(hash_base const& rhs) const
          {
              return m_st[0] == rhs.m_st[0]
                  && m_st[1] == rhs.m_st[1]
                  && m_st[2] == rhs.m_st[2];
          }

          bool operator<(hash_base const& rhs) const
          {
              if (m_st[0] < rhs.m_st[0]) return true;
              if (m_st[0] > rhs.m_st[0]) return false;
              if (m_st[1] < rhs.m_st[1]) return true;
              if (m_st[1] > rhs.m_st[1]) return false;
              return m_st[2] < rhs.m_st[2];
          }

        protected:
          uint_least32_t m_st[3];
          unsigned short m_n_free;
      };

    template<>
      struct hash_base<64> : hash_base<96>
      {
          static std::size_t const word_count = 2;

          hash_base() {}
          hash_base(word_type init)
              : hash_base<96>(init) {}

          word_iterator word_end() { return m_st + 2; }
          word_const_iterator word_end() const { return m_st + 2; }

          bool operator==(hash_base const& rhs) const
          {
              return m_st[0] == rhs.m_st[0]
                  && m_st[1] == rhs.m_st[1];
          }

          bool operator<(hash_base const& rhs) const
          {
              if (m_st[0] < rhs.m_st[0]) return true;
              if (m_st[0] > rhs.m_st[0]) return false;
              return m_st[1] < rhs.m_st[1];
          }
      };

    template<>
      struct hash_base<32> : hash_base<96>
      {
          static std::size_t const word_count = 1;

          hash_base() {}
          hash_base(word_type init)
              : hash_base<96>(init) {}

          word_iterator word_end() { return m_st + 1; }
          word_const_iterator word_end() const { return m_st + 1; }

          bool operator==(hash_base const& rhs) const
          {
              return m_st[0] == rhs.m_st[0];
          }

          bool operator<(hash_base const& rhs) const
          {
              return m_st[0] < rhs.m_st[0];
          }
      };
  }
  ///\endif

  /** Encode an integer in the range [0.. 52) as an alphabetic ASCII
      character. */
  inline char
  encode_alpha(unsigned int k)
  {
      if (k < 26)
          return 'A' + k;
      else if (k < 52)
          return 'a' - 26 + k;
      else
          throw std::out_of_range("more::math::encode_alnum: "
                                  "Number is too lange to encode.");
  }

  /** Decode an integer encoded with encode_alpha. */
  inline unsigned char
  decode_alpha(char ch)
  {
      if ('A' <= ch && ch <= 'Z')
          return ch - 'A';
      else if ('a' <= ch && ch <= 'z')
          return ch - ('a' - 26);
      else
          throw std::logic_error("more::math::decode_alpha: "
                                 "Invalid character in encoding.");
  }

  /** Encode an integer in the range [0..62) as an alphanumeric ASCII
      character. */
  inline char
  encode_alnum(unsigned int k)
  {
      if (k < 26)
          return 'A' + k;
      else if (k < 52)
          return 'a' - 26 + k;
      else if (k < 62)
          return '0' - 52 + k;
      else
          throw std::out_of_range("more::math::encode_alnum: "
                                  "Number is too lange to encode.");
  }

  /** Decode an integer encoded with encode_alnum. */
  inline unsigned char
  decode_alnum(char ch)
  {
      if ('A' <= ch && ch <= 'Z')
          return ch - 'A';
      else if ('a' <= ch && ch <= 'z')
          return ch - ('a' - 26);
      else if ('0' <= ch && ch <= '9')
          return ch - ('0' - 52);
      else
          throw std::logic_error("more::math::decode_alnum: "
                                 "Invalid character in encoding.");
  }

  /** Returns a 32 bits encoding of 6 lower case characters.  This may
      be useful for putting tags into hashes.  Picking a random number
      does the same effect, though macro can increases readability,
      and together with a consistent scheme help avoid collisions
      without resorting to big random numbers.  All sequences of
      letters of the same case will give differt values.  Mixing lower
      case letters with uppercase or digits may lead to collitions. */
  inline lang::uint_least32_t
  hash_id32(char ch0 = 0, char ch1 = 0, char ch2 = 0,
            char ch3 = 0, char ch4 = 0, char ch5 = 0)
  {
      // The first term is a random number small enough not to cause
      // overflow and thus system dependecy.  The last char is shifted
      // 25 bits, thus leaving 7 bits to avoid overflow.
      return 31719
          + ch0 + 32*(ch1 + 32*(ch2 + 32*(ch3 + 32*(ch4 + 32*ch5))));
  }

  /** Encodes a 64 bits numbers into 1 ASCII alphabetic followed by 10
      ASCII alphanumeric characters.  This function may me moved to
      another header and namespace. */
  void encode64_alnum(lang::uint_least64_t, char* s);

  /** Decodes a 64 bits number encoded with encode64_alnum. This
      function may me moved to another header and namespace.*/
  lang::uint_least64_t decode64_alnum(char const* s);

  /*x* Encodes a 32 bits number into 6 ASCII alphabetic
      characters. This function may me moved to another header and
      namespace.*/
//  void encode32_alpha(uint_least32_t, char*& s);

  /*x* Decodes a number encoded with encode32_alnum. This function may
      me moved to another header and namespace.*/
//  uint_least32_t decode32_alpha(char const*& s);

  /** \class hash hash.h more/math/hash.h
      A hash of minimum Width number of bits.  The implemented values
      for Width at the moment are 96 and 192, other values will be
      eigther truncated or non-truncated versions of an implementation
      with more bits.  Width > 192 gives compile-time error.  I
      believe this hash function is rather good, but DON'T USE IT FOR
      SECURITY without checking it, I take no responsibility!  It is
      used by the lang module to create unique file names.  */
  template<unsigned int Width>
    struct hash
        : bits::hash_base<(Width + 31)/32*32>
    {
      private:
        typedef bits::hash_base<(Width + 31)/32*32> base;
      public:
        typedef typename base::word_type word_type;
        typedef typename base::word_iterator word_iterator;
        typedef typename base::word_const_iterator word_const_iterator;
        static std::size_t const word_count = base::word_count;
        static std::size_t const word_width = base::word_width;
        static std::size_t const word_size = word_width/8;
        static std::size_t const width = word_count*word_width;
        static std::size_t const c_name_strlen
            = (word_width == 64? word_count*11 : word_count*word_size/2*3);

        /** Trivial constructor. */
        hash() {}

        /** Construct a hash with the given start value (seed). */
        hash(word_type x)
            : base(x) {}

        /** Chop a sequence of arithmetic values into the hash.  This
            is equivalent to inserting each value separately in the
            same order. */
        template <typename T>
          void
          insert(T const* it, T const* it_end)
          {
//XXX         if (sizeof(T) == sizeof(word_type))
//XXX             base::insert_impl((word_type*)it, (word_type*)it_end);
//XXX         else
                  insert_impl((unsigned char*)it, (unsigned char*)it_end);
          }

        /** Chop an arithmetic value into the hash. */
        template <typename T>
          void
          insert(T const& x)
          {
              insert(&x, &x + 1);
          }

        /** Writes c_name_strlen alphanumeric ascii characters to s,
            starting with an alphabetic.  The result is not
            0-terminated. */
        void
        strncpy_to_c_name(char* s) const
        {
            for (word_const_iterator it = word_begin();
                 it != word_end(); ++it)
                encode_word(*it, s);
        }

        /** Initializes the hash from a name written by
            strncpy_c_name.  The hash will compare equal to the
            original, but if this is a truncated hash type (cf the
            Width template argument), the hashes will develop
            differtly on further insertions. */
        void
        assign_from_c_name(char const* s)
        {
            s += c_name_strlen;
            word_iterator it = word_end();
            while (it != word_begin()) {
                --it;
                *it = decode_word(s);
            }
        }

#if 0
        std::string
        to_c_name() const
        {
            char buf[c_name_strlen];
            to_c_name(c_name_strlen);
            return std::string(buf, c_name_strlen);
        }

        void
        from_c_name(std::string const& str)
        {
            from_c_name(str.c_str());
        }
#endif

        void
        sync(io::syncstream& sio)
        {
            more::io::sync_range(sio, begin(), end());
        }

      private:
        static void
        encode_word(word_type k, char*& s)
        {
            if (word_width == 64) {
                encode64_alnum(k, s);
                s += 11;
            }
            else
                for (std::size_t j = 0; j < word_size/2; ++j) {
                    *s++ = encode_alpha(k & 0x1f);
                    k >>= 5;
                    *s++ = encode_alpha((k & 0x7ff) % 52);
                    *s++ = encode_alpha((k & 0x7ff) / 52);
                    k >>= 11;
                }
        }

        static word_type
        decode_word(char const*& s)
        {
            if (word_width == 64) {
                s -= 11;
                return decode64_alnum(s);
            }
            else {
                word_type k = 0;
                for (std::size_t j = 0; j < word_size/2; ++j) {
                    k <<= 11;
                    k += decode_alpha(*--s)*52;
                    k += decode_alpha(*--s);
                    k <<= 5;
                    k |= decode_alpha(*--s);
                }
                return k;
            }
        }
    };

  template <unsigned int Width>
    inline std::ostream&
    operator<<(std::ostream& os, hash<Width> const& h)
    {
        typename hash<Width>::word_const_iterator it = h.word_begin();
        os << std::setfill('0') << std::setbase(16) << std::setw(4) << *it;
        while (++it != h.word_end())
            os << ':' << std::setbase(16) << std::setw(4) << *it;
        return os;
    }


}}

#endif

---