1 // Aleth: Ethereum C++ client, tools and libraries. 2 // Copyright 2013-2019 Aleth Authors. 3 // Licensed under the GNU General Public License, Version 3. 4 5 /// @file 6 /// Recursive Linear-Prefix serialization / deserialization. 7 #pragma once 8 9 #include "Exceptions.h" 10 #include "FixedHash.h" 11 #include "vector_ref.h" 12 13 #include <array> 14 #include <exception> 15 #include <iomanip> 16 #include <iosfwd> 17 #include <vector> 18 19 namespace dev 20 { 21 22 class RLP; 23 24 template <class _T> struct intTraits { static const unsigned maxSize = sizeof(_T); }; 25 template <> struct intTraits<u160> { static const unsigned maxSize = 20; }; 26 template <> struct intTraits<u256> { static const unsigned maxSize = 32; }; 27 template <> struct intTraits<bigint> { static const unsigned maxSize = ~(unsigned)0; }; 28 29 static const byte c_rlpMaxLengthBytes = 8; 30 static const byte c_rlpDataImmLenStart = 0x80; 31 static const byte c_rlpListStart = 0xc0; 32 33 static const byte c_rlpDataImmLenCount = c_rlpListStart - c_rlpDataImmLenStart - c_rlpMaxLengthBytes; 34 static const byte c_rlpDataIndLenZero = c_rlpDataImmLenStart + c_rlpDataImmLenCount - 1; 35 static const byte c_rlpListImmLenCount = 256 - c_rlpListStart - c_rlpMaxLengthBytes; 36 static const byte c_rlpListIndLenZero = c_rlpListStart + c_rlpListImmLenCount - 1; 37 38 template <class T> struct Converter { static T convert(RLP const&, int) { BOOST_THROW_EXCEPTION(BadCast()); } }; 39 40 /** 41 * Class for interpreting Recursive Linear-Prefix Data. 42 */ 43 class RLP 44 { 45 public: 46 /// Conversion flags 47 enum 48 { 49 AllowNonCanon = 1, 50 ThrowOnFail = 4, 51 FailIfTooBig = 8, 52 FailIfTooSmall = 16, 53 Strict = ThrowOnFail | FailIfTooBig, 54 VeryStrict = ThrowOnFail | FailIfTooBig | FailIfTooSmall, 55 LaissezFaire = AllowNonCanon 56 }; 57 58 using Strictness = int; 59 60 /// Construct a null node. 61 RLP() {} 62 63 /// Construct a node of value given in the bytes. 64 explicit RLP(bytesConstRef _d, Strictness _s = VeryStrict); 65 66 /// Construct a node of value given in the bytes. 67 explicit RLP(bytes const& _d, Strictness _s = VeryStrict): RLP(&_d, _s) {} 68 69 /// Construct a node to read RLP data in the bytes given. 70 RLP(byte const* _b, unsigned _s, Strictness _st = VeryStrict): RLP(bytesConstRef(_b, _s), _st) {} 71 72 /// Construct a node to read RLP data in the string. 73 explicit RLP(std::string const& _s, Strictness _st = VeryStrict): RLP(bytesConstRef((byte const*)_s.data(), _s.size()), _st) {} 74 75 /// The bare data of the RLP. 76 bytesConstRef data() const { return m_data; } 77 78 /// @returns true if the RLP is non-null. 79 explicit operator bool() const { return !isNull(); } 80 81 /// No value. 82 bool isNull() const { return m_data.size() == 0; } 83 84 /// Contains a zero-length string or zero-length list. 85 bool isEmpty() const { return !isNull() && (m_data[0] == c_rlpDataImmLenStart || m_data[0] == c_rlpListStart); } 86 87 /// String value. 88 bool isData() const { return !isNull() && m_data[0] < c_rlpListStart; } 89 90 /// List value. 91 bool isList() const { return !isNull() && m_data[0] >= c_rlpListStart; } 92 93 /// Integer value. Must not have a leading zero. 94 bool isInt() const; 95 96 /// @returns the number of items in the list, or zero if it isn't a list. 97 size_t itemCount() const { return isList() ? items() : 0; } 98 size_t itemCountStrict() const { if (!isList()) BOOST_THROW_EXCEPTION(BadCast()); return items(); } 99 100 /// @returns the number of bytes in the data, or zero if it isn't data. 101 size_t size() const { return isData() ? length() : 0; } 102 size_t sizeStrict() const { if (!isData()) BOOST_THROW_EXCEPTION(BadCast()); return length(); } 103 104 /// Equality operators; does best-effort conversion and checks for equality. 105 bool operator==(char const* _s) const { return isData() && toString() == _s; } 106 bool operator!=(char const* _s) const { return isData() && toString() != _s; } 107 bool operator==(std::string const& _s) const { return isData() && toString() == _s; } 108 bool operator!=(std::string const& _s) const { return isData() && toString() != _s; } 109 template <unsigned _N> bool operator==(FixedHash<_N> const& _h) const { return isData() && toHash<_N>() == _h; } 110 template <unsigned _N> bool operator!=(FixedHash<_N> const& _s) const { return isData() && toHash<_N>() != _s; } 111 bool operator==(unsigned const& _i) const { return isInt() && toInt<unsigned>() == _i; } 112 bool operator!=(unsigned const& _i) const { return isInt() && toInt<unsigned>() != _i; } 113 bool operator==(u256 const& _i) const { return isInt() && toInt<u256>() == _i; } 114 bool operator!=(u256 const& _i) const { return isInt() && toInt<u256>() != _i; } 115 bool operator==(bigint const& _i) const { return isInt() && toInt<bigint>() == _i; } 116 bool operator!=(bigint const& _i) const { return isInt() && toInt<bigint>() != _i; } 117 118 /// Subscript operator. 119 /// @returns the list item @a _i if isList() and @a _i < listItems(), or RLP() otherwise. 120 /// @note if used to access items in ascending order, this is efficient. 121 RLP operator[](size_t _i) const; 122 123 using element_type = RLP; 124 125 /// @brief Iterator class for iterating through items of RLP list. 126 class iterator 127 { 128 friend class RLP; 129 130 public: 131 using value_type = RLP; 132 using element_type = RLP; 133 134 iterator& operator++(); 135 iterator operator++(int) { auto ret = *this; operator++(); return ret; } 136 RLP operator*() const { return RLP(m_currentItem); } 137 bool operator==(iterator const& _cmp) const { return m_currentItem == _cmp.m_currentItem; } 138 bool operator!=(iterator const& _cmp) const { return !operator==(_cmp); } 139 140 private: 141 iterator() {} 142 iterator(RLP const& _parent, bool _begin); 143 144 size_t m_remaining = 0; 145 bytesConstRef m_currentItem; 146 }; 147 148 /// @brief Iterator into beginning of sub-item list (valid only if we are a list). 149 iterator begin() const { return iterator(*this, true); } 150 151 /// @brief Iterator into end of sub-item list (valid only if we are a list). 152 iterator end() const { return iterator(*this, false); } 153 154 template <class T> inline T convert(int _flags) const; 155 156 /// Best-effort conversion operators. 157 explicit operator std::string() const { return toString(); } 158 explicit operator bytes() const { return toBytes(); } 159 explicit operator uint8_t() const { return toInt<uint8_t>(); } 160 explicit operator uint16_t() const { return toInt<uint16_t>(); } 161 explicit operator uint32_t() const { return toInt<uint32_t>(); } 162 explicit operator uint64_t() const { return toInt<uint64_t>(); } 163 explicit operator u160() const { return toInt<u160>(); } 164 explicit operator u256() const { return toInt<u256>(); } 165 explicit operator bigint() const { return toInt<bigint>(); } 166 template <unsigned N> explicit operator FixedHash<N>() const { return toHash<FixedHash<N>>(); } 167 template <class T, class U> explicit operator std::pair<T, U>() const { return toPair<T, U>(); } 168 template <class T> explicit operator std::vector<T>() const { return toVector<T>(); } 169 template <class T> explicit operator std::set<T>() const { return toSet<T>(); } 170 template <class T, size_t N> explicit operator std::array<T, N>() const { return toArray<T, N>(); } 171 172 /// Converts to bytearray. @returns the empty byte array if not a string. 173 bytes toBytes(int _flags = LaissezFaire) const { if (!isData()) { if (_flags & ThrowOnFail) BOOST_THROW_EXCEPTION(BadCast()); else return bytes(); } return bytes(payload().data(), payload().data() + length()); } 174 /// Converts to bytearray. @returns the empty byte array if not a string. 175 bytesConstRef toBytesConstRef(int _flags = LaissezFaire) const { if (!isData()) { if (_flags & ThrowOnFail) BOOST_THROW_EXCEPTION(BadCast()); else return bytesConstRef(); } return payload().cropped(0, length()); } 176 /// Converts to string. @returns the empty string if not a string. 177 std::string toString(int _flags = LaissezFaire) const { if (!isData()) { if (_flags & ThrowOnFail) BOOST_THROW_EXCEPTION(BadCast()); else return std::string(); } return payload().cropped(0, length()).toString(); } 178 /// Converts to string. @throws BadCast if not a string. 179 std::string toStringStrict() const { return toString(Strict); } 180 181 template <class T> 182 std::vector<T> toVector(int _flags = LaissezFaire) const 183 { 184 std::vector<T> ret; 185 if (isList()) 186 { 187 ret.reserve(itemCount()); 188 for (auto const& i: *this) 189 ret.push_back(i.convert<T>(_flags)); 190 } 191 else if (_flags & ThrowOnFail) 192 BOOST_THROW_EXCEPTION(BadCast()); 193 return ret; 194 } 195 196 template <class T> 197 std::set<T> toSet(int _flags = LaissezFaire) const 198 { 199 std::set<T> ret; 200 if (isList()) 201 for (auto const& i: *this) 202 ret.insert(i.convert<T>(_flags)); 203 else if (_flags & ThrowOnFail) 204 BOOST_THROW_EXCEPTION(BadCast()); 205 return ret; 206 } 207 208 template <class T> 209 std::unordered_set<T> toUnorderedSet(int _flags = LaissezFaire) const 210 { 211 std::unordered_set<T> ret; 212 if (isList()) 213 for (auto const& i: *this) 214 ret.insert(i.convert<T>(_flags)); 215 else if (_flags & ThrowOnFail) 216 BOOST_THROW_EXCEPTION(BadCast()); 217 return ret; 218 } 219 220 template <class T, class U> 221 std::pair<T, U> toPair(int _flags = Strict) const 222 { 223 std::pair<T, U> ret; 224 if (itemCountStrict() != 2) 225 { 226 if (_flags & ThrowOnFail) 227 BOOST_THROW_EXCEPTION(BadCast()); 228 else 229 return ret; 230 } 231 ret.first = (*this)[0].convert<T>(_flags); 232 ret.second = (*this)[1].convert<U>(_flags); 233 return ret; 234 } 235 236 template <class T, size_t N> 237 std::array<T, N> toArray(int _flags = LaissezFaire) const 238 { 239 if (itemCount() != N) 240 { 241 if (_flags & ThrowOnFail) 242 BOOST_THROW_EXCEPTION(BadCast()); 243 else 244 return std::array<T, N>(); 245 } 246 std::array<T, N> ret; 247 for (size_t i = 0; i < N; ++i) 248 ret[i] = operator[](i).convert<T>(_flags); 249 return ret; 250 } 251 252 /// Converts to int of type given; if isData(), decodes as big-endian bytestream. @returns 0 if not an int or data. 253 template <class _T = unsigned> _T toInt(int _flags = Strict) const 254 { 255 requireGood(); 256 if ((!isInt() && !(_flags & AllowNonCanon)) || isList() || isNull()) 257 { 258 if (_flags & ThrowOnFail) 259 BOOST_THROW_EXCEPTION(BadCast()); 260 else 261 return 0; 262 } 263 264 auto p = payload(); 265 if (p.size() > intTraits<_T>::maxSize && (_flags & FailIfTooBig)) 266 { 267 if (_flags & ThrowOnFail) 268 BOOST_THROW_EXCEPTION(BadCast()); 269 else 270 return 0; 271 } 272 273 return fromBigEndian<_T>(p); 274 } 275 276 int64_t toPositiveInt64(int _flags = Strict) const 277 { 278 int64_t i = toInt<int64_t>(_flags); 279 if ((_flags & ThrowOnFail) && i < 0) 280 BOOST_THROW_EXCEPTION(BadCast()); 281 return i; 282 } 283 284 template <class _N> _N toHash(int _flags = Strict) const 285 { 286 requireGood(); 287 auto p = payload(); 288 auto l = p.size(); 289 if (!isData() || (l > _N::size && (_flags & FailIfTooBig)) || (l < _N::size && (_flags & FailIfTooSmall))) 290 { 291 if (_flags & ThrowOnFail) 292 BOOST_THROW_EXCEPTION(BadCast()); 293 else 294 return _N(); 295 } 296 297 _N ret; 298 size_t s = std::min<size_t>(_N::size, l); 299 memcpy(ret.data() + _N::size - s, p.data(), s); 300 return ret; 301 } 302 303 /// @returns the data payload. Valid for all types. 304 bytesConstRef payload() const { auto l = length(); if (l > m_data.size()) BOOST_THROW_EXCEPTION(BadRLP()); return m_data.cropped(payloadOffset(), l); } 305 306 /// @returns the theoretical size of this item as encoded in the data. 307 /// @note Under normal circumstances, is equivalent to m_data.size() - use that unless you know it won't work. 308 size_t actualSize() const; 309 310 private: 311 /// Disable construction from rvalue 312 explicit RLP(bytes const&&) {} 313 314 /// Throws if is non-canonical data (i.e. single byte done in two bytes that could be done in one). 315 void requireGood() const; 316 317 /// Single-byte data payload. 318 bool isSingleByte() const { return !isNull() && m_data[0] < c_rlpDataImmLenStart; } 319 320 /// @returns the amount of bytes used to encode the length of the data. Valid for all types. 321 unsigned lengthSize() const { if (isData() && m_data[0] > c_rlpDataIndLenZero) return m_data[0] - c_rlpDataIndLenZero; if (isList() && m_data[0] > c_rlpListIndLenZero) return m_data[0] - c_rlpListIndLenZero; return 0; } 322 323 /// @returns the size in bytes of the payload, as given by the RLP as opposed to as inferred from m_data. 324 size_t length() const; 325 326 /// @returns the number of bytes into the data that the payload starts. 327 size_t payloadOffset() const { return isSingleByte() ? 0 : (1 + lengthSize()); } 328 329 /// @returns the number of data items. 330 size_t items() const; 331 332 /// @returns the size encoded into the RLP in @a _data and throws if _data is too short. 333 static size_t sizeAsEncoded(bytesConstRef _data) { return RLP(_data, ThrowOnFail | FailIfTooSmall).actualSize(); } 334 335 /// Our byte data. 336 bytesConstRef m_data; 337 338 /// The list-indexing cache. 339 // Index of the last item accessed with operator[] 340 mutable size_t m_lastIndex = (size_t)-1; 341 // Offset of the next byte after last byte of m_lastItem 342 mutable size_t m_lastEnd = 0; 343 // Data of the last item accessed with operator[] 344 mutable bytesConstRef m_lastItem; 345 }; 346 347 template <> struct Converter<std::string> { static std::string convert(RLP const& _r, int _flags) { return _r.toString(_flags); } }; 348 template <> struct Converter<bytes> { static bytes convert(RLP const& _r, int _flags) { return _r.toBytes(_flags); } }; 349 template <> struct Converter<uint8_t> { static uint8_t convert(RLP const& _r, int _flags) { return _r.toInt<uint8_t>(_flags); } }; 350 template <> struct Converter<uint16_t> { static uint16_t convert(RLP const& _r, int _flags) { return _r.toInt<uint16_t>(_flags); } }; 351 template <> struct Converter<uint32_t> { static uint32_t convert(RLP const& _r, int _flags) { return _r.toInt<uint32_t>(_flags); } }; 352 template <> struct Converter<uint64_t> { static uint64_t convert(RLP const& _r, int _flags) { return _r.toInt<uint64_t>(_flags); } }; 353 template <> struct Converter<u160> { static u160 convert(RLP const& _r, int _flags) { return _r.toInt<u160>(_flags); } }; 354 template <> struct Converter<u256> { static u256 convert(RLP const& _r, int _flags) { return _r.toInt<u256>(_flags); } }; 355 template <> struct Converter<bigint> { static bigint convert(RLP const& _r, int _flags) { return _r.toInt<bigint>(_flags); } }; 356 template <unsigned N> struct Converter<FixedHash<N>> { static FixedHash<N> convert(RLP const& _r, int _flags) { return _r.toHash<FixedHash<N>>(_flags); } }; 357 template <class T, class U> struct Converter<std::pair<T, U>> { static std::pair<T, U> convert(RLP const& _r, int _flags) { return _r.toPair<T, U>(_flags); } }; 358 template <class T> struct Converter<std::vector<T>> { static std::vector<T> convert(RLP const& _r, int _flags) { return _r.toVector<T>(_flags); } }; 359 template <class T> struct Converter<std::set<T>> { static std::set<T> convert(RLP const& _r, int _flags) { return _r.toSet<T>(_flags); } }; 360 template <class T> struct Converter<std::unordered_set<T>> { static std::unordered_set<T> convert(RLP const& _r, int _flags) { return _r.toUnorderedSet<T>(_flags); } }; 361 template <class T, size_t N> struct Converter<std::array<T, N>> { static std::array<T, N> convert(RLP const& _r, int _flags) { return _r.toArray<T, N>(_flags); } }; 362 363 template <class T> inline T RLP::convert(int _flags) const { return Converter<T>::convert(*this, _flags); } 364 365 /** 366 * @brief Class for writing to an RLP bytestream. 367 */ 368 class RLPStream 369 { 370 public: 371 /// Initializes empty RLPStream. 372 RLPStream() {} 373 374 /// Initializes the RLPStream as a list of @a _listItems items. 375 explicit RLPStream(size_t _listItems) { appendList(_listItems); } 376 377 ~RLPStream() {} 378 379 /// Append given datum to the byte stream. 380 RLPStream& append(unsigned _s) { return append(bigint(_s)); } 381 RLPStream& append(u160 _s) { return append(bigint(_s)); } 382 RLPStream& append(u256 _s) { return append(bigint(_s)); } 383 RLPStream& append(bigint _s); 384 RLPStream& append(bytesConstRef _s, bool _compact = false); 385 RLPStream& append(bytes const& _s) { return append(bytesConstRef(&_s)); } 386 RLPStream& append(std::string const& _s) { return append(bytesConstRef(_s)); } 387 RLPStream& append(char const* _s) { return append(std::string(_s)); } 388 template <unsigned N> RLPStream& append(FixedHash<N> _s, bool _compact = false, bool _allOrNothing = false) { return _allOrNothing && !_s ? append(bytesConstRef()) : append(_s.ref(), _compact); } 389 390 /// Appends an arbitrary RLP fragment - this *must* be a single item unless @a _itemCount is given. 391 RLPStream& append(RLP const& _rlp, size_t _itemCount = 1) { return appendRaw(_rlp.data(), _itemCount); } 392 393 /// Appends a sequence of data to the stream as a list. 394 template <class _T> RLPStream& append(std::vector<_T> const& _s) { return appendVector(_s); } 395 template <class _T> RLPStream& appendVector(std::vector<_T> const& _s) { appendList(_s.size()); for (auto const& i: _s) append(i); return *this; } 396 template <class _T, size_t S> RLPStream& append(std::array<_T, S> const& _s) { appendList(_s.size()); for (auto const& i: _s) append(i); return *this; } 397 template <class _T> RLPStream& append(std::set<_T> const& _s) { appendList(_s.size()); for (auto const& i: _s) append(i); return *this; } 398 template <class _T> RLPStream& append(std::unordered_set<_T> const& _s) { appendList(_s.size()); for (auto const& i: _s) append(i); return *this; } 399 template <class T, class U> RLPStream& append(std::pair<T, U> const& _s) { appendList(2); append(_s.first); append(_s.second); return *this; } 400 401 /// Appends a list. 402 RLPStream& appendList(size_t _items); 403 RLPStream& appendList(bytesConstRef _rlp); 404 RLPStream& appendList(bytes const& _rlp) { return appendList(&_rlp); } 405 RLPStream& appendList(RLPStream const& _s) { return appendList(&_s.out()); } 406 407 /// Appends raw (pre-serialised) RLP data. Use with caution. 408 RLPStream& appendRaw(bytesConstRef _rlp, size_t _itemCount = 1); 409 RLPStream& appendRaw(bytes const& _rlp, size_t _itemCount = 1) { return appendRaw(&_rlp, _itemCount); } 410 411 /// Shift operators for appending data items. 412 template <class T> RLPStream& operator<<(T _data) { return append(_data); } 413 414 /// Clear the output stream so far. 415 void clear() { m_out.clear(); m_listStack.clear(); } 416 417 /// Read the byte stream. 418 bytes const& out() const { if(!m_listStack.empty()) BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("listStack is not empty")); return m_out; } 419 420 /// Invalidate the object and steal the output byte stream. 421 bytes&& invalidate() { if(!m_listStack.empty()) BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("listStack is not empty")); return std::move(m_out); } 422 423 /// Swap the contents of the output stream out for some other byte array. 424 void swapOut(bytes& _dest) { if(!m_listStack.empty()) BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("listStack is not empty")); swap(m_out, _dest); } 425 426 private: 427 void noteAppended(size_t _itemCount = 1); 428 429 /// Push the node-type byte (using @a _base) along with the item count @a _count. 430 /// @arg _count is number of characters for strings, data-bytes for ints, or items for lists. 431 void pushCount(size_t _count, byte _offset); 432 433 /// Push an integer as a raw big-endian byte-stream. 434 template <class _T> void pushInt(_T _i, size_t _br) 435 { 436 m_out.resize(m_out.size() + _br); 437 byte* b = &m_out.back(); 438 for (; _i; _i >>= 8) 439 *(b--) = toUint8(_i); 440 } 441 442 /// Our output byte stream. 443 bytes m_out; 444 445 std::vector<std::pair<size_t, size_t>> m_listStack; 446 }; 447 448 template <class _T> void rlpListAux(RLPStream& _out, _T _t) { _out << _t; } 449 template <class _T, class ... _Ts> void rlpListAux(RLPStream& _out, _T _t, _Ts ... _ts) { rlpListAux(_out << _t, _ts...); } 450 451 /// Export a single item in RLP format, returning a byte array. 452 template <class _T> bytes rlp(_T _t) { return (RLPStream() << _t).out(); } 453 454 /// Export a list of items in RLP format, returning a byte array. 455 inline bytes rlpList() { return RLPStream(0).out(); } 456 template <class ... _Ts> bytes rlpList(_Ts ... _ts) 457 { 458 RLPStream out(sizeof ...(_Ts)); 459 rlpListAux(out, _ts...); 460 return out.out(); 461 } 462 463 /// The empty string in RLP format. 464 extern bytes RLPNull; 465 466 /// The empty list in RLP format. 467 extern bytes RLPEmptyList; 468 469 /// Human readable version of RLP. 470 std::ostream& operator<<(std::ostream& _out, dev::RLP const& _d); 471 472 } 473