// File: lib/memmove/src/Array.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

// create a user defined type that is a pointer to memory
type Array is bytes32;

/* 
Memory layout:
offset..offset+32: current first unset element (cheaper to have it first most of the time), aka "length"
offset+32..offset+64: capacity of elements in array
offset+64..offset+64+(capacity*32): elements

nominclature:
 - capacity: total number of elements able to be stored prior to having to perform a move
 - length/current unset index: the number of defined items in the array

a dynamic array is such a primitive data structure that it should be extremely optimized. so everything is in assembly
*/
library ArrayLib {
    function newArray(uint256 capacityHint) internal pure returns (Array s) {
        assembly ("memory-safe") {
            // grab free mem ptr
            s := mload(0x40)
            
            // update free memory pointer based on array's layout:
            //  + 32 bytes for capacity
            //  + 32 bytes for current unset pointer/length
            //  + 32*capacity
            //  + current free memory pointer (s is equal to mload(0x40)) 
            mstore(0x40, add(s, mul(add(0x02, capacityHint), 0x20)))

            // store the capacity in the second word (see memory layout above)
            mstore(add(0x20, s), capacityHint)

            // store length as 0 because otherwise the compiler may have rugged us
            mstore(s, 0x00)
        }
    }

    // capacity of elements before a move would occur
    function capacity(Array self) internal pure returns (uint256 cap) {
        assembly ("memory-safe") {
            cap := mload(add(0x20, self))
        }
    }

    // number of set elements in the array
    function length(Array self) internal pure returns (uint256 len) {
        assembly ("memory-safe") {
            len := mload(self)
        }
    }

    // gets a ptr to an element
    function unsafe_ptrToElement(Array self, uint256 index) internal pure returns (bytes32 ptr) {
        assembly ("memory-safe") {
            ptr := add(self, mul(0x20, add(0x02, index)))
        }
    }

    // overloaded to default push function with 0 overallocation
    function push(Array self, uint256 elem) internal view returns (Array ret) {
        ret = push(self, elem, 0);
    }

    // push an element safely into the array - will perform a move if needed as well as updating the free memory pointer
    // returns the new pointer.
    //
    // WARNING: if a move occurs, the user *must* update their pointer, thus the returned updated pointer. safest
    // method is *always* updating the pointer
    function push(Array self, uint256 elem, uint256 overalloc) internal view returns (Array) {
        Array ret;
        assembly ("memory-safe") {
            // set the return ptr
            ret := self
            // check if length == capacity (meaning no more preallocated space)
            switch eq(mload(self), mload(add(0x20, self))) 
            case 1 {
                // optimization: check if the free memory pointer is equal to the end of the preallocated space
                // if it is, we can just natively extend the array because nothing has been allocated *after*
                // us. i.e.:
                // evm_memory = [00...free_mem_ptr...Array.length...Array.lastElement]
                // this check compares free_mem_ptr to Array.lastElement, if they are equal, we know there is nothing after
                //
                // optimization 2: length == capacity in this case (per above) so we can avoid an add to look at capacity
                // to calculate where the last element it
                switch eq(mload(0x40), add(self, mul(add(0x02, mload(self)), 0x20))) 
                case 1 {
                    // the free memory pointer hasn't moved, i.e. free_mem_ptr == Array.lastElement, just extend

                    // Add 1 to the Array.capacity
                    mstore(add(0x20, self), add(0x01, mload(add(0x20, self))))

                    // the free mem ptr is where we want to place the next element
                    mstore(mload(0x40), elem)

                    // move the free_mem_ptr by a word (32 bytes. 0x20 in hex)
                    mstore(0x40, add(0x20, mload(0x40)))

                    // update the length
                    mstore(self, add(0x01, mload(self)))
                }
                default {
                    // we couldn't do the above optimization, use the `identity` precompile to perform a memory move
                    
                    // move the array to the free mem ptr by using the identity precompile which just returns the values
                    let array_size := mul(add(0x02, mload(self)), 0x20)
                    pop(
                        staticcall(
                            gas(), // pass gas
                            0x04,  // call identity precompile address 
                            self,  // arg offset == pointer to self
                            array_size,  // arg size: capacity + 2 * word_size (we add 2 to capacity to account for capacity and length words)
                            mload(0x40), // set return buffer to free mem ptr
                            array_size   // identity just returns the bytes of the input so equal to argsize 
                        )
                    )
                    
                    // add the element to the end of the array
                    mstore(add(mload(0x40), array_size), elem)

                    // add to the capacity
                    mstore(
                        add(0x20, mload(0x40)), // free_mem_ptr + word == new capacity word
                        add(add(0x01, overalloc), mload(add(0x20, mload(0x40)))) // add one + overalloc to capacity
                    )

                    // add to length
                    mstore(mload(0x40), add(0x01, mload(mload(0x40))))

                    // set the return ptr to the new array
                    ret := mload(0x40)

                    // update free memory pointer
                    // we also over allocate if requested
                    mstore(0x40, add(add(array_size, add(0x20, mul(overalloc, 0x20))), mload(0x40)))
                }
            }
            default {
                // we have capacity for the new element, store it
                mstore(
                    // mem_loc := capacity_ptr + (capacity + 2) * 32
                    // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                    add(self, mul(add(0x02, mload(self)), 0x20)), 
                    elem
                )

                // update length
                mstore(self, add(0x01, mload(self)))
            }
        }
        return ret;
    }

    // used when you *guarantee* that the array has the capacity available to be pushed to.
    // no need to update return pointer in this case
    //
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_push(Array self, uint256 elem) internal pure {
        assembly ("memory-safe") {
            mstore(
                // mem_loc := capacity_ptr + (capacity + 2) * 32
                // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                add(self, mul(add(0x02, mload(self)), 0x20)),
                elem
            )

            // update length
            mstore(self, add(0x01, mload(self)))
        }
    }

    // used when you *guarantee* that the index, i, is within the bounds of length
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_set(Array self, uint256 i, uint256 value) internal pure {
        assembly ("memory-safe") {
            mstore(add(self, mul(0x20, add(0x02, i))), value)
        }
    }

    function set(Array self, uint256 i, uint256 value) internal pure {
        // if the index is greater than or equal to the capacity, revert
        assembly ("memory-safe") {
            if lt(mload(add(0x20, self)), i) {
                // emit compiler native Panic(uint256) style error
                mstore(0x00, 0x4e487b7100000000000000000000000000000000000000000000000000000000)
                mstore(0x04, 0x32)
                revert(0, 0x24)
            }
            mstore(add(self, mul(0x20, add(0x02, i))), value)
        }
    }

    // used when you *guarantee* that the index, i, is within the bounds of length
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_get(Array self, uint256 i) internal pure returns (uint256 s) {
        assembly ("memory-safe") {
            s := mload(add(self, mul(0x20, add(0x02, i))))
        }
    }

    // a safe `get` that checks capacity
    function get(Array self, uint256 i) internal pure returns (uint256 s) {
        // if the index is greater than or equal to the capacity, revert
        assembly ("memory-safe") {
            if lt(mload(add(0x20, self)), i) {
                // emit compiler native Panic(uint256) style error
                mstore(0x00, 0x4e487b7100000000000000000000000000000000000000000000000000000000)
                mstore(0x04, 0x32)
                revert(0, 0x24)
            }
            s := mload(add(self, mul(0x20, add(0x02, i))))
        }
    }

    function pop(Array self) internal pure returns (uint256 s) {
        assembly ("memory-safe") {
            let len := mload(self)
            let last := add(self, mul(0x20, add(0x01, len)))
            s := mload(last)
            mstore(last, 0x00)
        }
    } 
}

