0
\$\begingroup\$

I had a file with 2 hash functions (DJB2, NMEA0183), written in C-like way, e.g. something like this:

uint8_t NMEA0183Hash(const char *s, size_t const size){
    uint8_t hash = 0;

    for(const char *c = s; c < s + size; ++c)
        hash = hash ^ (uint) c;

    return hash;
}

Everything looked nice. However, I needed those to be functors. I also wanted to see how FNV1 will compare, for this reason I refactor a bit.

Then I saw I have one and same loop in all functors. Then I saw how one can optimize FNV1 to avoid multiplication. I refactored bit more and result is this monstrosity.

I did not test final version, but gcc and clang clean the abstractions and result code is same as standard functions I started with.

Speed is the same, too. Usage is almost the same. Note I do like <uint64_t> part.

uint64_t const x = FNV1AHash<uint64_t>()("Hello");

Note - I did not tested SDBM.

Let me know if I can simplify it.

myhash.h

#include <cstdint>
#include <cstdlib>  // size_t

// DJB Hash function from CDB
template <typename uint>
struct DJB2Hash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

template <typename uint>
struct DJB2AHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// SDBM is reimplementation of NDBM
template <typename uint>
struct SDBMHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// FNV1 http://www.isthe.com/chongo/tech/comp/fnv/index.html
template <typename uint>
struct FNV1Hash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

template <typename uint>
struct FNV1AHash{
    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};



// NMEA0183
struct NMEA0183Hash{
    using uint = uint8_t;

    uint operator()(const char *s) const;
    uint operator()(const char *s, size_t const size) const;
};

myhash.cc

#include "myhash.h"

//#include <cstdio>

namespace{

    template <class HASH>
    class Hash_base_{
    public:
        using uint = typename HASH::uint;

        constexpr static uint offset_basis = HASH::offset_basis;

    public:
        uint calc(const char *s) const{
            uint hash = offset_basis;

            for(const char *c = s; *c; ++c)
                h_.add(hash, *c);

            return hash;
        }

        uint calc(const char *s, size_t const size) const{
            uint hash = offset_basis;

            for(const char *c = s; c < s + size; ++c)
                h_.add(hash, *c);

            return hash;
        }

    private:
        HASH h_;
    };



    // =====================================



    template <typename UINT>
    struct DJB2_base_{
        using uint = UINT;

        constexpr static uint offset_basis = 5381u;
    };

    template <typename uint>
    struct DJB2_ : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) + (uint) c;
        }
    };

    template <typename uint>
    struct DJB2A_ : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };



    // =====================================



    template <typename UINT>
    struct SDBM_{
        using uint = UINT;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };



    // =====================================



    template <typename UINT, UINT BASIS, UINT PRIME>
    struct FNV1_base_{
        using uint = UINT;

        constexpr static uint offset_basis = BASIS;
        constexpr static uint fnv_prime    = PRIME;

        void calc1(uint &hash, char const c) const{
            hash ^= (uint) c;
        }

        void calc2(uint &hash, char const c) const{
            hash *= fnv_prime;
        }
    };

    template <typename UINT>
    struct FNV1_base2_;

    template <>
    struct FNV1_base2_<uint32_t> : public FNV1_base_<uint32_t, 2166136261ul, 16777619ul>{
        constexpr static unsigned char ZERO_HASH[] = { 0x01, 0x47, 0x6c, 0x10, 0xf3, 0x00 };

        void calc2(uint &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 32 bit FNV_prime prime mod 2^32
            hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
        }
    };

    template <>
    struct FNV1_base2_<uint64_t> : public FNV1_base_<uint64_t, 14695981039346656037ull, 1099511628211ull>{
        constexpr static unsigned char ZERO_HASH[] = { 0x92, 0x06, 0x77, 0x4c, 0xe0, 0x2f, 0x89, 0x2a, 0xd2, 0x00 };

        void calc2(uint &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 64 bit FNV_prime prime mod 2^64
            hash += (hash << 1) + (hash << 4) + (hash << 5) +
                (hash << 7) + (hash << 8) + (hash << 40);
        }
    };

    // uint128_t
    // 144066263297769815596495629667062367629
    // 309485009821345068724781371

    template <typename uint>
    struct FNV1_ : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc1(hash, c);
            this->calc2(hash, c);
        }
    };

    template <typename uint>
    struct FNV1A_ : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc2(hash, c);
            this->calc1(hash, c);
        }
    };



    // =====================================



    struct NMEA0183_{
        using uint = uint8_t;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = hash ^ (uint) c;
        }
    };

} // namespace



// =====================================

