Merge #18112: Serialization improvements step 5 (blockencodings)

353f376277ad9b87e03c9ccbc1028c4b6d12e8ea Convert blockencodings.h to new serialization framework (Pieter Wuille)
e574fff53eec4a27c83b765cb69e31d8399047ea Add CustomUintFormatter (Pieter Wuille)
10633398f2dddf929d3f535aa48d138ad5e6c50f Add DifferenceFormatter (Russell Yanofsky)
56dd9f04c701aa3ac340e95065bf83de20373c8b Make VectorFormatter support stateful formatters (Russell Yanofsky)
3ca574cef0b4423f21b2c3efd8f5c9f71d52f219 Convert CCompactSize to proper formatter (Pieter Wuille)

Pull request description:

  This is probably the most involved change in the sequence of changes extracted from #10785.

  In order to implement the differential encoding of BIP152, this change changes `VectorFormatter` to permit a stateful sub-formatter, which is then used by `DifferenceFormatter`. A `CustomUintFormatter` is added as well to do the 48-bit serialization of short ids.

ACKs for top commit:
  laanwj:
    ACK 353f376277ad9b87e03c9ccbc1028c4b6d12e8ea, nice change
  ryanofsky:
    Code review ACK 353f376277ad9b87e03c9ccbc1028c4b6d12e8ea. Only changes since last review are suggested assert change and MASK->MAX rename

Tree-SHA512: 976618991a8be62ba0738725b7cfa166a56cde998ebf1031ba6f28557032f1577b666ac7ae25cd498c0e1e740108c3c56a342620b724df41d6cc9d8bdafac037

3 files changed, 87 insertions, 126 deletions

diff --git a/src/blockencodings.h b/src/blockencodings.h
index 55ed8989bb..be50166cfc 100644
--- a/src/blockencodings.h
+++ b/src/blockencodings.h
@@ -10,18 +10,29 @@
 
 class CTxMemPool;
 
