aboutsummaryrefslogtreecommitdiff
path: root/src/util
diff options
context:
space:
mode:
Diffstat (limited to 'src/util')
-rw-r--r--src/util/asmap.cpp112
-rw-r--r--src/util/asmap.h5
-rw-r--r--src/util/check.h4
-rw-r--r--src/util/ref.h38
-rw-r--r--src/util/string.h16
-rw-r--r--src/util/translation.h20
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>
generated by cgit v1.2.3 (git 2.26.2) at 2024-09-06 19:07:16 +0000