// A wrapper around the lower level array that does one layer of indirection so that the pointer
// the user has to hold never moves. Effectively a reference to the array. i.e. push doesn't return anything
// because it doesnt need to. Slightly less efficient, generally adds 1-3 memops per func
library RefArrayLib {
    using ArrayLib for Array;

    function newArray(uint16 capacityHint) internal pure returns (Array s) {
        Array referenced = ArrayLib.newArray(capacityHint);
        assembly ("memory-safe") {
            // grab free memory pointer for return value
            s := mload(0x40)
            // store referenced array in s
            mstore(mload(0x40), referenced)
            // update free mem ptr
            mstore(0x40, add(mload(0x40), 0x20))
        }
    }

    // capacity of elements before a move would occur
    function capacity(Array self) internal pure returns (uint256 cap) {
        assembly ("memory-safe") {
            cap := mload(add(0x20, mload(self)))
        }
    }

    // number of set elements in the array
    function length(Array self) internal pure returns (uint256 len) {
        assembly ("memory-safe") {
            len := mload(mload(self))
        }
    }

    // gets a ptr to an element
    function unsafe_ptrToElement(Array self, uint256 index) internal pure returns (bytes32 ptr) {
        assembly ("memory-safe") {
            ptr := add(mload(self), mul(0x20, add(0x02, index)))
        }
    }

    // overloaded to default push function with 0 overallocation
    function push(Array self, uint256 elem) internal view {
        push(self, elem, 0);
    }

    // dereferences the array
    function deref(Array self) internal pure returns (Array s) {
        assembly ("memory-safe") {
            s := mload(self)
        }
    }

    // push an element safely into the array - will perform a move if needed as well as updating the free memory pointer
    function push(Array self, uint256 elem, uint256 overalloc) internal view {
        Array newArr = deref(self).push(elem, overalloc);
        assembly ("memory-safe") {
            // we always just update the pointer because it is cheaper to do so than check whether
            // the array moved
            mstore(self, newArr)
        }
    }

    // used when you *guarantee* that the array has the capacity available to be pushed to.
    // no need to update return pointer in this case
    function unsafe_push(Array self, uint256 elem) internal pure {
        // no need to update pointer
        deref(self).unsafe_push(elem);
    }

    // used when you *guarantee* that the index, i, is within the bounds of length
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_set(Array self, uint256 i, uint256 value) internal pure {
        deref(self).unsafe_set(i, value);
    }

    function set(Array self, uint256 i, uint256 value) internal pure {
        deref(self).set(i, value);
    }

    // used when you *guarantee* that the index, i, is within the bounds of length
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_get(Array self, uint256 i) internal pure returns (uint256 s) {
        s = deref(self).unsafe_get(i);
    }

    // a safe `get` that checks capacity
    function get(Array self, uint256 i) internal pure returns (uint256 s) {
        s = deref(self).get(i);
    }
}
// File: lib/memmove/src/LinkedList.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

import "./Array.sol";

type LinkedList is bytes32;

// A basic wrapper around an array that returns a pointer to an element in
// the array. Unfortunately without generics, the user has to cast from a pointer to a type
// held in memory manually
//
// is indexable
//
// data structure:
//   |-----------------------------|                      |-------|
//   |                             v                      |       v  
// [ptr, ptr2, ptr3, ptr4]         {value, other value, next}     {value, other value, next}
//        |                                                       ^
//        |-------------------------------------------------------|
//
// where `mload(add(ptr, linkingOffset))` (aka `next`) == ptr2

library IndexableLinkedListLib {
    using ArrayLib for Array;

    function newIndexableLinkedList(uint16 capacityHint) internal pure returns (LinkedList s) {
        s = LinkedList.wrap(Array.unwrap(ArrayLib.newArray(capacityHint)));
    }

    function capacity(LinkedList self) internal pure returns (uint256 cap) {
        cap = Array.wrap(LinkedList.unwrap(self)).capacity();
    }

    function length(LinkedList self) internal pure returns (uint256 len) {
        len = Array.wrap(LinkedList.unwrap(self)).length();
    }

    function push_no_link(LinkedList self, bytes32 element) internal view returns (LinkedList s) {
        s = LinkedList.wrap(
            Array.unwrap(
                Array.wrap(LinkedList.unwrap(self)).push(uint256(element))
            )
        );
    }

    // linkingOffset is the offset from the element ptr that is written to 
    function push_and_link(LinkedList self, bytes32 element, uint256 linkingOffset) internal view returns (LinkedList s) {
        Array asArray = Array.wrap(LinkedList.unwrap(self));

        uint256 len = asArray.length();
        if (len == 0) {
            // nothing to link to
            Array arrayS = asArray.push(uint256(element), 3);
            s = LinkedList.wrap(Array.unwrap(arrayS));
        } else {
            // over alloc by 3
            Array arrayS = asArray.push(uint256(element), 3);
            uint256 newPtr = arrayS.unsafe_get(len);
            uint256 lastPtr = arrayS.unsafe_get(len - 1);
            
            // link the previous element with the new element
            assembly ("memory-safe") {
                mstore(add(lastPtr, linkingOffset), newPtr)
            }

            s = LinkedList.wrap(Array.unwrap(arrayS));
        }
    }

    function next(LinkedList /*self*/, bytes32 element, uint256 linkingOffset) internal pure returns (bool exists, bytes32 elem) {
        assembly ("memory-safe") {
            elem := mload(add(element, linkingOffset))
            exists := gt(elem, 0x00)
        }
    }

    function get(LinkedList self, uint256 index) internal pure returns (bytes32 elementPointer) {
        elementPointer = bytes32(Array.wrap(LinkedList.unwrap(self)).get(index));
    }

    function unsafe_get(LinkedList self, uint256 index) internal pure returns (bytes32 elementPointer) {
        elementPointer = bytes32(Array.wrap(LinkedList.unwrap(self)).unsafe_get(index));
    }
}

// the only way to traverse is to start at head and iterate via `next`. More memory efficient, better for maps
//
// data structure:
//   |-------------------------tail----------------------------|
//   |head|                                           |--------|
//   |    v                                           |        v
//  head, dataStruct{.., next} }     dataStruct{.., next}     dataStruct{.., next}
//                          |          ^
//                          |----------|
//
// `head` is a packed word split as 80, 80, 80 of linking offset, ptr to first element, ptr to last element
// `head` *isn't* stored in memory because it fits in a word 

library LinkedListLib {
    uint256 constant HEAD_MASK = 0xFFFFFFFFFFFFFFFFFFFF00000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF;
    uint256 constant TAIL_MASK = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000000;

    function newLinkedList(uint80 _linkingOffset) internal pure returns (LinkedList s) {
        assembly ("memory-safe") {
            s := shl(176, _linkingOffset)
        }
    }

    function tail(LinkedList s) internal pure returns (bytes32 elemPtr) {
        assembly ("memory-safe") {
            elemPtr := shr(176, shl(160, s))
        }
    }

    function head(LinkedList s) internal pure returns (bytes32 elemPtr) {
        assembly ("memory-safe") {
            elemPtr := shr(176, shl(80, s))
        }
    }

    function linkingOffset(LinkedList s) internal pure returns (uint80 offset) {
        assembly ("memory-safe") {
            offset := shr(176, s)
        }
    }

    function set_head(LinkedList self, bytes32 element) internal pure returns (LinkedList s) {
        assembly ("memory-safe") {
            s := or(and(self, HEAD_MASK), shl(96, element))
        }
    }

    // manually links one element to another
    function set_link(LinkedList self, bytes32 prevElem, bytes32 nextElem) internal pure {
        assembly ("memory-safe") {
            // store the new element as the `next` ptr for the tail
            mstore(
                add(
                    prevElem, // get the tail ptr
                    shr(176, self) // add the offset size to get `next`
                ),
                nextElem
            )
        }
    }

    function push_and_link(LinkedList self, bytes32 element) internal pure returns (LinkedList s) {
        assembly ("memory-safe") {
            switch gt(shr(176, shl(80, self)), 0) 
            case 1 {
                // store the new element as the `next` ptr for the tail
                mstore(
                    add(
                        shr(176, shl(160, self)), // get the tail ptr
                        shr(176, self) // add the offset size to get `next`
                    ),
                    element
                )

                // update the tail ptr
                s := or(and(self, TAIL_MASK), shl(16, element))
            }
            default {
                // no head, set element as head and tail
                s := or(or(self, shl(96, element)), shl(16, element))
            }
        }
    }

    function next(LinkedList self, bytes32 element) internal pure returns (bool exists, bytes32 elem) {
        assembly ("memory-safe") {
            elem := mload(add(element, shr(176, self)))
            exists := gt(elem, 0x00)
        }
    }
}
// File: lib/memmove/src/Mapping.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

import "./Array.sol";
import "./LinkedList.sol";

// create a user defined type that is a pointer to memory
type Mapping is bytes32;

struct Entry {
    bytes32 key;
    bytes32 value;
    bytes32 next;
}