template <typename uint>
uint DJB2Hash<uint>::operator()(const char *s) const{
    Hash_base_<DJB2_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint DJB2Hash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<DJB2_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint DJB2AHash<uint>::operator()(const char *s) const{
    Hash_base_<DJB2A_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint DJB2AHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<DJB2A_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint SDBMHash<uint>::operator()(const char *s) const{
    Hash_base_<SDBM_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint SDBMHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<SDBM_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint FNV1Hash<uint>::operator()(const char *s) const{
    Hash_base_<FNV1_<uint> > hb;

    return hb.calc(s);
}

template <typename uint>
uint FNV1Hash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<FNV1_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

template <typename uint>
uint FNV1AHash<uint>::operator()(const char *s) const{
    Hash_base_<FNV1A_<uint> > hb;
    return hb.calc(s);
}

template <typename uint>
uint FNV1AHash<uint>::operator()(const char *s, size_t const size) const{
    Hash_base_<FNV1A_<uint> > hb;
    return hb.calc(s, size);
}

// -------------------------------------

uint8_t NMEA0183Hash::operator()(const char *s) const{
    Hash_base_<NMEA0183_> hb;
    return hb.calc(s);
}

uint8_t NMEA0183Hash::operator()(const char *s, size_t const size) const{
    Hash_base_<NMEA0183_> hb;
    return hb.calc(s, size);
}

// =====================================

template struct DJB2Hash<uint32_t>;
template struct DJB2Hash<uint64_t>;

template struct DJB2AHash<uint32_t>;
template struct DJB2AHash<uint64_t>;

template struct SDBMHash<uint32_t>;
template struct SDBMHash<uint64_t>;

template struct FNV1Hash<uint32_t>;
template struct FNV1Hash<uint64_t>;

template struct FNV1AHash<uint32_t>;
template struct FNV1AHash<uint64_t>;
\$\endgroup\$
-2
\$\begingroup\$

Here is what I came up.

It is header only library now.

I believe is much more clear like this.

myhash.h

#ifndef MY_HASH_H_
#define MY_HASH_H_

#include <cstdint>
#include <cstdlib>  // size_t

#include "myhash_impl.h"

namespace myhash{

// DJB Hash function from CDB
template <typename uint>
using DJB2 = impl::MyHashBase<impl::DJB2<uint> >;

template <typename uint>
using DJB2A = impl::MyHashBase<impl::DJB2A<uint> >;


// SDBM is reimplementation of NDBM
template <typename uint>
using SDBM = impl::MyHashBase<impl::SDBM<uint> >;


// FNV1 http://www.isthe.com/chongo/tech/comp/fnv/index.html
template <typename uint>
using FNV1 = impl::MyHashBase<impl::FNV1<uint> >;

template <typename uint>
using FNV1A = impl::MyHashBase<impl::FNV1A<uint> >;


// NMEA0183
using NMEA0183 = impl::MyHashBase<impl::NMEA0183>;

} // namespace

#endif

myhash_impl.h

namespace myhash{
namespace impl{
namespace {

    template <class HASH>
    class MyHashBase{
    public:
        using uint = typename HASH::type;

        constexpr static uint offset_basis = HASH::offset_basis;

    public:
        uint operator()(const char *s) const{
            uint hash = offset_basis;

            for(const char *c = s; *c; ++c)
                h_.add(hash, *c);

            return hash;
        }

        uint operator()(const char *s, size_t const size) const{
            uint hash = offset_basis;

            for(const char *c = s; c < s + size; ++c)
                h_.add(hash, *c);

            return hash;
        }

    private:
        HASH h_;
    };

    // =====================================

    template <typename uint>
    struct DJB2_base_{
        using type = uint;

        constexpr static uint offset_basis = 5381u;
    };

    template <typename uint>
    struct DJB2 : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) + (uint) c;
        }
    };

    template <typename uint>
    struct DJB2A : public DJB2_base_<uint>{
        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };

    // =====================================

    template <typename uint>
    struct SDBM{
        using type = uint;

        constexpr static uint offset_basis = 0;

        void add(uint &hash, char const c) const{
            hash = ((hash << 5) + hash) ^ (uint) c;
        }
    };

    // =====================================

    struct NMEA0183{
        using type = uint8_t;

        constexpr static uint8_t offset_basis = 0;

        void add(uint8_t &hash, char const c) const{
            hash = hash ^ (uint8_t) c;
        }
    };

    // =====================================

    template <typename uint, uint BASIS, uint PRIME>
    struct FNV1_base_{
        using type = uint;

        constexpr static uint offset_basis = BASIS;
        constexpr static uint fnv_prime    = PRIME;

        void calc1(uint &hash, char const c) const{
            hash ^= (uint) c;
        }

        void calc2(uint &hash, char const c) const{
            hash *= fnv_prime;
        }
    };

    template <typename uint>
    struct FNV1_base2_;

    template <>
    struct FNV1_base2_<uint32_t> : public FNV1_base_<uint32_t, 2166136261ul, 16777619ul>{
        constexpr static unsigned char ZERO_HASH[] = { 0x01, 0x47, 0x6c, 0x10, 0xf3, 0x00 };

        void calc2(uint32_t &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 32 bit FNV_prime prime mod 2^32
            hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
        }
    };

    template <>
    struct FNV1_base2_<uint64_t> : public FNV1_base_<uint64_t, 14695981039346656037ull, 1099511628211ull>{
        constexpr static unsigned char ZERO_HASH[] = { 0x92, 0x06, 0x77, 0x4c, 0xe0, 0x2f, 0x89, 0x2a, 0xd2, 0x00 };

        void calc2(uint64_t &hash, char const c) const{
            (void)ZERO_HASH;

            // multiply by the 64 bit FNV_prime prime mod 2^64
            hash += (hash << 1) + (hash << 4) + (hash << 5) +
                (hash << 7) + (hash << 8) + (hash << 40);
        }
    };

    // uint128_t
    // 144066263297769815596495629667062367629
    // 309485009821345068724781371

    template <typename uint>
    struct FNV1 : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc1(hash, c);
            this->calc2(hash, c);
        }
    };

    template <typename uint>
    struct FNV1A : public FNV1_base2_<uint>{
        void add(uint &hash, char const c) const{
            this->calc2(hash, c);
            this->calc1(hash, c);
        }
    };

} // namespace anonymous
} // namespace impl
} // namespace
\$\endgroup\$
  • 1
    \$\begingroup\$ Just rewriting the OPs code is not a code review. It doesn't say why or what was good/bad. \$\endgroup\$ – Emily L. Jan 12 '17 at 16:07
  • \$\begingroup\$ @EmilyL. point well taken. It was mostly about code repetition vs boilerplate code. I still not sure if it is better, but I did include - "I believe is much more clear like this." \$\endgroup\$ – Nick Jan 13 '17 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.