Line data Source code
1 : // Copyright (c) 2019-2020 The Bitcoin Core developers
2 : // Distributed under the MIT software license, see the accompanying
3 : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 :
5 : #include <map>
6 : #include <vector>
7 : #include <assert.h>
8 : #include <crypto/common.h>
9 :
10 : namespace {
11 :
12 : constexpr uint32_t INVALID = 0xFFFFFFFF;
13 :
14 180848 : 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)
15 : {
16 180848 : uint32_t val = minval;
17 : bool bit;
18 1082508 : for (std::vector<uint8_t>::const_iterator bit_sizes_it = bit_sizes.begin();
19 901660 : bit_sizes_it != bit_sizes.end(); ++bit_sizes_it) {
20 901660 : if (bit_sizes_it + 1 != bit_sizes.end()) {
21 745774 : if (bitpos == endpos) break;
22 745774 : bit = *bitpos;
23 745774 : bitpos++;
24 745774 : } else {
25 : bit = 0;
26 : }
27 901660 : if (bit) {
28 720812 : val += (1 << *bit_sizes_it);
29 : } else {
30 1013838 : for (int b = 0; b < *bit_sizes_it; b++) {
31 832990 : if (bitpos == endpos) return INVALID; // Reached EOF in mantissa
32 832990 : bit = *bitpos;
33 832990 : bitpos++;
34 832990 : val += bit << (*bit_sizes_it - 1 - b);
35 : }
36 180848 : return val;
37 : }
38 : }
39 0 : return INVALID; // Reached EOF in exponent
40 180848 : }
41 :
42 : enum class Instruction : uint32_t
43 : {
44 : RETURN = 0,
45 : JUMP = 1,
46 : MATCH = 2,
47 : DEFAULT = 3,
48 : };
49 :
50 640 : const std::vector<uint8_t> TYPE_BIT_SIZES{0, 0, 1};
51 90424 : Instruction DecodeType(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
52 : {
53 90424 : return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES));
54 : }
55 :
56 640 : const std::vector<uint8_t> ASN_BIT_SIZES{15, 16, 17, 18, 19, 20, 21, 22, 23, 24};
57 5730 : uint32_t DecodeASN(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
58 : {
59 5730 : return DecodeBits(bitpos, endpos, 1, ASN_BIT_SIZES);
60 : }
61 :
62 :
63 640 : const std::vector<uint8_t> MATCH_BIT_SIZES{1, 2, 3, 4, 5, 6, 7, 8};
64 78137 : uint32_t DecodeMatch(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
65 : {
66 78137 : return DecodeBits(bitpos, endpos, 2, MATCH_BIT_SIZES);
67 : }
68 :
69 :
70 640 : const std::vector<uint8_t> JUMP_BIT_SIZES{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
71 6557 : uint32_t DecodeJump(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
72 : {
73 6557 : return DecodeBits(bitpos, endpos, 17, JUMP_BIT_SIZES);
74 : }
75 :
76 : }
77 :
78 6411 : uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip)
79 : {
80 6411 : std::vector<bool>::const_iterator pos = asmap.begin();
81 6411 : const std::vector<bool>::const_iterator endpos = asmap.end();
82 6411 : uint8_t bits = ip.size();
83 90300 : uint32_t default_asn = 0;
84 : uint32_t jump, match, matchlen;
85 : Instruction opcode;
86 90300 : while (pos != endpos) {
87 90300 : opcode = DecodeType(pos, endpos);
88 90300 : if (opcode == Instruction::RETURN) {
89 5694 : default_asn = DecodeASN(pos, endpos);
90 5694 : if (default_asn == INVALID) break; // ASN straddles EOF
91 5694 : return default_asn;
92 84606 : } else if (opcode == Instruction::JUMP) {
93 6525 : jump = DecodeJump(pos, endpos);
94 6525 : if (jump == INVALID) break; // Jump offset straddles EOF
95 6525 : if (bits == 0) break; // No input bits left
96 6525 : if (pos + jump < pos) break; // overflow
97 6525 : if (pos + jump >= endpos) break; // Jumping past EOF
98 6525 : if (ip[ip.size() - bits]) {
99 5703 : pos += jump;
100 5703 : }
101 6525 : bits--;
102 84606 : } else if (opcode == Instruction::MATCH) {
103 78081 : match = DecodeMatch(pos, endpos);
104 78081 : if (match == INVALID) break; // Match bits straddle EOF
105 78081 : matchlen = CountBits(match) - 1;
106 78081 : if (bits < matchlen) break; // Not enough input bits
107 699612 : for (uint32_t bit = 0; bit < matchlen; bit++) {
108 622248 : if ((ip[ip.size() - bits]) != ((match >> (matchlen - 1 - bit)) & 1)) {
109 717 : return default_asn;
110 : }
111 621531 : bits--;
112 : }
113 0 : } else if (opcode == Instruction::DEFAULT) {
114 0 : default_asn = DecodeASN(pos, endpos);
115 0 : if (default_asn == INVALID) break; // ASN straddles EOF
116 : } else {
117 : break; // Instruction straddles EOF
118 : }
119 : }
120 0 : assert(false); // Reached EOF without RETURN, or aborted (see any of the breaks above) - should have been caught by SanityCheckASMap below
121 : return 0; // 0 is not a valid ASN
122 6411 : }
123 :
124 5 : bool SanityCheckASMap(const std::vector<bool>& asmap, int bits)
125 : {
126 5 : const std::vector<bool>::const_iterator begin = asmap.begin(), endpos = asmap.end();
127 5 : std::vector<bool>::const_iterator pos = begin;
128 5 : std::vector<std::pair<uint32_t, int>> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left)
129 5 : jumps.reserve(bits);
130 129 : Instruction prevopcode = Instruction::JUMP;
131 129 : bool had_incomplete_match = false;
132 125 : while (pos != endpos) {
133 124 : uint32_t offset = pos - begin;
134 124 : if (!jumps.empty() && offset >= jumps.back().first) return false; // There was a jump into the middle of the previous instruction
135 124 : Instruction opcode = DecodeType(pos, endpos);
136 124 : if (opcode == Instruction::RETURN) {
137 36 : if (prevopcode == Instruction::DEFAULT) return false; // There should not be any RETURN immediately after a DEFAULT (could be combined into just RETURN)
138 36 : uint32_t asn = DecodeASN(pos, endpos);
139 36 : if (asn == INVALID) return false; // ASN straddles EOF
140 36 : if (jumps.empty()) {
141 : // Nothing to execute anymore
142 4 : if (endpos - pos > 7) return false; // Excessive padding
143 12 : while (pos != endpos) {
144 8 : if (*pos) return false; // Nonzero padding bit
145 8 : ++pos;
146 : }
147 4 : return true; // Sanely reached EOF
148 : } else {
149 : // Continue by pretending we jumped to the next instruction
150 32 : offset = pos - begin;
151 32 : if (offset != jumps.back().first) return false; // Unreachable code
152 32 : bits = jumps.back().second; // Restore the number of bits we would have had left after this jump
153 32 : jumps.pop_back();
154 : prevopcode = Instruction::JUMP;
155 : }
156 120 : } else if (opcode == Instruction::JUMP) {
157 32 : uint32_t jump = DecodeJump(pos, endpos);
158 32 : if (jump == INVALID) return false; // Jump offset straddles EOF
159 32 : if (pos + jump < pos) return false; // overflow
160 32 : if (pos + jump > endpos) return false; // Jump out of range
161 32 : if (bits == 0) return false; // Consuming bits past the end of the input
162 32 : --bits;
163 32 : uint32_t jump_offset = pos - begin + jump;
164 32 : if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps
165 32 : jumps.emplace_back(jump_offset, bits);
166 : prevopcode = Instruction::JUMP;
167 88 : } else if (opcode == Instruction::MATCH) {
168 56 : uint32_t match = DecodeMatch(pos, endpos);
169 56 : if (match == INVALID) return false; // Match bits straddle EOF
170 56 : int matchlen = CountBits(match) - 1;
171 56 : if (prevopcode != Instruction::MATCH) had_incomplete_match = false;
172 56 : if (matchlen < 8 && had_incomplete_match) return false; // Within a sequence of matches only at most one should be incomplete
173 56 : had_incomplete_match = (matchlen < 8);
174 56 : if (bits < matchlen) return false; // Consuming bits past the end of the input
175 56 : bits -= matchlen;
176 : prevopcode = Instruction::MATCH;
177 56 : } else if (opcode == Instruction::DEFAULT) {
178 0 : if (prevopcode == Instruction::DEFAULT) return false; // There should not be two successive DEFAULTs (they could be combined into one)
179 0 : uint32_t asn = DecodeASN(pos, endpos);
180 0 : if (asn == INVALID) return false; // ASN straddles EOF
181 : prevopcode = Instruction::DEFAULT;
182 0 : } else {
183 0 : return false; // Instruction straddles EOF
184 : }
185 120 : }
186 1 : return false; // Reached EOF without RETURN instruction
187 5 : }
|
