Bitcoin ABC  0.26.3
P2P Digital Currency
asmap.cpp
Go to the documentation of this file.
1 // Copyright (c) 2019 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 <util/asmap.h>
6 
7 #include <clientversion.h>
8 #include <crypto/common.h>
9 #include <logging.h>
10 #include <streams.h>
11 
12 #include <cassert>
13 #include <map>
14 #include <vector>
15 
16 namespace {
17 
18 constexpr uint32_t INVALID = 0xFFFFFFFF;
19 
20 uint32_t DecodeBits(std::vector<bool>::const_iterator &bitpos,
21  const std::vector<bool>::const_iterator &endpos,
22  uint8_t minval, const std::vector<uint8_t> &bit_sizes) {
23  uint32_t val = minval;
24  bool bit;
25  for (std::vector<uint8_t>::const_iterator bit_sizes_it = bit_sizes.begin();
26  bit_sizes_it != bit_sizes.end(); ++bit_sizes_it) {
27  if (bit_sizes_it + 1 != bit_sizes.end()) {
28  if (bitpos == endpos) {
29  break;
30  }
31  bit = *bitpos;
32  bitpos++;
33  } else {
34  bit = 0;
35  }
36  if (bit) {
37  val += (1 << *bit_sizes_it);
38  } else {
39  for (int b = 0; b < *bit_sizes_it; b++) {
40  if (bitpos == endpos) {
41  // Reached EOF in mantissa
42  return INVALID;
43  }
44  bit = *bitpos;
45  bitpos++;
46  val += bit << (*bit_sizes_it - 1 - b);
47  }
48  return val;
49  }
50  }
51  // Reached EOF in exponent
52  return INVALID;
53 }
54 
55 enum class Instruction : uint32_t {
56  RETURN = 0,
57  JUMP = 1,
58  MATCH = 2,
59  DEFAULT = 3,
60 };
61 
62 const std::vector<uint8_t> TYPE_BIT_SIZES{0, 0, 1};
63 Instruction DecodeType(std::vector<bool>::const_iterator &bitpos,
64  const std::vector<bool>::const_iterator &endpos) {
65  return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES));
66 }
67 
68 const std::vector<uint8_t> ASN_BIT_SIZES{15, 16, 17, 18, 19,
69  20, 21, 22, 23, 24};
70 uint32_t DecodeASN(std::vector<bool>::const_iterator &bitpos,
71  const std::vector<bool>::const_iterator &endpos) {
72  return DecodeBits(bitpos, endpos, 1, ASN_BIT_SIZES);
73 }
74 
75 const std::vector<uint8_t> MATCH_BIT_SIZES{1, 2, 3, 4, 5, 6, 7, 8};
76 uint32_t DecodeMatch(std::vector<bool>::const_iterator &bitpos,
77  const std::vector<bool>::const_iterator &endpos) {
78  return DecodeBits(bitpos, endpos, 2, MATCH_BIT_SIZES);
79 }
80 
81 const std::vector<uint8_t> JUMP_BIT_SIZES{5, 6, 7, 8, 9, 10, 11, 12, 13,
82  14, 15, 16, 17, 18, 19, 20, 21, 22,
83  23, 24, 25, 26, 27, 28, 29, 30};
84 uint32_t DecodeJump(std::vector<bool>::const_iterator &bitpos,
85  const std::vector<bool>::const_iterator &endpos) {
86  return DecodeBits(bitpos, endpos, 17, JUMP_BIT_SIZES);
87 }
88 
89 } // namespace
90 
91 uint32_t Interpret(const std::vector<bool> &asmap,
92  const std::vector<bool> &ip) {
93  std::vector<bool>::const_iterator pos = asmap.begin();
94  const std::vector<bool>::const_iterator endpos = asmap.end();
95  uint8_t bits = ip.size();
96  uint32_t default_asn = 0;
97  uint32_t jump, match, matchlen;
98  Instruction opcode;
99  while (pos != endpos) {
100  opcode = DecodeType(pos, endpos);
101  if (opcode == Instruction::RETURN) {
102  default_asn = DecodeASN(pos, endpos);
103  if (default_asn == INVALID) {
104  // ASN straddles EOF
105  break;
106  }
107  return default_asn;
108  } else if (opcode == Instruction::JUMP) {
109  jump = DecodeJump(pos, endpos);
110  if (jump == INVALID) {
111  // Jump offset straddles EOF
112  break;
113  }
114  if (bits == 0) {
115  // No input bits left
116  break;
117  }
118  if (pos + jump < pos) {
119  // overflow
120  break;
121  }
122  if (pos + jump >= endpos) {
123  // Jumping past EOF
124  break;
125  }
126  if (ip[ip.size() - bits]) {
127  pos += jump;
128  }
129  bits--;
130  } else if (opcode == Instruction::MATCH) {
131  match = DecodeMatch(pos, endpos);
132  if (match == INVALID) {
133  // Match bits straddle EOF
134  break;
135  }
136  matchlen = CountBits(match) - 1;
137  if (bits < matchlen) {
138  // Not enough input bits
139  break;
140  }
141  for (uint32_t bit = 0; bit < matchlen; bit++) {
142  if ((ip[ip.size() - bits]) !=
143  ((match >> (matchlen - 1 - bit)) & 1)) {
144  return default_asn;
145  }
146  bits--;
147  }
148  } else if (opcode == Instruction::DEFAULT) {
149  default_asn = DecodeASN(pos, endpos);
150  if (default_asn == INVALID) {
151  // ASN straddles EOF
152  break;
153  }
154  } else {
155  // Instruction straddles EOF
156  break;
157  }
158  }
159 
160  // Reached EOF without RETURN, or aborted (see any of the breaks above) -
161  // should have been caught by SanityCheckASMap below
162  assert(false);
163 
164  // 0 is not a valid ASN
165  return 0;
166 }
167 
168 bool SanityCheckASMap(const std::vector<bool> &asmap, int bits) {
169  const std::vector<bool>::const_iterator begin = asmap.begin(),
170  endpos = asmap.end();
171  std::vector<bool>::const_iterator pos = begin;
172  // All future positions we may jump to (bit offset in asmap -> bits to
173  // consume left)
174  std::vector<std::pair<uint32_t, int>> jumps;
175  jumps.reserve(bits);
176  Instruction prevopcode = Instruction::JUMP;
177  bool had_incomplete_match = false;
178  while (pos != endpos) {
179  uint32_t offset = pos - begin;
180  if (!jumps.empty() && offset >= jumps.back().first) {
181  // There was a jump into the middle of the previous instruction
182  return false;
183  }
184  Instruction opcode = DecodeType(pos, endpos);
185  if (opcode == Instruction::RETURN) {
186  if (prevopcode == Instruction::DEFAULT) {
187  // There should not be any RETURN immediately after a DEFAULT
188  // (could be combined into just RETURN)
189  return false;
190  }
191  uint32_t asn = DecodeASN(pos, endpos);
192  if (asn == INVALID) {
193  // ASN straddles EOF
194  return false;
195  }
196  if (jumps.empty()) {
197  // Nothing to execute anymore
198  if (endpos - pos > 7) {
199  // Excessive padding
200  return false;
201  }
202  while (pos != endpos) {
203  if (*pos) {
204  // Nonzero padding bit
205  return false;
206  }
207  ++pos;
208  }
209  // Sanely reached EOF
210  return true;
211  } else {
212  // Continue by pretending we jumped to the next instruction
213  offset = pos - begin;
214  if (offset != jumps.back().first) {
215  // Unreachable code
216  return false;
217  }
218  // Restore the number of bits we would have had left after this
219  // jump
220  bits = jumps.back().second;
221  jumps.pop_back();
222  prevopcode = Instruction::JUMP;
223  }
224  } else if (opcode == Instruction::JUMP) {
225  uint32_t jump = DecodeJump(pos, endpos);
226  if (jump == INVALID) {
227  // Jump offset straddles EOF
228  return false;
229  }
230  if (pos + jump < pos) {
231  // overflow
232  return false;
233  }
234  if (pos + jump > endpos) {
235  // Jump out of range
236  return false;
237  }
238  if (bits == 0) {
239  // Consuming bits past the end of the input
240  return false;
241  }
242  --bits;
243  uint32_t jump_offset = pos - begin + jump;
244  if (!jumps.empty() && jump_offset >= jumps.back().first) {
245  // Intersecting jumps
246  return false;
247  }
248  jumps.emplace_back(jump_offset, bits);
249  prevopcode = Instruction::JUMP;
250  } else if (opcode == Instruction::MATCH) {
251  uint32_t match = DecodeMatch(pos, endpos);
252  if (match == INVALID) {
253  // Match bits straddle EOF
254  return false;
255  }
256  int matchlen = CountBits(match) - 1;
257  if (prevopcode != Instruction::MATCH) {
258  had_incomplete_match = false;
259  }
260  if (matchlen < 8 && had_incomplete_match) {
261  // Within a sequence of matches only at most one should be
262  // incomplete
263  return false;
264  }
265  had_incomplete_match = (matchlen < 8);
266  if (bits < matchlen) {
267  // Consuming bits past the end of the input
268  return false;
269  }
270  bits -= matchlen;
271  prevopcode = Instruction::MATCH;
272  } else if (opcode == Instruction::DEFAULT) {
273  if (prevopcode == Instruction::DEFAULT) {
274  // There should not be two successive DEFAULTs (they could be
275  // combined into one)
276  return false;
277  }
278  uint32_t asn = DecodeASN(pos, endpos);
279  if (asn == INVALID) {
280  // ASN straddles EOF
281  return false;
282  }
283  prevopcode = Instruction::DEFAULT;
284  } else {
285  // Instruction straddles EOF
286  return false;
287  }
288  }
289  // Reached EOF without RETURN instruction
290  return false;
291 }
292 
293 std::vector<bool> DecodeAsmap(fs::path path) {
294  std::vector<bool> bits;
295  FILE *filestr = fsbridge::fopen(path, "rb");
296  CAutoFile file(filestr, SER_DISK, CLIENT_VERSION);
297  if (file.IsNull()) {
298  LogPrintf("Failed to open asmap file from disk\n");
299  return bits;
300  }
301  fseek(filestr, 0, SEEK_END);
302  int length = ftell(filestr);
303  LogPrintf("Opened asmap file %s (%d bytes) from disk\n",
304  fs::quoted(fs::PathToString(path)), length);
305  fseek(filestr, 0, SEEK_SET);
306  char cur_byte;
307  for (int i = 0; i < length; ++i) {
308  file >> cur_byte;
309  for (int bit = 0; bit < 8; ++bit) {
310  bits.push_back((cur_byte >> bit) & 1);
311  }
312  }
313  if (!SanityCheckASMap(bits, 128)) {
314  LogPrintf("Sanity check of asmap file %s failed\n",
316  return {};
317  }
318  return bits;
319 }
uint32_t Interpret(const std::vector< bool > &asmap, const std::vector< bool > &ip)
Definition: asmap.cpp:91
std::vector< bool > DecodeAsmap(fs::path path)
Read asmap from provided binary file.
Definition: asmap.cpp:293
bool SanityCheckASMap(const std::vector< bool > &asmap, int bits)
Definition: asmap.cpp:168
Non-refcounted RAII wrapper for FILE*.
Definition: streams.h:581
bool IsNull() const
Return true if the wrapped FILE* is nullptr, false otherwise.
Definition: streams.h:627
Path class wrapper to prepare application code for transition from boost::filesystem library to std::...
Definition: fs.h:33
static constexpr int CLIENT_VERSION
bitcoind-res.rc includes this file, but it cannot cope with real c++ code.
Definition: clientversion.h:44
static uint64_t CountBits(uint64_t x)
Return the smallest number n such that (x >> n) == 0 (or 64 if the highest bit in x is set.
Definition: common.h:82
#define LogPrintf(...)
Definition: logging.h:204
static auto quoted(const std::string &s)
Definition: fs.h:99
static std::string PathToString(const path &path)
Convert path object to byte string.
Definition: fs.h:134
FILE * fopen(const fs::path &p, const char *mode)
Definition: fs.cpp:27
@ SER_DISK
Definition: serialize.h:167
assert(!tx.IsCoinBase())