Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE
• 🤖 Code ReaderBeta

More Options

• Similar
• Submit Audit
• Compare

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.20;

import {SafeCast} from "@openzeppelin/contracts/utils/math/SafeCast.sol";

import {IBookManager} from "../interfaces/IBookManager.sol";
import {SegmentedSegmentTree} from "./SegmentedSegmentTree.sol";
import {Tick, TickLibrary} from "./Tick.sol";
import {OrderId, OrderIdLibrary} from "./OrderId.sol";
import {TotalClaimableMap} from "./TotalClaimableMap.sol";
import {TickBitmap} from "./TickBitmap.sol";

library Book {
    using Book for State;
    using TickBitmap for mapping(uint256 => uint256);
    using SegmentedSegmentTree for SegmentedSegmentTree.Core;
    using TotalClaimableMap for mapping(uint24 => uint256);
    using TickLibrary for Tick;
    using OrderIdLibrary for OrderId;

    error ZeroUnit();
    error BookAlreadyOpened();
    error BookNotOpened();
    error QueueReplaceFailed();
    error CancelFailed(uint64 maxCancelableUnit);

    // @dev Due to the segment tree implementation, the maximum order size is 2 ** 15.
    uint40 internal constant MAX_ORDER = 2 ** 15; // 32768
    uint256 internal constant MAX_ORDER_M = 2 ** 15 - 1; // % 32768

    struct Order {
        address provider;
        uint64 pending; // @dev unfilled unit + filled(claimable) unit
    }

    struct Queue {
        SegmentedSegmentTree.Core tree;
        Order[] orders;
    }

    struct State {
        IBookManager.BookKey key;
        mapping(Tick tick => Queue) queues;
        mapping(uint256 => uint256) tickBitmap;
        // @dev Four values of totalClaimable are stored in one uint256
        mapping(uint24 groupIndex => uint256) totalClaimableOf;
    }

    function open(State storage self, IBookManager.BookKey calldata key) external {
        if (self.isOpened()) revert BookAlreadyOpened();
        self.key = key;
    }

    function isOpened(State storage self) internal view returns (bool) {
        return self.key.unitSize != 0;
    }

    function checkOpened(State storage self) internal view {
        if (!self.isOpened()) revert BookNotOpened();
    }

    function depth(State storage self, Tick tick) internal view returns (uint64) {
        return self.queues[tick].tree.total() - self.totalClaimableOf.get(tick);
    }

    function highest(State storage self) internal view returns (Tick) {
        return self.tickBitmap.highest();
    }

    function maxLessThan(State storage self, Tick tick) internal view returns (Tick) {
        return self.tickBitmap.maxLessThan(tick);
    }

    function isEmpty(State storage self) internal view returns (bool) {
        return self.tickBitmap.isEmpty();
    }

    function _getOrder(State storage self, Tick tick, uint40 index) private view returns (Order storage) {
        return self.queues[tick].orders[index];
    }

    function getOrder(State storage self, Tick tick, uint40 index) internal view returns (Order memory) {
        return _getOrder(self, tick, index);
    }

    function make(State storage self, Tick tick, uint64 unit, address provider) external returns (uint40 orderIndex) {
        if (unit == 0) revert ZeroUnit();
        if (!self.tickBitmap.has(tick)) self.tickBitmap.set(tick);

        Queue storage queue = self.queues[tick];
        // @dev Assume that orders.length cannot reach to type(uint40).max + 1.
        orderIndex = SafeCast.toUint40(queue.orders.length);

        if (orderIndex >= MAX_ORDER) {
            unchecked {
                uint40 staleOrderIndex = orderIndex - MAX_ORDER;
                uint64 stalePendingUnit = queue.orders[staleOrderIndex].pending;
                if (stalePendingUnit > 0) {
                    // If the order is not settled completely, we cannot replace it
                    uint64 claimable = calculateClaimableUnit(self, tick, staleOrderIndex);
                    if (claimable != stalePendingUnit) revert QueueReplaceFailed();
                }
            }

            // The stale order is settled completely, so remove it from the totalClaimableOf.
            // We can determine the stale order is claimable.
            uint64 staleOrderedUnit = queue.tree.get(orderIndex & MAX_ORDER_M);
            if (staleOrderedUnit > 0) self.totalClaimableOf.sub(tick, staleOrderedUnit);
        }

        queue.tree.update(orderIndex & MAX_ORDER_M, unit);

        queue.orders.push(Order({pending: unit, provider: provider}));
    }

    /**
     * @notice Take orders from the book
     * @param self The book state
     * @param maxTakeUnit The maximum unit to take
     * @return takenUnit The actual unit to take
     */
    function take(State storage self, Tick tick, uint64 maxTakeUnit) external returns (uint64 takenUnit) {
        uint64 currentDepth = depth(self, tick);
        if (currentDepth > maxTakeUnit) {
            takenUnit = maxTakeUnit;
        } else {
            takenUnit = currentDepth;
            self.tickBitmap.clear(tick);
        }

        self.totalClaimableOf.add(tick, takenUnit);
    }

    function cancel(State storage self, OrderId orderId, uint64 to)
        external
        returns (uint64 canceled, uint64 afterPending)
    {
        (, Tick tick, uint40 orderIndex) = orderId.decode();
        Queue storage queue = self.queues[tick];
        uint64 pendingUnit = queue.orders[orderIndex].pending;
        uint64 claimableUnit = calculateClaimableUnit(self, tick, orderIndex);
        afterPending = to + claimableUnit;
        unchecked {
            if (pendingUnit < afterPending) revert CancelFailed(pendingUnit - claimableUnit);
            canceled = pendingUnit - afterPending;

            self.queues[tick].tree.update(
                orderIndex & MAX_ORDER_M, self.queues[tick].tree.get(orderIndex & MAX_ORDER_M) - canceled
            );
        }
        queue.orders[orderIndex].pending = afterPending;

        if (depth(self, tick) == 0) {
            // clear() won't revert so we can cancel with to=0 even if the depth() is already zero
            // works even if bitmap is empty
            self.tickBitmap.clear(tick);
        }
    }

    function claim(State storage self, Tick tick, uint40 index) external returns (uint64 claimedUnit) {
        Order storage order = _getOrder(self, tick, index);

        claimedUnit = calculateClaimableUnit(self, tick, index);
        unchecked {
            order.pending -= claimedUnit;
        }
    }

    function calculateClaimableUnit(State storage self, Tick tick, uint40 index) public view returns (uint64) {
        uint64 orderUnit = self.getOrder(tick, index).pending;

        Queue storage queue = self.queues[tick];
        // @dev Book logic always considers replaced orders as claimable.
        unchecked {
            if (uint256(index) + MAX_ORDER < queue.orders.length) return orderUnit;
            uint64 totalClaimableUnit = self.totalClaimableOf.get(tick);
            uint64 rangeRight = _getClaimRangeRight(queue, index);
            if (rangeRight - orderUnit >= totalClaimableUnit) return 0;

            // -------- totalClaimable ---------|---
            // ------|----  orderUnit  ----|--------
            //   rangeLeft           rangeRight
            if (rangeRight <= totalClaimableUnit) return orderUnit;
            // -- totalClaimable --|----------------
            // ------|----  orderUnit  ----|--------
            //   rangeLeft           rangeRight
            else return totalClaimableUnit - (rangeRight - orderUnit);
        }
    }

    function _getClaimRangeRight(Queue storage queue, uint256 orderIndex) private view returns (uint64 rangeRight) {
        uint256 l = queue.orders.length & MAX_ORDER_M;
        uint256 r = (orderIndex + 1) & MAX_ORDER_M;
        rangeRight = (l < r) ? queue.tree.query(l, r) : queue.tree.total() - queue.tree.query(r, l);
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (token/ERC20/IERC20.sol)

pragma solidity ^0.8.20;

/**
 * @dev Interface of the ERC-20 standard as defined in the ERC.
 */
interface IERC20 {
    /**
     * @dev Emitted when `value` tokens are moved from one account (`from`) to
     * another (`to`).
     *
     * Note that `value` may be zero.
     */
    event Transfer(address indexed from, address indexed to, uint256 value);

    /**
     * @dev Emitted when the allowance of a `spender` for an `owner` is set by
     * a call to {approve}. `value` is the new allowance.
     */
    event Approval(address indexed owner, address indexed spender, uint256 value);

    /**
     * @dev Returns the value of tokens in existence.
     */
    function totalSupply() external view returns (uint256);

    /**
     * @dev Returns the value of tokens owned by `account`.
     */
    function balanceOf(address account) external view returns (uint256);

    /**
     * @dev Moves a `value` amount of tokens from the caller's account to `to`.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transfer(address to, uint256 value) external returns (bool);

    /**
     * @dev Returns the remaining number of tokens that `spender` will be
     * allowed to spend on behalf of `owner` through {transferFrom}. This is
     * zero by default.
     *
     * This value changes when {approve} or {transferFrom} are called.
     */
    function allowance(address owner, address spender) external view returns (uint256);

    /**
     * @dev Sets a `value` amount of tokens as the allowance of `spender` over the
     * caller's tokens.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * IMPORTANT: Beware that changing an allowance with this method brings the risk
     * that someone may use both the old and the new allowance by unfortunate
     * transaction ordering. One possible solution to mitigate this race
     * condition is to first reduce the spender's allowance to 0 and set the
     * desired value afterwards:
     * https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
     *
     * Emits an {Approval} event.
     */
    function approve(address spender, uint256 value) external returns (bool);

    /**
     * @dev Moves a `value` amount of tokens from `from` to `to` using the
     * allowance mechanism. `value` is then deducted from the caller's
     * allowance.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(address from, address to, uint256 value) external returns (bool);
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (token/ERC721/extensions/IERC721Metadata.sol)

pragma solidity ^0.8.20;

import {IERC721} from "../IERC721.sol";

/**
 * @title ERC-721 Non-Fungible Token Standard, optional metadata extension
 * @dev See https://eips.ethereum.org/EIPS/eip-721
 */
interface IERC721Metadata is IERC721 {
    /**
     * @dev Returns the token collection name.
     */
    function name() external view returns (string memory);

    /**
     * @dev Returns the token collection symbol.
     */
    function symbol() external view returns (string memory);

    /**
     * @dev Returns the Uniform Resource Identifier (URI) for `tokenId` token.
     */
    function tokenURI(uint256 tokenId) external view returns (string memory);
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (token/ERC721/IERC721.sol)

pragma solidity ^0.8.20;

import {IERC165} from "../../utils/introspection/IERC165.sol";

/**
 * @dev Required interface of an ERC-721 compliant contract.
 */
interface IERC721 is IERC165 {
    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables `approved` to manage the `tokenId` token.
     */
    event Approval(address indexed owner, address indexed approved, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables or disables (`approved`) `operator` to manage all of its assets.
     */
    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /**
     * @dev Returns the number of tokens in ``owner``'s account.
     */
    function balanceOf(address owner) external view returns (uint256 balance);

    /**
     * @dev Returns the owner of the `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function ownerOf(uint256 tokenId) external view returns (address owner);

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon
     *   a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(address from, address to, uint256 tokenId, bytes calldata data) external;

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC-721 protocol to prevent tokens from being forever locked.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must have been allowed to move this token by either {approve} or
     *   {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon
     *   a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(address from, address to, uint256 tokenId) external;

    /**
     * @dev Transfers `tokenId` token from `from` to `to`.
     *
     * WARNING: Note that the caller is responsible to confirm that the recipient is capable of receiving ERC-721
     * or else they may be permanently lost. Usage of {safeTransferFrom} prevents loss, though the caller must
     * understand this adds an external call which potentially creates a reentrancy vulnerability.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(address from, address to, uint256 tokenId) external;

    /**
     * @dev Gives permission to `to` to transfer `tokenId` token to another account.
     * The approval is cleared when the token is transferred.
     *
     * Only a single account can be approved at a time, so approving the zero address clears previous approvals.
     *
     * Requirements:
     *
     * - The caller must own the token or be an approved operator.
     * - `tokenId` must exist.
     *
     * Emits an {Approval} event.
     */
    function approve(address to, uint256 tokenId) external;

    /**
     * @dev Approve or remove `operator` as an operator for the caller.
     * Operators can call {transferFrom} or {safeTransferFrom} for any token owned by the caller.
     *
     * Requirements:
     *
     * - The `operator` cannot be the address zero.
     *
     * Emits an {ApprovalForAll} event.
     */
    function setApprovalForAll(address operator, bool approved) external;

    /**
     * @dev Returns the account approved for `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function getApproved(uint256 tokenId) external view returns (address operator);

    /**
     * @dev Returns if the `operator` is allowed to manage all of the assets of `owner`.
     *
     * See {setApprovalForAll}
     */
    function isApprovedForAll(address owner, address operator) external view returns (bool);
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/introspection/IERC165.sol)

pragma solidity ^0.8.20;

/**
 * @dev Interface of the ERC-165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[ERC].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165 {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[ERC section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/math/SafeCast.sol)
// This file was procedurally generated from scripts/generate/templates/SafeCast.js.

pragma solidity ^0.8.20;

/**
 * @dev Wrappers over Solidity's uintXX/intXX/bool casting operators with added overflow
 * checks.
 *
 * Downcasting from uint256/int256 in Solidity does not revert on overflow. This can
 * easily result in undesired exploitation or bugs, since developers usually
 * assume that overflows raise errors. `SafeCast` restores this intuition by
 * reverting the transaction when such an operation overflows.
 *
 * Using this library instead of the unchecked operations eliminates an entire
 * class of bugs, so it's recommended to use it always.
 */
library SafeCast {
    /**
     * @dev Value doesn't fit in an uint of `bits` size.
     */
    error SafeCastOverflowedUintDowncast(uint8 bits, uint256 value);

    /**
     * @dev An int value doesn't fit in an uint of `bits` size.
     */
    error SafeCastOverflowedIntToUint(int256 value);

    /**
     * @dev Value doesn't fit in an int of `bits` size.
     */
    error SafeCastOverflowedIntDowncast(uint8 bits, int256 value);

    /**
     * @dev An uint value doesn't fit in an int of `bits` size.
     */
    error SafeCastOverflowedUintToInt(uint256 value);

    /**
     * @dev Returns the downcasted uint248 from uint256, reverting on
     * overflow (when the input is greater than largest uint248).
     *
     * Counterpart to Solidity's `uint248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     */
    function toUint248(uint256 value) internal pure returns (uint248) {
        if (value > type(uint248).max) {
            revert SafeCastOverflowedUintDowncast(248, value);
        }
        return uint248(value);
    }

    /**
     * @dev Returns the downcasted uint240 from uint256, reverting on
     * overflow (when the input is greater than largest uint240).
     *
     * Counterpart to Solidity's `uint240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     */
    function toUint240(uint256 value) internal pure returns (uint240) {
        if (value > type(uint240).max) {
            revert SafeCastOverflowedUintDowncast(240, value);
        }
        return uint240(value);
    }

    /**
     * @dev Returns the downcasted uint232 from uint256, reverting on
     * overflow (when the input is greater than largest uint232).
     *
     * Counterpart to Solidity's `uint232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     */
    function toUint232(uint256 value) internal pure returns (uint232) {
        if (value > type(uint232).max) {
            revert SafeCastOverflowedUintDowncast(232, value);
        }
        return uint232(value);
    }

    /**
     * @dev Returns the downcasted uint224 from uint256, reverting on
     * overflow (when the input is greater than largest uint224).
     *
     * Counterpart to Solidity's `uint224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     */
    function toUint224(uint256 value) internal pure returns (uint224) {
        if (value > type(uint224).max) {
            revert SafeCastOverflowedUintDowncast(224, value);
        }
        return uint224(value);
    }

    /**
     * @dev Returns the downcasted uint216 from uint256, reverting on
     * overflow (when the input is greater than largest uint216).
     *
     * Counterpart to Solidity's `uint216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     */
    function toUint216(uint256 value) internal pure returns (uint216) {
        if (value > type(uint216).max) {
            revert SafeCastOverflowedUintDowncast(216, value);
        }
        return uint216(value);
    }

    /**
     * @dev Returns the downcasted uint208 from uint256, reverting on
     * overflow (when the input is greater than largest uint208).
     *
     * Counterpart to Solidity's `uint208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     */
    function toUint208(uint256 value) internal pure returns (uint208) {
        if (value > type(uint208).max) {
            revert SafeCastOverflowedUintDowncast(208, value);
        }
        return uint208(value);
    }

    /**
     * @dev Returns the downcasted uint200 from uint256, reverting on
     * overflow (when the input is greater than largest uint200).
     *
     * Counterpart to Solidity's `uint200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     */
    function toUint200(uint256 value) internal pure returns (uint200) {
        if (value > type(uint200).max) {
            revert SafeCastOverflowedUintDowncast(200, value);
        }
        return uint200(value);
    }

    /**
     * @dev Returns the downcasted uint192 from uint256, reverting on
     * overflow (when the input is greater than largest uint192).
     *
     * Counterpart to Solidity's `uint192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     */
    function toUint192(uint256 value) internal pure returns (uint192) {
        if (value > type(uint192).max) {
            revert SafeCastOverflowedUintDowncast(192, value);
        }
        return uint192(value);
    }

    /**
     * @dev Returns the downcasted uint184 from uint256, reverting on
     * overflow (when the input is greater than largest uint184).
     *
     * Counterpart to Solidity's `uint184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     */
    function toUint184(uint256 value) internal pure returns (uint184) {
        if (value > type(uint184).max) {
            revert SafeCastOverflowedUintDowncast(184, value);
        }
        return uint184(value);
    }

    /**
     * @dev Returns the downcasted uint176 from uint256, reverting on
     * overflow (when the input is greater than largest uint176).
     *
     * Counterpart to Solidity's `uint176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     */
    function toUint176(uint256 value) internal pure returns (uint176) {
        if (value > type(uint176).max) {
            revert SafeCastOverflowedUintDowncast(176, value);
        }
        return uint176(value);
    }

    /**
     * @dev Returns the downcasted uint168 from uint256, reverting on
     * overflow (when the input is greater than largest uint168).
     *
     * Counterpart to Solidity's `uint168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     */
    function toUint168(uint256 value) internal pure returns (uint168) {
        if (value > type(uint168).max) {
            revert SafeCastOverflowedUintDowncast(168, value);
        }
        return uint168(value);
    }

    /**
     * @dev Returns the downcasted uint160 from uint256, reverting on
     * overflow (when the input is greater than largest uint160).
     *
     * Counterpart to Solidity's `uint160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     */
    function toUint160(uint256 value) internal pure returns (uint160) {
        if (value > type(uint160).max) {
            revert SafeCastOverflowedUintDowncast(160, value);
        }
        return uint160(value);
    }

    /**
     * @dev Returns the downcasted uint152 from uint256, reverting on
     * overflow (when the input is greater than largest uint152).
     *
     * Counterpart to Solidity's `uint152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     */
    function toUint152(uint256 value) internal pure returns (uint152) {
        if (value > type(uint152).max) {
            revert SafeCastOverflowedUintDowncast(152, value);
        }
        return uint152(value);
    }

    /**
     * @dev Returns the downcasted uint144 from uint256, reverting on
     * overflow (when the input is greater than largest uint144).
     *
     * Counterpart to Solidity's `uint144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     */
    function toUint144(uint256 value) internal pure returns (uint144) {
        if (value > type(uint144).max) {
            revert SafeCastOverflowedUintDowncast(144, value);
        }
        return uint144(value);
    }

    /**
     * @dev Returns the downcasted uint136 from uint256, reverting on
     * overflow (when the input is greater than largest uint136).
     *
     * Counterpart to Solidity's `uint136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     */
    function toUint136(uint256 value) internal pure returns (uint136) {
        if (value > type(uint136).max) {
            revert SafeCastOverflowedUintDowncast(136, value);
        }
        return uint136(value);
    }

    /**
     * @dev Returns the downcasted uint128 from uint256, reverting on
     * overflow (when the input is greater than largest uint128).
     *
     * Counterpart to Solidity's `uint128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     */
    function toUint128(uint256 value) internal pure returns (uint128) {
        if (value > type(uint128).max) {
            revert SafeCastOverflowedUintDowncast(128, value);
        }
        return uint128(value);
    }

    /**
     * @dev Returns the downcasted uint120 from uint256, reverting on
     * overflow (when the input is greater than largest uint120).
     *
     * Counterpart to Solidity's `uint120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     */
    function toUint120(uint256 value) internal pure returns (uint120) {
        if (value > type(uint120).max) {
            revert SafeCastOverflowedUintDowncast(120, value);
        }
        return uint120(value);
    }

    /**
     * @dev Returns the downcasted uint112 from uint256, reverting on
     * overflow (when the input is greater than largest uint112).
     *
     * Counterpart to Solidity's `uint112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     */
    function toUint112(uint256 value) internal pure returns (uint112) {
        if (value > type(uint112).max) {
            revert SafeCastOverflowedUintDowncast(112, value);
        }
        return uint112(value);
    }

    /**
     * @dev Returns the downcasted uint104 from uint256, reverting on
     * overflow (when the input is greater than largest uint104).
     *
     * Counterpart to Solidity's `uint104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     */
    function toUint104(uint256 value) internal pure returns (uint104) {
        if (value > type(uint104).max) {
            revert SafeCastOverflowedUintDowncast(104, value);
        }
        return uint104(value);
    }

    /**
     * @dev Returns the downcasted uint96 from uint256, reverting on
     * overflow (when the input is greater than largest uint96).
     *
     * Counterpart to Solidity's `uint96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     */
    function toUint96(uint256 value) internal pure returns (uint96) {
        if (value > type(uint96).max) {
            revert SafeCastOverflowedUintDowncast(96, value);
        }
        return uint96(value);
    }

    /**
     * @dev Returns the downcasted uint88 from uint256, reverting on
     * overflow (when the input is greater than largest uint88).
     *
     * Counterpart to Solidity's `uint88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     */
    function toUint88(uint256 value) internal pure returns (uint88) {
        if (value > type(uint88).max) {
            revert SafeCastOverflowedUintDowncast(88, value);
        }
        return uint88(value);
    }

    /**
     * @dev Returns the downcasted uint80 from uint256, reverting on
     * overflow (when the input is greater than largest uint80).
     *
     * Counterpart to Solidity's `uint80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     */
    function toUint80(uint256 value) internal pure returns (uint80) {
        if (value > type(uint80).max) {
            revert SafeCastOverflowedUintDowncast(80, value);
        }
        return uint80(value);
    }

    /**
     * @dev Returns the downcasted uint72 from uint256, reverting on
     * overflow (when the input is greater than largest uint72).
     *
     * Counterpart to Solidity's `uint72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     */
    function toUint72(uint256 value) internal pure returns (uint72) {
        if (value > type(uint72).max) {
            revert SafeCastOverflowedUintDowncast(72, value);
        }
        return uint72(value);
    }

    /**
     * @dev Returns the downcasted uint64 from uint256, reverting on
     * overflow (when the input is greater than largest uint64).
     *
     * Counterpart to Solidity's `uint64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     */
    function toUint64(uint256 value) internal pure returns (uint64) {
        if (value > type(uint64).max) {
            revert SafeCastOverflowedUintDowncast(64, value);
        }
        return uint64(value);
    }

    /**
     * @dev Returns the downcasted uint56 from uint256, reverting on
     * overflow (when the input is greater than largest uint56).
     *
     * Counterpart to Solidity's `uint56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     */
    function toUint56(uint256 value) internal pure returns (uint56) {
        if (value > type(uint56).max) {
            revert SafeCastOverflowedUintDowncast(56, value);
        }
        return uint56(value);
    }

    /**
     * @dev Returns the downcasted uint48 from uint256, reverting on
     * overflow (when the input is greater than largest uint48).
     *
     * Counterpart to Solidity's `uint48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     */
    function toUint48(uint256 value) internal pure returns (uint48) {
        if (value > type(uint48).max) {
            revert SafeCastOverflowedUintDowncast(48, value);
        }
        return uint48(value);
    }

    /**
     * @dev Returns the downcasted uint40 from uint256, reverting on
     * overflow (when the input is greater than largest uint40).
     *
     * Counterpart to Solidity's `uint40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     */
    function toUint40(uint256 value) internal pure returns (uint40) {
        if (value > type(uint40).max) {
            revert SafeCastOverflowedUintDowncast(40, value);
        }
        return uint40(value);
    }

    /**
     * @dev Returns the downcasted uint32 from uint256, reverting on
     * overflow (when the input is greater than largest uint32).
     *
     * Counterpart to Solidity's `uint32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     */
    function toUint32(uint256 value) internal pure returns (uint32) {
        if (value > type(uint32).max) {
            revert SafeCastOverflowedUintDowncast(32, value);
        }
        return uint32(value);
    }

    /**
     * @dev Returns the downcasted uint24 from uint256, reverting on
     * overflow (when the input is greater than largest uint24).
     *
     * Counterpart to Solidity's `uint24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     */
    function toUint24(uint256 value) internal pure returns (uint24) {
        if (value > type(uint24).max) {
            revert SafeCastOverflowedUintDowncast(24, value);
        }
        return uint24(value);
    }

    /**
     * @dev Returns the downcasted uint16 from uint256, reverting on
     * overflow (when the input is greater than largest uint16).
     *
     * Counterpart to Solidity's `uint16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     */
    function toUint16(uint256 value) internal pure returns (uint16) {
        if (value > type(uint16).max) {
            revert SafeCastOverflowedUintDowncast(16, value);
        }
        return uint16(value);
    }

    /**
     * @dev Returns the downcasted uint8 from uint256, reverting on
     * overflow (when the input is greater than largest uint8).
     *
     * Counterpart to Solidity's `uint8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     */
    function toUint8(uint256 value) internal pure returns (uint8) {
        if (value > type(uint8).max) {
            revert SafeCastOverflowedUintDowncast(8, value);
        }
        return uint8(value);
    }

    /**
     * @dev Converts a signed int256 into an unsigned uint256.
     *
     * Requirements:
     *
     * - input must be greater than or equal to 0.
     */
    function toUint256(int256 value) internal pure returns (uint256) {
        if (value < 0) {
            revert SafeCastOverflowedIntToUint(value);
        }
        return uint256(value);
    }

    /**
     * @dev Returns the downcasted int248 from int256, reverting on
     * overflow (when the input is less than smallest int248 or
     * greater than largest int248).
     *
     * Counterpart to Solidity's `int248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     */
    function toInt248(int256 value) internal pure returns (int248 downcasted) {
        downcasted = int248(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(248, value);
        }
    }

    /**
     * @dev Returns the downcasted int240 from int256, reverting on
     * overflow (when the input is less than smallest int240 or
     * greater than largest int240).
     *
     * Counterpart to Solidity's `int240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     */
    function toInt240(int256 value) internal pure returns (int240 downcasted) {
        downcasted = int240(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(240, value);
        }
    }

    /**
     * @dev Returns the downcasted int232 from int256, reverting on
     * overflow (when the input is less than smallest int232 or
     * greater than largest int232).
     *
     * Counterpart to Solidity's `int232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     */
    function toInt232(int256 value) internal pure returns (int232 downcasted) {
        downcasted = int232(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(232, value);
        }
    }

    /**
     * @dev Returns the downcasted int224 from int256, reverting on
     * overflow (when the input is less than smallest int224 or
     * greater than largest int224).
     *
     * Counterpart to Solidity's `int224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     */
    function toInt224(int256 value) internal pure returns (int224 downcasted) {
        downcasted = int224(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(224, value);
        }
    }

    /**
     * @dev Returns the downcasted int216 from int256, reverting on
     * overflow (when the input is less than smallest int216 or
     * greater than largest int216).
     *
     * Counterpart to Solidity's `int216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     */
    function toInt216(int256 value) internal pure returns (int216 downcasted) {
        downcasted = int216(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(216, value);
        }
    }

    /**
     * @dev Returns the downcasted int208 from int256, reverting on
     * overflow (when the input is less than smallest int208 or
     * greater than largest int208).
     *
     * Counterpart to Solidity's `int208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     */
    function toInt208(int256 value) internal pure returns (int208 downcasted) {
        downcasted = int208(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(208, value);
        }
    }

    /**
     * @dev Returns the downcasted int200 from int256, reverting on
     * overflow (when the input is less than smallest int200 or
     * greater than largest int200).
     *
     * Counterpart to Solidity's `int200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     */
    function toInt200(int256 value) internal pure returns (int200 downcasted) {
        downcasted = int200(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(200, value);
        }
    }

    /**
     * @dev Returns the downcasted int192 from int256, reverting on
     * overflow (when the input is less than smallest int192 or
     * greater than largest int192).
     *
     * Counterpart to Solidity's `int192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     */
    function toInt192(int256 value) internal pure returns (int192 downcasted) {
        downcasted = int192(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(192, value);
        }
    }

    /**
     * @dev Returns the downcasted int184 from int256, reverting on
     * overflow (when the input is less than smallest int184 or
     * greater than largest int184).
     *
     * Counterpart to Solidity's `int184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     */
    function toInt184(int256 value) internal pure returns (int184 downcasted) {
        downcasted = int184(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(184, value);
        }
    }

    /**
     * @dev Returns the downcasted int176 from int256, reverting on
     * overflow (when the input is less than smallest int176 or
     * greater than largest int176).
     *
     * Counterpart to Solidity's `int176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     */
    function toInt176(int256 value) internal pure returns (int176 downcasted) {
        downcasted = int176(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(176, value);
        }
    }

    /**
     * @dev Returns the downcasted int168 from int256, reverting on
     * overflow (when the input is less than smallest int168 or
     * greater than largest int168).
     *
     * Counterpart to Solidity's `int168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     */
    function toInt168(int256 value) internal pure returns (int168 downcasted) {
        downcasted = int168(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(168, value);
        }
    }

    /**
     * @dev Returns the downcasted int160 from int256, reverting on
     * overflow (when the input is less than smallest int160 or
     * greater than largest int160).
     *
     * Counterpart to Solidity's `int160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     */
    function toInt160(int256 value) internal pure returns (int160 downcasted) {
        downcasted = int160(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(160, value);
        }
    }

    /**
     * @dev Returns the downcasted int152 from int256, reverting on
     * overflow (when the input is less than smallest int152 or
     * greater than largest int152).
     *
     * Counterpart to Solidity's `int152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     */
    function toInt152(int256 value) internal pure returns (int152 downcasted) {
        downcasted = int152(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(152, value);
        }
    }

    /**
     * @dev Returns the downcasted int144 from int256, reverting on
     * overflow (when the input is less than smallest int144 or
     * greater than largest int144).
     *
     * Counterpart to Solidity's `int144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     */
    function toInt144(int256 value) internal pure returns (int144 downcasted) {
        downcasted = int144(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(144, value);
        }
    }

    /**
     * @dev Returns the downcasted int136 from int256, reverting on
     * overflow (when the input is less than smallest int136 or
     * greater than largest int136).
     *
     * Counterpart to Solidity's `int136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     */
    function toInt136(int256 value) internal pure returns (int136 downcasted) {
        downcasted = int136(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(136, value);
        }
    }

    /**
     * @dev Returns the downcasted int128 from int256, reverting on
     * overflow (when the input is less than smallest int128 or
     * greater than largest int128).
     *
     * Counterpart to Solidity's `int128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     */
    function toInt128(int256 value) internal pure returns (int128 downcasted) {
        downcasted = int128(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(128, value);
        }
    }

    /**
     * @dev Returns the downcasted int120 from int256, reverting on
     * overflow (when the input is less than smallest int120 or
     * greater than largest int120).
     *
     * Counterpart to Solidity's `int120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     */
    function toInt120(int256 value) internal pure returns (int120 downcasted) {
        downcasted = int120(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(120, value);
        }
    }

    /**
     * @dev Returns the downcasted int112 from int256, reverting on
     * overflow (when the input is less than smallest int112 or
     * greater than largest int112).
     *
     * Counterpart to Solidity's `int112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     */
    function toInt112(int256 value) internal pure returns (int112 downcasted) {
        downcasted = int112(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(112, value);
        }
    }

    /**
     * @dev Returns the downcasted int104 from int256, reverting on
     * overflow (when the input is less than smallest int104 or
     * greater than largest int104).
     *
     * Counterpart to Solidity's `int104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     */
    function toInt104(int256 value) internal pure returns (int104 downcasted) {
        downcasted = int104(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(104, value);
        }
    }

    /**
     * @dev Returns the downcasted int96 from int256, reverting on
     * overflow (when the input is less than smallest int96 or
     * greater than largest int96).
     *
     * Counterpart to Solidity's `int96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     */
    function toInt96(int256 value) internal pure returns (int96 downcasted) {
        downcasted = int96(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(96, value);
        }
    }

    /**
     * @dev Returns the downcasted int88 from int256, reverting on
     * overflow (when the input is less than smallest int88 or
     * greater than largest int88).
     *
     * Counterpart to Solidity's `int88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     */
    function toInt88(int256 value) internal pure returns (int88 downcasted) {
        downcasted = int88(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(88, value);
        }
    }

    /**
     * @dev Returns the downcasted int80 from int256, reverting on
     * overflow (when the input is less than smallest int80 or
     * greater than largest int80).
     *
     * Counterpart to Solidity's `int80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     */
    function toInt80(int256 value) internal pure returns (int80 downcasted) {
        downcasted = int80(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(80, value);
        }
    }

    /**
     * @dev Returns the downcasted int72 from int256, reverting on
     * overflow (when the input is less than smallest int72 or
     * greater than largest int72).
     *
     * Counterpart to Solidity's `int72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     */
    function toInt72(int256 value) internal pure returns (int72 downcasted) {
        downcasted = int72(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(72, value);
        }
    }

    /**
     * @dev Returns the downcasted int64 from int256, reverting on
     * overflow (when the input is less than smallest int64 or
     * greater than largest int64).
     *
     * Counterpart to Solidity's `int64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     */
    function toInt64(int256 value) internal pure returns (int64 downcasted) {
        downcasted = int64(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(64, value);
        }
    }

    /**
     * @dev Returns the downcasted int56 from int256, reverting on
     * overflow (when the input is less than smallest int56 or
     * greater than largest int56).
     *
     * Counterpart to Solidity's `int56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     */
    function toInt56(int256 value) internal pure returns (int56 downcasted) {
        downcasted = int56(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(56, value);
        }
    }

    /**
     * @dev Returns the downcasted int48 from int256, reverting on
     * overflow (when the input is less than smallest int48 or
     * greater than largest int48).
     *
     * Counterpart to Solidity's `int48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     */
    function toInt48(int256 value) internal pure returns (int48 downcasted) {
        downcasted = int48(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(48, value);
        }
    }

    /**
     * @dev Returns the downcasted int40 from int256, reverting on
     * overflow (when the input is less than smallest int40 or
     * greater than largest int40).
     *
     * Counterpart to Solidity's `int40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     */
    function toInt40(int256 value) internal pure returns (int40 downcasted) {
        downcasted = int40(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(40, value);
        }
    }

    /**
     * @dev Returns the downcasted int32 from int256, reverting on
     * overflow (when the input is less than smallest int32 or
     * greater than largest int32).
     *
     * Counterpart to Solidity's `int32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     */
    function toInt32(int256 value) internal pure returns (int32 downcasted) {
        downcasted = int32(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(32, value);
        }
    }

    /**
     * @dev Returns the downcasted int24 from int256, reverting on
     * overflow (when the input is less than smallest int24 or
     * greater than largest int24).
     *
     * Counterpart to Solidity's `int24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     */
    function toInt24(int256 value) internal pure returns (int24 downcasted) {
        downcasted = int24(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(24, value);
        }
    }

    /**
     * @dev Returns the downcasted int16 from int256, reverting on
     * overflow (when the input is less than smallest int16 or
     * greater than largest int16).
     *
     * Counterpart to Solidity's `int16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     */
    function toInt16(int256 value) internal pure returns (int16 downcasted) {
        downcasted = int16(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(16, value);
        }
    }

    /**
     * @dev Returns the downcasted int8 from int256, reverting on
     * overflow (when the input is less than smallest int8 or
     * greater than largest int8).
     *
     * Counterpart to Solidity's `int8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     */
    function toInt8(int256 value) internal pure returns (int8 downcasted) {
        downcasted = int8(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(8, value);
        }
    }

    /**
     * @dev Converts an unsigned uint256 into a signed int256.
     *
     * Requirements:
     *
     * - input must be less than or equal to maxInt256.
     */
    function toInt256(uint256 value) internal pure returns (int256) {
        // Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
        if (value > uint256(type(int256).max)) {
            revert SafeCastOverflowedUintToInt(value);
        }
        return int256(value);
    }

    /**
     * @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))
        }
    }
}

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.0;

import {IERC721Metadata} from "@openzeppelin/contracts/token/ERC721/extensions/IERC721Metadata.sol";

import {BookId} from "../libraries/BookId.sol";
import {Currency} from "../libraries/Currency.sol";
import {OrderId} from "../libraries/OrderId.sol";
import {Tick} from "../libraries/Tick.sol";
import {FeePolicy} from "../libraries/FeePolicy.sol";
import {IERC721Permit} from "./IERC721Permit.sol";
import {IHooks} from "./IHooks.sol";

/**
 * @title IBookManager
 * @notice The interface for the BookManager contract
 */
interface IBookManager is IERC721Metadata, IERC721Permit {
    error InvalidUnitSize();
    error InvalidFeePolicy();
    error InvalidProvider(address provider);
    error LockedBy(address locker, address hook);
    error CurrencyNotSettled();

    /**
     * @notice Event emitted when a new book is opened
     * @param id The book id
     * @param base The base currency
     * @param quote The quote currency
     * @param unitSize The unit size of the book
     * @param makerPolicy The maker fee policy
     * @param takerPolicy The taker fee policy
     * @param hooks The hooks contract
     */
    event Open(
        BookId indexed id,
        Currency indexed base,
        Currency indexed quote,
        uint64 unitSize,
        FeePolicy makerPolicy,
        FeePolicy takerPolicy,
        IHooks hooks
    );

    /**
     * @notice Event emitted when a new order is made
     * @param bookId The book id
     * @param user The user address
     * @param tick The order tick
     * @param orderIndex The order index
     * @param unit The order unit
     * @param provider The provider address
     */
    event Make(
        BookId indexed bookId, address indexed user, Tick tick, uint256 orderIndex, uint64 unit, address provider
    );

    /**
     * @notice Event emitted when an order is taken
     * @param bookId The book id
     * @param user The user address
     * @param tick The order tick
     * @param unit The order unit
     */
    event Take(BookId indexed bookId, address indexed user, Tick tick, uint64 unit);

    /**
     * @notice Event emitted when an order is canceled
     * @param orderId The order id
     * @param unit The canceled unit
     */
    event Cancel(OrderId indexed orderId, uint64 unit);

    /**
     * @notice Event emitted when an order is claimed
     * @param orderId The order id
     * @param unit The claimed unit
     */
    event Claim(OrderId indexed orderId, uint64 unit);

    /**
     * @notice Event emitted when a provider is whitelisted
     * @param provider The provider address
     */
    event Whitelist(address indexed provider);

    /**
     * @notice Event emitted when a provider is delisted
     * @param provider The provider address
     */
    event Delist(address indexed provider);

    /**
     * @notice Event emitted when a provider collects fees
     * @param provider The provider address
     * @param recipient The recipient address
     * @param currency The currency
     * @param amount The collected amount
     */
    event Collect(address indexed provider, address indexed recipient, Currency indexed currency, uint256 amount);

    /**
     * @notice Event emitted when new default provider is set
     * @param newDefaultProvider The new default provider address
     */
    event SetDefaultProvider(address indexed newDefaultProvider);

    /**
     * @notice This structure represents a unique identifier for a book in the BookManager.
     * @param base The base currency of the book
     * @param unitSize The unit size of the book
     * @param quote The quote currency of the book
     * @param makerPolicy The maker fee policy of the book
     * @param hooks The hooks contract of the book
     * @param takerPolicy The taker fee policy of the book
     */
    struct BookKey {
        Currency base;
        uint64 unitSize;
        Currency quote;
        FeePolicy makerPolicy;
        IHooks hooks;
        FeePolicy takerPolicy;
    }

    /**
     * @notice Returns the base URI
     * @return The base URI
     */
    function baseURI() external view returns (string memory);

    /**
     * @notice Returns the contract URI
     * @return The contract URI
     */
    function contractURI() external view returns (string memory);

    /**
     * @notice Returns the default provider
     * @return The default provider
     */
    function defaultProvider() external view returns (address);

    /**
     * @notice Returns the total reserves of a given currency
     * @param currency The currency in question
     * @return The total reserves amount
     */
    function reservesOf(Currency currency) external view returns (uint256);

    /**
     * @notice Checks if a provider is whitelisted
     * @param provider The address of the provider
     * @return True if the provider is whitelisted, false otherwise
     */
    function isWhitelisted(address provider) external view returns (bool);

    /**
     * @notice Verifies if an owner has authorized a spender for a token
     * @param owner The address of the token owner
     * @param spender The address of the spender
     * @param tokenId The token ID
     */
    function checkAuthorized(address owner, address spender, uint256 tokenId) external view;

    /**
     * @notice Calculates the amount owed to a provider in a given currency
     * @param provider The provider's address
     * @param currency The currency in question
     * @return The owed amount
     */
    function tokenOwed(address provider, Currency currency) external view returns (uint256);

    /**
     * @notice Calculates the currency balance changes for a given locker
     * @param locker The address of the locker
     * @param currency The currency in question
     * @return The net change in currency balance
     */
    function getCurrencyDelta(address locker, Currency currency) external view returns (int256);

    /**
     * @notice Retrieves the book key for a given book ID
     * @param id The book ID
     * @return The book key
     */
    function getBookKey(BookId id) external view returns (BookKey memory);

    /**
     * @notice This structure represents a current status for an order in the BookManager.
     * @param provider The provider of the order
     * @param open The open unit of the order
     * @param claimable The claimable unit of the order
     */
    struct OrderInfo {
        address provider;
        uint64 open;
        uint64 claimable;
    }

    /**
     * @notice Provides information about an order
     * @param id The order ID
     * @return Order information including provider, open status, and claimable unit
     */
    function getOrder(OrderId id) external view returns (OrderInfo memory);

    /**
     * @notice Retrieves the locker and caller addresses for a given lock
     * @param i The index of the lock
     * @return locker The locker's address
     * @return lockCaller The caller's address
     */
    function getLock(uint256 i) external view returns (address locker, address lockCaller);

    /**
     * @notice Provides the lock data
     * @return The lock data including necessary numeric values
     */
    function getLockData() external view returns (uint128, uint128);

    /**
     * @notice Returns the depth of a given book ID and tick
     * @param id The book ID
     * @param tick The tick
     * @return The depth of the tick
     */
    function getDepth(BookId id, Tick tick) external view returns (uint64);

    /**
     * @notice Retrieves the highest tick for a given book ID
     * @param id The book ID
     * @return tick The highest tick
     */
    function getHighest(BookId id) external view returns (Tick tick);

    /**
     * @notice Finds the maximum tick less than a specified tick in a book
     * @dev Returns `Tick.wrap(type(int24).min)` if the specified tick is the lowest
     * @param id The book ID
     * @param tick The specified tick
     * @return The next lower tick
     */
    function maxLessThan(BookId id, Tick tick) external view returns (Tick);

    /**
     * @notice Checks if a book is opened
     * @param id The book ID
     * @return True if the book is opened, false otherwise
     */
    function isOpened(BookId id) external view returns (bool);

    /**
     * @notice Checks if a book is empty
     * @param id The book ID
     * @return True if the book is empty, false otherwise
     */
    function isEmpty(BookId id) external view returns (bool);

    /**
     * @notice Encodes a BookKey into a BookId
     * @param key The BookKey to encode
     * @return The encoded BookId
     */
    function encodeBookKey(BookKey calldata key) external pure returns (BookId);

    /**
     * @notice Loads a value from a specific storage slot
     * @param slot The storage slot
     * @return The value in the slot
     */
    function load(bytes32 slot) external view returns (bytes32);

    /**
     * @notice Loads a sequence of values starting from a specific slot
     * @param startSlot The starting slot
     * @param nSlot The number of slots to load
     * @return The sequence of values
     */
    function load(bytes32 startSlot, uint256 nSlot) external view returns (bytes memory);

    /**
     * @notice Opens a new book
     * @param key The book key
     * @param hookData The hook data
     */
    function open(BookKey calldata key, bytes calldata hookData) external;

    /**
     * @notice Locks a book manager function
     * @param locker The locker address
     * @param data The lock data
     * @return The lock return data
     */
    function lock(address locker, bytes calldata data) external returns (bytes memory);

    /**
     * @notice This structure represents the parameters for making an order.
     * @param key The book key for the order
     * @param tick The tick for the order
     * @param unit The unit for the order. Times key.unitSize to get actual bid amount.
     * @param provider The provider for the order. The limit order service provider address to collect fees.
     */
    struct MakeParams {
        BookKey key;
        Tick tick;
        uint64 unit;
        address provider;
    }

    /**
     * @notice Make a limit order
     * @param params The order parameters
     * @param hookData The hook data
     * @return id The order id. Returns 0 if the order is not settled
     * @return quoteAmount The amount of quote currency to be paid
     */
    function make(MakeParams calldata params, bytes calldata hookData)
        external
        returns (OrderId id, uint256 quoteAmount);

    /**
     * @notice This structure represents the parameters for taking orders in the specified tick.
     * @param key The book key for the order
     * @param tick The tick for the order
     * @param maxUnit The max unit to take
     */
    struct TakeParams {
        BookKey key;
        Tick tick;
        uint64 maxUnit;
    }

    /**
     * @notice Take a limit order at specific tick
     * @param params The order parameters
     * @param hookData The hook data
     * @return quoteAmount The amount of quote currency to be received
     * @return baseAmount The amount of base currency to be paid
     */
    function take(TakeParams calldata params, bytes calldata hookData)
        external
        returns (uint256 quoteAmount, uint256 baseAmount);

    /**
     * @notice This structure represents the parameters for canceling an order.
     * @param id The order id for the order
     * @param toUnit The remaining open unit for the order after cancellation. Must not exceed the current open unit.
     */
    struct CancelParams {
        OrderId id;
        uint64 toUnit;
    }

    /**
     * @notice Cancel a limit order
     * @param params The order parameters
     * @param hookData The hook data
     * @return canceledAmount The amount of quote currency canceled
     */
    function cancel(CancelParams calldata params, bytes calldata hookData) external returns (uint256 canceledAmount);

    /**
     * @notice Claims an order
     * @param id The order ID
     * @param hookData The hook data
     * @return claimedAmount The amount claimed
     */
    function claim(OrderId id, bytes calldata hookData) external returns (uint256 claimedAmount);

    /**
     * @notice Collects fees from a provider
     * @param recipient The recipient address
     * @param currency The currency
     * @return The collected amount
     */
    function collect(address recipient, Currency currency) external returns (uint256);

    /**
     * @notice Withdraws a currency
     * @param currency The currency
     * @param to The recipient address
     * @param amount The amount
     */
    function withdraw(Currency currency, address to, uint256 amount) external;

    /**
     * @notice Settles a currency
     * @param currency The currency
     * @return The settled amount
     */
    function settle(Currency currency) external payable returns (uint256);

    /**
     * @notice Whitelists a provider
     * @param provider The provider address
     */
    function whitelist(address provider) external;

    /**
     * @notice Delists a provider
     * @param provider The provider address
     */
    function delist(address provider) external;

    /**
     * @notice Sets the default provider
     * @param newDefaultProvider The new default provider address
     */
    function setDefaultProvider(address newDefaultProvider) external;
}

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.0;

import {IERC721} from "@openzeppelin/contracts/token/ERC721/IERC721.sol";

/**
 * @title IERC721Permit
 * @notice An interface for the ERC721 permit extension
 */
interface IERC721Permit is IERC721 {
    error InvalidSignature();
    error PermitExpired();

    /**
     * @notice The EIP-712 typehash for the permit struct used by the contract
     */
    function PERMIT_TYPEHASH() external pure returns (bytes32);

    /**
     * @notice The EIP-712 domain separator for this contract
     */
    function DOMAIN_SEPARATOR() external view returns (bytes32);

    /**
     * @notice Approve the spender to transfer the given tokenId
     * @param spender The address to approve
     * @param tokenId The tokenId to approve
     * @param deadline The deadline for the signature
     * @param v The recovery id of the signature
     * @param r The r value of the signature
     * @param s The s value of the signature
     */
    function permit(address spender, uint256 tokenId, uint256 deadline, uint8 v, bytes32 r, bytes32 s) external;

    /**
     * @notice Get the current nonce for a token
     * @param tokenId The tokenId to get the nonce for
     * @return The current nonce
     */
    function nonces(uint256 tokenId) external view returns (uint256);
}

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.20;

import {IBookManager} from "./IBookManager.sol";
import {OrderId} from "../libraries/OrderId.sol";

/**
 * @title IHooks
 * @notice Interface for the hooks contract
 */
interface IHooks {
    /**
     * @notice Hook called before opening a new book
     * @param sender The sender of the open transaction
     * @param key The key of the book being opened
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function beforeOpen(address sender, IBookManager.BookKey calldata key, bytes calldata hookData)
        external
        returns (bytes4);

    /**
     * @notice Hook called after opening a new book
     * @param sender The sender of the open transaction
     * @param key The key of the book being opened
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function afterOpen(address sender, IBookManager.BookKey calldata key, bytes calldata hookData)
        external
        returns (bytes4);

    /**
     * @notice Hook called before making a new order
     * @param sender The sender of the make transaction
     * @param params The parameters of the make transaction
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function beforeMake(address sender, IBookManager.MakeParams calldata params, bytes calldata hookData)
        external
        returns (bytes4);

    /**
     * @notice Hook called after making a new order
     * @param sender The sender of the make transaction
     * @param params The parameters of the make transaction
     * @param orderId The id of the order that was made
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function afterMake(
        address sender,
        IBookManager.MakeParams calldata params,
        OrderId orderId,
        bytes calldata hookData
    ) external returns (bytes4);

    /**
     * @notice Hook called before taking an order
     * @param sender The sender of the take transaction
     * @param params The parameters of the take transaction
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function beforeTake(address sender, IBookManager.TakeParams calldata params, bytes calldata hookData)
        external
        returns (bytes4);

    /**
     * @notice Hook called after taking an order
     * @param sender The sender of the take transaction
     * @param params The parameters of the take transaction
     * @param takenUnit The unit that was taken
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function afterTake(
        address sender,
        IBookManager.TakeParams calldata params,
        uint64 takenUnit,
        bytes calldata hookData
    ) external returns (bytes4);

    /**
     * @notice Hook called before canceling an order
     * @param sender The sender of the cancel transaction
     * @param params The parameters of the cancel transaction
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function beforeCancel(address sender, IBookManager.CancelParams calldata params, bytes calldata hookData)
        external
        returns (bytes4);

    /**
     * @notice Hook called after canceling an order
     * @param sender The sender of the cancel transaction
     * @param params The parameters of the cancel transaction
     * @param canceledUnit The unit that was canceled
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function afterCancel(
        address sender,
        IBookManager.CancelParams calldata params,
        uint64 canceledUnit,
        bytes calldata hookData
    ) external returns (bytes4);

    /**
     * @notice Hook called before claiming an order
     * @param sender The sender of the claim transaction
     * @param orderId The id of the order being claimed
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function beforeClaim(address sender, OrderId orderId, bytes calldata hookData) external returns (bytes4);

    /**
     * @notice Hook called after claiming an order
     * @param sender The sender of the claim transaction
     * @param orderId The id of the order being claimed
     * @param claimedUnit The unit that was claimed
     * @param hookData The data passed to the hook
     * @return Returns the function selector if the hook is successful
     */
    function afterClaim(address sender, OrderId orderId, uint64 claimedUnit, bytes calldata hookData)
        external
        returns (bytes4);
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.20;

import {IBookManager} from "../interfaces/IBookManager.sol";

type BookId is uint192;

library BookIdLibrary {
    function toId(IBookManager.BookKey memory bookKey) internal pure returns (BookId id) {
        bytes32 hash = keccak256(abi.encode(bookKey));
        assembly {
            id := and(hash, 0xffffffffffffffffffffffffffffffffffffffffffffffff)
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.20;

import {IERC20} from "@openzeppelin/contracts/token/ERC20/IERC20.sol";

type Currency is address;

/// @title CurrencyLibrary
/// @dev This library allows for transferring and holding native tokens and ERC20 tokens
library CurrencyLibrary {
    using CurrencyLibrary for Currency;

    /// @notice Thrown when a native transfer fails
    error NativeTransferFailed();

    /// @notice Thrown when an ERC20 transfer fails
    error ERC20TransferFailed();

    Currency public constant NATIVE = Currency.wrap(address(0));

    function transfer(Currency currency, address to, uint256 amount) internal {
        // implementation from
        // https://github.com/transmissions11/solmate/blob/e8f96f25d48fe702117ce76c79228ca4f20206cb/src/utils/SafeTransferLib.sol

        bool success;
        if (currency.isNative()) {
            assembly {
                // Transfer the ETH and store if it succeeded or not.
                success := call(gas(), to, amount, 0, 0, 0, 0)
            }

            if (!success) revert NativeTransferFailed();
        } else {
            assembly {
                // Get a pointer to some free memory.
                let freeMemoryPointer := mload(0x40)

                // Write the abi-encoded calldata into memory, beginning with the function selector.
                mstore(freeMemoryPointer, 0xa9059cbb00000000000000000000000000000000000000000000000000000000)
                mstore(add(freeMemoryPointer, 4), and(to, 0xffffffffffffffffffffffffffffffffffffffff)) // Append and mask the "to" argument.
                mstore(add(freeMemoryPointer, 36), amount) // Append the "amount" argument. Masking not required as it's a full 32 byte type.

                success :=
                    and(
                        // Set success to whether the call reverted, if not we check it either
                        // returned exactly 1 (can't just be non-zero data), or had no return data.
                        or(and(eq(mload(0), 1), gt(returndatasize(), 31)), iszero(returndatasize())),
                        // We use 68 because the length of our calldata totals up like so: 4 + 32 * 2.
                        // We use 0 and 32 to copy up to 32 bytes of return data into the scratch space.
                        // Counterintuitively, this call must be positioned second to the or() call in the
                        // surrounding and() call or else returndatasize() will be zero during the computation.
                        call(gas(), currency, 0, freeMemoryPointer, 68, 0, 32)
                    )
            }

            if (!success) revert ERC20TransferFailed();
        }
    }

    function balanceOfSelf(Currency currency) internal view returns (uint256) {
        if (currency.isNative()) return address(this).balance;
        else return IERC20(Currency.unwrap(currency)).balanceOf(address(this));
    }

    function equals(Currency currency, Currency other) internal pure returns (bool) {
        return Currency.unwrap(currency) == Currency.unwrap(other);
    }

    function isNative(Currency currency) internal pure returns (bool) {
        return Currency.unwrap(currency) == Currency.unwrap(NATIVE);
    }

    function toId(Currency currency) internal pure returns (uint256) {
        return uint160(Currency.unwrap(currency));
    }

    function fromId(uint256 id) internal pure returns (Currency) {
        return Currency.wrap(address(uint160(id)));
    }
}

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.0;

library DirtyUint64 {
    error DirtyUint64Error(uint256 errorCode);

    uint256 private constant _OVERFLOW_ERROR = 0;
    uint256 private constant _UNDERFLOW_ERROR = 1;

    function toDirtyUnsafe(uint64 cleanUint) internal pure returns (uint64 dirtyUint) {
        assembly {
            dirtyUint := add(cleanUint, 1)
        }
    }

    function toDirty(uint64 cleanUint) internal pure returns (uint64 dirtyUint) {
        assembly {
            dirtyUint := add(cleanUint, 1)
        }
        if (dirtyUint == 0) {
            revert DirtyUint64Error(_OVERFLOW_ERROR);
        }
    }

    function toClean(uint64 dirtyUint) internal pure returns (uint64 cleanUint) {
        assembly {
            cleanUint := sub(dirtyUint, gt(dirtyUint, 0))
        }
    }

    function addClean(uint64 current, uint64 cleanUint) internal pure returns (uint64) {
        assembly {
            current := add(add(current, iszero(current)), cleanUint)
        }
        if (current < cleanUint) {
            revert DirtyUint64Error(_OVERFLOW_ERROR);
        }
        return current;
    }

    function addDirty(uint64 current, uint64 dirtyUint) internal pure returns (uint64) {
        assembly {
            current := sub(add(add(current, iszero(current)), add(dirtyUint, iszero(dirtyUint))), 1)
        }
        if (current < dirtyUint) {
            revert DirtyUint64Error(_OVERFLOW_ERROR);
        }
        return current;
    }

    function subClean(uint64 current, uint64 cleanUint) internal pure returns (uint64 ret) {
        assembly {
            current := add(current, iszero(current))
            ret := sub(current, cleanUint)
        }
        if (current < ret || ret == 0) {
            revert DirtyUint64Error(_UNDERFLOW_ERROR);
        }
    }

    function subDirty(uint64 current, uint64 dirtyUint) internal pure returns (uint64 ret) {
        assembly {
            current := add(current, iszero(current))
            ret := sub(add(current, 1), add(dirtyUint, iszero(dirtyUint)))
        }
        if (current < ret || ret == 0) {
            revert DirtyUint64Error(_UNDERFLOW_ERROR);
        }
    }

    function sumPackedUnsafe(uint256 packed, uint256 from, uint256 to) internal pure returns (uint64 ret) {
        packed = packed >> (from << 6);
        unchecked {
            for (uint256 i = from; i < to; ++i) {
                assembly {
                    let element := and(packed, 0xffffffffffffffff)
                    ret := add(ret, add(element, iszero(element)))
                    packed := shr(64, packed)
                }
            }
        }
        assembly {
            ret := sub(ret, sub(to, from))
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.20;

import {Math} from "./Math.sol";

type FeePolicy is uint24;

library FeePolicyLibrary {
    uint256 internal constant RATE_PRECISION = 10 ** 6;
    int256 internal constant MAX_FEE_RATE = 500000;
    int256 internal constant MIN_FEE_RATE = -500000;

    uint256 internal constant RATE_MASK = 0x7fffff; // 23 bits

    error InvalidFeePolicy();

    function encode(bool usesQuote_, int24 rate_) internal pure returns (FeePolicy feePolicy) {
        if (rate_ > MAX_FEE_RATE || rate_ < MIN_FEE_RATE) {
            revert InvalidFeePolicy();
        }

        uint256 mask = usesQuote_ ? 1 << 23 : 0;
        assembly {
            feePolicy := or(mask, add(and(rate_, 0xffffff), MAX_FEE_RATE))
        }
    }

    function isValid(FeePolicy self) internal pure returns (bool) {
        int24 r = rate(self);

        return !(r > MAX_FEE_RATE || r < MIN_FEE_RATE);
    }

    function usesQuote(FeePolicy self) internal pure returns (bool f) {
        assembly {
            f := shr(23, self)
        }
    }

    function rate(FeePolicy self) internal pure returns (int24 r) {
        assembly {
            r := sub(and(self, RATE_MASK), MAX_FEE_RATE)
        }
    }

    function calculateFee(FeePolicy self, uint256 amount, bool reverseRounding) internal pure returns (int256 fee) {
        int24 r = rate(self);

        bool positive = r > 0;
        uint256 absRate;
        unchecked {
            absRate = uint256(uint24(positive ? r : -r));
        }
        // @dev absFee must be less than type(int256).max
        uint256 absFee = Math.divide(amount * absRate, RATE_PRECISION, reverseRounding ? !positive : positive);
        fee = positive ? int256(absFee) : -int256(absFee);
    }

    function calculateOriginalAmount(FeePolicy self, uint256 amount, bool reverseFee)
        internal
        pure
        returns (uint256 originalAmount)
    {
        int24 r = rate(self);

        uint256 divider;
        assembly {
            if reverseFee { r := sub(0, r) }
            divider := add(RATE_PRECISION, r)
        }
        originalAmount = Math.divide(amount * RATE_PRECISION, divider, reverseFee);
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.0;

library Math {
    function divide(uint256 a, uint256 b, bool roundingUp) internal pure returns (uint256 ret) {
        // In the OrderBook contract code, b is never zero.
        assembly {
            ret := add(div(a, b), and(gt(mod(a, b), 0), roundingUp))
        }
    }

    /// @dev Returns `ln(x)`, denominated in `WAD`.
    /// Credit to Remco Bloemen under MIT license: https://2π.com/22/exp-ln
    function lnWad(int256 x) internal pure returns (int256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // We want to convert `x` from `10**18` fixed point to `2**96` fixed point.
            // We do this by multiplying by `2**96 / 10**18`. But since
            // `ln(x * C) = ln(x) + ln(C)`, we can simply do nothing here
            // and add `ln(2**96 / 10**18)` at the end.

            // Compute `k = log2(x) - 96`, `r = 159 - k = 255 - log2(x) = 255 ^ log2(x)`.
            r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            // We place the check here for more optimal stack operations.
            if iszero(sgt(x, 0)) {
                mstore(0x00, 0x1615e638) // `LnWadUndefined()`.
                revert(0x1c, 0x04)
            }
            // forgefmt: disable-next-item
            r := xor(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
                0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff))

            // Reduce range of x to (1, 2) * 2**96
            // ln(2^k * x) = k * ln(2) + ln(x)
            x := shr(159, shl(r, x))

            // Evaluate using a (8, 8)-term rational approximation.
            // `p` is made monic, we will multiply by a scale factor later.
            // forgefmt: disable-next-item
            let p := sub( // This heavily nested expression is to avoid stack-too-deep for via-ir.
                sar(96, mul(add(43456485725739037958740375743393,
                    sar(96, mul(add(24828157081833163892658089445524,
                        sar(96, mul(add(3273285459638523848632254066296,
                            x), x))), x))), x)), 11111509109440967052023855526967)
            p := sub(sar(96, mul(p, x)), 45023709667254063763336534515857)
            p := sub(sar(96, mul(p, x)), 14706773417378608786704636184526)
            p := sub(mul(p, x), shl(96, 795164235651350426258249787498))
            // We leave `p` in `2**192` basis so we don't need to scale it back up for the division.

            // `q` is monic by convention.
            let q := add(5573035233440673466300451813936, x)
            q := add(71694874799317883764090561454958, sar(96, mul(x, q)))
            q := add(283447036172924575727196451306956, sar(96, mul(x, q)))
            q := add(401686690394027663651624208769553, sar(96, mul(x, q)))
            q := add(204048457590392012362485061816622, sar(96, mul(x, q)))
            q := add(31853899698501571402653359427138, sar(96, mul(x, q)))
            q := add(909429971244387300277376558375, sar(96, mul(x, q)))

            // `p / q` is in the range `(0, 0.125) * 2**96`.

            // Finalization, we need to:
            // - Multiply by the scale factor `s = 5.549…`.
            // - Add `ln(2**96 / 10**18)`.
            // - Add `k * ln(2)`.
            // - Multiply by `10**18 / 2**96 = 5**18 >> 78`.

            // The q polynomial is known not to have zeros in the domain.
            // No scaling required because p is already `2**96` too large.
            p := sdiv(p, q)
            // Multiply by the scaling factor: `s * 5**18 * 2**96`, base is now `5**18 * 2**192`.
            p := mul(1677202110996718588342820967067443963516166, p)
            // Add `ln(2) * k * 5**18 * 2**192`.
            // forgefmt: disable-next-item
            p := add(mul(16597577552685614221487285958193947469193820559219878177908093499208371, sub(159, r)), p)
            // Base conversion: mul `2**96 / (5**18 * 2**192)`.
            r := sdiv(p, 302231454903657293676544000000000000000000)
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.0;

import {Tick} from "./Tick.sol";
import {BookId} from "./BookId.sol";

type OrderId is uint256;

library OrderIdLibrary {
    /**
     * @dev Encode the order id.
     * @param bookId The book id.
     * @param tick The tick.
     * @param index The index.
     * @return id The order id.
     */
    function encode(BookId bookId, Tick tick, uint40 index) internal pure returns (OrderId id) {
        // @dev If we just use tick at the assembly code, the code will convert tick into bytes32.
        //      e.g. When index == -2, the shifted value( shl(40, tick) ) will be
        //      0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000 instead of 0xfffffffe0000000000
        //      Therefore, we have to safely cast tick into uint256 first.
        uint256 _tick = uint256(uint24(Tick.unwrap(tick)));
        assembly {
            id := add(index, add(shl(40, _tick), shl(64, bookId)))
        }
    }

    function decode(OrderId id) internal pure returns (BookId bookId, Tick tick, uint40 index) {
        assembly {
            bookId := shr(64, id)
            tick := and(shr(40, id), 0xffffff)
            index := and(id, 0xffffffffff)
        }
    }

    function getBookId(OrderId id) internal pure returns (BookId bookId) {
        assembly {
            bookId := shr(64, id)
        }
    }

    function getTick(OrderId id) internal pure returns (Tick tick) {
        assembly {
            tick := and(shr(40, id), 0xffffff)
        }
    }

    function getIndex(OrderId id) internal pure returns (uint40 index) {
        assembly {
            index := and(id, 0xffffffffff)
        }
    }
}

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.0;

library PackedUint256 {
    error PackedUint256Error(uint256 errorCode);

    uint256 private constant _UINT8_INDEX_ERROR = 0;
    uint256 private constant _UINT16_INDEX_ERROR = 1;
    uint256 private constant _UINT32_INDEX_ERROR = 2;
    uint256 private constant _UINT64_INDEX_ERROR = 3;

    uint256 private constant _MAX_UINT64 = type(uint64).max;
    uint256 private constant _MAX_UINT32 = type(uint32).max;
    uint256 private constant _MAX_UINT16 = type(uint16).max;
    uint256 private constant _MAX_UINT8 = type(uint8).max;

    function get8Unsafe(uint256 packed, uint256 index) internal pure returns (uint8 ret) {
        assembly {
            ret := and(shr(shl(3, index), packed), 0xff)
        }
    }

    function get8(uint256 packed, uint256 index) internal pure returns (uint8 ret) {
        if (index > 31) {
            revert PackedUint256Error(_UINT8_INDEX_ERROR);
        }
        assembly {
            ret := and(shr(shl(3, index), packed), 0xff)
        }
    }

    function get16Unsafe(uint256 packed, uint256 index) internal pure returns (uint16 ret) {
        assembly {
            ret := and(shr(shl(4, index), packed), 0xffff)
        }
    }

    function get16(uint256 packed, uint256 index) internal pure returns (uint16 ret) {
        if (index > 15) {
            revert PackedUint256Error(_UINT16_INDEX_ERROR);
        }
        assembly {
            ret := and(shr(shl(4, index), packed), 0xffff)
        }
    }

    function get32Unsafe(uint256 packed, uint256 index) internal pure returns (uint32 ret) {
        assembly {
            ret := and(shr(shl(5, index), packed), 0xffffffff)
        }
    }

    function get32(uint256 packed, uint256 index) internal pure returns (uint32 ret) {
        if (index > 7) {
            revert PackedUint256Error(_UINT32_INDEX_ERROR);
        }
        assembly {
            ret := and(shr(shl(5, index), packed), 0xffffffff)
        }
    }

    function get64Unsafe(uint256 packed, uint256 index) internal pure returns (uint64 ret) {
        assembly {
            ret := and(shr(shl(6, index), packed), 0xffffffffffffffff)
        }
    }

    function get64(uint256 packed, uint256 index) internal pure returns (uint64 ret) {
        if (index > 3) {
            revert PackedUint256Error(_UINT64_INDEX_ERROR);
        }
        assembly {
            ret := and(shr(shl(6, index), packed), 0xffffffffffffffff)
        }
    }

    function add8Unsafe(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        assembly {
            ret := add(packed, shl(shl(3, index), and(value, 0xff)))
        }
    }

    function add8(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        if (index > 31) {
            revert PackedUint256Error(_UINT8_INDEX_ERROR);
        }
        uint8 current = get8Unsafe(packed, index);
        current += value;
        ret = update8Unsafe(packed, index, current);
    }

    function add16Unsafe(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        assembly {
            ret := add(packed, shl(shl(4, index), and(value, 0xffff)))
        }
    }

    function add16(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        if (index > 15) {
            revert PackedUint256Error(_UINT16_INDEX_ERROR);
        }
        uint16 current = get16Unsafe(packed, index);
        current += value;
        ret = update16Unsafe(packed, index, current);
    }

    function add32Unsafe(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        assembly {
            ret := add(packed, shl(shl(5, index), and(value, 0xffffffff)))
        }
    }

    function add32(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        if (index > 7) {
            revert PackedUint256Error(_UINT32_INDEX_ERROR);
        }
        uint32 current = get32Unsafe(packed, index);
        current += value;
        ret = update32Unsafe(packed, index, current);
    }

    function add64Unsafe(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        assembly {
            ret := add(packed, shl(shl(6, index), and(value, 0xffffffffffffffff)))
        }
    }

    function add64(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        if (index > 3) {
            revert PackedUint256Error(_UINT64_INDEX_ERROR);
        }
        uint64 current = get64Unsafe(packed, index);
        current += value;
        ret = update64Unsafe(packed, index, current);
    }

    function sub8Unsafe(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        assembly {
            ret := sub(packed, shl(shl(3, index), and(value, 0xff)))
        }
    }

    function sub8(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        if (index > 31) {
            revert PackedUint256Error(_UINT8_INDEX_ERROR);
        }
        uint8 current = get8Unsafe(packed, index);
        current -= value;
        ret = update8Unsafe(packed, index, current);
    }

    function sub16Unsafe(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        assembly {
            ret := sub(packed, shl(shl(4, index), and(value, 0xffff)))
        }
    }

    function sub16(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        if (index > 15) {
            revert PackedUint256Error(_UINT16_INDEX_ERROR);
        }
        uint16 current = get16Unsafe(packed, index);
        current -= value;
        ret = update16Unsafe(packed, index, current);
    }

    function sub32Unsafe(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        assembly {
            ret := sub(packed, shl(shl(5, index), and(value, 0xffffffff)))
        }
    }

    function sub32(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        if (index > 7) {
            revert PackedUint256Error(_UINT32_INDEX_ERROR);
        }
        uint32 current = get32Unsafe(packed, index);
        current -= value;
        ret = update32Unsafe(packed, index, current);
    }

    function sub64Unsafe(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        assembly {
            ret := sub(packed, shl(shl(6, index), and(value, 0xffffffffffffffff)))
        }
    }

    function sub64(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        if (index > 3) {
            revert PackedUint256Error(_UINT64_INDEX_ERROR);
        }
        uint64 current = get64Unsafe(packed, index);
        current -= value;
        ret = update64Unsafe(packed, index, current);
    }

    function update8Unsafe(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        unchecked {
            index = index << 3;
            packed = packed - (packed & (_MAX_UINT8 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xff)))
        }
    }

    function update8(uint256 packed, uint256 index, uint8 value) internal pure returns (uint256 ret) {
        if (index > 31) {
            revert PackedUint256Error(_UINT8_INDEX_ERROR);
        }
        unchecked {
            index = index << 3;
            packed = packed - (packed & (_MAX_UINT8 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xff)))
        }
    }

    function update16Unsafe(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        unchecked {
            index = index << 4;
            packed = packed - (packed & (_MAX_UINT16 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffff)))
        }
    }

    function update16(uint256 packed, uint256 index, uint16 value) internal pure returns (uint256 ret) {
        if (index > 15) {
            revert PackedUint256Error(_UINT16_INDEX_ERROR);
        }
        unchecked {
            index = index << 4;
            packed = packed - (packed & (_MAX_UINT16 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffff)))
        }
    }

    function update32Unsafe(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        unchecked {
            index = index << 5;
            packed = packed - (packed & (_MAX_UINT32 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffffffff)))
        }
    }

    function update32(uint256 packed, uint256 index, uint32 value) internal pure returns (uint256 ret) {
        if (index > 7) {
            revert PackedUint256Error(_UINT32_INDEX_ERROR);
        }
        unchecked {
            index = index << 5;
            packed = packed - (packed & (_MAX_UINT32 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffffffff)))
        }
    }

    function update64Unsafe(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        unchecked {
            index = index << 6;
            packed = packed - (packed & (_MAX_UINT64 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffffffffffffffff)))
        }
    }

    function update64(uint256 packed, uint256 index, uint64 value) internal pure returns (uint256 ret) {
        if (index > 3) {
            revert PackedUint256Error(_UINT64_INDEX_ERROR);
        }
        unchecked {
            index = index << 6;
            packed = packed - (packed & (_MAX_UINT64 << index));
        }
        assembly {
            ret := add(packed, shl(index, and(value, 0xffffffffffffffff)))
        }
    }

    function total32(uint256 packed) internal pure returns (uint256) {
        unchecked {
            uint256 ret = _MAX_UINT32 & packed;
            for (uint256 i = 0; i < 7; ++i) {
                packed = packed >> 32;
                ret += _MAX_UINT32 & packed;
            }
            return ret;
        }
    }

    function total64(uint256 packed) internal pure returns (uint256) {
        unchecked {
            uint256 ret = _MAX_UINT64 & packed;
            for (uint256 i = 0; i < 3; ++i) {
                packed = packed >> 64;
                ret += _MAX_UINT64 & packed;
            }
            return ret;
        }
    }

    function sum32(uint256 packed, uint256 from, uint256 to) internal pure returns (uint256) {
        unchecked {
            packed = packed >> (from << 5);
            uint256 ret = 0;
            for (uint256 i = from; i < to; ++i) {
                ret += _MAX_UINT32 & packed;
                packed = packed >> 32;
            }
            return ret;
        }
    }

    function sum64(uint256 packed, uint256 from, uint256 to) internal pure returns (uint256) {
        unchecked {
            packed = packed >> (from << 6);
            uint256 ret = 0;
            for (uint256 i = from; i < to; ++i) {
                ret += _MAX_UINT64 & packed;
                packed = packed >> 64;
            }
            return ret;
        }
    }
}

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.0;

import "./PackedUint256.sol";
import "./DirtyUint64.sol";

/**
 * 🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲
 *
 *                   Segmented Segment Tree
 *                          by Sonic Market
 *
 * ____________/\\\_______________/\\\\\____________/\\\____
 *  __________/\\\\\___________/\\\\////___________/\\\\\____
 *   ________/\\\/\\\________/\\\///______________/\\\/\\\____
 *    ______/\\\/\/\\\______/\\\\\\\\\\\_________/\\\/\/\\\____
 *     ____/\\\/__\/\\\_____/\\\\///////\\\_____/\\\/__\/\\\____
 *      __/\\\\\\\\\\\\\\\\_\/\\\______\//\\\__/\\\\\\\\\\\\\\\\_
 *       _\///////////\\\//__\//\\\______/\\\__\///////////\\\//__
 *        ___________\/\\\_____\///\\\\\\\\\/_____________\/\\\____
 *         ___________\///________\/////////_______________\///_____
 *
 *           4 Layers of 64-bit nodes, hence 464
 *
 * 🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲
 */
library SegmentedSegmentTree {
    using PackedUint256 for uint256;
    using DirtyUint64 for uint64;

    error SegmentedSegmentTreeError(uint256 errorCode);

    uint256 private constant _INDEX_ERROR = 0;
    uint256 private constant _OVERFLOW_ERROR = 1;

    //    uint8 private constant _R = 2; // There are `2` root node groups
    //    uint8 private constant _C = 4; // There are `4` children (each child is a node group of its own) for each node
    uint8 private constant _L = 4; // There are `4` layers of node groups
    uint256 private constant _P = 4; // uint256 / uint64 = `4`
    uint256 private constant _P_M = 3; // % 4 = & `3`
    uint256 private constant _P_P = 2; // 2 ** `2` = 4
    uint256 private constant _N_P = 4; // C * P = 2 ** `4`
    uint256 private constant _MAX_NODES = 2 ** 15; // (R * P) * ((C * P) ** (L - 1)) = `32768`
    uint256 private constant _MAX_NODES_P_MINUS_ONE = 14; // MAX_NODES / R = 2 ** `14`

    struct Core {
        mapping(uint256 => uint256)[_L] layers;
    }

    struct LayerIndex {
        uint256 group;
        uint256 node;
    }

    function get(Core storage core, uint256 index) internal view returns (uint64 ret) {
        if (index >= _MAX_NODES) {
            revert SegmentedSegmentTreeError(_INDEX_ERROR);
        }
        unchecked {
            ret = core.layers[_L - 1][index >> _P_P].get64(index & _P_M).toClean();
        }
    }

    function total(Core storage core) internal view returns (uint64) {
        return DirtyUint64.sumPackedUnsafe(core.layers[0][0], 0, _P)
            + DirtyUint64.sumPackedUnsafe(core.layers[0][1], 0, _P);
    }

    function query(Core storage core, uint256 left, uint256 right) internal view returns (uint64 sum) {
        if (left == right) {
            return 0;
        }
        // right should be greater than left
        if (left >= right) {
            revert SegmentedSegmentTreeError(_INDEX_ERROR);
        }
        if (right > _MAX_NODES) {
            revert SegmentedSegmentTreeError(_INDEX_ERROR);
        }

        LayerIndex[] memory leftIndices = _getLayerIndices(left);
        LayerIndex[] memory rightIndices = _getLayerIndices(right);
        uint256 ret;
        uint256 deficit;

        unchecked {
            uint256 leftNodeIndex;
            uint256 rightNodeIndex;
            for (uint256 l = _L - 1;; --l) {
                LayerIndex memory leftIndex = leftIndices[l];
                LayerIndex memory rightIndex = rightIndices[l];
                leftNodeIndex += leftIndex.node;
                rightNodeIndex += rightIndex.node;

                if (rightIndex.group == leftIndex.group) {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], leftNodeIndex, rightNodeIndex);
                    break;
                }

                if (rightIndex.group - leftIndex.group < 4) {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], leftNodeIndex, _P);

                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group], 0, rightNodeIndex);

                    for (uint256 group = leftIndex.group + 1; group < rightIndex.group; group++) {
                        ret += DirtyUint64.sumPackedUnsafe(core.layers[l][group], 0, _P);
                    }
                    break;
                }

                if (leftIndex.group % 4 == 0) {
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], 0, leftNodeIndex);
                    leftNodeIndex = 0;
                } else if (leftIndex.group % 4 == 1) {
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group - 1], 0, _P);
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], 0, leftNodeIndex);
                    leftNodeIndex = 0;
                } else if (leftIndex.group % 4 == 2) {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], leftNodeIndex, _P);
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group + 1], 0, _P);
                    leftNodeIndex = 1;
                } else {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][leftIndex.group], leftNodeIndex, _P);
                    leftNodeIndex = 1;
                }

                if (rightIndex.group % 4 == 0) {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group], 0, rightNodeIndex);
                    rightNodeIndex = 0;
                } else if (rightIndex.group % 4 == 1) {
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group - 1], 0, _P);
                    ret += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group], 0, rightNodeIndex);
                    rightNodeIndex = 0;
                } else if (rightIndex.group % 4 == 2) {
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group], rightNodeIndex, _P);
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group + 1], 0, _P);
                    rightNodeIndex = 1;
                } else {
                    deficit += DirtyUint64.sumPackedUnsafe(core.layers[l][rightIndex.group], rightNodeIndex, _P);
                    rightNodeIndex = 1;
                }
            }
            ret -= deficit;
        }
        sum = uint64(ret);
    }

    function update(Core storage core, uint256 index, uint64 value) internal returns (uint64 replaced) {
        if (index >= _MAX_NODES) {
            revert SegmentedSegmentTreeError(_INDEX_ERROR);
        }
        LayerIndex[] memory indices = _getLayerIndices(index);
        unchecked {
            LayerIndex memory bottomIndex = indices[_L - 1];
            replaced = core.layers[_L - 1][bottomIndex.group].get64Unsafe(bottomIndex.node).toClean();
            if (replaced >= value) {
                uint64 diff = replaced - value;
                for (uint256 l = 0; l < _L; ++l) {
                    LayerIndex memory layerIndex = indices[l];
                    uint256 node = core.layers[l][layerIndex.group];
                    core.layers[l][layerIndex.group] =
                        node.update64(layerIndex.node, node.get64(layerIndex.node).subClean(diff));
                }
            } else {
                uint64 diff = value - replaced;
                if (total(core) > type(uint64).max - diff) revert SegmentedSegmentTreeError(_OVERFLOW_ERROR);
                for (uint256 l = 0; l < _L; ++l) {
                    LayerIndex memory layerIndex = indices[l];
                    uint256 node = core.layers[l][layerIndex.group];
                    core.layers[l][layerIndex.group] =
                        node.update64(layerIndex.node, node.get64(layerIndex.node).addClean(diff));
                }
            }
        }
    }

    function _getLayerIndices(uint256 index) private pure returns (LayerIndex[] memory) {
        unchecked {
            LayerIndex[] memory indices = new LayerIndex[](_L);
            uint256 shifter = _MAX_NODES_P_MINUS_ONE;
            for (uint256 l = 0; l < _L; ++l) {
                indices[l] = LayerIndex({group: index >> shifter, node: (index >> (shifter - _P_P)) & _P_M});
                shifter = shifter - _N_P;
            }
            return indices;
        }
    }
}

