/*

This file is part of solidity.

solidity is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

solidity is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with solidity. If not, see <http://www.gnu.org/licenses/>.

*/

// SPDX-License-Identifier: GPL-3.0

/**

* Component that can generate various useful Yul functions.

*/

#include <libsolidity/codegen/YulUtilFunctions.h>

#include <libsolidity/codegen/MultiUseYulFunctionCollector.h>

#include <libsolidity/ast/AST.h>

#include <libsolidity/codegen/CompilerUtils.h>

#include <libsolutil/CommonData.h>

#include <libsolutil/FunctionSelector.h>

#include <libsolutil/Whiskers.h>

#include <libsolutil/StringUtils.h>

using namespace std;

using namespace solidity;

using namespace solidity::util;

using namespace solidity::frontend;

string YulUtilFunctions::identityFunction()

{

string functionName = "identity";

return m_functionCollector.createFunction("identity", [&](vector<string>& _args, vector<string>& _rets) {

_args.push_back("value");

_rets.push_back("ret");

return "ret := value";

});

}

string YulUtilFunctions::combineExternalFunctionIdFunction()

{

string functionName = "combine_external_function_id";

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>(addr, selector) -> combined {

combined := <shl64>(or(<shl32>(addr), and(selector, 0xffffffff)))

}

)")

("functionName", functionName)

("shl32", shiftLeftFunction(32))

("shl64", shiftLeftFunction(64))

.render();

});

}

string YulUtilFunctions::splitExternalFunctionIdFunction()

{

string functionName = "split_external_function_id";

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>(combined) -> addr, selector {

combined := <shr64>(combined)

selector := and(combined, 0xffffffff)

addr := <shr32>(combined)

}

)")

("functionName", functionName)

("shr32", shiftRightFunction(32))

("shr64", shiftRightFunction(64))

.render();

});

}

string YulUtilFunctions::copyToMemoryFunction(bool _fromCalldata)

{

string functionName = "copy_" + string(_fromCalldata ? "calldata" : "memory") + "_to_memory";

return m_functionCollector.createFunction(functionName, [&]() {

if (_fromCalldata)

{

return Whiskers(R"(

function <functionName>(src, dst, length) {

calldatacopy(dst, src, length)

// clear end

mstore(add(dst, length), 0)

}

)")

("functionName", functionName)

.render();

}

else

{

return Whiskers(R"(

function <functionName>(src, dst, length) {

let i := 0

for { } lt(i, length) { i := add(i, 32) }

{

mstore(add(dst, i), mload(add(src, i)))

}

if gt(i, length)

{

// clear end

mstore(add(dst, length), 0)

}

}

)")

("functionName", functionName)

.render();

}

});

}

string YulUtilFunctions::copyLiteralToMemoryFunction(string const& _literal)

{

string functionName = "copy_literal_to_memory_" + util::toHex(util::keccak256(_literal).asBytes());

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>() -> memPtr {

memPtr := <arrayAllocationFunction>(<size>)

<storeLiteralInMem>(add(memPtr, 32))

}

)")

("functionName", functionName)

("arrayAllocationFunction", allocateMemoryArrayFunction(*TypeProvider::array(DataLocation::Memory, true)))

("size", to_string(_literal.size()))

("storeLiteralInMem", storeLiteralInMemoryFunction(_literal))

.render();

});

}

string YulUtilFunctions::storeLiteralInMemoryFunction(string const& _literal)

{

string functionName = "store_literal_in_memory_" + util::toHex(util::keccak256(_literal).asBytes());

return m_functionCollector.createFunction(functionName, [&]() {

size_t words = (_literal.length() + 31) / 32;

vector<map<string, string>> wordParams(words);

for (size_t i = 0; i < words; ++i)

{

wordParams[i]["offset"] = to_string(i * 32);

wordParams[i]["wordValue"] = formatAsStringOrNumber(_literal.substr(32 * i, 32));

}

return Whiskers(R"(

function <functionName>(memPtr) {

<#word>

mstore(add(memPtr, <offset>), <wordValue>)

</word>

}

)")

("functionName", functionName)

("word", wordParams)

.render();

});

}

string YulUtilFunctions::copyLiteralToStorageFunction(string const& _literal)

