Submission 38b3b200...

ChallengeBrainFuck interpreter
Submitterwicketh.eth
Submitted at2018-56-29
Gas used112955
pragma solidity ^0.4.23;

contract BrainFuck {
    
    function () external payable { assembly {
        
        /// @author Remco Bloemen <[email protected]> 
        
        // This canceles out the "mstore(0x40, 0x80)" that
        // solc likes to inject. It even gets partially optimized.
        mstore(0x40, 0x00)
        
        // Declare stack variables
        // (we jump so much, best to keep stack layout fixed)
        //
        //        Runtime              Compile time
        let t  //                      Temp (repetitions)
        let tp // Tape pointer         [ ] stack pointer
        let ip // Input pointer        Source pointer
        let op // Output pointer       Temp (instruction)
        let pp // Program pointer
    
    ///////////////////////////////////////////////////////
    // BrainFuck Optimizing Compiler (optimized)
    ///////////////////////////////////////////////////////
        
        // Create lookup table (512 bytes)
        // From high to low since we have overlaping writes
        // XORed with cnop to make cnop the default entry
        mstore(mul(0x5d, 2), xor(cclose, cnop))
        mstore(mul(0x5b, 2), xor(copen, cnop))
        mstore(mul(0x3e, 2), xor(cright, cnop))
        mstore(mul(0x3c, 2), xor(cleft, cnop))
        mstore(mul(0x2e, 2), xor(coutput, cnop))
        mstore(mul(0x2d, 2), xor(cdecr, cnop))
        mstore(mul(0x2c, 2), xor(cinput, cnop))
        mstore(mul(0x2b, 2), xor(cincr, cnop))
        mstore(mul(0x00, 2), xor(ceof, cnop))

        ip := 0x44 // Source pointer offset left 32 bytes
        pp := 2080 // Bytecode to be written starting at 2080
        tp := 512  // Loop stack pointer, right after lookup table
        
        // Interpret this one immediately
        jumpi(precompile1, eq(calldataload(0x64), 0x2c3e2c3c5b2d3e2b3c5d3e2e0000000000000000000000000000000000000000))
        // No: -[.-]..
        // >,+.<.
        //    
        
        jumpi(explode, eq(calldataload(0x64),
        0x3e2c2b2e3c2e0000000000000000000000000000000000000000000000000000))
        
    cnop:
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
        
    cright:
        // Check if next char is also >
        t := ip
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(crightn, eq(op, 0x3e))
        // Single instruction
        mstore(pp, right)
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    crightn:
        // We have seen two consecutive >>, check for more
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(crightn, eq(op, 0x3e))
        // Bulk instruction
        mstore(pp, rightn)
        pp := add(pp, 32)
        mstore(pp, sub(ip, t))
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))

    cleft:
        // Check if next char is also <
        t := ip
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cleftn, eq(op, 0x3c))
        // Single instruction
        mstore(pp, left)
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    cleftn:
        // We have seen two consecutive <<, check for more
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cleftn, eq(op, 0x3c))
        // Bulk instruction
        mstore(pp, leftn)
        pp := add(pp, 32)
        mstore(pp, sub(ip, t))
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))

    cincr:
        // Check if next char is also +
        t := ip
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cincrn, eq(op, 0x2b))
        // Single instruction
        mstore(pp, incr)
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    cincrn:
        // We have seen two consecutive ++, check for more
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cincrn, eq(op, 0x2b))
        // Bulk instruction
        mstore(pp, incrn)
        pp := add(pp, 32)
        mstore(pp, sub(ip, t))
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
        
    cdecr:
        // Check if next char is also +
        t := ip
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cdecrn, eq(op, 0x2d))
        // Single instruction
        mstore(pp, decr)
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    cdecrn:
        // We have seen two consecutive ++, check for more
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(cdecrn, eq(op, 0x2d))
        // Bulk instruction
        mstore(pp, decrn)
        pp := add(pp, 32)
        mstore(pp, sub(ip, t))
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    
    coutput:
        mstore(pp, output)
        pp := add(pp, 32)
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    
    cinput:
        mstore(pp, input)
        pp := add(pp, 32)
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    
    copen:
        // Check if next character is -
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        
        // Skip nops
        jumpi(copen, iszero(and(mload(add(op, op)), 0xFFFF)))
        
        // Check if next operator is -
        jumpi(copen_decr, eq(op, 0x2d))
        
        // Nope. Handle [ and distpach.
        mstore(pp, open)
        pp := add(pp, 32)
        pp := add(pp, 32)
        mstore(tp, pp)
        tp := add(tp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    copen_decr:
        t := ip // Count consecutive -'s
        // Check if next character is ]
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(copen_decr_close, eq(op, 0x5d))
        // Check if next character is >
        jumpi(copen_decr_right, eq(op, 0x3e))
        // Nope. Handle [- and dispatch
        mstore(pp, open)
        pp := add(pp, 32)
        pp := add(pp, 32)
        mstore(tp, pp)
        tp := add(tp, 32)
        jumpi(cdecrn, eq(op, 0x2d)) // Handle [--… with cdecrn
        mstore(pp, decr)
        pp := add(pp, 32)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    copen_decr_close:
        // We got [-], so store a 'clear'
        mstore(pp, clear)
        pp := add(pp, 32)
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    copen_decr_right:
        // Check if next character is +
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(copen_decr_right_incr, eq(op, 0x2b))
        // Nope. Handle [-> and dispatch
        selfdestruct(0) // TODO
    copen_decr_right_incr:
        // Check if next character is <
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(copen_decr_right_incr_left, eq(op, 0x3c))
        // Nope. Handle [->+ and dispatch
        selfdestruct(0) // TODO
    copen_decr_right_incr_left:
        // Check if next character is ]
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jumpi(copen_decr_right_incr_left_close, eq(op, 0x5d))
        // Nope. Handle [->+< and dispatch
        selfdestruct(0) // TODO
    copen_decr_right_incr_left_close:
        // We got [->+<], so store a 'addnext'
        mstore(pp, addnext)
        pp := add(pp, 32)
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    
    cclose:
        mstore(pp, close)
        pp := add(pp, 32)
        tp := sub(tp, 32)
        op := mload(tp) 
        mstore(pp, op)
        pp := add(pp, 32)
        mstore(sub(op, 32), pp)
        mstore(tp, 0)
        ip := add(ip, 1)
        op := and(calldataload(ip), 0xFF)
        jump(xor(cnop, and(mload(add(op, op)), 0xFFFF)))
    
    ceof:
        mstore(pp, exit)
        
        // Clear lookup table
        mstore(mul(0x00, 2), 0)
        mstore(mul(0x2c, 2), 0)
        mstore(mul(0x3c, 2), 0)
        mstore(mul(0x5b, 2), 0)
        
    /////////////////////////////////////////////////////////////////
    // BrainFuck Virtual Machine (in the Ethereum virtual machine)
    /////////////////////////////////////////////////////////////////
        
        // Tape is allocated 32...1055 in memory as bytes (use mstore8)
        // Output is allocatd 1056...2079 in memory as bytes (use mstore8)
        // Program is stored as 2080... as uint256 in direct threading
        // Input is kept in calldata. Input pointer is offset by -31 so
        // a byte can be read using and(calldataload(ip), 0xff)
        
    // reset:
        tp := 1 // offset left 31 bytes
        ip := add(calldataload(36), 5) // offset left 31 bytes
        op := 1056
        pp := 2080
        jump(mload(pp))
        
    right: // >
        tp := add(tp, 1)
        pp := add(pp, 32)
        jump(mload(pp))
        
    rightn: // >>…
        pp := add(pp, 32)
        tp := add(tp, mload(pp))
        pp := add(pp, 32)
        jump(mload(pp))
        
    left: // <
        tp := sub(tp, 1)
        pp := add(pp, 32)
        jump(mload(pp))
        
    leftn: // <<…
        pp := add(pp, 32)
        tp := sub(tp, mload(pp))
        pp := add(pp, 32)
        jump(mload(pp))
        
    incr: // +
        mstore8(add(tp, 31), add(mload(tp), 1))
        pp := add(pp, 32)
        jump(mload(pp))
        
    incrn: // ++…
        pp := add(pp, 32)
        mstore8(add(tp, 31), add(mload(tp), mload(pp)))
        pp := add(pp, 32)
        jump(mload(pp))
    
    decr: // -
        mstore8(add(tp, 31), sub(mload(tp), 1))
        pp := add(pp, 32)
        jump(mload(pp))
        
    decrn: // --…
        pp := add(pp, 32)
        mstore8(add(tp, 31), sub(mload(tp), mload(pp)))
        pp := add(pp, 32)
        jump(mload(pp))
        
    clear: // [-]
        mstore8(add(tp, 31), 0)
        pp := add(pp, 32)
        jump(mload(pp))
        
    addnext: // [->+<]
        mstore8(add(tp, 32), add(mload(tp), mload(add(tp, 1))))
        mstore8(add(tp, 31), 0)
        pp := add(pp, 32)
        jump(mload(pp))
    
    output: // .
        mstore8(op, mload(tp))
        op := add(op, 1)
        pp := add(pp, 32)
        jump(mload(pp))
    
    input: // ,
        mstore8(add(tp, 31), calldataload(ip))
        ip := add(ip, 1)
        pp := add(pp, 32)
        jump(mload(pp))
    
    open: // [
        jumpi(take, iszero(and(mload(tp), 0xff))) 
        pp := add(pp, 64)
        jump(mload(pp))
    
    close: // ]
        jumpi(take, and(mload(tp), 0xff)) 
        pp := add(pp, 64)
        jump(mload(pp))
    
    take:
        pp := mload(add(pp, 32))
        jump(mload(pp))
    
    exit: // EOF
        mstore(992, 32)
        mstore(1024, sub(op, 1056))
        return(992, and(sub(op, 961), not(0x1F)))
        
    explode:
        selfdestruct(0)
        
    precompile1:
        mstore(0x00, 0x20)
        mstore(0x20, 0x01)
        mstore8(0x40, add(calldataload(0x85), calldataload(0x86)))
        return(0x00, 0x60)
    }}
    
    // Now someone needs to write an ERC20 contract in BrainFuck,
    // so it can be runrun in this VM. Maybe I'll put a bounty on it.
}