I was building a Uniswap clone and got this error. I`m using foundery and have downloaded the OpenZeppelin/openzeppelin-contracts
Full error:
Compiler run failed
error[2333]: DeclarationError: Identifier already declared.
--> src/UniswapV3NFTManager.sol:10:1:
|
10 | import "./lib/PoolAddress.sol";
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Note: The previous declaration is here:
--> lib/openzeppelin-contracts/contracts/utils/math/Math.sol:9:1:
|
9 | library Math {
| ^ (Relevant source part starts here and spans across multiple lines).
UniswapV3NFTManager.sol
// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.14;
import "solmate/tokens/ERC721.sol";
import "./interfaces/IERC20.sol";
import "./interfaces/IUniswapV3Pool.sol";
import "./lib/LiquidityMath.sol";
import "./lib/NFTRenderer.sol";
import "./lib/PoolAddress.sol";
import "./lib/TickMath.sol";
contract UniswapV3NFTManager is ERC721 {
error NotAuthorized();
error NotEnoughLiquidity();
error PositionNotCleared();
error SlippageCheckFailed(uint256 amount0, uint256 amount1);
error WrongToken();
event AddLiquidity(
uint256 indexed tokenId,
uint128 liquidity,
uint256 amount0,
uint256 amount1
);
event RemoveLiquidity(
uint256 indexed tokenId,
uint128 liquidity,
uint256 amount0,
uint256 amount1
);
struct TokenPosition {
address pool;
int24 lowerTick;
int24 upperTick;
}
uint256 public totalSupply;
uint256 private nextTokenId;
address public immutable factory;
mapping(uint256 => TokenPosition) public positions;
modifier isApprovedOrOwner(uint256 tokenId) {
address owner = ownerOf(tokenId);
if (
msg.sender != owner &&
!isApprovedForAll[owner][msg.sender] &&
getApproved[tokenId] != msg.sender
) revert NotAuthorized();
_;
}
constructor(address factoryAddress)
ERC721("UniswapV3 NFT Positions", "UNIV3")
{
factory = factoryAddress;
}
function tokenURI(uint256 tokenId)
public
view
override
returns (string memory)
{
TokenPosition memory tokenPosition = positions[tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
return
NFTRenderer.render(
NFTRenderer.RenderParams({
pool: tokenPosition.pool,
owner: address(this),
lowerTick: tokenPosition.lowerTick,
upperTick: tokenPosition.upperTick,
fee: pool.fee()
})
);
}
struct MintParams {
address recipient;
address tokenA;
address tokenB;
uint24 fee;
int24 lowerTick;
int24 upperTick;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function mint(MintParams calldata params) public returns (uint256 tokenId) {
IUniswapV3Pool pool = getPool(params.tokenA, params.tokenB, params.fee);
(uint128 liquidity, uint256 amount0, uint256 amount1) = _addLiquidity(
AddLiquidityInternalParams({
pool: pool,
lowerTick: params.lowerTick,
upperTick: params.upperTick,
amount0Desired: params.amount0Desired,
amount1Desired: params.amount1Desired,
amount0Min: params.amount0Min,
amount1Min: params.amount1Min
})
);
tokenId = nextTokenId++;
_mint(params.recipient, tokenId);
totalSupply++;
TokenPosition memory tokenPosition = TokenPosition({
pool: address(pool),
lowerTick: params.lowerTick,
upperTick: params.upperTick
});
positions[tokenId] = tokenPosition;
emit AddLiquidity(tokenId, liquidity, amount0, amount1);
}
struct AddLiquidityParams {
uint256 tokenId;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function addLiquidity(AddLiquidityParams calldata params)
public
returns (
uint128 liquidity,
uint256 amount0,
uint256 amount1
)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
(liquidity, amount0, amount1) = _addLiquidity(
AddLiquidityInternalParams({
pool: IUniswapV3Pool(tokenPosition.pool),
lowerTick: tokenPosition.lowerTick,
upperTick: tokenPosition.upperTick,
amount0Desired: params.amount0Desired,
amount1Desired: params.amount1Desired,
amount0Min: params.amount0Min,
amount1Min: params.amount1Min
})
);
emit AddLiquidity(params.tokenId, liquidity, amount0, amount1);
}
struct RemoveLiquidityParams {
uint256 tokenId;
uint128 liquidity;
}
// TODO: add slippage check
function removeLiquidity(RemoveLiquidityParams memory params)
public
isApprovedOrOwner(params.tokenId)
returns (uint256 amount0, uint256 amount1)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(uint128 availableLiquidity, , , , ) = pool.positions(
poolPositionKey(tokenPosition)
);
if (params.liquidity > availableLiquidity) revert NotEnoughLiquidity();
(amount0, amount1) = pool.burn(
tokenPosition.lowerTick,
tokenPosition.upperTick,
params.liquidity
);
emit RemoveLiquidity(
params.tokenId,
params.liquidity,
amount0,
amount1
);
}
struct CollectParams {
uint256 tokenId;
uint128 amount0;
uint128 amount1;
}
function collect(CollectParams memory params)
public
isApprovedOrOwner(params.tokenId)
returns (uint128 amount0, uint128 amount1)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(amount0, amount1) = pool.collect(
msg.sender,
tokenPosition.lowerTick,
tokenPosition.upperTick,
params.amount0,
params.amount1
);
}
function burn(uint256 tokenId) public isApprovedOrOwner(tokenId) {
TokenPosition memory tokenPosition = positions[tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(uint128 liquidity, , , uint128 tokensOwed0, uint128 tokensOwed1) = pool
.positions(poolPositionKey(tokenPosition));
if (liquidity > 0 || tokensOwed0 > 0 || tokensOwed1 > 0)
revert PositionNotCleared();
delete positions[tokenId];
_burn(tokenId);
totalSupply--;
}
////////////////////////////////////////////////////////////////////////////
//
// CALLBACKS
//
////////////////////////////////////////////////////////////////////////////
function uniswapV3MintCallback(
uint256 amount0,
uint256 amount1,
bytes calldata data
) public {
IUniswapV3Pool.CallbackData memory extra = abi.decode(
data,
(IUniswapV3Pool.CallbackData)
);
IERC20(extra.token0).transferFrom(extra.payer, msg.sender, amount0);
IERC20(extra.token1).transferFrom(extra.payer, msg.sender, amount1);
}
////////////////////////////////////////////////////////////////////////////
//
// INTERNAL
//
////////////////////////////////////////////////////////////////////////////
struct AddLiquidityInternalParams {
IUniswapV3Pool pool;
int24 lowerTick;
int24 upperTick;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function _addLiquidity(AddLiquidityInternalParams memory params)
internal
returns (
uint128 liquidity,
uint256 amount0,
uint256 amount1
)
{
(uint160 sqrtPriceX96, , , , ) = params.pool.slot0();
liquidity = LiquidityMath.getLiquidityForAmounts(
sqrtPriceX96,
TickMath.getSqrtRatioAtTick(params.lowerTick),
TickMath.getSqrtRatioAtTick(params.upperTick),
params.amount0Desired,
params.amount1Desired
);
(amount0, amount1) = params.pool.mint(
address(this),
params.lowerTick,
params.upperTick,
liquidity,
abi.encode(
IUniswapV3Pool.CallbackData({
token0: params.pool.token0(),
token1: params.pool.token1(),
payer: msg.sender
})
)
);
if (amount0 < params.amount0Min || amount1 < params.amount1Min)
revert SlippageCheckFailed(amount0, amount1);
}
function getPool(
address token0,
address token1,
uint24 fee
) internal view returns (IUniswapV3Pool pool) {
(token0, token1) = token0 < token1
? (token0, token1)
: (token1, token0);
pool = IUniswapV3Pool(
PoolAddress.computeAddress(factory, token0, token1, fee)
);
}
/*
Returns position ID within a pool
*/
function poolPositionKey(TokenPosition memory position)
internal
view
returns (bytes32 key)
{
key = keccak256(
abi.encodePacked(
address(this),
position.lowerTick,
position.upperTick
)
);
}
/*
Returns position ID within the NFT manager
*/
function positionKey(TokenPosition memory position)
internal
pure
returns (bytes32 key)
{
key = keccak256(
abi.encodePacked(
address(position.pool),
position.lowerTick,
position.upperTick
)
);
// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.14;
import "solmate/tokens/ERC721.sol";
import "./interfaces/IERC20.sol";
import "./interfaces/IUniswapV3Pool.sol";
import "./lib/LiquidityMath.sol";
import "./lib/NFTRenderer.sol";
import "./lib/PoolAddress.sol";
import "./lib/TickMath.sol";
contract UniswapV3NFTManager is ERC721 {
error NotAuthorized();
error NotEnoughLiquidity();
error PositionNotCleared();
error SlippageCheckFailed(uint256 amount0, uint256 amount1);
error WrongToken();
event AddLiquidity(
uint256 indexed tokenId,
uint128 liquidity,
uint256 amount0,
uint256 amount1
);
event RemoveLiquidity(
uint256 indexed tokenId,
uint128 liquidity,
uint256 amount0,
uint256 amount1
);
struct TokenPosition {
address pool;
int24 lowerTick;
int24 upperTick;
}
uint256 public totalSupply;
uint256 private nextTokenId;
address public immutable factory;
mapping(uint256 => TokenPosition) public positions;
modifier isApprovedOrOwner(uint256 tokenId) {
address owner = ownerOf(tokenId);
if (
msg.sender != owner &&
!isApprovedForAll[owner][msg.sender] &&
getApproved[tokenId] != msg.sender
) revert NotAuthorized();
_;
}
constructor(address factoryAddress)
ERC721("UniswapV3 NFT Positions", "UNIV3")
{
factory = factoryAddress;
}
function tokenURI(uint256 tokenId)
public
view
override
returns (string memory)
{
TokenPosition memory tokenPosition = positions[tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
return
NFTRenderer.render(
NFTRenderer.RenderParams({
pool: tokenPosition.pool,
owner: address(this),
lowerTick: tokenPosition.lowerTick,
upperTick: tokenPosition.upperTick,
fee: pool.fee()
})
);
}
struct MintParams {
address recipient;
address tokenA;
address tokenB;
uint24 fee;
int24 lowerTick;
int24 upperTick;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function mint(MintParams calldata params) public returns (uint256 tokenId) {
IUniswapV3Pool pool = getPool(params.tokenA, params.tokenB, params.fee);
(uint128 liquidity, uint256 amount0, uint256 amount1) = _addLiquidity(
AddLiquidityInternalParams({
pool: pool,
lowerTick: params.lowerTick,
upperTick: params.upperTick,
amount0Desired: params.amount0Desired,
amount1Desired: params.amount1Desired,
amount0Min: params.amount0Min,
amount1Min: params.amount1Min
})
);
tokenId = nextTokenId++;
_mint(params.recipient, tokenId);
totalSupply++;
TokenPosition memory tokenPosition = TokenPosition({
pool: address(pool),
lowerTick: params.lowerTick,
upperTick: params.upperTick
});
positions[tokenId] = tokenPosition;
emit AddLiquidity(tokenId, liquidity, amount0, amount1);
}
struct AddLiquidityParams {
uint256 tokenId;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function addLiquidity(AddLiquidityParams calldata params)
public
returns (
uint128 liquidity,
uint256 amount0,
uint256 amount1
)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
(liquidity, amount0, amount1) = _addLiquidity(
AddLiquidityInternalParams({
pool: IUniswapV3Pool(tokenPosition.pool),
lowerTick: tokenPosition.lowerTick,
upperTick: tokenPosition.upperTick,
amount0Desired: params.amount0Desired,
amount1Desired: params.amount1Desired,
amount0Min: params.amount0Min,
amount1Min: params.amount1Min
})
);
emit AddLiquidity(params.tokenId, liquidity, amount0, amount1);
}
struct RemoveLiquidityParams {
uint256 tokenId;
uint128 liquidity;
}
// TODO: add slippage check
function removeLiquidity(RemoveLiquidityParams memory params)
public
isApprovedOrOwner(params.tokenId)
returns (uint256 amount0, uint256 amount1)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(uint128 availableLiquidity, , , , ) = pool.positions(
poolPositionKey(tokenPosition)
);
if (params.liquidity > availableLiquidity) revert NotEnoughLiquidity();
(amount0, amount1) = pool.burn(
tokenPosition.lowerTick,
tokenPosition.upperTick,
params.liquidity
);
emit RemoveLiquidity(
params.tokenId,
params.liquidity,
amount0,
amount1
);
}
struct CollectParams {
uint256 tokenId;
uint128 amount0;
uint128 amount1;
}
function collect(CollectParams memory params)
public
isApprovedOrOwner(params.tokenId)
returns (uint128 amount0, uint128 amount1)
{
TokenPosition memory tokenPosition = positions[params.tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(amount0, amount1) = pool.collect(
msg.sender,
tokenPosition.lowerTick,
tokenPosition.upperTick,
params.amount0,
params.amount1
);
}
function burn(uint256 tokenId) public isApprovedOrOwner(tokenId) {
TokenPosition memory tokenPosition = positions[tokenId];
if (tokenPosition.pool == address(0x00)) revert WrongToken();
IUniswapV3Pool pool = IUniswapV3Pool(tokenPosition.pool);
(uint128 liquidity, , , uint128 tokensOwed0, uint128 tokensOwed1) = pool
.positions(poolPositionKey(tokenPosition));
if (liquidity > 0 || tokensOwed0 > 0 || tokensOwed1 > 0)
revert PositionNotCleared();
delete positions[tokenId];
_burn(tokenId);
totalSupply--;
}
////////////////////////////////////////////////////////////////////////////
//
// CALLBACKS
//
////////////////////////////////////////////////////////////////////////////
function uniswapV3MintCallback(
uint256 amount0,
uint256 amount1,
bytes calldata data
) public {
IUniswapV3Pool.CallbackData memory extra = abi.decode(
data,
(IUniswapV3Pool.CallbackData)
);
IERC20(extra.token0).transferFrom(extra.payer, msg.sender, amount0);
IERC20(extra.token1).transferFrom(extra.payer, msg.sender, amount1);
}
////////////////////////////////////////////////////////////////////////////
//
// INTERNAL
//
////////////////////////////////////////////////////////////////////////////
struct AddLiquidityInternalParams {
IUniswapV3Pool pool;
int24 lowerTick;
int24 upperTick;
uint256 amount0Desired;
uint256 amount1Desired;
uint256 amount0Min;
uint256 amount1Min;
}
function _addLiquidity(AddLiquidityInternalParams memory params)
internal
returns (
uint128 liquidity,
uint256 amount0,
uint256 amount1
)
{
(uint160 sqrtPriceX96, , , , ) = params.pool.slot0();
liquidity = LiquidityMath.getLiquidityForAmounts(
sqrtPriceX96,
TickMath.getSqrtRatioAtTick(params.lowerTick),
TickMath.getSqrtRatioAtTick(params.upperTick),
params.amount0Desired,
params.amount1Desired
);
(amount0, amount1) = params.pool.mint(
address(this),
params.lowerTick,
params.upperTick,
liquidity,
abi.encode(
IUniswapV3Pool.CallbackData({
token0: params.pool.token0(),
token1: params.pool.token1(),
payer: msg.sender
})
)
);
if (amount0 < params.amount0Min || amount1 < params.amount1Min)
revert SlippageCheckFailed(amount0, amount1);
}
function getPool(
address token0,
address token1,
uint24 fee
) internal view returns (IUniswapV3Pool pool) {
(token0, token1) = token0 < token1
? (token0, token1)
: (token1, token0);
pool = IUniswapV3Pool(
PoolAddress.computeAddress(factory, token0, token1, fee)
);
}
/*
Returns position ID within a pool
*/
function poolPositionKey(TokenPosition memory position)
internal
view
returns (bytes32 key)
{
key = keccak256(
abi.encodePacked(
address(this),
position.lowerTick,
position.upperTick
)
);
}
/*
Returns position ID within the NFT manager
*/
function positionKey(TokenPosition memory position)
internal
pure
returns (bytes32 key)
{
key = keccak256(
abi.encodePacked(
address(position.pool),
position.lowerTick,
position.upperTick
)
);
}
}}
}
PoolAddress.sol
// SPDopenX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.14;
import "../UniswapV3Pool.sol";
library PoolAddress {
function computeAddress(
address factory,
address token0,
address token1,
uint24 fee
) internal pure returns (address pool) {
require(token0 < token1);
pool = address(
uint160(
uint256(
keccak256(
abi.encodePacked(
hex"ff",
factory,
keccak256(abi.encodePacked(token0, token1, fee)),
keccak256(type(UniswapV3Pool).creationCode)
)
)
)
)
);
}
}
Math.sol
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/math/Math.sol)
pragma solidity ^0.8.0;
/**
* @dev Standard math utilities missing in the Solidity language.
*/
library Math {
enum Rounding {
Down, // Toward negative infinity
Up, // Toward infinity
Zero // Toward zero
}
/**
* @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 up instead
* of rounding down.
*/
function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
// (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; // Least significant 256 bits of the product
uint256 prod1; // Most significant 256 bits of the product
assembly {
let mm := mulmod(x, y, not(0))
prod0 := mul(x, y)
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
// Handle non-overflow cases, 256 by 256 division.
if (prod1 == 0) {
return prod0 / denominator;
}
// Make sure the result is less than 2^256. Also prevents denominator == 0.
require(denominator > prod1);
///////////////////////////////////////////////
// 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.
// Does not overflow because the denominator cannot be zero at this stage in the function.
uint256 twos = denominator & (~denominator + 1);
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 (rounding == Rounding.Up && 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 down.
*
* 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 + (rounding == Rounding.Up && result * result < a ? 1 : 0);
}
}
/**
* @dev Return the log in base 2, rounded down, of a positive value.
* 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 + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
}
}
/**
* @dev Return the log in base 10, rounded down, of a positive value.
* 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 + (rounding == Rounding.Up && 10**result < value ? 1 : 0);
}
}
/**
* @dev Return the log in base 256, rounded down, of a positive value.
* 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 10, 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 + (rounding == Rounding.Up && 1 << (result * 8) < value ? 1 : 0);
}
}
}