// A mapping with the following structure:
//                                      |---------------------------------------------------|
// |------------|                       |  |------------|        |------------|             |
// |            |                       |  | key        |   |--> | key        |   |-> ...   |   
// |  bucket 1  | - holds pointer to >  |  | value      |   |    | value      |   |         |
// |            |                       |  | ptr_to ----|---|    | ptr_to ----|---|         |
// |------------|                       |  |------------|        |------------|             |
// |            |                       |---------------------------------------------------|
// |  bucket 2  | ...
// |            |
// |------------|
// |     ...    |
// |------------|
// where the number of buckets is determined by the capacity. The number of buckets is
// currently static at initialization, but this limitation could be lifted later
// 
// in general, its a memory/lookup speed tradeoff. We use a basic modulo operation for bucketing,
// which isn't ideal
//
// Complexity: best case O(1), worst case O(n)
library MappingLib {
    using ArrayLib for Array;
    using LinkedListLib for LinkedList;

    function newMapping(uint16 capacityHint) internal pure returns (Mapping s) {
        Array bucketArray = ArrayLib.newArray(capacityHint);
        for (uint256 i; i < capacityHint; i++) {
            // create a new linked list with a link offset of 64 bytes
            uint256 linkedListPtr = uint256(LinkedList.unwrap(LinkedListLib.newLinkedList(0x40)));
            bucketArray.unsafe_push(linkedListPtr);
        }

        s = Mapping.wrap(Array.unwrap(bucketArray));
    }

    function buckets(Mapping self) internal pure returns (uint256 _buckets) {
        _buckets = Array.wrap(Mapping.unwrap(self)).capacity();
    }

    // since we never resize the buckets array, the mapping itself can never move out from under us
    // does a raw insert - it does *not* check for the presence of the key already in the map
    //
    // use `update` if you know a key already exists
    function uncheckedInsert(Mapping self, bytes32 key, uint256 value) internal pure {
        uint256 bucket = uint256(key) % buckets(self);

        Entry memory entry = Entry({
            key: key,
            value: bytes32(value),
            next: bytes32(0)
        });
        bytes32 entryPtr;

        assembly ("memory-safe") {
            entryPtr := entry
        }

        // Safety:
        //  1. since buckets is guaranteed to be the capacity, we are able to make this unsafe_get
        LinkedList linkedList = LinkedList.wrap(bytes32(Array.wrap(Mapping.unwrap(self)).unsafe_get(bucket)));
        Array.wrap(Mapping.unwrap(self)).unsafe_set(bucket, uint256(LinkedList.unwrap(linkedList.push_and_link(entryPtr))));
    }

    // since we never resize the buckets array, the mapping itself can never move out from under us
    // does a raw insert - it *does* check for the presence of the key already in the map and will update it
    // if it exists
    function insert(Mapping self, bytes32 key, uint256 value) internal pure {
        uint256 bucket = uint256(key) % buckets(self);

        LinkedList linkedList = LinkedList.wrap(bytes32(Array.wrap(Mapping.unwrap(self)).unsafe_get(bucket)));
        bytes32 element = linkedList.head();
        bool success = true;
        if (element != bytes32(0)) {
            while (success) {
                bool wasSet;
                assembly ("memory-safe") {
                    let elemKey := mload(element)
                    if eq(elemKey, key) {
                        mstore(add(element, 0x20), value)
                        wasSet := 1
                    }
                }
                if (wasSet) {
                    return;
                }
                (success, element) = linkedList.next(element);
            }
        }

        // if we have reached here, the key is not present, add it
        Entry memory entry = Entry({
            key: key,
            value: bytes32(value),
            next: bytes32(0)
        });
        bytes32 entryPtr;

        assembly ("memory-safe") {
            entryPtr := entry
        }

        // Safety:
        //  1. since buckets is guaranteed to be the capacity, we are able to make this unsafe_get
        Array.wrap(Mapping.unwrap(self)).unsafe_set(bucket, uint256(LinkedList.unwrap(linkedList.push_and_link(entryPtr))));
    }

    // updates an existing value
    // use when you want to ensure a value was set
    function update(Mapping self, bytes32 key, uint256 value) internal pure returns (bool wasSet) {
        uint256 bucket = uint256(key) % buckets(self);
        LinkedList linkedList = LinkedList.wrap(bytes32(Array.wrap(Mapping.unwrap(self)).unsafe_get(bucket)));
        bytes32 element = linkedList.head();
        bool success = true;
        while (success) {
            assembly ("memory-safe") {
                let elemKey := mload(element)
                if eq(elemKey, key) {
                    mstore(add(element, 0x20), value)
                    wasSet := 1
                }
            }
            if (wasSet) {
                break;
            }
            (success, element) = linkedList.next(element);
        }
    }

    // check if map contains key
    function containsKey(Mapping self, bytes32 key) internal pure returns (bool hasKey) {
        uint256 bucket = uint256(key) % buckets(self);
        LinkedList linkedList = LinkedList.wrap(bytes32(Array.wrap(Mapping.unwrap(self)).unsafe_get(bucket)));
        bytes32 element = linkedList.head();
        bool success = true;
        if (element != bytes32(0)) {
            while (success) {
                assembly ("memory-safe") {
                    let elemKey := mload(element)
                    if eq(elemKey, key) {
                        hasKey := 1
                    }
                }
                if (hasKey) {
                    break;
                }
                (success, element) = linkedList.next(element);
            }
        }
    }

    function get(Mapping self, bytes32 key) internal pure returns (bool found, uint256 val) {
        uint256 bucket = uint256(key) % buckets(self);
        LinkedList linkedList = LinkedList.wrap(bytes32(Array.wrap(Mapping.unwrap(self)).unsafe_get(bucket)));
        bytes32 element = linkedList.head();
        bool success = true;
        if (element != bytes32(0)) {
            while (success) {
                assembly ("memory-safe") {
                    let elemKey := mload(element)
                    if eq(elemKey, key) {
                        val   := mload(add(element, 0x20))
                        found := 1
                    }
                }
                if (found) {
                    break;
                }
                (success, element) = linkedList.next(element);
            }
        }
    }
}
// File: lib/solvm/src/Evm.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;
import "./Stack.sol";
import "./Memory.sol";
import "./Storage.sol";
import "./EvmContext.sol";
import "memmove/Array.sol";
import "memmove/Mapping.sol";

// create a user defined type that is a pointer to memory
type Evm is bytes32;

