diff --git a/src/script/script.h b/src/script/script.h --- a/src/script/script.h +++ b/src/script/script.h @@ -189,8 +189,6 @@ const char *GetOpName(opcodetype opcode); -std::vector MinimalizeBigEndianArray(const std::vector &data); - class scriptnum_error : public std::runtime_error { public: explicit scriptnum_error(const std::string &str) @@ -227,6 +225,8 @@ const std::vector &vch, const size_t nMaxNumSize = CScriptNum::MAXIMUM_ELEMENT_SIZE); + static bool MinimallyEncode(std::vector &data); + inline bool operator==(const int64_t &rhs) const { return m_value == rhs; } inline bool operator!=(const int64_t &rhs) const { return m_value != rhs; } inline bool operator<=(const int64_t &rhs) const { return m_value <= rhs; } diff --git a/src/script/script.cpp b/src/script/script.cpp --- a/src/script/script.cpp +++ b/src/script/script.cpp @@ -292,57 +292,50 @@ return true; } -std::vector -MinimalizeBigEndianArray(const std::vector &data) { - std::vector res; - - // Can't encode more than this, go ahead and grab as much room as we could - // possibly need - res.reserve(data.size()); - - // Ensure we have a byte to work with. +bool CScriptNum::MinimallyEncode(std::vector &data) { if (data.size() == 0) { - return res; + return false; } - // Store the MSB - uint8_t neg = data[0] & 0x80; - bool havePushed = false; - for (size_t i = 0; i < data.size(); ++i) { - uint8_t x = data[i]; - - // Remove any MSB that might exist - if (i == 0) { - x &= 0x7f; - } - - // If we haven't pushed anything, and the current value is zero, keep - // ignoring bytes. - if (!havePushed && x == 0) { - continue; - } + // If the last byte is not 0x00 or 0x80, we are minimally encoded. + uint8_t last = data.back(); + if (last & 0x7f) { + return false; + } - // Record that we have begun pushing, and store the current value. - havePushed = true; - res.push_back(x); + // If the script is one byte long, then we have a zero, which encodes as an + // empty array. + if (data.size() == 1) { + data = {}; + return true; } - // Give us at least one byte - if (res.size() == 0) { - return res; + // If the next byte has it sign bit set, then we are minimaly encoded. + if (data[data.size() - 2] & 0x80) { + return false; } - // Only add back the sign if a value has been pushed. This implies the - // result is non-zero. - if (havePushed) { - // If the MSB is currently occupied, we need one extra byte. - if ((res[0] & 0x80) != 0) { - res.insert(res.begin(), 0); + // We are not minimally encoded, we need to figure out how much to trim. + for (size_t i = data.size() - 1; i > 0; i--) { + // We found a non zero byte, time to encode. + if (data[i - 1] != 0) { + if (data[i - 1] & 0x80) { + // We found a byte with it sign bit set so we need one more + // byte. + data[i++] = last; + } else { + // the sign bit is clear, we can use it. + data[i - 1] |= last; + } + + data.resize(i); + return true; } - res[0] |= neg; } - return res; + // If we the whole thing is zeros, then we have a zero. + data = {}; + return true; } unsigned int CScript::GetSigOpCount(bool fAccurate) const { diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -415,47 +415,6 @@ } } // namespace -BOOST_AUTO_TEST_CASE(minimize_big_endian_test) { - // Empty array case - BOOST_CHECK(MinimalizeBigEndianArray(std::vector()) == - std::vector()); - - // Zero arrays of various lengths - std::vector zeroArray({0x00}); - std::vector negZeroArray({0x80}); - for (int i = 0; i < 16; i++) { - if (i > 0) { - zeroArray.push_back(0x00); - negZeroArray.push_back(0x00); - } - - BOOST_CHECK(MinimalizeBigEndianArray(zeroArray) == - std::vector()); - - // -0 should always evaluate to 0x00 - BOOST_CHECK(MinimalizeBigEndianArray(negZeroArray) == - std::vector()); - } - - // Shouldn't minimalize this array to a negative number - std::vector notNegArray({{0x00, 0x80}}); - std::vector notNegArrayPadded({{0x00, 0x80}}); - for (int i = 0; i < 16; i++) { - notNegArray.push_back(i); - notNegArrayPadded.insert(notNegArrayPadded.begin(), 0x00); - BOOST_CHECK(MinimalizeBigEndianArray(notNegArray) == notNegArray); - BOOST_CHECK(MinimalizeBigEndianArray(notNegArrayPadded) == - std::vector({{0x00, 0x80}})); - } - - // Shouldn't minimalize these arrays at all - std::vector noMinArray; - for (int i = 1; i < 0x80; i++) { - noMinArray.push_back(i); - BOOST_CHECK(MinimalizeBigEndianArray(noMinArray) == noMinArray); - } -} - BOOST_AUTO_TEST_CASE(script_build) { const KeyData keys; diff --git a/src/test/scriptnum_tests.cpp b/src/test/scriptnum_tests.cpp --- a/src/test/scriptnum_tests.cpp +++ b/src/test/scriptnum_tests.cpp @@ -202,4 +202,53 @@ } } +static void CheckMinimalyEncode(std::vector data, + const std::vector &expected) { + bool alreadyEncoded = CScriptNum::IsMinimallyEncoded(data, data.size()); + bool hasEncoded = CScriptNum::MinimallyEncode(data); + BOOST_CHECK_EQUAL(hasEncoded, !alreadyEncoded); + BOOST_CHECK(data == expected); +} + +BOOST_AUTO_TEST_CASE(minimize_encoding_test) { + CheckMinimalyEncode({}, {}); + + // Check that positive and negative zeros encode to nothing. + std::vector zero, negZero; + for (size_t i = 0; i < MAX_SCRIPT_ELEMENT_SIZE; i++) { + zero.push_back(0x00); + CheckMinimalyEncode(zero, {}); + + negZero.push_back(0x80); + CheckMinimalyEncode(negZero, {}); + + // prepare for next round. + negZero[negZero.size() - 1] = 0x00; + } + + // Keep one leading zero when sign bit is used. + std::vector n{0x80, 0x00}, negn{0x80, 0x80}; + std::vector npadded = n, negnpadded = negn; + for (size_t i = 0; i < MAX_SCRIPT_ELEMENT_SIZE; i++) { + CheckMinimalyEncode(npadded, n); + npadded.push_back(0x00); + + CheckMinimalyEncode(negnpadded, negn); + negnpadded[negnpadded.size() - 1] = 0x00; + negnpadded.push_back(0x80); + } + + // Mege leading byte when sign bit isn't used. + std::vector k{0x7f}, negk{0xff}; + std::vector kpadded = k, negkpadded = negk; + for (size_t i = 0; i < MAX_SCRIPT_ELEMENT_SIZE; i++) { + CheckMinimalyEncode(kpadded, k); + kpadded.push_back(0x00); + + CheckMinimalyEncode(negkpadded, negk); + negkpadded[negkpadded.size() - 1] &= 0x7f; + negkpadded.push_back(0x80); + } +} + BOOST_AUTO_TEST_SUITE_END()