1 /*
2 This file is part of solidity.
3
4 solidity is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 solidity is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with solidity. If not, see <http://www.gnu.org/licenses/>.
16 */
17 // SPDX-License-Identifier: GPL-3.0
18 /**
19 * Yul interpreter module that evaluates EVM instructions.
20 */
21
22 #include <test/tools/yulInterpreter/EVMInstructionInterpreter.h>
23
24 #include <test/tools/yulInterpreter/Interpreter.h>
25
26 #include <libyul/backends/evm/EVMDialect.h>
27 #include <libyul/AST.h>
28
29 #include <libevmasm/Instruction.h>
30
31 #include <libsolutil/Keccak256.h>
32 #include <libsolutil/Numeric.h>
33
34 #include <limits>
35
36 using namespace std;
37 using namespace solidity;
38 using namespace solidity::yul;
39 using namespace solidity::yul::test;
40
41 using solidity::util::h160;
42 using solidity::util::h256;
43 using solidity::util::keccak256;
44
45 namespace
46 {
47
48 /// Reads 32 bytes from @a _data at position @a _offset bytes while
49 /// interpreting @a _data to be padded with an infinite number of zero
50 /// bytes beyond its end.
readZeroExtended(bytes const & _data,u256 const & _offset)51 u256 readZeroExtended(bytes const& _data, u256 const& _offset)
52 {
53 if (_offset >= _data.size())
54 return 0;
55 else if (_offset + 32 <= _data.size())
56 return *reinterpret_cast<h256 const*>(_data.data() + static_cast<size_t>(_offset));
57 else
58 {
59 size_t off = static_cast<size_t>(_offset);
60 u256 val;
61 for (size_t i = 0; i < 32; ++i)
62 {
63 val <<= 8;
64 if (off + i < _data.size())
65 val += _data[off + i];
66 }
67 return val;
68 }
69 }
70
71 /// Copy @a _size bytes of @a _source at offset @a _sourceOffset to
72 /// @a _target at offset @a _targetOffset. Behaves as if @a _source would
73 /// continue with an infinite sequence of zero bytes beyond its end.
copyZeroExtended(map<u256,uint8_t> & _target,bytes const & _source,size_t _targetOffset,size_t _sourceOffset,size_t _size)74 void copyZeroExtended(
75 map<u256, uint8_t>& _target, bytes const& _source,
76 size_t _targetOffset, size_t _sourceOffset, size_t _size
77 )
78 {
79 for (size_t i = 0; i < _size; ++i)
80 _target[_targetOffset + i] = _sourceOffset + i < _source.size() ? _source[_sourceOffset + i] : 0;
81 }
82
83 }
84
85 using u512 = boost::multiprecision::number<boost::multiprecision::cpp_int_backend<512, 256, boost::multiprecision::unsigned_magnitude, boost::multiprecision::unchecked, void>>;
86
eval(evmasm::Instruction _instruction,vector<u256> const & _arguments)87 u256 EVMInstructionInterpreter::eval(
88 evmasm::Instruction _instruction,
89 vector<u256> const& _arguments
90 )
91 {
92 using namespace solidity::evmasm;
93 using evmasm::Instruction;
94
95 auto info = instructionInfo(_instruction);
96 yulAssert(static_cast<size_t>(info.args) == _arguments.size(), "");
97
98 auto const& arg = _arguments;
99 switch (_instruction)
100 {
101 case Instruction::STOP:
102 BOOST_THROW_EXCEPTION(ExplicitlyTerminated());
103 // --------------- arithmetic ---------------
104 case Instruction::ADD:
105 return arg[0] + arg[1];
106 case Instruction::MUL:
107 return arg[0] * arg[1];
108 case Instruction::SUB:
109 return arg[0] - arg[1];
110 case Instruction::DIV:
111 return arg[1] == 0 ? 0 : arg[0] / arg[1];
112 case Instruction::SDIV:
113 return arg[1] == 0 ? 0 : s2u(u2s(arg[0]) / u2s(arg[1]));
114 case Instruction::MOD:
115 return arg[1] == 0 ? 0 : arg[0] % arg[1];
116 case Instruction::SMOD:
117 return arg[1] == 0 ? 0 : s2u(u2s(arg[0]) % u2s(arg[1]));
118 case Instruction::EXP:
119 return exp256(arg[0], arg[1]);
120 case Instruction::NOT:
121 return ~arg[0];
122 case Instruction::LT:
123 return arg[0] < arg[1] ? 1 : 0;
124 case Instruction::GT:
125 return arg[0] > arg[1] ? 1 : 0;
126 case Instruction::SLT:
127 return u2s(arg[0]) < u2s(arg[1]) ? 1 : 0;
128 case Instruction::SGT:
129 return u2s(arg[0]) > u2s(arg[1]) ? 1 : 0;
130 case Instruction::EQ:
131 return arg[0] == arg[1] ? 1 : 0;
132 case Instruction::ISZERO:
133 return arg[0] == 0 ? 1 : 0;
134 case Instruction::AND:
135 return arg[0] & arg[1];
136 case Instruction::OR:
137 return arg[0] | arg[1];
138 case Instruction::XOR:
139 return arg[0] ^ arg[1];
140 case Instruction::BYTE:
141 return arg[0] >= 32 ? 0 : (arg[1] >> unsigned(8 * (31 - arg[0]))) & 0xff;
142 case Instruction::SHL:
143 return arg[0] > 255 ? 0 : (arg[1] << unsigned(arg[0]));
144 case Instruction::SHR:
145 return arg[0] > 255 ? 0 : (arg[1] >> unsigned(arg[0]));
146 case Instruction::SAR:
147 {
148 static u256 const hibit = u256(1) << 255;
149 if (arg[0] >= 256)
150 return arg[1] & hibit ? u256(-1) : 0;
151 else
152 {
153 unsigned amount = unsigned(arg[0]);
154 u256 v = arg[1] >> amount;
155 if (arg[1] & hibit)
156 v |= u256(-1) << (256 - amount);
157 return v;
158 }
159 }
160 case Instruction::ADDMOD:
161 return arg[2] == 0 ? 0 : u256((u512(arg[0]) + u512(arg[1])) % arg[2]);
162 case Instruction::MULMOD:
163 return arg[2] == 0 ? 0 : u256((u512(arg[0]) * u512(arg[1])) % arg[2]);
164 case Instruction::SIGNEXTEND:
165 if (arg[0] >= 31)
166 return arg[1];
167 else
168 {
169 unsigned testBit = unsigned(arg[0]) * 8 + 7;
170 u256 ret = arg[1];
171 u256 mask = ((u256(1) << testBit) - 1);
172 if (boost::multiprecision::bit_test(ret, testBit))
173 ret |= ~mask;
174 else
175 ret &= mask;
176 return ret;
177 }
178 // --------------- blockchain stuff ---------------
179 case Instruction::KECCAK256:
180 {
181 if (!accessMemory(arg[0], arg[1]))
182 return u256("0x1234cafe1234cafe1234cafe") + arg[0];
183 uint64_t offset = uint64_t(arg[0] & uint64_t(-1));
184 uint64_t size = uint64_t(arg[1] & uint64_t(-1));
185 return u256(keccak256(readMemory(offset, size)));
186 }
187 case Instruction::ADDRESS:
188 return h256(m_state.address, h256::AlignRight);
189 case Instruction::BALANCE:
190 if (arg[0] == h256(m_state.address, h256::AlignRight))
191 return m_state.selfbalance;
192 else
193 return m_state.balance;
194 case Instruction::SELFBALANCE:
195 return m_state.selfbalance;
196 case Instruction::ORIGIN:
197 return h256(m_state.origin, h256::AlignRight);
198 case Instruction::CALLER:
199 return h256(m_state.caller, h256::AlignRight);
200 case Instruction::CALLVALUE:
201 return m_state.callvalue;
202 case Instruction::CALLDATALOAD:
203 return readZeroExtended(m_state.calldata, arg[0]);
204 case Instruction::CALLDATASIZE:
205 return m_state.calldata.size();
206 case Instruction::CALLDATACOPY:
207 if (accessMemory(arg[0], arg[2]))
208 copyZeroExtended(
209 m_state.memory, m_state.calldata,
210 size_t(arg[0]), size_t(arg[1]), size_t(arg[2])
211 );
212 return 0;
213 case Instruction::CODESIZE:
214 return m_state.code.size();
215 case Instruction::CODECOPY:
216 if (accessMemory(arg[0], arg[2]))
217 copyZeroExtended(
218 m_state.memory, m_state.code,
219 size_t(arg[0]), size_t(arg[1]), size_t(arg[2])
220 );
221 return 0;
222 case Instruction::GASPRICE:
223 return m_state.gasprice;
224 case Instruction::CHAINID:
225 return m_state.chainid;
226 case Instruction::BASEFEE:
227 return m_state.basefee;
228 case Instruction::EXTCODESIZE:
229 return u256(keccak256(h256(arg[0]))) & 0xffffff;
230 case Instruction::EXTCODEHASH:
231 return u256(keccak256(h256(arg[0] + 1)));
232 case Instruction::EXTCODECOPY:
233 logTrace(_instruction, arg);
234 if (accessMemory(arg[1], arg[3]))
235 // TODO this way extcodecopy and codecopy do the same thing.
236 copyZeroExtended(
237 m_state.memory, m_state.code,
238 size_t(arg[1]), size_t(arg[2]), size_t(arg[3])
239 );
240 return 0;
241 case Instruction::RETURNDATASIZE:
242 return m_state.returndata.size();
243 case Instruction::RETURNDATACOPY:
244 logTrace(_instruction, arg);
245 if (accessMemory(arg[0], arg[2]))
246 copyZeroExtended(
247 m_state.memory, m_state.returndata,
248 size_t(arg[0]), size_t(arg[1]), size_t(arg[2])
249 );
250 return 0;
251 case Instruction::BLOCKHASH:
252 if (arg[0] >= m_state.blockNumber || arg[0] + 256 < m_state.blockNumber)
253 return 0;
254 else
255 return 0xaaaaaaaa + (arg[0] - m_state.blockNumber - 256);
256 case Instruction::COINBASE:
257 return h256(m_state.coinbase, h256::AlignRight);
258 case Instruction::TIMESTAMP:
259 return m_state.timestamp;
260 case Instruction::NUMBER:
261 return m_state.blockNumber;
262 case Instruction::DIFFICULTY:
263 return m_state.difficulty;
264 case Instruction::GASLIMIT:
265 return m_state.gaslimit;
266 // --------------- memory / storage / logs ---------------
267 case Instruction::MLOAD:
268 accessMemory(arg[0], 0x20);
269 return readMemoryWord(arg[0]);
270 case Instruction::MSTORE:
271 accessMemory(arg[0], 0x20);
272 writeMemoryWord(arg[0], arg[1]);
273 return 0;
274 case Instruction::MSTORE8:
275 accessMemory(arg[0], 1);
276 m_state.memory[arg[0]] = uint8_t(arg[1] & 0xff);
277 return 0;
278 case Instruction::SLOAD:
279 return m_state.storage[h256(arg[0])];
280 case Instruction::SSTORE:
281 m_state.storage[h256(arg[0])] = h256(arg[1]);
282 return 0;
283 case Instruction::PC:
284 return 0x77;
285 case Instruction::MSIZE:
286 return m_state.msize;
287 case Instruction::GAS:
288 return 0x99;
289 case Instruction::LOG0:
290 accessMemory(arg[0], arg[1]);
291 logTrace(_instruction, arg);
292 return 0;
293 case Instruction::LOG1:
294 accessMemory(arg[0], arg[1]);
295 logTrace(_instruction, arg);
296 return 0;
297 case Instruction::LOG2:
298 accessMemory(arg[0], arg[1]);
299 logTrace(_instruction, arg);
300 return 0;
301 case Instruction::LOG3:
302 accessMemory(arg[0], arg[1]);
303 logTrace(_instruction, arg);
304 return 0;
305 case Instruction::LOG4:
306 accessMemory(arg[0], arg[1]);
307 logTrace(_instruction, arg);
308 return 0;
309 // --------------- calls ---------------
310 case Instruction::CREATE:
311 accessMemory(arg[1], arg[2]);
312 logTrace(_instruction, arg);
313 return (0xcccccc + arg[1]) & u256("0xffffffffffffffffffffffffffffffffffffffff");
314 case Instruction::CREATE2:
315 accessMemory(arg[2], arg[3]);
316 logTrace(_instruction, arg);
317 return (0xdddddd + arg[1]) & u256("0xffffffffffffffffffffffffffffffffffffffff");
318 case Instruction::CALL:
319 case Instruction::CALLCODE:
320 // TODO assign returndata
321 accessMemory(arg[3], arg[4]);
322 accessMemory(arg[5], arg[6]);
323 logTrace(_instruction, arg);
324 return arg[0] & 1;
325 case Instruction::DELEGATECALL:
326 case Instruction::STATICCALL:
327 accessMemory(arg[2], arg[3]);
328 accessMemory(arg[4], arg[5]);
329 logTrace(_instruction, arg);
330 return 0;
331 case Instruction::RETURN:
332 {
333 bytes data;
334 if (accessMemory(arg[0], arg[1]))
335 data = readMemory(arg[0], arg[1]);
336 logTrace(_instruction, arg, data);
337 BOOST_THROW_EXCEPTION(ExplicitlyTerminated());
338 }
339 case Instruction::REVERT:
340 accessMemory(arg[0], arg[1]);
341 logTrace(_instruction, arg);
342 BOOST_THROW_EXCEPTION(ExplicitlyTerminated());
343 case Instruction::INVALID:
344 logTrace(_instruction);
345 BOOST_THROW_EXCEPTION(ExplicitlyTerminated());
346 case Instruction::SELFDESTRUCT:
347 logTrace(_instruction, arg);
348 BOOST_THROW_EXCEPTION(ExplicitlyTerminated());
349 case Instruction::POP:
350 break;
351 // --------------- invalid in strict assembly ---------------
352 case Instruction::JUMP:
353 case Instruction::JUMPI:
354 case Instruction::JUMPDEST:
355 case Instruction::PUSH1:
356 case Instruction::PUSH2:
357 case Instruction::PUSH3:
358 case Instruction::PUSH4:
359 case Instruction::PUSH5:
360 case Instruction::PUSH6:
361 case Instruction::PUSH7:
362 case Instruction::PUSH8:
363 case Instruction::PUSH9:
364 case Instruction::PUSH10:
365 case Instruction::PUSH11:
366 case Instruction::PUSH12:
367 case Instruction::PUSH13:
368 case Instruction::PUSH14:
369 case Instruction::PUSH15:
370 case Instruction::PUSH16:
371 case Instruction::PUSH17:
372 case Instruction::PUSH18:
373 case Instruction::PUSH19:
374 case Instruction::PUSH20:
375 case Instruction::PUSH21:
376 case Instruction::PUSH22:
377 case Instruction::PUSH23:
378 case Instruction::PUSH24:
379 case Instruction::PUSH25:
380 case Instruction::PUSH26:
381 case Instruction::PUSH27:
382 case Instruction::PUSH28:
383 case Instruction::PUSH29:
384 case Instruction::PUSH30:
385 case Instruction::PUSH31:
386 case Instruction::PUSH32:
387 case Instruction::DUP1:
388 case Instruction::DUP2:
389 case Instruction::DUP3:
390 case Instruction::DUP4:
391 case Instruction::DUP5:
392 case Instruction::DUP6:
393 case Instruction::DUP7:
394 case Instruction::DUP8:
395 case Instruction::DUP9:
396 case Instruction::DUP10:
397 case Instruction::DUP11:
398 case Instruction::DUP12:
399 case Instruction::DUP13:
400 case Instruction::DUP14:
401 case Instruction::DUP15:
402 case Instruction::DUP16:
403 case Instruction::SWAP1:
404 case Instruction::SWAP2:
405 case Instruction::SWAP3:
406 case Instruction::SWAP4:
407 case Instruction::SWAP5:
408 case Instruction::SWAP6:
409 case Instruction::SWAP7:
410 case Instruction::SWAP8:
411 case Instruction::SWAP9:
412 case Instruction::SWAP10:
413 case Instruction::SWAP11:
414 case Instruction::SWAP12:
415 case Instruction::SWAP13:
416 case Instruction::SWAP14:
417 case Instruction::SWAP15:
418 case Instruction::SWAP16:
419 {
420 yulAssert(false, "");
421 return 0;
422 }
423 }
424
425 return 0;
426 }
427
evalBuiltin(BuiltinFunctionForEVM const & _fun,vector<Expression> const & _arguments,vector<u256> const & _evaluatedArguments)428 u256 EVMInstructionInterpreter::evalBuiltin(
429 BuiltinFunctionForEVM const& _fun,
430 vector<Expression> const& _arguments,
431 vector<u256> const& _evaluatedArguments
432 )
433 {
434 if (_fun.instruction)
435 return eval(*_fun.instruction, _evaluatedArguments);
436
437 string fun = _fun.name.str();
438 // Evaluate datasize/offset/copy instructions
439 if (fun == "datasize" || fun == "dataoffset")
440 {
441 string arg = std::get<Literal>(_arguments.at(0)).value.str();
442 if (arg.length() < 32)
443 arg.resize(32, 0);
444 if (fun == "datasize")
445 return u256(keccak256(arg)) & 0xfff;
446 else
447 {
448 // Force different value than for datasize
449 arg[31]++;
450 arg[31]++;
451 return u256(keccak256(arg)) & 0xfff;
452 }
453 }
454 else if (fun == "datacopy")
455 {
456 // This is identical to codecopy.
457 if (accessMemory(_evaluatedArguments.at(0), _evaluatedArguments.at(2)))
458 copyZeroExtended(
459 m_state.memory,
460 m_state.code,
461 size_t(_evaluatedArguments.at(0)),
462 size_t(_evaluatedArguments.at(1) & numeric_limits<size_t>::max()),
463 size_t(_evaluatedArguments.at(2))
464 );
465 return 0;
466 }
467 else
468 yulAssert(false, "Unknown builtin: " + fun);
469 return 0;
470 }
471
472
accessMemory(u256 const & _offset,u256 const & _size)473 bool EVMInstructionInterpreter::accessMemory(u256 const& _offset, u256 const& _size)
474 {
475 if (((_offset + _size) >= _offset) && ((_offset + _size + 0x1f) >= (_offset + _size)))
476 {
477 u256 newSize = (_offset + _size + 0x1f) & ~u256(0x1f);
478 m_state.msize = max(m_state.msize, newSize);
479 return _size <= 0xffff;
480 }
481 else
482 m_state.msize = u256(-1);
483
484 return false;
485 }
486
readMemory(u256 const & _offset,u256 const & _size)487 bytes EVMInstructionInterpreter::readMemory(u256 const& _offset, u256 const& _size)
488 {
489 yulAssert(_size <= 0xffff, "Too large read.");
490 bytes data(size_t(_size), uint8_t(0));
491 for (size_t i = 0; i < data.size(); ++i)
492 data[i] = m_state.memory[_offset + i];
493 return data;
494 }
495
readMemoryWord(u256 const & _offset)496 u256 EVMInstructionInterpreter::readMemoryWord(u256 const& _offset)
497 {
498 return u256(h256(readMemory(_offset, 32)));
499 }
500
writeMemoryWord(u256 const & _offset,u256 const & _value)501 void EVMInstructionInterpreter::writeMemoryWord(u256 const& _offset, u256 const& _value)
502 {
503 for (size_t i = 0; i < 32; i++)
504 m_state.memory[_offset + i] = uint8_t((_value >> (8 * (31 - i))) & 0xff);
505 }
506
507
logTrace(evmasm::Instruction _instruction,std::vector<u256> const & _arguments,bytes const & _data)508 void EVMInstructionInterpreter::logTrace(evmasm::Instruction _instruction, std::vector<u256> const& _arguments, bytes const& _data)
509 {
510 logTrace(evmasm::instructionInfo(_instruction).name, _arguments, _data);
511 }
512
logTrace(std::string const & _pseudoInstruction,std::vector<u256> const & _arguments,bytes const & _data)513 void EVMInstructionInterpreter::logTrace(std::string const& _pseudoInstruction, std::vector<u256> const& _arguments, bytes const& _data)
514 {
515 string message = _pseudoInstruction + "(";
516 for (size_t i = 0; i < _arguments.size(); ++i)
517 message += (i > 0 ? ", " : "") + formatNumber(_arguments[i]);
518 message += ")";
519 if (!_data.empty())
520 message += " [" + util::toHex(_data) + "]";
521 m_state.trace.emplace_back(std::move(message));
522 if (m_state.maxTraceSize > 0 && m_state.trace.size() >= m_state.maxTraceSize)
523 {
524 m_state.trace.emplace_back("Trace size limit reached.");
525 BOOST_THROW_EXCEPTION(TraceLimitReached());
526 }
527 }
528