// SPDX-License-Identifier: MIT// OpenZeppelin Contracts (last updated v4.9.0) (utils/math/Math.sol)pragmasolidity ^0.8.0;/**
* @dev Standard math utilities missing in the Solidity language.
*/libraryMath{
enumRounding {
Down, // Toward negative infinity
Up, // Toward infinity
Zero // Toward zero
}
/**
* @dev Returns the largest of two numbers.
*/functionmax(uint256 a, uint256 b) internalpurereturns (uint256) {
return a > b ? a : b;
}
/**
* @dev Returns the smallest of two numbers.
*/functionmin(uint256 a, uint256 b) internalpurereturns (uint256) {
return a < b ? a : b;
}
/**
* @dev Returns the average of two numbers. The result is rounded towards
* zero.
*/functionaverage(uint256 a, uint256 b) internalpurereturns (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.
*/functionceilDiv(uint256 a, uint256 b) internalpurereturns (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.
*/functionmulDiv(uint256 x, uint256 y, uint256 denominator) internalpurereturns (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 productuint256 prod1; // Most significant 256 bits of the productassembly {
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) {
// 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.require(denominator > prod1, "Math: mulDiv overflow");
///////////////////////////////////////////////// 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.
*/functionmulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internalpurereturns (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).
*/functionsqrt(uint256 a) internalpurereturns (uint256) {
if (a ==0) {
return0;
}
// 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.
*/functionsqrt(uint256 a, Rounding rounding) internalpurereturns (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.
*/functionlog2(uint256 value) internalpurereturns (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.
*/functionlog2(uint256 value, Rounding rounding) internalpurereturns (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.
*/functionlog10(uint256 value) internalpurereturns (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.
*/functionlog10(uint256 value, Rounding rounding) internalpurereturns (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.
*/functionlog256(uint256 value) internalpurereturns (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.
*/functionlog256(uint256 value, Rounding rounding) internalpurereturns (uint256) {
unchecked {
uint256 result = log256(value);
return result + (rounding == Rounding.Up &&1<< (result <<3) < value ? 1 : 0);
}
}
}
Contract Source Code
File 4 of 5: SignedMath.sol
// SPDX-License-Identifier: MIT// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/SignedMath.sol)pragmasolidity ^0.8.0;/**
* @dev Standard signed math utilities missing in the Solidity language.
*/librarySignedMath{
/**
* @dev Returns the largest of two signed numbers.
*/functionmax(int256 a, int256 b) internalpurereturns (int256) {
return a > b ? a : b;
}
/**
* @dev Returns the smallest of two signed numbers.
*/functionmin(int256 a, int256 b) internalpurereturns (int256) {
return a < b ? a : b;
}
/**
* @dev Returns the average of two signed numbers without overflow.
* The result is rounded towards zero.
*/functionaverage(int256 a, int256 b) internalpurereturns (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.
*/functionabs(int256 n) internalpurereturns (uint256) {
unchecked {
// must be unchecked in order to support `n = type(int256).min`returnuint256(n >=0 ? n : -n);
}
}
}
Contract Source Code
File 5 of 5: Strings.sol
// SPDX-License-Identifier: MIT// OpenZeppelin Contracts (last updated v4.9.0) (utils/Strings.sol)pragmasolidity ^0.8.0;import"./math/Math.sol";
import"./math/SignedMath.sol";
/**
* @dev String operations.
*/libraryStrings{
bytes16privateconstant _SYMBOLS ="0123456789abcdef";
uint8privateconstant _ADDRESS_LENGTH =20;
/**
* @dev Converts a `uint256` to its ASCII `string` decimal representation.
*/functiontoString(uint256 value) internalpurereturns (stringmemory) {
unchecked {
uint256 length = Math.log10(value) +1;
stringmemory buffer =newstring(length);
uint256 ptr;
/// @solidity memory-safe-assemblyassembly {
ptr :=add(buffer, add(32, length))
}
while (true) {
ptr--;
/// @solidity memory-safe-assemblyassembly {
mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
}
value /=10;
if (value ==0) break;
}
return buffer;
}
}
/**
* @dev Converts a `int256` to its ASCII `string` decimal representation.
*/functiontoString(int256 value) internalpurereturns (stringmemory) {
returnstring(abi.encodePacked(value <0 ? "-" : "", toString(SignedMath.abs(value))));
}
/**
* @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
*/functiontoHexString(uint256 value) internalpurereturns (stringmemory) {
unchecked {
return toHexString(value, Math.log256(value) +1);
}
}
/**
* @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
*/functiontoHexString(uint256 value, uint256 length) internalpurereturns (stringmemory) {
bytesmemory buffer =newbytes(2* length +2);
buffer[0] ="0";
buffer[1] ="x";
for (uint256 i =2* length +1; i >1; --i) {
buffer[i] = _SYMBOLS[value &0xf];
value >>=4;
}
require(value ==0, "Strings: hex length insufficient");
returnstring(buffer);
}
/**
* @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
*/functiontoHexString(address addr) internalpurereturns (stringmemory) {
return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
}
/**
* @dev Returns true if the two strings are equal.
*/functionequal(stringmemory a, stringmemory b) internalpurereturns (bool) {
returnkeccak256(bytes(a)) ==keccak256(bytes(b));
}
}
