Contract Source Code:
// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;
import { Constants } from "src/libraries/Constants.sol";
/// @title Proxy
/// @notice Proxy is a transparent proxy that passes through the call if the caller is the owner or
/// if the caller is address(0), meaning that the call originated from an off-chain
/// simulation.
contract Proxy {
/// @notice An event that is emitted each time the implementation is changed. This event is part
/// of the EIP-1967 specification.
/// @param implementation The address of the implementation contract
event Upgraded(address indexed implementation);
/// @notice An event that is emitted each time the owner is upgraded. This event is part of the
/// EIP-1967 specification.
/// @param previousAdmin The previous owner of the contract
/// @param newAdmin The new owner of the contract
event AdminChanged(address previousAdmin, address newAdmin);
/// @notice A modifier that reverts if not called by the owner or by address(0) to allow
/// eth_call to interact with this proxy without needing to use low-level storage
/// inspection. We assume that nobody is able to trigger calls from address(0) during
/// normal EVM execution.
modifier proxyCallIfNotAdmin() {
if (msg.sender == _getAdmin() || msg.sender == address(0)) {
_;
} else {
// This WILL halt the call frame on completion.
_doProxyCall();
}
}
/// @notice Sets the initial admin during contract deployment. Admin address is stored at the
/// EIP-1967 admin storage slot so that accidental storage collision with the
/// implementation is not possible.
/// @param _admin Address of the initial contract admin. Admin has the ability to access the
/// transparent proxy interface.
constructor(address _admin) {
_changeAdmin(_admin);
}
// slither-disable-next-line locked-ether
receive() external payable {
// Proxy call by default.
_doProxyCall();
}
// slither-disable-next-line locked-ether
fallback() external payable {
// Proxy call by default.
_doProxyCall();
}
/// @notice Set the implementation contract address. The code at the given address will execute
/// when this contract is called.
/// @param _implementation Address of the implementation contract.
function upgradeTo(address _implementation) public virtual proxyCallIfNotAdmin {
_setImplementation(_implementation);
}
/// @notice Set the implementation and call a function in a single transaction. Useful to ensure
/// atomic execution of initialization-based upgrades.
/// @param _implementation Address of the implementation contract.
/// @param _data Calldata to delegatecall the new implementation with.
function upgradeToAndCall(
address _implementation,
bytes calldata _data
)
public
payable
virtual
proxyCallIfNotAdmin
returns (bytes memory)
{
_setImplementation(_implementation);
(bool success, bytes memory returndata) = _implementation.delegatecall(_data);
require(success, "Proxy: delegatecall to new implementation contract failed");
return returndata;
}
/// @notice Changes the owner of the proxy contract. Only callable by the owner.
/// @param _admin New owner of the proxy contract.
function changeAdmin(address _admin) public virtual proxyCallIfNotAdmin {
_changeAdmin(_admin);
}
/// @notice Gets the owner of the proxy contract.
/// @return Owner address.
function admin() public virtual proxyCallIfNotAdmin returns (address) {
return _getAdmin();
}
//// @notice Queries the implementation address.
/// @return Implementation address.
function implementation() public virtual proxyCallIfNotAdmin returns (address) {
return _getImplementation();
}
/// @notice Sets the implementation address.
/// @param _implementation New implementation address.
function _setImplementation(address _implementation) internal {
bytes32 proxyImplementation = Constants.PROXY_IMPLEMENTATION_ADDRESS;
assembly {
sstore(proxyImplementation, _implementation)
}
emit Upgraded(_implementation);
}
/// @notice Changes the owner of the proxy contract.
/// @param _admin New owner of the proxy contract.
function _changeAdmin(address _admin) internal {
address previous = _getAdmin();
bytes32 proxyOwner = Constants.PROXY_OWNER_ADDRESS;
assembly {
sstore(proxyOwner, _admin)
}
emit AdminChanged(previous, _admin);
}
/// @notice Performs the proxy call via a delegatecall.
function _doProxyCall() internal {
address impl = _getImplementation();
require(impl != address(0), "Proxy: implementation not initialized");
assembly {
// Copy calldata into memory at 0x0....calldatasize.
calldatacopy(0x0, 0x0, calldatasize())
// Perform the delegatecall, make sure to pass all available gas.
let success := delegatecall(gas(), impl, 0x0, calldatasize(), 0x0, 0x0)
// Copy returndata into memory at 0x0....returndatasize. Note that this *will*
// overwrite the calldata that we just copied into memory but that doesn't really
// matter because we'll be returning in a second anyway.
returndatacopy(0x0, 0x0, returndatasize())
// Success == 0 means a revert. We'll revert too and pass the data up.
if iszero(success) { revert(0x0, returndatasize()) }
// Otherwise we'll just return and pass the data up.
return(0x0, returndatasize())
}
}
/// @notice Queries the implementation address.
/// @return Implementation address.
function _getImplementation() internal view returns (address) {
address impl;
bytes32 proxyImplementation = Constants.PROXY_IMPLEMENTATION_ADDRESS;
assembly {
impl := sload(proxyImplementation)
}
return impl;
}
/// @notice Queries the owner of the proxy contract.
/// @return Owner address.
function _getAdmin() internal view returns (address) {
address owner;
bytes32 proxyOwner = Constants.PROXY_OWNER_ADDRESS;
assembly {
owner := sload(proxyOwner)
}
return owner;
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import { ResourceMetering } from "src/L1/ResourceMetering.sol";
/// @title Constants
/// @notice Constants is a library for storing constants. Simple! Don't put everything in here, just
/// the stuff used in multiple contracts. Constants that only apply to a single contract
/// should be defined in that contract instead.
library Constants {
/// @notice Special address to be used as the tx origin for gas estimation calls in the
/// OptimismPortal and CrossDomainMessenger calls. You only need to use this address if
/// the minimum gas limit specified by the user is not actually enough to execute the
/// given message and you're attempting to estimate the actual necessary gas limit. We
/// use address(1) because it's the ecrecover precompile and therefore guaranteed to
/// never have any code on any EVM chain.
address internal constant ESTIMATION_ADDRESS = address(1);
/// @notice Value used for the L2 sender storage slot in both the OptimismPortal and the
/// CrossDomainMessenger contracts before an actual sender is set. This value is
/// non-zero to reduce the gas cost of message passing transactions.
address internal constant DEFAULT_L2_SENDER = 0x000000000000000000000000000000000000dEaD;
/// @notice The storage slot that holds the address of a proxy implementation.
/// @dev `bytes32(uint256(keccak256('eip1967.proxy.implementation')) - 1)`
bytes32 internal constant PROXY_IMPLEMENTATION_ADDRESS =
0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
/// @notice The storage slot that holds the address of the owner.
/// @dev `bytes32(uint256(keccak256('eip1967.proxy.admin')) - 1)`
bytes32 internal constant PROXY_OWNER_ADDRESS = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;
/// @notice Returns the default values for the ResourceConfig. These are the recommended values
/// for a production network.
function DEFAULT_RESOURCE_CONFIG() internal pure returns (ResourceMetering.ResourceConfig memory) {
ResourceMetering.ResourceConfig memory config = ResourceMetering.ResourceConfig({
maxResourceLimit: 20_000_000,
elasticityMultiplier: 10,
baseFeeMaxChangeDenominator: 8,
maxTransactionLimit: 8,
minimumBaseFee: 1 gwei,
systemTxMaxGas: 1_000_000,
maximumBaseFee: type(uint128).max
});
return config;
}
}
// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;
import { Initializable } from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import { Math } from "@openzeppelin/contracts/utils/math/Math.sol";
import { Burn } from "src/libraries/Burn.sol";
import { Arithmetic } from "src/libraries/Arithmetic.sol";
/// @custom:upgradeable
/// @title ResourceMetering
/// @notice ResourceMetering implements an EIP-1559 style resource metering system where pricing
/// updates automatically based on current demand.
abstract contract ResourceMetering is Initializable {
/// @notice Error returned when too much gas resource is consumed.
error OutOfGas();
/// @notice Represents the various parameters that control the way in which resources are
/// metered. Corresponds to the EIP-1559 resource metering system.
/// @custom:field prevBaseFee Base fee from the previous block(s).
/// @custom:field prevBoughtGas Amount of gas bought so far in the current block.
/// @custom:field prevBlockNum Last block number that the base fee was updated.
/// @custom:field prevTxCount Number of transactions in the current block.
struct ResourceParams {
uint128 prevBaseFee;
uint64 prevBoughtGas;
uint64 prevBlockNum;
uint16 prevTxCount;
}
/// @notice Represents the configuration for the EIP-1559 based curve for the deposit gas
/// market. These values should be set with care as it is possible to set them in
/// a way that breaks the deposit gas market. The target resource limit is defined as
/// maxResourceLimit / elasticityMultiplier. This struct was designed to fit within a
/// single word. There is additional space for additions in the future.
/// @custom:field maxResourceLimit Represents the maximum amount of deposit gas that
/// can be purchased per block.
/// @custom:field elasticityMultiplier Determines the target resource limit along with
/// the resource limit.
/// @custom:field baseFeeMaxChangeDenominator Determines max change on fee per block.
/// @custom:field maxTransactionLimit Determines max deposit transaction count per block.
/// @custom:field minimumBaseFee The min deposit base fee, it is clamped to this
/// value.
/// @custom:field systemTxMaxGas The amount of gas supplied to the system
/// transaction. This should be set to the same
/// number that the op-node sets as the gas limit
/// for the system transaction.
/// @custom:field maximumBaseFee The max deposit base fee, it is clamped to this
/// value.
struct ResourceConfig {
uint32 maxResourceLimit;
uint8 elasticityMultiplier;
uint8 baseFeeMaxChangeDenominator;
uint16 maxTransactionLimit;
uint32 minimumBaseFee;
uint32 systemTxMaxGas;
uint128 maximumBaseFee;
}
/// @notice EIP-1559 style gas parameters.
ResourceParams public params;
/// @notice Reserve extra slots (to a total of 50) in the storage layout for future upgrades.
uint256[48] private __gap;
event GasBurned(uint256 gasAmount, address indexed sender);
/// @notice Meters access to a function based an amount of a requested resource.
/// @param _amount Amount of the resource requested.
modifier metered(uint64 _amount) {
// Record initial gas amount so we can refund for it later.
uint256 initialGas = gasleft();
// Run the underlying function.
_;
// Run the metering function.
_metered(_amount, initialGas);
}
/// @notice An internal function that holds all of the logic for metering a resource.
/// @param _amount Amount of the resource requested.
/// @param _initialGas The amount of gas before any modifier execution.
function _metered(uint64 _amount, uint256 _initialGas) internal {
// Update block number and base fee if necessary.
uint256 blockDiff = block.number - params.prevBlockNum;
ResourceConfig memory config = _resourceConfig();
int256 targetResourceLimit =
int256(uint256(config.maxResourceLimit)) / int256(uint256(config.elasticityMultiplier));
if (blockDiff > 0) {
// Handle updating EIP-1559 style gas parameters. We use EIP-1559 to restrict the rate
// at which deposits can be created and therefore limit the potential for deposits to
// spam the L2 system. Fee scheme is very similar to EIP-1559 with minor changes.
// If limit deposit limit is hit, increase the gas fee by max amount
uint256 boughtGas = params.prevBoughtGas;
if (params.prevTxCount == config.maxTransactionLimit) {
boughtGas = Math.max(uint256(targetResourceLimit * 2), boughtGas);
}
int256 gasUsedDelta = int256(boughtGas) - targetResourceLimit;
int256 baseFeeDelta = (int256(uint256(params.prevBaseFee)) * gasUsedDelta)
/ (targetResourceLimit * int256(uint256(config.baseFeeMaxChangeDenominator)));
// Update base fee by adding the base fee delta and clamp the resulting value between
// min and max.
int256 newBaseFee = Arithmetic.clamp({
_value: int256(uint256(params.prevBaseFee)) + baseFeeDelta,
_min: int256(uint256(config.minimumBaseFee)),
_max: int256(uint256(config.maximumBaseFee))
});
// If we skipped more than one block, we also need to account for every empty block.
// Empty block means there was no demand for deposits in that block, so we should
// reflect this lack of demand in the fee.
if (blockDiff > 1) {
// Update the base fee by repeatedly applying the exponent 1-(1/change_denominator)
// blockDiff - 1 times. Simulates multiple empty blocks. Clamp the resulting value
// between min and max.
newBaseFee = Arithmetic.clamp({
_value: Arithmetic.cdexp({
_coefficient: newBaseFee,
_denominator: int256(uint256(config.baseFeeMaxChangeDenominator)),
_exponent: int256(blockDiff - 1)
}),
_min: int256(uint256(config.minimumBaseFee)),
_max: int256(uint256(config.maximumBaseFee))
});
}
// Update new base fee, reset bought gas, and update block number.
params.prevBaseFee = uint128(uint256(newBaseFee));
params.prevBoughtGas = 0;
params.prevTxCount = 0;
params.prevBlockNum = uint64(block.number);
}
params.prevTxCount += 1;
// If limit is surpassed,
require(params.prevTxCount <= config.maxTransactionLimit, "ResourceMetering: too many deposits in this block");
// Make sure we can actually buy the resource amount requested by the user.
params.prevBoughtGas += _amount;
if (int256(uint256(params.prevBoughtGas)) > int256(uint256(config.maxResourceLimit))) {
revert OutOfGas();
}
// Determine the amount of ETH to be paid.
uint256 resourceCost = uint256(_amount) * uint256(params.prevBaseFee);
// We currently charge for this ETH amount as an L1 gas burn, so we convert the ETH amount
// into gas by dividing by the L1 base fee. We assume a minimum base fee of 1 gwei to avoid
// division by zero for L1s that don't support 1559 or to avoid excessive gas burns during
// periods of extremely low L1 demand. One-day average gas fee hasn't dipped below 1 gwei
// during any 1 day period in the last 5 years, so should be fine.
uint256 gasCost = resourceCost / Math.max(block.basefee, 1 gwei);
// Give the user a refund based on the amount of gas they used to do all of the work up to
// this point. Since we're at the end of the modifier, this should be pretty accurate. Acts
// effectively like a dynamic stipend (with a minimum value).
uint256 usedGas = _initialGas - gasleft();
if (gasCost > usedGas) {
// We calculate gasToBurn based on the resourceCosts, but reserve some Gas for an event
// that keeps track of the GasBurned. There we add the costs for the event because we
// would be burning it otherwise
uint256 gasToBurn = gasCost - usedGas;
// Gas Costs For Event:
// 375 Per LOG* operation.
// 375 per indexed parameter
// 8 Per byte in a LOG* operation's data.
// 375 + 375 + 256 + 160 = 1166 (uint256 32 bytes, address 20bytes)
uint256 estimatedEventGasCosts = 1200;
// Ensure gasToBurn is greater than estimatedEventGasCosts to avoid underflow
if (gasToBurn > estimatedEventGasCosts) {
emit GasBurned(gasToBurn - estimatedEventGasCosts, tx.origin);
// Subtract estimatedEventGasCosts because the event emission accounts for this already
Burn.gas(gasToBurn - estimatedEventGasCosts);
} else {
// Handle case where gasToBurn is not enough to cover estimatedEventGasCosts
// Emit event with what we have and burn zero gas
emit GasBurned(estimatedEventGasCosts, tx.origin);
Burn.gas(0);
}
}
}
/// @notice Virtual function that returns the resource config.
/// Contracts that inherit this contract must implement this function.
/// @return ResourceConfig
function _resourceConfig() internal virtual returns (ResourceConfig memory);
/// @notice Sets initial resource parameter values.
/// This function must either be called by the initializer function of an upgradeable
/// child contract.
// solhint-disable-next-line func-name-mixedcase
function __ResourceMetering_init() internal onlyInitializing {
if (params.prevBlockNum == 0) {
params = ResourceParams({ prevBaseFee: 1 gwei, prevBoughtGas: 0, prevBlockNum: uint64(block.number), prevTxCount: 0 });
}
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (proxy/utils/Initializable.sol)
pragma solidity ^0.8.20;
/**
* @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
* behind a proxy. Since proxied contracts do not make use of a constructor, it's common to move constructor logic to an
* external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
* function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
*
* The initialization functions use a version number. Once a version number is used, it is consumed and cannot be
* reused. This mechanism prevents re-execution of each "step" but allows the creation of new initialization steps in
* case an upgrade adds a module that needs to be initialized.
*
* For example:
*
* [.hljs-theme-light.nopadding]
* ```solidity
* contract MyToken is ERC20Upgradeable {
* function initialize() initializer public {
* __ERC20_init("MyToken", "MTK");
* }
* }
*
* contract MyTokenV2 is MyToken, ERC20PermitUpgradeable {
* function initializeV2() reinitializer(2) public {
* __ERC20Permit_init("MyToken");
* }
* }
* ```
*
* TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
* possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
*
* CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
* that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
*
* [CAUTION]
* ====
* Avoid leaving a contract uninitialized.
*
* An uninitialized contract can be taken over by an attacker. This applies to both a proxy and its implementation
* contract, which may impact the proxy. To prevent the implementation contract from being used, you should invoke
* the {_disableInitializers} function in the constructor to automatically lock it when it is deployed:
*
* [.hljs-theme-light.nopadding]
* ```
* /// @custom:oz-upgrades-unsafe-allow constructor
* constructor() {
* _disableInitializers();
* }
* ```
* ====
*/
abstract contract Initializable {
/**
* @dev Storage of the initializable contract.
*
* It's implemented on a custom ERC-7201 namespace to reduce the risk of storage collisions
* when using with upgradeable contracts.
*
* @custom:storage-location erc7201:openzeppelin.storage.Initializable
*/
struct InitializableStorage {
/**
* @dev Indicates that the contract has been initialized.
*/
uint64 _initialized;
/**
* @dev Indicates that the contract is in the process of being initialized.
*/
bool _initializing;
}
// keccak256(abi.encode(uint256(keccak256("openzeppelin.storage.Initializable")) - 1)) & ~bytes32(uint256(0xff))
bytes32 private constant INITIALIZABLE_STORAGE = 0xf0c57e16840df040f15088dc2f81fe391c3923bec73e23a9662efc9c229c6a00;
/**
* @dev The contract is already initialized.
*/
error InvalidInitialization();
/**
* @dev The contract is not initializing.
*/
error NotInitializing();
/**
* @dev Triggered when the contract has been initialized or reinitialized.
*/
event Initialized(uint64 version);
/**
* @dev A modifier that defines a protected initializer function that can be invoked at most once. In its scope,
* `onlyInitializing` functions can be used to initialize parent contracts.
*
* Similar to `reinitializer(1)`, except that in the context of a constructor an `initializer` may be invoked any
* number of times. This behavior in the constructor can be useful during testing and is not expected to be used in
* production.
*
* Emits an {Initialized} event.
*/
modifier initializer() {
// solhint-disable-next-line var-name-mixedcase
InitializableStorage storage $ = _getInitializableStorage();
// Cache values to avoid duplicated sloads
bool isTopLevelCall = !$._initializing;
uint64 initialized = $._initialized;
// Allowed calls:
// - initialSetup: the contract is not in the initializing state and no previous version was
// initialized
// - construction: the contract is initialized at version 1 (no reininitialization) and the
// current contract is just being deployed
bool initialSetup = initialized == 0 && isTopLevelCall;
bool construction = initialized == 1 && address(this).code.length == 0;
if (!initialSetup && !construction) {
revert InvalidInitialization();
}
$._initialized = 1;
if (isTopLevelCall) {
$._initializing = true;
}
_;
if (isTopLevelCall) {
$._initializing = false;
emit Initialized(1);
}
}
/**
* @dev A modifier that defines a protected reinitializer function that can be invoked at most once, and only if the
* contract hasn't been initialized to a greater version before. In its scope, `onlyInitializing` functions can be
* used to initialize parent contracts.
*
* A reinitializer may be used after the original initialization step. This is essential to configure modules that
* are added through upgrades and that require initialization.
*
* When `version` is 1, this modifier is similar to `initializer`, except that functions marked with `reinitializer`
* cannot be nested. If one is invoked in the context of another, execution will revert.
*
* Note that versions can jump in increments greater than 1; this implies that if multiple reinitializers coexist in
* a contract, executing them in the right order is up to the developer or operator.
*
* WARNING: Setting the version to 2**64 - 1 will prevent any future reinitialization.
*
* Emits an {Initialized} event.
*/
modifier reinitializer(uint64 version) {
// solhint-disable-next-line var-name-mixedcase
InitializableStorage storage $ = _getInitializableStorage();
if ($._initializing || $._initialized >= version) {
revert InvalidInitialization();
}
$._initialized = version;
$._initializing = true;
_;
$._initializing = false;
emit Initialized(version);
}
/**
* @dev Modifier to protect an initialization function so that it can only be invoked by functions with the
* {initializer} and {reinitializer} modifiers, directly or indirectly.
*/
modifier onlyInitializing() {
_checkInitializing();
_;
}
/**
* @dev Reverts if the contract is not in an initializing state. See {onlyInitializing}.
*/
function _checkInitializing() internal view virtual {
if (!_isInitializing()) {
revert NotInitializing();
}
}
/**
* @dev Locks the contract, preventing any future reinitialization. This cannot be part of an initializer call.
* Calling this in the constructor of a contract will prevent that contract from being initialized or reinitialized
* to any version. It is recommended to use this to lock implementation contracts that are designed to be called
* through proxies.
*
* Emits an {Initialized} event the first time it is successfully executed.
*/
function _disableInitializers() internal virtual {
// solhint-disable-next-line var-name-mixedcase
InitializableStorage storage $ = _getInitializableStorage();
if ($._initializing) {
revert InvalidInitialization();
}
if ($._initialized != type(uint64).max) {
$._initialized = type(uint64).max;
emit Initialized(type(uint64).max);
}
}
/**
* @dev Returns the highest version that has been initialized. See {reinitializer}.
*/
function _getInitializedVersion() internal view returns (uint64) {
return _getInitializableStorage()._initialized;
}
/**
* @dev Returns `true` if the contract is currently initializing. See {onlyInitializing}.
*/
function _isInitializing() internal view returns (bool) {
return _getInitializableStorage()._initializing;
}
/**
* @dev Returns a pointer to the storage namespace.
*/
// solhint-disable-next-line var-name-mixedcase
function _getInitializableStorage() private pure returns (InitializableStorage storage $) {
assembly {
$.slot := INITIALIZABLE_STORAGE
}
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/math/Math.sol)
pragma solidity ^0.8.20;
/**
* @dev Standard math utilities missing in the Solidity language.
*/
library Math {
/**
* @dev Muldiv operation overflow.
*/
error MathOverflowedMulDiv();
enum Rounding {
Floor, // Toward negative infinity
Ceil, // Toward positive infinity
Trunc, // Toward zero
Expand // Away from zero
}
/**
* @dev Returns the addition of two unsigned integers, with an overflow flag.
*/
function tryAdd(uint256 a, uint256 b) internal pure returns (bool, uint256) {
unchecked {
uint256 c = a + b;
if (c < a) return (false, 0);
return (true, c);
}
}
/**
* @dev Returns the subtraction of two unsigned integers, with an overflow flag.
*/
function trySub(uint256 a, uint256 b) internal pure returns (bool, uint256) {
unchecked {
if (b > a) return (false, 0);
return (true, a - b);
}
}
/**
* @dev Returns the multiplication of two unsigned integers, with an overflow flag.
*/
function tryMul(uint256 a, uint256 b) internal pure returns (bool, uint256) {
unchecked {
// Gas optimization: this is cheaper than requiring 'a' not being zero, but the
// benefit is lost if 'b' is also tested.
// See: https://github.com/OpenZeppelin/openzeppelin-contracts/pull/522
if (a == 0) return (true, 0);
uint256 c = a * b;
if (c / a != b) return (false, 0);
return (true, c);
}
}
/**
* @dev Returns the division of two unsigned integers, with a division by zero flag.
*/
function tryDiv(uint256 a, uint256 b) internal pure returns (bool, uint256) {
unchecked {
if (b == 0) return (false, 0);
return (true, a / b);
}
}
/**
* @dev Returns the remainder of dividing two unsigned integers, with a division by zero flag.
*/
function tryMod(uint256 a, uint256 b) internal pure returns (bool, uint256) {
unchecked {
if (b == 0) return (false, 0);
return (true, a % b);
}
}
/**
* @dev Returns the largest of two numbers.
*/
function max(uint256 a, uint256 b) internal pure returns (uint256) {
return a > b ? a : b;
}
/**
* @dev Returns the smallest of two numbers.
*/
function min(uint256 a, uint256 b) internal pure returns (uint256) {
return a < b ? a : b;
}
/**
* @dev Returns the average of two numbers. The result is rounded towards
* zero.
*/
function average(uint256 a, uint256 b) internal pure returns (uint256) {
// (a + b) / 2 can overflow.
return (a & b) + (a ^ b) / 2;
}
/**
* @dev Returns the ceiling of the division of two numbers.
*
* This differs from standard division with `/` in that it rounds towards infinity instead
* of rounding towards zero.
*/
function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
if (b == 0) {
// Guarantee the same behavior as in a regular Solidity division.
return a / b;
}
// (a + b - 1) / b can overflow on addition, so we distribute.
return a == 0 ? 0 : (a - 1) / b + 1;
}
/**
* @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or
* denominator == 0.
* @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv) with further edits by
* Uniswap Labs also under MIT license.
*/
function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256 result) {
unchecked {
// 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
// use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
// variables such that product = prod1 * 2^256 + prod0.
uint256 prod0 = x * y; // Least significant 256 bits of the product
uint256 prod1; // Most significant 256 bits of the product
assembly {
let mm := mulmod(x, y, not(0))
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
// Handle non-overflow cases, 256 by 256 division.
if (prod1 == 0) {
// Solidity will revert if denominator == 0, unlike the div opcode on its own.
// The surrounding unchecked block does not change this fact.
// See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
return prod0 / denominator;
}
// Make sure the result is less than 2^256. Also prevents denominator == 0.
if (denominator <= prod1) {
revert MathOverflowedMulDiv();
}
///////////////////////////////////////////////
// 512 by 256 division.
///////////////////////////////////////////////
// Make division exact by subtracting the remainder from [prod1 prod0].
uint256 remainder;
assembly {
// Compute remainder using mulmod.
remainder := mulmod(x, y, denominator)
// Subtract 256 bit number from 512 bit number.
prod1 := sub(prod1, gt(remainder, prod0))
prod0 := sub(prod0, remainder)
}
// Factor powers of two out of denominator and compute largest power of two divisor of denominator.
// Always >= 1. See https://cs.stackexchange.com/q/138556/92363.
uint256 twos = denominator & (0 - denominator);
assembly {
// Divide denominator by twos.
denominator := div(denominator, twos)
// Divide [prod1 prod0] by twos.
prod0 := div(prod0, twos)
// Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
twos := add(div(sub(0, twos), twos), 1)
}
// Shift in bits from prod1 into prod0.
prod0 |= prod1 * twos;
// Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
// that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
// four bits. That is, denominator * inv = 1 mod 2^4.
uint256 inverse = (3 * denominator) ^ 2;
// Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also
// works in modular arithmetic, doubling the correct bits in each step.
inverse *= 2 - denominator * inverse; // inverse mod 2^8
inverse *= 2 - denominator * inverse; // inverse mod 2^16
inverse *= 2 - denominator * inverse; // inverse mod 2^32
inverse *= 2 - denominator * inverse; // inverse mod 2^64
inverse *= 2 - denominator * inverse; // inverse mod 2^128
inverse *= 2 - denominator * inverse; // inverse mod 2^256
// Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
// This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
// less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
// is no longer required.
result = prod0 * inverse;
return result;
}
}
/**
* @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
*/
function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256) {
uint256 result = mulDiv(x, y, denominator);
if (unsignedRoundsUp(rounding) && mulmod(x, y, denominator) > 0) {
result += 1;
}
return result;
}
/**
* @dev Returns the square root of a number. If the number is not a perfect square, the value is rounded
* towards zero.
*
* Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
*/
function sqrt(uint256 a) internal pure returns (uint256) {
if (a == 0) {
return 0;
}
// For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
//
// We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
// `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
//
// This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
// → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
// → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
//
// Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
uint256 result = 1 << (log2(a) >> 1);
// At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
// since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
// every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
// into the expected uint128 result.
unchecked {
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
result = (result + a / result) >> 1;
return min(result, a / result);
}
}
/**
* @notice Calculates sqrt(a), following the selected rounding direction.
*/
function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
unchecked {
uint256 result = sqrt(a);
return result + (unsignedRoundsUp(rounding) && result * result < a ? 1 : 0);
}
}
/**
* @dev Return the log in base 2 of a positive value rounded towards zero.
* Returns 0 if given 0.
*/
function log2(uint256 value) internal pure returns (uint256) {
uint256 result = 0;
unchecked {
if (value >> 128 > 0) {
value >>= 128;
result += 128;
}
if (value >> 64 > 0) {
value >>= 64;
result += 64;
}
if (value >> 32 > 0) {
value >>= 32;
result += 32;
}
if (value >> 16 > 0) {
value >>= 16;
result += 16;
}
if (value >> 8 > 0) {
value >>= 8;
result += 8;
}
if (value >> 4 > 0) {
value >>= 4;
result += 4;
}
if (value >> 2 > 0) {
value >>= 2;
result += 2;
}
if (value >> 1 > 0) {
result += 1;
}
}
return result;
}
/**
* @dev Return the log in base 2, following the selected rounding direction, of a positive value.
* Returns 0 if given 0.
*/
function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
unchecked {
uint256 result = log2(value);
return result + (unsignedRoundsUp(rounding) && 1 << result < value ? 1 : 0);
}
}
/**
* @dev Return the log in base 10 of a positive value rounded towards zero.
* Returns 0 if given 0.
*/
function log10(uint256 value) internal pure returns (uint256) {
uint256 result = 0;
unchecked {
if (value >= 10 ** 64) {
value /= 10 ** 64;
result += 64;
}
if (value >= 10 ** 32) {
value /= 10 ** 32;
result += 32;
}
if (value >= 10 ** 16) {
value /= 10 ** 16;
result += 16;
}
if (value >= 10 ** 8) {
value /= 10 ** 8;
result += 8;
}
if (value >= 10 ** 4) {
value /= 10 ** 4;
result += 4;
}
if (value >= 10 ** 2) {
value /= 10 ** 2;
result += 2;
}
if (value >= 10 ** 1) {
result += 1;
}
}
return result;
}
/**
* @dev Return the log in base 10, following the selected rounding direction, of a positive value.
* Returns 0 if given 0.
*/
function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
unchecked {
uint256 result = log10(value);
return result + (unsignedRoundsUp(rounding) && 10 ** result < value ? 1 : 0);
}
}
/**
* @dev Return the log in base 256 of a positive value rounded towards zero.
* Returns 0 if given 0.
*
* Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
*/
function log256(uint256 value) internal pure returns (uint256) {
uint256 result = 0;
unchecked {
if (value >> 128 > 0) {
value >>= 128;
result += 16;
}
if (value >> 64 > 0) {
value >>= 64;
result += 8;
}
if (value >> 32 > 0) {
value >>= 32;
result += 4;
}
if (value >> 16 > 0) {
value >>= 16;
result += 2;
}
if (value >> 8 > 0) {
result += 1;
}
}
return result;
}
/**
* @dev Return the log in base 256, following the selected rounding direction, of a positive value.
* Returns 0 if given 0.
*/
function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
unchecked {
uint256 result = log256(value);
return result + (unsignedRoundsUp(rounding) && 1 << (result << 3) < value ? 1 : 0);
}
}
/**
* @dev Returns whether a provided rounding mode is considered rounding up for unsigned integers.
*/
function unsignedRoundsUp(Rounding rounding) internal pure returns (bool) {
return uint8(rounding) % 2 == 1;
}
}
// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;
/// @title Burn
/// @notice Utilities for burning stuff.
library Burn {
/// @notice Burns a given amount of ETH.
/// @param _amount Amount of ETH to burn.
function eth(uint256 _amount) internal {
new Burner{ value: _amount }();
}
/// @notice Burns a given amount of gas.
/// @param _amount Amount of gas to burn.
function gas(uint256 _amount) internal view {
uint256 i = 0;
uint256 initialGas = gasleft();
while (initialGas - gasleft() < _amount) {
++i;
}
}
}
/// @title Burner
/// @notice Burner self-destructs on creation and sends all ETH to itself, removing all ETH given to
/// the contract from the circulating supply. Self-destructing is the only way to remove ETH
/// from the circulating supply.
contract Burner {
constructor() payable {
selfdestruct(payable(address(this)));
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import { SignedMath } from "@openzeppelin/contracts/utils/math/SignedMath.sol";
import { FixedPointMathLib } from "@rari-capital/solmate/src/utils/FixedPointMathLib.sol";
/// @title Arithmetic
/// @notice Even more math than before.
library Arithmetic {
/// @notice Clamps a value between a minimum and maximum.
/// @param _value The value to clamp.
/// @param _min The minimum value.
/// @param _max The maximum value.
/// @return The clamped value.
function clamp(int256 _value, int256 _min, int256 _max) internal pure returns (int256) {
return SignedMath.min(SignedMath.max(_value, _min), _max);
}
/// @notice (c)oefficient (d)enominator (exp)onentiation function.
/// Returns the result of: c * (1 - 1/d)^exp.
/// @param _coefficient Coefficient of the function.
/// @param _denominator Fractional denominator.
/// @param _exponent Power function exponent.
/// @return Result of c * (1 - 1/d)^exp.
function cdexp(int256 _coefficient, int256 _denominator, int256 _exponent) internal pure returns (int256) {
return (_coefficient * (FixedPointMathLib.powWad(1e18 - (1e18 / _denominator), _exponent * 1e18))) / 1e18;
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/math/SignedMath.sol)
pragma solidity ^0.8.20;
/**
* @dev Standard signed math utilities missing in the Solidity language.
*/
library SignedMath {
/**
* @dev Returns the largest of two signed numbers.
*/
function max(int256 a, int256 b) internal pure returns (int256) {
return a > b ? a : b;
}
/**
* @dev Returns the smallest of two signed numbers.
*/
function min(int256 a, int256 b) internal pure returns (int256) {
return a < b ? a : b;
}
/**
* @dev Returns the average of two signed numbers without overflow.
* The result is rounded towards zero.
*/
function average(int256 a, int256 b) internal pure returns (int256) {
// Formula from the book "Hacker's Delight"
int256 x = (a & b) + ((a ^ b) >> 1);
return x + (int256(uint256(x) >> 255) & (a ^ b));
}
/**
* @dev Returns the absolute unsigned value of a signed value.
*/
function abs(int256 n) internal pure returns (uint256) {
unchecked {
// must be unchecked in order to support `n = type(int256).min`
return uint256(n >= 0 ? n : -n);
}
}
}
// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;
/// @notice Arithmetic library with operations for fixed-point numbers.
/// @author Solmate (https://github.com/Rari-Capital/solmate/blob/main/src/utils/FixedPointMathLib.sol)
library FixedPointMathLib {
/*//////////////////////////////////////////////////////////////
SIMPLIFIED FIXED POINT OPERATIONS
//////////////////////////////////////////////////////////////*/
uint256 internal constant WAD = 1e18; // The scalar of ETH and most ERC20s.
function mulWadDown(uint256 x, uint256 y) internal pure returns (uint256) {
return mulDivDown(x, y, WAD); // Equivalent to (x * y) / WAD rounded down.
}
function mulWadUp(uint256 x, uint256 y) internal pure returns (uint256) {
return mulDivUp(x, y, WAD); // Equivalent to (x * y) / WAD rounded up.
}
function divWadDown(uint256 x, uint256 y) internal pure returns (uint256) {
return mulDivDown(x, WAD, y); // Equivalent to (x * WAD) / y rounded down.
}
function divWadUp(uint256 x, uint256 y) internal pure returns (uint256) {
return mulDivUp(x, WAD, y); // Equivalent to (x * WAD) / y rounded up.
}
function powWad(int256 x, int256 y) internal pure returns (int256) {
// Equivalent to x to the power of y because x ** y = (e ** ln(x)) ** y = e ** (ln(x) * y)
return expWad((lnWad(x) * y) / int256(WAD)); // Using ln(x) means x must be greater than 0.
}
function expWad(int256 x) internal pure returns (int256 r) {
unchecked {
// When the result is < 0.5 we return zero. This happens when
// x <= floor(log(0.5e18) * 1e18) ~ -42e18
if (x <= -42139678854452767551) return 0;
// When the result is > (2**255 - 1) / 1e18 we can not represent it as an
// int. This happens when x >= floor(log((2**255 - 1) / 1e18) * 1e18) ~ 135.
if (x >= 135305999368893231589) revert("EXP_OVERFLOW");
// x is now in the range (-42, 136) * 1e18. Convert to (-42, 136) * 2**96
// for more intermediate precision and a binary basis. This base conversion
// is a multiplication by 1e18 / 2**96 = 5**18 / 2**78.
x = (x << 78) / 5**18;
// Reduce range of x to (-½ ln 2, ½ ln 2) * 2**96 by factoring out powers
// of two such that exp(x) = exp(x') * 2**k, where k is an integer.
// Solving this gives k = round(x / log(2)) and x' = x - k * log(2).
int256 k = ((x << 96) / 54916777467707473351141471128 + 2**95) >> 96;
x = x - k * 54916777467707473351141471128;
// k is in the range [-61, 195].
// Evaluate using a (6, 7)-term rational approximation.
// p is made monic, we'll multiply by a scale factor later.
int256 y = x + 1346386616545796478920950773328;
y = ((y * x) >> 96) + 57155421227552351082224309758442;
int256 p = y + x - 94201549194550492254356042504812;
p = ((p * y) >> 96) + 28719021644029726153956944680412240;
p = p * x + (4385272521454847904659076985693276 << 96);
// We leave p in 2**192 basis so we don't need to scale it back up for the division.
int256 q = x - 2855989394907223263936484059900;
q = ((q * x) >> 96) + 50020603652535783019961831881945;
q = ((q * x) >> 96) - 533845033583426703283633433725380;
q = ((q * x) >> 96) + 3604857256930695427073651918091429;
q = ((q * x) >> 96) - 14423608567350463180887372962807573;
q = ((q * x) >> 96) + 26449188498355588339934803723976023;
assembly {
// Div in assembly because solidity adds a zero check despite the unchecked.
// The q polynomial won't have zeros in the domain as all its roots are complex.
// No scaling is necessary because p is already 2**96 too large.
r := sdiv(p, q)
}
// r should be in the range (0.09, 0.25) * 2**96.
// We now need to multiply r by:
// * the scale factor s = ~6.031367120.
// * the 2**k factor from the range reduction.
// * the 1e18 / 2**96 factor for base conversion.
// We do this all at once, with an intermediate result in 2**213
// basis, so the final right shift is always by a positive amount.
r = int256((uint256(r) * 3822833074963236453042738258902158003155416615667) >> uint256(195 - k));
}
}
function lnWad(int256 x) internal pure returns (int256 r) {
unchecked {
require(x > 0, "UNDEFINED");
// We want to convert x from 10**18 fixed point to 2**96 fixed point.
// We do this by multiplying by 2**96 / 10**18. But since
// ln(x * C) = ln(x) + ln(C), we can simply do nothing here
// and add ln(2**96 / 10**18) at the end.
// Reduce range of x to (1, 2) * 2**96
// ln(2^k * x) = k * ln(2) + ln(x)
int256 k = int256(log2(uint256(x))) - 96;
x <<= uint256(159 - k);
x = int256(uint256(x) >> 159);
// Evaluate using a (8, 8)-term rational approximation.
// p is made monic, we will multiply by a scale factor later.
int256 p = x + 3273285459638523848632254066296;
p = ((p * x) >> 96) + 24828157081833163892658089445524;
p = ((p * x) >> 96) + 43456485725739037958740375743393;
p = ((p * x) >> 96) - 11111509109440967052023855526967;
p = ((p * x) >> 96) - 45023709667254063763336534515857;
p = ((p * x) >> 96) - 14706773417378608786704636184526;
p = p * x - (795164235651350426258249787498 << 96);
// We leave p in 2**192 basis so we don't need to scale it back up for the division.
// q is monic by convention.
int256 q = x + 5573035233440673466300451813936;
q = ((q * x) >> 96) + 71694874799317883764090561454958;
q = ((q * x) >> 96) + 283447036172924575727196451306956;
q = ((q * x) >> 96) + 401686690394027663651624208769553;
q = ((q * x) >> 96) + 204048457590392012362485061816622;
q = ((q * x) >> 96) + 31853899698501571402653359427138;
q = ((q * x) >> 96) + 909429971244387300277376558375;
assembly {
// Div in assembly because solidity adds a zero check despite the unchecked.
// The q polynomial is known not to have zeros in the domain.
// No scaling required because p is already 2**96 too large.
r := sdiv(p, q)
}
// r is in the range (0, 0.125) * 2**96
// Finalization, we need to:
// * multiply by the scale factor s = 5.549…
// * add ln(2**96 / 10**18)
// * add k * ln(2)
// * multiply by 10**18 / 2**96 = 5**18 >> 78
// mul s * 5e18 * 2**96, base is now 5**18 * 2**192
r *= 1677202110996718588342820967067443963516166;
// add ln(2) * k * 5e18 * 2**192
r += 16597577552685614221487285958193947469193820559219878177908093499208371 * k;
// add ln(2**96 / 10**18) * 5e18 * 2**192
r += 600920179829731861736702779321621459595472258049074101567377883020018308;
// base conversion: mul 2**18 / 2**192
r >>= 174;
}
}
/*//////////////////////////////////////////////////////////////
LOW LEVEL FIXED POINT OPERATIONS
//////////////////////////////////////////////////////////////*/
function mulDivDown(
uint256 x,
uint256 y,
uint256 denominator
) internal pure returns (uint256 z) {
assembly {
// Store x * y in z for now.
z := mul(x, y)
// Equivalent to require(denominator != 0 && (x == 0 || (x * y) / x == y))
if iszero(and(iszero(iszero(denominator)), or(iszero(x), eq(div(z, x), y)))) {
revert(0, 0)
}
// Divide z by the denominator.
z := div(z, denominator)
}
}
function mulDivUp(
uint256 x,
uint256 y,
uint256 denominator
) internal pure returns (uint256 z) {
assembly {
// Store x * y in z for now.
z := mul(x, y)
// Equivalent to require(denominator != 0 && (x == 0 || (x * y) / x == y))
if iszero(and(iszero(iszero(denominator)), or(iszero(x), eq(div(z, x), y)))) {
revert(0, 0)
}
// First, divide z - 1 by the denominator and add 1.
// We allow z - 1 to underflow if z is 0, because we multiply the
// end result by 0 if z is zero, ensuring we return 0 if z is zero.
z := mul(iszero(iszero(z)), add(div(sub(z, 1), denominator), 1))
}
}
function rpow(
uint256 x,
uint256 n,
uint256 scalar
) internal pure returns (uint256 z) {
assembly {
switch x
case 0 {
switch n
case 0 {
// 0 ** 0 = 1
z := scalar
}
default {
// 0 ** n = 0
z := 0
}
}
default {
switch mod(n, 2)
case 0 {
// If n is even, store scalar in z for now.
z := scalar
}
default {
// If n is odd, store x in z for now.
z := x
}
// Shifting right by 1 is like dividing by 2.
let half := shr(1, scalar)
for {
// Shift n right by 1 before looping to halve it.
n := shr(1, n)
} n {
// Shift n right by 1 each iteration to halve it.
n := shr(1, n)
} {
// Revert immediately if x ** 2 would overflow.
// Equivalent to iszero(eq(div(xx, x), x)) here.
if shr(128, x) {
revert(0, 0)
}
// Store x squared.
let xx := mul(x, x)
// Round to the nearest number.
let xxRound := add(xx, half)
// Revert if xx + half overflowed.
if lt(xxRound, xx) {
revert(0, 0)
}
// Set x to scaled xxRound.
x := div(xxRound, scalar)
// If n is even:
if mod(n, 2) {
// Compute z * x.
let zx := mul(z, x)
// If z * x overflowed:
if iszero(eq(div(zx, x), z)) {
// Revert if x is non-zero.
if iszero(iszero(x)) {
revert(0, 0)
}
}
// Round to the nearest number.
let zxRound := add(zx, half)
// Revert if zx + half overflowed.
if lt(zxRound, zx) {
revert(0, 0)
}
// Return properly scaled zxRound.
z := div(zxRound, scalar)
}
}
}
}
}
/*//////////////////////////////////////////////////////////////
GENERAL NUMBER UTILITIES
//////////////////////////////////////////////////////////////*/
function sqrt(uint256 x) internal pure returns (uint256 z) {
assembly {
let y := x // We start y at x, which will help us make our initial estimate.
z := 181 // The "correct" value is 1, but this saves a multiplication later.
// This segment is to get a reasonable initial estimate for the Babylonian method. With a bad
// start, the correct # of bits increases ~linearly each iteration instead of ~quadratically.
// We check y >= 2^(k + 8) but shift right by k bits
// each branch to ensure that if x >= 256, then y >= 256.
if iszero(lt(y, 0x10000000000000000000000000000000000)) {
y := shr(128, y)
z := shl(64, z)
}
if iszero(lt(y, 0x1000000000000000000)) {
y := shr(64, y)
z := shl(32, z)
}
if iszero(lt(y, 0x10000000000)) {
y := shr(32, y)
z := shl(16, z)
}
if iszero(lt(y, 0x1000000)) {
y := shr(16, y)
z := shl(8, z)
}
// Goal was to get z*z*y within a small factor of x. More iterations could
// get y in a tighter range. Currently, we will have y in [256, 256*2^16).
// We ensured y >= 256 so that the relative difference between y and y+1 is small.
// That's not possible if x < 256 but we can just verify those cases exhaustively.
// Now, z*z*y <= x < z*z*(y+1), and y <= 2^(16+8), and either y >= 256, or x < 256.
// Correctness can be checked exhaustively for x < 256, so we assume y >= 256.
// Then z*sqrt(y) is within sqrt(257)/sqrt(256) of sqrt(x), or about 20bps.
// For s in the range [1/256, 256], the estimate f(s) = (181/1024) * (s+1) is in the range
// (1/2.84 * sqrt(s), 2.84 * sqrt(s)), with largest error when s = 1 and when s = 256 or 1/256.
// Since y is in [256, 256*2^16), let a = y/65536, so that a is in [1/256, 256). Then we can estimate
// sqrt(y) using sqrt(65536) * 181/1024 * (a + 1) = 181/4 * (y + 65536)/65536 = 181 * (y + 65536)/2^18.
// There is no overflow risk here since y < 2^136 after the first branch above.
z := shr(18, mul(z, add(y, 65536))) // A mul() is saved from starting z at 181.
// Given the worst case multiplicative error of 2.84 above, 7 iterations should be enough.
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
z := shr(1, add(z, div(x, z)))
// If x+1 is a perfect square, the Babylonian method cycles between
// floor(sqrt(x)) and ceil(sqrt(x)). This statement ensures we return floor.
// See: https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division
// Since the ceil is rare, we save gas on the assignment and repeat division in the rare case.
// If you don't care whether the floor or ceil square root is returned, you can remove this statement.
z := sub(z, lt(div(x, z), z))
}
}
function log2(uint256 x) internal pure returns (uint256 r) {
require(x > 0, "UNDEFINED");
assembly {
r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
r := or(r, shl(4, lt(0xffff, shr(r, x))))
r := or(r, shl(3, lt(0xff, shr(r, x))))
r := or(r, shl(2, lt(0xf, shr(r, x))))
r := or(r, shl(1, lt(0x3, shr(r, x))))
r := or(r, lt(0x1, shr(r, x)))
}
}
}