-// Dumb helper to handle CTransaction compression at serialize-time
-struct TransactionCompressor {
-private:
-    CTransactionRef& tx;
-public:
-    explicit TransactionCompressor(CTransactionRef& txIn) : tx(txIn) {}
+// Transaction compression schemes for compact block relay can be introduced by writing
+// an actual formatter here.
+using TransactionCompression = DefaultFormatter;
 
-    ADD_SERIALIZE_METHODS;
+class DifferenceFormatter
+{
+    uint64_t m_shift = 0;
 
-    template <typename Stream, typename Operation>
-    inline void SerializationOp(Stream& s, Operation ser_action) {
-        READWRITE(tx); //TODO: Compress tx encoding
+public:
+    template<typename Stream, typename I>
+    void Ser(Stream& s, I v)
+    {
+        if (v < m_shift || v >= std::numeric_limits<uint64_t>::max()) throw std::ios_base::failure("differential value overflow");
+        WriteCompactSize(s, v - m_shift);
+        m_shift = uint64_t(v) + 1;
+    }
+    template<typename Stream, typename I>
+    void Unser(Stream& s, I& v)
+    {
+        uint64_t n = ReadCompactSize(s);
+        m_shift += n;
+        if (m_shift < n || m_shift >= std::numeric_limits<uint64_t>::max() || m_shift < std::numeric_limits<I>::min() || m_shift > std::numeric_limits<I>::max()) throw std::ios_base::failure("differential value overflow");
+        v = I(m_shift++);
     }
 };
 
@@ -31,39 +42,9 @@ public:
     uint256 blockhash;
     std::vector<uint16_t> indexes;
 
-    ADD_SERIALIZE_METHODS;
-
-    template <typename Stream, typename Operation>
-    inline void SerializationOp(Stream& s, Operation ser_action) {
-        READWRITE(blockhash);
-        uint64_t indexes_size = (uint64_t)indexes.size();
-        READWRITE(COMPACTSIZE(indexes_size));
-        if (ser_action.ForRead()) {
-            size_t i = 0;
-            while (indexes.size() < indexes_size) {
-                indexes.resize(std::min((uint64_t)(1000 + indexes.size()), indexes_size));
-                for (; i < indexes.size(); i++) {
-                    uint64_t index = 0;
-                    READWRITE(COMPACTSIZE(index));
-                    if (index > std::numeric_limits<uint16_t>::max())
-                        throw std::ios_base::failure("index overflowed 16 bits");
-                    indexes[i] = index;
-                }
-            }
-
-            int32_t offset = 0;
-            for (size_t j = 0; j < indexes.size(); j++) {
-                if (int32_t(indexes[j]) + offset > std::numeric_limits<uint16_t>::max())
-                    throw std::ios_base::failure("indexes overflowed 16 bits");
-                indexes[j] = indexes[j] + offset;
-                offset = int32_t(indexes[j]) + 1;
-            }
-        } else {
-            for (size_t i = 0; i < indexes.size(); i++) {
-                uint64_t index = indexes[i] - (i == 0 ? 0 : (indexes[i - 1] + 1));
-                READWRITE(COMPACTSIZE(index));
-            }
-        }
+    SERIALIZE_METHODS(BlockTransactionsRequest, obj)
+    {
+        READWRITE(obj.blockhash, Using<VectorFormatter<DifferenceFormatter>>(obj.indexes));
     }
 };
 
@@ -77,24 +58,9 @@ public:
     explicit BlockTransactions(const BlockTransactionsRequest& req) :
         blockhash(req.blockhash), txn(req.indexes.size()) {}
 
-    ADD_SERIALIZE_METHODS;
-
-    template <typename Stream, typename Operation>
-    inline void SerializationOp(Stream& s, Operation ser_action) {
-        READWRITE(blockhash);
-        uint64_t txn_size = (uint64_t)txn.size();
-        READWRITE(COMPACTSIZE(txn_size));
-        if (ser_action.ForRead()) {
-            size_t i = 0;
-            while (txn.size() < txn_size) {
-                txn.resize(std::min((uint64_t)(1000 + txn.size()), txn_size));
-                for (; i < txn.size(); i++)
-                    READWRITE(TransactionCompressor(txn[i]));
-            }
-        } else {
-            for (size_t i = 0; i < txn.size(); i++)
-                READWRITE(TransactionCompressor(txn[i]));
-        }
+    SERIALIZE_METHODS(BlockTransactions, obj)
+    {
+        READWRITE(obj.blockhash, Using<VectorFormatter<TransactionCompression>>(obj.txn));
     }
 };
 
@@ -105,17 +71,7 @@ struct PrefilledTransaction {
     uint16_t index;
     CTransactionRef tx;
 
-    ADD_SERIALIZE_METHODS;
-
-    template <typename Stream, typename Operation>
-    inline void SerializationOp(Stream& s, Operation ser_action) {
-        uint64_t idx = index;
-        READWRITE(COMPACTSIZE(idx));
-        if (idx > std::numeric_limits<uint16_t>::max())
-            throw std::ios_base::failure("index overflowed 16-bits");
-        index = idx;
-        READWRITE(TransactionCompressor(tx));
-    }
+    SERIALIZE_METHODS(PrefilledTransaction, obj) { READWRITE(COMPACTSIZE(obj.index), Using<TransactionCompression>(obj.tx)); }
 };
 
 typedef enum ReadStatus_t
@@ -153,43 +109,15 @@ public:
 
     size_t BlockTxCount() const { return shorttxids.size() + prefilledtxn.size(); }
 
-    ADD_SERIALIZE_METHODS;
-
-    template <typename Stream, typename Operation>
-    inline void SerializationOp(Stream& s, Operation ser_action) {
-        READWRITE(header);
-        READWRITE(nonce);
-
-        uint64_t shorttxids_size = (uint64_t)shorttxids.size();
-        READWRITE(COMPACTSIZE(shorttxids_size));
+    SERIALIZE_METHODS(CBlockHeaderAndShortTxIDs, obj)
+    {
+        READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn);
         if (ser_action.ForRead()) {
-            size_t i = 0;
-            while (shorttxids.size() < shorttxids_size) {
-                shorttxids.resize(std::min((uint64_t)(1000 + shorttxids.size()), shorttxids_size));
-                for (; i < shorttxids.size(); i++) {
-                    uint32_t lsb = 0; uint16_t msb = 0;
-                    READWRITE(lsb);
-                    READWRITE(msb);
-                    shorttxids[i] = (uint64_t(msb) << 32) | uint64_t(lsb);
-                    static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids serialization assumes 6-byte shorttxids");
-                }
-            }
-        } else {
-            for (size_t i = 0; i < shorttxids.size(); i++) {
-                uint32_t lsb = shorttxids[i] & 0xffffffff;
-                uint16_t msb = (shorttxids[i] >> 32) & 0xffff;
-                READWRITE(lsb);
-                READWRITE(msb);
+            if (obj.BlockTxCount() > std::numeric_limits<uint16_t>::max()) {
+                throw std::ios_base::failure("indexes overflowed 16 bits");
             }
+            obj.FillShortTxIDSelector();
         }
-
-        READWRITE(prefilledtxn);
-
-        if (BlockTxCount() > std::numeric_limits<uint16_t>::max())
-            throw std::ios_base::failure("indexes overflowed 16 bits");
-
-        if (ser_action.ForRead())
-            FillShortTxIDSelector();
     }
 };
 
diff --git a/src/prevector.h b/src/prevector.h
index 09debedc4f..6d690e7f96 100644
--- a/src/prevector.h
+++ b/src/prevector.h
@@ -424,15 +424,20 @@ public:
         return first;
     }
 
-    void push_back(const T& value) {
+    template<typename... Args>
+    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>(args)...);
         _size++;
     }
 