{

string functionName = "copy_literal_to_storage_" + util::toHex(util::keccak256(_literal).asBytes());

return m_functionCollector.createFunction(functionName, [&](vector<string>& _args, vector<string>&) {

_args = {"slot"};

if (_literal.size() >= 32)

{

size_t words = (_literal.length() + 31) / 32;

vector<map<string, string>> wordParams(words);

for (size_t i = 0; i < words; ++i)

{

wordParams[i]["offset"] = to_string(i);

wordParams[i]["wordValue"] = formatAsStringOrNumber(_literal.substr(32 * i, 32));

}

return Whiskers(R"(

let oldLen := <byteArrayLength>(sload(slot))

<cleanUpArrayEnd>(slot, oldLen, <length>)

sstore(slot, <encodedLen>)

let dstPtr := <dataArea>(slot)

<#word>

sstore(add(dstPtr, <offset>), <wordValue>)

</word>

)")

("byteArrayLength", extractByteArrayLengthFunction())

("cleanUpArrayEnd", cleanUpDynamicByteArrayEndSlotsFunction(*TypeProvider::bytesStorage()))

("dataArea", arrayDataAreaFunction(*TypeProvider::bytesStorage()))

("word", wordParams)

("length", to_string(_literal.size()))

("encodedLen", to_string(2 * _literal.size() + 1))

.render();

}

else

return Whiskers(R"(

let oldLen := <byteArrayLength>(sload(slot))

<cleanUpArrayEnd>(slot, oldLen, <length>)

sstore(slot, add(<wordValue>, <encodedLen>))

)")

("byteArrayLength", extractByteArrayLengthFunction())

("cleanUpArrayEnd", cleanUpDynamicByteArrayEndSlotsFunction(*TypeProvider::bytesStorage()))

("wordValue", formatAsStringOrNumber(_literal))

("length", to_string(_literal.size()))

("encodedLen", to_string(2 * _literal.size()))

.render();

});

}

string YulUtilFunctions::requireOrAssertFunction(bool _assert, Type const* _messageType)

{

string functionName =

string(_assert ? "assert_helper" : "require_helper") +

(_messageType ? ("_" + _messageType->identifier()) : "");

solAssert(!_assert || !_messageType, "Asserts can't have messages!");

return m_functionCollector.createFunction(functionName, [&]() {

if (!_messageType)

return Whiskers(R"(

function <functionName>(condition) {

if iszero(condition) { <error> }

}

)")

("error", _assert ? panicFunction(PanicCode::Assert) + "()" : "revert(0, 0)")

("functionName", functionName)

.render();

int const hashHeaderSize = 4;

u256 const errorHash = util::selectorFromSignature("Error(string)");

string const encodeFunc = ABIFunctions(m_evmVersion, m_revertStrings, m_functionCollector)

.tupleEncoder(

{_messageType},

{TypeProvider::stringMemory()}

);

return Whiskers(R"(

function <functionName>(condition <messageVars>) {

if iszero(condition) {

let memPtr := <allocateUnbounded>()

mstore(memPtr, <errorHash>)

let end := <abiEncodeFunc>(add(memPtr, <hashHeaderSize>) <messageVars>)

revert(memPtr, sub(end, memPtr))

}

}

)")

("functionName", functionName)

("allocateUnbounded", allocateUnboundedFunction())

("errorHash", formatNumber(errorHash))

("abiEncodeFunc", encodeFunc)

("hashHeaderSize", to_string(hashHeaderSize))

("messageVars",

(_messageType->sizeOnStack() > 0 ? ", " : "") +

suffixedVariableNameList("message_", 1, 1 + _messageType->sizeOnStack())

)

.render();

});

}

string YulUtilFunctions::leftAlignFunction(Type const& _type)