library EvmLib {
    using StackLib for Stack;
    using MathOps for Stack;
    using BinOps for Stack;
    using Builtins for Stack;
    using ControlFlow for Stack;
    
    using MemoryLib for Memory;

    using StorageLib for Storage;

    using ArrayLib for Array;
    using MappingLib for Mapping;

    function newEvm(
        EvmContext memory ctx
    ) internal pure returns (Evm e) {
        assembly ("memory-safe") {
            e := ctx
        }
    }

    function setupOpTable() internal view returns (Array ops) {
        ops = ArrayLib.newArray(0x5a);
        // set capacity
        assembly ("memory-safe") {
            mstore(ops, 0x5a)
        }

        // stack
        ops.unsafe_set(0x01, intoPtr(MathOps.add));
        ops.unsafe_set(0x02, intoPtr(MathOps.mul));
        ops.unsafe_set(0x03, intoPtr(MathOps.sub));
        ops.unsafe_set(0x04, intoPtr(MathOps.div));
        ops.unsafe_set(0x05, intoPtr(MathOps.sdiv));
        ops.unsafe_set(0x06, intoPtr(MathOps.mod));
        ops.unsafe_set(0x07, intoPtr(MathOps.smod));
        ops.unsafe_set(0x08, intoPtr(MathOps._addmod));
        ops.unsafe_set(0x09, intoPtr(MathOps._mulmod));
        ops.unsafe_set(0x0a, intoPtr(MathOps._exp));
        ops.unsafe_set(0x0b, intoPtr(MathOps.signextend));
        ops.unsafe_set(0x10, intoPtr(MathOps.lt));
        ops.unsafe_set(0x11, intoPtr(MathOps.gt));
        ops.unsafe_set(0x12, intoPtr(MathOps.slt));
        ops.unsafe_set(0x13, intoPtr(MathOps.sgt));
        ops.unsafe_set(0x14, intoPtr(MathOps.eq));
        ops.unsafe_set(0x15, intoPtr(MathOps.iszero));

        ops.unsafe_set(0x16, intoPtr(BinOps.and));
        ops.unsafe_set(0x17, intoPtr(BinOps.or));
        ops.unsafe_set(0x18, intoPtr(BinOps.xor));
        ops.unsafe_set(0x19, intoPtr(BinOps.not));
        ops.unsafe_set(0x1a, intoPtr(BinOps._byte));
        ops.unsafe_set(0x1b, intoPtr(BinOps.shl));
        ops.unsafe_set(0x1c, intoPtr(BinOps.shr));
        ops.unsafe_set(0x1d, intoPtr(BinOps.sar));

        ops.unsafe_set(0x20, intoPtr(Builtins._sha3));

        // Context
        ops.unsafe_set(0x30, intoPtr(EvmContextLib._address));
        ops.unsafe_set(0x31, intoPtr(EvmContextLib._balance));
        ops.unsafe_set(0x32, intoPtr(EvmContextLib.origin));
        ops.unsafe_set(0x33, intoPtr(EvmContextLib.caller));
        ops.unsafe_set(0x34, intoPtr(EvmContextLib.callvalue));
        ops.unsafe_set(0x35, intoPtr(EvmContextLib.calldataload));
        ops.unsafe_set(0x36, intoPtr(EvmContextLib.calldatasize));
        ops.unsafe_set(0x37, intoPtr(EvmContextLib.calldatacopy));

        ops.unsafe_set(0x41, intoPtr(EvmContextLib.coinbase));
        ops.unsafe_set(0x42, intoPtr(EvmContextLib.timestamp));
        ops.unsafe_set(0x43, intoPtr(EvmContextLib.number));
        ops.unsafe_set(0x44, intoPtr(EvmContextLib.difficulty));
        ops.unsafe_set(0x45, intoPtr(EvmContextLib.gaslimit));
        ops.unsafe_set(0x46, intoPtr(EvmContextLib.chainid));
        ops.unsafe_set(0x47, intoPtr(EvmContextLib.selfbalance));
        ops.unsafe_set(0x48, intoPtr(EvmContextLib.basefee));

        ops.unsafe_set(0x50, intoPtr(StackLib._pop));

        ops.unsafe_set(0x51, intoPtr(MemoryLib.mload));
        ops.unsafe_set(0x52, intoPtr(MemoryLib.mstore));

        ops.unsafe_set(0x54, intoPtr(StorageLib.sload));
        ops.unsafe_set(0x55, intoPtr(StorageLib.sstore));

        ops.unsafe_set(0x5a, intoPtr(Builtins._gas));
    }

    function setupCompressedOpTable() internal view returns (Array ops) {
        // only use 16 bits 
        ops = ArrayLib.newArray(6);
        // set capacity
        assembly ("memory-safe") {
            mstore(ops, 6)
        }

        // The internal function dispatch table works by reference.
        // since we reference pop first, it gets referenceId 1 so it will be most optimized
        uint256 fifth = 0;
        fifth = compress(fifth, 0x50, intoPtr(StackLib._pop));

        fifth = compress(fifth, 0x51, intoPtr(MemoryLib.mload));
        fifth = compress(fifth, 0x52, intoPtr(MemoryLib.mstore));
        fifth = compress(fifth, 0x53, intoPtr(MemoryLib.mstore8));

        uint256 zeroth;
        zeroth = compress(zeroth, 0x01, intoPtr(MathOps.add));
        zeroth = compress(zeroth, 0x02, intoPtr(MathOps.mul));
        zeroth = compress(zeroth, 0x03, intoPtr(MathOps.sub));
        zeroth = compress(zeroth, 0x04, intoPtr(MathOps.div));
        zeroth = compress(zeroth, 0x05, intoPtr(MathOps.sdiv));
        zeroth = compress(zeroth, 0x06, intoPtr(MathOps.mod));
        zeroth = compress(zeroth, 0x07, intoPtr(MathOps.smod));
        zeroth = compress(zeroth, 0x08, intoPtr(MathOps._addmod));
        zeroth = compress(zeroth, 0x09, intoPtr(MathOps._mulmod));
        zeroth = compress(zeroth, 0x0a, intoPtr(MathOps._exp));
        zeroth = compress(zeroth, 0x0b, intoPtr(MathOps.signextend));
        ops.unsafe_set(0, zeroth);

        uint256 first = 0;
        first = compress(first, 0x10, intoPtr(MathOps.lt));
        first = compress(first, 0x11, intoPtr(MathOps.gt));
        first = compress(first, 0x12, intoPtr(MathOps.slt));
        first = compress(first, 0x13, intoPtr(MathOps.sgt));
        first = compress(first, 0x14, intoPtr(MathOps.eq));
        first = compress(first, 0x15, intoPtr(MathOps.iszero));
        first = compress(first, 0x16, intoPtr(BinOps.and));
        first = compress(first, 0x17, intoPtr(BinOps.or));
        first = compress(first, 0x18, intoPtr(BinOps.xor));
        first = compress(first, 0x19, intoPtr(BinOps.not));
        first = compress(first, 0x1a, intoPtr(BinOps._byte));
        first = compress(first, 0x1b, intoPtr(BinOps.shl));
        first = compress(first, 0x1c, intoPtr(BinOps.shr));
        first = compress(first, 0x1d, intoPtr(BinOps.sar));
        ops.unsafe_set(1, first);

        uint256 second = 0;
        second = compress(second, 0x20, intoPtr(Builtins._sha3));
        ops.unsafe_set(2, second);

        uint256 third = 0;
        // Context
        third = compress(third, 0x30, intoPtr(EvmContextLib._address));
        third = compress(third, 0x31, intoPtr(EvmContextLib._balance));
        third = compress(third, 0x32, intoPtr(EvmContextLib.origin));
        third = compress(third, 0x33, intoPtr(EvmContextLib.caller));
        third = compress(third, 0x34, intoPtr(EvmContextLib.callvalue));
        third = compress(third, 0x35, intoPtr(EvmContextLib.calldataload));
        third = compress(third, 0x36, intoPtr(EvmContextLib.calldatasize));
        third = compress(third, 0x37, intoPtr(EvmContextLib.calldatacopy));
        ops.unsafe_set(3, third);

        uint256 fourth = 0;
        fourth = compress(fourth, 0x41, intoPtr(EvmContextLib.coinbase));
        fourth = compress(fourth, 0x42, intoPtr(EvmContextLib.timestamp));
        fourth = compress(fourth, 0x43, intoPtr(EvmContextLib.number));
        fourth = compress(fourth, 0x44, intoPtr(EvmContextLib.difficulty));
        fourth = compress(fourth, 0x45, intoPtr(EvmContextLib.gaslimit));
        fourth = compress(fourth, 0x46, intoPtr(EvmContextLib.chainid));
        fourth = compress(fourth, 0x47, intoPtr(EvmContextLib.selfbalance));
        fourth = compress(fourth, 0x48, intoPtr(EvmContextLib.basefee));
        ops.unsafe_set(4, fourth);

        

        fifth = compress(fifth, 0x54, intoPtr(StorageLib.sload));
        fifth = compress(fifth, 0x55, intoPtr(StorageLib.sstore));

        fifth = compress(fifth, 0x5a, intoPtr(Builtins._gas));
        ops.unsafe_set(5, fifth);
    }

    function compress(uint256 ptrs, uint256 op, uint256 ptr16bit) internal pure returns (uint256 ps) {
        uint256 placement = op % 16;
        ps = ptrs | ptr16bit << (240 - 16*placement);
    }

    function uncompress(Array combinedPtrs, uint256 op) internal pure returns (uint256 ptr) {
        uint256 index = op / 16;
        uint256 placement = op % 16;
        uint256 ptrs = combinedPtrs.unsafe_get(index);
        ptr = ptrs << (16*placement) >> 240;
    }

    function context(Evm self) internal pure returns (EvmContext memory ctx) {
        assembly ("memory-safe") {
            ctx := self
        }
    }

    function evaluate(Evm self, bytes memory bytecode) internal returns (bool success, bytes memory ret) {
        (success, ret) = evaluate(self, bytecode, 32, 10, 32);
    }

    function evaluate(Evm self, bytes memory bytecode, uint16 stackSizeHint, uint16 storageSizeHint, uint32 memSizeHint) internal returns (bool success, bytes memory ret) {
        Array ops = setupCompressedOpTable();

        bytes32 ctx = Evm.unwrap(self);

        // stack capacity unlikely to surpass 32 words
        Stack stack = StackLib.newStack(stackSizeHint);
        
        // creates a storage map
        Storage store = StorageLib.newStorage(storageSizeHint);

        // mem capacity unlikely to surpass 32 words, but likely not a big deal if it does
        // (assuming no stack/storage/ctx moves)
        Memory mem = MemoryLib.newMemory(memSizeHint);

        success = true;
        ret = "";
        uint256 bcodeLen = bytecode.length;
        uint256 start;
        assembly ("memory-safe") {
            start := add(0x20, bytecode)
        }
        for (uint256 i; i < bcodeLen; ++i) {
            uint256 op;
            assembly ("memory-safe") {
                op := shr(248, mload(add(start, i)))
            }

            // we only use the optable for opcodes <= 0x5a, so try to short circuit
            if (op == 0) {
                // STOP
                break;
            } else if (op <= 0x5a) {
                if (op >= 0x56 && op <= 0x58) {
                    if (op == 0x56) {
                        // jump
                        i = stack.pop();
                        // check for jumpdest
                        assembly ("memory-safe") {
                            op := shr(248, mload(add(start, i)))
                        }
                        if (op != 0x5b) {
                            ret = "invalid jump";
                            success = false;
                            break;
                        }
                    } else if (op == 0x57) {
                        // jumpi
                        uint256 jump_loc = stack.pop();
                        uint256 b = stack.pop();
                        if (b != 0) {
                            i = jump_loc;
                            // check for jumpdest
                            assembly ("memory-safe") {
                                op := shr(248, mload(add(start, i)))
                            }
                            if (op != 0x5b) {
                                ret = "invalid jump";
                                success = false;
                                break;
                            }
                        }
                    } else {
                        // pc, 0x58
                        stack = stack.push(i, 0);
                    } 
                } else if (op == 0x38) {
                    // codesize
                    stack = stack.push(bcodeLen, 0);
                } else if (op == 0x39) {
                    // codecopy
                    codecopy(stack, mem, start);
                } else {
                    // any op not specifically handled
                    (stack, mem, store, ctx) = intoOp(uncompress(ops, op))(mem, stack, store, ctx);
                }
            } else if (op <= 0x7F) {
                // pushN
                (stack, i) = push(stack, start, op, i);
            } else if (op <= 0x8F) {
                // dupN
                uint256 index = op - 0x80;
                stack = stack.dup(index);
            } else if (op <= 0x9F) {
                // swapN
                uint256 index = op - 0x8F;
                stack.swap(index);
            } else if (op == 0xF3) {
                // return
                ret = stack._return(mem);
                break;
            } else if (op == 0xFD) {
                // revert
                ret = stack._revert(mem);
                success = false;
                break;
            } else {
                ret = "invalid op";
                success = false;
                break;
            }
        }
    }

    function codecopy(Stack stack, Memory mem, uint256 start) internal {
        uint256 destOffset = stack.pop();
        uint256 offset = stack.pop();
        uint256 size = stack.pop();
        uint256 ptr_mask = MemoryLib.ptr_mask;

        // just use the identity precompile for simplicity
        // TODO: unsafe. fix
        assembly ("memory-safe") {
            pop(
                staticcall(
                    gas(), // pass gas
                    0x04,  // call identity precompile address 
                    add(start, offset), // arg offset == pointer to calldata
                    size,  // arg size
                    add(and(mem, ptr_mask), destOffset), // set return buffer to memory ptr + destination offset
                    size   // identity just returns the bytes of the input so equal to argsize 
                )
            )
        }
    }

    function push(Stack self, uint256 start, uint256 op, uint256 i) internal view returns (Stack s, uint256 j) {
        if (op == 0x5f) {
            s = self.push(0);
            return (s, i);
        }
        uint256 pushBytes;
        assembly ("memory-safe") {
            let full_word := mload(add(start, add(i, 0x01)))
            let size := sub(op, 0x5f)
            j := add(size, i)
            pushBytes := shr(sub(256, mul(size, 8)), full_word)
        }
        s = self.push(pushBytes);
    }

    function intoPtr(function(Memory, Stack, Storage, bytes32) internal view returns (Stack, Memory, Storage, bytes32) op) internal pure returns (uint256 ptr) {
        assembly ("memory-safe") {
            ptr := op
        }
    }

    function intoOp(uint256 ptr) internal pure returns (function(Memory, Stack, Storage, bytes32) internal view returns (Stack, Memory, Storage, bytes32) op) {
        assembly ("memory-safe") {
            op := ptr
        }
    }

    function intoPushPtr(function(Stack, bytes memory, uint256, uint256) internal view returns (Stack, uint256) op) internal pure returns (uint256 ptr) {
        assembly ("memory-safe") {
            ptr := op
        }
    }

    function intoPushOp(uint256 ptr) internal pure returns (function(Stack, bytes memory, uint256, uint256) internal pure returns (Stack, uint256) op) {
        assembly ("memory-safe") {
            op := ptr
        }
    }

    function intoDupOpPtr(function(Stack, uint256) view returns (Stack) op) internal pure returns (uint256 ptr) {
        assembly ("memory-safe") {
            ptr := op
        }
    }

    function intoDupOp(uint256 ptr) internal pure returns (function(Stack, uint256) view returns (Stack) op) {
        assembly ("memory-safe") {
            op := ptr
        }
    }

    function intoSwapOpPtr(function(Stack, uint256) op) internal pure returns (uint256 ptr) {
        assembly ("memory-safe") {
            ptr := op
        }
    }

    function intoSwapOp(uint256 ptr) internal pure returns (function(Stack, uint256) view op) {
        assembly ("memory-safe") {
            op := ptr
        }
    }
}
// File: lib/solvm/src/EvmContext.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;
import "./Stack.sol";
import "./Memory.sol";
import "./Storage.sol";
import "memmove/Array.sol";
import "memmove/Mapping.sol";

