// SPDX-License-Identifier: MIT // OpenZeppelin Contracts (last updated v5.3.0) (utils/math/Math.sol) // Source: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v5.3.0/contracts/utils/math/Math.sol // note: We only copy the subset of the library methods that we need. pragma solidity ^0.8.0; library Math { /// @dev division or modulo by zero uint256 internal constant DIVISION_BY_ZERO = 0x12; /// @dev arithmetic underflow or overflow uint256 internal constant UNDER_OVERFLOW = 0x11; /** * @dev Return the 512-bit multiplication of two uint256. * * The result is stored in two 256 variables such that product = high * 2²⁵⁶ + low. */ function mul512( uint256 a, uint256 b ) internal pure returns (uint256 high, uint256 low) { // 512-bit multiply [high low] = x * y. Compute the product mod 2²⁵⁶ and mod 2²⁵⁶ - 1, then use // the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256 // variables such that product = high * 2²⁵⁶ + low. /// @solidity memory-safe-assembly assembly { let mm := mulmod(a, b, not(0)) low := mul(a, b) high := sub(sub(mm, low), lt(mm, low)) } } /** * @dev Branchless ternary evaluation for `a ? b : c`. Gas costs are constant. * * IMPORTANT: This function may reduce bytecode size and consume less gas when used standalone. * However, the compiler may optimize Solidity ternary operations (i.e. `a ? b : c`) to only compute * one branch when needed, making this function more expensive. */ function ternary( bool condition, uint256 a, uint256 b ) internal pure returns (uint256) { unchecked { // branchless ternary works because: // b ^ (a ^ b) == a // b ^ 0 == b return b ^ ((a ^ b) * toUint(condition)); } } /** * @dev Cast a boolean (false or true) to a uint256 (0 or 1) with no jump. */ function toUint(bool b) internal pure returns (uint256 u) { /// @solidity memory-safe-assembly assembly { u := iszero(iszero(b)) } } /// @dev Reverts with a panic code. Recommended to use with /// the internal constants with predefined codes. function panic(uint256 code) internal pure { /// @solidity memory-safe-assembly assembly { mstore(0x00, 0x4e487b71) mstore(0x20, code) revert(0x1c, 0x24) } } /** * @dev Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or * denominator == 0. * * 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 { (uint256 high, uint256 low) = mul512(x, y); // Handle non-overflow cases, 256 by 256 division. if (high == 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 low / denominator; } // Make sure the result is less than 2²⁵⁶. Also prevents denominator == 0. if (denominator <= high) { panic( ternary(denominator == 0, DIVISION_BY_ZERO, UNDER_OVERFLOW) ); } /////////////////////////////////////////////// // 512 by 256 division. /////////////////////////////////////////////// // Make division exact by subtracting the remainder from [high low]. uint256 remainder; /// @solidity memory-safe-assembly assembly { // Compute remainder using mulmod. remainder := mulmod(x, y, denominator) // Subtract 256 bit number from 512 bit number. high := sub(high, gt(remainder, low)) low := sub(low, 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); /// @solidity memory-safe-assembly assembly { // Divide denominator by twos. denominator := div(denominator, twos) // Divide [high low] by twos. low := div(low, twos) // Flip twos such that it is 2²⁵⁶ / twos. If twos is zero, then it becomes one. twos := add(div(sub(0, twos), twos), 1) } // Shift in bits from high into low. low |= high * twos; // Invert denominator mod 2²⁵⁶. Now that denominator is an odd number, it has an inverse modulo 2²⁵⁶ such // that denominator * inv ≡ 1 mod 2²⁵⁶. Compute the inverse by starting with a seed that is correct for // four bits. That is, denominator * inv ≡ 1 mod 2⁴. 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⁸ inverse *= 2 - denominator * inverse; // inverse mod 2¹⁶ inverse *= 2 - denominator * inverse; // inverse mod 2³² inverse *= 2 - denominator * inverse; // inverse mod 2⁶⁴ inverse *= 2 - denominator * inverse; // inverse mod 2¹²⁸ inverse *= 2 - denominator * inverse; // inverse mod 2²⁵⁶ // 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²⁵⁶. Since the preconditions guarantee that the outcome is // less than 2²⁵⁶, this is the final result. We don't need to compute the high bits of the result and high // is no longer required. result = low * inverse; return result; } } // /** // * @dev 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) { // return mulDiv(x, y, denominator) + toUint(unsignedRoundsUp(rounding) && mulmod(x, y, denominator) > 0); // } /** * @dev Returns the absolute unsigned value of a signed value. */ function abs(int256 n) internal pure returns (uint256) { unchecked { // Formula from the "Bit Twiddling Hacks" by Sean Eron Anderson. // Since `n` is a signed integer, the generated bytecode will use the SAR opcode to perform the right shift, // taking advantage of the most significant (or "sign" bit) in two's complement representation. // This opcode adds new most significant bits set to the value of the previous most significant bit. As a result, // the mask will either be `bytes32(0)` (if n is positive) or `~bytes32(0)` (if n is negative). int256 mask = n >> 255; // A `bytes32(0)` mask leaves the input unchanged, while a `~bytes32(0)` mask complements it. return uint256((n + mask) ^ mask); } } /** * @dev Returns the multiplication of two unsigned integers, with a success flag (no overflow). */ function tryMul( uint256 a, uint256 b ) internal pure returns (bool success, uint256 result) { unchecked { uint256 c = a * b; /// @solidity memory-safe-assembly assembly { // Only true when the multiplication doesn't overflow // (c / a == b) || (a == 0) success := or(eq(div(c, a), b), iszero(a)) } // equivalent to: success ? c : 0 result = c * toUint(success); } } /** * @dev Returns the division of two unsigned integers, with a success flag (no division by zero). */ function tryDiv( uint256 a, uint256 b ) internal pure returns (bool success, uint256 result) { unchecked { success = b > 0; /// @solidity memory-safe-assembly assembly { // The `DIV` opcode returns zero when the denominator is 0. result := div(a, b) } } } }