FixedHash.h 15.3 KB
Newer Older
Adrien Béraud's avatar
Adrien Béraud committed
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
/*
	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/>.
*/
/** @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>
29 30
#include <random>
#include <sstream>
Adrien Béraud's avatar
Adrien Béraud committed
31 32
#include <opendht/rng.h>

Adrien Béraud's avatar
Adrien Béraud committed
33 34 35 36 37 38 39 40 41
#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 }; };

Adrien Béraud's avatar
Adrien Béraud committed
42
extern dht::crypto::random_device s_fixedHashEngine;
Adrien Béraud's avatar
Adrien Béraud committed
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

/// 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 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 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.
Adrien Béraud's avatar
Adrien Béraud committed
79
	explicit FixedHash(uint8_t const* _bs, ConstructFromPointerType) { memcpy(m_data.data(), _bs, N); }
Adrien Béraud's avatar
Adrien Béraud committed
80 81 82 83 84

	/// 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) {}

	/// @returns true iff this is the empty hash.
Adrien Béraud's avatar
Adrien Béraud committed
85
	explicit operator bool() const { return std::any_of(m_data.begin(), m_data.end(), [](uint8_t _b) { return _b != 0; }); }
Adrien Béraud's avatar
Adrien Béraud committed
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

	// 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.
Adrien Béraud's avatar
Adrien Béraud committed
111
	uint8_t& operator[](unsigned _i) { return m_data[_i]; }
Adrien Béraud's avatar
Adrien Béraud committed
112
	/// @returns a particular byte from the hash.
Adrien Béraud's avatar
Adrien Béraud committed
113
	uint8_t operator[](unsigned _i) const { return m_data[_i]; }
Adrien Béraud's avatar
Adrien Béraud committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130

	/// @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.
Adrien Béraud's avatar
Adrien Béraud committed
131
	uint8_t* data() { return m_data.data(); }
Adrien Béraud's avatar
Adrien Béraud committed
132 133

	/// @returns a constant byte pointer to the object's data.
Adrien Béraud's avatar
Adrien Béraud committed
134
	uint8_t const* data() const { return m_data.data(); }
Adrien Béraud's avatar
Adrien Béraud committed
135

136
	/// @returns begin iterator.
Adrien Béraud's avatar
Adrien Béraud committed
137
	auto begin() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.begin(); }
138 139

	/// @returns end iterator.
Adrien Béraud's avatar
Adrien Béraud committed
140
	auto end() const -> typename std::array<uint8_t, N>::const_iterator { return m_data.end(); }
141

Adrien Béraud's avatar
Adrien Béraud committed
142 143 144 145
	/// @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.
Adrien Béraud's avatar
Adrien Béraud committed
146
	std::array<uint8_t, N>& asArray() { return m_data; }
Adrien Béraud's avatar
Adrien Béraud committed
147 148

	/// @returns a constant reference to the object's data as an STL array.
Adrien Béraud's avatar
Adrien Béraud committed
149
	std::array<uint8_t, N> const& asArray() const { return m_data; }
Adrien Béraud's avatar
Adrien Béraud committed
150 151 152 153 154 155

	/// Populate with random data.
	template <class Engine>
	void randomize(Engine& _eng)
	{
		for (auto& i: m_data)
156
			i = (uint8_t)std::uniform_int_distribution<uint16_t>(0, 255)(_eng);
Adrien Béraud's avatar
Adrien Béraud committed
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
	}

	/// @returns a random valued object.
	static FixedHash random() { FixedHash ret; ret.randomize(s_fixedHashEngine); 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;
Adrien Béraud's avatar
Adrien Béraud committed
182
		uint8_t const* p = data();
Adrien Béraud's avatar
Adrien Béraud committed
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
		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:
Adrien Béraud's avatar
Adrien Béraud committed
212
	std::array<uint8_t, N> m_data;		///< The binary data.
Adrien Béraud's avatar
Adrien Béraud committed
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
};

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) {}
	explicit SecureFixedHash(bytesSec const& _b, ConstructFromHashType _t = FixedHash<T>::FailIfDifferent): FixedHash<T>(_b.ref(), _t) {}
	template <unsigned M> explicit SecureFixedHash(FixedHash<M> const& _h, ConstructFromHashType _t = FixedHash<T>::AlignLeft): FixedHash<T>(_h, _t) {}
	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;

	bytesSec asBytesSec() const { return bytesSec(ref()); }

	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(); }
Adrien Béraud's avatar
Adrien Béraud committed
285
	uint8_t const* data() const { return FixedHash<T>::data(); }
Adrien Béraud's avatar
Adrien Béraud committed
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304

	static SecureFixedHash<T> random() { SecureFixedHash<T> ret; ret.randomize(s_fixedHashEngine); return ret; }
	using FixedHash<T>::firstBitSet;

	void clear() { ref().cleanse(); }
};

/// 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]);
}

/// Stream I/O for the FixedHash class.
template <unsigned N>
inline std::ostream& operator<<(std::ostream& _out, FixedHash<N> const& _h)
{
305
	_out << toHex(_h);
Adrien Béraud's avatar
Adrien Béraud committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
	return _out;
}

/// Stream I/O for the SecureFixedHash class.
template <unsigned N>
inline std::ostream& operator<<(std::ostream& _out, SecureFixedHash<N> const& _h)
{
	_out << "SecureFixedHash#" << std::hex << typename FixedHash<N>::hash()(_h.makeInsecure()) << 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;
}

inline std::string toString(h256s const& _bs)
{
	std::ostringstream out;
	out << "[ ";
346
	for (h256 const& i: _bs)
Adrien Béraud's avatar
Adrien Béraud committed
347 348 349 350 351 352
		out << i.abridged() << ", ";
	out << "]";
	return out.str();
}

}