struct EvmContext {
    address origin;
    address caller;
    address execution_address;
    uint256 callvalue;
    address coinbase;
    uint256 timestamp;
    uint256 number;
    uint256 gaslimit;
    uint256 difficulty;
    uint256 chainid;
    uint256 basefee;
    Mapping balances;
    bytes calld;
}

library EvmContextLib {
    using StackLib for Stack;
    using MemoryLib for Memory;
    using StorageLib for Storage;

    using ArrayLib for Array;
    using MappingLib for Mapping;

    function internalOrigin(bytes32 ct) internal pure returns (uint256 addr) {
        assembly ("memory-safe") {
            addr := mload(ct)
        }
    }

    function internalCaller(bytes32 ct) internal pure returns (uint256 addr) {
        assembly ("memory-safe") {
            addr := mload(add(ct, 0x20))
        }
    }

    function internalAddress(bytes32 ct) internal pure returns (uint256 addr) {
        assembly ("memory-safe") {
            addr := mload(add(ct, 0x40))
        }
    }

    function internalCallValue(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0x60))
        }
    }

    function internalCoinbase(bytes32 ct) internal pure returns (uint256 addr) {
        assembly ("memory-safe") {
            addr := mload(add(ct, 0x80))
        }
    }

    function internalTimestamp(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0xa0))
        }
    }

    function internalNumber(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0xc0))
        }
    }

    function internalGasLimit(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0xe0))
        }
    }

    function internalDifficulty(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0x100))
        }
    }

    function internalChainId(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0x120))
        }
    }

    function internalBaseFee(bytes32 ct) internal pure returns (uint256 val) {
        assembly ("memory-safe") {
            val := mload(add(ct, 0x140))
        }
    }

    function internalBalances(bytes32 ct) internal pure returns (Mapping map) {
        assembly ("memory-safe") {
            map := mload(add(ct, 0x160))
        }
    }

    function internalCallDataPtr(bytes32 ct) internal pure returns (bytes32 calldataPtr) {
        assembly ("memory-safe") {
            calldataPtr := add(ct, 0x180)
        }
    }

    function _address(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalAddress(ct), 0);
        return (stack, mem, store, ct);
    }

    function _balance(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        bytes32 addr = bytes32(stack.pop());
        Mapping balances = internalBalances(ct);
        (, uint256 bal) = balances.get(addr);
        stack.unsafe_push(bal);
        return (stack, mem, store, ct);
    }

    function origin(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalOrigin(ct), 0);
        return (stack, mem, store, ct);
    }

    function caller(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalCaller(ct), 0);
        return (stack, mem, store, ct);
    }

    function callvalue(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalCallValue(ct), 0);
        return (stack, mem, store, ct);
    }

    function calldataload(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        uint256 word;
        uint256 offset = stack.pop();
        EvmContext memory ctx;
        assembly ("memory-safe") {
            ctx := ct
        }

        bytes memory calld = ctx.calld;
        assembly ("memory-safe") {
            word := mload(add(calld, add(offset, 0x20)))
        }

        stack.unsafe_push(word);
        return (stack, mem, store, ct);
    }

    function calldatasize(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        uint256 len;
        assembly ("memory-safe") {
            len := mload(add(ct, 0x180))
        }
        stack = stack.push(len, 0);
        return (stack, mem, store, ct);
    }

    function calldatacopy(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        (uint256 destOffset, uint256 offset, uint256 size) = stack.pop3();
        uint256 ptr_mask = MemoryLib.ptr_mask;

        // just use the identity precompile for simplicity
        // TODO: unsafe, fix
        assembly ("memory-safe") {
            let calldataPtr := add(ct, 0x180)
            pop(
                staticcall(
                    gas(), // pass gas
                    0x04,  // call identity precompile address 
                    add(calldataPtr, offset), // arg offset == pointer to calldata
                    size,  // arg size
                    add(and(mem, ptr_mask), destOffset), // set return buffer to memory ptr + destination offset
                    size   // identity just returns the bytes of the input so equal to argsize 
                )
            )
        }
        return (stack, mem, store, ct);
    }

    function coinbase(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalCoinbase(ct), 0);
        return (stack, mem, store, ct);
    }

    function timestamp(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalTimestamp(ct), 0);
        return (stack, mem, store, ct);
    }

    function number(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalNumber(ct), 0);
        return (stack, mem, store, ct);
    }

    function difficulty(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalDifficulty(ct), 0);
        return (stack, mem, store, ct);
    }

    function gaslimit(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalGasLimit(ct), 0);
        return (stack, mem, store, ct);
    }

    function chainid(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalChainId(ct), 0);
        return (stack, mem, store, ct);
    }

    function selfbalance(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        Mapping balances = internalBalances(ct);

        (, uint256 selfbal) = balances.get(bytes32(internalAddress(ct)));
        stack = stack.push(selfbal, 0);
        return (stack, mem, store, ct);
    }
    
    function basefee(Memory mem, Stack stack, Storage store, bytes32 ct) internal view returns(Stack, Memory, Storage, bytes32) {
        stack = stack.push(internalBaseFee(ct), 0);
        return (stack, mem, store, ct);
    }
}
// File: lib/solvm/src/Memory.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