{

string functionName = string("leftAlign_") + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

Whiskers templ(R"(

function <functionName>(value) -> aligned {

<body>

}

)");

templ("functionName", functionName);

switch (_type.category())

{

case Type::Category::Address:

templ("body", "aligned := " + leftAlignFunction(IntegerType(160)) + "(value)");

break;

case Type::Category::Integer:

{

IntegerType const& type = dynamic_cast<IntegerType const&>(_type);

if (type.numBits() == 256)

templ("body", "aligned := value");

else

templ("body", "aligned := " + shiftLeftFunction(256 - type.numBits()) + "(value)");

break;

}

case Type::Category::RationalNumber:

solAssert(false, "Left align requested for rational number.");

break;

case Type::Category::Bool:

templ("body", "aligned := " + leftAlignFunction(IntegerType(8)) + "(value)");

break;

case Type::Category::FixedPoint:

solUnimplemented("Fixed point types not implemented.");

break;

case Type::Category::Array:

case Type::Category::Struct:

solAssert(false, "Left align requested for non-value type.");

break;

case Type::Category::FixedBytes:

templ("body", "aligned := value");

break;

case Type::Category::Contract:

templ("body", "aligned := " + leftAlignFunction(*TypeProvider::address()) + "(value)");

break;

case Type::Category::Enum:

{

solAssert(dynamic_cast<EnumType const&>(_type).storageBytes() == 1, "");

templ("body", "aligned := " + leftAlignFunction(IntegerType(8)) + "(value)");

break;

}

case Type::Category::InaccessibleDynamic:

solAssert(false, "Left align requested for inaccessible dynamic type.");

break;

default:

solAssert(false, "Left align of type " + _type.identifier() + " requested.");

}

return templ.render();

});

}

string YulUtilFunctions::shiftLeftFunction(size_t _numBits)

{

solAssert(_numBits < 256, "");

string functionName = "shift_left_" + to_string(_numBits);

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value) -> newValue {

newValue :=

<?hasShifts>

shl(<numBits>, value)

<!hasShifts>

mul(value, <multiplier>)

</hasShifts>

}

)")

("functionName", functionName)

("numBits", to_string(_numBits))

("hasShifts", m_evmVersion.hasBitwiseShifting())

("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))

.render();

});

}

string YulUtilFunctions::shiftLeftFunctionDynamic()

{

string functionName = "shift_left_dynamic";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(bits, value) -> newValue {

newValue :=

<?hasShifts>

shl(bits, value)

<!hasShifts>

mul(value, exp(2, bits))

</hasShifts>

}

)")

("functionName", functionName)

("hasShifts", m_evmVersion.hasBitwiseShifting())

.render();

});

}

string YulUtilFunctions::shiftRightFunction(size_t _numBits)

{

solAssert(_numBits < 256, "");

// Note that if this is extended with signed shifts,

// the opcodes SAR and SDIV behave differently with regards to rounding!

string functionName = "shift_right_" + to_string(_numBits) + "_unsigned";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value) -> newValue {

newValue :=

<?hasShifts>

shr(<numBits>, value)

<!hasShifts>

div(value, <multiplier>)

</hasShifts>

}

)")

("functionName", functionName)

("hasShifts", m_evmVersion.hasBitwiseShifting())

("numBits", to_string(_numBits))

("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))

.render();

});

}

string YulUtilFunctions::shiftRightFunctionDynamic()

{

string const functionName = "shift_right_unsigned_dynamic";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(bits, value) -> newValue {

newValue :=

<?hasShifts>

shr(bits, value)

<!hasShifts>

div(value, exp(2, bits))

</hasShifts>

}

)")

("functionName", functionName)

("hasShifts", m_evmVersion.hasBitwiseShifting())

.render();

});

}

string YulUtilFunctions::shiftRightSignedFunctionDynamic()

{

string const functionName = "shift_right_signed_dynamic";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(bits, value) -> result {

<?hasShifts>

result := sar(bits, value)

<!hasShifts>

let divisor := exp(2, bits)

let xor_mask := sub(0, slt(value, 0))

result := xor(div(xor(value, xor_mask), divisor), xor_mask)

// combined version of

// switch slt(value, 0)

// case 0 { result := div(value, divisor) }

// default { result := not(div(not(value), divisor)) }

</hasShifts>

}

)")

("functionName", functionName)

("hasShifts", m_evmVersion.hasBitwiseShifting())

.render();

});

}

string YulUtilFunctions::typedShiftLeftFunction(Type const& _type, Type const& _amountType)

{

solUnimplementedAssert(_type.category() != Type::Category::FixedPoint, "Not yet implemented - FixedPointType.");

solAssert(_type.category() == Type::Category::FixedBytes || _type.category() == Type::Category::Integer, "");

solAssert(_amountType.category() == Type::Category::Integer, "");

solAssert(!dynamic_cast<IntegerType const&>(_amountType).isSigned(), "");

string const functionName = "shift_left_" + _type.identifier() + "_" + _amountType.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value, bits) -> result {

bits := <cleanAmount>(bits)

result := <cleanup>(<shift>(bits, <cleanup>(value)))

}

)")

