// SPDX-License-Identifier: MIT

pragma solidity ^0.8.4;

/// @notice Library for RLP encoding and CREATE address computation.
/// @author Modified from Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibRLP.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibRLP.sol)
library LibRLP {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                          STRUCTS                           */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev A pointer to a RLP item list in memory.
    struct List {
        // Do NOT modify the `_data` directly.
        uint256 _data;
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                  RLP ENCODING OPERATIONS                   */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    // Note:
    // - addresses are treated like byte strings of length 20, agnostic of leading zero bytes.
    // - uint256s are converted to byte strings, stripped of leading zero bytes, and encoded.
    // - bools are converted to uint256s (`b ? 1 : 0`), then encoded with the uint256.
    // - For bytes1 to bytes32, you must manually convert them to bytes memory
    //   with `abi.encodePacked(x)` before encoding.

    /// @dev Returns a new empty list.
    function l() internal pure returns (List memory result) {}

    /// @dev Returns a new list with `x` as the only element. Equivalent to `LibRLP.l().p(x)`.
    function l(uint256 x) internal pure returns (List memory result) {
        p(result, x);
    }

    /// @dev Returns a new list with `x` as the only element. Equivalent to `LibRLP.l().p(x)`.
    function l(address x) internal pure returns (List memory result) {
        p(result, x);
    }

    /// @dev Returns a new list with `x` as the only element. Equivalent to `LibRLP.l().p(x)`.
    function l(bool x) internal pure returns (List memory result) {
        p(result, x);
    }

    /// @dev Returns a new list with `x` as the only element. Equivalent to `LibRLP.l().p(x)`.
    function l(bytes memory x) internal pure returns (List memory result) {
        p(result, x);
    }

    /// @dev Returns a new list with `x` as the only element. Equivalent to `LibRLP.l().p(x)`.
    function l(List memory x) internal pure returns (List memory result) {
        p(result, x);
    }

    /// @dev Appends `x` to `list`. Returns `list` for function chaining.
    function p(List memory list, uint256 x) internal pure returns (List memory result) {
        result._data = x << 48;
        _updateTail(list, result);
        /// @solidity memory-safe-assembly
        assembly {
            // If `x` is too big, we cannot pack it inline with the node.
            // We'll have to allocate a new slot for `x` and store the pointer to it in the node.
            if shr(208, x) {
                let m := mload(0x40)
                mstore(m, x)
                mstore(0x40, add(m, 0x20))
                mstore(result, shl(40, or(1, shl(8, m))))
            }
        }
        result = list;
    }

    /// @dev Appends `x` to `list`. Returns `list` for function chaining.
    function p(List memory list, address x) internal pure returns (List memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(result, shl(40, or(4, shl(8, x))))
        }
        _updateTail(list, result);
        result = list;
    }

    /// @dev Appends `x` to `list`. Returns `list` for function chaining.
    function p(List memory list, bool x) internal pure returns (List memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(result, shl(48, iszero(iszero(x))))
        }
        _updateTail(list, result);
        result = list;
    }

    /// @dev Appends `x` to `list`. Returns `list` for function chaining.
    function p(List memory list, bytes memory x) internal pure returns (List memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(result, shl(40, or(2, shl(8, x))))
        }
        _updateTail(list, result);
        result = list;
    }

    /// @dev Appends `x` to `list`. Returns `list` for function chaining.
    function p(List memory list, List memory x) internal pure returns (List memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(result, shl(40, or(3, shl(8, x))))
        }
        _updateTail(list, result);
        result = list;
    }

    /// @dev Returns the RLP encoding of `list`.
    function encode(List memory list) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            function encodeUint(x_, o_) -> _o {
                _o := add(o_, 1)
                if iszero(gt(x_, 0x7f)) {
                    mstore8(o_, or(shl(7, iszero(x_)), x_)) // Copy `x_`.
                    leave
                }
                let 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(shr(3, r_), lt(0xff, shr(r_, x_)))
                mstore8(o_, add(r_, 0x81)) // Store the prefix.
                mstore(0x00, x_)
                mstore(_o, mload(xor(31, r_))) // Copy `x_`.
                _o := add(add(1, r_), _o)
            }
            function encodeAddress(x_, o_) -> _o {
                _o := add(o_, 0x15)
                mstore(o_, shl(88, x_))
                mstore8(o_, 0x94)
            }
            function encodeBytes(x_, o_, c_) -> _o {
                _o := add(o_, 1)
                let n_ := mload(x_)
                if iszero(gt(n_, 55)) {
                    let f_ := mload(add(0x20, x_))
                    if iszero(and(eq(1, n_), lt(byte(0, f_), 0x80))) {
                        mstore8(o_, add(n_, c_)) // Store the prefix.
                        mstore(add(0x21, o_), mload(add(0x40, x_)))
                        mstore(_o, f_)
                        _o := add(n_, _o)
                        leave
                    }
                    mstore(o_, f_) // Copy `x_`.
                    leave
                }
                returndatacopy(returndatasize(), returndatasize(), shr(32, n_))
                let r_ := add(1, add(lt(0xff, n_), add(lt(0xffff, n_), lt(0xffffff, n_))))
                mstore(o_, shl(248, add(r_, add(c_, 55)))) // Store the prefix.
                // Copy `x`.
                let i_ := add(r_, _o)
                _o := add(i_, n_)
                for { let d_ := sub(add(0x20, x_), i_) } 1 {} {
                    mstore(i_, mload(add(d_, i_)))
                    i_ := add(i_, 0x20)
                    if iszero(lt(i_, _o)) { break }
                }
                mstore(o_, or(mload(o_), shl(sub(248, shl(3, r_)), n_))) // Store the prefix.
            }
            function encodeList(l_, o_) -> _o {
                if iszero(mload(l_)) {
                    mstore8(o_, 0xc0)
                    _o := add(o_, 1)
                    leave
                }
                let j_ := add(o_, 0x20)
                for { let h_ := l_ } 1 {} {
                    h_ := and(mload(h_), 0xffffffffff)
                    if iszero(h_) { break }
                    let t_ := byte(26, mload(h_))
                    if iszero(gt(t_, 1)) {
                        if iszero(t_) {
                            j_ := encodeUint(shr(48, mload(h_)), j_)
                            continue
                        }
                        j_ := encodeUint(mload(shr(48, mload(h_))), j_)
                        continue
                    }
                    if eq(t_, 2) {
                        j_ := encodeBytes(shr(48, mload(h_)), j_, 0x80)
                        continue
                    }
                    if eq(t_, 3) {
                        j_ := encodeList(shr(48, mload(h_)), j_)
                        continue
                    }
                    j_ := encodeAddress(shr(48, mload(h_)), j_)
                }
                mstore(o_, sub(j_, add(o_, 0x20)))
                _o := encodeBytes(o_, o_, 0xc0)
            }
            result := mload(0x40)
            let begin := add(result, 0x20)
            let end := encodeList(list, begin)
            mstore(result, sub(end, begin)) // Store the length of `result`.
            mstore(end, 0) // Zeroize the slot after `result`.
            mstore(0x40, add(end, 0x20)) // Allocate memory for `result`.
        }
    }

    /// @dev Returns the RLP encoding of `x`.
    function encode(uint256 x) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            for {} 1 {} {
                result := mload(0x40)
                if iszero(gt(x, 0x7f)) {
                    mstore(result, 1) // Store the length of `result`.
                    mstore(add(result, 0x20), shl(248, or(shl(7, iszero(x)), x))) // Copy `x`.
                    mstore(0x40, add(result, 0x40)) // Allocate memory for `result`.
                    break
                }
                let 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 := add(2, or(shr(3, r), lt(0xff, shr(r, x))))
                mstore(add(r, result), x) // Copy `x`.
                mstore(add(result, 1), add(r, 0x7f)) // Store the prefix.
                mstore(result, r) // Store the length of `result`.
                mstore(add(r, add(result, 0x20)), 0) // Zeroize the slot after `result`.
                mstore(0x40, add(result, 0x60)) // Allocate memory for `result`.
                break
            }
        }
    }

    /// @dev Returns the RLP encoding of `x`.
    function encode(address x) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            result := mload(0x40)
            mstore(result, 0x15)
            let o := add(0x20, result)
            mstore(o, shl(88, x))
            mstore8(o, 0x94)
            mstore(0x40, add(0x20, o))
        }
    }

    /// @dev Returns the RLP encoding of `x`.
    function encode(bool x) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            result := mload(0x40)
            mstore(result, 1)
            mstore(add(0x20, result), shl(add(0xf8, mul(7, iszero(x))), 0x01))
            mstore(0x40, add(0x40, result))
        }
    }

    /// @dev Returns the RLP encoding of `x`.
    function encode(bytes memory x) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            result := x

            for {} iszero(and(eq(1, mload(x)), lt(byte(0, mload(add(x, 0x20))), 0x80))) {} {
                result := mload(0x40)
                let n := mload(x) // Length of `x`.
                if iszero(gt(n, 55)) {
                    mstore(0x40, add(result, 0x60))
                    mstore(add(0x41, result), mload(add(0x40, x)))
                    mstore(add(0x21, result), mload(add(0x20, x)))
                    mstore(add(1, result), add(n, 0x80)) // Store the prefix.
                    mstore(result, add(1, n)) // Store the length of `result`.
                    mstore(add(add(result, 0x21), n), 0) // Zeroize the slot after `result`.
                    break
                }
                returndatacopy(returndatasize(), returndatasize(), shr(32, n)) // out of
                let r := add(2, add(lt(0xff, n), add(lt(0xffff, n), lt(0xffffff, n))))
                // Copy `x`.
                let i := add(r, add(0x20, result))
                let end := add(i, n)
                for { let d := sub(add(0x20, x), i) } 1 {} {
                    mstore(i, mload(add(d, i)))
                    i := add(i, 0x20)
                    if iszero(lt(i, end)) { break }
                }
                mstore(add(r, result), n) // Store the prefix.
                mstore(add(1, result), add(r, 0xb6)) // Store the prefix.
                mstore(result, add(r, n)) // Store the length of `result`.
                mstore(end, 0) // Zeroize the slot after `result`.
                mstore(0x40, add(end, 0x20)) // Allocate memory.
                break
            }
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                      PRIVATE HELPERS                       */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Updates the tail in `list`.
    function _updateTail(List memory list, List memory result) private pure {
        /// @solidity memory-safe-assembly
        assembly {
            let v := or(shr(mload(list), result), mload(list))
            let tail := shr(40, v)
            mstore(list, xor(shl(40, xor(tail, result)), v)) // Update the tail.
            mstore(tail, or(mload(tail), result)) // Make the previous tail point to `result`.
        }
    }
}