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 5352 : 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 784 : explicit FixedHash(bytes const& _b, ConstructFromHashType _t = FailIfDifferent)
85 : {
86 784 : if (_b.size() == N)
87 784 : 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 784 : }
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 1523 : explicit FixedHash(uint8_t const* _bs, ConstructFromPointerType)
117 : {
118 1523 : memcpy(m_data.data(), _bs, N);
119 1523 : }
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 2262 : explicit operator bool() const
130 : {
131 4535 : 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 1568 : std::string hex() const { return toHex(ref()); }
207 :
208 : /// @returns a mutable byte vector_ref to the object's data.
209 1567 : bytesRef ref() { return bytesRef(m_data.data(), N); }
210 :
211 : /// @returns a constant byte vector_ref to the object's data.
212 6092 : bytesConstRef ref() const { return bytesConstRef(m_data.data(), N); }
213 :
214 : /// @returns a mutable byte pointer to the object's data.
215 1523 : uint8_t* data() { return m_data.data(); }
216 :
217 : /// @returns a constant byte pointer to the object's data.
218 4524 : 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 739 : 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 739 : void randomize(Engine& _eng)
238 : {
239 24387 : for (auto& i : m_data)
240 23648 : i = (uint8_t) std::uniform_int_distribution<uint16_t>(0, 255)(_eng);
241 739 : }
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 739 : SecureFixedHash() = default;
316 784 : explicit SecureFixedHash(bytes const& _b,
317 : ConstructFromHashType _t = FixedHash<T>::FailIfDifferent)
318 784 : : FixedHash<T>(_b, _t)
319 784 : {}
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 2262 : SecureFixedHash(SecureFixedHash<T> const& _h)
330 2262 : : FixedHash<T>(_h.makeInsecure())
331 2262 : {}
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 3785 : ~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 3001 : 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 3785 : bytesConstRef ref() const { return FixedHash<T>::ref(); }
463 1523 : uint8_t const* data() const { return FixedHash<T>::data(); }
464 :
465 739 : static SecureFixedHash<T> random()
466 : {
467 739 : SecureFixedHash<T> ret;
468 739 : std::random_device rd;
469 739 : ret.randomize(rd);
470 1478 : return ret;
471 739 : }
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 1523 : right160(h256 const& _t)
508 : {
509 1523 : h160 ret;
510 1523 : memcpy(ret.data(), _t.data() + 12, 20);
511 1523 : return ret;
512 : }
513 :
514 : } // namespace dev
|