("functionName", functionName)

("cleanAmount", cleanupFunction(_amountType))

("shift", shiftLeftFunctionDynamic())

("cleanup", cleanupFunction(_type))

.render();

});

}

string YulUtilFunctions::typedShiftRightFunction(Type const& _type, Type const& _amountType)

{

solUnimplementedAssert(_type.category() != Type::Category::FixedPoint, "Not yet implemented - FixedPointType.");

solAssert(_type.category() == Type::Category::FixedBytes || _type.category() == Type::Category::Integer, "");

solAssert(_amountType.category() == Type::Category::Integer, "");

solAssert(!dynamic_cast<IntegerType const&>(_amountType).isSigned(), "");

IntegerType const* integerType = dynamic_cast<IntegerType const*>(&_type);

bool valueSigned = integerType && integerType->isSigned();

string const functionName = "shift_right_" + _type.identifier() + "_" + _amountType.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value, bits) -> result {

bits := <cleanAmount>(bits)

result := <cleanup>(<shift>(bits, <cleanup>(value)))

}

)")

("functionName", functionName)

("cleanAmount", cleanupFunction(_amountType))

("shift", valueSigned ? shiftRightSignedFunctionDynamic() : shiftRightFunctionDynamic())

("cleanup", cleanupFunction(_type))

.render();

});

}

string YulUtilFunctions::updateByteSliceFunction(size_t _numBytes, size_t _shiftBytes)

{

solAssert(_numBytes <= 32, "");

solAssert(_shiftBytes <= 32, "");

size_t numBits = _numBytes * 8;

size_t shiftBits = _shiftBytes * 8;

string functionName = "update_byte_slice_" + to_string(_numBytes) + "_shift_" + to_string(_shiftBytes);

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value, toInsert) -> result {

let mask := <mask>

toInsert := <shl>(toInsert)

value := and(value, not(mask))

result := or(value, and(toInsert, mask))

}

)")

("functionName", functionName)

("mask", formatNumber(((bigint(1) << numBits) - 1) << shiftBits))

("shl", shiftLeftFunction(shiftBits))

.render();

});

}

string YulUtilFunctions::updateByteSliceFunctionDynamic(size_t _numBytes)

{

solAssert(_numBytes <= 32, "");

size_t numBits = _numBytes * 8;

string functionName = "update_byte_slice_dynamic" + to_string(_numBytes);

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value, shiftBytes, toInsert) -> result {

let shiftBits := mul(shiftBytes, 8)

let mask := <shl>(shiftBits, <mask>)

toInsert := <shl>(shiftBits, toInsert)

value := and(value, not(mask))

result := or(value, and(toInsert, mask))

}

)")

("functionName", functionName)

("mask", formatNumber((bigint(1) << numBits) - 1))

("shl", shiftLeftFunctionDynamic())

.render();

});

}

string YulUtilFunctions::maskBytesFunctionDynamic()

{

string functionName = "mask_bytes_dynamic";

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>(data, bytes) -> result {

let mask := not(<shr>(mul(8, bytes), not(0)))

result := and(data, mask)

})")

("functionName", functionName)

("shr", shiftRightFunctionDynamic())

.render();

});

}

string YulUtilFunctions::maskLowerOrderBytesFunction(size_t _bytes)

{

string functionName = "mask_lower_order_bytes_" + to_string(_bytes);

solAssert(_bytes <= 32, "");

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>(data) -> result {

result := and(data, <mask>)

})")

("functionName", functionName)

("mask", formatNumber((~u256(0)) >> (256 - 8 * _bytes)))

.render();

});

}

string YulUtilFunctions::maskLowerOrderBytesFunctionDynamic()

{

string functionName = "mask_lower_order_bytes_dynamic";

return m_functionCollector.createFunction(functionName, [&]() {

return Whiskers(R"(

function <functionName>(data, bytes) -> result {

let mask := not(<shl>(mul(8, bytes), not(0)))

result := and(data, mask)

})")

("functionName", functionName)

("shl", shiftLeftFunctionDynamic())

.render();

});

}

