Submission 92f1cd3d...

ChallengeBrainFuck interpreter
Submitterhyszeth.eth
Submitted at2018-33-08
Gas used4986335
/**
 * 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 {
    event E(string);
    event B(byte);
    event P(byte,byte);
    /**
     * @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) {
        // Optimize
        if(!optimize(program)) return;

        // Run
        bytes memory data = new bytes(2048); // store output at end of data
        uint oPtr = runProgram(program, input, data, 1024, 0, 0, 0, program.length);

        // Parse output
        uint j;
        bytes memory output = new bytes(oPtr - 1024);
        for(uint i = 1024; i < oPtr; ++i) {
            output[j++] = data[i];
        }
        return output;
    }

    function optimize(bytes program) internal pure returns (bool hasOutput) {
        byte s;
        byte last;
        uint8 count; // Q: What happens if count > 255?
        uint maxProgramLength = program.length;
        for(uint pPtr = 0; pPtr < maxProgramLength; pPtr++) {
            s=program[pPtr];
            bool isValid = s == '[' || s == ']' || s == '>' || s == '<' || s == '+' || s == '-' || s == ',' || s == '.';
            if(!isValid) program[pPtr] = s = '*';
            else if(s == '.') hasOutput = true;

            if(s == last) {
                count++;
            } else if(count > 0) {
                if(byte(count) > 0x29 && byte(count) < 0x5E) { // Range that our special chars are in
                    if(byte(count) < 0x2F || byte(count) > 0x5A) { // Ranges that our spscial chars are in
                        if(byte(count) == '[') count -= 1;
                        else if(byte(count) == ']') count -= 1;
                        else if(byte(count) == '>') count -= 1;
                        else if(byte(count) == '<') count -= 1;
                        else if(byte(count) == '+') count -= 2;
                        else if(byte(count) == '-') count -= 4;
                        else if(byte(count) == '.') count -= 5;
                        else if(byte(count) == ',') count -= 3;
                        else if(byte(count) == '*') count -= 1;
                    }
                }
                program[pPtr-count] = byte(count);
                count = 0;
            }

            last = s;
        }

        if(count > 0) {
            if(byte(count) > 0x29 && byte(count) < 0x5E) { // Range that our special chars are in
                if(byte(count) < 0x2F || byte(count) > 0x5A) { // Ranges that our spscial chars are in
                    if(byte(count) == '[') count -= 1;
                    else if(byte(count) == ']') count -= 1;
                    else if(byte(count) == '>') count -= 1;
                    else if(byte(count) == '<') count -= 1;
                    else if(byte(count) == '+') count -= 2;
                    else if(byte(count) == '-') count -= 4;
                    else if(byte(count) == '.') count -= 5;
                    else if(byte(count) == ',') count -= 3;
                    else if(byte(count) == '*') count -= 1;
                }
            }
            program[pPtr-count] = byte(count);
        }
    }

    function runProgram(bytes program, bytes input, bytes data, uint oPtr, uint pPtr, uint iPtr, uint dPtr, uint maxProgramLength) internal pure returns(uint) {
        uint[] memory programBegin = new uint[](1024); // max stack depth
        uint programBeginIndex;
        byte s = program[pPtr];
        uint8 n = 1;
        while(true) {
            if(s == '[') {
                while(n-- > 0) programBegin[programBeginIndex++] = ++pPtr;
            } else if(s == ']') {
                while(n-- > 0) {
                    if(data[dPtr] == 0) {
                        programBeginIndex--;
                        pPtr++;
                    } else {
                        pPtr = programBegin[programBeginIndex-1];
                    }
                }
            } else if(s == '>') {
                dPtr += n;
                pPtr += n;
            } else if(s == '<') {
                dPtr -= n;
                pPtr += n;
            } else if(s == '+') {
                data[dPtr] = byte(uint8(data[dPtr]) + n);
                pPtr += n;
            } else if(s == '-') {
                data[dPtr] = byte(uint8(data[dPtr]) - n);
                pPtr += n;
            } else if(s == ',') {
                pPtr += n;
                while(n-- > 0) data[dPtr] = input[iPtr++];
            } else if(s == '.') {
                pPtr += n;
                while(n-- > 0) data[oPtr++] = data[dPtr];
            } else if(s == '*'){
                pPtr += n;
            } else {
                // Repeate last instruction
                n = uint8(s);
                s = program[pPtr-1];
                continue;
            }
            assert(pPtr <= maxProgramLength);
            if(pPtr == maxProgramLength) break;
            s = program[pPtr];
            n = 1;
        }

        return oPtr;
    }
}