// SPDX-License-Identifier: BSD-4-Clause
/*
 * ABDK Math 64.64 Smart Contract Library.  Copyright © 2019 by ABDK Consulting.
 * Author: Mikhail Vladimirov <mikhail.vladimirov@gmail.com>
 */
pragma solidity ^0.8.0;

/**
 * Smart contract library of mathematical functions operating with signed
 * 64.64-bit fixed point numbers.  Signed 64.64-bit fixed point number is
 * basically a simple fraction whose numerator is signed 128-bit integer and
 * denominator is 2^64.  As long as denominator is always the same, there is no
 * need to store it, thus in Solidity signed 64.64-bit fixed point numbers are
 * represented by int128 type holding only the numerator.
 */
library Math64x64 {
	/*
	 * Minimum value signed 64.64-bit fixed point number may have.
	 */
	int128 private constant MIN_64x64 = -0x80000000000000000000000000000000;

	/*
	 * Maximum value signed 64.64-bit fixed point number may have.
	 */
	int128 private constant MAX_64x64 = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;

	/**
	 * Convert unsigned 256-bit integer number into signed 64.64-bit fixed point
	 * number.  Revert on overflow.
	 *
	 * @param x unsigned 256-bit integer number
	 * @return signed 64.64-bit fixed point number
	 */
	function fromUInt(uint256 x) internal pure returns (int128) {
		unchecked {
			require(x <= 0x7FFFFFFFFFFFFFFF);
			return int128(int256(x << 64));
		}
	}

	/**
	 * Convert signed 64.64 fixed point number into unsigned 64-bit integer
	 * number rounding down.  Revert on underflow.
	 *
	 * @param x signed 64.64-bit fixed point number
	 * @return unsigned 64-bit integer number
	 */
	function toUInt(int128 x) internal pure returns (uint64) {
		unchecked {
			require(x >= 0);
			return uint64(uint128(x >> 64));
		}
	}

	/**
	 * Calculate x * y rounding down, where x is signed 64.64 fixed point number
	 * and y is unsigned 256-bit integer number.  Revert on overflow.
	 *
	 * @param x signed 64.64 fixed point number
	 * @param y unsigned 256-bit integer number
	 * @return unsigned 256-bit integer number
	 */
	function mulu(int128 x, uint256 y) internal pure returns (uint256) {
		unchecked {
			if (y == 0) return 0;

			require(x >= 0);

			uint256 lo = (uint256(int256(x)) *
				(y & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)) >> 64;
			uint256 hi = uint256(int256(x)) * (y >> 128);

			require(hi <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF);
			hi <<= 64;

			require(
				hi <=
					0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF -
						lo
			);
			return hi + lo;
		}
	}

	/**
	 * Calculate x / y rounding towards zero, where x and y are unsigned 256-bit
	 * integer numbers.  Revert on overflow or when y is zero.
	 *
	 * @param x unsigned 256-bit integer number
	 * @param y unsigned 256-bit integer number
	 * @return signed 64.64-bit fixed point number
	 */
	function divu(uint256 x, uint256 y) internal pure returns (int128) {
		unchecked {
			require(y != 0);
			uint128 result = divuu(x, y);
			require(result <= uint128(MAX_64x64));
			return int128(result);
		}
	}

	/**
	 * Calculate x^y assuming 0^0 is 1, where x is signed 64.64 fixed point number
	 * and y is unsigned 256-bit integer number.  Revert on overflow.
	 *
	 * @param x signed 64.64-bit fixed point number
	 * @param y uint256 value
	 * @return signed 64.64-bit fixed point number
	 */
	function pow(int128 x, uint256 y) internal pure returns (int128) {
		unchecked {
			bool negative = x < 0 && y & 1 == 1;

			uint256 absX = uint128(x < 0 ? -x : x);
			uint256 absResult;
			absResult = 0x100000000000000000000000000000000;

			if (absX <= 0x10000000000000000) {
				absX <<= 63;
				while (y != 0) {
					if (y & 0x1 != 0) {
						absResult = (absResult * absX) >> 127;
					}
					absX = (absX * absX) >> 127;

					if (y & 0x2 != 0) {
						absResult = (absResult * absX) >> 127;
					}
					absX = (absX * absX) >> 127;

					if (y & 0x4 != 0) {
						absResult = (absResult * absX) >> 127;
					}
					absX = (absX * absX) >> 127;

					if (y & 0x8 != 0) {
						absResult = (absResult * absX) >> 127;
					}
					absX = (absX * absX) >> 127;

					y >>= 4;
				}

				absResult >>= 64;
			} else {
				uint256 absXShift = 63;
				if (absX < 0x1000000000000000000000000) {
					absX <<= 32;
					absXShift -= 32;
				}
				if (absX < 0x10000000000000000000000000000) {
					absX <<= 16;
					absXShift -= 16;
				}
				if (absX < 0x1000000000000000000000000000000) {
					absX <<= 8;
					absXShift -= 8;
				}
				if (absX < 0x10000000000000000000000000000000) {
					absX <<= 4;
					absXShift -= 4;
				}
				if (absX < 0x40000000000000000000000000000000) {
					absX <<= 2;
					absXShift -= 2;
				}
				if (absX < 0x80000000000000000000000000000000) {
					absX <<= 1;
					absXShift -= 1;
				}

				uint256 resultShift = 0;
				while (y != 0) {
					require(absXShift < 64);

					if (y & 0x1 != 0) {
						absResult = (absResult * absX) >> 127;
						resultShift += absXShift;
						if (absResult > 0x100000000000000000000000000000000) {
							absResult >>= 1;
							resultShift += 1;
						}
					}
					absX = (absX * absX) >> 127;
					absXShift <<= 1;
					if (absX >= 0x100000000000000000000000000000000) {
						absX >>= 1;
						absXShift += 1;
					}

					y >>= 1;
				}

				require(resultShift < 64);
				absResult >>= 64 - resultShift;
			}
			int256 result = negative ? -int256(absResult) : int256(absResult);
			require(result >= MIN_64x64 && result <= MAX_64x64);
			return int128(result);
		}
	}

	/**
	 * Calculate x / y rounding towards zero, where x and y are unsigned 256-bit
	 * integer numbers.  Revert on overflow or when y is zero.
	 *
	 * @param x unsigned 256-bit integer number
	 * @param y unsigned 256-bit integer number
	 * @return unsigned 64.64-bit fixed point number
	 */
	function divuu(uint256 x, uint256 y) private pure returns (uint128) {
		unchecked {
			require(y != 0);

			uint256 result;

			if (x <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
				result = (x << 64) / y;
			else {
				uint256 msb = 192;
				uint256 xc = x >> 192;
				if (xc >= 0x100000000) {
					xc >>= 32;
					msb += 32;
				}
				if (xc >= 0x10000) {
					xc >>= 16;
					msb += 16;
				}
				if (xc >= 0x100) {
					xc >>= 8;
					msb += 8;
				}
				if (xc >= 0x10) {
					xc >>= 4;
					msb += 4;
				}
				if (xc >= 0x4) {
					xc >>= 2;
					msb += 2;
				}
				if (xc >= 0x2) msb += 1; // No need to shift xc anymore

				result = (x << (255 - msb)) / (((y - 1) >> (msb - 191)) + 1);
				require(result <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF);

				uint256 hi = result * (y >> 128);
				uint256 lo = result * (y & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF);

				uint256 xh = x >> 192;
				uint256 xl = x << 64;

				if (xl < lo) xh -= 1;
				xl -= lo; // We rely on overflow behavior here
				lo = hi << 128;
				if (xl < lo) xh -= 1;
				xl -= lo; // We rely on overflow behavior here

				assert(xh == hi >> 128);

				result += xl / y;
			}

			require(result <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF);
			return uint128(result);
		}
	}
}