string YulUtilFunctions::roundUpFunction()

{

string functionName = "round_up_to_mul_of_32";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(value) -> result {

result := and(add(value, 31), not(31))

}

)")

("functionName", functionName)

.render();

});

}

string YulUtilFunctions::divide32CeilFunction()

{

return m_functionCollector.createFunction(

"divide_by_32_ceil",

[&](vector<string>& _args, vector<string>& _ret) {

_args = {"value"};

_ret = {"result"};

return "result := div(add(value, 31), 32)";

}

);

}

string YulUtilFunctions::overflowCheckedIntAddFunction(IntegerType const& _type)

{

string functionName = "checked_add_" + _type.identifier();

// TODO: Consider to add a special case for unsigned 256-bit integers

// and use the following instead:

// sum := add(x, y) if lt(sum, x) { <panic>() }

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> sum {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

<?signed>

// overflow, if x >= 0 and y > (maxValue - x)

if and(iszero(slt(x, 0)), sgt(y, sub(<maxValue>, x))) { <panic>() }

// underflow, if x < 0 and y < (minValue - x)

if and(slt(x, 0), slt(y, sub(<minValue>, x))) { <panic>() }

<!signed>

// overflow, if x > (maxValue - y)

if gt(x, sub(<maxValue>, y)) { <panic>() }

</signed>

sum := add(x, y)

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("maxValue", toCompactHexWithPrefix(u256(_type.maxValue())))

("minValue", toCompactHexWithPrefix(u256(_type.minValue())))

("cleanupFunction", cleanupFunction(_type))

("panic", panicFunction(PanicCode::UnderOverflow))

.render();

});

}

string YulUtilFunctions::wrappingIntAddFunction(IntegerType const& _type)

{

string functionName = "wrapping_add_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> sum {

sum := <cleanupFunction>(add(x, y))

}

)")

("functionName", functionName)

("cleanupFunction", cleanupFunction(_type))

.render();

});

}

string YulUtilFunctions::overflowCheckedIntMulFunction(IntegerType const& _type)

{

string functionName = "checked_mul_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

// Multiplication by zero could be treated separately and directly return zero.

Whiskers(R"(

function <functionName>(x, y) -> product {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

<?signed>

// overflow, if x > 0, y > 0 and x > (maxValue / y)

if and(and(sgt(x, 0), sgt(y, 0)), gt(x, div(<maxValue>, y))) { <panic>() }

// underflow, if x > 0, y < 0 and y < (minValue / x)

if and(and(sgt(x, 0), slt(y, 0)), slt(y, sdiv(<minValue>, x))) { <panic>() }

// underflow, if x < 0, y > 0 and x < (minValue / y)

if and(and(slt(x, 0), sgt(y, 0)), slt(x, sdiv(<minValue>, y))) { <panic>() }

// overflow, if x < 0, y < 0 and x < (maxValue / y)

if and(and(slt(x, 0), slt(y, 0)), slt(x, sdiv(<maxValue>, y))) { <panic>() }

<!signed>

// overflow, if x != 0 and y > (maxValue / x)

if and(iszero(iszero(x)), gt(y, div(<maxValue>, x))) { <panic>() }

</signed>

product := mul(x, y)

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("maxValue", toCompactHexWithPrefix(u256(_type.maxValue())))

("minValue", toCompactHexWithPrefix(u256(_type.minValue())))

("cleanupFunction", cleanupFunction(_type))

("panic", panicFunction(PanicCode::UnderOverflow))

.render();

});

}

string YulUtilFunctions::wrappingIntMulFunction(IntegerType const& _type)

{

string functionName = "wrapping_mul_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> product {

product := <cleanupFunction>(mul(x, y))

}

)")

("functionName", functionName)

("cleanupFunction", cleanupFunction(_type))

.render();

});

}

string YulUtilFunctions::overflowCheckedIntDivFunction(IntegerType const& _type)

