Math.sol 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
  1. // SPDX-License-Identifier: MIT
  2. // OpenZeppelin Contracts (last updated v4.5.0) (utils/math/Math.sol)
  3. pragma solidity ^0.8.0;
  4. /**
  5. * @dev Standard math utilities missing in the Solidity language.
  6. */
  7. library Math {
  8. enum Rounding {
  9. Down, // Toward negative infinity
  10. Up, // Toward infinity
  11. Zero // Toward zero
  12. }
  13. /**
  14. * @dev Returns the largest of two numbers.
  15. */
  16. function max(uint256 a, uint256 b) internal pure returns (uint256) {
  17. return a >= b ? a : b;
  18. }
  19. /**
  20. * @dev Returns the smallest of two numbers.
  21. */
  22. function min(uint256 a, uint256 b) internal pure returns (uint256) {
  23. return a < b ? a : b;
  24. }
  25. /**
  26. * @dev Returns the average of two numbers. The result is rounded towards
  27. * zero.
  28. */
  29. function average(uint256 a, uint256 b) internal pure returns (uint256) {
  30. // (a + b) / 2 can overflow.
  31. return (a & b) + (a ^ b) / 2;
  32. }
  33. /**
  34. * @dev Returns the ceiling of the division of two numbers.
  35. *
  36. * This differs from standard division with `/` in that it rounds up instead
  37. * of rounding down.
  38. */
  39. function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
  40. // (a + b - 1) / b can overflow on addition, so we distribute.
  41. return a == 0 ? 0 : (a - 1) / b + 1;
  42. }
  43. /**
  44. * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
  45. * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
  46. * with further edits by Uniswap Labs also under MIT license.
  47. */
  48. function mulDiv(
  49. uint256 x,
  50. uint256 y,
  51. uint256 denominator
  52. ) internal pure returns (uint256 result) {
  53. unchecked {
  54. // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
  55. // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
  56. // variables such that product = prod1 * 2^256 + prod0.
  57. uint256 prod0; // Least significant 256 bits of the product
  58. uint256 prod1; // Most significant 256 bits of the product
  59. assembly {
  60. let mm := mulmod(x, y, not(0))
  61. prod0 := mul(x, y)
  62. prod1 := sub(sub(mm, prod0), lt(mm, prod0))
  63. }
  64. // Handle non-overflow cases, 256 by 256 division.
  65. if (prod1 == 0) {
  66. return prod0 / denominator;
  67. }
  68. // Make sure the result is less than 2^256. Also prevents denominator == 0.
  69. require(denominator > prod1);
  70. ///////////////////////////////////////////////
  71. // 512 by 256 division.
  72. ///////////////////////////////////////////////
  73. // Make division exact by subtracting the remainder from [prod1 prod0].
  74. uint256 remainder;
  75. assembly {
  76. // Compute remainder using mulmod.
  77. remainder := mulmod(x, y, denominator)
  78. // Subtract 256 bit number from 512 bit number.
  79. prod1 := sub(prod1, gt(remainder, prod0))
  80. prod0 := sub(prod0, remainder)
  81. }
  82. // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
  83. // See https://cs.stackexchange.com/q/138556/92363.
  84. // Does not overflow because the denominator cannot be zero at this stage in the function.
  85. uint256 twos = denominator & (~denominator + 1);
  86. assembly {
  87. // Divide denominator by twos.
  88. denominator := div(denominator, twos)
  89. // Divide [prod1 prod0] by twos.
  90. prod0 := div(prod0, twos)
  91. // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
  92. twos := add(div(sub(0, twos), twos), 1)
  93. }
  94. // Shift in bits from prod1 into prod0.
  95. prod0 |= prod1 * twos;
  96. // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
  97. // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
  98. // four bits. That is, denominator * inv = 1 mod 2^4.
  99. uint256 inverse = (3 * denominator) ^ 2;
  100. // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
  101. // in modular arithmetic, doubling the correct bits in each step.
  102. inverse *= 2 - denominator * inverse; // inverse mod 2^8
  103. inverse *= 2 - denominator * inverse; // inverse mod 2^16
  104. inverse *= 2 - denominator * inverse; // inverse mod 2^32
  105. inverse *= 2 - denominator * inverse; // inverse mod 2^64
  106. inverse *= 2 - denominator * inverse; // inverse mod 2^128
  107. inverse *= 2 - denominator * inverse; // inverse mod 2^256
  108. // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
  109. // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
  110. // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
  111. // is no longer required.
  112. result = prod0 * inverse;
  113. return result;
  114. }
  115. }
  116. /**
  117. * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
  118. */
  119. function mulDiv(
  120. uint256 x,
  121. uint256 y,
  122. uint256 denominator,
  123. Rounding rounding
  124. ) internal pure returns (uint256) {
  125. uint256 result = mulDiv(x, y, denominator);
  126. if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
  127. result += 1;
  128. }
  129. return result;
  130. }
  131. }