+    void push_back(const T& value) {
+        emplace_back(value);
+    }
+
     void pop_back() {
         erase(end() - 1, end());
     }
diff --git a/src/serialize.h b/src/serialize.h
index 0a43913f83..5045cb3c7f 100644
--- a/src/serialize.h
+++ b/src/serialize.h
@@ -500,7 +500,7 @@ static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&
 
 #define VARINT_MODE(obj, mode) Using<VarIntFormatter<mode>>(obj)
 #define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
-#define COMPACTSIZE(obj) CCompactSize(REF(obj))
+#define COMPACTSIZE(obj) Using<CompactSizeFormatter>(obj)
 #define LIMITED_STRING(obj,n) LimitedString< n >(REF(obj))
 
 /** Serialization wrapper class for integers in VarInt format. */
@@ -518,6 +518,28 @@ struct VarIntFormatter
     }
 };
 
+template<int Bytes>
+struct CustomUintFormatter
+{
+    static_assert(Bytes > 0 && Bytes <= 8, "CustomUintFormatter Bytes out of range");
+    static constexpr uint64_t MAX = 0xffffffffffffffff >> (8 * (8 - Bytes));
+
+    template <typename Stream, typename I> void Ser(Stream& s, I v)
+    {
+        if (v < 0 || v > MAX) throw std::ios_base::failure("CustomUintFormatter value out of range");
+        uint64_t raw = htole64(v);
+        s.write((const char*)&raw, Bytes);
+    }
+
+    template <typename Stream, typename I> void Unser(Stream& s, I& v)
+    {
+        static_assert(std::numeric_limits<I>::max() >= MAX && std::numeric_limits<I>::min() <= 0, "CustomUintFormatter type too small");
+        uint64_t raw = 0;
+        s.read((char*)&raw, Bytes);
+        v = le64toh(raw);
+    }
+};
+
 /** Serialization wrapper class for big-endian integers.
  *
  * Use this wrapper around integer types that are stored in memory in native
@@ -552,21 +574,26 @@ public:
     }
 };
 
-class CCompactSize
+/** Formatter for integers in CompactSize format. */
+struct CompactSizeFormatter
 {
-protected:
-    uint64_t &n;
-public:
-    explicit CCompactSize(uint64_t& nIn) : n(nIn) { }
-
-    template<typename Stream>
-    void Serialize(Stream &s) const {
-        WriteCompactSize<Stream>(s, n);
+    template<typename Stream, typename I>
+    void Unser(Stream& s, I& v)
+    {
+        uint64_t n = ReadCompactSize<Stream>(s);
+        if (n < std::numeric_limits<I>::min() || n > std::numeric_limits<I>::max()) {
+            throw std::ios_base::failure("CompactSize exceeds limit of type");
+        }
+        v = n;
     }
 
-    template<typename Stream>
-    void Unserialize(Stream& s) {
-        n = ReadCompactSize<Stream>(s);
+    template<typename Stream, typename I>
+    void Ser(Stream& s, I v)
+    {
+        static_assert(std::is_unsigned<I>::value, "CompactSize only supported for unsigned integers");
+        static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max(), "CompactSize only supports 64-bit integers and below");
+
+        WriteCompactSize<Stream>(s, v);
     }
 };
 
@@ -613,7 +640,7 @@ BigEndian<I> WrapBigEndian(I& n) { return BigEndian<I>(n); }
  * 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<class Formatter>
 struct VectorFormatter
@@ -621,15 +648,17 @@ struct VectorFormatter
     template<typename Stream, typename V>
     void Ser(Stream& s, const V& v)
     {
+        Formatter formatter;
         WriteCompactSize(s, v.size());
         for (const typename V::value_type& elem : v) {
-            s << Using<Formatter>(elem);
+            formatter.Ser(s, elem);
         }
     }
 
     template<typename Stream, typename V>
     void Unser(Stream& s, V& v)
     {
+        Formatter formatter;
         v.clear();
         size_t size = ReadCompactSize(s);
         size_t allocated = 0;
@@ -641,9 +670,8 @@ struct VectorFormatter
             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<Formatter>(val);
-                v.push_back(std::move(val));
+                v.emplace_back();
+                formatter.Unser(s, v.back());
             }
         }
     };