Submission 90a17dbd...

ChallengeBrainFuck interpreter
Submitter0xd0b40847c318da4...
Submitted at2018-42-30
Gas used2643083
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract BrainFuck {
    /**
     * @dev Executes a BrainFuck program, as described at https://en.wikipedia.org/wiki/Brainfuck.
     *
     * Memory cells, input, and output values are all expected to be 8 bit
     * integers. Incrementing past 255 should overflow to 0, and decrementing
     * below 0 should overflow to 255.
     *
     * Programs and input streams may be of any length. The memory tape starts
     * at cell 0, and will never be moved below 0 or above 1023. No program will
     * output more than 1024 values.
     *
     * @param program The BrainFuck program.
     * @param input The program's input stream.
     * @return The program's output stream. Should be exactly the length of the
     *          number of outputs produced by the program.
     */
    function execute(bytes program, bytes input) public pure returns(bytes) {
        uint len = program.length;
        uint ipp;
        uint opp;
        uint dp;
        uint ip;
        uint[] memory jumpStack;
        uint[] memory jump;
        byte b;
        bool[94] memory alright;
        bytes memory mem = new bytes(1024);
        bytes memory output = new bytes(1024);

        if (len == 0) {
            return;
        }

        alright[43] = true;
        alright[44] = true;
        alright[45] = true;
        alright[46] = true;
        alright[60] = true;
        alright[62] = true;
        alright[91] = true;
        alright[93] = true;


        dp = len;
        for(; ip < len; ip++) {
            b = program[ip];
            if (b > 93 || !alright[uint(b)]) {
                dp = ip;
                break;
            } else if (b == ']') {
                opp = ip; // record last ]
            }
        }
        for(ip++; ip < len; ip++) {
            b = program[ip];
            if (b < 94 && alright[uint(b)]) {
                if (b == ']') opp = dp; // record last ]
                program[dp] = b;
                dp++;
            }
        }
        len = dp;

        if (opp != 0) {
            dp = opp+1;
            jump = new uint[](dp);
            jumpStack = new uint[](dp/2);
        }

        for(ip = 0; ip < len; ip++) {
            b = program[ip];
            if(b == '[') {
                ipp++;
                jumpStack[ipp] = ip;
            } else if(b == ']') {
                opp = jumpStack[ipp];
                jump[opp] = ip;
                jump[ip] = opp;
                ipp--;
            }
        }

        opp = ipp = dp = 0;
        for(ip = 0; ip < len; ip++) {
            b = program[ip];
            if (b < 47) {
                if(b == '+') {
                    mem[dp] = byte(uint(mem[dp]) + 1);
                } else if(b == '-') {
                    mem[dp] = byte(uint8(mem[dp])-1);
                } else if(b == '.') {
                    output[opp++] = mem[dp];
                } else if(b == ',') {
                    mem[dp] = input[ipp++];
                }
            } else {
                if(b == '>') {
                    dp++;
                } else if(b == '<') {
                    dp--;
                } else if(b == '[') {
                    if(mem[dp] == 0) {
                        ip = jump[ip];
                    }
                } else if(b == ']') {
                    if(mem[dp] != 0) {
                        ip = jump[ip];
                    }
                }
            }
        }

        if (opp == 1024) {
            return output;
        }

        bytes memory ret = new bytes(opp);
        for(ip = 0; ip < opp; ip++) {
            ret[ip] = output[ip];
        }
        return ret;
    }
}