Untitled diff
138 lines
pragma solidity 0.8.10;
pragma solidity ^0.8.10;
import {BitMath} from "./BitMath.sol";
library Uint256x256Math {
library Uint256x256Math {
error Uint256x256Math__MulShiftOverflow();
error Uint256x256Math__MulShiftOverflow();
error Uint256x256Math__MulDivOverflow();
error Uint256x256Math__MulDivOverflow();
function mulDivRoundDown(
function mulDivRoundDown(
uint256 x,
uint256 x,
uint256 y,
uint256 y,
uint256 denominator
uint256 denominator
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
(uint256 prod0, uint256 prod1) = _getMulProds(x, y);
(uint256 prod0, uint256 prod1) = _getMulProds(x, y);
return _getEndOfDivRoundDown(x, y, denominator, prod0, prod1);
return _getEndOfDivRoundDown(x, y, denominator, prod0, prod1);
}
}
function mulDivRoundUp(
function mulDivRoundUp(
uint256 x,
uint256 x,
uint256 y,
uint256 y,
uint256 denominator
uint256 denominator
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
result = mulDivRoundDown(x, y, denominator);
result = mulDivRoundDown(x, y, denominator);
if (mulmod(x, y, denominator) != 0) result += 1;
if (mulmod(x, y, denominator) != 0) result += 1;
}
}
function mulShiftRoundDown(
function mulShiftRoundDown(
uint256 x,
uint256 x,
uint256 y,
uint256 y,
uint8 offset
uint8 offset
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
(uint256 prod0, uint256 prod1) = _getMulProds(x, y);
(uint256 prod0, uint256 prod1) = _getMulProds(x, y);
if (prod0 != 0) result = prod0 >> offset;
if (prod0 != 0) result = prod0 >> offset;
if (prod1 != 0) {
if (prod1 != 0) {
if (prod1 >= 1 << offset)
if (prod1 >= 1 << offset)
revert Uint256x256Math__MulShiftOverflow();
revert Uint256x256Math__MulShiftOverflow();
unchecked {
unchecked {
result += prod1 << (256 - offset);
result += prod1 << (256 - offset);
}
}
}
}
}
}
function mulShiftRoundUp(
function mulShiftRoundUp(
uint256 x,
uint256 x,
uint256 y,
uint256 y,
uint8 offset
uint8 offset
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
result = mulShiftRoundDown(x, y, offset);
result = mulShiftRoundDown(x, y, offset);
if (mulmod(x, y, 1 << offset) != 0) result += 1;
if (mulmod(x, y, 1 << offset) != 0) result += 1;
}
}
function shiftDivRoundDown(
function shiftDivRoundDown(
uint256 x,
uint256 x,
uint8 offset,
uint8 offset,
uint256 denominator
uint256 denominator
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
uint256 prod0;
uint256 prod0;
uint256 prod1;
uint256 prod1;
prod0 = x << offset;
prod0 = x << offset;
unchecked {
unchecked {
prod1 = x >> (256 - offset);
prod1 = x >> (256 - offset);
}
}
return _getEndOfDivRoundDown(x, 1 << offset, denominator, prod0, prod1);
return _getEndOfDivRoundDown(x, 1 << offset, denominator, prod0, prod1);
}
}
function shiftDivRoundUp(
function shiftDivRoundUp(
uint256 x,
uint256 x,
uint8 offset,
uint8 offset,
uint256 denominator
uint256 denominator
) internal pure returns (uint256 result) {
) internal pure returns (uint256 result) {
result = shiftDivRoundDown(x, offset, denominator);
result = shiftDivRoundDown(x, offset, denominator);
if (mulmod(x, 1 << offset, denominator) != 0) result += 1;
if (mulmod(x, 1 << offset, denominator) != 0) result += 1;
}
}
function _getMulProds(uint256 x, uint256 y)
function _getMulProds(uint256 x, uint256 y)
private
private
pure
pure
returns (uint256 prod0, uint256 prod1)
returns (uint256 prod0, uint256 prod1)
{
{
assembly {
assembly {
let mm := mulmod(x, y, not(0))
let mm := mulmod(x, y, not(0))
prod0 := mul(x, y)
prod0 := mul(x, y)
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
}
}
}
function _getEndOfDivRoundDown(
function _getEndOfDivRoundDown(
uint256 x,
uint256 x,
uint256 y,
uint256 y,
uint256 denominator,
uint256 denominator,
uint256 prod0,
uint256 prod0,
uint256 prod1
uint256 prod1
) private pure returns (uint256 result) {
) private pure returns (uint256 result) {
if (prod1 == 0) {
if (prod1 == 0) {
unchecked {
unchecked {
result = prod0 / denominator;
result = prod0 / denominator;
}
}
} else {
} else {
if (prod1 >= denominator) revert Uint256x256Math__MulDivOverflow();
if (prod1 >= denominator) revert Uint256x256Math__MulDivOverflow();
uint256 remainder;
uint256 remainder;
assembly {
assembly {
remainder := mulmod(x, y, denominator)
remainder := mulmod(x, y, denominator)
prod1 := sub(prod1, gt(remainder, prod0))
prod1 := sub(prod1, gt(remainder, prod0))
prod0 := sub(prod0, remainder)
prod0 := sub(prod0, remainder)
}
}
unchecked {
unchecked {
uint256 lpotdod = denominator & (~denominator + 1);
uint256 lpotdod = denominator & (~denominator + 1);
assembly {
assembly {
denominator := div(denominator, lpotdod)
denominator := div(denominator, lpotdod)
prod0 := div(prod0, lpotdod)
prod0 := div(prod0, lpotdod)
lpotdod := add(div(sub(0, lpotdod), lpotdod), 1)
lpotdod := add(div(sub(0, lpotdod), lpotdod), 1)
}
}
prod0 |= prod1 * lpotdod;
prod0 |= prod1 * lpotdod;
uint256 inverse = (3 * denominator) ^ 2;
uint256 inverse = (3 * denominator) ^ 2;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
inverse *= 2 - denominator * inverse;
result = prod0 * inverse;
result = prod0 * inverse;
}
}
}
}
}
}
function sqrt(uint256 x) internal pure returns (uint256 sqrtX) {
if (x == 0) return 0;
uint256 msb = BitMath.mostSignificantBit(x);
assembly {
sqrtX := shl(shr(1, msb), 1)
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
sqrtX := shr(1, add(sqrtX, div(x, sqrtX)))
x := div(x, sqrtX)
}
return sqrtX < x ? sqrtX : x;
}
}
}