diff --git a/src/prevector.h b/src/prevector.h index 00afe6166..6ae8d774b 100644 --- a/src/prevector.h +++ b/src/prevector.h @@ -1,611 +1,613 @@ // Copyright (c) 2015-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_PREVECTOR_H #define BITCOIN_PREVECTOR_H #include #include #include #include #include #include #include #include /** * Implements a drop-in replacement for std::vector which stores up to N * elements directly (without heap allocation). The types Size and Diff are used * to store element counts, and can be any unsigned + signed type. * * Storage layout is either: * - Direct allocation: * - Size _size: the number of used elements (between 0 and N) * - T direct[N]: an array of N elements of type T * (only the first _size are initialized). * - Indirect allocation: * - Size _size: the number of used elements plus N + 1 * - Size capacity: the number of allocated elements * - T* indirect: a pointer to an array of capacity elements of type T * (only the first _size are initialized). * * The data type T must be movable by memmove/realloc(). Once we switch to C++, * move constructors can be used instead. */ template class prevector { public: typedef Size size_type; typedef Diff difference_type; typedef T value_type; typedef value_type &reference; typedef const value_type &const_reference; typedef value_type *pointer; typedef const value_type *const_pointer; class iterator { T *ptr; public: typedef Diff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; typedef std::random_access_iterator_tag iterator_category; iterator() : ptr(nullptr) {} iterator(T *ptr_) : ptr(ptr_) {} T &operator*() const { return *ptr; } T *operator->() const { return ptr; } T &operator[](size_type pos) { return ptr[pos]; } const T &operator[](size_type pos) const { return ptr[pos]; } iterator &operator++() { ptr++; return *this; } iterator &operator--() { ptr--; return *this; } iterator operator++(int) { iterator copy(*this); ++(*this); return copy; } iterator operator--(int) { iterator copy(*this); --(*this); return copy; } difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); } iterator operator+(size_type n) { return iterator(ptr + n); } iterator &operator+=(size_type n) { ptr += n; return *this; } iterator operator-(size_type n) { return iterator(ptr - n); } iterator &operator-=(size_type n) { ptr -= n; return *this; } bool operator==(iterator x) const { return ptr == x.ptr; } bool operator!=(iterator x) const { return ptr != x.ptr; } bool operator>=(iterator x) const { return ptr >= x.ptr; } bool operator<=(iterator x) const { return ptr <= x.ptr; } bool operator>(iterator x) const { return ptr > x.ptr; } bool operator<(iterator x) const { return ptr < x.ptr; } }; class reverse_iterator { T *ptr; public: typedef Diff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; typedef std::bidirectional_iterator_tag iterator_category; reverse_iterator() : ptr(nullptr) {} reverse_iterator(T *ptr_) : ptr(ptr_) {} T &operator*() { return *ptr; } const T &operator*() const { return *ptr; } T *operator->() { return ptr; } const T *operator->() const { return ptr; } reverse_iterator &operator--() { ptr++; return *this; } reverse_iterator &operator++() { ptr--; return *this; } reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; } reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; } bool operator==(reverse_iterator x) const { return ptr == x.ptr; } bool operator!=(reverse_iterator x) const { return ptr != x.ptr; } }; class const_iterator { const T *ptr; public: typedef Diff difference_type; typedef const T value_type; typedef const T *pointer; typedef const T &reference; typedef std::random_access_iterator_tag iterator_category; const_iterator() : ptr(nullptr) {} const_iterator(const T *ptr_) : ptr(ptr_) {} const_iterator(iterator x) : ptr(&(*x)) {} const T &operator*() const { return *ptr; } const T *operator->() const { return ptr; } const T &operator[](size_type pos) const { return ptr[pos]; } const_iterator &operator++() { ptr++; return *this; } const_iterator &operator--() { ptr--; return *this; } const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; } const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; } difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); } const_iterator operator+(size_type n) { return const_iterator(ptr + n); } const_iterator &operator+=(size_type n) { ptr += n; return *this; } const_iterator operator-(size_type n) { return const_iterator(ptr - n); } const_iterator &operator-=(size_type n) { ptr -= n; return *this; } bool operator==(const_iterator x) const { return ptr == x.ptr; } bool operator!=(const_iterator x) const { return ptr != x.ptr; } bool operator>=(const_iterator x) const { return ptr >= x.ptr; } bool operator<=(const_iterator x) const { return ptr <= x.ptr; } bool operator>(const_iterator x) const { return ptr > x.ptr; } bool operator<(const_iterator x) const { return ptr < x.ptr; } }; class const_reverse_iterator { const T *ptr; public: typedef Diff difference_type; typedef const T value_type; typedef const T *pointer; typedef const T &reference; typedef std::bidirectional_iterator_tag iterator_category; const_reverse_iterator() : ptr(nullptr) {} const_reverse_iterator(const T *ptr_) : ptr(ptr_) {} const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {} const T &operator*() const { return *ptr; } const T *operator->() const { return ptr; } const_reverse_iterator &operator--() { ptr++; return *this; } const_reverse_iterator &operator++() { ptr--; return *this; } const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; } const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; } bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; } bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; } }; private: #pragma pack(push, 1) union direct_or_indirect { char direct[sizeof(T) * N]; struct { char *indirect; size_type capacity; }; }; #pragma pack(pop) alignas(char *) direct_or_indirect _union = {}; size_type _size = 0; static_assert(alignof(char *) % alignof(size_type) == 0 && sizeof(char *) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment " "requirement than pointer"); static_assert(alignof(char *) % alignof(T) == 0, "value_type T cannot have more restrictive alignment " "requirement than pointer"); T *direct_ptr(difference_type pos) { return reinterpret_cast(_union.direct) + pos; } const T *direct_ptr(difference_type pos) const { return reinterpret_cast(_union.direct) + pos; } T *indirect_ptr(difference_type pos) { return reinterpret_cast(_union.indirect) + pos; } const T *indirect_ptr(difference_type pos) const { return reinterpret_cast(_union.indirect) + pos; } bool is_direct() const { return _size <= N; } void change_capacity(size_type new_capacity) { if (new_capacity <= N) { if (!is_direct()) { T *indirect = indirect_ptr(0); T *src = indirect; T *dst = direct_ptr(0); memcpy(dst, src, size() * sizeof(T)); free(indirect); _size -= N + 1; } } else { if (!is_direct()) { // FIXME: Because malloc/realloc here won't call new_handler if // allocation fails, assert success. These should instead use an // allocator or new/delete so that handlers are called as // necessary, but performance would be slightly degraded by // doing so. _union.indirect = static_cast(realloc( _union.indirect, ((size_t)sizeof(T)) * new_capacity)); assert(_union.indirect); _union.capacity = new_capacity; } else { char *new_indirect = static_cast( malloc(((size_t)sizeof(T)) * new_capacity)); assert(new_indirect); T *src = direct_ptr(0); T *dst = reinterpret_cast(new_indirect); memcpy(dst, src, size() * sizeof(T)); _union.indirect = new_indirect; _union.capacity = new_capacity; _size += N + 1; } } } T *item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); } const T *item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); } void fill(T *dst, ptrdiff_t count, const T &value = T{}) { std::fill_n(dst, count, value); } template void fill(T *dst, InputIterator first, InputIterator last) { while (first != last) { new (static_cast(dst)) T(*first); ++dst; ++first; } } public: void assign(size_type n, const T &val) { clear(); if (capacity() < n) { change_capacity(n); } _size += n; fill(item_ptr(0), n, val); } template void assign(InputIterator first, InputIterator last) { size_type n = last - first; clear(); if (capacity() < n) { change_capacity(n); } _size += n; fill(item_ptr(0), first, last); } prevector() {} explicit prevector(size_type n) { resize(n); } explicit prevector(size_type n, const T &val) { change_capacity(n); _size += n; fill(item_ptr(0), n, val); } template prevector(InputIterator first, InputIterator last) { size_type n = last - first; change_capacity(n); _size += n; fill(item_ptr(0), first, last); } prevector(const prevector &other) { size_type n = other.size(); change_capacity(n); _size += n; fill(item_ptr(0), other.begin(), other.end()); } prevector(prevector &&other) { swap(other); } prevector &operator=(const prevector &other) { if (&other == this) { return *this; } assign(other.begin(), other.end()); return *this; } prevector &operator=(prevector &&other) { swap(other); return *this; } size_type size() const { return is_direct() ? _size : _size - N - 1; } bool empty() const { return size() == 0; } iterator begin() { return iterator(item_ptr(0)); } const_iterator begin() const { return const_iterator(item_ptr(0)); } iterator end() { return iterator(item_ptr(size())); } const_iterator end() const { return const_iterator(item_ptr(size())); } reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); } const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); } reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); } const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); } size_t capacity() const { if (is_direct()) { return N; } else { return _union.capacity; } } T &operator[](size_type pos) { return *item_ptr(pos); } const T &operator[](size_type pos) const { return *item_ptr(pos); } void resize(size_type new_size) { size_type cur_size = size(); if (cur_size == new_size) { return; } if (cur_size > new_size) { erase(item_ptr(new_size), end()); return; } if (new_size > capacity()) { change_capacity(new_size); } ptrdiff_t increase = new_size - cur_size; fill(item_ptr(cur_size), increase); _size += increase; } void reserve(size_type new_capacity) { if (new_capacity > capacity()) { change_capacity(new_capacity); } } void shrink_to_fit() { change_capacity(size()); } void clear() { resize(0); } iterator insert(iterator pos, const T &value) { size_type p = pos - begin(); size_type new_size = size() + 1; if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } T *ptr = item_ptr(p); memmove(ptr + 1, ptr, (size() - p) * sizeof(T)); _size++; new (static_cast(ptr)) T(value); return iterator(ptr); } void insert(iterator pos, size_type count, const T &value) { size_type p = pos - begin(); size_type new_size = size() + count; if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } T *ptr = item_ptr(p); memmove(ptr + count, ptr, (size() - p) * sizeof(T)); _size += count; fill(item_ptr(p), count, value); } template void insert(iterator pos, InputIterator first, InputIterator last) { size_type p = pos - begin(); difference_type count = last - first; size_type new_size = size() + count; if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } T *ptr = item_ptr(p); memmove(ptr + count, ptr, (size() - p) * sizeof(T)); _size += count; fill(ptr, first, last); } inline void resize_uninitialized(size_type new_size) { // resize_uninitialized changes the size of the prevector but does not // initialize it. If size < new_size, the added elements must be // initialized explicitly. if (capacity() < new_size) { change_capacity(new_size); _size += new_size - size(); return; } if (new_size < size()) { erase(item_ptr(new_size), end()); } else { _size += new_size - size(); } } iterator erase(iterator pos) { return erase(pos, pos + 1); } iterator erase(iterator first, iterator last) { // Erase is not allowed to the change the object's capacity. That means // that when starting with an indirectly allocated prevector with // size and capacity > N, the result may be a still indirectly allocated // prevector with size <= N and capacity > N. A shrink_to_fit() call is // necessary to switch to the (more efficient) directly allocated // representation (with capacity N and size <= N). iterator p = first; char *endp = (char *)&(*end()); if (!std::is_trivially_destructible::value) { while (p != last) { (*p).~T(); _size--; ++p; } } else { _size -= last - p; } memmove(&(*first), &(*last), endp - ((char *)(&(*last)))); return first; } - void push_back(const T &value) { + template void emplace_back(Args &&... args) { size_type new_size = size() + 1; if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } - new (item_ptr(size())) T(value); + new (item_ptr(size())) T(std::forward(args)...); _size++; } + void push_back(const T &value) { emplace_back(value); } + void pop_back() { erase(end() - 1, end()); } T &front() { return *item_ptr(0); } const T &front() const { return *item_ptr(0); } T &back() { return *item_ptr(size() - 1); } const T &back() const { return *item_ptr(size() - 1); } void swap(prevector &other) { std::swap(_union, other._union); std::swap(_size, other._size); } ~prevector() { if (!std::is_trivially_destructible::value) { clear(); } if (!is_direct()) { free(_union.indirect); _union.indirect = nullptr; } } bool operator==(const prevector &other) const { if (other.size() != size()) { return false; } const_iterator b1 = begin(); const_iterator b2 = other.begin(); const_iterator e1 = end(); while (b1 != e1) { if ((*b1) != (*b2)) { return false; } ++b1; ++b2; } return true; } bool operator!=(const prevector &other) const { return !(*this == other); } bool operator<(const prevector &other) const { if (size() < other.size()) { return true; } if (size() > other.size()) { return false; } const_iterator b1 = begin(); const_iterator b2 = other.begin(); const_iterator e1 = end(); while (b1 != e1) { if ((*b1) < (*b2)) { return true; } if ((*b2) < (*b1)) { return false; } ++b1; ++b2; } return false; } size_t allocated_memory() const { if (is_direct()) { return 0; } else { return ((size_t)(sizeof(T))) * _union.capacity; } } value_type *data() { return item_ptr(0); } const value_type *data() const { return item_ptr(0); } }; #endif // BITCOIN_PREVECTOR_H diff --git a/src/serialize.h b/src/serialize.h index e173589da..9851d14c0 100644 --- a/src/serialize.h +++ b/src/serialize.h @@ -1,1179 +1,1180 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_SERIALIZE_H #define BITCOIN_SERIALIZE_H #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include static const uint64_t MAX_SIZE = 0x02000000; /** * Maximum amount of memory (in bytes) to allocate at once when deserializing * vectors. */ static const unsigned int MAX_VECTOR_ALLOCATE = 5000000; /** * Dummy data type to identify deserializing constructors. * * By convention, a constructor of a type T with signature * * template T::T(deserialize_type, Stream& s) * * is a deserializing constructor, which builds the type by deserializing it * from s. If T contains const fields, this is likely the only way to do so. */ struct deserialize_type {}; constexpr deserialize_type deserialize{}; /** * Used to bypass the rule against non-const reference to temporary * where it makes sense with wrappers. */ template inline T &REF(const T &val) { return const_cast(val); } /** * Used to acquire a non-const pointer "this" to generate bodies of const * serialization operations from a template */ template inline T *NCONST_PTR(const T *val) { return const_cast(val); } //! Safely convert odd char pointer types to standard ones. inline char *CharCast(char *c) { return c; } inline char *CharCast(uint8_t *c) { return (char *)c; } inline const char *CharCast(const char *c) { return c; } inline const char *CharCast(const uint8_t *c) { return (const char *)c; } /** * Lowest-level serialization and conversion. * @note Sizes of these types are verified in the tests */ template inline void ser_writedata8(Stream &s, uint8_t obj) { s.write((char *)&obj, 1); } template inline void ser_writedata16(Stream &s, uint16_t obj) { obj = htole16(obj); s.write((char *)&obj, 2); } template inline void ser_writedata16be(Stream &s, uint16_t obj) { obj = htobe16(obj); s.write((char *)&obj, 2); } template inline void ser_writedata32(Stream &s, uint32_t obj) { obj = htole32(obj); s.write((char *)&obj, 4); } template inline void ser_writedata32be(Stream &s, uint32_t obj) { obj = htobe32(obj); s.write((char *)&obj, 4); } template inline void ser_writedata64(Stream &s, uint64_t obj) { obj = htole64(obj); s.write((char *)&obj, 8); } template inline uint8_t ser_readdata8(Stream &s) { uint8_t obj; s.read((char *)&obj, 1); return obj; } template inline uint16_t ser_readdata16(Stream &s) { uint16_t obj; s.read((char *)&obj, 2); return le16toh(obj); } template inline uint16_t ser_readdata16be(Stream &s) { uint16_t obj; s.read((char *)&obj, 2); return be16toh(obj); } template inline uint32_t ser_readdata32(Stream &s) { uint32_t obj; s.read((char *)&obj, 4); return le32toh(obj); } template inline uint32_t ser_readdata32be(Stream &s) { uint32_t obj; s.read((char *)&obj, 4); return be32toh(obj); } template inline uint64_t ser_readdata64(Stream &s) { uint64_t obj; s.read((char *)&obj, 8); return le64toh(obj); } inline uint64_t ser_double_to_uint64(double x) { uint64_t tmp; std::memcpy(&tmp, &x, sizeof(x)); static_assert(sizeof(tmp) == sizeof(x), "double and uint64_t assumed to have the same size"); return tmp; } inline uint32_t ser_float_to_uint32(float x) { uint32_t tmp; std::memcpy(&tmp, &x, sizeof(x)); static_assert(sizeof(tmp) == sizeof(x), "float and uint32_t assumed to have the same size"); return tmp; } inline double ser_uint64_to_double(uint64_t y) { double tmp; std::memcpy(&tmp, &y, sizeof(y)); static_assert(sizeof(tmp) == sizeof(y), "double and uint64_t assumed to have the same size"); return tmp; } inline float ser_uint32_to_float(uint32_t y) { float tmp; std::memcpy(&tmp, &y, sizeof(y)); static_assert(sizeof(tmp) == sizeof(y), "float and uint32_t assumed to have the same size"); return tmp; } ///////////////////////////////////////////////////////////////// // // Templates for serializing to anything that looks like a stream, // i.e. anything that supports .read(char*, size_t) and .write(char*, size_t) // class CSizeComputer; enum { // primary actions SER_NETWORK = (1 << 0), SER_DISK = (1 << 1), SER_GETHASH = (1 << 2), }; //! Convert the reference base type to X, without changing constness or //! reference type. template X &ReadWriteAsHelper(X &x) { return x; } template const X &ReadWriteAsHelper(const X &x) { return x; } #define READWRITE(...) (::SerReadWriteMany(s, ser_action, __VA_ARGS__)) #define READWRITEAS(type, obj) \ (::SerReadWriteMany(s, ser_action, ReadWriteAsHelper(obj))) /** * Implement three methods for serializable objects. These are actually wrappers * over "SerializationOp" template, which implements the body of each class' * serialization code. Adding "ADD_SERIALIZE_METHODS" in the body of the class * causes these wrappers to be added as members. */ #define ADD_SERIALIZE_METHODS \ template void Serialize(Stream &s) const { \ NCONST_PTR(this)->SerializationOp(s, CSerActionSerialize()); \ } \ template void Unserialize(Stream &s) { \ SerializationOp(s, CSerActionUnserialize()); \ } /** * Implement the Ser and Unser methods needed for implementing a formatter * (see Using below). * * Both Ser and Unser are delegated to a single static method SerializationOps, * which is polymorphic in the serialized/deserialized type (allowing it to be * const when serializing, and non-const when deserializing). * * Example use: * struct FooFormatter { * FORMATTER_METHODS(Class, obj) { READWRITE(obj.val1, VARINT(obj.val2)); } * } * would define a class FooFormatter that defines a serialization of Class * objects consisting of serializing its val1 member using the default * serialization, and its val2 member using VARINT serialization. That * FooFormatter can then be used in statements like * READWRITE(Using(obj.bla)). */ #define FORMATTER_METHODS(cls, obj) \ template static void Ser(Stream &s, const cls &obj) { \ SerializationOps(obj, s, CSerActionSerialize()); \ } \ template static void Unser(Stream &s, cls &obj) { \ SerializationOps(obj, s, CSerActionUnserialize()); \ } \ template \ static inline void SerializationOps(Type &obj, Stream &s, \ Operation ser_action) /** * Implement the Serialize and Unserialize methods by delegating to a * single templated static method that takes the to-be-(de)serialized * object as a parameter. This approach has the advantage that the * constness of the object becomes a template parameter, and thus * allows a single implementation that sees the object as const for * serializing and non-const for deserializing, without casts. */ #define SERIALIZE_METHODS(cls, obj) \ template void Serialize(Stream &s) const { \ static_assert(std::is_same::value, \ "Serialize type mismatch"); \ Ser(s, *this); \ } \ template void Unserialize(Stream &s) { \ static_assert(std::is_same::value, \ "Unserialize type mismatch"); \ Unser(s, *this); \ } \ FORMATTER_METHODS(cls, obj) #ifndef CHAR_EQUALS_INT8 // TODO Get rid of bare char template inline void Serialize(Stream &s, char a) { ser_writedata8(s, a); } #endif template inline void Serialize(Stream &s, int8_t a) { ser_writedata8(s, a); } template inline void Serialize(Stream &s, uint8_t a) { ser_writedata8(s, a); } template inline void Serialize(Stream &s, int16_t a) { ser_writedata16(s, a); } template inline void Serialize(Stream &s, uint16_t a) { ser_writedata16(s, a); } template inline void Serialize(Stream &s, int32_t a) { ser_writedata32(s, a); } template inline void Serialize(Stream &s, uint32_t a) { ser_writedata32(s, a); } template inline void Serialize(Stream &s, int64_t a) { ser_writedata64(s, a); } template inline void Serialize(Stream &s, uint64_t a) { ser_writedata64(s, a); } template inline void Serialize(Stream &s, float a) { ser_writedata32(s, ser_float_to_uint32(a)); } template inline void Serialize(Stream &s, double a) { ser_writedata64(s, ser_double_to_uint64(a)); } template inline void Serialize(Stream &s, const int8_t (&a)[N]) { s.write(a, N); } template inline void Serialize(Stream &s, const uint8_t (&a)[N]) { s.write(CharCast(a), N); } template inline void Serialize(Stream &s, const std::array &a) { s.write(a.data(), N); } template inline void Serialize(Stream &s, const std::array &a) { s.write(CharCast(a.data()), N); } #ifndef CHAR_EQUALS_INT8 // TODO Get rid of bare char template inline void Unserialize(Stream &s, char &a) { a = ser_readdata8(s); } template inline void Serialize(Stream &s, const char (&a)[N]) { s.write(a, N); } template inline void Serialize(Stream &s, const std::array &a) { s.write(a.data(), N); } #endif template inline void Serialize(Stream &s, const Span &span) { s.write(CharCast(span.data()), span.size()); } template inline void Serialize(Stream &s, const Span &span) { s.write(CharCast(span.data()), span.size()); } template inline void Unserialize(Stream &s, int8_t &a) { a = ser_readdata8(s); } template inline void Unserialize(Stream &s, uint8_t &a) { a = ser_readdata8(s); } template inline void Unserialize(Stream &s, int16_t &a) { a = ser_readdata16(s); } template inline void Unserialize(Stream &s, uint16_t &a) { a = ser_readdata16(s); } template inline void Unserialize(Stream &s, int32_t &a) { a = ser_readdata32(s); } template inline void Unserialize(Stream &s, uint32_t &a) { a = ser_readdata32(s); } template inline void Unserialize(Stream &s, int64_t &a) { a = ser_readdata64(s); } template inline void Unserialize(Stream &s, uint64_t &a) { a = ser_readdata64(s); } template inline void Unserialize(Stream &s, float &a) { a = ser_uint32_to_float(ser_readdata32(s)); } template inline void Unserialize(Stream &s, double &a) { a = ser_uint64_to_double(ser_readdata64(s)); } template inline void Unserialize(Stream &s, int8_t (&a)[N]) { s.read(a, N); } template inline void Unserialize(Stream &s, uint8_t (&a)[N]) { s.read(CharCast(a), N); } template inline void Unserialize(Stream &s, std::array &a) { s.read(a.data(), N); } template inline void Unserialize(Stream &s, std::array &a) { s.read(CharCast(a.data()), N); } #ifndef CHAR_EQUALS_INT8 template inline void Unserialize(Stream &s, char (&a)[N]) { s.read(CharCast(a), N); } template inline void Unserialize(Stream &s, std::array &a) { s.read(CharCast(a.data()), N); } #endif template inline void Serialize(Stream &s, bool a) { char f = a; ser_writedata8(s, f); } template inline void Unserialize(Stream &s, bool &a) { char f = ser_readdata8(s); a = f; } template inline void Unserialize(Stream &s, Span &span) { s.read(CharCast(span.data()), span.size()); } /** * Compact Size * size < 253 -- 1 byte * size <= USHRT_MAX -- 3 bytes (253 + 2 bytes) * size <= UINT_MAX -- 5 bytes (254 + 4 bytes) * size > UINT_MAX -- 9 bytes (255 + 8 bytes) */ inline uint32_t GetSizeOfCompactSize(uint64_t nSize) { if (nSize < 253) { return sizeof(uint8_t); } if (nSize <= std::numeric_limits::max()) { return sizeof(uint8_t) + sizeof(uint16_t); } if (nSize <= std::numeric_limits::max()) { return sizeof(uint8_t) + sizeof(uint32_t); } return sizeof(uint8_t) + sizeof(uint64_t); } inline void WriteCompactSize(CSizeComputer &os, uint64_t nSize); template void WriteCompactSize(Stream &os, uint64_t nSize) { if (nSize < 253) { ser_writedata8(os, nSize); } else if (nSize <= std::numeric_limits::max()) { ser_writedata8(os, 253); ser_writedata16(os, nSize); } else if (nSize <= std::numeric_limits::max()) { ser_writedata8(os, 254); ser_writedata32(os, nSize); } else { ser_writedata8(os, 255); ser_writedata64(os, nSize); } return; } template uint64_t ReadCompactSize(Stream &is) { uint8_t chSize = ser_readdata8(is); uint64_t nSizeRet = 0; if (chSize < 253) { nSizeRet = chSize; } else if (chSize == 253) { nSizeRet = ser_readdata16(is); if (nSizeRet < 253) { throw std::ios_base::failure("non-canonical ReadCompactSize()"); } } else if (chSize == 254) { nSizeRet = ser_readdata32(is); if (nSizeRet < 0x10000u) { throw std::ios_base::failure("non-canonical ReadCompactSize()"); } } else { nSizeRet = ser_readdata64(is); if (nSizeRet < 0x100000000ULL) { throw std::ios_base::failure("non-canonical ReadCompactSize()"); } } if (nSizeRet > MAX_SIZE) { throw std::ios_base::failure("ReadCompactSize(): size too large"); } return nSizeRet; } /** * Variable-length integers: bytes are a MSB base-128 encoding of the number. * The high bit in each byte signifies whether another digit follows. To make * sure the encoding is one-to-one, one is subtracted from all but the last * digit. Thus, the byte sequence a[] with length len, where all but the last * byte has bit 128 set, encodes the number: * * (a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1)) * * Properties: * * Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes) * * Every integer has exactly one encoding * * Encoding does not depend on size of original integer type * * No redundancy: every (infinite) byte sequence corresponds to a list * of encoded integers. * * 0: [0x00] 256: [0x81 0x00] * 1: [0x01] 16383: [0xFE 0x7F] * 127: [0x7F] 16384: [0xFF 0x00] * 128: [0x80 0x00] 16511: [0xFF 0x7F] * 255: [0x80 0x7F] 65535: [0x82 0xFE 0x7F] * 2^32: [0x8E 0xFE 0xFE 0xFF 0x00] */ /** * Mode for encoding VarInts. * * Currently there is no support for signed encodings. The default mode will not * compile with signed values, and the legacy "nonnegative signed" mode will * accept signed values, but improperly encode and decode them if they are * negative. In the future, the DEFAULT mode could be extended to support * negative numbers in a backwards compatible way, and additional modes could be * added to support different varint formats (e.g. zigzag encoding). */ enum class VarIntMode { DEFAULT, NONNEGATIVE_SIGNED }; template struct CheckVarIntMode { constexpr CheckVarIntMode() { static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned::value, "Unsigned type required with mode DEFAULT."); static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed::value, "Signed type required with mode NONNEGATIVE_SIGNED."); } }; template inline unsigned int GetSizeOfVarInt(I n) { CheckVarIntMode(); int nRet = 0; while (true) { nRet++; if (n <= 0x7F) { return nRet; } n = (n >> 7) - 1; } } template inline void WriteVarInt(CSizeComputer &os, I n); template void WriteVarInt(Stream &os, I n) { CheckVarIntMode(); uint8_t tmp[(sizeof(n) * 8 + 6) / 7]; int len = 0; while (true) { tmp[len] = (n & 0x7F) | (len ? 0x80 : 0x00); if (n <= 0x7F) { break; } n = (n >> 7) - 1; len++; } do { ser_writedata8(os, tmp[len]); } while (len--); } template I ReadVarInt(Stream &is) { CheckVarIntMode(); I n = 0; while (true) { uint8_t chData = ser_readdata8(is); if (n > (std::numeric_limits::max() >> 7)) { throw std::ios_base::failure("ReadVarInt(): size too large"); } n = (n << 7) | (chData & 0x7F); if ((chData & 0x80) == 0) { return n; } if (n == std::numeric_limits::max()) { throw std::ios_base::failure("ReadVarInt(): size too large"); } n++; } } /** * Simple wrapper class to serialize objects using a formatter; used by * Using(). */ template class Wrapper { static_assert(std::is_lvalue_reference::value, "Wrapper needs an lvalue reference type T"); protected: T m_object; public: explicit Wrapper(T obj) : m_object(obj) {} template void Serialize(Stream &s) const { Formatter().Ser(s, m_object); } template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } }; /** * Cause serialization/deserialization of an object to be done using a * specified formatter class. * * To use this, you need a class Formatter that has public functions Ser(stream, * const object&) for serialization, and Unser(stream, object&) for * deserialization. Serialization routines (inside READWRITE, or directly with * << and >> operators), can then use Using(object). * * This works by constructing a Wrapper-wrapped version of object, * where T is const during serialization, and non-const during deserialization, * which maintains const correctness. */ template static inline Wrapper Using(T &&t) { return Wrapper(t); } #define VARINT_MODE(obj, mode) Using>(obj) #define VARINT(obj) Using>(obj) #define COMPACTSIZE(obj) Using(obj) #define LIMITED_STRING(obj, n) LimitedString(REF(obj)) /** * Serialization wrapper class for integers in VarInt format. */ template struct VarIntFormatter { template void Ser(Stream &s, I v) { WriteVarInt::type>(s, v); } template void Unser(Stream &s, I &v) { v = ReadVarInt::type>(s); } }; /** Serialization wrapper class for big-endian integers. * * Use this wrapper around integer types that are stored in memory in native * byte order, but serialized in big endian notation. This is only intended * to implement serializers that are compatible with existing formats, and * its use is not recommended for new data structures. * * Only 16-bit types are supported for now. */ template class BigEndian { protected: I &m_val; public: explicit BigEndian(I &val) : m_val(val) { static_assert(std::is_unsigned::value, "BigEndian type must be unsigned integer"); static_assert(sizeof(I) == 2 && std::numeric_limits::min() == 0 && std::numeric_limits::max() == std::numeric_limits::max(), "Unsupported BigEndian size"); } template void Serialize(Stream &s) const { ser_writedata16be(s, m_val); } template void Unserialize(Stream &s) { m_val = ser_readdata16be(s); } }; /** Formatter for integers in CompactSize format. */ struct CompactSizeFormatter { template void Unser(Stream &s, I &v) { uint64_t n = ReadCompactSize(s); if (n < std::numeric_limits::min() || n > std::numeric_limits::max()) { throw std::ios_base::failure("CompactSize exceeds limit of type"); } v = n; } template void Ser(Stream &s, I v) { static_assert(std::is_unsigned::value, "CompactSize only supported for unsigned integers"); static_assert(std::numeric_limits::max() <= std::numeric_limits::max(), "CompactSize only supports 64-bit integers and below"); WriteCompactSize(s, v); } }; template class LimitedString { protected: std::string &string; public: explicit LimitedString(std::string &_string) : string(_string) {} template void Unserialize(Stream &s) { size_t size = ReadCompactSize(s); if (size > Limit) { throw std::ios_base::failure("String length limit exceeded"); } string.resize(size); if (size != 0) { s.read((char *)string.data(), size); } } template void Serialize(Stream &s) const { WriteCompactSize(s, string.size()); if (!string.empty()) { s.write((char *)string.data(), string.size()); } } }; template BigEndian WrapBigEndian(I &n) { return BigEndian(n); } /** * Formatter to serialize/deserialize vector elements using another formatter * * Example: * struct X { * std::vector v; * SERIALIZE_METHODS(X, obj) { * READWRITE(Using>(obj.v)); * } * }; * will define a struct that contains a vector of uint64_t, which is serialized * as a vector of VarInt-encoded integers. * * V is not required to be an std::vector type. It works for any class that - * exposes a value_type, size, reserve, push_back, and const iterators. + * exposes a value_type, size, reserve, emplace_back, back, and const iterators. */ template struct VectorFormatter { template void Ser(Stream &s, const V &v) { + Formatter formatter; WriteCompactSize(s, v.size()); for (const typename V::value_type &elem : v) { - s << Using(elem); + formatter.Ser(s, elem); } } template void Unser(Stream &s, V &v) { + Formatter formatter; v.clear(); size_t size = ReadCompactSize(s); size_t allocated = 0; while (allocated < size) { // For DoS prevention, do not blindly allocate as much as the stream // claims to contain. Instead, allocate in 5MiB batches, so that an // attacker actually needs to provide X MiB of data to make us // allocate X+5 Mib. static_assert(sizeof(typename V::value_type) <= MAX_VECTOR_ALLOCATE, "Vector element size too large"); allocated = std::min(size, allocated + MAX_VECTOR_ALLOCATE / sizeof(typename V::value_type)); v.reserve(allocated); while (v.size() < allocated) { - typename V::value_type val; - s >> Using(val); - v.push_back(std::move(val)); + v.emplace_back(); + formatter.Unser(s, v.back()); } } }; }; /** * Forward declarations */ /** * string */ template void Serialize(Stream &os, const std::basic_string &str); template void Unserialize(Stream &is, std::basic_string &str); /** * prevector * prevectors of uint8_t are a special case and are intended to be serialized as * a single opaque blob. */ template void Serialize_impl(Stream &os, const prevector &v, const uint8_t &); template void Serialize_impl(Stream &os, const prevector &v, const V &); template inline void Serialize(Stream &os, const prevector &v); template void Unserialize_impl(Stream &is, prevector &v, const uint8_t &); template void Unserialize_impl(Stream &is, prevector &v, const V &); template inline void Unserialize(Stream &is, prevector &v); /** * vector * vectors of uint8_t are a special case and are intended to be serialized as a * single opaque blob. */ template void Serialize_impl(Stream &os, const std::vector &v, const uint8_t &); template void Serialize_impl(Stream &os, const std::vector &v, const bool &); template void Serialize_impl(Stream &os, const std::vector &v, const V &); template inline void Serialize(Stream &os, const std::vector &v); template void Unserialize_impl(Stream &is, std::vector &v, const uint8_t &); template void Unserialize_impl(Stream &is, std::vector &v, const V &); template inline void Unserialize(Stream &is, std::vector &v); /** * pair */ template void Serialize(Stream &os, const std::pair &item); template void Unserialize(Stream &is, std::pair &item); /** * map */ template void Serialize(Stream &os, const std::map &m); template void Unserialize(Stream &is, std::map &m); /** * set */ template void Serialize(Stream &os, const std::set &m); template void Unserialize(Stream &is, std::set &m); /** * shared_ptr */ template void Serialize(Stream &os, const std::shared_ptr &p); template void Unserialize(Stream &os, std::shared_ptr &p); /** * unique_ptr */ template void Serialize(Stream &os, const std::unique_ptr &p); template void Unserialize(Stream &os, std::unique_ptr &p); /** * If none of the specialized versions above matched, default to calling member * function. */ template inline void Serialize(Stream &os, const T &a) { a.Serialize(os); } template inline void Unserialize(Stream &is, T &&a) { a.Unserialize(is); } /** * Default formatter. Serializes objects as themselves. * * The vector/prevector serialization code passes this to VectorFormatter * to enable reusing that logic. It shouldn't be needed elsewhere. */ struct DefaultFormatter { template static void Ser(Stream &s, const T &t) { Serialize(s, t); } template static void Unser(Stream &s, T &t) { Unserialize(s, t); } }; /** * string */ template void Serialize(Stream &os, const std::basic_string &str) { WriteCompactSize(os, str.size()); if (!str.empty()) { os.write((char *)str.data(), str.size() * sizeof(C)); } } template void Unserialize(Stream &is, std::basic_string &str) { size_t nSize = ReadCompactSize(is); str.resize(nSize); if (nSize != 0) { is.read((char *)str.data(), nSize * sizeof(C)); } } /** * prevector */ template void Serialize_impl(Stream &os, const prevector &v, const uint8_t &) { WriteCompactSize(os, v.size()); if (!v.empty()) { os.write((char *)v.data(), v.size() * sizeof(T)); } } template void Serialize_impl(Stream &os, const prevector &v, const V &) { Serialize(os, Using>(v)); } template inline void Serialize(Stream &os, const prevector &v) { Serialize_impl(os, v, T()); } template void Unserialize_impl(Stream &is, prevector &v, const uint8_t &) { // Limit size per read so bogus size value won't cause out of memory v.clear(); size_t nSize = ReadCompactSize(is); size_t i = 0; while (i < nSize) { size_t blk = std::min(nSize - i, size_t(1 + 4999999 / sizeof(T))); v.resize_uninitialized(i + blk); is.read((char *)&v[i], blk * sizeof(T)); i += blk; } } template void Unserialize_impl(Stream &is, prevector &v, const V &) { Unserialize(is, Using>(v)); } template inline void Unserialize(Stream &is, prevector &v) { Unserialize_impl(is, v, T()); } /** * vector */ template void Serialize_impl(Stream &os, const std::vector &v, const uint8_t &) { WriteCompactSize(os, v.size()); if (!v.empty()) { os.write((char *)v.data(), v.size() * sizeof(T)); } } template void Serialize_impl(Stream &os, const std::vector &v, const bool &) { // A special case for std::vector, as dereferencing // std::vector::const_iterator does not result in a const bool& // due to std::vector's special casing for bool arguments. WriteCompactSize(os, v.size()); for (bool elem : v) { ::Serialize(os, elem); } } template void Serialize_impl(Stream &os, const std::vector &v, const V &) { Serialize(os, Using>(v)); } template inline void Serialize(Stream &os, const std::vector &v) { Serialize_impl(os, v, T()); } template void Unserialize_impl(Stream &is, std::vector &v, const uint8_t &) { // Limit size per read so bogus size value won't cause out of memory v.clear(); size_t nSize = ReadCompactSize(is); size_t i = 0; while (i < nSize) { size_t blk = std::min(nSize - i, size_t(1 + 4999999 / sizeof(T))); v.resize(i + blk); is.read((char *)&v[i], blk * sizeof(T)); i += blk; } } template void Unserialize_impl(Stream &is, std::vector &v, const V &) { Unserialize(is, Using>(v)); } template inline void Unserialize(Stream &is, std::vector &v) { Unserialize_impl(is, v, T()); } /** * pair */ template void Serialize(Stream &os, const std::pair &item) { Serialize(os, item.first); Serialize(os, item.second); } template void Unserialize(Stream &is, std::pair &item) { Unserialize(is, item.first); Unserialize(is, item.second); } /** * map */ template void Serialize(Stream &os, const std::map &m) { WriteCompactSize(os, m.size()); for (const auto &entry : m) { Serialize(os, entry); } } template void Unserialize(Stream &is, std::map &m) { m.clear(); size_t nSize = ReadCompactSize(is); typename std::map::iterator mi = m.begin(); for (size_t i = 0; i < nSize; i++) { std::pair item; Unserialize(is, item); mi = m.insert(mi, item); } } /** * set */ template void Serialize(Stream &os, const std::set &m) { WriteCompactSize(os, m.size()); for (const K &i : m) { Serialize(os, i); } } template void Unserialize(Stream &is, std::set &m) { m.clear(); size_t nSize = ReadCompactSize(is); typename std::set::iterator it = m.begin(); for (size_t i = 0; i < nSize; i++) { K key; Unserialize(is, key); it = m.insert(it, key); } } /** * unique_ptr */ template void Serialize(Stream &os, const std::unique_ptr &p) { Serialize(os, *p); } template void Unserialize(Stream &is, std::unique_ptr &p) { p.reset(new T(deserialize, is)); } /** * shared_ptr */ template void Serialize(Stream &os, const std::shared_ptr &p) { Serialize(os, *p); } template void Unserialize(Stream &is, std::shared_ptr &p) { p = std::make_shared(deserialize, is); } /** * Support for ADD_SERIALIZE_METHODS and READWRITE macro */ struct CSerActionSerialize { constexpr bool ForRead() const { return false; } }; struct CSerActionUnserialize { constexpr bool ForRead() const { return true; } }; /** * ::GetSerializeSize implementations * * Computing the serialized size of objects is done through a special stream * object of type CSizeComputer, which only records the number of bytes written * to it. * * If your Serialize or SerializationOp method has non-trivial overhead for * serialization, it may be worthwhile to implement a specialized version for * CSizeComputer, which uses the s.seek() method to record bytes that would * be written instead. */ class CSizeComputer { protected: size_t nSize; const int nVersion; public: explicit CSizeComputer(int nVersionIn) : nSize(0), nVersion(nVersionIn) {} void write(const char *psz, size_t _nSize) { this->nSize += _nSize; } /** Pretend _nSize bytes are written, without specifying them. */ void seek(size_t _nSize) { this->nSize += _nSize; } template CSizeComputer &operator<<(const T &obj) { ::Serialize(*this, obj); return (*this); } size_t size() const { return nSize; } int GetVersion() const { return nVersion; } }; template void SerializeMany(Stream &s) {} template void SerializeMany(Stream &s, const Arg &arg, const Args &... args) { ::Serialize(s, arg); ::SerializeMany(s, args...); } template inline void UnserializeMany(Stream &s) {} template inline void UnserializeMany(Stream &s, Arg &&arg, Args &&... args) { ::Unserialize(s, arg); ::UnserializeMany(s, args...); } template inline void SerReadWriteMany(Stream &s, CSerActionSerialize ser_action, const Args &... args) { ::SerializeMany(s, args...); } template inline void SerReadWriteMany(Stream &s, CSerActionUnserialize ser_action, Args &&... args) { ::UnserializeMany(s, args...); } template inline void WriteVarInt(CSizeComputer &s, I n) { s.seek(GetSizeOfVarInt(n)); } inline void WriteCompactSize(CSizeComputer &s, uint64_t nSize) { s.seek(GetSizeOfCompactSize(nSize)); } template size_t GetSerializeSize(const T &t, int nVersion = 0) { return (CSizeComputer(nVersion) << t).size(); } template size_t GetSerializeSizeMany(int nVersion, const T &... t) { CSizeComputer sc(nVersion); SerializeMany(sc, t...); return sc.size(); } #endif // BITCOIN_SERIALIZE_H