FixedHash.h

Go to the documentation of this file.

/*
    This file is part of cpp-ethereum.
 
    cpp-ethereum 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 3 of the License, or
    (at your option) any later version.
 
    cpp-ethereum 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 cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
 
#include <array>
#include <cstdint>
#include <algorithm>
#include <random>
#include <opendht/rng.h>
 
#include "CommonData.h"
 
namespace dev {
 
template<unsigned N>
struct StaticLog2
{
    enum { result = 1 + StaticLog2<N / 2>::result };
};
template<>
struct StaticLog2<1>
{
    enum { result = 0 };
};
 
template<unsigned N>
class FixedHash
{
public:
    enum { size = N };
 
    enum ConstructFromPointerType { ConstructFromPointer };
 
    enum ConstructFromStringType { FromHex, FromBinary };
 
    enum ConstructFromHashType { AlignLeft, AlignRight, FailIfDifferent };
 
    FixedHash() { m_data.fill(0); }
 
    template<unsigned M>
    explicit FixedHash(FixedHash<M> const& _h, ConstructFromHashType _t = AlignLeft)
    {
        m_data.fill(0);
        unsigned c = std::min(M, N);
        for (unsigned i = 0; i < c; ++i)
            m_data[_t == AlignRight ? N - 1 - i : i] = _h[_t == AlignRight ? M - 1 - i : i];
    }
 
    explicit FixedHash(unsigned _u) { toBigEndian(_u, m_data); }
 
    explicit FixedHash(bytes const& _b, ConstructFromHashType _t = FailIfDifferent)
    {
        if (_b.size() == N)
            memcpy(m_data.data(), _b.data(), std::min<unsigned>(_b.size(), N));
        else {
            m_data.fill(0);
            if (_t != FailIfDifferent) {
                auto c = std::min<unsigned>(_b.size(), N);
                for (unsigned i = 0; i < c; ++i)
                    m_data[_t == AlignRight ? N - 1 - i : i] = _b[_t == AlignRight ? _b.size() - 1 - i : i];
            }
        }
    }
 
    explicit FixedHash(bytesConstRef _b, ConstructFromHashType _t = FailIfDifferent)
    {
        if (_b.size() == N)
            memcpy(m_data.data(), _b.data(), std::min<unsigned>(_b.size(), N));
        else {
            m_data.fill(0);
            if (_t != FailIfDifferent) {
                auto c = std::min<unsigned>(_b.size(), N);
                for (unsigned i = 0; i < c; ++i)
                    m_data[_t == AlignRight ? N - 1 - i : i] = _b[_t == AlignRight ? _b.size() - 1 - i : i];
            }
        }
    }
 
    explicit FixedHash(uint8_t const* _bs, ConstructFromPointerType) { memcpy(m_data.data(), _bs, N); }
 
    explicit FixedHash(std::string const& _s,
                       ConstructFromStringType _t = FromHex,
                       ConstructFromHashType _ht = FailIfDifferent)
        : FixedHash(_t == FromHex ? fromHex(_s, WhenError::Throw) : dev::asBytes(_s), _ht)
    {}
 
    explicit operator bool() const
    {
        return std::any_of(m_data.begin(), m_data.end(), [](uint8_t _b) { return _b != 0; });
    }
 
    // The obvious comparison operators.
    bool operator==(FixedHash const& _c) const { return m_data == _c.m_data; }
    bool operator!=(FixedHash const& _c) const { return m_data != _c.m_data; }
    bool operator<(FixedHash const& _c) const
    {
        for (unsigned i = 0; i < N; ++i)
            if (m_data[i] < _c.m_data[i])
                return true;
            else if (m_data[i] > _c.m_data[i])
                return false;
        return false;
    }
    bool operator>=(FixedHash const& _c) const { return !operator<(_c); }
    bool operator<=(FixedHash const& _c) const { return operator==(_c) || operator<(_c); }
    bool operator>(FixedHash const& _c) const { return !operator<=(_c); }
 
    // The obvious binary operators.
    FixedHash& operator^=(FixedHash const& _c)
    {
        for (unsigned i = 0; i < N; ++i)
            m_data[i] ^= _c.m_data[i];
        return *this;
    }
    FixedHash operator^(FixedHash const& _c) const { return FixedHash(*this) ^= _c; }
    FixedHash& operator|=(FixedHash const& _c)
    {
        for (unsigned i = 0; i < N; ++i)
            m_data[i] |= _c.m_data[i];
        return *this;
    }
    FixedHash operator|(FixedHash const& _c) const { return FixedHash(*this) |= _c; }
    FixedHash& operator&=(FixedHash const& _c)
    {
        for (unsigned i = 0; i < N; ++i)
            m_data[i] &= _c.m_data[i];
        return *this;
    }
    FixedHash operator&(FixedHash const& _c) const { return FixedHash(*this) &= _c; }
    FixedHash operator~() const
    {
        FixedHash ret;
        for (unsigned i = 0; i < N; ++i)
            ret[i] = ~m_data[i];
        return ret;
    }
 
    // Big-endian increment.
    FixedHash& operator++()
    {
        for (unsigned i = size; i > 0 && !++m_data[--i];) {
        }
        return *this;
    }
 
    bool contains(FixedHash const& _c) const { return (*this & _c) == _c; }
 
    uint8_t& operator[](unsigned _i) { return m_data[_i]; }
    uint8_t operator[](unsigned _i) const { return m_data[_i]; }
 
    std::string abridged() const { return toHex(ref().cropped(0, 4)) + "\342\200\246"; }
 
    std::string abridgedMiddle() const
    {
        return toHex(ref().cropped(0, 4)) + "\342\200\246" + toHex(ref().cropped(N - 4));
    }
 
    std::string hex() const { return toHex(ref()); }
 
    bytesRef ref() { return bytesRef(m_data.data(), N); }
 
    bytesConstRef ref() const { return bytesConstRef(m_data.data(), N); }
 
    uint8_t* data() { return m_data.data(); }
 
    uint8_t const* data() const { return m_data.data(); }
 
    auto begin() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.begin(); }
 
    auto end() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.end(); }
 
    bytes asBytes() const { return bytes(data(), data() + N); }
 
    std::array<uint8_t, N>& asArray() { return m_data; }
 
    std::array<uint8_t, N> const& asArray() const { return m_data; }
 
    template<class Engine>
    void randomize(Engine& _eng)
    {
        for (auto& i : m_data)
            i = (uint8_t) std::uniform_int_distribution<uint16_t>(0, 255)(_eng);
    }
 
    static FixedHash random()
    {
        FixedHash ret;
        std::random_device rd;
        ret.randomize(rd);
        return ret;
    }
 
    template<unsigned P, unsigned M>
    inline FixedHash& shiftBloom(FixedHash<M> const& _h)
    {
        return (*this |= _h.template bloomPart<P, N>());
    }
 
    template<unsigned P, unsigned M>
    inline bool containsBloom(FixedHash<M> const& _h)
    {
        return contains(_h.template bloomPart<P, N>());
    }
 
    template<unsigned P, unsigned M>
    inline FixedHash<M> bloomPart() const
    {
        unsigned const c_bloomBits = M * 8;
        unsigned const c_mask = c_bloomBits - 1;
        unsigned const c_bloomBytes = (StaticLog2<c_bloomBits>::result + 7) / 8;
 
        static_assert((M & (M - 1)) == 0, "M must be power-of-two");
        static_assert(P * c_bloomBytes <= N, "out of range");
 
        FixedHash<M> ret;
        uint8_t const* p = data();
        for (unsigned i = 0; i < P; ++i) {
            unsigned index = 0;
            for (unsigned j = 0; j < c_bloomBytes; ++j, ++p)
                index = (index << 8) | *p;
            index &= c_mask;
            ret[M - 1 - index / 8] |= (1 << (index % 8));
        }
        return ret;
    }
 
    inline unsigned firstBitSet() const
    {
        unsigned ret = 0;
        for (auto d : m_data)
            if (d)
                for (;; ++ret, d <<= 1)
                    if (d & 0x80)
                        return ret;
                    else {
                    }
            else
                ret += 8;
        return ret;
    }
 
    void clear() { m_data.fill(0); }
 
private:
    std::array<uint8_t, N> m_data; 
};
 
template<unsigned T>
class SecureFixedHash : private FixedHash<T>
{
public:
    using ConstructFromHashType = typename FixedHash<T>::ConstructFromHashType;
    using ConstructFromStringType = typename FixedHash<T>::ConstructFromStringType;
    using ConstructFromPointerType = typename FixedHash<T>::ConstructFromPointerType;
    SecureFixedHash() = default;
    explicit SecureFixedHash(bytes const& _b, ConstructFromHashType _t = FixedHash<T>::FailIfDifferent)
        : FixedHash<T>(_b, _t)
    {}
    explicit SecureFixedHash(bytesConstRef _b, ConstructFromHashType _t = FixedHash<T>::FailIfDifferent)
        : FixedHash<T>(_b, _t)
    {}
    template<unsigned M>
    explicit SecureFixedHash(FixedHash<M> const& _h, ConstructFromHashType _t = FixedHash<T>::AlignLeft)
        : FixedHash<T>(_h, _t)
    {}
    SecureFixedHash(SecureFixedHash<T> const& _h)
        : FixedHash<T>(_h.makeInsecure())
    {}
    template<unsigned M>
    explicit SecureFixedHash(SecureFixedHash<M> const& _h, ConstructFromHashType _t = FixedHash<T>::AlignLeft)
        : FixedHash<T>(_h.makeInsecure(), _t)
    {}
    explicit SecureFixedHash(std::string const& _s,
                             ConstructFromStringType _t = FixedHash<T>::FromHex,
                             ConstructFromHashType _ht = FixedHash<T>::FailIfDifferent)
        : FixedHash<T>(_s, _t, _ht)
    {}
    explicit SecureFixedHash(bytes const* _d, ConstructFromPointerType _t)
        : FixedHash<T>(_d, _t)
    {}
    ~SecureFixedHash() { ref().cleanse(); }
 
    SecureFixedHash<T>& operator=(SecureFixedHash<T> const& _c)
    {
        if (&_c == this)
            return *this;
        ref().cleanse();
        FixedHash<T>::operator=(static_cast<FixedHash<T> const&>(_c));
        return *this;
    }
 
    using FixedHash<T>::size;
 
    FixedHash<T> const& makeInsecure() const { return static_cast<FixedHash<T> const&>(*this); }
    FixedHash<T>& writable()
    {
        clear();
        return static_cast<FixedHash<T>&>(*this);
    }
 
    using FixedHash<T>::operator bool;
 
    // The obvious comparison operators.
    bool operator==(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator==(static_cast<FixedHash<T> const&>(_c));
    }
    bool operator!=(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator!=(static_cast<FixedHash<T> const&>(_c));
    }
    bool operator<(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator<(static_cast<FixedHash<T> const&>(_c));
    }
    bool operator>=(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator>=(static_cast<FixedHash<T> const&>(_c));
    }
    bool operator<=(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator<=(static_cast<FixedHash<T> const&>(_c));
    }
    bool operator>(SecureFixedHash const& _c) const
    {
        return static_cast<FixedHash<T> const&>(*this).operator>(static_cast<FixedHash<T> const&>(_c));
    }
 
    using FixedHash<T>::operator==;
    using FixedHash<T>::operator!=;
    using FixedHash<T>::operator<;
    using FixedHash<T>::operator>=;
    using FixedHash<T>::operator<=;
    using FixedHash<T>::operator>;
 
    // The obvious binary operators.
    SecureFixedHash& operator^=(FixedHash<T> const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(_c);
        return *this;
    }
    SecureFixedHash operator^(FixedHash<T> const& _c) const { return SecureFixedHash(*this) ^= _c; }
    SecureFixedHash& operator|=(FixedHash<T> const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(_c);
        return *this;
    }
    SecureFixedHash operator|(FixedHash<T> const& _c) const { return SecureFixedHash(*this) |= _c; }
    SecureFixedHash& operator&=(FixedHash<T> const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(_c);
        return *this;
    }
    SecureFixedHash operator&(FixedHash<T> const& _c) const { return SecureFixedHash(*this) &= _c; }
 
    SecureFixedHash& operator^=(SecureFixedHash const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
        return *this;
    }
    SecureFixedHash operator^(SecureFixedHash const& _c) const { return SecureFixedHash(*this) ^= _c; }
    SecureFixedHash& operator|=(SecureFixedHash const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
        return *this;
    }
    SecureFixedHash operator|(SecureFixedHash const& _c) const { return SecureFixedHash(*this) |= _c; }
    SecureFixedHash& operator&=(SecureFixedHash const& _c)
    {
        static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
        return *this;
    }
    SecureFixedHash operator&(SecureFixedHash const& _c) const { return SecureFixedHash(*this) &= _c; }
    SecureFixedHash operator~() const
    {
        auto r = ~static_cast<FixedHash<T> const&>(*this);
        return static_cast<SecureFixedHash const&>(r);
    }
 
    using FixedHash<T>::abridged;
    using FixedHash<T>::abridgedMiddle;
 
    bytesConstRef ref() const { return FixedHash<T>::ref(); }
    uint8_t const* data() const { return FixedHash<T>::data(); }
 
    static SecureFixedHash<T> random()
    {
        SecureFixedHash<T> ret;
        std::random_device rd;
        ret.randomize(rd);
        return ret;
    }
    using FixedHash<T>::firstBitSet;
 
    void clear() { ref().cleanse(); }
};
 
template<>
inline bool
FixedHash<32>::operator==(FixedHash<32> const& _other) const
{
    const uint64_t* hash1 = (const uint64_t*) data();
    const uint64_t* hash2 = (const uint64_t*) _other.data();
    return (hash1[0] == hash2[0]) && (hash1[1] == hash2[1]) && (hash1[2] == hash2[2]) && (hash1[3] == hash2[3]);
}
 
// Common types of FixedHash.
using h2048 = FixedHash<256>;
using h1024 = FixedHash<128>;
using h520 = FixedHash<65>;
using h512 = FixedHash<64>;
using h256 = FixedHash<32>;
using h160 = FixedHash<20>;
using h128 = FixedHash<16>;
using h64 = FixedHash<8>;
using h512s = std::vector<h512>;
using h256s = std::vector<h256>;
using h160s = std::vector<h160>;
using h256Set = std::set<h256>;
using h160Set = std::set<h160>;
using h256Hash = std::unordered_set<h256>;
using h160Hash = std::unordered_set<h160>;
 
inline h160
right160(h256 const& _t)
{
    h160 ret;
    memcpy(ret.data(), _t.data() + 12, 20);
    return ret;
}
 
} // namespace dev