import "./Stack.sol";
import "./Storage.sol";
import "./EvmContext.sol";

// create a user defined type that is a pointer to memory
type Memory is bytes32;

// size, capacity, ptr
library MemoryLib {
    using StackLib for Stack;
    uint256 internal constant ptr_mask = 0x1fffffffffffffffffffff;
    function newMemory(uint32 capacityHint) internal pure returns (Memory m) {
        assembly ("memory-safe") {
            // grab free mem ptr
            m := mload(0x40)
            // update free mem ptr 
            mstore(0x40, add(m, mul(capacityHint, 0x20)))
            m := or(shl(85, mul(capacityHint, 0x20)), m)
        }
    }

    function loc(Memory self) internal pure returns (uint256 startLoc) {
        assembly ("memory-safe") {
            startLoc := and(ptr_mask, self)
        }
    }

    function end(Memory self) internal pure returns (uint256 endLoc) {
        assembly ("memory-safe") {
            endLoc := add(and(ptr_mask, self), shr(171, shl(86, self)))
        }
    }

    function msize_internal(Memory self) internal pure returns (uint256 size) {
        assembly ("memory-safe") {
            size := shr(170, self)
        }
    }

    function msize(Memory self, Stack stack, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        Stack s = stack.push(msize_internal(self), 0);
        return (s, self, store, ctx);
    }

    function mload(Memory self, Stack stack, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(stack)
            let target := add(stack, mul(add(0x01, len), 0x20))
            mstore(target, add(mload(target), and(ptr_mask, self)))
        }
        return (stack, self, store, ctx);
    }

    function mstore(Memory self, Stack stack, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        // set the return ptr
        Memory ret = self;

        assembly ("memory-safe") {
            let ptr := and(ptr_mask, self)
            let endLoc := add(ptr, shr(171, shl(86, self)))
            let len := mload(stack)
            let last := add(stack, mul(add(0x01, len), 0x20))
            let offset := add(ptr, mload(last))
            let elem := mload(sub(last, 0x20)) 
            mstore(stack, sub(len, 0x02))

            // check if offset > capacity (meaning no more preallocated space)
            switch gt(offset, endLoc) 
            case 1 {
                // optimization: check if the free memory pointer is equal to the end of the preallocated space
                // if it is, we can just natively extend the Stack because nothing has been allocated *after*
                // us. i.e.:
                // evm_memory = [00...free_mem_ptr...Stack.length...Stack.lastElement]
                // this check compares free_mem_ptr to Stack.lastElement, if they are equal, we know there is nothing after
                //
                switch eq(mload(0x40), endLoc)
                case 1 {
                    // the free memory pointer hasn't moved, i.e. free_mem_ptr == Memory.lastElement, just extend

                    // Add a word to the Memory.capacity & Memory.length
                    let startLoc := and(self, ptr_mask)
                    endLoc   := offset
                    let cap := sub(endLoc, startLoc)
                    ret := or(or(shl(85, cap), shl(170, cap)), startLoc)

                    // the free mem ptr is where we want to place the next element
                    mstore(offset, elem)

                    // move the free_mem_ptr by a word (32 bytes. 0x20 in hex)
                    mstore(0x40, add(endLoc, 0x20))
                }
                default {
                    // we couldn't do the above optimization, use the `identity` precompile to perform a memory move
                    
                    // move the Stack to the free mem ptr by using the identity precompile which just returns the values
                    let curr_loc := and(ptr_mask, self)
                    let mem_size := sub(endLoc, curr_loc)
                    pop(
                        staticcall(
                            gas(), // pass gas
                            0x04,  // call identity precompile address 
                            curr_loc,  // arg offset == pointer to self
                            mem_size,  // arg size: capacity + 2 * word_size (we add 2 to capacity to account for capacity and length words)
                            mload(0x40), // set return buffer to free mem ptr
                            mem_size   // identity just returns the bytes of the input so equal to argsize 
                        )
                    )
                    
                    // add the element to the end of the Stack
                    mstore(
                        offset, 
                        elem
                    )

                    let startLoc := mload(0x40)
                    endLoc   := offset
                    let cap := sub(endLoc, startLoc)
                    ret := or(or(shl(85, cap), shl(170, cap)), startLoc)

                    // update free memory pointer
                    mstore(0x40, add(endLoc, 0x20))
                }
            }
            default {
                // we have capacity for the new element, store it
                mstore(
                    // mem_loc := capacity_ptr + (capacity + 2) * 32
                    // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                    offset, 
                    elem
                )
            }
        }
        return (stack, self, store, ctx);
    }

    function mstore8(Memory self, Stack stack, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        // set the return ptr
        Memory ret = self;

        assembly ("memory-safe") {
            let ptr := and(ptr_mask, self)
            let endLoc := add(ptr, shr(171, shl(86, self)))
            let len := mload(stack)
            let last := add(stack, mul(add(0x01, len), 0x20))
            let offset := add(ptr, mload(last))
            let elem := mload(sub(last, 0x20)) 
            mstore(stack, sub(len, 0x02))

            // check if offset > capacity (meaning no more preallocated space)
            switch gt(offset, endLoc) 
            case 1 {
                // optimization: check if the free memory pointer is equal to the end of the preallocated space
                // if it is, we can just natively extend the Stack because nothing has been allocated *after*
                // us. i.e.:
                // evm_memory = [00...free_mem_ptr...Stack.length...Stack.lastElement]
                // this check compares free_mem_ptr to Stack.lastElement, if they are equal, we know there is nothing after
                //
                switch eq(mload(0x40), endLoc)
                case 1 {
                    // the free memory pointer hasn't moved, i.e. free_mem_ptr == Memory.lastElement, just extend

                    // Add a word to the Memory.capacity & Memory.length
                    let startLoc := and(self, ptr_mask)
                    endLoc   := offset
                    let cap := sub(endLoc, startLoc)
                    ret := or(or(shl(85, cap), shl(170, cap)), startLoc)

                    // the free mem ptr is where we want to place the next element
                    mstore8(offset, elem)

                    // move the free_mem_ptr by a word (32 bytes. 0x20 in hex)
                    mstore(0x40, add(endLoc, 0x20))
                }
                default {
                    // we couldn't do the above optimization, use the `identity` precompile to perform a memory move
                    
                    // move the Stack to the free mem ptr by using the identity precompile which just returns the values
                    let curr_loc := and(ptr_mask, self)
                    let mem_size := sub(endLoc, curr_loc)
                    pop(
                        staticcall(
                            gas(), // pass gas
                            0x04,  // call identity precompile address 
                            curr_loc,  // arg offset == pointer to self
                            mem_size,  // arg size: capacity + 2 * word_size (we add 2 to capacity to account for capacity and length words)
                            mload(0x40), // set return buffer to free mem ptr
                            mem_size   // identity just returns the bytes of the input so equal to argsize 
                        )
                    )
                    
                    // add the element to the end of the Stack
                    mstore8(
                        offset, 
                        elem
                    )

                    let startLoc := mload(0x40)
                    endLoc   := offset
                    let cap := sub(endLoc, startLoc)
                    ret := or(or(shl(85, cap), shl(170, cap)), startLoc)

                    // update free memory pointer
                    mstore(0x40, add(endLoc, 0x20))
                }
            }
            default {
                // we have capacity for the new element, store it
                mstore8(
                    // mem_loc := capacity_ptr + (capacity + 2) * 32
                    // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                    offset, 
                    elem
                )
            }
        }
        return (stack, self, store, ctx);
    }

    function _sha3(Memory self, uint256 offset, uint256 size) internal pure returns (uint256 ret) {
        assembly ("memory-safe") {
            let startLoc := and(ptr_mask, self)
            let off := add(startLoc, offset)
            ret := keccak256(off, size)
        }
    }
}
// File: lib/solvm/src/Stack.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

import "./Memory.sol";
import "./EvmContext.sol";
import "./Storage.sol";

// create a user defined type that is a pointer to memory
type Stack is bytes32;