{

string functionName = "checked_div_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> r {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

if iszero(y) { <panicDivZero>() }

<?signed>

// overflow for minVal / -1

if and(

eq(x, <minVal>),

eq(y, sub(0, 1))

) { <panicOverflow>() }

</signed>

r := <?signed>s</signed>div(x, y)

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("minVal", toCompactHexWithPrefix(u256(_type.minValue())))

("cleanupFunction", cleanupFunction(_type))

("panicDivZero", panicFunction(PanicCode::DivisionByZero))

("panicOverflow", panicFunction(PanicCode::UnderOverflow))

.render();

});

}

string YulUtilFunctions::wrappingIntDivFunction(IntegerType const& _type)

{

string functionName = "wrapping_div_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> r {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

if iszero(y) { <error>() }

r := <?signed>s</signed>div(x, y)

}

)")

("functionName", functionName)

("cleanupFunction", cleanupFunction(_type))

("signed", _type.isSigned())

("error", panicFunction(PanicCode::DivisionByZero))

.render();

});

}

string YulUtilFunctions::intModFunction(IntegerType const& _type)

{

string functionName = "mod_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(x, y) -> r {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

if iszero(y) { <panic>() }

r := <?signed>s</signed>mod(x, y)

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("cleanupFunction", cleanupFunction(_type))

("panic", panicFunction(PanicCode::DivisionByZero))

.render();

});

}

string YulUtilFunctions::overflowCheckedIntSubFunction(IntegerType const& _type)

{

string functionName = "checked_sub_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&] {

return

Whiskers(R"(

function <functionName>(x, y) -> diff {

x := <cleanupFunction>(x)

y := <cleanupFunction>(y)

<?signed>

// underflow, if y >= 0 and x < (minValue + y)

if and(iszero(slt(y, 0)), slt(x, add(<minValue>, y))) { <panic>() }

// overflow, if y < 0 and x > (maxValue + y)

if and(slt(y, 0), sgt(x, add(<maxValue>, y))) { <panic>() }

<!signed>

if lt(x, y) { <panic>() }

</signed>

diff := sub(x, y)

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("maxValue", toCompactHexWithPrefix(u256(_type.maxValue())))

("minValue", toCompactHexWithPrefix(u256(_type.minValue())))

("cleanupFunction", cleanupFunction(_type))

("panic", panicFunction(PanicCode::UnderOverflow))

.render();

});

}

string YulUtilFunctions::wrappingIntSubFunction(IntegerType const& _type)

{

string functionName = "wrapping_sub_" + _type.identifier();

return m_functionCollector.createFunction(functionName, [&] {

return

Whiskers(R"(

function <functionName>(x, y) -> diff {

diff := <cleanupFunction>(sub(x, y))

}

)")

("functionName", functionName)

("cleanupFunction", cleanupFunction(_type))

.render();

});

}

string YulUtilFunctions::overflowCheckedIntExpFunction(

IntegerType const& _type,

IntegerType const& _exponentType

)

{

solAssert(!_exponentType.isSigned(), "");

string functionName = "checked_exp_" + _type.identifier() + "_" + _exponentType.identifier();

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(base, exponent) -> power {

base := <baseCleanupFunction>(base)

exponent := <exponentCleanupFunction>(exponent)

<?signed>

power := <exp>(base, exponent, <minValue>, <maxValue>)

<!signed>

power := <exp>(base, exponent, <maxValue>)

</signed>

}

)")

("functionName", functionName)

("signed", _type.isSigned())

("exp", _type.isSigned() ? overflowCheckedSignedExpFunction() : overflowCheckedUnsignedExpFunction())

("maxValue", toCompactHexWithPrefix(_type.max()))

("minValue", toCompactHexWithPrefix(_type.min()))

("baseCleanupFunction", cleanupFunction(_type))

("exponentCleanupFunction", cleanupFunction(_exponentType))

.render();

});

}

string YulUtilFunctions::overflowCheckedIntLiteralExpFunction(

RationalNumberType const& _baseType,

IntegerType const& _exponentType,

IntegerType const& _commonType

)

