Submission d430ee8d...

ChallengeBrainFuck interpreter
Submitterhyszeth.eth
Submitted at2018-23-08
Gas used3511430
/**
 * 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);
    event E(uint256);
    /**
     * @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
        //emit E(string(program));
        (bool hasOutput, uint16 nBranches) = optimize(program);
        if(!hasOutput) return;
        //emit E(string(program));

        // Run
        bytes memory data = new bytes(1024);    // store output at end of data
        uint[] memory programBegin = new uint[](nBranches);  // max stack depth
        return runProgram(
            program,
            input,
            data,
            0,
            0,
            0,
            0,
            program.length,
            programBegin
        );
    }

    function optimize(bytes program) internal pure returns (bool hasOutput, uint16 nBranches) {
        byte s;
        byte last;
        uint8 count; // Q: What happens if count > 255?
        uint maxProgramLength = program.length;
        int8 lastIsValid = -1;
        bool stateChanged;
        for(uint pPtr = 0; pPtr < maxProgramLength; pPtr++) {
            s=program[pPtr];
            int8 isValid;
            bool same;
            if(s == '[') {
                //if(stateChanged) {
                    nBranches++;
                    isValid = 1;
                    same = (s == last);
                /*} else {
                    // we know this cannot evaluate to true. Erase it all!
                    uint balance = 1; // find corresponding ']' and turn it all to garbage
                    count = 0;
                    while(balance > 0) {
                        s = program[++pPtr];
                        if(s == '[') balance++;
                        else if(s == ']') balance--;
                        count++;
                    }
                    // set state for update below
                    program[pPtr-count] = '*';
                    isValid = -1;
                    same = false;
                    count -= 1;
                }*/
            } else if(s == ']' || s == '>' || s == '<') {
                isValid = 1;
                same = (s == last);
            } else if(s == '+' || s == '-' || s == ',') {
                stateChanged = true;
                isValid = 1;
                same = (s == last);
            } else if(s == '.') {
                hasOutput = true;
                isValid = 1;
                same = (s == last);
            } else if(uint8(s) <= 0x29){
                // isValid == false and it's in our "repeate instruction" range
                // So, we'll switch it to be *
                program[pPtr] = s = '*';
                if(lastIsValid == 0) same = true;
            } else {
                //if(lastIsValid == 0) same = true;
            }

            if(s == last && count < 0x29) { // 0x29 is last char before our special characters start
                count++;
            } else if(count == 1) {
                count = 0;
            } else if(count > 1) {
                program[pPtr-count-1] = byte(count+1);
                count = 0;
            }

            last = s;
            lastIsValid = isValid;
        }

        if(count > 1 && count < 0x29) {
            program[pPtr-count] = byte(count);
        }
    }

    function runProgram(
        bytes program,
        bytes input,
        bytes data,
        uint oPtr,
        uint pPtr,
        uint iPtr,
        uint dPtr,
        uint maxProgramLength,
        uint[] memory programBegin
    )
        internal
        pure
        returns (bytes memory sanitizedOutput)
    {
        bytes memory output = new bytes(1024);
        uint programBeginIndex;
        byte s = program[pPtr];
        byte last = byte(uint8(s)+1); // just need it to not equal s
        uint8 n = 1;
        while(true) {
            if(s == '[') {
                while(n-- > 0) programBegin[programBeginIndex++] = ++pPtr;
            } else if(s == ']') {
                if(data[dPtr] == 0) {
                    programBeginIndex -= n;
                    pPtr += n;
                } else {
                    pPtr = programBegin[programBeginIndex-n];
                }
            } 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;
                data[dPtr] = input[(iPtr+=(n-1))];
                iPtr++;
            } else if(s == '.') {
                pPtr += n;
                last = data[dPtr]; // recycle last
                while(n-- > 0) output[oPtr++] = last;
            } else if(uint8(s) <= 0x29){
                // Repeat next instruction
                n = uint8(s);
                s = program[pPtr+1];
                continue;
                //s = last;
                //continue;
            } else {
                pPtr += n;
            }
            if(pPtr == maxProgramLength) break;
            s = program[pPtr];
            n = 1;
        }

        sanitizedOutput = new bytes(oPtr);
        dPtr = 0; // recycle dPtr
        while(dPtr < oPtr) {
            sanitizedOutput[dPtr++] = output[dPtr];
        }
        return sanitizedOutput;
    }
}