library StackLib {
    function newStack(uint16 capacityHint) internal pure returns (Stack s) {
        assembly ("memory-safe") {
            // grab free mem ptr
            s := mload(0x40)
            
            // update free memory pointer based on Stack's layout:
            //  + 32 bytes for capacity
            //  + 32 bytes for current unset pointer/length
            //  + 32*capacity
            //  + current free memory pointer (s is equal to mload(0x40)) 
            mstore(0x40, add(s, mul(add(0x02, capacityHint), 0x20)))

            // store the capacity in the second word (see memory layout above)
            mstore(add(0x20, s), capacityHint)

            // store length as 0 because otherwise the compiler may have rugged us
            mstore(s, 0x00)
        }
    }

    // capacity of elements before a move would occur
    function capacity(Stack self) internal pure returns (uint256 cap) {
        assembly ("memory-safe") {
            cap := mload(add(0x20, self))
        }
    }

    // number of set elements in the Stack
    function length(Stack self) internal pure returns (uint256 len) {
        assembly ("memory-safe") {
            len := mload(self)
        }
    }

    // overloaded to default push function with 0 overallocation
    function push(Stack self, uint256 elem) internal view returns (Stack ret) {
        ret = push(self, elem, 0);
    }

    // push an element safely into the Stack - will perform a move if needed as well as updating the free memory pointer
    // returns the new pointer.
    //
    // WARNING: if a move occurs, the user *must* update their pointer, thus the returned updated pointer. safest
    // method is *always* updating the pointer
    function push(Stack self, uint256 elem, uint256 overalloc) internal view returns (Stack) {
        Stack ret;
        assembly ("memory-safe") {
            // set the return ptr
            ret := self
            // check if length == capacity (meaning no more preallocated space)
            let len := mload(self)
            let capPtr := add(0x20, self)
            let cap := mload(capPtr)
            let freememptr := mload(0x40)
            switch eq(len, cap) 
            case 1 {
                // optimization: check if the free memory pointer is equal to the end of the preallocated space
                // if it is, we can just natively extend the Stack because nothing has been allocated *after*
                // us. i.e.:
                // evm_memory = [00...free_mem_ptr...Stack.length...Stack.lastElement]
                // this check compares free_mem_ptr to Stack.lastElement, if they are equal, we know there is nothing after
                //
                // optimization 2: length == capacity in this case (per above) so we can avoid an add to look at capacity
                // to calculate where the last element it
                let stack_size := mul(cap, 0x20)
                let endPtr := add(capPtr, stack_size)
                switch eq(freememptr, endPtr) 
                case 1 {
                    // the free memory pointer hasn't moved, i.e. free_mem_ptr == Stack.lastElement, just extend

                    // Add 1 to the Stack.capacity
                    mstore(capPtr, add(0x01, cap))

                    // the free mem ptr is where we want to place the next element
                    mstore(freememptr, elem)

                    // move the free_mem_ptr by a word (32 bytes. 0x20 in hex)
                    mstore(0x40, add(0x20, freememptr))

                    // update the length
                    mstore(self, add(0x01, len))
                }
                default {
                    // we couldn't do the above optimization, use the `identity` precompile to perform a memory move
                    // set the return ptr to the new Stack
                    ret := freememptr
                    capPtr := add(0x20, ret)
                    // move the Stack to the free mem ptr by using the identity precompile which just returns the values
                    pop(
                        staticcall(
                            gas(), // pass gas
                            0x04,  // call identity precompile address 
                            self,  // arg offset == pointer to self
                            stack_size,  // arg size: capacity + 2 * word_size (we add 2 to capacity to account for capacity and length words)
                            ret, // set return buffer to free mem ptr
                            stack_size   // identity just returns the bytes of the input so equal to argsize 
                        )
                    )
                    
                    // add the element to the end of the Stack
                    mstore(add(ret, stack_size), elem)

                    // add to the capacity
                    cap := add(add(0x01, overalloc), cap) // add one + overalloc to capacity
                    mstore(
                        capPtr, // new capacity ptr
                        cap
                    )

                    // add to length
                    mstore(ret, add(0x01, mload(ret)))

                    // update free memory pointer
                    // we also over allocate if requested
                    mstore(0x40, add(0x20, add(capPtr, mul(0x20, cap))))
                }
            }
            default {
                // we have capacity for the new element, store it
                mstore(
                    // mem_loc := len_ptr + (len + 2) * 32
                    // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                    add(self, mul(add(0x02, len), 0x20)), 
                    elem
                )

                // update length
                mstore(self, add(0x01, len))
            }
        }
        return ret;
    }

    // used when you *guarantee* that the Stack has the capacity available to be pushed to.
    // no need to update return pointer in this case
    //
    // NOTE: marked as memory safe, but potentially not memory safe if the safety contract is broken by the caller
    function unsafe_push(Stack self, uint256 elem) internal pure {
        assembly ("memory-safe") {
            mstore(
                // mem_loc := capacity_ptr + (capacity + 2) * 32
                // we add 2 to capacity to acct for capacity and length words, then multiply by element size
                add(self, mul(add(0x02, mload(self)), 0x20)),
                elem
            )

            // update length
            mstore(self, add(0x01, mload(self)))
        }
    }

    function pop(Stack self) internal pure returns (uint256 ret) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            ret := mload(last)
            mstore(self, sub(len, 0x01))
        }
    }

    function pop2(Stack self) internal pure returns (uint256 ret1, uint256 ret2) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            ret1 := mload(last)
            ret2 := mload(sub(last, 0x20))
            mstore(self, sub(len, 0x02))
        }
    }

    function pop3(Stack self) internal pure returns (uint256 ret1, uint256 ret2, uint256 ret3) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            ret1 := mload(last)
            ret2 := mload(sub(last, 0x20))
            ret3 := mload(sub(last, 0x40))
            mstore(self, sub(len, 0x03))
        }
    }

    function _pop(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32){
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function swap(Stack self, uint256 index) internal pure {
        assembly ("memory-safe") {
            let last := add(self, mul(add(0x01, mload(self)), 0x20))
            let to_swap := sub(last, mul(index, 0x20))
            let last_val := mload(last)
            let swap_val := mload(to_swap)
            mstore(last, swap_val)
            mstore(to_swap, last_val)
        }
    }

    function dup(Stack self, uint256 index) internal view returns (Stack s) {
        uint256 val;
        assembly ("memory-safe") {
            let last := add(self, mul(add(0x01, mload(self)), 0x20))
            let to_dup := sub(last, mul(index, 0x20))
            val := mload(to_dup)
        }

        s = push(self, val, 0);
    }
}

