Copy
121// 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
122// use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
123// variables such that product = prod1 * 2^256 + prod0.
124uint256 prod0; // Least significant 256 bits of the product
125uint256 prod1; // Most significant 256 bits of the product
126assembly {
127    let mm := mulmod(x, y, not(0))
128    prod0 := mul(x, y)
129    prod1 := sub(sub(mm, prod0), lt(mm, prod0))
130}
131
132// Handle non-overflow cases, 256 by 256 division.
133if (prod1 == 0) {
134    // Solidity will revert if denominator == 0, unlike the div opcode on its own.
135    // The surrounding unchecked block does not change this fact.
136    // See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
137    return prod0 / denominator;
138}
139
140// Make sure the result is less than 2^256. Also prevents denominator == 0.
141if (denominator <= prod1) {
142    revert MathOverflowedMulDiv();
143}
144
145///////////////////////////////////////////////
146// 512 by 256 division.
147///////////////////////////////////////////////
148
149// Make division exact by subtracting the remainder from [prod1 prod0].
150uint256 remainder;
151assembly {
152    // Compute remainder using mulmod.
153    remainder := mulmod(x, y, denominator)
154
155    // Subtract 256 bit number from 512 bit number.
156    prod1 := sub(prod1, gt(remainder, prod0))
157    prod0 := sub(prod0, remainder)
158}
159
160// Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
161// See https://cs.stackexchange.com/q/138556/92363.
162
163// Does not overflow because the denominator cannot be zero at this stage in the function.
164uint256 twos = denominator & (~denominator + 1);