/*
 * Segmented Segment Tree is a Segment Tree
 * that has been compressed so that `C` nodes
 * are compressed into a single uint256.
 *
 * Each node in a non-leaf node group is the sum of the
 * total sum of each child node group that it represents.
 * Each non-leaf node represents `E` node groups.
 *
 * A node group consists of `S` uint256.
 *
 * By expressing the index in `N` notation,
 * we can find the index in each respective layer
 *
 * S: Size of each node group
 * C: Compression Coefficient
 * E: Expansion Coefficient
 * L: Number of Layers
 * N: Notation, S * C * E
 *
 * `E` will not be considered for this version of the implementation. (E = 2)
 */

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.0;

library SignificantBit {
    // http://supertech.csail.mit.edu/papers/debruijn.pdf
    uint256 internal constant DEBRUIJN_SEQ = 0x818283848586878898A8B8C8D8E8F929395969799A9B9D9E9FAAEB6BEDEEFF;
    bytes internal constant DEBRUIJN_INDEX =
        hex"0001020903110a19042112290b311a3905412245134d2a550c5d32651b6d3a7506264262237d468514804e8d2b95569d0d495ea533a966b11c886eb93bc176c9071727374353637324837e9b47af86c7155181ad4fd18ed32c9096db57d59ee30e2e4a6a5f92a6be3498aae067ddb2eb1d5989b56fd7baf33ca0c2ee77e5caf7ff0810182028303840444c545c646c7425617c847f8c949c48a4a8b087b8c0c816365272829aaec650acd0d28fdad4e22d6991bd97dfdcea58b4d6f29fede4f6fe0f1f2f3f4b5b6b607b8b93a3a7b7bf357199c5abcfd9e168bcdee9b3f1ecf5fd1e3e5a7a8aa2b670c4ced8bbe8f0f4fc3d79a1c3cde7effb78cce6facbf9f8";

    /**
     * @notice Finds the index of the least significant bit.
     * @param x The value to compute the least significant bit for. Must be a non-zero value.
     * @return ret The index of the least significant bit.
     */
    function leastSignificantBit(uint256 x) internal pure returns (uint8) {
        require(x > 0);
        uint256 index;
        assembly {
            index := shr(248, mul(and(x, add(not(x), 1)), DEBRUIJN_SEQ))
        }
        return uint8(DEBRUIJN_INDEX[index]); // can optimize with CODECOPY opcode
    }

    function mostSignificantBit(uint256 x) internal pure returns (uint8 msb) {
        require(x > 0);
        assembly {
            let f := shl(7, gt(x, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(6, gt(x, 0xFFFFFFFFFFFFFFFF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(5, gt(x, 0xFFFFFFFF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(4, gt(x, 0xFFFF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(3, gt(x, 0xFF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(2, gt(x, 0xF))
            msb := or(msb, f)
            x := shr(f, x)
            f := shl(1, gt(x, 0x3))
            msb := or(msb, f)
            x := shr(f, x)
            f := gt(x, 0x1)
            msb := or(msb, f)
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later

pragma solidity ^0.8.20;

import {Math} from "./Math.sol";

type Tick is int24;

library TickLibrary {
    using Math for *;
    using TickLibrary for Tick;

    error InvalidTick();
    error InvalidPrice();
    error TickOverflow();

    int24 internal constant MAX_TICK = 2 ** 19 - 1;
    int24 internal constant MIN_TICK = -MAX_TICK;

    uint256 internal constant MIN_PRICE = 1350587;
    uint256 internal constant MAX_PRICE = 4647684107270898330752324302845848816923571339324334;

    uint256 private constant _R0 = 0xfff97272373d413259a46990;
    uint256 private constant _R1 = 0xfff2e50f5f656932ef12357c;
    uint256 private constant _R2 = 0xffe5caca7e10e4e61c3624ea;
    uint256 private constant _R3 = 0xffcb9843d60f6159c9db5883;
    uint256 private constant _R4 = 0xff973b41fa98c081472e6896;
    uint256 private constant _R5 = 0xff2ea16466c96a3843ec78b3;
    uint256 private constant _R6 = 0xfe5dee046a99a2a811c461f1;
    uint256 private constant _R7 = 0xfcbe86c7900a88aedcffc83b;
    uint256 private constant _R8 = 0xf987a7253ac413176f2b074c;
    uint256 private constant _R9 = 0xf3392b0822b70005940c7a39;
    uint256 private constant _R10 = 0xe7159475a2c29b7443b29c7f;
    uint256 private constant _R11 = 0xd097f3bdfd2022b8845ad8f7;
    uint256 private constant _R12 = 0xa9f746462d870fdf8a65dc1f;
    uint256 private constant _R13 = 0x70d869a156d2a1b890bb3df6;
    uint256 private constant _R14 = 0x31be135f97d08fd981231505;
    uint256 private constant _R15 = 0x9aa508b5b7a84e1c677de54;
    uint256 private constant _R16 = 0x5d6af8dedb81196699c329;
    uint256 private constant _R17 = 0x2216e584f5fa1ea92604;
    uint256 private constant _R18 = 0x48a170391f7dc42;
    uint256 private constant _R19 = 0x149b34;

    function validateTick(Tick tick) internal pure {
        if (Tick.unwrap(tick) > MAX_TICK || Tick.unwrap(tick) < MIN_TICK) revert InvalidTick();
    }

    modifier validatePrice(uint256 price) {
        if (price > MAX_PRICE || price < MIN_PRICE) revert InvalidPrice();
        _;
    }

    function fromPrice(uint256 price) internal pure validatePrice(price) returns (Tick) {
        unchecked {
            int24 tick = int24((int256(price).lnWad() * 42951820407860) / 2 ** 128);
            if (toPrice(Tick.wrap(tick)) > price) return Tick.wrap(tick - 1);
            return Tick.wrap(tick);
        }
    }

    function toPrice(Tick tick) internal pure returns (uint256 price) {
        validateTick(tick);
        int24 tickValue = Tick.unwrap(tick);
        uint256 absTick = uint24(tickValue < 0 ? -tickValue : tickValue);

        unchecked {
            if (absTick & 0x1 != 0) price = _R0;
            else price = 1 << 96;
            if (absTick & 0x2 != 0) price = (price * _R1) >> 96;
            if (absTick & 0x4 != 0) price = (price * _R2) >> 96;
            if (absTick & 0x8 != 0) price = (price * _R3) >> 96;
            if (absTick & 0x10 != 0) price = (price * _R4) >> 96;
            if (absTick & 0x20 != 0) price = (price * _R5) >> 96;
            if (absTick & 0x40 != 0) price = (price * _R6) >> 96;
            if (absTick & 0x80 != 0) price = (price * _R7) >> 96;
            if (absTick & 0x100 != 0) price = (price * _R8) >> 96;
            if (absTick & 0x200 != 0) price = (price * _R9) >> 96;
            if (absTick & 0x400 != 0) price = (price * _R10) >> 96;
            if (absTick & 0x800 != 0) price = (price * _R11) >> 96;
            if (absTick & 0x1000 != 0) price = (price * _R12) >> 96;
            if (absTick & 0x2000 != 0) price = (price * _R13) >> 96;
            if (absTick & 0x4000 != 0) price = (price * _R14) >> 96;
            if (absTick & 0x8000 != 0) price = (price * _R15) >> 96;
            if (absTick & 0x10000 != 0) price = (price * _R16) >> 96;
            if (absTick & 0x20000 != 0) price = (price * _R17) >> 96;
            if (absTick & 0x40000 != 0) price = (price * _R18) >> 96;
        }
        if (tickValue > 0) price = 0x1000000000000000000000000000000000000000000000000 / price;
    }

    function gt(Tick a, Tick b) internal pure returns (bool) {
        return Tick.unwrap(a) > Tick.unwrap(b);
    }

    function baseToQuote(Tick tick, uint256 base, bool roundingUp) internal pure returns (uint256) {
        return Math.divide((base * tick.toPrice()), 1 << 96, roundingUp);
    }

    function quoteToBase(Tick tick, uint256 quote, bool roundingUp) internal pure returns (uint256) {
        // @dev quote = unit(uint64) * unitSize(uint64) < 2^96
        //      We don't need to check overflow here
        return Math.divide(quote << 96, tick.toPrice(), roundingUp);
    }
}

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.0;

import {SignificantBit} from "./SignificantBit.sol";
import {Tick} from "./Tick.sol";

library TickBitmap {
    using SignificantBit for uint256;

    error EmptyError();
    error AlreadyExistsError();

    uint256 public constant B0_BITMAP_KEY = uint256(keccak256("TickBitmap")) + 1;
    uint256 public constant MAX_UINT_256_MINUS_1 = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe;

    function has(mapping(uint256 => uint256) storage self, Tick tick) internal view returns (bool) {
        (uint256 b0b1, uint256 b2) = _split(tick);
        uint256 mask = 1 << b2;
        return self[b0b1] & mask == mask;
    }

    function isEmpty(mapping(uint256 => uint256) storage self) internal view returns (bool) {
        return self[B0_BITMAP_KEY] == 0;
    }

    function _split(Tick tick) private pure returns (uint256 b0b1, uint256 b2) {
        assembly {
            let value := add(not(tick), 0x800000)
            b0b1 := shr(8, and(value, 0xffff00))
            b2 := and(value, 0xff)
        }
    }

    function highest(mapping(uint256 => uint256) storage self) internal view returns (Tick) {
        if (isEmpty(self)) revert EmptyError();

        uint256 b0 = self[B0_BITMAP_KEY].leastSignificantBit();
        uint256 b0b1 = (b0 << 8) | (self[~b0].leastSignificantBit());
        uint256 b2 = self[b0b1].leastSignificantBit();
        return _toTick((b0b1 << 8) | b2);
    }

    function set(mapping(uint256 => uint256) storage self, Tick tick) internal {
        (uint256 b0b1, uint256 b2) = _split(tick);
        uint256 mask = 1 << b2;
        uint256 b2Bitmap = self[b0b1];
        if (b2Bitmap & mask > 0) revert AlreadyExistsError();

        self[b0b1] = b2Bitmap | mask;
        if (b2Bitmap == 0) {
            mask = 1 << (b0b1 & 0xff);
            uint256 b1BitmapKey = ~(b0b1 >> 8);
            uint256 b1Bitmap = self[b1BitmapKey];
            self[b1BitmapKey] = b1Bitmap | mask;

            if (b1Bitmap == 0) self[B0_BITMAP_KEY] = self[B0_BITMAP_KEY] | (1 << ~b1BitmapKey);
        }
    }

    function clear(mapping(uint256 => uint256) storage self, Tick tick) internal {
        (uint256 b0b1, uint256 b2) = _split(tick);
        uint256 mask = 1 << b2;
        uint256 b2Bitmap = self[b0b1];

        self[b0b1] = b2Bitmap & (~mask);
        if (b2Bitmap == mask) {
            mask = 1 << (b0b1 & 0xff);
            uint256 b1BitmapKey = ~(b0b1 >> 8);
            uint256 b1Bitmap = self[b1BitmapKey];

            self[b1BitmapKey] = b1Bitmap & (~mask);
            if (mask == b1Bitmap) {
                mask = 1 << (~b1BitmapKey);
                self[B0_BITMAP_KEY] = self[B0_BITMAP_KEY] & (~mask);
            }
        }
    }

    function maxLessThan(mapping(uint256 => uint256) storage self, Tick tick) internal view returns (Tick) {
        (uint256 b0b1, uint256 b2) = _split(tick);
        uint256 b2Bitmap = (MAX_UINT_256_MINUS_1 << b2) & self[b0b1];
        if (b2Bitmap == 0) {
            uint256 b0 = b0b1 >> 8;
            uint256 b1Bitmap = (MAX_UINT_256_MINUS_1 << (b0b1 & 0xff)) & self[~b0];
            if (b1Bitmap == 0) {
                uint256 b0Bitmap = (MAX_UINT_256_MINUS_1 << b0) & self[B0_BITMAP_KEY];
                if (b0Bitmap == 0) return Tick.wrap(type(int24).min);
                b0 = b0Bitmap.leastSignificantBit();
                b1Bitmap = self[~b0];
            }
            b0b1 = (b0 << 8) | b1Bitmap.leastSignificantBit();
            b2Bitmap = self[b0b1];
        }
        b2 = b2Bitmap.leastSignificantBit();
        return _toTick((b0b1 << 8) | b2);
    }

    function _toTick(uint256 raw) private pure returns (Tick t) {
        assembly {
            t := and(not(sub(raw, 0x800000)), 0xffffff)
        }
    }
}

// SPDX-License-Identifier: -
// License: https://license.sonic.market/LICENSE.pdf

pragma solidity ^0.8.20;

import {DirtyUint64} from "./DirtyUint64.sol";
import {PackedUint256} from "./PackedUint256.sol";
import {Tick} from "./Tick.sol";

library TotalClaimableMap {
    using DirtyUint64 for uint64;
    using PackedUint256 for uint256;

    // @dev n should be less than type(uint64).max due to the dirty storage logic.
    function add(mapping(uint24 => uint256) storage self, Tick tick, uint64 n) internal {
        (uint24 groupIndex, uint8 elementIndex) = _splitTick(tick);
        uint256 group = self[groupIndex];
        // @notice Be aware of dirty storage add logic
        self[groupIndex] = group.update64Unsafe(
            elementIndex, // elementIndex < 4
            group.get64Unsafe(elementIndex).addClean(n)
        );
    }

    function sub(mapping(uint24 => uint256) storage self, Tick tick, uint64 n) internal {
        (uint24 groupIndex, uint8 elementIndex) = _splitTick(tick);
        self[groupIndex] = self[groupIndex].sub64Unsafe(elementIndex, n);
    }

    function get(mapping(uint24 => uint256) storage self, Tick tick) internal view returns (uint64) {
        (uint24 groupIndex, uint8 elementIndex) = _splitTick(tick);
        return self[groupIndex].get64Unsafe(elementIndex).toClean();
    }

    function _splitTick(Tick tick) internal pure returns (uint24 groupIndex, uint8 elementIndex) {
        uint256 casted = uint24(Tick.unwrap(tick));
        assembly {
            groupIndex := shr(2, casted) // div 4
            elementIndex := and(casted, 3) // mod 4
        }
    }
}

{
  "evmVersion": "cancun",
  "optimizer": {
    "enabled": true,
    "runs": 1000
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "metadata": {
    "useLiteralContent": true
  },
  "libraries": {}
}

• No Contract Security Audit Submitted- Submit Audit Here

[{"inputs":[],"name":"AlreadyExistsError","type":"error"},{"inputs":[],"name":"BookAlreadyOpened","type":"error"},{"inputs":[],"name":"BookNotOpened","type":"error"},{"inputs":[{"internalType":"uint64","name":"maxCancelableUnit","type":"uint64"}],"name":"CancelFailed","type":"error"},{"inputs":[{"internalType":"uint256","name":"errorCode","type":"uint256"}],"name":"DirtyUint64Error","type":"error"},{"inputs":[{"internalType":"uint256","name":"errorCode","type":"uint256"}],"name":"PackedUint256Error","type":"error"},{"inputs":[],"name":"QueueReplaceFailed","type":"error"},{"inputs":[{"internalType":"uint8","name":"bits","type":"uint8"},{"internalType":"uint256","name":"value","type":"uint256"}],"name":"SafeCastOverflowedUintDowncast","type":"error"},{"inputs":[{"internalType":"uint256","name":"errorCode","type":"uint256"}],"name":"SegmentedSegmentTreeError","type":"error"},{"inputs":[],"name":"ZeroUnit","type":"error"}]

6118ef610034600b8282823980515f1a607314602857634e487b7160e01b5f525f60045260245ffd5b305f52607381538281f3fe730000000000000000000000000000000000000000301460806040526004361061007a575f3560e01c8063ab8a7e3f11610058578063ab8a7e3f1461010e578063c49d26211461012f578063ffa0afb51461014e575f80fd5b8063329b4a011461007e5780633ac502c1146100af578063a151a7e1146100ef575b5f80fd5b61009161008c366004611567565b610183565b60405167ffffffffffffffff90911681526020015b60405180910390f35b8180156100ba575f80fd5b506100ce6100c93660046115c5565b61025e565b6040805167ffffffffffffffff9384168152929091166020830152016100a6565b8180156100fa575f80fd5b506100916101093660046115f0565b61040b565b818015610119575f80fd5b5061012d610128366004611622565b610463565b005b81801561013a575f80fd5b50610091610149366004611567565b6104bf565b818015610159575f80fd5b5061016d61016836600461166b565b610525565b60405164ffffffffff90911681526020016100a6565b5f80610190858585610776565b602090810151600286900b5f90815260038801909252604090912060048101549192509064ffffffffff85166180000110156101ce57509050610257565b5f6101dc60058801876107ca565b90505f6101f0838764ffffffffff1661081f565b90508167ffffffffffffffff1684820367ffffffffffffffff161061021b575f945050505050610257565b8167ffffffffffffffff168167ffffffffffffffff16116102425783945050505050610257565b8381038203945050505050610257565b505050505b9392505050565b602882901c62ffffff16600281900b5f908152600385016020526040812060048101805492938493909264ffffffffff8816929091859190849081106102a6576102a66116b9565b5f918252602082200154600160a01b900467ffffffffffffffff1691506102ce8a8686610183565b90506102da81896116e1565b95508567ffffffffffffffff168267ffffffffffffffff16101561033d576040517fc332559a00000000000000000000000000000000000000000000000000000000815267ffffffffffffffff8284031660048201526024015b60405180910390fd5b600285900b5f90815260038b0160205260409020868303975061038990617fff861690899061036c9083610872565b600289900b5f90815260038f0160205260409020929190036108be565b5085836004018564ffffffffff16815481106103a7576103a76116b9565b905f5260205f20015f0160146101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055506103e18a86610b16565b67ffffffffffffffff165f036103fe576103fe60048b0186610b4b565b5050505050935093915050565b5f806104178585610b16565b90508267ffffffffffffffff168167ffffffffffffffff16111561043d5782915061044d565b90508061044d6004860185610b4b565b61045b600586018584610c49565b509392505050565b8154600160a01b900467ffffffffffffffff16156104ad576040517fc15ba32200000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80826104b9828261171c565b50505050565b5f806104cc858585610cc7565b90506104d9858585610183565b815467ffffffffffffffff600160a01b8083048216849003909116027fffffffff0000000000000000ffffffffffffffffffffffffffffffffffffffff90911617909155949350505050565b5f8267ffffffffffffffff165f03610569576040517ff21c16aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b62800000841901600881901c61ffff165f908152600487016020526040902054600160ff9092169190911b908116146105a9576105a96004860185610d08565b600284900b5f908152600386016020526040902060048101546105cb90610e28565b915061800064ffffffffff8316106106dd575f618000830390505f826004018264ffffffffff1681548110610602576106026116b9565b5f91825260209091200154600160a01b900467ffffffffffffffff1690508015610683575f610632898985610183565b90508167ffffffffffffffff168167ffffffffffffffff1614610681576040517ff2f9ac9900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b505b505f905061069582617fff8516610872565b905067ffffffffffffffff8116156106db57623fffff600287901c165f9081526005880160205260409020805467ffffffffffffffff831660c060068a901b161b900390555b505b6106ec81617fff8416866108be565b50604080518082019091526001600160a01b03938416815267ffffffffffffffff9485166020808301918252600490930180546001810182555f91825293902091519190920180549251909516600160a01b027fffffffff000000000000000000000000000000000000000000000000000000009092169316929092179190911790915592915050565b604080518082019091525f8082526020820152610794848484610cc7565b6040805180820190915290546001600160a01b0381168252600160a01b900467ffffffffffffffff166020820152949350505050565b600281901c623fffff165f81815260208490526040812054909190600384169061081490600686901b60c0161c67ffffffffffffffff165b67ffffffffffffffff16801515900390565b925050505b92915050565b60048201545f90617fff90811690829061083a856001611885565b1690508082106108675761084f858284610e76565b61085886611319565b6108629190611898565b610814565b610814858383610e76565b5f61800082106108975760405163163da48960e01b81525f6004820152602401610334565b6102576108026003848116908690600287901c5f9081529101602052604090205490611358565b5f61800083106108e35760405163163da48960e01b81525f6004820152602401610334565b5f6108ed84611390565b90505f81600160040360ff1681518110610909576109096116b9565b60209081029190910181015190810151909150610949906108029088600385515f908152910160205260409020549060061b1c67ffffffffffffffff1690565b92508367ffffffffffffffff168367ffffffffffffffff1610610a20578383035f5b6004811015610a19575f848281518110610987576109876116b9565b602002602001015190505f895f0183600481106109a6576109a66116b9565b83515f90815291016020908152604090912054908301519091506109ea906109e2866109d28584611358565b67ffffffffffffffff1690611436565b839190611483565b8a84600481106109fc576109fc6116b9565b93515f90815293016020526040909220919091555060010161096b565b5050610b0d565b82840367ffffffffffffffff81810316610a3988611319565b67ffffffffffffffff161115610a655760405163163da48960e01b815260016004820152602401610334565b5f5b6004811015610252575f848281518110610a8357610a836116b9565b602002602001015190505f895f018360048110610aa257610aa26116b9565b83515f9081529101602090815260409091205490830151909150610ade906109e286610ace8584611358565b67ffffffffffffffff16906114ca565b8a8460048110610af057610af06116b9565b93515f908152930160205260409092209190915550600101610a67565b50509392505050565b5f610b2460058401836107ca565b600283900b5f9081526003850160205260409020610b4190611319565b6102579190611898565b62800000811901600881901c61ffff165f8181526020859052604090208054600160ff90941693841b80198216909255919291818103610c4157600884901c195f8181526020889052604090208054600160ff88161b80198216909255909350808403610c3e5781196001901b93508319885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610bed9190611885565b81526020019081526020015f205416885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610c2d9190611885565b815260208101919091526040015f20555b50505b505050505050565b623fffff600283901c165f818152602085905260409020546003841690610ca782610c888667ffffffffffffffff60c060068b901b1686901c16610ace565b67ffffffffffffffff90811660069290921b91821b911b831683030190565b62ffffff9093165f90815260209690965250506040909320929092555050565b600282900b5f9081526003840160205260408120600401805464ffffffffff8416908110610cf757610cf76116b9565b905f5260205f200190509392505050565b62800000811901600881901c61ffff165f81815260208590526040902054909160ff16906001821b9081811615610d6b576040517feb73dbfd00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f8481526020879052604081208284179055819003610c4157600884901c195f8181526020889052604081208054600160ff89161b81811790925590945090819003610c3e5781196001901b885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610de89190611885565b81526020019081526020015f205417885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610c2d9190611885565b5f64ffffffffff821115610e72576040517f6dfcc6500000000000000000000000000000000000000000000000000000000081526028600482015260248101839052604401610334565b5090565b5f818303610e8557505f610257565b818310610ea75760405163163da48960e01b81525f6004820152602401610334565b618000821115610ecc5760405163163da48960e01b81525f6004820152602401610334565b5f610ed684611390565b90505f610ee284611390565b90505f80808060035b5f878281518110610efe57610efe6116b9565b602002602001015190505f878381518110610f1b57610f1b6116b9565b60200260200101519050816020015185019450806020015184019350815f0151815f015103610f8557610f708d8460048110610f5957610f596116b9565b84515f908152910160205260409020548686611511565b67ffffffffffffffff1687019650505061130a565b815181516004919003101561106757610fc18d8460048110610fa957610fa96116b9565b84515f90815291016020526040902054866004611511565b67ffffffffffffffff169690960195610ffc8d8460048110610fe557610fe56116b9565b83515f908152910160205260408120549086611511565b825167ffffffffffffffff9190911697909701966001015b815181101561105f576110488e8560048110611032576110326116b9565b5f84815291016020526040812054906004611511565b67ffffffffffffffff169790970196600101611014565b50505061130a565b81516003165f036110b45761109e8d8460048110611087576110876116b9565b84515f908152910160205260408120549087611511565b67ffffffffffffffff16860195505f94506111b3565b8151600316600103611114576110f08d84600481106110d5576110d56116b9565b84515f19015f90815291016020526040812054906004611511565b67ffffffffffffffff16959095019461109e8d8460048110611087576110876116b9565b815160031660020361118b576111358d8460048110610fa957610fa96116b9565b67ffffffffffffffff1696909601956111748d8460048110611159576111596116b9565b84516001015f90815291016020526040812054906004611511565b67ffffffffffffffff1687019650600194506111b3565b6111a08d8460048110610fa957610fa96116b9565b67ffffffffffffffff1687019650600194505b80516003165f036111e9576111d38d8460048110610fe557610fe56116b9565b67ffffffffffffffff16870196505f9350611300565b8051600316600103611249576112258d846004811061120a5761120a6116b9565b83515f19015f90815291016020526040812054906004611511565b67ffffffffffffffff1696909601956111d38d8460048110610fe557610fe56116b9565b80516003166002036112d8576112828d846004811061126a5761126a6116b9565b83515f90815291016020526040902054856004611511565b67ffffffffffffffff1695909501946112c18d84600481106112a6576112a66116b9565b83516001015f90815291016020526040812054906004611511565b67ffffffffffffffff168601955060019350611300565b6112ed8d846004811061126a5761126a6116b9565b67ffffffffffffffff1686019550600193505b50505f1901610eeb565b50505090039695505050505050565b60015f9081526020829052604081205461133590826004611511565b5f8080526020849052604081205461134e916004611511565b61081991906116e1565b5f600382111561137e5760405163b8710e2160e01b815260036004820152602401610334565b5060061b1c67ffffffffffffffff1690565b60408051600480825260a082019092526060915f9190816020015b604080518082019091525f80825260208201528152602001906001900390816113ab579050509050600e5f5b600481101561142d5760405180604001604052808387901c815260200160036002850388901c16815250838281518110611413576114136116b9565b6020908102919091010152600319909101906001016113d7565b50909392505050565b81159091019080820367ffffffffffffffff8082169084161080611462575067ffffffffffffffff8116155b1561081957604051633e6c0de960e11b815260016004820152602401610334565b5f60038311156114a95760405163b8710e2160e01b815260036004820152602401610334565b5067ffffffffffffffff90811660069290921b91821b911b82169091030190565b5f81831584010192508167ffffffffffffffff168367ffffffffffffffff16101561150a57604051633e6c0de960e11b81525f6004820152602401610334565b5090919050565b600682901b9290921c915f825b8281101561154657604085901c9467ffffffffffffffff16801501919091019060010161151e565b509190039003919050565b8035600281900b8114611562575f80fd5b919050565b5f805f60608486031215611579575f80fd5b8335925061158960208501611551565b9150604084013564ffffffffff811681146115a2575f80fd5b809150509250925092565b67ffffffffffffffff811681146115c2575f80fd5b50565b5f805f606084860312156115d7575f80fd5b833592506020840135915060408401356115a2816115ad565b5f805f60608486031215611602575f80fd5b8335925061161260208501611551565b915060408401356115a2816115ad565b5f8082840360e0811215611634575f80fd5b8335925060c0601f1982011215611649575f80fd5b506020830190509250929050565b6001600160a01b03811681146115c2575f80fd5b5f805f806080858703121561167e575f80fd5b8435935061168e60208601611551565b9250604085013561169e816115ad565b915060608501356116ae81611657565b939692955090935050565b634e487b7160e01b5f52603260045260245ffd5b634e487b7160e01b5f52601160045260245ffd5b67ffffffffffffffff818116838216019080821115611702576117026116cd565b5092915050565b5f813562ffffff81168114610819575f80fd5b813561172781611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b03821617825550602082013561175c816115ad565b81547fffffffff0000000000000000ffffffffffffffffffffffffffffffffffffffff1660a09190911b7bffffffffffffffff0000000000000000000000000000000000000000161781556001810160408301356117b981611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b038216178255506118376117ef60608501611709565b82547fffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffff1660a09190911b76ffffff000000000000000000000000000000000000000016178255565b5060028101608083013561184a81611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b038216178255506118806117ef60a08501611709565b505050565b80820180821115610819576108196116cd565b67ffffffffffffffff828116828216039080821115611702576117026116cd56fea2646970667358221220a13247593ae5c15419d78b3ece674bf54ca1bc0139bfadcff46d347c626dcd5b64736f6c63430008190033

0x735489922f8312c812fbb7184ebf70b9dbfaeed9d4301460806040526004361061007a575f3560e01c8063ab8a7e3f11610058578063ab8a7e3f1461010e578063c49d26211461012f578063ffa0afb51461014e575f80fd5b8063329b4a011461007e5780633ac502c1146100af578063a151a7e1146100ef575b5f80fd5b61009161008c366004611567565b610183565b60405167ffffffffffffffff90911681526020015b60405180910390f35b8180156100ba575f80fd5b506100ce6100c93660046115c5565b61025e565b6040805167ffffffffffffffff9384168152929091166020830152016100a6565b8180156100fa575f80fd5b506100916101093660046115f0565b61040b565b818015610119575f80fd5b5061012d610128366004611622565b610463565b005b81801561013a575f80fd5b50610091610149366004611567565b6104bf565b818015610159575f80fd5b5061016d61016836600461166b565b610525565b60405164ffffffffff90911681526020016100a6565b5f80610190858585610776565b602090810151600286900b5f90815260038801909252604090912060048101549192509064ffffffffff85166180000110156101ce57509050610257565b5f6101dc60058801876107ca565b90505f6101f0838764ffffffffff1661081f565b90508167ffffffffffffffff1684820367ffffffffffffffff161061021b575f945050505050610257565b8167ffffffffffffffff168167ffffffffffffffff16116102425783945050505050610257565b8381038203945050505050610257565b505050505b9392505050565b602882901c62ffffff16600281900b5f908152600385016020526040812060048101805492938493909264ffffffffff8816929091859190849081106102a6576102a66116b9565b5f918252602082200154600160a01b900467ffffffffffffffff1691506102ce8a8686610183565b90506102da81896116e1565b95508567ffffffffffffffff168267ffffffffffffffff16101561033d576040517fc332559a00000000000000000000000000000000000000000000000000000000815267ffffffffffffffff8284031660048201526024015b60405180910390fd5b600285900b5f90815260038b0160205260409020868303975061038990617fff861690899061036c9083610872565b600289900b5f90815260038f0160205260409020929190036108be565b5085836004018564ffffffffff16815481106103a7576103a76116b9565b905f5260205f20015f0160146101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055506103e18a86610b16565b67ffffffffffffffff165f036103fe576103fe60048b0186610b4b565b5050505050935093915050565b5f806104178585610b16565b90508267ffffffffffffffff168167ffffffffffffffff16111561043d5782915061044d565b90508061044d6004860185610b4b565b61045b600586018584610c49565b509392505050565b8154600160a01b900467ffffffffffffffff16156104ad576040517fc15ba32200000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80826104b9828261171c565b50505050565b5f806104cc858585610cc7565b90506104d9858585610183565b815467ffffffffffffffff600160a01b8083048216849003909116027fffffffff0000000000000000ffffffffffffffffffffffffffffffffffffffff90911617909155949350505050565b5f8267ffffffffffffffff165f03610569576040517ff21c16aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b62800000841901600881901c61ffff165f908152600487016020526040902054600160ff9092169190911b908116146105a9576105a96004860185610d08565b600284900b5f908152600386016020526040902060048101546105cb90610e28565b915061800064ffffffffff8316106106dd575f618000830390505f826004018264ffffffffff1681548110610602576106026116b9565b5f91825260209091200154600160a01b900467ffffffffffffffff1690508015610683575f610632898985610183565b90508167ffffffffffffffff168167ffffffffffffffff1614610681576040517ff2f9ac9900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b505b505f905061069582617fff8516610872565b905067ffffffffffffffff8116156106db57623fffff600287901c165f9081526005880160205260409020805467ffffffffffffffff831660c060068a901b161b900390555b505b6106ec81617fff8416866108be565b50604080518082019091526001600160a01b03938416815267ffffffffffffffff9485166020808301918252600490930180546001810182555f91825293902091519190920180549251909516600160a01b027fffffffff000000000000000000000000000000000000000000000000000000009092169316929092179190911790915592915050565b604080518082019091525f8082526020820152610794848484610cc7565b6040805180820190915290546001600160a01b0381168252600160a01b900467ffffffffffffffff166020820152949350505050565b600281901c623fffff165f81815260208490526040812054909190600384169061081490600686901b60c0161c67ffffffffffffffff165b67ffffffffffffffff16801515900390565b925050505b92915050565b60048201545f90617fff90811690829061083a856001611885565b1690508082106108675761084f858284610e76565b61085886611319565b6108629190611898565b610814565b610814858383610e76565b5f61800082106108975760405163163da48960e01b81525f6004820152602401610334565b6102576108026003848116908690600287901c5f9081529101602052604090205490611358565b5f61800083106108e35760405163163da48960e01b81525f6004820152602401610334565b5f6108ed84611390565b90505f81600160040360ff1681518110610909576109096116b9565b60209081029190910181015190810151909150610949906108029088600385515f908152910160205260409020549060061b1c67ffffffffffffffff1690565b92508367ffffffffffffffff168367ffffffffffffffff1610610a20578383035f5b6004811015610a19575f848281518110610987576109876116b9565b602002602001015190505f895f0183600481106109a6576109a66116b9565b83515f90815291016020908152604090912054908301519091506109ea906109e2866109d28584611358565b67ffffffffffffffff1690611436565b839190611483565b8a84600481106109fc576109fc6116b9565b93515f90815293016020526040909220919091555060010161096b565b5050610b0d565b82840367ffffffffffffffff81810316610a3988611319565b67ffffffffffffffff161115610a655760405163163da48960e01b815260016004820152602401610334565b5f5b6004811015610252575f848281518110610a8357610a836116b9565b602002602001015190505f895f018360048110610aa257610aa26116b9565b83515f9081529101602090815260409091205490830151909150610ade906109e286610ace8584611358565b67ffffffffffffffff16906114ca565b8a8460048110610af057610af06116b9565b93515f908152930160205260409092209190915550600101610a67565b50509392505050565b5f610b2460058401836107ca565b600283900b5f9081526003850160205260409020610b4190611319565b6102579190611898565b62800000811901600881901c61ffff165f8181526020859052604090208054600160ff90941693841b80198216909255919291818103610c4157600884901c195f8181526020889052604090208054600160ff88161b80198216909255909350808403610c3e5781196001901b93508319885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610bed9190611885565b81526020019081526020015f205416885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610c2d9190611885565b815260208101919091526040015f20555b50505b505050505050565b623fffff600283901c165f818152602085905260409020546003841690610ca782610c888667ffffffffffffffff60c060068b901b1686901c16610ace565b67ffffffffffffffff90811660069290921b91821b911b831683030190565b62ffffff9093165f90815260209690965250506040909320929092555050565b600282900b5f9081526003840160205260408120600401805464ffffffffff8416908110610cf757610cf76116b9565b905f5260205f200190509392505050565b62800000811901600881901c61ffff165f81815260208590526040902054909160ff16906001821b9081811615610d6b576040517feb73dbfd00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f8481526020879052604081208284179055819003610c4157600884901c195f8181526020889052604081208054600160ff89161b81811790925590945090819003610c3e5781196001901b885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610de89190611885565b81526020019081526020015f205417885f7f7710c0702d438d37259561c892984b894ff622adfa3d98b5dfe5a9763f94b9545f1c6001610c2d9190611885565b5f64ffffffffff821115610e72576040517f6dfcc6500000000000000000000000000000000000000000000000000000000081526028600482015260248101839052604401610334565b5090565b5f818303610e8557505f610257565b818310610ea75760405163163da48960e01b81525f6004820152602401610334565b618000821115610ecc5760405163163da48960e01b81525f6004820152602401610334565b5f610ed684611390565b90505f610ee284611390565b90505f80808060035b5f878281518110610efe57610efe6116b9565b602002602001015190505f878381518110610f1b57610f1b6116b9565b60200260200101519050816020015185019450806020015184019350815f0151815f015103610f8557610f708d8460048110610f5957610f596116b9565b84515f908152910160205260409020548686611511565b67ffffffffffffffff1687019650505061130a565b815181516004919003101561106757610fc18d8460048110610fa957610fa96116b9565b84515f90815291016020526040902054866004611511565b67ffffffffffffffff169690960195610ffc8d8460048110610fe557610fe56116b9565b83515f908152910160205260408120549086611511565b825167ffffffffffffffff9190911697909701966001015b815181101561105f576110488e8560048110611032576110326116b9565b5f84815291016020526040812054906004611511565b67ffffffffffffffff169790970196600101611014565b50505061130a565b81516003165f036110b45761109e8d8460048110611087576110876116b9565b84515f908152910160205260408120549087611511565b67ffffffffffffffff16860195505f94506111b3565b8151600316600103611114576110f08d84600481106110d5576110d56116b9565b84515f19015f90815291016020526040812054906004611511565b67ffffffffffffffff16959095019461109e8d8460048110611087576110876116b9565b815160031660020361118b576111358d8460048110610fa957610fa96116b9565b67ffffffffffffffff1696909601956111748d8460048110611159576111596116b9565b84516001015f90815291016020526040812054906004611511565b67ffffffffffffffff1687019650600194506111b3565b6111a08d8460048110610fa957610fa96116b9565b67ffffffffffffffff1687019650600194505b80516003165f036111e9576111d38d8460048110610fe557610fe56116b9565b67ffffffffffffffff16870196505f9350611300565b8051600316600103611249576112258d846004811061120a5761120a6116b9565b83515f19015f90815291016020526040812054906004611511565b67ffffffffffffffff1696909601956111d38d8460048110610fe557610fe56116b9565b80516003166002036112d8576112828d846004811061126a5761126a6116b9565b83515f90815291016020526040902054856004611511565b67ffffffffffffffff1695909501946112c18d84600481106112a6576112a66116b9565b83516001015f90815291016020526040812054906004611511565b67ffffffffffffffff168601955060019350611300565b6112ed8d846004811061126a5761126a6116b9565b67ffffffffffffffff1686019550600193505b50505f1901610eeb565b50505090039695505050505050565b60015f9081526020829052604081205461133590826004611511565b5f8080526020849052604081205461134e916004611511565b61081991906116e1565b5f600382111561137e5760405163b8710e2160e01b815260036004820152602401610334565b5060061b1c67ffffffffffffffff1690565b60408051600480825260a082019092526060915f9190816020015b604080518082019091525f80825260208201528152602001906001900390816113ab579050509050600e5f5b600481101561142d5760405180604001604052808387901c815260200160036002850388901c16815250838281518110611413576114136116b9565b6020908102919091010152600319909101906001016113d7565b50909392505050565b81159091019080820367ffffffffffffffff8082169084161080611462575067ffffffffffffffff8116155b1561081957604051633e6c0de960e11b815260016004820152602401610334565b5f60038311156114a95760405163b8710e2160e01b815260036004820152602401610334565b5067ffffffffffffffff90811660069290921b91821b911b82169091030190565b5f81831584010192508167ffffffffffffffff168367ffffffffffffffff16101561150a57604051633e6c0de960e11b81525f6004820152602401610334565b5090919050565b600682901b9290921c915f825b8281101561154657604085901c9467ffffffffffffffff16801501919091019060010161151e565b509190039003919050565b8035600281900b8114611562575f80fd5b919050565b5f805f60608486031215611579575f80fd5b8335925061158960208501611551565b9150604084013564ffffffffff811681146115a2575f80fd5b809150509250925092565b67ffffffffffffffff811681146115c2575f80fd5b50565b5f805f606084860312156115d7575f80fd5b833592506020840135915060408401356115a2816115ad565b5f805f60608486031215611602575f80fd5b8335925061161260208501611551565b915060408401356115a2816115ad565b5f8082840360e0811215611634575f80fd5b8335925060c0601f1982011215611649575f80fd5b506020830190509250929050565b6001600160a01b03811681146115c2575f80fd5b5f805f806080858703121561167e575f80fd5b8435935061168e60208601611551565b9250604085013561169e816115ad565b915060608501356116ae81611657565b939692955090935050565b634e487b7160e01b5f52603260045260245ffd5b634e487b7160e01b5f52601160045260245ffd5b67ffffffffffffffff818116838216019080821115611702576117026116cd565b5092915050565b5f813562ffffff81168114610819575f80fd5b813561172781611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b03821617825550602082013561175c816115ad565b81547fffffffff0000000000000000ffffffffffffffffffffffffffffffffffffffff1660a09190911b7bffffffffffffffff0000000000000000000000000000000000000000161781556001810160408301356117b981611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b038216178255506118376117ef60608501611709565b82547fffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffff1660a09190911b76ffffff000000000000000000000000000000000000000016178255565b5060028101608083013561184a81611657565b815473ffffffffffffffffffffffffffffffffffffffff19166001600160a01b038216178255506118806117ef60a08501611709565b505050565b80820180821115610819576108196116cd565b67ffffffffffffffff828116828216039080821115611702576117026116cd56fea2646970667358221220a13247593ae5c15419d78b3ece674bf54ca1bc0139bfadcff46d347c626dcd5b64736f6c63430008190033