Submission d272b189...

ChallengeBrainFuck interpreter
Submitterwicketh.eth
Submitted at2018-46-12
Gas used1323506
pragma solidity ^0.4.23;

contract BrainFuck {
    
    /// @author Remco Bloemen <[email protected]>

    struct VMState {
        bytes out;
        bytes inp;
        uint256[] arg;
        uint256 mp;
        uint256 ip;
        uint256 op;
        uint256 pp;
    }

    function execute(bytes pro, bytes inp)
        public pure
        returns(bytes)
    {
        bytes memory out = new bytes(2048);
        uint256[] memory arg = new uint256[](pro.length);
        
        // Stress test the parser. (It's a dynamic array of function pointers)
        function(VMState memory) internal pure [] memory byt = new function(VMState memory) internal pure [] (pro.length + 1);
        
        compile(pro, arg, byt);
        
        uint256 op = run(byt, inp, out, arg);
        
        // Create output array
        bytes memory ret = new bytes(op);
        for(uint256 i = 0; i < op; i++) {
            ret[i] = out[i];
        }
        return ret;
    }
    
    function compile(bytes memory pro, uint256[] memory arg, function(VMState memory) internal pure [] memory byt)
        private pure
    {
        // Compute arguments
        uint256[20] memory stack;
        uint256 sp = 0;
        uint256 bp = 0;
        uint256 amount;
        for(uint pp = 0; pp < pro.length; pp++) {
            bytes32 instruction = pro[pp];
            if (instruction == '>') {
                if (pro[pp + 1] == '>') {
                    amount = 1;
                    do {
                        amount += 1;
                        pp++;
                    } while (pro[pp + 1] == '>');
                    byt[bp] = right;
                    arg[bp] = amount;
                } else {
                    byt[bp] = right1;
                }
                bp++;
            } else if (instruction == '<') {
                if (pro[pp + 1] == '<') {
                    amount = 1;
                    do {
                        amount += 1;
                        pp++;
                    } while (pro[pp + 1] == '<');
                    byt[bp] = left;
                    arg[bp] = amount;
                } else {
                    byt[bp] = left1;
                }
                bp++;
            } else if (instruction == '+') {
                if (pro[pp + 1] == '+') {
                    amount = 1;
                    do {
                        amount += 1;
                        pp++;
                    } while (pro[pp + 1] == '+');
                    byt[bp] = incr;
                    arg[bp] = amount;
                } else {
                    byt[bp] = incr1;
                }
                bp++;
            } else if (instruction == '-') {
                if (pro[pp + 1] == '-') {
                    amount = 1;
                    do {
                        amount += 1;
                        pp++;
                    } while (pro[pp + 1] == '-');
                    byt[bp] = decr;
                    arg[bp] = amount;
                } else {
                    byt[bp] = decr1;
                }
                bp++;
            } else if (instruction == '.') {
                byt[bp] = output;
                bp++;
            } else if (instruction == ',') {
                byt[bp] = input;
                bp++;
            } else if(instruction == '[') {
                byt[bp] = open;
                stack[sp++] = bp;
                bp++;
            } else if(instruction == ']') {
                byt[bp] = close;
                amount = stack[--sp];
                arg[amount] = bp + 1;
                arg[bp] = amount + 1;
                bp++;
            }
        }
        byt[bp] = exit;
    }
    
    function run(function(VMState memory) internal pure [] memory byt, bytes memory inp, bytes memory out, uint256[] memory arg) private pure returns (uint256 op)
    {
        VMState memory s = VMState({
            out: out,
            inp: inp,
            arg: arg,
            mp: 1024,
            pp: 0,
            ip: 0,
            op: 0
        });
        for(; s.pp < byt.length;) {
            byt[s.pp](s);
        }
        return s.op;
    }
    
    function nop(VMState memory s) private pure
    {
        s.pp++;
    }
    
    function right1(VMState memory s) private pure
    {
        s.mp += 1;
        s.pp++;
    }
    
    function right(VMState memory s) private pure
    {
        s.mp += s.arg[s.pp];
        s.pp++;
    }
    
    function left1(VMState memory s) private pure
    {
        s.mp -= 1;
        s.pp++;
    }
    
    function left(VMState memory s) private pure
    {
        s.mp -= s.arg[s.pp];
        s.pp++;
    }
    
    function incr1(VMState memory s) private pure
    {
        s.out[s.mp] = bytes1(read1(s.out, s.mp) + 1);
        s.pp++;
    }
    
    function incr(VMState memory s) private pure
    {
        s.out[s.mp] = bytes1(read1(s.out, s.mp) + s.arg[s.pp]);
        s.pp++;
    }
    
    function decr1(VMState memory s) private pure
    {
        s.out[s.mp] = bytes1(read1(s.out, s.mp) - 1);
        s.pp++;
    }
    
    function decr(VMState memory s) private pure
    {
        s.out[s.mp] = bytes1(read1(s.out, s.mp) - s.arg[s.pp]);
        s.pp++;
    }
    
    function output(VMState memory s) private pure
    {
        s.out[s.op] = s.out[s.mp];
        s.op++;
        s.pp++;
    }
    
    function input(VMState memory s) private pure
    {
        s.out[s.mp] = s.inp[s.ip];
        s.ip++;
        s.pp++;
    }
    
    function open(VMState memory s) private pure
    {
        if (s.out[s.mp] == 0) {
            s.pp = s.arg[s.pp];
        } else {
            s.pp++;
        }
    }
    
    function close(VMState memory s) private pure
    {
        if (s.out[s.mp] != 0) {
            s.pp = s.arg[s.pp];
        } else {
            s.pp++;
        }
    }
    
    function exit(VMState memory s) private pure
    {
        s.pp = 0x123456789ABCDEF;
    }
    
    function read1(bytes memory inp, uint256 i)
        internal pure
        returns (uint256)
    {
        return uint256(inp[i]);
    }
}