library MathOps {
    using StackLib for Stack;
    function add(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, add(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function mul(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, mul(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function sub(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, sub(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function div(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, div(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function sdiv(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 inv_a, uint256 inv_b) = self.pop2();
        int256 a = int256(inv_a);
        int256 b = int256(inv_b);
        self.unsafe_push(uint256(a / b));
        return (self, mem, store, ctx);
    }

    function mod(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, mod(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function smod(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 inv_a, uint256 inv_b) = self.pop2();
        int256 a = int256(inv_a);
        int256 b = int256(inv_b);
        self.unsafe_push(uint256(a % b));
        return (self, mem, store, ctx);
    }

    function _addmod(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let a := add(self, mul(add(0x01, len), 0x20))
            let b := sub(a, 0x20)
            let target := sub(a, 0x40)
            mstore(target, addmod(mload(a), mload(b), mload(target)))
            mstore(self, sub(len, 0x02))
        }
        return (self, mem, store, ctx);
    }

    function _mulmod(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let a := add(self, mul(add(0x01, len), 0x20))
            let b := sub(a, 0x20)
            let target := sub(a, 0x40)
            mstore(target, mulmod(mload(a), mload(b), mload(target)))
            mstore(self, sub(len, 0x02))
        }
        return (self, mem, store, ctx);
    }

    function _exp(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, exp(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function lt(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, lt(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function gt(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, gt(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function slt(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 inv_a, uint256 inv_b) = self.pop2();
        int256 a = int256(inv_a);
        int256 b = int256(inv_b);
        bool c = a < b;
        uint256 d;
        assembly ("memory-safe") {
            d := c
        }
        self.unsafe_push(d);
        return (self, mem, store, ctx);
    }

    function sgt(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 inv_a, uint256 inv_b) = self.pop2();
        int256 a = int256(inv_a);
        int256 b = int256(inv_b);
        bool c = a > b;
        uint256 d;
        assembly ("memory-safe") {
            d := c
        }
        self.unsafe_push(d);
        return (self, mem, store, ctx);
    }

    function eq(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, eq(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function iszero(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            mstore(last, iszero(mload(last)))
        }
        return (self, mem, store, ctx);
    }

    function signextend(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 b, uint256 x) = self.pop2();
        uint256 c;
        assembly ("memory-safe") {
            c := signextend(b, x)
        }
        self.unsafe_push(c);
        return (self, mem, store, ctx);
    }
}

library BinOps {
    using StackLib for Stack;

    function and(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, and(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function or(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, or(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function xor(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, xor(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function not(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let target := add(self, mul(add(0x01, len), 0x20))
            mstore(target, not(mload(target)))
        }
        return (self, mem, store, ctx);
    }

    function _byte(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, byte(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function shl(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, shl(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function shr(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        assembly ("memory-safe") {
            // we only add one to get last element
            let len := mload(self)
            let last := add(self, mul(add(0x01, len), 0x20))
            let target := sub(last, 0x20) 
            mstore(target, shr(mload(last), mload(target)))
            mstore(self, sub(len, 0x01))
        }
        return (self, mem, store, ctx);
    }

    function sar(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32){
        (uint256 shift, uint256 inv_value) = self.pop2();
        int256 value = int256(inv_value);
        self.unsafe_push(uint256(value >> shift));
        return (self, mem, store, ctx);
    }
}

library Builtins {
    using StackLib for Stack;
    using MemoryLib for Memory;
    function _sha3(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        (uint256 offset, uint256 value) = self.pop2();
        uint256 hash = mem._sha3(offset, value);
        self.unsafe_push(hash);
        return (self, mem, store, ctx);
    }

    function _gas(Memory mem, Stack self, Storage store, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        self = self.push(gasleft(), 0);
        return (self, mem, store, ctx);
    }
}

library ControlFlow {
    using StackLib for Stack;
    using MemoryLib for Memory;
    function _return(Stack self, Memory mem) internal pure returns (bytes memory ret) {
        (uint256 offset, uint256 size) = self.pop2();
        offset += mem.loc();
        assembly ("memory-safe") {
            ret := sub(offset, 0x20)
            mstore(ret, size)
        }
    }

    function _revert(Stack self, Memory mem) internal pure returns (bytes memory ret) {
        (uint256 offset, uint256 size) = self.pop2();
        offset += mem.loc();
        assembly ("memory-safe") {
            ret := sub(offset, 0x20)
            mstore(ret, size)
        }
    }
}
// File: lib/solvm/src/Storage.sol



// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13 <0.9.0;

import "memmove/Mapping.sol";
import "./Stack.sol";
import "./Memory.sol";
import "./EvmContext.sol";

// create a user defined type that is a pointer to memory
type Storage is bytes32;

library StorageLib {
    using StackLib for Stack;
    using MappingLib for Mapping;
    
    function newStorage(uint16 capacityHint) internal pure returns (Storage m) {
        Mapping map = MappingLib.newMapping(capacityHint);
        m = Storage.wrap(Mapping.unwrap(map));
    }

    function sload(Memory mem, Stack stack, Storage self, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32)  {
        Mapping map = Mapping.wrap(Storage.unwrap(self));
        uint256 key = stack.pop();
        (, uint256 value) = map.get(bytes32(key));
        stack.unsafe_push(value);
        return (stack, mem, self, ctx);
    }

    function sstore(Memory mem, Stack stack, Storage self, bytes32 ctx) internal view returns (Stack, Memory, Storage, bytes32) {
        Mapping map = Mapping.wrap(Storage.unwrap(self));
        uint256 key = stack.pop();
        uint256 value = stack.pop();
        map.insert(bytes32(key), value);
        return (stack, mem, self, ctx);
    }
}
// File: src/Challenge.sol



// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.17;

import "memmove/Mapping.sol";
import "solvm/Evm.sol";


interface IPuzzle {
    /// @notice Returns the puzzle's name.
    /// @return The puzzle's name.
    function name() external pure returns (string memory);

    /// @notice Generates the puzzle's starting position based on a seed.
    /// @dev The seed is intended to be `msg.sender` of some wrapper function or
    /// call.
    /// @param _seed The seed to use to generate the puzzle.
    /// @return The puzzle's starting position.
    function generate(address _seed) external returns (uint256);

    /// @notice Verifies that a solution is valid for the puzzle.
    /// @dev `_start` is intended to be an output from {IPuzzle-generate}.
    /// @param _start The puzzle's starting position.
    /// @param _solution The solution to the puzzle.
    /// @return Whether the solution is valid.
    function verify(uint256 _start, uint256 _solution) external returns (bool);
}

struct Solution {
    uint8 stop;
    uint8 ctxSetting;
    bytes code;
}

contract MiniMutant is IPuzzle {
    using EvmLib for Evm;
    using MappingLib for Mapping;

    function name() external pure returns (string memory) {
        return "Mini Mutant";
    }

    function generate(address _seed) external returns (uint256) {
        return uint256(keccak256(abi.encodePacked(_seed)));
    }

    function verify(uint256 _start, uint256 _solution) external returns (bool) {

        Solution memory sol = Solution({
            stop: 0,
            ctxSetting: 0,
            code: abi.encodePacked(_solution)
        });

        address origin = tx.origin;
        address caller = msg.sender;
        address execution_address = address(this);
        bytes memory calld = abi.encodePacked(_start);

        while (sol.stop == 0) {
            if (sol.ctxSetting == 0) {
                origin = tx.origin;
                caller = msg.sender;
                execution_address = address(this);
            } else if (sol.ctxSetting == 1) {
                origin = msg.sender;
                caller = address(this);
            }

            (bool succ, bytes memory ret) = this.run(origin, caller, execution_address, calld, sol.code);
            require(succ, "Script failed");
            require(ret.length > 2, "Bad return length");
            sol.stop = uint8(ret[0]);
            sol.ctxSetting = uint8(ret[1]);
            sol.code = slice(ret, 2, ret.length - 2);
        }

        (bool succ, bytes memory ret) = this.run(origin, caller, execution_address, calld, sol.code);
        require(succ, "Script failed");
        uint256 result = abi.decode(ret, (uint256));
        require(result == _start, "Fail");
        return true;
    }

    function run(
        address origin,
        address caller,
        address execution_address,
        bytes calldata calld,
        bytes calldata executionCode
    ) external returns (bool, bytes memory) {
        uint256 fee;
        uint256 id;
        assembly("memory-safe") {
            fee := basefee()
            id := chainid()
        }
        EvmContext memory ctx = EvmContext({
            origin: origin,
            caller: caller,
            execution_address: execution_address,
            callvalue: 0,
            coinbase: block.coinbase,
            timestamp: block.timestamp,
            number: block.number,
            gaslimit: block.gaslimit,
            difficulty: block.difficulty,
            chainid: id,
            basefee: fee,
            balances: MappingLib.newMapping(1),
            calld: calld
        });
        Evm evm = EvmLib.newEvm(ctx);

        // NOTE: No frame switching opcodes are supported (i.e. Call, Create, etc.)
        return evm.evaluate(executionCode);
    }

    function slice(
        bytes memory _bytes,
        uint256 _start,
        uint256 _length
    )
        internal
        pure
        returns (bytes memory)
    {
        require(_length + 31 >= _length, "slice_overflow");
        require(_bytes.length >= _start + _length, "slice_outOfBounds");

        bytes memory tempBytes;

        assembly {
            switch iszero(_length)
            case 0 {
                // Get a location of some free memory and store it in tempBytes as
                // Solidity does for memory variables.
                tempBytes := mload(0x40)

                // The first word of the slice result is potentially a partial
                // word read from the original array. To read it, we calculate
                // the length of that partial word and start copying that many
                // bytes into the array. The first word we copy will start with
                // data we don't care about, but the last `lengthmod` bytes will
                // land at the beginning of the contents of the new array. When
                // we're done copying, we overwrite the full first word with
                // the actual length of the slice.
                let lengthmod := and(_length, 31)

                // The multiplication in the next line is necessary
                // because when slicing multiples of 32 bytes (lengthmod == 0)
                // the following copy loop was copying the origin's length
                // and then ending prematurely not copying everything it should.
                let mc := add(add(tempBytes, lengthmod), mul(0x20, iszero(lengthmod)))
                let end := add(mc, _length)

                for {
                    // The multiplication in the next line has the same exact purpose
                    // as the one above.
                    let cc := add(add(add(_bytes, lengthmod), mul(0x20, iszero(lengthmod))), _start)
                } lt(mc, end) {
                    mc := add(mc, 0x20)
                    cc := add(cc, 0x20)
                } {
                    mstore(mc, mload(cc))
                }

                mstore(tempBytes, _length)

                //update free-memory pointer
                //allocating the array padded to 32 bytes like the compiler does now
                mstore(0x40, and(add(mc, 31), not(31)))
            }
            //if we want a zero-length slice let's just return a zero-length array
            default {
                tempBytes := mload(0x40)
                //zero out the 32 bytes slice we are about to return
                //we need to do it because Solidity does not garbage collect
                mstore(tempBytes, 0)

                mstore(0x40, add(tempBytes, 0x20))
            }
        }

        return tempBytes;
    }
}