{

solAssert(!_exponentType.isSigned(), "");

solAssert(_baseType.isNegative() == _commonType.isSigned(), "");

solAssert(_commonType.numBits() == 256, "");

string functionName = "checked_exp_" + _baseType.richIdentifier() + "_" + _exponentType.identifier();

return m_functionCollector.createFunction(functionName, [&]()

{

// Converts a bigint number into u256 (negative numbers represented in two's complement form.)

// We assume that `_v` fits in 256 bits.

auto bigint2u = [&](bigint const& _v) -> u256

{

if (_v < 0)

return s2u(s256(_v));

return u256(_v);

};

// Calculates the upperbound for exponentiation, that is, calculate `b`, such that

// _base**b <= _maxValue and _base**(b + 1) > _maxValue

auto findExponentUpperbound = [](bigint const _base, bigint const _maxValue) -> unsigned

{

// There is no overflow for these cases

if (_base == 0 || _base == -1 || _base == 1)

return 0;

unsigned first = 0;

unsigned last = 255;

unsigned middle;

while (first < last)

{

middle = (first + last) / 2;

if (

// The condition on msb is a shortcut that avoids computing large powers in

// arbitrary precision.

boost::multiprecision::msb(_base) * middle <= boost::multiprecision::msb(_maxValue) &&

boost::multiprecision::pow(_base, middle) <= _maxValue

)

{

if (boost::multiprecision::pow(_base, middle + 1) > _maxValue)

return middle;

else

first = middle + 1;

}

else

last = middle;

}

return last;

};

bigint baseValue = _baseType.isNegative() ?

u2s(_baseType.literalValue(nullptr)) :

_baseType.literalValue(nullptr);

bool needsOverflowCheck = !((baseValue == 0) || (baseValue == -1) || (baseValue == 1));

unsigned exponentUpperbound;

if (_baseType.isNegative())

{

// Only checks for underflow. The only case where this can be a problem is when, for a

// negative base, say `b`, and an even exponent, say `e`, `b**e = 2**255` (which is an

// overflow.) But this never happens because, `255 = 3*5*17`, and therefore there is no even

// number `e` such that `b**e = 2**255`.

exponentUpperbound = findExponentUpperbound(abs(baseValue), abs(_commonType.minValue()));

bigint power = boost::multiprecision::pow(baseValue, exponentUpperbound);

bigint overflowedPower = boost::multiprecision::pow(baseValue, exponentUpperbound + 1);

if (needsOverflowCheck)

solAssert(

(power <= _commonType.maxValue()) && (power >= _commonType.minValue()) &&

!((overflowedPower <= _commonType.maxValue()) && (overflowedPower >= _commonType.minValue())),

"Incorrect exponent upper bound calculated."

);

}

else

{

exponentUpperbound = findExponentUpperbound(baseValue, _commonType.maxValue());

if (needsOverflowCheck)

solAssert(

boost::multiprecision::pow(baseValue, exponentUpperbound) <= _commonType.maxValue() &&

boost::multiprecision::pow(baseValue, exponentUpperbound + 1) > _commonType.maxValue(),

"Incorrect exponent upper bound calculated."

);

}

return Whiskers(R"(

function <functionName>(exponent) -> power {

exponent := <exponentCleanupFunction>(exponent)

<?needsOverflowCheck>

if gt(exponent, <exponentUpperbound>) { <panic>() }

</needsOverflowCheck>

power := exp(<base>, exponent)

}

)")

("functionName", functionName)

("exponentCleanupFunction", cleanupFunction(_exponentType))

("needsOverflowCheck", needsOverflowCheck)

("exponentUpperbound", to_string(exponentUpperbound))

("panic", panicFunction(PanicCode::UnderOverflow))

("base", bigint2u(baseValue).str())

.render();

});

}

string YulUtilFunctions::overflowCheckedUnsignedExpFunction()

{

// Checks for the "small number specialization" below.

using namespace boost::multiprecision;

solAssert(pow(bigint(10), 77) < pow(bigint(2), 256), "");

solAssert(pow(bigint(11), 77) >= pow(bigint(2), 256), "");

solAssert(pow(bigint(10), 78) >= pow(bigint(2), 256), "");

solAssert(pow(bigint(306), 31) < pow(bigint(2), 256), "");

solAssert(pow(bigint(307), 31) >= pow(bigint(2), 256), "");

solAssert(pow(bigint(306), 32) >= pow(bigint(2), 256), "");

string functionName = "checked_exp_unsigned";

return m_functionCollector.createFunction(functionName, [&]() {

return

Whiskers(R"(

function <functionName>(base, exponent, max) -> power {

// This function currently cannot be inlined because of the

// "leave" statements. We have to improve the optimizer.

// Note that 0**0 == 1