diff options
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/asmap.cpp | 112 | ||||
-rw-r--r-- | src/util/asmap.h | 5 | ||||
-rw-r--r-- | src/util/check.h | 4 | ||||
-rw-r--r-- | src/util/ref.h | 38 | ||||
-rw-r--r-- | src/util/string.h | 16 | ||||
-rw-r--r-- | src/util/translation.h | 20 |
6 files changed, 168 insertions, 27 deletions
diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 5354cdb962..bd77d74218 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -2,12 +2,15 @@ // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. +#include <map> #include <vector> #include <assert.h> #include <crypto/common.h> namespace { +constexpr uint32_t INVALID = 0xFFFFFFFF; + uint32_t DecodeBits(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos, uint8_t minval, const std::vector<uint8_t> &bit_sizes) { uint32_t val = minval; @@ -25,7 +28,7 @@ uint32_t DecodeBits(std::vector<bool>::const_iterator& bitpos, const std::vector val += (1 << *bit_sizes_it); } else { for (int b = 0; b < *bit_sizes_it; b++) { - if (bitpos == endpos) break; + if (bitpos == endpos) return INVALID; // Reached EOF in mantissa bit = *bitpos; bitpos++; val += bit << (*bit_sizes_it - 1 - b); @@ -33,13 +36,21 @@ uint32_t DecodeBits(std::vector<bool>::const_iterator& bitpos, const std::vector return val; } } - return -1; + return INVALID; // Reached EOF in exponent } +enum class Instruction : uint32_t +{ + RETURN = 0, + JUMP = 1, + MATCH = 2, + DEFAULT = 3, +}; + const std::vector<uint8_t> TYPE_BIT_SIZES{0, 0, 1}; -uint32_t DecodeType(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos) +Instruction DecodeType(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos) { - return DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES); + return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES)); } const std::vector<uint8_t> ASN_BIT_SIZES{15, 16, 17, 18, 19, 20, 21, 22, 23, 24}; @@ -70,34 +81,107 @@ uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip) const std::vector<bool>::const_iterator endpos = asmap.end(); uint8_t bits = ip.size(); uint32_t default_asn = 0; - uint32_t opcode, jump, match, matchlen; + uint32_t jump, match, matchlen; + Instruction opcode; while (pos != endpos) { opcode = DecodeType(pos, endpos); - if (opcode == 0) { - return DecodeASN(pos, endpos); - } else if (opcode == 1) { + if (opcode == Instruction::RETURN) { + default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) break; // ASN straddles EOF + return default_asn; + } else if (opcode == Instruction::JUMP) { jump = DecodeJump(pos, endpos); - if (bits == 0) break; + if (jump == INVALID) break; // Jump offset straddles EOF + if (bits == 0) break; // No input bits left + if (pos + jump < pos) break; // overflow + if (pos + jump >= endpos) break; // Jumping past EOF if (ip[ip.size() - bits]) { - if (jump >= endpos - pos) break; pos += jump; } bits--; - } else if (opcode == 2) { + } else if (opcode == Instruction::MATCH) { match = DecodeMatch(pos, endpos); + if (match == INVALID) break; // Match bits straddle EOF matchlen = CountBits(match) - 1; + if (bits < matchlen) break; // Not enough input bits for (uint32_t bit = 0; bit < matchlen; bit++) { - if (bits == 0) break; if ((ip[ip.size() - bits]) != ((match >> (matchlen - 1 - bit)) & 1)) { return default_asn; } bits--; } - } else if (opcode == 3) { + } else if (opcode == Instruction::DEFAULT) { default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) break; // ASN straddles EOF } else { - break; + break; // Instruction straddles EOF } } + assert(false); // Reached EOF without RETURN, or aborted (see any of the breaks above) - should have been caught by SanityCheckASMap below return 0; // 0 is not a valid ASN } + +bool SanityCheckASMap(const std::vector<bool>& asmap, int bits) +{ + const std::vector<bool>::const_iterator begin = asmap.begin(), endpos = asmap.end(); + std::vector<bool>::const_iterator pos = begin; + std::vector<std::pair<uint32_t, int>> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left) + jumps.reserve(bits); + Instruction prevopcode = Instruction::JUMP; + bool had_incomplete_match = false; + while (pos != endpos) { + uint32_t offset = pos - begin; + if (!jumps.empty() && offset >= jumps.back().first) return false; // There was a jump into the middle of the previous instruction + Instruction opcode = DecodeType(pos, endpos); + if (opcode == Instruction::RETURN) { + if (prevopcode == Instruction::DEFAULT) return false; // There should not be any RETURN immediately after a DEFAULT (could be combined into just RETURN) + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) return false; // ASN straddles EOF + if (jumps.empty()) { + // Nothing to execute anymore + if (endpos - pos > 7) return false; // Excessive padding + while (pos != endpos) { + if (*pos) return false; // Nonzero padding bit + ++pos; + } + return true; // Sanely reached EOF + } else { + // Continue by pretending we jumped to the next instruction + offset = pos - begin; + if (offset != jumps.back().first) return false; // Unreachable code + bits = jumps.back().second; // Restore the number of bits we would have had left after this jump + jumps.pop_back(); + prevopcode = Instruction::JUMP; + } + } else if (opcode == Instruction::JUMP) { + uint32_t jump = DecodeJump(pos, endpos); + if (jump == INVALID) return false; // Jump offset straddles EOF + if (pos + jump < pos) return false; // overflow + if (pos + jump > endpos) return false; // Jump out of range + if (bits == 0) return false; // Consuming bits past the end of the input + --bits; + uint32_t jump_offset = pos - begin + jump; + if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps + jumps.emplace_back(jump_offset, bits); + prevopcode = Instruction::JUMP; + } else if (opcode == Instruction::MATCH) { + uint32_t match = DecodeMatch(pos, endpos); + if (match == INVALID) return false; // Match bits straddle EOF + int matchlen = CountBits(match) - 1; + if (prevopcode != Instruction::MATCH) had_incomplete_match = false; + if (matchlen < 8 && had_incomplete_match) return false; // Within a sequence of matches only at most one should be incomplete + had_incomplete_match = (matchlen < 8); + if (bits < matchlen) return false; // Consuming bits past the end of the input + bits -= matchlen; + prevopcode = Instruction::MATCH; + } else if (opcode == Instruction::DEFAULT) { + if (prevopcode == Instruction::DEFAULT) return false; // There should not be two successive DEFAULTs (they could be combined into one) + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) return false; // ASN straddles EOF + prevopcode = Instruction::DEFAULT; + } else { + return false; // Instruction straddles EOF + } + } + return false; // Reached EOF without RETURN instruction +} diff --git a/src/util/asmap.h b/src/util/asmap.h index a0e14013c5..b31e639bb5 100644 --- a/src/util/asmap.h +++ b/src/util/asmap.h @@ -5,6 +5,11 @@ #ifndef BITCOIN_UTIL_ASMAP_H #define BITCOIN_UTIL_ASMAP_H +#include <stdint.h> +#include <vector> + uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip); +bool SanityCheckASMap(const std::vector<bool>& asmap, int bits); + #endif // BITCOIN_UTIL_ASMAP_H diff --git a/src/util/check.h b/src/util/check.h index d18887ae95..5c0f32cf51 100644 --- a/src/util/check.h +++ b/src/util/check.h @@ -5,6 +5,10 @@ #ifndef BITCOIN_UTIL_CHECK_H #define BITCOIN_UTIL_CHECK_H +#if defined(HAVE_CONFIG_H) +#include <config/bitcoin-config.h> +#endif + #include <tinyformat.h> #include <stdexcept> diff --git a/src/util/ref.h b/src/util/ref.h new file mode 100644 index 0000000000..9685ea9fec --- /dev/null +++ b/src/util/ref.h @@ -0,0 +1,38 @@ +// Copyright (c) 2020 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_UTIL_REF_H +#define BITCOIN_UTIL_REF_H + +#include <util/check.h> + +#include <typeindex> + +namespace util { + +/** + * Type-safe dynamic reference. + * + * This implements a small subset of the functionality in C++17's std::any + * class, and can be dropped when the project updates to C++17 + * (https://github.com/bitcoin/bitcoin/issues/16684) + */ +class Ref +{ +public: + Ref() = default; + template<typename T> Ref(T& value) { Set(value); } + template<typename T> T& Get() const { CHECK_NONFATAL(Has<T>()); return *static_cast<T*>(m_value); } + template<typename T> void Set(T& value) { m_value = &value; m_type = std::type_index(typeid(T)); } + template<typename T> bool Has() const { return m_value && m_type == std::type_index(typeid(T)); } + void Clear() { m_value = nullptr; m_type = std::type_index(typeid(void)); } + +private: + void* m_value = nullptr; + std::type_index m_type = std::type_index(typeid(void)); +}; + +} // namespace util + +#endif // BITCOIN_UTIL_REF_H diff --git a/src/util/string.h b/src/util/string.h index b8e2a06235..cdb41630c6 100644 --- a/src/util/string.h +++ b/src/util/string.h @@ -30,10 +30,11 @@ NODISCARD inline std::string TrimString(const std::string& str, const std::strin * @param separator The separator * @param unary_op Apply this operator to each item in the list */ -template <typename T, typename UnaryOp> -std::string Join(const std::vector<T>& list, const std::string& separator, UnaryOp unary_op) +template <typename T, typename BaseType, typename UnaryOp> +auto Join(const std::vector<T>& list, const BaseType& separator, UnaryOp unary_op) + -> decltype(unary_op(list.at(0))) { - std::string ret; + decltype(unary_op(list.at(0))) ret; for (size_t i = 0; i < list.size(); ++i) { if (i > 0) ret += separator; ret += unary_op(list.at(i)); @@ -41,9 +42,16 @@ std::string Join(const std::vector<T>& list, const std::string& separator, Unary return ret; } +template <typename T> +T Join(const std::vector<T>& list, const T& separator) +{ + return Join(list, separator, [](const T& i) { return i; }); +} + +// Explicit overload needed for c_str arguments, which would otherwise cause a substitution failure in the template above. inline std::string Join(const std::vector<std::string>& list, const std::string& separator) { - return Join(list, separator, [](const std::string& i) { return i; }); + return Join<std::string>(list, separator); } /** diff --git a/src/util/translation.h b/src/util/translation.h index b2d964c977..268bcf30a7 100644 --- a/src/util/translation.h +++ b/src/util/translation.h @@ -16,21 +16,23 @@ struct bilingual_str { std::string original; std::string translated; + + bilingual_str& operator+=(const bilingual_str& rhs) + { + original += rhs.original; + translated += rhs.translated; + return *this; + } }; -inline bilingual_str operator+(const bilingual_str& lhs, const bilingual_str& rhs) +inline bilingual_str operator+(bilingual_str lhs, const bilingual_str& rhs) { - return bilingual_str{ - lhs.original + rhs.original, - lhs.translated + rhs.translated}; + lhs += rhs; + return lhs; } /** Mark a bilingual_str as untranslated */ -inline static bilingual_str Untranslated(std::string original) { return {original, original}; } -/** Unary operator to return the original */ -inline static std::string OpOriginal(const bilingual_str& b) { return b.original; } -/** Unary operator to return the translation */ -inline static std::string OpTranslated(const bilingual_str& b) { return b.translated; } +inline bilingual_str Untranslated(std::string original) { return {original, original}; } namespace tinyformat { template <typename... Args> |