LCOV - code coverage report
Current view: top level - src/jamidht/eth/libdevcore - FixedHash.h (source / functions) Hit Total Coverage
Test: jami-coverage-filtered.info Lines: 41 64 64.1 %
Date: 2024-03-18 07:59:09 Functions: 26 32 81.2 %

          Line data    Source code
       1             : /*
       2             :     This file is part of cpp-ethereum.
       3             : 
       4             :     cpp-ethereum is free software: you can redistribute it and/or modify
       5             :     it under the terms of the GNU General Public License as published by
       6             :     the Free Software Foundation, either version 3 of the License, or
       7             :     (at your option) any later version.
       8             : 
       9             :     cpp-ethereum is distributed in the hope that it will be useful,
      10             :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :     GNU General Public License for more details.
      13             : 
      14             :     You should have received a copy of the GNU General Public License
      15             :     along with cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
      16             : */
      17             : /** @file FixedHash.h
      18             :  * @author Gav Wood <i@gavwood.com>
      19             :  * @date 2014
      20             :  *
      21             :  * The FixedHash fixed-size "hash" container type.
      22             :  */
      23             : 
      24             : #pragma once
      25             : 
      26             : #include <array>
      27             : #include <cstdint>
      28             : #include <algorithm>
      29             : #include <random>
      30             : #include <opendht/rng.h>
      31             : 
      32             : #include "CommonData.h"
      33             : 
      34             : namespace dev {
      35             : 
      36             : /// Compile-time calculation of Log2 of constant values.
      37             : template<unsigned N>
      38             : struct StaticLog2
      39             : {
      40             :     enum { result = 1 + StaticLog2<N / 2>::result };
      41             : };
      42             : template<>
      43             : struct StaticLog2<1>
      44             : {
      45             :     enum { result = 0 };
      46             : };
      47             : 
      48             : /// Fixed-size raw-byte array container type, with an API optimised for storing hashes.
      49             : /// Transparently converts to/from the corresponding arithmetic type; this will
      50             : /// assume the data contained in the hash is big-endian.
      51             : template<unsigned N>
      52             : class FixedHash
      53             : {
      54             : public:
      55             :     /// The size of the container.
      56             :     enum { size = N };
      57             : 
      58             :     /// A dummy flag to avoid accidental construction from pointer.
      59             :     enum ConstructFromPointerType { ConstructFromPointer };
      60             : 
      61             :     /// Method to convert from a string.
      62             :     enum ConstructFromStringType { FromHex, FromBinary };
      63             : 
      64             :     /// Method to convert from a string.
      65             :     enum ConstructFromHashType { AlignLeft, AlignRight, FailIfDifferent };
      66             : 
      67             :     /// Construct an empty hash.
      68        5289 :     FixedHash() { m_data.fill(0); }
      69             : 
      70             :     /// Construct from another hash, filling with zeroes or cropping as necessary.
      71             :     template<unsigned M>
      72             :     explicit FixedHash(FixedHash<M> const& _h, ConstructFromHashType _t = AlignLeft)
      73             :     {
      74             :         m_data.fill(0);
      75             :         unsigned c = std::min(M, N);
      76             :         for (unsigned i = 0; i < c; ++i)
      77             :             m_data[_t == AlignRight ? N - 1 - i : i] = _h[_t == AlignRight ? M - 1 - i : i];
      78             :     }
      79             : 
      80             :     /// Convert from unsigned
      81             :     explicit FixedHash(unsigned _u) { toBigEndian(_u, m_data); }
      82             : 
      83             :     /// Explicitly construct, copying from a byte array.
      84         775 :     explicit FixedHash(bytes const& _b, ConstructFromHashType _t = FailIfDifferent)
      85             :     {
      86         775 :         if (_b.size() == N)
      87         775 :             memcpy(m_data.data(), _b.data(), std::min<unsigned>(_b.size(), N));
      88             :         else {
      89           0 :             m_data.fill(0);
      90           0 :             if (_t != FailIfDifferent) {
      91           0 :                 auto c = std::min<unsigned>(_b.size(), N);
      92           0 :                 for (unsigned i = 0; i < c; ++i)
      93           0 :                     m_data[_t == AlignRight ? N - 1 - i : i]
      94           0 :                         = _b[_t == AlignRight ? _b.size() - 1 - i : i];
      95             :             }
      96             :         }
      97         775 :     }
      98             : 
      99             :     /// Explicitly construct, copying from a byte array.
     100             :     explicit FixedHash(bytesConstRef _b, ConstructFromHashType _t = FailIfDifferent)
     101             :     {
     102             :         if (_b.size() == N)
     103             :             memcpy(m_data.data(), _b.data(), std::min<unsigned>(_b.size(), N));
     104             :         else {
     105             :             m_data.fill(0);
     106             :             if (_t != FailIfDifferent) {
     107             :                 auto c = std::min<unsigned>(_b.size(), N);
     108             :                 for (unsigned i = 0; i < c; ++i)
     109             :                     m_data[_t == AlignRight ? N - 1 - i : i]
     110             :                         = _b[_t == AlignRight ? _b.size() - 1 - i : i];
     111             :             }
     112             :         }
     113             :     }
     114             : 
     115             :     /// Explicitly construct, copying from a bytes in memory with given pointer.
     116        1505 :     explicit FixedHash(uint8_t const* _bs, ConstructFromPointerType)
     117             :     {
     118        1505 :         memcpy(m_data.data(), _bs, N);
     119        1505 :     }
     120             : 
     121             :     /// Explicitly construct, copying from a  string.
     122           0 :     explicit FixedHash(std::string const& _s,
     123             :                        ConstructFromStringType _t = FromHex,
     124             :                        ConstructFromHashType _ht = FailIfDifferent)
     125           0 :         : FixedHash(_t == FromHex ? fromHex(_s, WhenError::Throw) : dev::asBytes(_s), _ht)
     126           0 :     {}
     127             : 
     128             :     /// @returns true iff this is the empty hash.
     129        2235 :     explicit operator bool() const
     130             :     {
     131        4479 :         return std::any_of(m_data.begin(), m_data.end(), [](uint8_t _b) { return _b != 0; });
     132             :     }
     133             : 
     134             :     // The obvious comparison operators.
     135             :     bool operator==(FixedHash const& _c) const { return m_data == _c.m_data; }
     136             :     bool operator!=(FixedHash const& _c) const { return m_data != _c.m_data; }
     137           0 :     bool operator<(FixedHash const& _c) const
     138             :     {
     139           0 :         for (unsigned i = 0; i < N; ++i)
     140           0 :             if (m_data[i] < _c.m_data[i])
     141           0 :                 return true;
     142           0 :             else if (m_data[i] > _c.m_data[i])
     143           0 :                 return false;
     144           0 :         return false;
     145             :     }
     146             :     bool operator>=(FixedHash const& _c) const { return !operator<(_c); }
     147           0 :     bool operator<=(FixedHash const& _c) const { return operator==(_c) || operator<(_c); }
     148           0 :     bool operator>(FixedHash const& _c) const { return !operator<=(_c); }
     149             : 
     150             :     // The obvious binary operators.
     151             :     FixedHash& operator^=(FixedHash const& _c)
     152             :     {
     153             :         for (unsigned i = 0; i < N; ++i)
     154             :             m_data[i] ^= _c.m_data[i];
     155             :         return *this;
     156             :     }
     157             :     FixedHash operator^(FixedHash const& _c) const { return FixedHash(*this) ^= _c; }
     158             :     FixedHash& operator|=(FixedHash const& _c)
     159             :     {
     160             :         for (unsigned i = 0; i < N; ++i)
     161             :             m_data[i] |= _c.m_data[i];
     162             :         return *this;
     163             :     }
     164             :     FixedHash operator|(FixedHash const& _c) const { return FixedHash(*this) |= _c; }
     165             :     FixedHash& operator&=(FixedHash const& _c)
     166             :     {
     167             :         for (unsigned i = 0; i < N; ++i)
     168             :             m_data[i] &= _c.m_data[i];
     169             :         return *this;
     170             :     }
     171             :     FixedHash operator&(FixedHash const& _c) const { return FixedHash(*this) &= _c; }
     172             :     FixedHash operator~() const
     173             :     {
     174             :         FixedHash ret;
     175             :         for (unsigned i = 0; i < N; ++i)
     176             :             ret[i] = ~m_data[i];
     177             :         return ret;
     178             :     }
     179             : 
     180             :     // Big-endian increment.
     181             :     FixedHash& operator++()
     182             :     {
     183             :         for (unsigned i = size; i > 0 && !++m_data[--i];) {
     184             :         }
     185             :         return *this;
     186             :     }
     187             : 
     188             :     /// @returns true if all one-bits in @a _c are set in this object.
     189             :     bool contains(FixedHash const& _c) const { return (*this & _c) == _c; }
     190             : 
     191             :     /// @returns a particular byte from the hash.
     192             :     uint8_t& operator[](unsigned _i) { return m_data[_i]; }
     193             :     /// @returns a particular byte from the hash.
     194             :     uint8_t operator[](unsigned _i) const { return m_data[_i]; }
     195             : 
     196             :     /// @returns an abridged version of the hash as a user-readable hex string.
     197             :     std::string abridged() const { return toHex(ref().cropped(0, 4)) + "\342\200\246"; }
     198             : 
     199             :     /// @returns a version of the hash as a user-readable hex string that leaves out the middle part.
     200             :     std::string abridgedMiddle() const
     201             :     {
     202             :         return toHex(ref().cropped(0, 4)) + "\342\200\246" + toHex(ref().cropped(N - 4));
     203             :     }
     204             : 
     205             :     /// @returns the hash as a user-readable hex string.
     206        1550 :     std::string hex() const { return toHex(ref()); }
     207             : 
     208             :     /// @returns a mutable byte vector_ref to the object's data.
     209        1549 :     bytesRef ref() { return bytesRef(m_data.data(), N); }
     210             : 
     211             :     /// @returns a constant byte vector_ref to the object's data.
     212        7480 :     bytesConstRef ref() const { return bytesConstRef(m_data.data(), N); }
     213             : 
     214             :     /// @returns a mutable byte pointer to the object's data.
     215        1505 :     uint8_t* data() { return m_data.data(); }
     216             : 
     217             :     /// @returns a constant byte pointer to the object's data.
     218        4470 :     uint8_t const* data() const { return m_data.data(); }
     219             : 
     220             :     /// @returns begin iterator.
     221             :     auto begin() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.begin(); }
     222             : 
     223             :     /// @returns end iterator.
     224             :     auto end() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.end(); }
     225             : 
     226             :     /// @returns a copy of the object's data as a byte vector.
     227         730 :     bytes asBytes() const { return bytes(data(), data() + N); }
     228             : 
     229             :     /// @returns a mutable reference to the object's data as an STL array.
     230             :     std::array<uint8_t, N>& asArray() { return m_data; }
     231             : 
     232             :     /// @returns a constant reference to the object's data as an STL array.
     233             :     std::array<uint8_t, N> const& asArray() const { return m_data; }
     234             : 
     235             :     /// Populate with random data.
     236             :     template<class Engine>
     237         730 :     void randomize(Engine& _eng)
     238             :     {
     239       24090 :         for (auto& i : m_data)
     240       23360 :             i = (uint8_t) std::uniform_int_distribution<uint16_t>(0, 255)(_eng);
     241         730 :     }
     242             : 
     243             :     /// @returns a random valued object.
     244             :     static FixedHash random()
     245             :     {
     246             :         FixedHash ret;
     247             :         std::random_device rd;
     248             :         ret.randomize(rd);
     249             :         return ret;
     250             :     }
     251             : 
     252             :     template<unsigned P, unsigned M>
     253             :     inline FixedHash& shiftBloom(FixedHash<M> const& _h)
     254             :     {
     255             :         return (*this |= _h.template bloomPart<P, N>());
     256             :     }
     257             : 
     258             :     template<unsigned P, unsigned M>
     259             :     inline bool containsBloom(FixedHash<M> const& _h)
     260             :     {
     261             :         return contains(_h.template bloomPart<P, N>());
     262             :     }
     263             : 
     264             :     template<unsigned P, unsigned M>
     265             :     inline FixedHash<M> bloomPart() const
     266             :     {
     267             :         unsigned const c_bloomBits = M * 8;
     268             :         unsigned const c_mask = c_bloomBits - 1;
     269             :         unsigned const c_bloomBytes = (StaticLog2<c_bloomBits>::result + 7) / 8;
     270             : 
     271             :         static_assert((M & (M - 1)) == 0, "M must be power-of-two");
     272             :         static_assert(P * c_bloomBytes <= N, "out of range");
     273             : 
     274             :         FixedHash<M> ret;
     275             :         uint8_t const* p = data();
     276             :         for (unsigned i = 0; i < P; ++i) {
     277             :             unsigned index = 0;
     278             :             for (unsigned j = 0; j < c_bloomBytes; ++j, ++p)
     279             :                 index = (index << 8) | *p;
     280             :             index &= c_mask;
     281             :             ret[M - 1 - index / 8] |= (1 << (index % 8));
     282             :         }
     283             :         return ret;
     284             :     }
     285             : 
     286             :     /// Returns the index of the first bit set to one, or size() * 8 if no bits are set.
     287             :     inline unsigned firstBitSet() const
     288             :     {
     289             :         unsigned ret = 0;
     290             :         for (auto d : m_data)
     291             :             if (d)
     292             :                 for (;; ++ret, d <<= 1)
     293             :                     if (d & 0x80)
     294             :                         return ret;
     295             :                     else {
     296             :                     }
     297             :             else
     298             :                 ret += 8;
     299             :         return ret;
     300             :     }
     301             : 
     302             :     void clear() { m_data.fill(0); }
     303             : 
     304             : private:
     305             :     std::array<uint8_t, N> m_data; ///< The binary data.
     306             : };
     307             : 
     308             : template<unsigned T>
     309             : class SecureFixedHash : private FixedHash<T>
     310             : {
     311             : public:
     312             :     using ConstructFromHashType = typename FixedHash<T>::ConstructFromHashType;
     313             :     using ConstructFromStringType = typename FixedHash<T>::ConstructFromStringType;
     314             :     using ConstructFromPointerType = typename FixedHash<T>::ConstructFromPointerType;
     315         730 :     SecureFixedHash() = default;
     316         775 :     explicit SecureFixedHash(bytes const& _b,
     317             :                              ConstructFromHashType _t = FixedHash<T>::FailIfDifferent)
     318         775 :         : FixedHash<T>(_b, _t)
     319         775 :     {}
     320             :     explicit SecureFixedHash(bytesConstRef _b,
     321             :                              ConstructFromHashType _t = FixedHash<T>::FailIfDifferent)
     322             :         : FixedHash<T>(_b, _t)
     323             :     {}
     324             :     template<unsigned M>
     325             :     explicit SecureFixedHash(FixedHash<M> const& _h,
     326             :                              ConstructFromHashType _t = FixedHash<T>::AlignLeft)
     327             :         : FixedHash<T>(_h, _t)
     328             :     {}
     329        3695 :     SecureFixedHash(SecureFixedHash<T> const& _h)
     330        3695 :         : FixedHash<T>(_h.makeInsecure())
     331        3695 :     {}
     332             :     template<unsigned M>
     333             :     explicit SecureFixedHash(SecureFixedHash<M> const& _h,
     334             :                              ConstructFromHashType _t = FixedHash<T>::AlignLeft)
     335             :         : FixedHash<T>(_h.makeInsecure(), _t)
     336             :     {}
     337             :     explicit SecureFixedHash(std::string const& _s,
     338             :                              ConstructFromStringType _t = FixedHash<T>::FromHex,
     339             :                              ConstructFromHashType _ht = FixedHash<T>::FailIfDifferent)
     340             :         : FixedHash<T>(_s, _t, _ht)
     341             :     {}
     342             :     explicit SecureFixedHash(bytes const* _d, ConstructFromPointerType _t)
     343             :         : FixedHash<T>(_d, _t)
     344             :     {}
     345        5200 :     ~SecureFixedHash() { ref().cleanse(); }
     346             : 
     347             :     SecureFixedHash<T>& operator=(SecureFixedHash<T> const& _c)
     348             :     {
     349             :         if (&_c == this)
     350             :             return *this;
     351             :         ref().cleanse();
     352             :         FixedHash<T>::operator=(static_cast<FixedHash<T> const&>(_c));
     353             :         return *this;
     354             :     }
     355             : 
     356             :     using FixedHash<T>::size;
     357             : 
     358        4425 :     FixedHash<T> const& makeInsecure() const { return static_cast<FixedHash<T> const&>(*this); }
     359             :     FixedHash<T>& writable()
     360             :     {
     361             :         clear();
     362             :         return static_cast<FixedHash<T>&>(*this);
     363             :     }
     364             : 
     365             :     using FixedHash<T>::operator bool;
     366             : 
     367             :     // The obvious comparison operators.
     368             :     bool operator==(SecureFixedHash const& _c) const
     369             :     {
     370             :         return static_cast<FixedHash<T> const&>(*this).operator==(
     371             :             static_cast<FixedHash<T> const&>(_c));
     372             :     }
     373             :     bool operator!=(SecureFixedHash const& _c) const
     374             :     {
     375             :         return static_cast<FixedHash<T> const&>(*this).operator!=(
     376             :             static_cast<FixedHash<T> const&>(_c));
     377             :     }
     378             :     bool operator<(SecureFixedHash const& _c) const
     379             :     {
     380             :         return static_cast<FixedHash<T> const&>(*this).operator<(
     381             :             static_cast<FixedHash<T> const&>(_c));
     382             :     }
     383             :     bool operator>=(SecureFixedHash const& _c) const
     384             :     {
     385             :         return static_cast<FixedHash<T> const&>(*this).operator>=(
     386             :             static_cast<FixedHash<T> const&>(_c));
     387             :     }
     388             :     bool operator<=(SecureFixedHash const& _c) const
     389             :     {
     390             :         return static_cast<FixedHash<T> const&>(*this).operator<=(
     391             :             static_cast<FixedHash<T> const&>(_c));
     392             :     }
     393             :     bool operator>(SecureFixedHash const& _c) const
     394             :     {
     395             :         return static_cast<FixedHash<T> const&>(*this).operator>(
     396             :             static_cast<FixedHash<T> const&>(_c));
     397             :     }
     398             : 
     399             :     using FixedHash<T>::operator==;
     400             :     using FixedHash<T>::operator!=;
     401             :     using FixedHash<T>::operator<;
     402             :     using FixedHash<T>::operator>=;
     403             :     using FixedHash<T>::operator<=;
     404             :     using FixedHash<T>::operator>;
     405             : 
     406             :     // The obvious binary operators.
     407             :     SecureFixedHash& operator^=(FixedHash<T> const& _c)
     408             :     {
     409             :         static_cast<FixedHash<T>&>(*this).operator^=(_c);
     410             :         return *this;
     411             :     }
     412             :     SecureFixedHash operator^(FixedHash<T> const& _c) const { return SecureFixedHash(*this) ^= _c; }
     413             :     SecureFixedHash& operator|=(FixedHash<T> const& _c)
     414             :     {
     415             :         static_cast<FixedHash<T>&>(*this).operator^=(_c);
     416             :         return *this;
     417             :     }
     418             :     SecureFixedHash operator|(FixedHash<T> const& _c) const { return SecureFixedHash(*this) |= _c; }
     419             :     SecureFixedHash& operator&=(FixedHash<T> const& _c)
     420             :     {
     421             :         static_cast<FixedHash<T>&>(*this).operator^=(_c);
     422             :         return *this;
     423             :     }
     424             :     SecureFixedHash operator&(FixedHash<T> const& _c) const { return SecureFixedHash(*this) &= _c; }
     425             : 
     426             :     SecureFixedHash& operator^=(SecureFixedHash const& _c)
     427             :     {
     428             :         static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
     429             :         return *this;
     430             :     }
     431             :     SecureFixedHash operator^(SecureFixedHash const& _c) const
     432             :     {
     433             :         return SecureFixedHash(*this) ^= _c;
     434             :     }
     435             :     SecureFixedHash& operator|=(SecureFixedHash const& _c)
     436             :     {
     437             :         static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
     438             :         return *this;
     439             :     }
     440             :     SecureFixedHash operator|(SecureFixedHash const& _c) const
     441             :     {
     442             :         return SecureFixedHash(*this) |= _c;
     443             :     }
     444             :     SecureFixedHash& operator&=(SecureFixedHash const& _c)
     445             :     {
     446             :         static_cast<FixedHash<T>&>(*this).operator^=(static_cast<FixedHash<T> const&>(_c));
     447             :         return *this;
     448             :     }
     449             :     SecureFixedHash operator&(SecureFixedHash const& _c) const
     450             :     {
     451             :         return SecureFixedHash(*this) &= _c;
     452             :     }
     453             :     SecureFixedHash operator~() const
     454             :     {
     455             :         auto r = ~static_cast<FixedHash<T> const&>(*this);
     456             :         return static_cast<SecureFixedHash const&>(r);
     457             :     }
     458             : 
     459             :     using FixedHash<T>::abridged;
     460             :     using FixedHash<T>::abridgedMiddle;
     461             : 
     462        5200 :     bytesConstRef ref() const { return FixedHash<T>::ref(); }
     463        1505 :     uint8_t const* data() const { return FixedHash<T>::data(); }
     464             : 
     465         730 :     static SecureFixedHash<T> random()
     466             :     {
     467         730 :         SecureFixedHash<T> ret;
     468         730 :         std::random_device rd;
     469         730 :         ret.randomize(rd);
     470        1460 :         return ret;
     471         730 :     }
     472             :     using FixedHash<T>::firstBitSet;
     473             : 
     474             :     void clear() { ref().cleanse(); }
     475             : };
     476             : 
     477             : /// Fast equality operator for h256.
     478             : template<>
     479             : inline bool
     480           0 : FixedHash<32>::operator==(FixedHash<32> const& _other) const
     481             : {
     482           0 :     const uint64_t* hash1 = (const uint64_t*) data();
     483           0 :     const uint64_t* hash2 = (const uint64_t*) _other.data();
     484           0 :     return (hash1[0] == hash2[0]) && (hash1[1] == hash2[1]) && (hash1[2] == hash2[2])
     485           0 :            && (hash1[3] == hash2[3]);
     486             : }
     487             : 
     488             : // Common types of FixedHash.
     489             : using h2048 = FixedHash<256>;
     490             : using h1024 = FixedHash<128>;
     491             : using h520 = FixedHash<65>;
     492             : using h512 = FixedHash<64>;
     493             : using h256 = FixedHash<32>;
     494             : using h160 = FixedHash<20>;
     495             : using h128 = FixedHash<16>;
     496             : using h64 = FixedHash<8>;
     497             : using h512s = std::vector<h512>;
     498             : using h256s = std::vector<h256>;
     499             : using h160s = std::vector<h160>;
     500             : using h256Set = std::set<h256>;
     501             : using h160Set = std::set<h160>;
     502             : using h256Hash = std::unordered_set<h256>;
     503             : using h160Hash = std::unordered_set<h160>;
     504             : 
     505             : /// Convert the given value into h160 (160-bit unsigned integer) using the right 20 bytes.
     506             : inline h160
     507        1505 : right160(h256 const& _t)
     508             : {
     509        1505 :     h160 ret;
     510        1505 :     memcpy(ret.data(), _t.data() + 12, 20);
     511        1505 :     return ret;
     512             : }
     513             : 
     514             : } // namespace dev

Generated by: LCOV version 1.14