aboutsummaryrefslogtreecommitdiffstats
path: root/libdevcore/FixedHash.h
blob: 5b1c7acf5e6320b4bec83cd8cac9e95ca7b0e866 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
/*
    This file is part of solidity.

    solidity 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.

    solidity 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 solidity.  If not, see <http://www.gnu.org/licenses/>.
*/
/** @file FixedHash.h
 * @author Gav Wood <i@gavwood.com>
 * @date 2014
 *
 * The FixedHash fixed-size "hash" container type.
 */

#pragma once

#include <array>
#include <cstdint>
#include <algorithm>
#include <boost/functional/hash.hpp>
#include "CommonData.h"

namespace dev
{

/// Compile-time calculation of Log2 of constant values.
template <unsigned N> struct StaticLog2 { enum { result = 1 + StaticLog2<N/2>::result }; };
template <> struct StaticLog2<1> { enum { result = 0 }; };

/// Fixed-size raw-byte array container type, with an API optimised for storing hashes.
/// Transparently converts to/from the corresponding arithmetic type; this will
/// assume the data contained in the hash is big-endian.
template <unsigned N>
class FixedHash
{
public:
    /// The corresponding arithmetic type.
    using Arith = boost::multiprecision::number<boost::multiprecision::cpp_int_backend<N * 8, N * 8, boost::multiprecision::unsigned_magnitude, boost::multiprecision::unchecked, void>>;

    /// The size of the container.
    enum { size = N };

    /// A dummy flag to avoid accidental construction from pointer.
    enum ConstructFromPointerType { ConstructFromPointer };

    /// Method to convert from a string.
    enum ConstructFromStringType { FromHex, FromBinary };

    /// Method to convert from a string.
    enum ConstructFromHashType { AlignLeft, AlignRight, FailIfDifferent };

    /// Construct an empty hash.
    FixedHash() { m_data.fill(0); }

    /// Construct from another hash, filling with zeroes or cropping as necessary.
    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]; }

    /// Convert from the corresponding arithmetic type.
    FixedHash(Arith const& _arith) { toBigEndian(_arith, m_data); }

    /// Convert from unsigned
    explicit FixedHash(unsigned _u) { toBigEndian(_u, m_data); }

    /// Explicitly construct, copying from a byte array.
    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]; } } }

    /// Explicitly construct, copying from a byte array.
    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]; } } }

    /// Explicitly construct, copying from a bytes in memory with given pointer.
    explicit FixedHash(byte const* _bs, ConstructFromPointerType) { memcpy(m_data.data(), _bs, N); }

    /// Explicitly construct, copying from a  string.
    explicit FixedHash(std::string const& _s, ConstructFromStringType _t = FromHex, ConstructFromHashType _ht = FailIfDifferent): FixedHash(_t == FromHex ? fromHex(_s, WhenError::Throw) : dev::asBytes(_s), _ht) {}

    /// Convert to arithmetic type.
    operator Arith() const { return fromBigEndian<Arith>(m_data); }

    /// @returns true iff this is the empty hash.
    explicit operator bool() const { return std::any_of(m_data.begin(), m_data.end(), [](byte _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; }

    /// @returns true if all one-bits in @a _c are set in this object.
    bool contains(FixedHash const& _c) const { return (*this & _c) == _c; }

    /// @returns a particular byte from the hash.
    byte& operator[](unsigned _i) { return m_data[_i]; }
    /// @returns a particular byte from the hash.
    byte operator[](unsigned _i) const { return m_data[_i]; }

    /// @returns an abridged version of the hash as a user-readable hex string.
    std::string abridged() const { return toHex(ref().cropped(0, 4)) + "\342\200\246"; }

    /// @returns a version of the hash as a user-readable hex string that leaves out the middle part.
    std::string abridgedMiddle() const { return toHex(ref().cropped(0, 4)) + "\342\200\246" + toHex(ref().cropped(N - 4)); }

    /// @returns the hash as a user-readable hex string.
    std::string hex() const { return toHex(ref()); }

    /// @returns a mutable byte vector_ref to the object's data.
    bytesRef ref() { return bytesRef(m_data.data(), N); }

    /// @returns a constant byte vector_ref to the object's data.
    bytesConstRef ref() const { return bytesConstRef(m_data.data(), N); }

    /// @returns a mutable byte pointer to the object's data.
    byte* data() { return m_data.data(); }

    /// @returns a constant byte pointer to the object's data.
    byte const* data() const { return m_data.data(); }

    /// @returns a copy of the object's data as a byte vector.
    bytes asBytes() const { return bytes(data(), data() + N); }

    /// @returns a mutable reference to the object's data as an STL array.
    std::array<byte, N>& asArray() { return m_data; }

    /// @returns a constant reference to the object's data as an STL array.
    std::array<byte, N> const& asArray() const { return m_data; }

    struct hash
    {
        /// Make a hash of the object's data.
        size_t operator()(FixedHash const& _value) const { return boost::hash_range(_value.m_data.cbegin(), _value.m_data.cend()); }
    };

    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;
        byte 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;
    }

    /// Returns the index of the first bit set to one, or size() * 8 if no bits are set.
    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<byte, N> m_data;     ///< The binary data.
};

/// Fast equality operator for h256.
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]);
}

/// Fast std::hash compatible hash function object for h256.
template<> inline size_t FixedHash<32>::hash::operator()(FixedHash<32> const& value) const
{
    uint64_t const* data = reinterpret_cast<uint64_t const*>(value.data());
    return boost::hash_range(data, data + 4);
}

/// Stream I/O for the FixedHash class.
template <unsigned N>
inline std::ostream& operator<<(std::ostream& _out, FixedHash<N> const& _h)
{
    _out << std::noshowbase << std::hex << std::setfill('0');
    for (unsigned i = 0; i < N; ++i)
        _out << std::setw(2) << (int)_h[i];
    _out << std::dec;
    return _out;
}

// 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>;

/// Convert the given value into h160 (160-bit unsigned integer) using the right 20 bytes.
inline h160 right160(h256 const& _t)
{
    h160 ret;
    memcpy(ret.data(), _t.data() + 12, 20);
    return ret;
}

/// Convert the given value into h160 (160-bit unsigned integer) using the left 20 bytes.
inline h160 left160(h256 const& _t)
{
    h160 ret;
    memcpy(&ret[0], _t.data(), 20);
    return ret;
}

inline std::string toString(h256s const& _bs)
{
    std::ostringstream out;
    out << "[ ";
    for (auto i: _bs)
        out << i.abridged() << ", ";
    out << "]";
    return out.str();
}

}

namespace std
{
    /// Forward std::hash<dev::FixedHash> to dev::FixedHash::hash.
    template<> struct hash<dev::h64>: dev::h64::hash {};
    template<> struct hash<dev::h128>: dev::h128::hash {};
    template<> struct hash<dev::h160>: dev::h160::hash {};
    template<> struct hash<dev::h256>: dev::h256::hash {};
    template<> struct hash<dev::h512>: dev::h512::hash {};
}