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