Contract

Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE
• 🤖 Code ReaderBeta
• Remix IDE

More Options

• Similar
• Sol2Uml
• Submit Audit
• Compare

// SPDX-License-Identifier: MIT
pragma solidity 0.8.15;

import { ISemver } from "src/universal/ISemver.sol";
import { IPreimageOracle } from "./interfaces/IPreimageOracle.sol";
import { PreimageKeyLib } from "./PreimageKeyLib.sol";

/// @title MIPS
/// @notice The MIPS contract emulates a single MIPS instruction.
///         Note that delay slots are isolated instructions:
///         the nextPC in the state pre-schedules where the VM jumps next.
///         The Step input is a packed VM state, with binary-merkle-tree
///         witness data for memory reads/writes.
///         The Step outputs a keccak256 hash of the packed VM State,
///         and logs the resulting state for offchain usage.
/// @dev https://inst.eecs.berkeley.edu/~cs61c/resources/MIPS_Green_Sheet.pdf
/// @dev https://www.cs.cmu.edu/afs/cs/academic/class/15740-f97/public/doc/mips-isa.pdf
///      (page A-177)
/// @dev https://uweb.engr.arizona.edu/~ece369/Resources/spim/MIPSReference.pdf
/// @dev https://en.wikibooks.org/wiki/MIPS_Assembly/Instruction_Formats
/// @dev https://github.com/golang/go/blob/master/src/syscall/zerrors_linux_mips.go
///      MIPS linux kernel errors used by Go runtime
contract MIPS is ISemver {
    /// @notice Stores the VM state.
    ///         Total state size: 32 + 32 + 6 * 4 + 1 + 1 + 8 + 32 * 4 = 226 bytes
    ///         If nextPC != pc + 4, then the VM is executing a branch/jump delay slot.
    struct State {
        bytes32 memRoot;
        bytes32 preimageKey;
        uint32 preimageOffset;
        uint32 pc;
        uint32 nextPC;
        uint32 lo;
        uint32 hi;
        uint32 heap;
        uint8 exitCode;
        bool exited;
        uint64 step;
        uint32[32] registers;
    }

    /// @notice Start of the data segment.
    uint32 public constant BRK_START = 0x40000000;

    /// @notice The semantic version of the MIPS contract.
    /// @custom:semver 0.1.0
    string public constant version = "0.1.0";

    uint32 internal constant FD_STDIN = 0;
    uint32 internal constant FD_STDOUT = 1;
    uint32 internal constant FD_STDERR = 2;
    uint32 internal constant FD_HINT_READ = 3;
    uint32 internal constant FD_HINT_WRITE = 4;
    uint32 internal constant FD_PREIMAGE_READ = 5;
    uint32 internal constant FD_PREIMAGE_WRITE = 6;

    uint32 internal constant EBADF = 0x9;
    uint32 internal constant EINVAL = 0x16;

    /// @notice The preimage oracle contract.
    IPreimageOracle internal immutable ORACLE;

    /// @param _oracle The address of the preimage oracle contract.
    constructor(IPreimageOracle _oracle) {
        ORACLE = _oracle;
    }

    /// @notice Getter for the pre-image oracle contract.
    /// @return oracle_ The IPreimageOracle contract.
    function oracle() external view returns (IPreimageOracle oracle_) {
        oracle_ = ORACLE;
    }

    /// @notice Extends the value leftwards with its most significant bit (sign extension).
    function SE(uint32 _dat, uint32 _idx) internal pure returns (uint32 out_) {
        unchecked {
            bool isSigned = (_dat >> (_idx - 1)) != 0;
            uint256 signed = ((1 << (32 - _idx)) - 1) << _idx;
            uint256 mask = (1 << _idx) - 1;
            return uint32(_dat & mask | (isSigned ? signed : 0));
        }
    }

    /// @notice Computes the hash of the MIPS state.
    /// @return out_ The hashed MIPS state.
    function outputState() internal returns (bytes32 out_) {
        assembly {
            // copies 'size' bytes, right-aligned in word at 'from', to 'to', incl. trailing data
            function copyMem(from, to, size) -> fromOut, toOut {
                mstore(to, mload(add(from, sub(32, size))))
                fromOut := add(from, 32)
                toOut := add(to, size)
            }

            // From points to the MIPS State
            let from := 0x80

            // Copy to the free memory pointer
            let start := mload(0x40)
            let to := start

            // Copy state to free memory
            from, to := copyMem(from, to, 32) // memRoot
            from, to := copyMem(from, to, 32) // preimageKey
            from, to := copyMem(from, to, 4) // preimageOffset
            from, to := copyMem(from, to, 4) // pc
            from, to := copyMem(from, to, 4) // nextPC
            from, to := copyMem(from, to, 4) // lo
            from, to := copyMem(from, to, 4) // hi
            from, to := copyMem(from, to, 4) // heap
            let exitCode := mload(from)
            from, to := copyMem(from, to, 1) // exitCode
            let exited := mload(from)
            from, to := copyMem(from, to, 1) // exited
            from, to := copyMem(from, to, 8) // step
            from := add(from, 32) // offset to registers

            // Copy registers
            for { let i := 0 } lt(i, 32) { i := add(i, 1) } { from, to := copyMem(from, to, 4) }

            // Clean up end of memory
            mstore(to, 0)

            // Log the resulting MIPS state, for debugging
            log0(start, sub(to, start))

            // Determine the VM status
            let status := 0
            switch exited
            case 1 {
                switch exitCode
                // VMStatusValid
                case 0 { status := 0 }
                // VMStatusInvalid
                case 1 { status := 1 }
                // VMStatusPanic
                default { status := 2 }
            }
            // VMStatusUnfinished
            default { status := 3 }

            // Compute the hash of the resulting MIPS state and set the status byte
            out_ := keccak256(start, sub(to, start))
            out_ := or(and(not(shl(248, 0xFF)), out_), shl(248, status))
        }
    }

    /// @notice Handles a syscall.
    /// @param _localContext The local key context for the preimage oracle.
    /// @return out_ The hashed MIPS state.
    function handleSyscall(bytes32 _localContext) internal returns (bytes32 out_) {
        unchecked {
            // Load state from memory
            State memory state;
            assembly {
                state := 0x80
            }

            // Load the syscall number from the registers
            uint32 syscall_no = state.registers[2];
            uint32 v0 = 0;
            uint32 v1 = 0;

            // Load the syscall arguments from the registers
            uint32 a0 = state.registers[4];
            uint32 a1 = state.registers[5];
            uint32 a2 = state.registers[6];

            // mmap: Allocates a page from the heap.
            if (syscall_no == 4090) {
                uint32 sz = a1;
                if (sz & 4095 != 0) {
                    // adjust size to align with page size
                    sz += 4096 - (sz & 4095);
                }
                if (a0 == 0) {
                    v0 = state.heap;
                    state.heap += sz;
                } else {
                    v0 = a0;
                }
            }
            // brk: Returns a fixed address for the program break at 0x40000000
            else if (syscall_no == 4045) {
                v0 = BRK_START;
            }
            // clone (not supported) returns 1
            else if (syscall_no == 4120) {
                v0 = 1;
            }
            // exit group: Sets the Exited and ExitCode states to true and argument 0.
            else if (syscall_no == 4246) {
                state.exited = true;
                state.exitCode = uint8(a0);
                return outputState();
            }
            // read: Like Linux read syscall. Splits unaligned reads into aligned reads.
            else if (syscall_no == 4003) {
                // args: a0 = fd, a1 = addr, a2 = count
                // returns: v0 = read, v1 = err code
                if (a0 == FD_STDIN) {
                    // Leave v0 and v1 zero: read nothing, no error
                }
                // pre-image oracle read
                else if (a0 == FD_PREIMAGE_READ) {
                    // verify proof 1 is correct, and get the existing memory.
                    uint32 mem = readMem(a1 & 0xFFffFFfc, 1); // mask the addr to align it to 4 bytes
                    bytes32 preimageKey = state.preimageKey;
                    // If the preimage key is a local key, localize it in the context of the caller.
                    if (uint8(preimageKey[0]) == 1) {
                        preimageKey = PreimageKeyLib.localize(preimageKey, _localContext);
                    }
                    (bytes32 dat, uint256 datLen) = ORACLE.readPreimage(preimageKey, state.preimageOffset);

                    // Transform data for writing to memory
                    // We use assembly for more precise ops, and no var count limit
                    assembly {
                        let alignment := and(a1, 3) // the read might not start at an aligned address
                        let space := sub(4, alignment) // remaining space in memory word
                        if lt(space, datLen) { datLen := space } // if less space than data, shorten data
                        if lt(a2, datLen) { datLen := a2 } // if requested to read less, read less
                        dat := shr(sub(256, mul(datLen, 8)), dat) // right-align data
                        dat := shl(mul(sub(sub(4, datLen), alignment), 8), dat) // position data to insert into memory
                            // word
                        let mask := sub(shl(mul(sub(4, alignment), 8), 1), 1) // mask all bytes after start
                        let suffixMask := sub(shl(mul(sub(sub(4, alignment), datLen), 8), 1), 1) // mask of all bytes
                            // starting from end, maybe none
                        mask := and(mask, not(suffixMask)) // reduce mask to just cover the data we insert
                        mem := or(and(mem, not(mask)), dat) // clear masked part of original memory, and insert data
                    }

                    // Write memory back
                    writeMem(a1 & 0xFFffFFfc, 1, mem);
                    state.preimageOffset += uint32(datLen);
                    v0 = uint32(datLen);
                }
                // hint response
                else if (a0 == FD_HINT_READ) {
                    // Don't read into memory, just say we read it all
                    // The result is ignored anyway
                    v0 = a2;
                } else {
                    v0 = 0xFFffFFff;
                    v1 = EBADF;
                }
            }
            // write: like Linux write syscall. Splits unaligned writes into aligned writes.
            else if (syscall_no == 4004) {
                // args: a0 = fd, a1 = addr, a2 = count
                // returns: v0 = written, v1 = err code
                if (a0 == FD_STDOUT || a0 == FD_STDERR || a0 == FD_HINT_WRITE) {
                    v0 = a2; // tell program we have written everything
                }
                // pre-image oracle
                else if (a0 == FD_PREIMAGE_WRITE) {
                    uint32 mem = readMem(a1 & 0xFFffFFfc, 1); // mask the addr to align it to 4 bytes
                    bytes32 key = state.preimageKey;

                    // Construct pre-image key from memory
                    // We use assembly for more precise ops, and no var count limit
                    assembly {
                        let alignment := and(a1, 3) // the read might not start at an aligned address
                        let space := sub(4, alignment) // remaining space in memory word
                        if lt(space, a2) { a2 := space } // if less space than data, shorten data
                        key := shl(mul(a2, 8), key) // shift key, make space for new info
                        let mask := sub(shl(mul(a2, 8), 1), 1) // mask for extracting value from memory
                        mem := and(shr(mul(sub(space, a2), 8), mem), mask) // align value to right, mask it
                        key := or(key, mem) // insert into key
                    }

                    // Write pre-image key to oracle
                    state.preimageKey = key;
                    state.preimageOffset = 0; // reset offset, to read new pre-image data from the start
                    v0 = a2;
                } else {
                    v0 = 0xFFffFFff;
                    v1 = EBADF;
                }
            }
            // fcntl: Like linux fcntl syscall, but only supports minimal file-descriptor control commands,
            // to retrieve the file-descriptor R/W flags.
            else if (syscall_no == 4055) {
                // fcntl
                // args: a0 = fd, a1 = cmd
                if (a1 == 3) {
                    // F_GETFL: get file descriptor flags
                    if (a0 == FD_STDIN || a0 == FD_PREIMAGE_READ || a0 == FD_HINT_READ) {
                        v0 = 0; // O_RDONLY
                    } else if (a0 == FD_STDOUT || a0 == FD_STDERR || a0 == FD_PREIMAGE_WRITE || a0 == FD_HINT_WRITE) {
                        v0 = 1; // O_WRONLY
                    } else {
                        v0 = 0xFFffFFff;
                        v1 = EBADF;
                    }
                } else {
                    v0 = 0xFFffFFff;
                    v1 = EINVAL; // cmd not recognized by this kernel
                }
            }

            // Write the results back to the state registers
            state.registers[2] = v0;
            state.registers[7] = v1;

            // Update the PC and nextPC
            state.pc = state.nextPC;
            state.nextPC = state.nextPC + 4;

            out_ = outputState();
        }
    }

    /// @notice Handles a branch instruction, updating the MIPS state PC where needed.
    /// @param _opcode The opcode of the branch instruction.
    /// @param _insn The instruction to be executed.
    /// @param _rtReg The register to be used for the branch.
    /// @param _rs The register to be compared with the branch register.
    /// @return out_ The hashed MIPS state.
    function handleBranch(uint32 _opcode, uint32 _insn, uint32 _rtReg, uint32 _rs) internal returns (bytes32 out_) {
        unchecked {
            // Load state from memory
            State memory state;
            assembly {
                state := 0x80
            }

            bool shouldBranch = false;

            if (state.nextPC != state.pc + 4) {
                revert("branch in delay slot");
            }

            // beq/bne: Branch on equal / not equal
            if (_opcode == 4 || _opcode == 5) {
                uint32 rt = state.registers[_rtReg];
                shouldBranch = (_rs == rt && _opcode == 4) || (_rs != rt && _opcode == 5);
            }
            // blez: Branches if instruction is less than or equal to zero
            else if (_opcode == 6) {
                shouldBranch = int32(_rs) <= 0;
            }
            // bgtz: Branches if instruction is greater than zero
            else if (_opcode == 7) {
                shouldBranch = int32(_rs) > 0;
            }
            // bltz/bgez: Branch on less than zero / greater than or equal to zero
            else if (_opcode == 1) {
                // regimm
                uint32 rtv = ((_insn >> 16) & 0x1F);
                if (rtv == 0) {
                    shouldBranch = int32(_rs) < 0;
                }
                if (rtv == 1) {
                    shouldBranch = int32(_rs) >= 0;
                }
            }

            // Update the state's previous PC
            uint32 prevPC = state.pc;

            // Execute the delay slot first
            state.pc = state.nextPC;

            // If we should branch, update the PC to the branch target
            // Otherwise, proceed to the next instruction
            if (shouldBranch) {
                state.nextPC = prevPC + 4 + (SE(_insn & 0xFFFF, 16) << 2);
            } else {
                state.nextPC = state.nextPC + 4;
            }

            // Return the hash of the resulting state
            out_ = outputState();
        }
    }

    /// @notice Handles HI and LO register instructions.
    /// @param _func The function code of the instruction.
    /// @param _rs The value of the RS register.
    /// @param _rt The value of the RT register.
    /// @param _storeReg The register to store the result in.
    /// @return out_ The hashed MIPS state.
    function handleHiLo(uint32 _func, uint32 _rs, uint32 _rt, uint32 _storeReg) internal returns (bytes32 out_) {
        unchecked {
            // Load state from memory
            State memory state;
            assembly {
                state := 0x80
            }

            uint32 val;

            // mfhi: Move the contents of the HI register into the destination
            if (_func == 0x10) {
                val = state.hi;
            }
            // mthi: Move the contents of the source into the HI register
            else if (_func == 0x11) {
                state.hi = _rs;
            }
            // mflo: Move the contents of the LO register into the destination
            else if (_func == 0x12) {
                val = state.lo;
            }
            // mtlo: Move the contents of the source into the LO register
            else if (_func == 0x13) {
                state.lo = _rs;
            }
            // mult: Multiplies `rs` by `rt` and stores the result in HI and LO registers
            else if (_func == 0x18) {
                uint64 acc = uint64(int64(int32(_rs)) * int64(int32(_rt)));
                state.hi = uint32(acc >> 32);
                state.lo = uint32(acc);
            }
            // multu: Unsigned multiplies `rs` by `rt` and stores the result in HI and LO registers
            else if (_func == 0x19) {
                uint64 acc = uint64(uint64(_rs) * uint64(_rt));
                state.hi = uint32(acc >> 32);
                state.lo = uint32(acc);
            }
            // div: Divides `rs` by `rt`.
            // Stores the quotient in LO
            // And the remainder in HI
            else if (_func == 0x1a) {
                state.hi = uint32(int32(_rs) % int32(_rt));
                state.lo = uint32(int32(_rs) / int32(_rt));
            }
            // divu: Unsigned divides `rs` by `rt`.
            // Stores the quotient in LO
            // And the remainder in HI
            else if (_func == 0x1b) {
                state.hi = _rs % _rt;
                state.lo = _rs / _rt;
            }

            // Store the result in the destination register, if applicable
            if (_storeReg != 0) {
                state.registers[_storeReg] = val;
            }

            // Update the PC
            state.pc = state.nextPC;
            state.nextPC = state.nextPC + 4;

            // Return the hash of the resulting state
            out_ = outputState();
        }
    }

    /// @notice Handles a jump instruction, updating the MIPS state PC where needed.
    /// @param _linkReg The register to store the link to the instruction after the delay slot instruction.
    /// @param _dest The destination to jump to.
    /// @return out_ The hashed MIPS state.
    function handleJump(uint32 _linkReg, uint32 _dest) internal returns (bytes32 out_) {
        unchecked {
            // Load state from memory.
            State memory state;
            assembly {
                state := 0x80
            }

            if (state.nextPC != state.pc + 4) {
                revert("jump in delay slot");
            }

            // Update the next PC to the jump destination.
            uint32 prevPC = state.pc;
            state.pc = state.nextPC;
            state.nextPC = _dest;

            // Update the link-register to the instruction after the delay slot instruction.
            if (_linkReg != 0) {
                state.registers[_linkReg] = prevPC + 8;
            }

            // Return the hash of the resulting state.
            out_ = outputState();
        }
    }

    /// @notice Handles a storing a value into a register.
    /// @param _storeReg The register to store the value into.
    /// @param _val The value to store.
    /// @param _conditional Whether or not the store is conditional.
    /// @return out_ The hashed MIPS state.
    function handleRd(uint32 _storeReg, uint32 _val, bool _conditional) internal returns (bytes32 out_) {
        unchecked {
            // Load state from memory.
            State memory state;
            assembly {
                state := 0x80
            }

            // The destination register must be valid.
            require(_storeReg < 32, "valid register");

            // Never write to reg 0, and it can be conditional (movz, movn).
            if (_storeReg != 0 && _conditional) {
                state.registers[_storeReg] = _val;
            }

            // Update the PC.
            state.pc = state.nextPC;
            state.nextPC = state.nextPC + 4;

            // Return the hash of the resulting state.
            out_ = outputState();
        }
    }

    /// @notice Computes the offset of the proof in the calldata.
    /// @param _proofIndex The index of the proof in the calldata.
    /// @return offset_ The offset of the proof in the calldata.
    function proofOffset(uint8 _proofIndex) internal pure returns (uint256 offset_) {
        unchecked {
            // A proof of 32 bit memory, with 32-byte leaf values, is (32-5)=27 bytes32 entries.
            // And the leaf value itself needs to be encoded as well. And proof.offset == 420
            offset_ = 420 + (uint256(_proofIndex) * (28 * 32));
            uint256 s = 0;
            assembly {
                s := calldatasize()
            }
            require(s >= (offset_ + 28 * 32), "check that there is enough calldata");
            return offset_;
        }
    }

    /// @notice Reads a 32-bit value from memory.
    /// @param _addr The address to read from.
    /// @param _proofIndex The index of the proof in the calldata.
    /// @return out_ The hashed MIPS state.
    function readMem(uint32 _addr, uint8 _proofIndex) internal pure returns (uint32 out_) {
        unchecked {
            // Compute the offset of the proof in the calldata.
            uint256 offset = proofOffset(_proofIndex);

            assembly {
                // Validate the address alignement.
                if and(_addr, 3) { revert(0, 0) }

                // Load the leaf value.
                let leaf := calldataload(offset)
                offset := add(offset, 32)

                // Convenience function to hash two nodes together in scratch space.
                function hashPair(a, b) -> h {
                    mstore(0, a)
                    mstore(32, b)
                    h := keccak256(0, 64)
                }

                // Start with the leaf node.
                // Work back up by combining with siblings, to reconstruct the root.
                let path := shr(5, _addr)
                let node := leaf
                for { let i := 0 } lt(i, 27) { i := add(i, 1) } {
                    let sibling := calldataload(offset)
                    offset := add(offset, 32)
                    switch and(shr(i, path), 1)
                    case 0 { node := hashPair(node, sibling) }
                    case 1 { node := hashPair(sibling, node) }
                }

                // Load the memory root from the first field of state.
                let memRoot := mload(0x80)

                // Verify the root matches.
                if iszero(eq(node, memRoot)) {
                    mstore(0, 0x0badf00d)
                    revert(0, 32)
                }

                // Bits to shift = (32 - 4 - (addr % 32)) * 8
                let shamt := shl(3, sub(sub(32, 4), and(_addr, 31)))
                out_ := and(shr(shamt, leaf), 0xFFffFFff)
            }
        }
    }

    /// @notice Writes a 32-bit value to memory.
    ///         This function first overwrites the part of the leaf.
    ///         Then it recomputes the memory merkle root.
    /// @param _addr The address to write to.
    /// @param _proofIndex The index of the proof in the calldata.
    /// @param _val The value to write.
    function writeMem(uint32 _addr, uint8 _proofIndex, uint32 _val) internal pure {
        unchecked {
            // Compute the offset of the proof in the calldata.
            uint256 offset = proofOffset(_proofIndex);

            assembly {
                // Validate the address alignement.
                if and(_addr, 3) { revert(0, 0) }

                // Load the leaf value.
                let leaf := calldataload(offset)
                let shamt := shl(3, sub(sub(32, 4), and(_addr, 31)))

                // Mask out 4 bytes, and OR in the value
                leaf := or(and(leaf, not(shl(shamt, 0xFFffFFff))), shl(shamt, _val))
                offset := add(offset, 32)

                // Convenience function to hash two nodes together in scratch space.
                function hashPair(a, b) -> h {
                    mstore(0, a)
                    mstore(32, b)
                    h := keccak256(0, 64)
                }

                // Start with the leaf node.
                // Work back up by combining with siblings, to reconstruct the root.
                let path := shr(5, _addr)
                let node := leaf
                for { let i := 0 } lt(i, 27) { i := add(i, 1) } {
                    let sibling := calldataload(offset)
                    offset := add(offset, 32)
                    switch and(shr(i, path), 1)
                    case 0 { node := hashPair(node, sibling) }
                    case 1 { node := hashPair(sibling, node) }
                }

                // Store the new memory root in the first field of state.
                mstore(0x80, node)
            }
        }
    }

    /// @notice Executes a single step of the vm.
    ///         Will revert if any required input state is missing.
    /// @param _stateData The encoded state witness data.
    /// @param _proof The encoded proof data for leaves within the MIPS VM's memory.
    /// @param _localContext The local key context for the preimage oracle. Optional, can be set as a constant
    ///                      if the caller only requires one set of local keys.
    function step(bytes calldata _stateData, bytes calldata _proof, bytes32 _localContext) public returns (bytes32) {
        unchecked {
            State memory state;

            // Packed calldata is ~6 times smaller than state size
            assembly {
                if iszero(eq(state, 0x80)) {
                    // expected state mem offset check
                    revert(0, 0)
                }
                if iszero(eq(mload(0x40), shl(5, 48))) {
                    // expected memory check
                    revert(0, 0)
                }
                if iszero(eq(_stateData.offset, 132)) {
                    // 32*4+4=132 expected state data offset
                    revert(0, 0)
                }
                if iszero(eq(_proof.offset, 420)) {
                    // 132+32+256=420 expected proof offset
                    revert(0, 0)
                }

                function putField(callOffset, memOffset, size) -> callOffsetOut, memOffsetOut {
                    // calldata is packed, thus starting left-aligned, shift-right to pad and right-align
                    let w := shr(shl(3, sub(32, size)), calldataload(callOffset))
                    mstore(memOffset, w)
                    callOffsetOut := add(callOffset, size)
                    memOffsetOut := add(memOffset, 32)
                }

                // Unpack state from calldata into memory
                let c := _stateData.offset // calldata offset
                let m := 0x80 // mem offset
                c, m := putField(c, m, 32) // memRoot
                c, m := putField(c, m, 32) // preimageKey
                c, m := putField(c, m, 4) // preimageOffset
                c, m := putField(c, m, 4) // pc
                c, m := putField(c, m, 4) // nextPC
                c, m := putField(c, m, 4) // lo
                c, m := putField(c, m, 4) // hi
                c, m := putField(c, m, 4) // heap
                c, m := putField(c, m, 1) // exitCode
                c, m := putField(c, m, 1) // exited
                c, m := putField(c, m, 8) // step

                // Unpack register calldata into memory
                mstore(m, add(m, 32)) // offset to registers
                m := add(m, 32)
                for { let i := 0 } lt(i, 32) { i := add(i, 1) } { c, m := putField(c, m, 4) }
            }

            // Don't change state once exited
            if (state.exited) {
                return outputState();
            }

            state.step += 1;

            // instruction fetch
            uint32 insn = readMem(state.pc, 0);
            uint32 opcode = insn >> 26; // 6-bits

            // j-type j/jal
            if (opcode == 2 || opcode == 3) {
                // Take top 4 bits of the next PC (its 256 MB region), and concatenate with the 26-bit offset
                uint32 target = (state.nextPC & 0xF0000000) | (insn & 0x03FFFFFF) << 2;
                return handleJump(opcode == 2 ? 0 : 31, target);
            }

            // register fetch
            uint32 rs; // source register 1 value
            uint32 rt; // source register 2 / temp value
            uint32 rtReg = (insn >> 16) & 0x1F;

            // R-type or I-type (stores rt)
            rs = state.registers[(insn >> 21) & 0x1F];
            uint32 rdReg = rtReg;

            if (opcode == 0 || opcode == 0x1c) {
                // R-type (stores rd)
                rt = state.registers[rtReg];
                rdReg = (insn >> 11) & 0x1F;
            } else if (opcode < 0x20) {
                // rt is SignExtImm
                // don't sign extend for andi, ori, xori
                if (opcode == 0xC || opcode == 0xD || opcode == 0xe) {
                    // ZeroExtImm
                    rt = insn & 0xFFFF;
                } else {
                    // SignExtImm
                    rt = SE(insn & 0xFFFF, 16);
                }
            } else if (opcode >= 0x28 || opcode == 0x22 || opcode == 0x26) {
                // store rt value with store
                rt = state.registers[rtReg];

                // store actual rt with lwl and lwr
                rdReg = rtReg;
            }

            if ((opcode >= 4 && opcode < 8) || opcode == 1) {
                return handleBranch(opcode, insn, rtReg, rs);
            }

            uint32 storeAddr = 0xFF_FF_FF_FF;
            // memory fetch (all I-type)
            // we do the load for stores also
            uint32 mem;
            if (opcode >= 0x20) {
                // M[R[rs]+SignExtImm]
                rs += SE(insn & 0xFFFF, 16);
                uint32 addr = rs & 0xFFFFFFFC;
                mem = readMem(addr, 1);
                if (opcode >= 0x28 && opcode != 0x30) {
                    // store
                    storeAddr = addr;
                    // store opcodes don't write back to a register
                    rdReg = 0;
                }
            }

            // ALU
            uint32 val = execute(insn, rs, rt, mem) & 0xffFFffFF; // swr outputs more than 4 bytes without the mask

            uint32 func = insn & 0x3f; // 6-bits
            if (opcode == 0 && func >= 8 && func < 0x1c) {
                if (func == 8 || func == 9) {
                    // jr/jalr
                    return handleJump(func == 8 ? 0 : rdReg, rs);
                }

                if (func == 0xa) {
                    // movz
                    return handleRd(rdReg, rs, rt == 0);
                }
                if (func == 0xb) {
                    // movn
                    return handleRd(rdReg, rs, rt != 0);
                }

                // syscall (can read and write)
                if (func == 0xC) {
                    return handleSyscall(_localContext);
                }

                // lo and hi registers
                // can write back
                if (func >= 0x10 && func < 0x1c) {
                    return handleHiLo(func, rs, rt, rdReg);
                }
            }

            // stupid sc, write a 1 to rt
            if (opcode == 0x38 && rtReg != 0) {
                state.registers[rtReg] = 1;
            }

            // write memory
            if (storeAddr != 0xFF_FF_FF_FF) {
                writeMem(storeAddr, 1, val);
            }

            // write back the value to destination register
            return handleRd(rdReg, val, true);
        }
    }

    /// @notice Execute an instruction.
    function execute(uint32 insn, uint32 rs, uint32 rt, uint32 mem) internal pure returns (uint32 out) {
        unchecked {
            uint32 opcode = insn >> 26; // 6-bits

            if (opcode == 0 || (opcode >= 8 && opcode < 0xF)) {
                uint32 func = insn & 0x3f; // 6-bits
                assembly {
                    // transform ArithLogI to SPECIAL
                    switch opcode
                    // addi
                    case 0x8 { func := 0x20 }
                    // addiu
                    case 0x9 { func := 0x21 }
                    // stli
                    case 0xA { func := 0x2A }
                    // sltiu
                    case 0xB { func := 0x2B }
                    // andi
                    case 0xC { func := 0x24 }
                    // ori
                    case 0xD { func := 0x25 }
                    // xori
                    case 0xE { func := 0x26 }
                }

                // sll
                if (func == 0x00) {
                    return rt << ((insn >> 6) & 0x1F);
                }
                // srl
                else if (func == 0x02) {
                    return rt >> ((insn >> 6) & 0x1F);
                }
                // sra
                else if (func == 0x03) {
                    uint32 shamt = (insn >> 6) & 0x1F;
                    return SE(rt >> shamt, 32 - shamt);
                }
                // sllv
                else if (func == 0x04) {
                    return rt << (rs & 0x1F);
                }
                // srlv
                else if (func == 0x6) {
                    return rt >> (rs & 0x1F);
                }
                // srav
                else if (func == 0x07) {
                    return SE(rt >> rs, 32 - rs);
                }
                // functs in range [0x8, 0x1b] are handled specially by other functions
                // Explicitly enumerate each funct in range to reduce code diff against Go Vm
                // jr
                else if (func == 0x08) {
                    return rs;
                }
                // jalr
                else if (func == 0x09) {
                    return rs;
                }
                // movz
                else if (func == 0x0a) {
                    return rs;
                }
                // movn
                else if (func == 0x0b) {
                    return rs;
                }
                // syscall
                else if (func == 0x0c) {
                    return rs;
                }
                // 0x0d - break not supported
                // sync
                else if (func == 0x0f) {
                    return rs;
                }
                // mfhi
                else if (func == 0x10) {
                    return rs;
                }
                // mthi
                else if (func == 0x11) {
                    return rs;
                }
                // mflo
                else if (func == 0x12) {
                    return rs;
                }
                // mtlo
                else if (func == 0x13) {
                    return rs;
                }
                // mult
                else if (func == 0x18) {
                    return rs;
                }
                // multu
                else if (func == 0x19) {
                    return rs;
                }
                // div
                else if (func == 0x1a) {
                    return rs;
                }
                // divu
                else if (func == 0x1b) {
                    return rs;
                }
                // The rest includes transformed R-type arith imm instructions
                // add
                else if (func == 0x20) {
                    return (rs + rt);
                }
                // addu
                else if (func == 0x21) {
                    return (rs + rt);
                }
                // sub
                else if (func == 0x22) {
                    return (rs - rt);
                }
                // subu
                else if (func == 0x23) {
                    return (rs - rt);
                }
                // and
                else if (func == 0x24) {
                    return (rs & rt);
                }
                // or
                else if (func == 0x25) {
                    return (rs | rt);
                }
                // xor
                else if (func == 0x26) {
                    return (rs ^ rt);
                }
                // nor
                else if (func == 0x27) {
                    return ~(rs | rt);
                }
                // slti
                else if (func == 0x2a) {
                    return int32(rs) < int32(rt) ? 1 : 0;
                }
                // sltiu
                else if (func == 0x2b) {
                    return rs < rt ? 1 : 0;
                } else {
                    revert("invalid instruction");
                }
            } else {
                // SPECIAL2
                if (opcode == 0x1C) {
                    uint32 func = insn & 0x3f; // 6-bits
                    // mul
                    if (func == 0x2) {
                        return uint32(int32(rs) * int32(rt));
                    }
                    // clz, clo
                    else if (func == 0x20 || func == 0x21) {
                        if (func == 0x20) {
                            rs = ~rs;
                        }
                        uint32 i = 0;
                        while (rs & 0x80000000 != 0) {
                            i++;
                            rs <<= 1;
                        }
                        return i;
                    }
                }
                // lui
                else if (opcode == 0x0F) {
                    return rt << 16;
                }
                // lb
                else if (opcode == 0x20) {
                    return SE((mem >> (24 - (rs & 3) * 8)) & 0xFF, 8);
                }
                // lh
                else if (opcode == 0x21) {
                    return SE((mem >> (16 - (rs & 2) * 8)) & 0xFFFF, 16);
                }
                // lwl
                else if (opcode == 0x22) {
                    uint32 val = mem << ((rs & 3) * 8);
                    uint32 mask = uint32(0xFFFFFFFF) << ((rs & 3) * 8);
                    return (rt & ~mask) | val;
                }
                // lw
                else if (opcode == 0x23) {
                    return mem;
                }
                // lbu
                else if (opcode == 0x24) {
                    return (mem >> (24 - (rs & 3) * 8)) & 0xFF;
                }
                //  lhu
                else if (opcode == 0x25) {
                    return (mem >> (16 - (rs & 2) * 8)) & 0xFFFF;
                }
                //  lwr
                else if (opcode == 0x26) {
                    uint32 val = mem >> (24 - (rs & 3) * 8);
                    uint32 mask = uint32(0xFFFFFFFF) >> (24 - (rs & 3) * 8);
                    return (rt & ~mask) | val;
                }
                //  sb
                else if (opcode == 0x28) {
                    uint32 val = (rt & 0xFF) << (24 - (rs & 3) * 8);
                    uint32 mask = 0xFFFFFFFF ^ uint32(0xFF << (24 - (rs & 3) * 8));
                    return (mem & mask) | val;
                }
                //  sh
                else if (opcode == 0x29) {
                    uint32 val = (rt & 0xFFFF) << (16 - (rs & 2) * 8);
                    uint32 mask = 0xFFFFFFFF ^ uint32(0xFFFF << (16 - (rs & 2) * 8));
                    return (mem & mask) | val;
                }
                //  swl
                else if (opcode == 0x2a) {
                    uint32 val = rt >> ((rs & 3) * 8);
                    uint32 mask = uint32(0xFFFFFFFF) >> ((rs & 3) * 8);
                    return (mem & ~mask) | val;
                }
                //  sw
                else if (opcode == 0x2b) {
                    return rt;
                }
                //  swr
                else if (opcode == 0x2e) {
                    uint32 val = rt << (24 - (rs & 3) * 8);
                    uint32 mask = uint32(0xFFFFFFFF) << (24 - (rs & 3) * 8);
                    return (mem & ~mask) | val;
                }
                // ll
                else if (opcode == 0x30) {
                    return mem;
                }
                // sc
                else if (opcode == 0x38) {
                    return rt;
                } else {
                    revert("invalid instruction");
                }
            }
            revert("invalid instruction");
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @title ISemver
/// @notice ISemver is a simple contract for ensuring that contracts are
///         versioned using semantic versioning.
interface ISemver {
    /// @notice Getter for the semantic version of the contract. This is not
    ///         meant to be used onchain but instead meant to be used by offchain
    ///         tooling.
    /// @return Semver contract version as a string.
    function version() external view returns (string memory);
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.15;

/// @title IPreimageOracle
/// @notice Interface for a preimage oracle.
interface IPreimageOracle {
    /// @notice Reads a preimage from the oracle.
    /// @param _key The key of the preimage to read.
    /// @param _offset The offset of the preimage to read.
    /// @return dat_ The preimage data.
    /// @return datLen_ The length of the preimage data.
    function readPreimage(bytes32 _key, uint256 _offset) external view returns (bytes32 dat_, uint256 datLen_);

    /// @notice Loads of local data part into the preimage oracle.
    /// @param _ident The identifier of the local data.
    /// @param _localContext The local key context for the preimage oracle. Optionally, can be set as a constant
    ///                      if the caller only requires one set of local keys.
    /// @param _word The local data word.
    /// @param _size The number of bytes in `_word` to load.
    /// @param _partOffset The offset of the local data part to write to the oracle.
    /// @dev The local data parts are loaded into the preimage oracle under the context
    ///      of the caller - no other account can write to the caller's context
    ///      specific data.
    ///
    ///      There are 5 local data identifiers:
    ///      ┌────────────┬────────────────────────┐
    ///      │ Identifier │      Data              │
    ///      ├────────────┼────────────────────────┤
    ///      │          1 │ L1 Head Hash (bytes32) │
    ///      │          2 │ Output Root (bytes32)  │
    ///      │          3 │ Root Claim (bytes32)   │
    ///      │          4 │ L2 Block Number (u64)  │
    ///      │          5 │ Chain ID (u64)         │
    ///      └────────────┴────────────────────────┘
    function loadLocalData(
        uint256 _ident,
        bytes32 _localContext,
        bytes32 _word,
        uint256 _size,
        uint256 _partOffset
    )
        external
        returns (bytes32 key_);

    /// @notice Prepares a preimage to be read by keccak256 key, starting at the given offset and up to 32 bytes
    ///         (clipped at preimage length, if out of data).
    /// @param _partOffset The offset of the preimage to read.
    /// @param _preimage The preimage data.
    function loadKeccak256PreimagePart(uint256 _partOffset, bytes calldata _preimage) external;

    /// @notice Prepares a preimage to be read by sha256 key, starting at the given offset and up to 32 bytes
    ///         (clipped at preimage length, if out of data).
    /// @param _partOffset The offset of the preimage to read.
    /// @param _preimage The preimage data.
    function loadSha256PreimagePart(uint256 _partOffset, bytes calldata _preimage) external;

    /// @notice Verifies that `p(_z) = _y` given `_commitment` that corresponds to the polynomial `p(x)` and a KZG
    //          proof. The value `y` is the pre-image, and the preimage key is `5 ++ keccak256(_commitment ++ z)[1:]`.
    /// @param _z Big endian point value. Part of the preimage key.
    /// @param _y Big endian point value. The preimage for the key.
    /// @param _commitment The commitment to the polynomial. 48 bytes, part of the preimage key.
    /// @param _proof The KZG proof, part of the preimage key.
    /// @param _partOffset The offset of the preimage to store.
    function loadBlobPreimagePart(
        uint256 _z,
        uint256 _y,
        bytes calldata _commitment,
        bytes calldata _proof,
        uint256 _partOffset
    )
        external;

    /// @notice Prepares a precompile result to be read by a precompile key for the specified offset.
    ///         The precompile result data is a concatenation of the precompile call status byte and its return data.
    ///         The preimage key is `6 ++ keccak256(precompile ++ input)[1:]`.
    /// @param _partOffset The offset of the precompile result being loaded.
    /// @param _precompile The precompile address
    /// @param _input The input to the precompile call.
    function loadPrecompilePreimagePart(uint256 _partOffset, address _precompile, bytes calldata _input) external;
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.15;

/// @title PreimageKeyLib
/// @notice Shared utilities for localizing local keys in the preimage oracle.
library PreimageKeyLib {
    /// @notice Generates a context-specific local key for the given local data identifier.
    /// @dev See `localize` for a description of the localization operation.
    /// @param _ident The identifier of the local data. [0, 32) bytes in size.
    /// @param _localContext The local context for the key.
    /// @return key_ The context-specific local key.
    function localizeIdent(uint256 _ident, bytes32 _localContext) internal view returns (bytes32 key_) {
        assembly {
            // Set the type byte in the given identifier to `1` (Local). We only care about
            // the [1, 32) bytes in this value.
            key_ := or(shl(248, 1), and(_ident, not(shl(248, 0xFF))))
        }
        // Localize the key with the given local context.
        key_ = localize(key_, _localContext);
    }

    /// @notice Localizes a given local data key for the caller's context.
    /// @dev The localization operation is defined as:
    ///      localize(k) = H(k .. sender .. local_context) & ~(0xFF << 248) | (0x01 << 248)
    ///      where H is the Keccak-256 hash function.
    /// @param _key The local data key to localize.
    /// @param _localContext The local context for the key.
    /// @return localizedKey_ The localized local data key.
    function localize(bytes32 _key, bytes32 _localContext) internal view returns (bytes32 localizedKey_) {
        assembly {
            // Grab the current free memory pointer to restore later.
            let ptr := mload(0x40)
            // Store the local data key and caller next to each other in memory for hashing.
            mstore(0, _key)
            mstore(0x20, caller())
            mstore(0x40, _localContext)
            // Localize the key with the above `localize` operation.
            localizedKey_ := or(and(keccak256(0, 0x60), not(shl(248, 0xFF))), shl(248, 1))
            // Restore the free memory pointer.
            mstore(0x40, ptr)
        }
    }

    /// @notice Computes and returns the key for a global keccak pre-image.
    /// @param _preimage The pre-image.
    /// @return key_ The pre-image key.
    function keccak256PreimageKey(bytes memory _preimage) internal pure returns (bytes32 key_) {
        assembly {
            // Grab the size of the `_preimage`
            let size := mload(_preimage)

            // Compute the pre-image keccak256 hash (aka the pre-image key)
            let h := keccak256(add(_preimage, 0x20), size)

            // Mask out prefix byte, replace with type 2 byte
            key_ := or(and(h, not(shl(248, 0xFF))), shl(248, 2))
        }
    }
}

{
  "remappings": [
    "@openzeppelin/contracts-upgradeable/=lib/openzeppelin-contracts-upgradeable/contracts/",
    "@openzeppelin/contracts/=lib/openzeppelin-contracts/contracts/",
    "@rari-capital/solmate/=lib/solmate/",
    "@cwia/=lib/clones-with-immutable-args/src/",
    "@lib-keccak/=lib/lib-keccak/contracts/lib/",
    "forge-std/=lib/forge-std/src/",
    "ds-test/=lib/forge-std/lib/ds-test/src/",
    "safe-contracts/=lib/safe-contracts/contracts/",
    "kontrol-cheatcodes/=lib/kontrol-cheatcodes/src/",
    "solady/=lib/solady/src/",
    "@solady-test/=lib/lib-keccak/lib/solady/test/",
    "@solady/=lib/lib-keccak/lib/solady/src/",
    "clones-with-immutable-args/=lib/clones-with-immutable-args/src/",
    "lib-keccak/=lib/lib-keccak/contracts/",
    "openzeppelin-contracts-upgradeable/=lib/openzeppelin-contracts-upgradeable/",
    "openzeppelin-contracts/=lib/openzeppelin-contracts/",
    "solmate/=lib/solmate/src/"
  ],
  "optimizer": {
    "enabled": true,
    "runs": 999999
  },
  "metadata": {
    "useLiteralContent": false,
    "bytecodeHash": "none"
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "evmVersion": "london",
  "viaIR": false,
  "libraries": {}
}

• No Contract Security Audit Submitted- Submit Audit Here

[{"inputs":[{"internalType":"contract IPreimageOracle","name":"_oracle","type":"address"}],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"BRK_START","outputs":[{"internalType":"uint32","name":"","type":"uint32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"oracle","outputs":[{"internalType":"contract IPreimageOracle","name":"oracle_","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes","name":"_stateData","type":"bytes"},{"internalType":"bytes","name":"_proof","type":"bytes"},{"internalType":"bytes32","name":"_localContext","type":"bytes32"}],"name":"step","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"version","outputs":[{"internalType":"string","name":"","type":"string"}],"stateMutability":"view","type":"function"}]

0x608060405234801561001057600080fd5b506004361061004c5760003560e01c8063155633fe1461005157806354fd4d50146100765780637dc0d1d0146100bf578063e14ced3214610103575b600080fd5b61005c634000000081565b60405163ffffffff90911681526020015b60405180910390f35b6100b26040518060400160405280600581526020017f302e312e3000000000000000000000000000000000000000000000000000000081525081565b60405161006d9190611d39565b60405173ffffffffffffffffffffffffffffffffffffffff7f000000000000000000000000089a4754538b74ff63bc6abead7a95973ab0357216815260200161006d565b610116610111366004611df5565b610124565b60405190815260200161006d565b600061012e611caf565b6080811461013b57600080fd5b6040516106001461014b57600080fd5b6084871461015857600080fd5b6101a4851461016657600080fd5b8635608052602087013560a052604087013560e090811c60c09081526044890135821c82526048890135821c61010052604c890135821c610120526050890135821c61014052605489013590911c61016052605888013560f890811c610180526059890135901c6101a052605a880135901c6101c0526102006101e0819052606288019060005b602081101561021157823560e01c82526004909201916020909101906001016101ed565b5050508061012001511561022f5761022761066f565b915050610666565b6101408101805160010167ffffffffffffffff1690526060810151600090610257908261078b565b9050603f601a82901c16600281148061027657508063ffffffff166003145b156102cb5760006002836303ffffff1663ffffffff16901b846080015163f0000000161790506102c08263ffffffff166002146102b457601f6102b7565b60005b60ff1682610847565b945050505050610666565b6101608301516000908190601f601086901c81169190601587901c16602081106102f7576102f7611e69565b602002015192508063ffffffff8516158061031857508463ffffffff16601c145b1561034f578661016001518263ffffffff166020811061033a5761033a611e69565b6020020151925050601f600b86901c1661040b565b60208563ffffffff1610156103b1578463ffffffff16600c148061037957508463ffffffff16600d145b8061038a57508463ffffffff16600e145b1561039b578561ffff16925061040b565b6103aa8661ffff166010610938565b925061040b565b60288563ffffffff161015806103cd57508463ffffffff166022145b806103de57508463ffffffff166026145b1561040b578661016001518263ffffffff166020811061040057610400611e69565b602002015192508190505b60048563ffffffff1610158015610428575060088563ffffffff16105b8061043957508463ffffffff166001145b156104585761044a858784876109ab565b975050505050505050610666565b63ffffffff60006020878316106104bd576104788861ffff166010610938565b9095019463fffffffc861661048e81600161078b565b915060288863ffffffff16101580156104ae57508763ffffffff16603014155b156104bb57809250600093505b505b60006104cb89888885610bbb565b63ffffffff9081169150603f8a169089161580156104f0575060088163ffffffff1610155b80156105025750601c8163ffffffff16105b156105df578063ffffffff166008148061052257508063ffffffff166009145b15610559576105478163ffffffff1660081461053e5785610541565b60005b89610847565b9b505050505050505050505050610666565b8063ffffffff16600a0361057957610547858963ffffffff8a161561134b565b8063ffffffff16600b0361059a57610547858963ffffffff8a16151561134b565b8063ffffffff16600c036105b1576105478d611431565b60108163ffffffff16101580156105ce5750601c8163ffffffff16105b156105df5761054781898988611968565b8863ffffffff1660381480156105fa575063ffffffff861615155b1561062f5760018b61016001518763ffffffff166020811061061e5761061e611e69565b63ffffffff90921660209290920201525b8363ffffffff1663ffffffff1461064c5761064c84600184611b62565b6106588583600161134b565b9b5050505050505050505050505b95945050505050565b60408051608051815260a051602082015260dc519181019190915260fc51604482015261011c51604882015261013c51604c82015261015c51605082015261017c5160548201526101805161019f5160588301526101a0516101bf5160598401526101d851605a840152600092610200929091606283019190855b602081101561070e57601c86015184526020909501946004909301926001016106ea565b506000835283830384a060009450806001811461072e5760039550610756565b828015610746576001811461074f5760029650610754565b60009650610754565b600196505b505b50505081900390207effffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff1660f89190911b17919050565b60008061079783611c06565b905060038416156107a757600080fd5b6020810190358460051c8160005b601b81101561080d5760208501943583821c60011680156107dd57600181146107f257610803565b60008481526020839052604090209350610803565b600082815260208590526040902093505b50506001016107b5565b50608051915081811461082857630badf00d60005260206000fd5b5050601f94909416601c0360031b9390931c63ffffffff169392505050565b6000610851611caf565b60809050806060015160040163ffffffff16816080015163ffffffff16146108da576040517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601260248201527f6a756d7020696e2064656c617920736c6f74000000000000000000000000000060448201526064015b60405180910390fd5b60608101805160808301805163ffffffff90811690935285831690529085161561093057806008018261016001518663ffffffff166020811061091f5761091f611e69565b63ffffffff90921660209290920201525b61066661066f565b600063ffffffff8381167fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff80850183169190911c821615159160016020869003821681901b830191861691821b92911b0182610995576000610997565b815b90861663ffffffff16179250505092915050565b60006109b5611caf565b608090506000816060015160040163ffffffff16826080015163ffffffff1614610a3b576040517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601460248201527f6272616e636820696e2064656c617920736c6f7400000000000000000000000060448201526064016108d1565b8663ffffffff1660041480610a5657508663ffffffff166005145b15610ad25760008261016001518663ffffffff1660208110610a7a57610a7a611e69565b602002015190508063ffffffff168563ffffffff16148015610aa257508763ffffffff166004145b80610aca57508063ffffffff168563ffffffff1614158015610aca57508763ffffffff166005145b915050610b4f565b8663ffffffff16600603610aef5760008460030b13159050610b4f565b8663ffffffff16600703610b0b5760008460030b139050610b4f565b8663ffffffff16600103610b4f57601f601087901c166000819003610b345760008560030b1291505b8063ffffffff16600103610b4d5760008560030b121591505b505b606082018051608084015163ffffffff169091528115610b95576002610b7a8861ffff166010610938565b63ffffffff90811690911b8201600401166080840152610ba7565b60808301805160040163ffffffff1690525b610baf61066f565b98975050505050505050565b6000603f601a86901c16801580610bea575060088163ffffffff1610158015610bea5750600f8163ffffffff16105b1561104057603f86168160088114610c315760098114610c3a57600a8114610c4357600b8114610c4c57600c8114610c5557600d8114610c5e57600e8114610c6757610c6c565b60209150610c6c565b60219150610c6c565b602a9150610c6c565b602b9150610c6c565b60249150610c6c565b60259150610c6c565b602691505b508063ffffffff16600003610c935750505063ffffffff8216601f600686901c161b611343565b8063ffffffff16600203610cb95750505063ffffffff8216601f600686901c161c611343565b8063ffffffff16600303610cef57601f600688901c16610ce563ffffffff8716821c6020839003610938565b9350505050611343565b8063ffffffff16600403610d115750505063ffffffff8216601f84161b611343565b8063ffffffff16600603610d335750505063ffffffff8216601f84161c611343565b8063ffffffff16600703610d6657610d5d8663ffffffff168663ffffffff16901c87602003610938565b92505050611343565b8063ffffffff16600803610d7e578592505050611343565b8063ffffffff16600903610d96578592505050611343565b8063ffffffff16600a03610dae578592505050611343565b8063ffffffff16600b03610dc6578592505050611343565b8063ffffffff16600c03610dde578592505050611343565b8063ffffffff16600f03610df6578592505050611343565b8063ffffffff16601003610e0e578592505050611343565b8063ffffffff16601103610e26578592505050611343565b8063ffffffff16601203610e3e578592505050611343565b8063ffffffff16601303610e56578592505050611343565b8063ffffffff16601803610e6e578592505050611343565b8063ffffffff16601903610e86578592505050611343565b8063ffffffff16601a03610e9e578592505050611343565b8063ffffffff16601b03610eb6578592505050611343565b8063ffffffff16602003610ecf57505050828201611343565b8063ffffffff16602103610ee857505050828201611343565b8063ffffffff16602203610f0157505050818303611343565b8063ffffffff16602303610f1a57505050818303611343565b8063ffffffff16602403610f3357505050828216611343565b8063ffffffff16602503610f4c57505050828217611343565b8063ffffffff16602603610f6557505050828218611343565b8063ffffffff16602703610f7f5750505082821719611343565b8063ffffffff16602a03610fb0578460030b8660030b12610fa1576000610fa4565b60015b60ff1692505050611343565b8063ffffffff16602b03610fd8578463ffffffff168663ffffffff1610610fa1576000610fa4565b6040517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601360248201527f696e76616c696420696e737472756374696f6e0000000000000000000000000060448201526064016108d1565b50610fd8565b8063ffffffff16601c036110c457603f8616600281900361106657505050828202611343565b8063ffffffff166020148061108157508063ffffffff166021145b1561103a578063ffffffff16602003611098579419945b60005b63800000008716156110ba576401fffffffe600197881b16960161109b565b9250611343915050565b8063ffffffff16600f036110e657505065ffffffff0000601083901b16611343565b8063ffffffff166020036111225761111a8560031660080260180363ffffffff168463ffffffff16901c60ff166008610938565b915050611343565b8063ffffffff166021036111575761111a8560021660080260100363ffffffff168463ffffffff16901c61ffff166010610938565b8063ffffffff1660220361118657505063ffffffff60086003851602811681811b198416918316901b17611343565b8063ffffffff1660230361119d5782915050611343565b8063ffffffff166024036111cf578460031660080260180363ffffffff168363ffffffff16901c60ff16915050611343565b8063ffffffff16602503611202578460021660080260100363ffffffff168363ffffffff16901c61ffff16915050611343565b8063ffffffff1660260361123457505063ffffffff60086003851602601803811681811c198416918316901c17611343565b8063ffffffff1660280361126a57505060ff63ffffffff60086003861602601803811682811b9091188316918416901b17611343565b8063ffffffff166029036112a157505061ffff63ffffffff60086002861602601003811682811b9091188316918416901b17611343565b8063ffffffff16602a036112d057505063ffffffff60086003851602811681811c198316918416901c17611343565b8063ffffffff16602b036112e75783915050611343565b8063ffffffff16602e0361131957505063ffffffff60086003851602601803811681811b198316918416901b17611343565b8063ffffffff166030036113305782915050611343565b8063ffffffff16603803610fd857839150505b949350505050565b6000611355611caf565b506080602063ffffffff8616106113c8576040517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152600e60248201527f76616c696420726567697374657200000000000000000000000000000000000060448201526064016108d1565b63ffffffff8516158015906113da5750825b1561140e57838161016001518663ffffffff16602081106113fd576113fd611e69565b63ffffffff90921660209290920201525b60808101805163ffffffff8082166060850152600490910116905261066661066f565b600061143b611caf565b506101e051604081015160808083015160a084015160c09094015191936000928392919063ffffffff8616610ffa036114b55781610fff81161561148457610fff811661100003015b8363ffffffff166000036114ab5760e08801805163ffffffff8382011690915295506114af565b8395505b50611927565b8563ffffffff16610fcd036114d05763400000009450611927565b8563ffffffff16611018036114e85760019450611927565b8563ffffffff166110960361151e57600161012088015260ff831661010088015261151161066f565b9998505050505050505050565b8563ffffffff16610fa30361178a5763ffffffff831615611927577ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb63ffffffff8416016117445760006115798363fffffffc16600161078b565b60208901519091508060001a6001036115e857604080516000838152336020528d83526060902091527effffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167f01000000000000000000000000000000000000000000000000000000000000001790505b6040808a015190517fe03110e10000000000000000000000000000000000000000000000000000000081526004810183905263ffffffff9091166024820152600090819073ffffffffffffffffffffffffffffffffffffffff7f000000000000000000000000089a4754538b74ff63bc6abead7a95973ab03572169063e03110e1906044016040805180830381865afa158015611689573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906116ad9190611e98565b915091506003861680600403828110156116c5578092505b50818610156116d2578591505b8260088302610100031c9250826008828460040303021b9250600180600883600403021b036001806008858560040303021b039150811981169050838119871617955050506117298663fffffffc16600186611b62565b60408b018051820163ffffffff169052975061178592505050565b7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd63ffffffff84160161177957809450611927565b63ffffffff9450600993505b611927565b8563ffffffff16610fa40361187b5763ffffffff8316600114806117b4575063ffffffff83166002145b806117c5575063ffffffff83166004145b156117d257809450611927565b7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa63ffffffff8416016117795760006118128363fffffffc16600161078b565b6020890151909150600384166004038381101561182d578093505b83900360089081029290921c7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff600193850293841b0116911b17602088015260006040880152935083611927565b8563ffffffff16610fd703611927578163ffffffff1660030361191b5763ffffffff831615806118b1575063ffffffff83166005145b806118c2575063ffffffff83166003145b156118d05760009450611927565b63ffffffff8316600114806118eb575063ffffffff83166002145b806118fc575063ffffffff83166006145b8061190d575063ffffffff83166004145b156117795760019450611927565b63ffffffff9450601693505b6101608701805163ffffffff808816604090920191909152905185821660e09091015260808801805180831660608b0152600401909116905261151161066f565b6000611972611caf565b506080600063ffffffff8716601003611990575060c0810151611af9565b8663ffffffff166011036119af5763ffffffff861660c0830152611af9565b8663ffffffff166012036119c8575060a0810151611af9565b8663ffffffff166013036119e75763ffffffff861660a0830152611af9565b8663ffffffff16601803611a1b5763ffffffff600387810b9087900b02602081901c821660c08501521660a0830152611af9565b8663ffffffff16601903611a4c5763ffffffff86811681871602602081901c821660c08501521660a0830152611af9565b8663ffffffff16601a03611aa2578460030b8660030b81611a6f57611a6f611ebc565b0763ffffffff1660c0830152600385810b9087900b81611a9157611a91611ebc565b0563ffffffff1660a0830152611af9565b8663ffffffff16601b03611af9578463ffffffff168663ffffffff1681611acb57611acb611ebc565b0663ffffffff90811660c084015285811690871681611aec57611aec611ebc565b0463ffffffff1660a08301525b63ffffffff841615611b3457808261016001518563ffffffff1660208110611b2357611b23611e69565b63ffffffff90921660209290920201525b60808201805163ffffffff80821660608601526004909101169052611b5761066f565b979650505050505050565b6000611b6d83611c06565b90506003841615611b7d57600080fd5b6020810190601f8516601c0360031b83811b913563ffffffff90911b1916178460051c60005b601b811015611bfb5760208401933582821c6001168015611bcb5760018114611be057611bf1565b60008581526020839052604090209450611bf1565b600082815260208690526040902094505b5050600101611ba3565b505060805250505050565b60ff8116610380026101a4810190369061052401811015611ca9576040517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152602360248201527f636865636b207468617420746865726520697320656e6f7567682063616c6c6460448201527f617461000000000000000000000000000000000000000000000000000000000060648201526084016108d1565b50919050565b6040805161018081018252600080825260208201819052918101829052606081018290526080810182905260a0810182905260c0810182905260e08101829052610100810182905261012081018290526101408101919091526101608101611d15611d1a565b905290565b6040518061040001604052806020906020820280368337509192915050565b600060208083528351808285015260005b81811015611d6657858101830151858201604001528201611d4a565b81811115611d78576000604083870101525b50601f017fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe016929092016040019392505050565b60008083601f840112611dbe57600080fd5b50813567ffffffffffffffff811115611dd657600080fd5b602083019150836020828501011115611dee57600080fd5b9250929050565b600080600080600060608688031215611e0d57600080fd5b853567ffffffffffffffff80821115611e2557600080fd5b611e3189838a01611dac565b90975095506020880135915080821115611e4a57600080fd5b50611e5788828901611dac565b96999598509660400135949350505050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b60008060408385031215611eab57600080fd5b505080516020909101519092909150565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601260045260246000fdfea164736f6c634300080f000a