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  * @author Christian <c@ethdev.com>
20  * @date 2015
21  * Code generation utils that handle arrays.
22  */
23 
24 #include <libsolidity/codegen/ArrayUtils.h>
25 
26 #include <libsolidity/ast/Types.h>
27 #include <libsolidity/ast/TypeProvider.h>
28 #include <libsolidity/codegen/CompilerContext.h>
29 #include <libsolidity/codegen/CompilerUtils.h>
30 #include <libsolidity/codegen/LValue.h>
31 
32 #include <libsolutil/FunctionSelector.h>
33 #include <libsolutil/Whiskers.h>
34 
35 #include <libevmasm/Instruction.h>
36 #include <liblangutil/Exceptions.h>
37 
38 using namespace std;
39 using namespace solidity;
40 using namespace solidity::evmasm;
41 using namespace solidity::frontend;
42 using namespace solidity::langutil;
43 
copyArrayToStorage(ArrayType const & _targetType,ArrayType const & _sourceType) const44 void ArrayUtils::copyArrayToStorage(ArrayType const& _targetType, ArrayType const& _sourceType) const
45 {
46 	// this copies source to target and also clears target if it was larger
47 	// need to leave "target_ref target_byte_off" on the stack at the end
48 
49 	// stack layout: [source_ref] [source length] target_ref (top)
50 	solAssert(_targetType.location() == DataLocation::Storage, "");
51 
52 	Type const* uint256 = TypeProvider::uint256();
53 	Type const* targetBaseType = _targetType.isByteArray() ? uint256 : _targetType.baseType();
54 	Type const* sourceBaseType = _sourceType.isByteArray() ? uint256 : _sourceType.baseType();
55 
56 	// TODO unroll loop for small sizes
57 
58 	bool sourceIsStorage = _sourceType.location() == DataLocation::Storage;
59 	bool fromCalldata = _sourceType.location() == DataLocation::CallData;
60 	bool directCopy = sourceIsStorage && sourceBaseType->isValueType() && *sourceBaseType == *targetBaseType;
61 	bool haveByteOffsetSource = !directCopy && sourceIsStorage && sourceBaseType->storageBytes() <= 16;
62 	bool haveByteOffsetTarget = !directCopy && targetBaseType->storageBytes() <= 16;
63 	unsigned byteOffsetSize = (haveByteOffsetSource ? 1u : 0u) + (haveByteOffsetTarget ? 1u : 0u);
64 
65 	// stack: source_ref [source_length] target_ref
66 	// store target_ref
67 	for (unsigned i = _sourceType.sizeOnStack(); i > 0; --i)
68 		m_context << swapInstruction(i);
69 	// stack: target_ref source_ref [source_length]
70 	// stack: target_ref source_ref [source_length]
71 	// retrieve source length
72 	if (_sourceType.location() != DataLocation::CallData || !_sourceType.isDynamicallySized())
73 		retrieveLength(_sourceType); // otherwise, length is already there
74 	if (_sourceType.location() == DataLocation::Memory && _sourceType.isDynamicallySized())
75 	{
76 		// increment source pointer to point to data
77 		m_context << Instruction::SWAP1 << u256(0x20);
78 		m_context << Instruction::ADD << Instruction::SWAP1;
79 	}
80 
81 	// stack: target_ref source_ref source_length
82 	Type const* targetType = &_targetType;
83 	Type const* sourceType = &_sourceType;
84 	m_context.callLowLevelFunction(
85 		"$copyArrayToStorage_" + sourceType->identifier() + "_to_" + targetType->identifier(),
86 		3,
87 		1,
88 		[=](CompilerContext& _context)
89 		{
90 			ArrayUtils utils(_context);
91 			ArrayType const& _sourceType = dynamic_cast<ArrayType const&>(*sourceType);
92 			ArrayType const& _targetType = dynamic_cast<ArrayType const&>(*targetType);
93 			// stack: target_ref source_ref source_length
94 			_context << Instruction::DUP3;
95 			// stack: target_ref source_ref source_length target_ref
96 			utils.retrieveLength(_targetType);
97 			// stack: target_ref source_ref source_length target_ref target_length
98 			if (_targetType.isDynamicallySized())
99 				// store new target length
100 				if (!_targetType.isByteArray())
101 					// Otherwise, length will be stored below.
102 					_context << Instruction::DUP3 << Instruction::DUP3 << Instruction::SSTORE;
103 			if (sourceBaseType->category() == Type::Category::Mapping)
104 			{
105 				solAssert(targetBaseType->category() == Type::Category::Mapping, "");
106 				solAssert(_sourceType.location() == DataLocation::Storage, "");
107 				// nothing to copy
108 				_context
109 					<< Instruction::POP << Instruction::POP
110 					<< Instruction::POP << Instruction::POP;
111 				return;
112 			}
113 			// stack: target_ref source_ref source_length target_ref target_length
114 			// compute hashes (data positions)
115 			_context << Instruction::SWAP1;
116 			if (_targetType.isDynamicallySized())
117 				CompilerUtils(_context).computeHashStatic();
118 			// stack: target_ref source_ref source_length target_length target_data_pos
119 			_context << Instruction::SWAP1;
120 			utils.convertLengthToSize(_targetType);
121 			_context << Instruction::DUP2 << Instruction::ADD;
122 			// stack: target_ref source_ref source_length target_data_pos target_data_end
123 			_context << Instruction::SWAP3;
124 			// stack: target_ref target_data_end source_length target_data_pos source_ref
125 
126 			evmasm::AssemblyItem copyLoopEndWithoutByteOffset = _context.newTag();
127 
128 			// special case for short byte arrays: Store them together with their length.
129 			if (_targetType.isByteArray())
130 			{
131 				// stack: target_ref target_data_end source_length target_data_pos source_ref
132 				_context << Instruction::DUP3;
133 				evmasm::AssemblyItem nonEmptyByteArray = _context.appendConditionalJump();
134 				// Empty source, just zero out the main slot.
135 				_context << u256(0) << Instruction::DUP6 << Instruction::SSTORE;
136 				_context.appendJumpTo(copyLoopEndWithoutByteOffset);
137 
138 				_context << nonEmptyByteArray;
139 				// Non-empty source.
140 				// stack: target_ref target_data_end source_length target_data_pos source_ref
141 				_context << Instruction::DUP3 << u256(31) << Instruction::LT;
142 				evmasm::AssemblyItem longByteArray = _context.appendConditionalJump();
143 				// store the short byte array
144 				solAssert(_sourceType.isByteArray(), "");
145 				if (_sourceType.location() == DataLocation::Storage)
146 				{
147 					// just copy the slot, it contains length and data
148 					_context << Instruction::DUP1 << Instruction::SLOAD;
149 					_context << Instruction::DUP6 << Instruction::SSTORE;
150 				}
151 				else
152 				{
153 					_context << Instruction::DUP1;
154 					CompilerUtils(_context).loadFromMemoryDynamic(*sourceBaseType, fromCalldata, true, false);
155 					// stack: target_ref target_data_end source_length target_data_pos source_ref value
156 					// clear the lower-order byte - which will hold the length
157 					_context << u256(0xff) << Instruction::NOT << Instruction::AND;
158 					// fetch the length and shift it left by one
159 					_context << Instruction::DUP4 << Instruction::DUP1 << Instruction::ADD;
160 					// combine value and length and store them
161 					_context << Instruction::OR << Instruction::DUP6 << Instruction::SSTORE;
162 				}
163 				// end of special case, jump right into cleaning target data area
164 				_context.appendJumpTo(copyLoopEndWithoutByteOffset);
165 				_context << longByteArray;
166 				// Store length (2*length+1)
167 				_context << Instruction::DUP3 << Instruction::DUP1 << Instruction::ADD;
168 				_context << u256(1) << Instruction::ADD;
169 				_context << Instruction::DUP6 << Instruction::SSTORE;
170 			}
171 
172 			// skip copying if source length is zero
173 			_context << Instruction::DUP3 << Instruction::ISZERO;
174 			_context.appendConditionalJumpTo(copyLoopEndWithoutByteOffset);
175 
176 			if (_sourceType.location() == DataLocation::Storage && _sourceType.isDynamicallySized())
177 				CompilerUtils(_context).computeHashStatic();
178 			// stack: target_ref target_data_end source_length target_data_pos source_data_pos
179 			_context << Instruction::SWAP2;
180 			utils.convertLengthToSize(_sourceType);
181 			_context << Instruction::DUP3 << Instruction::ADD;
182 			// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end
183 			if (haveByteOffsetTarget)
184 				_context << u256(0);
185 			if (haveByteOffsetSource)
186 				_context << u256(0);
187 			// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end [target_byte_offset] [source_byte_offset]
188 			evmasm::AssemblyItem copyLoopStart = _context.newTag();
189 			_context << copyLoopStart;
190 			// check for loop condition
191 			_context
192 				<< dupInstruction(3 + byteOffsetSize) << dupInstruction(2 + byteOffsetSize)
193 				<< Instruction::GT << Instruction::ISZERO;
194 			evmasm::AssemblyItem copyLoopEnd = _context.appendConditionalJump();
195 			// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end [target_byte_offset] [source_byte_offset]
196 			// copy
197 			if (sourceBaseType->category() == Type::Category::Array)
198 			{
199 				solAssert(byteOffsetSize == 0, "Byte offset for array as base type.");
200 				auto const& sourceBaseArrayType = dynamic_cast<ArrayType const&>(*sourceBaseType);
201 
202 				solUnimplementedAssert(
203 					_sourceType.location() != DataLocation::CallData ||
204 					!_sourceType.isDynamicallyEncoded() ||
205 					!sourceBaseArrayType.isDynamicallySized(),
206 					"Copying nested calldata dynamic arrays to storage is not implemented in the old code generator."
207 				);
208 				_context << Instruction::DUP3;
209 				if (sourceBaseArrayType.location() == DataLocation::Memory)
210 					_context << Instruction::MLOAD;
211 				_context << Instruction::DUP3;
212 				utils.copyArrayToStorage(dynamic_cast<ArrayType const&>(*targetBaseType), sourceBaseArrayType);
213 				_context << Instruction::POP;
214 			}
215 			else if (directCopy)
216 			{
217 				solAssert(byteOffsetSize == 0, "Byte offset for direct copy.");
218 				_context
219 					<< Instruction::DUP3 << Instruction::SLOAD
220 					<< Instruction::DUP3 << Instruction::SSTORE;
221 			}
222 			else
223 			{
224 				// Note that we have to copy each element on its own in case conversion is involved.
225 				// We might copy too much if there is padding at the last element, but this way end
226 				// checking is easier.
227 				// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end [target_byte_offset] [source_byte_offset]
228 				_context << dupInstruction(3 + byteOffsetSize);
229 				if (_sourceType.location() == DataLocation::Storage)
230 				{
231 					if (haveByteOffsetSource)
232 						_context << Instruction::DUP2;
233 					else
234 						_context << u256(0);
235 					StorageItem(_context, *sourceBaseType).retrieveValue(SourceLocation(), true);
236 				}
237 				else if (sourceBaseType->isValueType())
238 					CompilerUtils(_context).loadFromMemoryDynamic(*sourceBaseType, fromCalldata, true, false);
239 				else
240 					solUnimplemented("Copying of type " + _sourceType.toString(false) + " to storage not yet supported.");
241 				// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end [target_byte_offset] [source_byte_offset] <source_value>...
242 				assertThrow(
243 					2 + byteOffsetSize + sourceBaseType->sizeOnStack() <= 16,
244 					StackTooDeepError,
245 					"Stack too deep, try removing local variables."
246 				);
247 				// fetch target storage reference
248 				_context << dupInstruction(2 + byteOffsetSize + sourceBaseType->sizeOnStack());
249 				if (haveByteOffsetTarget)
250 					_context << dupInstruction(1 + byteOffsetSize + sourceBaseType->sizeOnStack());
251 				else
252 					_context << u256(0);
253 				StorageItem(_context, *targetBaseType).storeValue(*sourceBaseType, SourceLocation(), true);
254 			}
255 			// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end [target_byte_offset] [source_byte_offset]
256 			// increment source
257 			if (haveByteOffsetSource)
258 				utils.incrementByteOffset(sourceBaseType->storageBytes(), 1, haveByteOffsetTarget ? 5 : 4);
259 			else
260 			{
261 				_context << swapInstruction(2 + byteOffsetSize);
262 				if (sourceIsStorage)
263 					_context << sourceBaseType->storageSize();
264 				else if (_sourceType.location() == DataLocation::Memory)
265 					_context << sourceBaseType->memoryHeadSize();
266 				else
267 					_context << sourceBaseType->calldataHeadSize();
268 				_context
269 					<< Instruction::ADD
270 					<< swapInstruction(2 + byteOffsetSize);
271 			}
272 			// increment target
273 			if (haveByteOffsetTarget)
274 				utils.incrementByteOffset(targetBaseType->storageBytes(), byteOffsetSize, byteOffsetSize + 2);
275 			else
276 				_context
277 					<< swapInstruction(1 + byteOffsetSize)
278 					<< targetBaseType->storageSize()
279 					<< Instruction::ADD
280 					<< swapInstruction(1 + byteOffsetSize);
281 			_context.appendJumpTo(copyLoopStart);
282 			_context << copyLoopEnd;
283 			if (haveByteOffsetTarget)
284 			{
285 				// clear elements that might be left over in the current slot in target
286 				// stack: target_ref target_data_end source_data_pos target_data_pos source_data_end target_byte_offset [source_byte_offset]
287 				_context << dupInstruction(byteOffsetSize) << Instruction::ISZERO;
288 				evmasm::AssemblyItem copyCleanupLoopEnd = _context.appendConditionalJump();
289 				_context << dupInstruction(2 + byteOffsetSize) << dupInstruction(1 + byteOffsetSize);
290 				StorageItem(_context, *targetBaseType).setToZero(SourceLocation(), true);
291 				utils.incrementByteOffset(targetBaseType->storageBytes(), byteOffsetSize, byteOffsetSize + 2);
292 				_context.appendJumpTo(copyLoopEnd);
293 
294 				_context << copyCleanupLoopEnd;
295 				_context << Instruction::POP; // might pop the source, but then target is popped next
296 			}
297 			if (haveByteOffsetSource)
298 				_context << Instruction::POP;
299 			_context << copyLoopEndWithoutByteOffset;
300 
301 			// zero-out leftovers in target
302 			// stack: target_ref target_data_end source_data_pos target_data_pos_updated source_data_end
303 			_context << Instruction::POP << Instruction::SWAP1 << Instruction::POP;
304 			// stack: target_ref target_data_end target_data_pos_updated
305 			if (targetBaseType->storageBytes() < 32)
306 				utils.clearStorageLoop(TypeProvider::uint256());
307 			else
308 				utils.clearStorageLoop(targetBaseType);
309 			_context << Instruction::POP;
310 		}
311 	);
312 }
313 
copyArrayToMemory(ArrayType const & _sourceType,bool _padToWordBoundaries) const314 void ArrayUtils::copyArrayToMemory(ArrayType const& _sourceType, bool _padToWordBoundaries) const
315 {
316 	solUnimplementedAssert(
317 		!_sourceType.baseType()->isDynamicallySized(),
318 		"Nested dynamic arrays not implemented here."
319 	);
320 	CompilerUtils utils(m_context);
321 
322 	if (_sourceType.location() == DataLocation::CallData)
323 	{
324 		if (!_sourceType.isDynamicallySized())
325 			m_context << _sourceType.length();
326 		if (!_sourceType.isByteArray())
327 			convertLengthToSize(_sourceType);
328 
329 		string routine = "calldatacopy(target, source, len)\n";
330 		if (_padToWordBoundaries)
331 			routine += R"(
332 				// Set padding suffix to zero
333 				mstore(add(target, len), 0)
334 				len := and(add(len, 0x1f), not(0x1f))
335 			)";
336 		routine += "target := add(target, len)\n";
337 		m_context.appendInlineAssembly("{" + routine + "}", {"target", "source", "len"});
338 		m_context << Instruction::POP << Instruction::POP;
339 	}
340 	else if (_sourceType.location() == DataLocation::Memory)
341 	{
342 		retrieveLength(_sourceType);
343 		// stack: target source length
344 		if (!_sourceType.baseType()->isValueType())
345 		{
346 			// copy using a loop
347 			m_context << u256(0) << Instruction::SWAP3;
348 			// stack: counter source length target
349 			auto repeat = m_context.newTag();
350 			m_context << repeat;
351 			m_context << Instruction::DUP2 << Instruction::DUP5;
352 			m_context << Instruction::LT << Instruction::ISZERO;
353 			auto loopEnd = m_context.appendConditionalJump();
354 			m_context << Instruction::DUP3 << Instruction::DUP5;
355 			accessIndex(_sourceType, false);
356 			MemoryItem(m_context, *_sourceType.baseType(), true).retrieveValue(SourceLocation(), true);
357 			if (auto baseArray = dynamic_cast<ArrayType const*>(_sourceType.baseType()))
358 				copyArrayToMemory(*baseArray, _padToWordBoundaries);
359 			else
360 				utils.storeInMemoryDynamic(*_sourceType.baseType());
361 			m_context << Instruction::SWAP3 << u256(1) << Instruction::ADD;
362 			m_context << Instruction::SWAP3;
363 			m_context.appendJumpTo(repeat);
364 			m_context << loopEnd;
365 			m_context << Instruction::SWAP3;
366 			utils.popStackSlots(3);
367 			// stack: updated_target_pos
368 			return;
369 		}
370 
371 		// memcpy using the built-in contract
372 		if (_sourceType.isDynamicallySized())
373 		{
374 			// change pointer to data part
375 			m_context << Instruction::SWAP1 << u256(32) << Instruction::ADD;
376 			m_context << Instruction::SWAP1;
377 		}
378 		if (!_sourceType.isByteArray())
379 			convertLengthToSize(_sourceType);
380 		// stack: <target> <source> <size>
381 		m_context << Instruction::DUP1 << Instruction::DUP4 << Instruction::DUP4;
382 		// We can resort to copying full 32 bytes only if
383 		// - the length is known to be a multiple of 32 or
384 		// - we will pad to full 32 bytes later anyway.
385 		if (!_sourceType.isByteArray() || _padToWordBoundaries)
386 			utils.memoryCopy32();
387 		else
388 			utils.memoryCopy();
389 
390 		m_context << Instruction::SWAP1 << Instruction::POP;
391 		// stack: <target> <size>
392 
393 		bool paddingNeeded = _padToWordBoundaries && _sourceType.isByteArray();
394 
395 		if (paddingNeeded)
396 		{
397 			// stack: <target> <size>
398 			m_context << Instruction::SWAP1 << Instruction::DUP2 << Instruction::ADD;
399 			// stack: <length> <target + size>
400 			m_context << Instruction::SWAP1 << u256(31) << Instruction::AND;
401 			// stack: <target + size> <remainder = size % 32>
402 			evmasm::AssemblyItem skip = m_context.newTag();
403 			if (_sourceType.isDynamicallySized())
404 			{
405 				m_context << Instruction::DUP1 << Instruction::ISZERO;
406 				m_context.appendConditionalJumpTo(skip);
407 			}
408 			// round off, load from there.
409 			// stack <target + size> <remainder = size % 32>
410 			m_context << Instruction::DUP1 << Instruction::DUP3;
411 			m_context << Instruction::SUB;
412 			// stack: target+size remainder <target + size - remainder>
413 			m_context << Instruction::DUP1 << Instruction::MLOAD;
414 			// Now we AND it with ~(2**(8 * (32 - remainder)) - 1)
415 			m_context << u256(1);
416 			m_context << Instruction::DUP4 << u256(32) << Instruction::SUB;
417 			// stack: ...<v> 1 <32 - remainder>
418 			m_context << u256(0x100) << Instruction::EXP << Instruction::SUB;
419 			m_context << Instruction::NOT << Instruction::AND;
420 			// stack: target+size remainder target+size-remainder <v & ...>
421 			m_context << Instruction::DUP2 << Instruction::MSTORE;
422 			// stack: target+size remainder target+size-remainder
423 			m_context << u256(32) << Instruction::ADD;
424 			// stack: target+size remainder <new_padded_end>
425 			m_context << Instruction::SWAP2 << Instruction::POP;
426 
427 			if (_sourceType.isDynamicallySized())
428 				m_context << skip.tag();
429 			// stack <target + "size"> <remainder = size % 32>
430 			m_context << Instruction::POP;
431 		}
432 		else
433 			// stack: <target> <size>
434 			m_context << Instruction::ADD;
435 	}
436 	else
437 	{
438 		solAssert(_sourceType.location() == DataLocation::Storage, "");
439 		unsigned storageBytes = _sourceType.baseType()->storageBytes();
440 		u256 storageSize = _sourceType.baseType()->storageSize();
441 		solAssert(storageSize > 1 || (storageSize == 1 && storageBytes > 0), "");
442 
443 		retrieveLength(_sourceType);
444 		// stack here: memory_offset storage_offset length
445 		// jump to end if length is zero
446 		m_context << Instruction::DUP1 << Instruction::ISZERO;
447 		evmasm::AssemblyItem loopEnd = m_context.appendConditionalJump();
448 		// Special case for tightly-stored byte arrays
449 		if (_sourceType.isByteArray())
450 		{
451 			// stack here: memory_offset storage_offset length
452 			m_context << Instruction::DUP1 << u256(31) << Instruction::LT;
453 			evmasm::AssemblyItem longByteArray = m_context.appendConditionalJump();
454 			// store the short byte array (discard lower-order byte)
455 			m_context << u256(0x100) << Instruction::DUP1;
456 			m_context << Instruction::DUP4 << Instruction::SLOAD;
457 			m_context << Instruction::DIV << Instruction::MUL;
458 			m_context << Instruction::DUP4 << Instruction::MSTORE;
459 			// stack here: memory_offset storage_offset length
460 			// add 32 or length to memory offset
461 			m_context << Instruction::SWAP2;
462 			if (_padToWordBoundaries)
463 				m_context << u256(32);
464 			else
465 				m_context << Instruction::DUP3;
466 			m_context << Instruction::ADD;
467 			m_context << Instruction::SWAP2;
468 			m_context.appendJumpTo(loopEnd);
469 			m_context << longByteArray;
470 		}
471 		else
472 			// convert length to memory size
473 			m_context << _sourceType.baseType()->memoryHeadSize() << Instruction::MUL;
474 
475 		m_context << Instruction::DUP3 << Instruction::ADD << Instruction::SWAP2;
476 		if (_sourceType.isDynamicallySized())
477 		{
478 			// actual array data is stored at KECCAK256(storage_offset)
479 			m_context << Instruction::SWAP1;
480 			utils.computeHashStatic();
481 			m_context << Instruction::SWAP1;
482 		}
483 
484 		// stack here: memory_end_offset storage_data_offset memory_offset
485 		bool haveByteOffset = !_sourceType.isByteArray() && storageBytes <= 16;
486 		if (haveByteOffset)
487 			m_context << u256(0) << Instruction::SWAP1;
488 		// stack here: memory_end_offset storage_data_offset [storage_byte_offset] memory_offset
489 		evmasm::AssemblyItem loopStart = m_context.newTag();
490 		m_context << loopStart;
491 		// load and store
492 		if (_sourceType.isByteArray())
493 		{
494 			// Packed both in storage and memory.
495 			m_context << Instruction::DUP2 << Instruction::SLOAD;
496 			m_context << Instruction::DUP2 << Instruction::MSTORE;
497 			// increment storage_data_offset by 1
498 			m_context << Instruction::SWAP1 << u256(1) << Instruction::ADD;
499 			// increment memory offset by 32
500 			m_context << Instruction::SWAP1 << u256(32) << Instruction::ADD;
501 		}
502 		else
503 		{
504 			// stack here: memory_end_offset storage_data_offset [storage_byte_offset] memory_offset
505 			if (haveByteOffset)
506 				m_context << Instruction::DUP3 << Instruction::DUP3;
507 			else
508 				m_context << Instruction::DUP2 << u256(0);
509 			StorageItem(m_context, *_sourceType.baseType()).retrieveValue(SourceLocation(), true);
510 			if (auto baseArray = dynamic_cast<ArrayType const*>(_sourceType.baseType()))
511 				copyArrayToMemory(*baseArray, _padToWordBoundaries);
512 			else
513 				utils.storeInMemoryDynamic(*_sourceType.baseType());
514 			// increment storage_data_offset and byte offset
515 			if (haveByteOffset)
516 				incrementByteOffset(storageBytes, 2, 3);
517 			else
518 			{
519 				m_context << Instruction::SWAP1;
520 				m_context << storageSize << Instruction::ADD;
521 				m_context << Instruction::SWAP1;
522 			}
523 		}
524 		// check for loop condition
525 		m_context << Instruction::DUP1 << dupInstruction(haveByteOffset ? 5 : 4);
526 		m_context << Instruction::GT;
527 		m_context.appendConditionalJumpTo(loopStart);
528 		// stack here: memory_end_offset storage_data_offset [storage_byte_offset] memory_offset
529 		if (haveByteOffset)
530 			m_context << Instruction::SWAP1 << Instruction::POP;
531 		if (!_sourceType.isByteArray())
532 		{
533 			solAssert(_sourceType.calldataStride() % 32 == 0, "");
534 			solAssert(_sourceType.memoryStride() % 32 == 0, "");
535 		}
536 		if (_padToWordBoundaries && _sourceType.isByteArray())
537 		{
538 			// memory_end_offset - start is the actual length (we want to compute the ceil of).
539 			// memory_offset - start is its next multiple of 32, but it might be off by 32.
540 			// so we compute: memory_end_offset += (memory_offset - memory_end_offest) & 31
541 			m_context << Instruction::DUP3 << Instruction::SWAP1 << Instruction::SUB;
542 			m_context << u256(31) << Instruction::AND;
543 			m_context << Instruction::DUP3 << Instruction::ADD;
544 			m_context << Instruction::SWAP2;
545 		}
546 		m_context << loopEnd << Instruction::POP << Instruction::POP;
547 	}
548 }
549 
clearArray(ArrayType const & _typeIn) const550 void ArrayUtils::clearArray(ArrayType const& _typeIn) const
551 {
552 	Type const* type = &_typeIn;
553 	m_context.callLowLevelFunction(
554 		"$clearArray_" + _typeIn.identifier(),
555 		2,
556 		0,
557 		[type](CompilerContext& _context)
558 		{
559 			ArrayType const& _type = dynamic_cast<ArrayType const&>(*type);
560 			unsigned stackHeightStart = _context.stackHeight();
561 			solAssert(_type.location() == DataLocation::Storage, "");
562 			if (_type.baseType()->storageBytes() < 32)
563 			{
564 				solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
565 				solAssert(_type.baseType()->storageSize() <= 1, "Invalid storage size for type.");
566 			}
567 			if (_type.baseType()->isValueType())
568 				solAssert(_type.baseType()->storageSize() <= 1, "Invalid size for value type.");
569 
570 			_context << Instruction::POP; // remove byte offset
571 			if (_type.isDynamicallySized())
572 				ArrayUtils(_context).clearDynamicArray(_type);
573 			else if (_type.length() == 0 || _type.baseType()->category() == Type::Category::Mapping)
574 				_context << Instruction::POP;
575 			else if (_type.baseType()->isValueType() && _type.storageSize() <= 5)
576 			{
577 				// unroll loop for small arrays @todo choose a good value
578 				// Note that we loop over storage slots here, not elements.
579 				for (unsigned i = 1; i < _type.storageSize(); ++i)
580 					_context
581 						<< u256(0) << Instruction::DUP2 << Instruction::SSTORE
582 						<< u256(1) << Instruction::ADD;
583 				_context << u256(0) << Instruction::SWAP1 << Instruction::SSTORE;
584 			}
585 			else if (!_type.baseType()->isValueType() && _type.length() <= 4)
586 			{
587 				// unroll loop for small arrays @todo choose a good value
588 				solAssert(_type.baseType()->storageBytes() >= 32, "Invalid storage size.");
589 				for (unsigned i = 1; i < _type.length(); ++i)
590 				{
591 					_context << u256(0);
592 					StorageItem(_context, *_type.baseType()).setToZero(SourceLocation(), false);
593 					_context
594 						<< Instruction::POP
595 						<< u256(_type.baseType()->storageSize()) << Instruction::ADD;
596 				}
597 				_context << u256(0);
598 				StorageItem(_context, *_type.baseType()).setToZero(SourceLocation(), true);
599 			}
600 			else
601 			{
602 				_context << Instruction::DUP1 << _type.length();
603 				ArrayUtils(_context).convertLengthToSize(_type);
604 				_context << Instruction::ADD << Instruction::SWAP1;
605 				if (_type.baseType()->storageBytes() < 32)
606 					ArrayUtils(_context).clearStorageLoop(TypeProvider::uint256());
607 				else
608 					ArrayUtils(_context).clearStorageLoop(_type.baseType());
609 				_context << Instruction::POP;
610 			}
611 			solAssert(_context.stackHeight() == stackHeightStart - 2, "");
612 		}
613 	);
614 }
615 
clearDynamicArray(ArrayType const & _type) const616 void ArrayUtils::clearDynamicArray(ArrayType const& _type) const
617 {
618 	solAssert(_type.location() == DataLocation::Storage, "");
619 	solAssert(_type.isDynamicallySized(), "");
620 
621 	// fetch length
622 	retrieveLength(_type);
623 	// set length to zero
624 	m_context << u256(0) << Instruction::DUP3 << Instruction::SSTORE;
625 	// Special case: short byte arrays are stored togeher with their length
626 	evmasm::AssemblyItem endTag = m_context.newTag();
627 	if (_type.isByteArray())
628 	{
629 		// stack: ref old_length
630 		m_context << Instruction::DUP1 << u256(31) << Instruction::LT;
631 		evmasm::AssemblyItem longByteArray = m_context.appendConditionalJump();
632 		m_context << Instruction::POP;
633 		m_context.appendJumpTo(endTag);
634 		m_context.adjustStackOffset(1); // needed because of jump
635 		m_context << longByteArray;
636 	}
637 	// stack: ref old_length
638 	convertLengthToSize(_type);
639 	// compute data positions
640 	m_context << Instruction::SWAP1;
641 	CompilerUtils(m_context).computeHashStatic();
642 	// stack: len data_pos
643 	m_context << Instruction::SWAP1 << Instruction::DUP2 << Instruction::ADD
644 		<< Instruction::SWAP1;
645 	// stack: data_pos_end data_pos
646 	if (_type.storageStride() < 32)
647 		clearStorageLoop(TypeProvider::uint256());
648 	else
649 		clearStorageLoop(_type.baseType());
650 	// cleanup
651 	m_context << endTag;
652 	m_context << Instruction::POP;
653 }
654 
resizeDynamicArray(ArrayType const & _typeIn) const655 void ArrayUtils::resizeDynamicArray(ArrayType const& _typeIn) const
656 {
657 	Type const* type = &_typeIn;
658 	m_context.callLowLevelFunction(
659 		"$resizeDynamicArray_" + _typeIn.identifier(),
660 		2,
661 		0,
662 		[type](CompilerContext& _context)
663 		{
664 			ArrayType const& _type = dynamic_cast<ArrayType const&>(*type);
665 			solAssert(_type.location() == DataLocation::Storage, "");
666 			solAssert(_type.isDynamicallySized(), "");
667 			if (!_type.isByteArray() && _type.baseType()->storageBytes() < 32)
668 				solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
669 
670 			unsigned stackHeightStart = _context.stackHeight();
671 			evmasm::AssemblyItem resizeEnd = _context.newTag();
672 
673 			// stack: ref new_length
674 			// fetch old length
675 			ArrayUtils(_context).retrieveLength(_type, 1);
676 			// stack: ref new_length old_length
677 			solAssert(_context.stackHeight() - stackHeightStart == 3 - 2, "2");
678 
679 			// Special case for short byte arrays, they are stored together with their length
680 			if (_type.isByteArray())
681 			{
682 				evmasm::AssemblyItem regularPath = _context.newTag();
683 				// We start by a large case-distinction about the old and new length of the byte array.
684 
685 				_context << Instruction::DUP3 << Instruction::SLOAD;
686 				// stack: ref new_length current_length ref_value
687 
688 				solAssert(_context.stackHeight() - stackHeightStart == 4 - 2, "3");
689 				_context << Instruction::DUP2 << u256(31) << Instruction::LT;
690 				evmasm::AssemblyItem currentIsLong = _context.appendConditionalJump();
691 				_context << Instruction::DUP3 << u256(31) << Instruction::LT;
692 				evmasm::AssemblyItem newIsLong = _context.appendConditionalJump();
693 
694 				// Here: short -> short
695 
696 				// Compute 1 << (256 - 8 * new_size)
697 				evmasm::AssemblyItem shortToShort = _context.newTag();
698 				_context << shortToShort;
699 				_context << Instruction::DUP3 << u256(8) << Instruction::MUL;
700 				_context << u256(0x100) << Instruction::SUB;
701 				_context << u256(2) << Instruction::EXP;
702 				// Divide and multiply by that value, clearing bits.
703 				_context << Instruction::DUP1 << Instruction::SWAP2;
704 				_context << Instruction::DIV << Instruction::MUL;
705 				// Insert 2*length.
706 				_context << Instruction::DUP3 << Instruction::DUP1 << Instruction::ADD;
707 				_context << Instruction::OR;
708 				// Store.
709 				_context << Instruction::DUP4 << Instruction::SSTORE;
710 				solAssert(_context.stackHeight() - stackHeightStart == 3 - 2, "3");
711 				_context.appendJumpTo(resizeEnd);
712 
713 				_context.adjustStackOffset(1); // we have to do that because of the jumps
714 				// Here: short -> long
715 
716 				_context << newIsLong;
717 				// stack: ref new_length current_length ref_value
718 				solAssert(_context.stackHeight() - stackHeightStart == 4 - 2, "3");
719 				// Zero out lower-order byte.
720 				_context << u256(0xff) << Instruction::NOT << Instruction::AND;
721 				// Store at data location.
722 				_context << Instruction::DUP4;
723 				CompilerUtils(_context).computeHashStatic();
724 				_context << Instruction::SSTORE;
725 				// stack: ref new_length current_length
726 				// Store new length: Compule 2*length + 1 and store it.
727 				_context << Instruction::DUP2 << Instruction::DUP1 << Instruction::ADD;
728 				_context << u256(1) << Instruction::ADD;
729 				// stack: ref new_length current_length 2*new_length+1
730 				_context << Instruction::DUP4 << Instruction::SSTORE;
731 				solAssert(_context.stackHeight() - stackHeightStart == 3 - 2, "3");
732 				_context.appendJumpTo(resizeEnd);
733 
734 				_context.adjustStackOffset(1); // we have to do that because of the jumps
735 
736 				_context << currentIsLong;
737 				_context << Instruction::DUP3 << u256(31) << Instruction::LT;
738 				_context.appendConditionalJumpTo(regularPath);
739 
740 				// Here: long -> short
741 				// Read the first word of the data and store it on the stack. Clear the data location and
742 				// then jump to the short -> short case.
743 
744 				// stack: ref new_length current_length ref_value
745 				solAssert(_context.stackHeight() - stackHeightStart == 4 - 2, "3");
746 				_context << Instruction::POP << Instruction::DUP3;
747 				CompilerUtils(_context).computeHashStatic();
748 				_context << Instruction::DUP1 << Instruction::SLOAD << Instruction::SWAP1;
749 				// stack: ref new_length current_length first_word data_location
750 				_context << Instruction::DUP3;
751 				ArrayUtils(_context).convertLengthToSize(_type);
752 				_context << Instruction::DUP2 << Instruction::ADD << Instruction::SWAP1;
753 				// stack: ref new_length current_length first_word data_location_end data_location
754 				ArrayUtils(_context).clearStorageLoop(TypeProvider::uint256());
755 				_context << Instruction::POP;
756 				// stack: ref new_length current_length first_word
757 				solAssert(_context.stackHeight() - stackHeightStart == 4 - 2, "3");
758 				_context.appendJumpTo(shortToShort);
759 
760 				_context << regularPath;
761 				// stack: ref new_length current_length ref_value
762 				_context << Instruction::POP;
763 			}
764 
765 			// Change of length for a regular array (i.e. length at location, data at KECCAK256(location)).
766 			// stack: ref new_length old_length
767 			// store new length
768 			_context << Instruction::DUP2;
769 			if (_type.isByteArray())
770 				// For a "long" byte array, store length as 2*length+1
771 				_context << Instruction::DUP1 << Instruction::ADD << u256(1) << Instruction::ADD;
772 			_context << Instruction::DUP4 << Instruction::SSTORE;
773 			// skip if size is not reduced
774 			_context << Instruction::DUP2 << Instruction::DUP2
775 				<< Instruction::GT << Instruction::ISZERO;
776 			_context.appendConditionalJumpTo(resizeEnd);
777 
778 			// size reduced, clear the end of the array
779 			// stack: ref new_length old_length
780 			ArrayUtils(_context).convertLengthToSize(_type);
781 			_context << Instruction::DUP2;
782 			ArrayUtils(_context).convertLengthToSize(_type);
783 			// stack: ref new_length old_size new_size
784 			// compute data positions
785 			_context << Instruction::DUP4;
786 			CompilerUtils(_context).computeHashStatic();
787 			// stack: ref new_length old_size new_size data_pos
788 			_context << Instruction::SWAP2 << Instruction::DUP3 << Instruction::ADD;
789 			// stack: ref new_length data_pos new_size delete_end
790 			_context << Instruction::SWAP2 << Instruction::ADD;
791 			// stack: ref new_length delete_end delete_start
792 			if (_type.storageStride() < 32)
793 				ArrayUtils(_context).clearStorageLoop(TypeProvider::uint256());
794 			else
795 				ArrayUtils(_context).clearStorageLoop(_type.baseType());
796 
797 			_context << resizeEnd;
798 			// cleanup
799 			_context << Instruction::POP << Instruction::POP << Instruction::POP;
800 			solAssert(_context.stackHeight() == stackHeightStart - 2, "");
801 		}
802 	);
803 }
804 
incrementDynamicArraySize(ArrayType const & _type) const805 void ArrayUtils::incrementDynamicArraySize(ArrayType const& _type) const
806 {
807 	solAssert(_type.location() == DataLocation::Storage, "");
808 	solAssert(_type.isDynamicallySized(), "");
809 	if (!_type.isByteArray() && _type.baseType()->storageBytes() < 32)
810 		solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
811 
812 	if (_type.isByteArray())
813 	{
814 		// We almost always just add 2 (length of byte arrays is shifted left by one)
815 		// except for the case where we transition from a short byte array
816 		// to a long byte array, there we have to copy.
817 		// This happens if the length is exactly 31, which means that the
818 		// lowest-order byte (we actually use a mask with fewer bits) must
819 		// be (31*2+0) = 62
820 
821 		m_context << Instruction::DUP1 << Instruction::SLOAD << Instruction::DUP1;
822 		m_context.callYulFunction(m_context.utilFunctions().extractByteArrayLengthFunction(), 1, 1);
823 		m_context.appendInlineAssembly(R"({
824 			// We have to copy if length is exactly 31, because that marks
825 			// the transition between in-place and out-of-place storage.
826 			switch length
827 			case 31
828 			{
829 				mstore(0, ref)
830 				let data_area := keccak256(0, 0x20)
831 				sstore(data_area, and(data, not(0xff)))
832 				// Set old length in new format (31 * 2 + 1)
833 				data := 63
834 			}
835 			sstore(ref, add(data, 2))
836 			// return new length in ref
837 			ref := add(length, 1)
838 		})", {"ref", "data", "length"});
839 		m_context << Instruction::POP << Instruction::POP;
840 	}
841 	else
842 		m_context.appendInlineAssembly(R"({
843 			let new_length := add(sload(ref), 1)
844 			sstore(ref, new_length)
845 			ref := new_length
846 		})", {"ref"});
847 }
848 
popStorageArrayElement(ArrayType const & _type) const849 void ArrayUtils::popStorageArrayElement(ArrayType const& _type) const
850 {
851 	solAssert(_type.location() == DataLocation::Storage, "");
852 	solAssert(_type.isDynamicallySized(), "");
853 	if (!_type.isByteArray() && _type.baseType()->storageBytes() < 32)
854 		solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
855 
856 	if (_type.isByteArray())
857 	{
858 		m_context << Instruction::DUP1 << Instruction::SLOAD << Instruction::DUP1;
859 		m_context.callYulFunction(m_context.utilFunctions().extractByteArrayLengthFunction(), 1, 1);
860 		util::Whiskers code(R"({
861 			if iszero(length) {
862 				mstore(0, <panicSelector>)
863 				mstore(4, <emptyArrayPop>)
864 				revert(0, 0x24)
865 			}
866 			switch gt(length, 31)
867 			case 0 {
868 				// short byte array
869 				// Zero-out the suffix including the least significant byte.
870 				let mask := sub(exp(0x100, sub(33, length)), 1)
871 				length := sub(length, 1)
872 				slot_value := or(and(not(mask), slot_value), mul(length, 2))
873 			}
874 			case 1 {
875 				// long byte array
876 				mstore(0, ref)
877 				let slot := keccak256(0, 0x20)
878 				switch length
879 				case 32
880 				{
881 					let data := sload(slot)
882 					sstore(slot, 0)
883 					data := and(data, not(0xff))
884 					slot_value := or(data, 62)
885 				}
886 				default
887 				{
888 					let offset_inside_slot := and(sub(length, 1), 0x1f)
889 					slot := add(slot, div(sub(length, 1), 32))
890 					let data := sload(slot)
891 
892 					// Zero-out the suffix of the byte array by masking it.
893 					// ((1<<(8 * (32 - offset))) - 1)
894 					let mask := sub(exp(0x100, sub(32, offset_inside_slot)), 1)
895 					data := and(not(mask), data)
896 					sstore(slot, data)
897 
898 					// Reduce the length by 1
899 					slot_value := sub(slot_value, 2)
900 				}
901 			}
902 			sstore(ref, slot_value)
903 		})");
904 		code("panicSelector", util::selectorFromSignature("Panic(uint256)").str());
905 		code("emptyArrayPop", to_string(unsigned(util::PanicCode::EmptyArrayPop)));
906 		m_context.appendInlineAssembly(code.render(), {"ref", "slot_value", "length"});
907 		m_context << Instruction::POP << Instruction::POP << Instruction::POP;
908 	}
909 	else
910 	{
911 		// stack: ArrayReference
912 		retrieveLength(_type);
913 		// stack: ArrayReference oldLength
914 		m_context << Instruction::DUP1;
915 		// stack: ArrayReference oldLength oldLength
916 		m_context << Instruction::ISZERO;
917 		m_context.appendConditionalPanic(util::PanicCode::EmptyArrayPop);
918 
919 		// Stack: ArrayReference oldLength
920 		m_context << u256(1) << Instruction::SWAP1 << Instruction::SUB;
921 		// Stack ArrayReference newLength
922 
923 		if (_type.baseType()->category() != Type::Category::Mapping)
924 		{
925 			m_context << Instruction::DUP2 << Instruction::DUP2;
926 			// Stack ArrayReference newLength ArrayReference newLength;
927 			accessIndex(_type, false);
928 			// Stack: ArrayReference newLength storage_slot byte_offset
929 			StorageItem(m_context, *_type.baseType()).setToZero(SourceLocation(), true);
930 		}
931 
932 		// Stack: ArrayReference newLength
933 		m_context << Instruction::SWAP1 << Instruction::SSTORE;
934 	}
935 }
936 
clearStorageLoop(Type const * _type) const937 void ArrayUtils::clearStorageLoop(Type const* _type) const
938 {
939 	solAssert(_type->storageBytes() >= 32, "");
940 	m_context.callLowLevelFunction(
941 		"$clearStorageLoop_" + _type->identifier(),
942 		2,
943 		1,
944 		[_type](CompilerContext& _context)
945 		{
946 			unsigned stackHeightStart = _context.stackHeight();
947 			if (_type->category() == Type::Category::Mapping)
948 			{
949 				_context << Instruction::POP;
950 				return;
951 			}
952 			// stack: end_pos pos
953 
954 			evmasm::AssemblyItem loopStart = _context.appendJumpToNew();
955 			_context << loopStart;
956 			// check for loop condition
957 			_context <<
958 				Instruction::DUP1 <<
959 				Instruction::DUP3 <<
960 				Instruction::GT <<
961 				Instruction::ISZERO;
962 			evmasm::AssemblyItem zeroLoopEnd = _context.newTag();
963 			_context.appendConditionalJumpTo(zeroLoopEnd);
964 			// delete
965 			_context << u256(0);
966 			StorageItem(_context, *_type).setToZero(SourceLocation(), false);
967 			_context << Instruction::POP;
968 			// increment
969 			_context << _type->storageSize() << Instruction::ADD;
970 			_context.appendJumpTo(loopStart);
971 			// cleanup
972 			_context << zeroLoopEnd;
973 			_context << Instruction::POP;
974 
975 			solAssert(_context.stackHeight() == stackHeightStart - 1, "");
976 		}
977 	);
978 }
979 
convertLengthToSize(ArrayType const & _arrayType,bool _pad) const980 void ArrayUtils::convertLengthToSize(ArrayType const& _arrayType, bool _pad) const
981 {
982 	if (_arrayType.location() == DataLocation::Storage)
983 	{
984 		if (_arrayType.baseType()->storageSize() <= 1)
985 		{
986 			unsigned baseBytes = _arrayType.baseType()->storageBytes();
987 			if (baseBytes == 0)
988 				m_context << Instruction::POP << u256(1);
989 			else if (baseBytes <= 16)
990 			{
991 				unsigned itemsPerSlot = 32 / baseBytes;
992 				m_context
993 					<< u256(itemsPerSlot - 1) << Instruction::ADD
994 					<< u256(itemsPerSlot) << Instruction::SWAP1 << Instruction::DIV;
995 			}
996 		}
997 		else
998 			m_context << _arrayType.baseType()->storageSize() << Instruction::MUL;
999 	}
1000 	else
1001 	{
1002 		if (!_arrayType.isByteArray())
1003 		{
1004 			if (_arrayType.location() == DataLocation::Memory)
1005 				m_context << _arrayType.memoryStride();
1006 			else
1007 				m_context << _arrayType.calldataStride();
1008 			m_context << Instruction::MUL;
1009 		}
1010 		else if (_pad)
1011 			m_context << u256(31) << Instruction::ADD
1012 				<< u256(32) << Instruction::DUP1
1013 				<< Instruction::SWAP2 << Instruction::DIV << Instruction::MUL;
1014 	}
1015 }
1016 
retrieveLength(ArrayType const & _arrayType,unsigned _stackDepth) const1017 void ArrayUtils::retrieveLength(ArrayType const& _arrayType, unsigned _stackDepth) const
1018 {
1019 	if (!_arrayType.isDynamicallySized())
1020 		m_context << _arrayType.length();
1021 	else
1022 	{
1023 		m_context << dupInstruction(1 + _stackDepth);
1024 		switch (_arrayType.location())
1025 		{
1026 		case DataLocation::CallData:
1027 			// length is stored on the stack
1028 			break;
1029 		case DataLocation::Memory:
1030 			m_context << Instruction::MLOAD;
1031 			break;
1032 		case DataLocation::Storage:
1033 			m_context << Instruction::SLOAD;
1034 			if (_arrayType.isByteArray())
1035 				m_context.callYulFunction(m_context.utilFunctions().extractByteArrayLengthFunction(), 1, 1);
1036 			break;
1037 		}
1038 	}
1039 }
1040 
accessIndex(ArrayType const & _arrayType,bool _doBoundsCheck,bool _keepReference) const1041 void ArrayUtils::accessIndex(ArrayType const& _arrayType, bool _doBoundsCheck, bool _keepReference) const
1042 {
1043 	/// Stack: reference [length] index
1044 	DataLocation location = _arrayType.location();
1045 
1046 	if (_doBoundsCheck)
1047 	{
1048 		// retrieve length
1049 		ArrayUtils::retrieveLength(_arrayType, 1);
1050 		// Stack: ref [length] index length
1051 		// check out-of-bounds access
1052 		m_context << Instruction::DUP2 << Instruction::LT << Instruction::ISZERO;
1053 		// out-of-bounds access throws exception
1054 		m_context.appendConditionalPanic(util::PanicCode::ArrayOutOfBounds);
1055 	}
1056 	if (location == DataLocation::CallData && _arrayType.isDynamicallySized())
1057 		// remove length if present
1058 		m_context << Instruction::SWAP1 << Instruction::POP;
1059 
1060 	// stack: <base_ref> <index>
1061 	switch (location)
1062 	{
1063 	case DataLocation::Memory:
1064 		// stack: <base_ref> <index>
1065 		if (!_arrayType.isByteArray())
1066 			m_context << u256(_arrayType.memoryHeadSize()) << Instruction::MUL;
1067 		if (_arrayType.isDynamicallySized())
1068 			m_context << u256(32) << Instruction::ADD;
1069 		if (_keepReference)
1070 			m_context << Instruction::DUP2;
1071 		m_context << Instruction::ADD;
1072 		break;
1073 	case DataLocation::CallData:
1074 		if (!_arrayType.isByteArray())
1075 		{
1076 			m_context << _arrayType.calldataStride();
1077 			m_context << Instruction::MUL;
1078 		}
1079 		// stack: <base_ref> <index * size>
1080 		if (_keepReference)
1081 			m_context << Instruction::DUP2;
1082 		m_context << Instruction::ADD;
1083 		break;
1084 	case DataLocation::Storage:
1085 	{
1086 		if (_keepReference)
1087 			m_context << Instruction::DUP2;
1088 		else
1089 			m_context << Instruction::SWAP1;
1090 		// stack: [<base_ref>] <index> <base_ref>
1091 
1092 		evmasm::AssemblyItem endTag = m_context.newTag();
1093 		if (_arrayType.isByteArray())
1094 		{
1095 			// Special case of short byte arrays.
1096 			m_context << Instruction::SWAP1;
1097 			m_context << Instruction::DUP2 << Instruction::SLOAD;
1098 			m_context << u256(1) << Instruction::AND << Instruction::ISZERO;
1099 			// No action needed for short byte arrays.
1100 			m_context.appendConditionalJumpTo(endTag);
1101 			m_context << Instruction::SWAP1;
1102 		}
1103 		if (_arrayType.isDynamicallySized())
1104 			CompilerUtils(m_context).computeHashStatic();
1105 		m_context << Instruction::SWAP1;
1106 		if (_arrayType.baseType()->storageBytes() <= 16)
1107 		{
1108 			// stack: <data_ref> <index>
1109 			// goal:
1110 			// <ref> <byte_number> = <base_ref + index / itemsPerSlot> <(index % itemsPerSlot) * byteSize>
1111 			unsigned byteSize = _arrayType.baseType()->storageBytes();
1112 			solAssert(byteSize != 0, "");
1113 			unsigned itemsPerSlot = 32 / byteSize;
1114 			m_context << u256(itemsPerSlot) << Instruction::SWAP2;
1115 			// stack: itemsPerSlot index data_ref
1116 			m_context
1117 				<< Instruction::DUP3 << Instruction::DUP3
1118 				<< Instruction::DIV << Instruction::ADD
1119 			// stack: itemsPerSlot index (data_ref + index / itemsPerSlot)
1120 				<< Instruction::SWAP2 << Instruction::SWAP1
1121 				<< Instruction::MOD;
1122 			if (byteSize != 1)
1123 				m_context << u256(byteSize) << Instruction::MUL;
1124 		}
1125 		else
1126 		{
1127 			if (_arrayType.baseType()->storageSize() != 1)
1128 				m_context << _arrayType.baseType()->storageSize() << Instruction::MUL;
1129 			m_context << Instruction::ADD << u256(0);
1130 		}
1131 		m_context << endTag;
1132 		break;
1133 	}
1134 	}
1135 }
1136 
accessCallDataArrayElement(ArrayType const & _arrayType,bool _doBoundsCheck) const1137 void ArrayUtils::accessCallDataArrayElement(ArrayType const& _arrayType, bool _doBoundsCheck) const
1138 {
1139 	solAssert(_arrayType.location() == DataLocation::CallData, "");
1140 	if (_arrayType.baseType()->isDynamicallyEncoded())
1141 	{
1142 		// stack layout: <base_ref> <length> <index>
1143 		ArrayUtils(m_context).accessIndex(_arrayType, _doBoundsCheck, true);
1144 		// stack layout: <base_ref> <ptr_to_tail>
1145 
1146 		CompilerUtils(m_context).accessCalldataTail(*_arrayType.baseType());
1147 		// stack layout: <tail_ref> [length]
1148 	}
1149 	else
1150 	{
1151 		ArrayUtils(m_context).accessIndex(_arrayType, _doBoundsCheck);
1152 		if (_arrayType.baseType()->isValueType())
1153 		{
1154 			solAssert(_arrayType.baseType()->storageBytes() <= 32, "");
1155 			if (
1156 				!_arrayType.isByteArray() &&
1157 				_arrayType.baseType()->storageBytes() < 32 &&
1158 				m_context.useABICoderV2()
1159 			)
1160 			{
1161 				m_context << u256(32);
1162 				CompilerUtils(m_context).abiDecodeV2({_arrayType.baseType()}, false);
1163 			}
1164 			else
1165 				CompilerUtils(m_context).loadFromMemoryDynamic(
1166 					*_arrayType.baseType(),
1167 					true,
1168 					!_arrayType.isByteArray(),
1169 					false
1170 				);
1171 		}
1172 		else
1173 			solAssert(
1174 				_arrayType.baseType()->category() == Type::Category::Struct ||
1175 				_arrayType.baseType()->category() == Type::Category::Array,
1176 				"Invalid statically sized non-value base type on array access."
1177 			);
1178 	}
1179 }
1180 
incrementByteOffset(unsigned _byteSize,unsigned _byteOffsetPosition,unsigned _storageOffsetPosition) const1181 void ArrayUtils::incrementByteOffset(unsigned _byteSize, unsigned _byteOffsetPosition, unsigned _storageOffsetPosition) const
1182 {
1183 	solAssert(_byteSize < 32, "");
1184 	solAssert(_byteSize != 0, "");
1185 	// We do the following, but avoiding jumps:
1186 	// byteOffset += byteSize
1187 	// if (byteOffset + byteSize > 32)
1188 	// {
1189 	//     storageOffset++;
1190 	//     byteOffset = 0;
1191 	// }
1192 	if (_byteOffsetPosition > 1)
1193 		m_context << swapInstruction(_byteOffsetPosition - 1);
1194 	m_context << u256(_byteSize) << Instruction::ADD;
1195 	if (_byteOffsetPosition > 1)
1196 		m_context << swapInstruction(_byteOffsetPosition - 1);
1197 	// compute, X := (byteOffset + byteSize - 1) / 32, should be 1 iff byteOffset + bytesize > 32
1198 	m_context
1199 		<< u256(32) << dupInstruction(1 + _byteOffsetPosition) << u256(_byteSize - 1)
1200 		<< Instruction::ADD << Instruction::DIV;
1201 	// increment storage offset if X == 1 (just add X to it)
1202 	// stack: X
1203 	m_context
1204 		<< swapInstruction(_storageOffsetPosition) << dupInstruction(_storageOffsetPosition + 1)
1205 		<< Instruction::ADD << swapInstruction(_storageOffsetPosition);
1206 	// stack: X
1207 	// set source_byte_offset to zero if X == 1 (using source_byte_offset *= 1 - X)
1208 	m_context << u256(1) << Instruction::SUB;
1209 	// stack: 1 - X
1210 	if (_byteOffsetPosition == 1)
1211 		m_context << Instruction::MUL;
1212 	else
1213 		m_context
1214 			<< dupInstruction(_byteOffsetPosition + 1) << Instruction::MUL
1215 			<< swapInstruction(_byteOffsetPosition) << Instruction::POP;
1216 }
1217