diff --git a/src/blockencodings.h b/src/blockencodings.h index 9231ca792..33fca9fa2 100644 --- a/src/blockencodings.h +++ b/src/blockencodings.h @@ -1,159 +1,137 @@ // Copyright (c) 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_BLOCKENCODINGS_H #define BITCOIN_BLOCKENCODINGS_H #include +#include class Config; class CTxMemPool; // Transaction compression schemes for compact block relay can be introduced by // writing an actual formatter here. using TransactionCompression = DefaultFormatter; -class DifferenceFormatter { - uint64_t m_shift = 0; - -public: - template void Ser(Stream &s, I v) { - if (v < m_shift || v >= std::numeric_limits::max()) { - throw std::ios_base::failure("differential value overflow"); - } - WriteCompactSize(s, v - m_shift); - m_shift = uint64_t(v) + 1; - } - template void Unser(Stream &s, I &v) { - uint64_t n = ReadCompactSize(s); - m_shift += n; - if (m_shift < n || m_shift >= std::numeric_limits::max() || - m_shift < std::numeric_limits::min() || - m_shift > std::numeric_limits::max()) { - throw std::ios_base::failure("differential value overflow"); - } - v = I(m_shift++); - } -}; - class BlockTransactionsRequest { public: // A BlockTransactionsRequest message BlockHash blockhash; std::vector indices; SERIALIZE_METHODS(BlockTransactionsRequest, obj) { READWRITE(obj.blockhash, Using>(obj.indices)); } }; class BlockTransactions { public: // A BlockTransactions message BlockHash blockhash; std::vector txn; BlockTransactions() {} explicit BlockTransactions(const BlockTransactionsRequest &req) : blockhash(req.blockhash), txn(req.indices.size()) {} SERIALIZE_METHODS(BlockTransactions, obj) { READWRITE(obj.blockhash, Using>(obj.txn)); } }; // Dumb serialization/storage-helper for CBlockHeaderAndShortTxIDs and // PartiallyDownloadedBlock struct PrefilledTransaction { // Used as an offset since last prefilled tx in CBlockHeaderAndShortTxIDs, // as a proper transaction-in-block-index in PartiallyDownloadedBlock uint32_t index; CTransactionRef tx; SERIALIZE_METHODS(PrefilledTransaction, obj) { READWRITE(COMPACTSIZE(obj.index), Using(obj.tx)); } }; typedef enum ReadStatus_t { READ_STATUS_OK, // Invalid object, peer is sending bogus crap. // FIXME: differenciate bogus crap from crap that do not fit our policy. READ_STATUS_INVALID, // Failed to process object. READ_STATUS_FAILED, // Used only by FillBlock to indicate a failure in CheckBlock. READ_STATUS_CHECKBLOCK_FAILED, } ReadStatus; class CBlockHeaderAndShortTxIDs { private: mutable uint64_t shorttxidk0, shorttxidk1; uint64_t nonce; void FillShortTxIDSelector() const; friend class PartiallyDownloadedBlock; protected: std::vector shorttxids; std::vector prefilledtxn; public: static constexpr int SHORTTXIDS_LENGTH = 6; CBlockHeader header; // Dummy for deserialization CBlockHeaderAndShortTxIDs() {} explicit CBlockHeaderAndShortTxIDs(const CBlock &block); uint64_t GetShortID(const TxHash &txhash) const; size_t BlockTxCount() const { return shorttxids.size() + prefilledtxn.size(); } SERIALIZE_METHODS(CBlockHeaderAndShortTxIDs, obj) { READWRITE( obj.header, obj.nonce, Using>>( obj.shorttxids), obj.prefilledtxn); if (ser_action.ForRead()) { if (obj.BlockTxCount() > std::numeric_limits::max()) { throw std::ios_base::failure("indices overflowed 32 bits"); } obj.FillShortTxIDSelector(); } } }; class PartiallyDownloadedBlock { protected: std::vector txns_available; size_t prefilled_count = 0, mempool_count = 0, extra_count = 0; const CTxMemPool *pool; const Config *config; public: CBlockHeader header; PartiallyDownloadedBlock(const Config &configIn, CTxMemPool *poolIn) : pool(poolIn), config(&configIn) {} // extra_txn is a list of extra transactions to look at, in form. ReadStatus InitData(const CBlockHeaderAndShortTxIDs &cmpctblock, const std::vector> &extra_txn); bool IsTxAvailable(size_t index) const; ReadStatus FillBlock(CBlock &block, const std::vector &vtx_missing); }; #endif // BITCOIN_BLOCKENCODINGS_H diff --git a/src/serialize.h b/src/serialize.h index 1c7326de9..f94c52e06 100644 --- a/src/serialize.h +++ b/src/serialize.h @@ -1,1215 +1,1248 @@ // 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 #include /** * The maximum size of a serialized object in bytes or number of elements * (for eg vectors) when the size is encoded as CompactSize. */ static constexpr 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{}; //! 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))) #define SER_READ(obj, code) \ ::SerRead( \ s, ser_action, obj, \ [&](Stream &s, typename std::remove_const::type &obj) { code; }) #define SER_WRITE(obj, code) \ ::SerWrite(s, ser_action, obj, [&](Stream &s, const Type &obj) { code; }) /** * 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; } /** * Decode a CompactSize-encoded variable-length integer. * * As these are primarily used to encode the size of vector-like serializations, * by default a range check is performed. When used as a generic number * encoding, range_check should be set to false. */ template uint64_t ReadCompactSize(Stream &is, bool range_check = true) { 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 (range_check && 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) Using>(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 custom integers and enums. * * It permits specifying the serialized size (1 to 8 bytes) and endianness. * * Use the big endian mode for values 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. */ template struct CustomUintFormatter { static_assert(Bytes > 0 && Bytes <= 8, "CustomUintFormatter Bytes out of range"); static constexpr uint64_t MAX = 0xffffffffffffffff >> (8 * (8 - Bytes)); template void Ser(Stream &s, I v) { if (v < 0 || v > MAX) { throw std::ios_base::failure( "CustomUintFormatter value out of range"); } if (BigEndian) { uint64_t raw = htobe64(v); s.write(((const char *)&raw) + 8 - Bytes, Bytes); } else { uint64_t raw = htole64(v); s.write((const char *)&raw, Bytes); } } template void Unser(Stream &s, I &v) { using U = typename std::conditional::value, std::underlying_type, std::common_type>::type::type; static_assert(std::numeric_limits::max() >= MAX && std::numeric_limits::min() <= 0, "Assigned type too small"); uint64_t raw = 0; if (BigEndian) { s.read(((char *)&raw) + 8 - Bytes, Bytes); v = static_cast(be64toh(raw)); } else { s.read((char *)&raw, Bytes); v = static_cast(le64toh(raw)); } } }; template using BigEndianFormatter = CustomUintFormatter; /** Formatter for integers in CompactSize format. */ template struct CompactSizeFormatter { template void Unser(Stream &s, I &v) { uint64_t n = ReadCompactSize(s, RangeCheck); 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 struct LimitedStringFormatter { template void Unser(Stream &s, std::string &v) { size_t size = ReadCompactSize(s); if (size > Limit) { throw std::ios_base::failure("String length limit exceeded"); } v.resize(size); if (size != 0) { s.read((char *)v.data(), size); } } template void Ser(Stream &s, const std::string &v) { s << v; } }; /** * 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, 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) { 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) { v.emplace_back(); formatter.Unser(s, v.back()); } } }; }; +/** + * Helper for differentially encoded Compact Size integers in lists. + * + * Instead of using raw indexes, the number encoded is the difference between + * the current index and the previous index, minus one. For example, a first + * index of 0 implies a real index of 0, a second index of 0 thereafter refers + * to a real index of 1, etc. + * + * To be used with a VectorFormatter. + */ +class DifferenceFormatter { + uint64_t m_shift = 0; + +public: + template void Ser(Stream &s, I v) { + if (v < m_shift || v >= std::numeric_limits::max()) { + throw std::ios_base::failure("differential value overflow"); + } + WriteCompactSize(s, v - m_shift); + m_shift = uint64_t(v) + 1; + } + template void Unser(Stream &s, I &v) { + uint64_t n = ReadCompactSize(s); + m_shift += n; + if (m_shift < n || m_shift >= std::numeric_limits::max() || + m_shift < std::numeric_limits::min() || + m_shift > std::numeric_limits::max()) { + throw std::ios_base::failure("differential value overflow"); + } + v = I(m_shift++); + } +}; + /** * 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); /** * RCUPtr */ template void Serialize(Stream &os, const RCUPtr &p); template void Unserialize(Stream &os, RCUPtr &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); } /** * RCUPtr */ template void Serialize(Stream &os, const RCUPtr &p) { Serialize(os, *p); } template void Unserialize(Stream &is, RCUPtr &p) { p = RCUPtr::make(deserialize, is); } /** * Support for 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 SerRead(Stream &s, CSerActionSerialize ser_action, Type &&, Fn &&) { } template inline void SerRead(Stream &s, CSerActionUnserialize ser_action, Type &&obj, Fn &&fn) { fn(s, std::forward(obj)); } template inline void SerWrite(Stream &s, CSerActionSerialize ser_action, Type &&obj, Fn &&fn) { fn(s, std::forward(obj)); } template inline void SerWrite(Stream &s, CSerActionUnserialize ser_action, Type &&, Fn &&) {} 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 diff --git a/src/test/serialize_tests.cpp b/src/test/serialize_tests.cpp index 6f14abaa5..c80a23d0f 100644 --- a/src/test/serialize_tests.cpp +++ b/src/test/serialize_tests.cpp @@ -1,455 +1,513 @@ // Copyright (c) 2012-2019 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include #include #include #include #include #include BOOST_FIXTURE_TEST_SUITE(serialize_tests, BasicTestingSetup) class CSerializeMethodsTestSingle { protected: int intval; bool boolval; std::string stringval; char charstrval[16]; CTransactionRef txval; avalanche::ProofRef proofval; public: CSerializeMethodsTestSingle() = default; CSerializeMethodsTestSingle(int intvalin, bool boolvalin, std::string stringvalin, const char *charstrvalin, const CTransactionRef &txvalin, const avalanche::ProofRef &proofvalin) : intval(intvalin), boolval(boolvalin), stringval(std::move(stringvalin)), txval(txvalin), proofval(proofvalin) { memcpy(charstrval, charstrvalin, sizeof(charstrval)); } SERIALIZE_METHODS(CSerializeMethodsTestSingle, obj) { READWRITE(obj.intval); READWRITE(obj.boolval); READWRITE(obj.stringval); READWRITE(obj.charstrval); READWRITE(obj.txval); READWRITE(obj.proofval); } bool operator==(const CSerializeMethodsTestSingle &rhs) { return intval == rhs.intval && boolval == rhs.boolval && stringval == rhs.stringval && strcmp(charstrval, rhs.charstrval) == 0 && *txval == *rhs.txval && proofval->getId() == rhs.proofval->getId(); } }; class CSerializeMethodsTestMany : public CSerializeMethodsTestSingle { public: using CSerializeMethodsTestSingle::CSerializeMethodsTestSingle; SERIALIZE_METHODS(CSerializeMethodsTestMany, obj) { READWRITE(obj.intval, obj.boolval, obj.stringval, obj.charstrval, obj.txval, obj.proofval); } }; BOOST_AUTO_TEST_CASE(sizes) { BOOST_CHECK_EQUAL(sizeof(char), GetSerializeSize(char(0))); BOOST_CHECK_EQUAL(sizeof(int8_t), GetSerializeSize(int8_t(0))); BOOST_CHECK_EQUAL(sizeof(uint8_t), GetSerializeSize(uint8_t(0))); BOOST_CHECK_EQUAL(sizeof(int16_t), GetSerializeSize(int16_t(0))); BOOST_CHECK_EQUAL(sizeof(uint16_t), GetSerializeSize(uint16_t(0))); BOOST_CHECK_EQUAL(sizeof(int32_t), GetSerializeSize(int32_t(0))); BOOST_CHECK_EQUAL(sizeof(uint32_t), GetSerializeSize(uint32_t(0))); BOOST_CHECK_EQUAL(sizeof(int64_t), GetSerializeSize(int64_t(0))); BOOST_CHECK_EQUAL(sizeof(uint64_t), GetSerializeSize(uint64_t(0))); BOOST_CHECK_EQUAL(sizeof(float), GetSerializeSize(float(0))); BOOST_CHECK_EQUAL(sizeof(double), GetSerializeSize(double(0))); // Bool is serialized as char BOOST_CHECK_EQUAL(sizeof(char), GetSerializeSize(bool(0))); // Sanity-check GetSerializeSize and c++ type matching BOOST_CHECK_EQUAL(GetSerializeSize(char(0)), 1U); BOOST_CHECK_EQUAL(GetSerializeSize(int8_t(0)), 1U); BOOST_CHECK_EQUAL(GetSerializeSize(uint8_t(0)), 1U); BOOST_CHECK_EQUAL(GetSerializeSize(int16_t(0)), 2U); BOOST_CHECK_EQUAL(GetSerializeSize(uint16_t(0)), 2U); BOOST_CHECK_EQUAL(GetSerializeSize(int32_t(0)), 4U); BOOST_CHECK_EQUAL(GetSerializeSize(uint32_t(0)), 4U); BOOST_CHECK_EQUAL(GetSerializeSize(int64_t(0)), 8U); BOOST_CHECK_EQUAL(GetSerializeSize(uint64_t(0)), 8U); BOOST_CHECK_EQUAL(GetSerializeSize(float(0)), 4U); BOOST_CHECK_EQUAL(GetSerializeSize(double(0)), 8U); BOOST_CHECK_EQUAL(GetSerializeSize(bool(0)), 1U); } BOOST_AUTO_TEST_CASE(floats_conversion) { // Choose values that map unambiguously to binary floating point to avoid // rounding issues at the compiler side. BOOST_CHECK_EQUAL(ser_uint32_to_float(0x00000000), 0.0F); BOOST_CHECK_EQUAL(ser_uint32_to_float(0x3f000000), 0.5F); BOOST_CHECK_EQUAL(ser_uint32_to_float(0x3f800000), 1.0F); BOOST_CHECK_EQUAL(ser_uint32_to_float(0x40000000), 2.0F); BOOST_CHECK_EQUAL(ser_uint32_to_float(0x40800000), 4.0F); BOOST_CHECK_EQUAL(ser_uint32_to_float(0x44444444), 785.066650390625F); BOOST_CHECK_EQUAL(ser_float_to_uint32(0.0F), 0x00000000U); BOOST_CHECK_EQUAL(ser_float_to_uint32(0.5F), 0x3f000000U); BOOST_CHECK_EQUAL(ser_float_to_uint32(1.0F), 0x3f800000U); BOOST_CHECK_EQUAL(ser_float_to_uint32(2.0F), 0x40000000U); BOOST_CHECK_EQUAL(ser_float_to_uint32(4.0F), 0x40800000U); BOOST_CHECK_EQUAL(ser_float_to_uint32(785.066650390625F), 0x44444444U); } BOOST_AUTO_TEST_CASE(doubles_conversion) { // Choose values that map unambiguously to binary floating point to avoid // rounding issues at the compiler side. BOOST_CHECK_EQUAL(ser_uint64_to_double(0x0000000000000000ULL), 0.0); BOOST_CHECK_EQUAL(ser_uint64_to_double(0x3fe0000000000000ULL), 0.5); BOOST_CHECK_EQUAL(ser_uint64_to_double(0x3ff0000000000000ULL), 1.0); BOOST_CHECK_EQUAL(ser_uint64_to_double(0x4000000000000000ULL), 2.0); BOOST_CHECK_EQUAL(ser_uint64_to_double(0x4010000000000000ULL), 4.0); BOOST_CHECK_EQUAL(ser_uint64_to_double(0x4088888880000000ULL), 785.066650390625); BOOST_CHECK_EQUAL(ser_double_to_uint64(0.0), 0x0000000000000000ULL); BOOST_CHECK_EQUAL(ser_double_to_uint64(0.5), 0x3fe0000000000000ULL); BOOST_CHECK_EQUAL(ser_double_to_uint64(1.0), 0x3ff0000000000000ULL); BOOST_CHECK_EQUAL(ser_double_to_uint64(2.0), 0x4000000000000000ULL); BOOST_CHECK_EQUAL(ser_double_to_uint64(4.0), 0x4010000000000000ULL); BOOST_CHECK_EQUAL(ser_double_to_uint64(785.066650390625), 0x4088888880000000ULL); } /* Python code to generate the below hashes: def reversed_hex(x): return b''.join(reversed(x)).hex().encode() def dsha256(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() reversed_hex(dsha256(b''.join(struct.pack('> j; BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i); } } BOOST_AUTO_TEST_CASE(doubles) { CDataStream ss(SER_DISK, 0); // encode for (int i = 0; i < 1000; i++) { ss << double(i); } BOOST_CHECK(Hash(ss) == uint256S("43d0c82591953c4eafe114590d392676a01585d25b25d433557f0" "d7878b23f96")); // decode for (int i = 0; i < 1000; i++) { double j; ss >> j; BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i); } } BOOST_AUTO_TEST_CASE(varints) { // encode CDataStream ss(SER_DISK, 0); CDataStream::size_type size = 0; for (int i = 0; i < 100000; i++) { ss << VARINT_MODE(i, VarIntMode::NONNEGATIVE_SIGNED); size += ::GetSerializeSize(VARINT_MODE(i, VarIntMode::NONNEGATIVE_SIGNED)); BOOST_CHECK(size == ss.size()); } for (uint64_t i = 0; i < 100000000000ULL; i += 999999937) { ss << VARINT(i); size += ::GetSerializeSize(VARINT(i)); BOOST_CHECK(size == ss.size()); } // decode for (int i = 0; i < 100000; i++) { int j = -1; ss >> VARINT_MODE(j, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i); } for (uint64_t i = 0; i < 100000000000ULL; i += 999999937) { uint64_t j = std::numeric_limits::max(); ss >> VARINT(j); BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i); } } BOOST_AUTO_TEST_CASE(varints_bitpatterns) { CDataStream ss(SER_DISK, 0); ss << VARINT_MODE(0, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "00"); ss.clear(); ss << VARINT_MODE(0x7f, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "7f"); ss.clear(); ss << VARINT_MODE((int8_t)0x7f, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "7f"); ss.clear(); ss << VARINT_MODE(0x80, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "8000"); ss.clear(); ss << VARINT((uint8_t)0x80); BOOST_CHECK_EQUAL(HexStr(ss), "8000"); ss.clear(); ss << VARINT_MODE(0x1234, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "a334"); ss.clear(); ss << VARINT_MODE((int16_t)0x1234, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "a334"); ss.clear(); ss << VARINT_MODE(0xffff, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "82fe7f"); ss.clear(); ss << VARINT((uint16_t)0xffff); BOOST_CHECK_EQUAL(HexStr(ss), "82fe7f"); ss.clear(); ss << VARINT_MODE(0x123456, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "c7e756"); ss.clear(); ss << VARINT_MODE((int32_t)0x123456, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "c7e756"); ss.clear(); ss << VARINT(0x80123456U); BOOST_CHECK_EQUAL(HexStr(ss), "86ffc7e756"); ss.clear(); ss << VARINT((uint32_t)0x80123456U); BOOST_CHECK_EQUAL(HexStr(ss), "86ffc7e756"); ss.clear(); ss << VARINT(0xffffffff); BOOST_CHECK_EQUAL(HexStr(ss), "8efefefe7f"); ss.clear(); ss << VARINT_MODE(0x7fffffffffffffffLL, VarIntMode::NONNEGATIVE_SIGNED); BOOST_CHECK_EQUAL(HexStr(ss), "fefefefefefefefe7f"); ss.clear(); ss << VARINT(0xffffffffffffffffULL); BOOST_CHECK_EQUAL(HexStr(ss), "80fefefefefefefefe7f"); ss.clear(); } static bool isTooLargeException(const std::ios_base::failure &ex) { std::ios_base::failure expectedException( "ReadCompactSize(): size too large"); // The string returned by what() can be different for different platforms. // Instead of directly comparing the ex.what() with an expected string, // create an instance of exception to see if ex.what() matches the expected // explanatory string returned by the exception instance. return strcmp(expectedException.what(), ex.what()) == 0; } BOOST_AUTO_TEST_CASE(compactsize) { CDataStream ss(SER_DISK, 0); std::vector::size_type i, j; for (i = 1; i <= MAX_SIZE; i *= 2) { WriteCompactSize(ss, i - 1); WriteCompactSize(ss, i); } for (i = 1; i <= MAX_SIZE; i *= 2) { j = ReadCompactSize(ss); BOOST_CHECK_MESSAGE((i - 1) == j, "decoded:" << j << " expected:" << (i - 1)); j = ReadCompactSize(ss); BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i); } WriteCompactSize(ss, MAX_SIZE); BOOST_CHECK_EQUAL(ReadCompactSize(ss), MAX_SIZE); WriteCompactSize(ss, MAX_SIZE + 1); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isTooLargeException); WriteCompactSize(ss, std::numeric_limits::max()); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isTooLargeException); WriteCompactSize(ss, std::numeric_limits::max()); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isTooLargeException); } static bool isCanonicalException(const std::ios_base::failure &ex) { std::ios_base::failure expectedException("non-canonical ReadCompactSize()"); // The string returned by what() can be different for different platforms. // Instead of directly comparing the ex.what() with an expected string, // create an instance of exception to see if ex.what() matches the expected // explanatory string returned by the exception instance. return strcmp(expectedException.what(), ex.what()) == 0; } BOOST_AUTO_TEST_CASE(vector_bool) { std::vector vec1{1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1}; std::vector vec2{1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1}; BOOST_CHECK(vec1 == std::vector(vec2.begin(), vec2.end())); BOOST_CHECK(SerializeHash(vec1) == SerializeHash(vec2)); } BOOST_AUTO_TEST_CASE(noncanonical) { // Write some non-canonical CompactSize encodings, and make sure an // exception is thrown when read back. CDataStream ss(SER_DISK, 0); std::vector::size_type n; // zero encoded with three bytes: ss.write("\xfd\x00\x00", 3); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); // 0xfc encoded with three bytes: ss.write("\xfd\xfc\x00", 3); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); // 0xfd encoded with three bytes is OK: ss.write("\xfd\xfd\x00", 3); n = ReadCompactSize(ss); BOOST_CHECK(n == 0xfd); // zero encoded with five bytes: ss.write("\xfe\x00\x00\x00\x00", 5); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); // 0xffff encoded with five bytes: ss.write("\xfe\xff\xff\x00\x00", 5); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); // zero encoded with nine bytes: ss.write("\xff\x00\x00\x00\x00\x00\x00\x00\x00", 9); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); // 0x01ffffff encoded with nine bytes: ss.write("\xff\xff\xff\xff\x01\x00\x00\x00\x00", 9); BOOST_CHECK_EXCEPTION(ReadCompactSize(ss), std::ios_base::failure, isCanonicalException); } BOOST_AUTO_TEST_CASE(insert_delete) { // Test inserting/deleting bytes. CDataStream ss(SER_DISK, 0); BOOST_CHECK_EQUAL(ss.size(), 0U); ss.write("\x00\x01\x02\xff", 4); BOOST_CHECK_EQUAL(ss.size(), 4U); char c = (char)11; // Inserting at beginning/end/middle: ss.insert(ss.begin(), c); BOOST_CHECK_EQUAL(ss.size(), 5U); BOOST_CHECK_EQUAL(ss[0], c); BOOST_CHECK_EQUAL(ss[1], 0); ss.insert(ss.end(), c); BOOST_CHECK_EQUAL(ss.size(), 6U); BOOST_CHECK_EQUAL(ss[4], (char)0xff); BOOST_CHECK_EQUAL(ss[5], c); ss.insert(ss.begin() + 2, c); BOOST_CHECK_EQUAL(ss.size(), 7U); BOOST_CHECK_EQUAL(ss[2], c); // Delete at beginning/end/middle ss.erase(ss.begin()); BOOST_CHECK_EQUAL(ss.size(), 6U); BOOST_CHECK_EQUAL(ss[0], 0); ss.erase(ss.begin() + ss.size() - 1); BOOST_CHECK_EQUAL(ss.size(), 5U); BOOST_CHECK_EQUAL(ss[4], (char)0xff); ss.erase(ss.begin() + 1); BOOST_CHECK_EQUAL(ss.size(), 4U); BOOST_CHECK_EQUAL(ss[0], 0); BOOST_CHECK_EQUAL(ss[1], 1); BOOST_CHECK_EQUAL(ss[2], 2); BOOST_CHECK_EQUAL(ss[3], (char)0xff); // Make sure GetAndClear does the right thing: CSerializeData d; ss.GetAndClear(d); BOOST_CHECK_EQUAL(ss.size(), 0U); } BOOST_AUTO_TEST_CASE(class_methods) { int intval(100); bool boolval(true); std::string stringval("testing"); const char charstrval[16] = "testing charstr"; CMutableTransaction txval; CTransactionRef tx_ref{MakeTransactionRef(txval)}; avalanche::ProofBuilder pb(0, 0, CKey::MakeCompressedKey()); avalanche::ProofRef proofval = pb.build(); CSerializeMethodsTestSingle methodtest1(intval, boolval, stringval, charstrval, tx_ref, proofval); CSerializeMethodsTestMany methodtest2(intval, boolval, stringval, charstrval, tx_ref, proofval); CSerializeMethodsTestSingle methodtest3; CSerializeMethodsTestMany methodtest4; CDataStream ss(SER_DISK, PROTOCOL_VERSION); BOOST_CHECK(methodtest1 == methodtest2); ss << methodtest1; ss >> methodtest4; ss << methodtest2; ss >> methodtest3; BOOST_CHECK(methodtest1 == methodtest2); BOOST_CHECK(methodtest2 == methodtest3); BOOST_CHECK(methodtest3 == methodtest4); CDataStream ss2(SER_DISK, PROTOCOL_VERSION, intval, boolval, stringval, charstrval, txval, proofval); ss2 >> methodtest3; BOOST_CHECK(methodtest3 == methodtest4); } +BOOST_AUTO_TEST_CASE(difference_formatter) { + VectorFormatter formatter; + + { + std::vector indicesIn{0, 1, 2, 5, 10, 20, 50, 100}; + std::vector indicesOut; + + CDataStream ss(SER_DISK, PROTOCOL_VERSION); + formatter.Ser(ss, indicesIn); + + // Check the stream is differentially encoded. Don't care about the + // prefixes and vector length here (assumed to be < 253). + const std::string streamStr = ss.str(); + const std::string differences = + HexStr(streamStr.substr(streamStr.size() - indicesIn.size())); + BOOST_CHECK_EQUAL(differences, "0000000204091d31"); + + formatter.Unser(ss, indicesOut); + BOOST_CHECK_EQUAL_COLLECTIONS(indicesIn.begin(), indicesIn.end(), + indicesOut.begin(), indicesOut.end()); + } + + { + std::vector indicesIn{1, 0}; + + CDataStream ss(SER_DISK, PROTOCOL_VERSION); + BOOST_CHECK_EXCEPTION(formatter.Ser(ss, indicesIn), + std::ios_base::failure, + HasReason("differential value overflow")); + } + + { + std::vector indicesOut; + + // Compute the number of MAX_SIZE increment we need to cause an overflow + const uint64_t overflow = + uint64_t(std::numeric_limits::max()) + 1; + BOOST_CHECK_GE(overflow, MAX_SIZE); + const uint64_t overflowIter = overflow / MAX_SIZE; + + // Make sure the iteration fits in an uint32_t + BOOST_CHECK_LE(overflowIter, std::numeric_limits::max()); + uint32_t remainder = uint32_t(overflow - (MAX_SIZE * overflowIter)); + + CDataStream ss(SER_DISK, PROTOCOL_VERSION); + WriteCompactSize(ss, overflowIter); + for (uint32_t i = 0; i < overflowIter; i++) { + WriteCompactSize(ss, MAX_SIZE); + } + // This is the overflow + WriteCompactSize(ss, remainder); + + BOOST_CHECK_EXCEPTION(formatter.Unser(ss, indicesOut), + std::ios_base::failure, + HasReason("differential value overflow")); + } +} + BOOST_AUTO_TEST_SUITE_END()