Contract Name:
ERC1967Proxy
Contract Source Code:
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (proxy/ERC1967/ERC1967Proxy.sol)
pragma solidity ^0.8.20;
import {Proxy} from "../Proxy.sol";
import {ERC1967Utils} from "./ERC1967Utils.sol";
/**
* @dev This contract implements an upgradeable proxy. It is upgradeable because calls are delegated to an
* implementation address that can be changed. This address is stored in storage in the location specified by
* https://eips.ethereum.org/EIPS/eip-1967[EIP1967], so that it doesn't conflict with the storage layout of the
* implementation behind the proxy.
*/
contract ERC1967Proxy is Proxy {
/**
* @dev Initializes the upgradeable proxy with an initial implementation specified by `implementation`.
*
* If `_data` is nonempty, it's used as data in a delegate call to `implementation`. This will typically be an
* encoded function call, and allows initializing the storage of the proxy like a Solidity constructor.
*
* Requirements:
*
* - If `data` is empty, `msg.value` must be zero.
*/
constructor(address implementation, bytes memory _data) payable {
ERC1967Utils.upgradeToAndCall(implementation, _data);
}
/**
* @dev Returns the current implementation address.
*
* TIP: To get this value clients can read directly from the storage slot shown below (specified by EIP1967) using
* the https://eth.wiki/json-rpc/API#eth_getstorageat[`eth_getStorageAt`] RPC call.
* `0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc`
*/
function _implementation() internal view virtual override returns (address) {
return ERC1967Utils.getImplementation();
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (proxy/Proxy.sol)
pragma solidity ^0.8.20;
/**
* @dev This abstract contract provides a fallback function that delegates all calls to another contract using the EVM
* instruction `delegatecall`. We refer to the second contract as the _implementation_ behind the proxy, and it has to
* be specified by overriding the virtual {_implementation} function.
*
* Additionally, delegation to the implementation can be triggered manually through the {_fallback} function, or to a
* different contract through the {_delegate} function.
*
* The success and return data of the delegated call will be returned back to the caller of the proxy.
*/
abstract contract Proxy {
/**
* @dev Delegates the current call to `implementation`.
*
* This function does not return to its internal call site, it will return directly to the external caller.
*/
function _delegate(address implementation) internal virtual {
assembly {
// Copy msg.data. We take full control of memory in this inline assembly
// block because it will not return to Solidity code. We overwrite the
// Solidity scratch pad at memory position 0.
calldatacopy(0, 0, calldatasize())
// Call the implementation.
// out and outsize are 0 because we don't know the size yet.
let result := delegatecall(gas(), implementation, 0, calldatasize(), 0, 0)
// Copy the returned data.
returndatacopy(0, 0, returndatasize())
switch result
// delegatecall returns 0 on error.
case 0 {
revert(0, returndatasize())
}
default {
return(0, returndatasize())
}
}
}
/**
* @dev This is a virtual function that should be overridden so it returns the address to which the fallback
* function and {_fallback} should delegate.
*/
function _implementation() internal view virtual returns (address);
/**
* @dev Delegates the current call to the address returned by `_implementation()`.
*
* This function does not return to its internal call site, it will return directly to the external caller.
*/
function _fallback() internal virtual {
_delegate(_implementation());
}
/**
* @dev Fallback function that delegates calls to the address returned by `_implementation()`. Will run if no other
* function in the contract matches the call data.
*/
fallback() external payable virtual {
_fallback();
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (interfaces/draft-IERC1822.sol)
pragma solidity ^0.8.20;
/**
* @dev ERC1822: Universal Upgradeable Proxy Standard (UUPS) documents a method for upgradeability through a simplified
* proxy whose upgrades are fully controlled by the current implementation.
*/
interface IERC1822Proxiable {
/**
* @dev Returns the storage slot that the proxiable contract assumes is being used to store the implementation
* address.
*
* IMPORTANT: A proxy pointing at a proxiable contract should not be considered proxiable itself, because this risks
* bricking a proxy that upgrades to it, by delegating to itself until out of gas. Thus it is critical that this
* function revert if invoked through a proxy.
*/
function proxiableUUID() external view returns (bytes32);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (proxy/ERC1967/ERC1967Utils.sol)
pragma solidity ^0.8.20;
import {IBeacon} from "../beacon/IBeacon.sol";
import {Address} from "../../utils/Address.sol";
import {StorageSlot} from "../../utils/StorageSlot.sol";
/**
* @dev This abstract contract provides getters and event emitting update functions for
* https://eips.ethereum.org/EIPS/eip-1967[EIP1967] slots.
*/
library ERC1967Utils {
// We re-declare ERC-1967 events here because they can't be used directly from IERC1967.
// This will be fixed in Solidity 0.8.21. At that point we should remove these events.
/**
* @dev Emitted when the implementation is upgraded.
*/
event Upgraded(address indexed implementation);
/**
* @dev Emitted when the admin account has changed.
*/
event AdminChanged(address previousAdmin, address newAdmin);
/**
* @dev Emitted when the beacon is changed.
*/
event BeaconUpgraded(address indexed beacon);
/**
* @dev Storage slot with the address of the current implementation.
* This is the keccak-256 hash of "eip1967.proxy.implementation" subtracted by 1.
*/
// solhint-disable-next-line private-vars-leading-underscore
bytes32 internal constant IMPLEMENTATION_SLOT = 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
/**
* @dev The `implementation` of the proxy is invalid.
*/
error ERC1967InvalidImplementation(address implementation);
/**
* @dev The `admin` of the proxy is invalid.
*/
error ERC1967InvalidAdmin(address admin);
/**
* @dev The `beacon` of the proxy is invalid.
*/
error ERC1967InvalidBeacon(address beacon);
/**
* @dev An upgrade function sees `msg.value > 0` that may be lost.
*/
error ERC1967NonPayable();
/**
* @dev Returns the current implementation address.
*/
function getImplementation() internal view returns (address) {
return StorageSlot.getAddressSlot(IMPLEMENTATION_SLOT).value;
}
/**
* @dev Stores a new address in the EIP1967 implementation slot.
*/
function _setImplementation(address newImplementation) private {
if (newImplementation.code.length == 0) {
revert ERC1967InvalidImplementation(newImplementation);
}
StorageSlot.getAddressSlot(IMPLEMENTATION_SLOT).value = newImplementation;
}
/**
* @dev Performs implementation upgrade with additional setup call if data is nonempty.
* This function is payable only if the setup call is performed, otherwise `msg.value` is rejected
* to avoid stuck value in the contract.
*
* Emits an {IERC1967-Upgraded} event.
*/
function upgradeToAndCall(address newImplementation, bytes memory data) internal {
_setImplementation(newImplementation);
emit Upgraded(newImplementation);
if (data.length > 0) {
Address.functionDelegateCall(newImplementation, data);
} else {
_checkNonPayable();
}
}
/**
* @dev Storage slot with the admin of the contract.
* This is the keccak-256 hash of "eip1967.proxy.admin" subtracted by 1.
*/
// solhint-disable-next-line private-vars-leading-underscore
bytes32 internal constant ADMIN_SLOT = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;
/**
* @dev Returns the current admin.
*
* TIP: To get this value clients can read directly from the storage slot shown below (specified by EIP1967) using
* the https://eth.wiki/json-rpc/API#eth_getstorageat[`eth_getStorageAt`] RPC call.
* `0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103`
*/
function getAdmin() internal view returns (address) {
return StorageSlot.getAddressSlot(ADMIN_SLOT).value;
}
/**
* @dev Stores a new address in the EIP1967 admin slot.
*/
function _setAdmin(address newAdmin) private {
if (newAdmin == address(0)) {
revert ERC1967InvalidAdmin(address(0));
}
StorageSlot.getAddressSlot(ADMIN_SLOT).value = newAdmin;
}
/**
* @dev Changes the admin of the proxy.
*
* Emits an {IERC1967-AdminChanged} event.
*/
function changeAdmin(address newAdmin) internal {
emit AdminChanged(getAdmin(), newAdmin);
_setAdmin(newAdmin);
}
/**
* @dev The storage slot of the UpgradeableBeacon contract which defines the implementation for this proxy.
* This is the keccak-256 hash of "eip1967.proxy.beacon" subtracted by 1.
*/
// solhint-disable-next-line private-vars-leading-underscore
bytes32 internal constant BEACON_SLOT = 0xa3f0ad74e5423aebfd80d3ef4346578335a9a72aeaee59ff6cb3582b35133d50;
/**
* @dev Returns the current beacon.
*/
function getBeacon() internal view returns (address) {
return StorageSlot.getAddressSlot(BEACON_SLOT).value;
}
/**
* @dev Stores a new beacon in the EIP1967 beacon slot.
*/
function _setBeacon(address newBeacon) private {
if (newBeacon.code.length == 0) {
revert ERC1967InvalidBeacon(newBeacon);
}
StorageSlot.getAddressSlot(BEACON_SLOT).value = newBeacon;
address beaconImplementation = IBeacon(newBeacon).implementation();
if (beaconImplementation.code.length == 0) {
revert ERC1967InvalidImplementation(beaconImplementation);
}
}
/**
* @dev Change the beacon and trigger a setup call if data is nonempty.
* This function is payable only if the setup call is performed, otherwise `msg.value` is rejected
* to avoid stuck value in the contract.
*
* Emits an {IERC1967-BeaconUpgraded} event.
*
* CAUTION: Invoking this function has no effect on an instance of {BeaconProxy} since v5, since
* it uses an immutable beacon without looking at the value of the ERC-1967 beacon slot for
* efficiency.
*/
function upgradeBeaconToAndCall(address newBeacon, bytes memory data) internal {
_setBeacon(newBeacon);
emit BeaconUpgraded(newBeacon);
if (data.length > 0) {
Address.functionDelegateCall(IBeacon(newBeacon).implementation(), data);
} else {
_checkNonPayable();
}
}
/**
* @dev Reverts if `msg.value` is not zero. It can be used to avoid `msg.value` stuck in the contract
* if an upgrade doesn't perform an initialization call.
*/
function _checkNonPayable() private {
if (msg.value > 0) {
revert ERC1967NonPayable();
}
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (proxy/beacon/IBeacon.sol)
pragma solidity ^0.8.20;
/**
* @dev This is the interface that {BeaconProxy} expects of its beacon.
*/
interface IBeacon {
/**
* @dev Must return an address that can be used as a delegate call target.
*
* {UpgradeableBeacon} will check that this address is a contract.
*/
function implementation() external view returns (address);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/Address.sol)
pragma solidity ^0.8.20;
/**
* @dev Collection of functions related to the address type
*/
library Address {
/**
* @dev The ETH balance of the account is not enough to perform the operation.
*/
error AddressInsufficientBalance(address account);
/**
* @dev There's no code at `target` (it is not a contract).
*/
error AddressEmptyCode(address target);
/**
* @dev A call to an address target failed. The target may have reverted.
*/
error FailedInnerCall();
/**
* @dev Replacement for Solidity's `transfer`: sends `amount` wei to
* `recipient`, forwarding all available gas and reverting on errors.
*
* https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
* of certain opcodes, possibly making contracts go over the 2300 gas limit
* imposed by `transfer`, making them unable to receive funds via
* `transfer`. {sendValue} removes this limitation.
*
* https://consensys.net/diligence/blog/2019/09/stop-using-soliditys-transfer-now/[Learn more].
*
* IMPORTANT: because control is transferred to `recipient`, care must be
* taken to not create reentrancy vulnerabilities. Consider using
* {ReentrancyGuard} or the
* https://solidity.readthedocs.io/en/v0.8.20/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
*/
function sendValue(address payable recipient, uint256 amount) internal {
if (address(this).balance < amount) {
revert AddressInsufficientBalance(address(this));
}
(bool success, ) = recipient.call{value: amount}("");
if (!success) {
revert FailedInnerCall();
}
}
/**
* @dev Performs a Solidity function call using a low level `call`. A
* plain `call` is an unsafe replacement for a function call: use this
* function instead.
*
* If `target` reverts with a revert reason or custom error, it is bubbled
* up by this function (like regular Solidity function calls). However, if
* the call reverted with no returned reason, this function reverts with a
* {FailedInnerCall} error.
*
* Returns the raw returned data. To convert to the expected return value,
* use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
*
* Requirements:
*
* - `target` must be a contract.
* - calling `target` with `data` must not revert.
*/
function functionCall(address target, bytes memory data) internal returns (bytes memory) {
return functionCallWithValue(target, data, 0);
}
/**
* @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
* but also transferring `value` wei to `target`.
*
* Requirements:
*
* - the calling contract must have an ETH balance of at least `value`.
* - the called Solidity function must be `payable`.
*/
function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
if (address(this).balance < value) {
revert AddressInsufficientBalance(address(this));
}
(bool success, bytes memory returndata) = target.call{value: value}(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
* but performing a static call.
*/
function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
(bool success, bytes memory returndata) = target.staticcall(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
* but performing a delegate call.
*/
function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
(bool success, bytes memory returndata) = target.delegatecall(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Tool to verify that a low level call to smart-contract was successful, and reverts if the target
* was not a contract or bubbling up the revert reason (falling back to {FailedInnerCall}) in case of an
* unsuccessful call.
*/
function verifyCallResultFromTarget(
address target,
bool success,
bytes memory returndata
) internal view returns (bytes memory) {
if (!success) {
_revert(returndata);
} else {
// only check if target is a contract if the call was successful and the return data is empty
// otherwise we already know that it was a contract
if (returndata.length == 0 && target.code.length == 0) {
revert AddressEmptyCode(target);
}
return returndata;
}
}
/**
* @dev Tool to verify that a low level call was successful, and reverts if it wasn't, either by bubbling the
* revert reason or with a default {FailedInnerCall} error.
*/
function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory) {
if (!success) {
_revert(returndata);
} else {
return returndata;
}
}
/**
* @dev Reverts with returndata if present. Otherwise reverts with {FailedInnerCall}.
*/
function _revert(bytes memory returndata) private pure {
// Look for revert reason and bubble it up if present
if (returndata.length > 0) {
// The easiest way to bubble the revert reason is using memory via assembly
/// @solidity memory-safe-assembly
assembly {
let returndata_size := mload(returndata)
revert(add(32, returndata), returndata_size)
}
} else {
revert FailedInnerCall();
}
}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/StorageSlot.sol)
// This file was procedurally generated from scripts/generate/templates/StorageSlot.js.
pragma solidity ^0.8.20;
/**
* @dev Library for reading and writing primitive types to specific storage slots.
*
* Storage slots are often used to avoid storage conflict when dealing with upgradeable contracts.
* This library helps with reading and writing to such slots without the need for inline assembly.
*
* The functions in this library return Slot structs that contain a `value` member that can be used to read or write.
*
* Example usage to set ERC1967 implementation slot:
* ```solidity
* contract ERC1967 {
* bytes32 internal constant _IMPLEMENTATION_SLOT = 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
*
* function _getImplementation() internal view returns (address) {
* return StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value;
* }
*
* function _setImplementation(address newImplementation) internal {
* require(newImplementation.code.length > 0);
* StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value = newImplementation;
* }
* }
* ```
*/
library StorageSlot {
struct AddressSlot {
address value;
}
struct BooleanSlot {
bool value;
}
struct Bytes32Slot {
bytes32 value;
}
struct Uint256Slot {
uint256 value;
}
struct StringSlot {
string value;
}
struct BytesSlot {
bytes value;
}
/**
* @dev Returns an `AddressSlot` with member `value` located at `slot`.
*/
function getAddressSlot(bytes32 slot) internal pure returns (AddressSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `BooleanSlot` with member `value` located at `slot`.
*/
function getBooleanSlot(bytes32 slot) internal pure returns (BooleanSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `Bytes32Slot` with member `value` located at `slot`.
*/
function getBytes32Slot(bytes32 slot) internal pure returns (Bytes32Slot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `Uint256Slot` with member `value` located at `slot`.
*/
function getUint256Slot(bytes32 slot) internal pure returns (Uint256Slot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `StringSlot` with member `value` located at `slot`.
*/
function getStringSlot(bytes32 slot) internal pure returns (StringSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `StringSlot` representation of the string storage pointer `store`.
*/
function getStringSlot(string storage store) internal pure returns (StringSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := store.slot
}
}
/**
* @dev Returns an `BytesSlot` with member `value` located at `slot`.
*/
function getBytesSlot(bytes32 slot) internal pure returns (BytesSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := slot
}
}
/**
* @dev Returns an `BytesSlot` representation of the bytes storage pointer `store`.
*/
function getBytesSlot(bytes storage store) internal pure returns (BytesSlot storage r) {
/// @solidity memory-safe-assembly
assembly {
r.slot := store.slot
}
}
}
// 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;
}
}