Submission 3aa6cf40...

ChallengeBrainFuck interpreter
Submitterhyszeth.eth
Submitted at2018-45-11
Gas used2765357
/**
 * 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)
    {
        // Analyze
        uint programLength = program.length;
        (bool hasOutput, uint16 nBranches) = analyze(program, programLength);
        if(!hasOutput) return;

        // Run
        uint8[] memory data = new uint8[](2048 + nBranches);    // store output at end of data
        uint[] memory programBegin = new uint[](nBranches);  // max stack depth
        uint oPtr = runProgram(
            program,
            input,
            data,
            0,
            0,
            0,
            1024,
            programLength,
            programBegin
        );

        bytes memory output = new bytes(oPtr);
        for(uint i = 0; i < oPtr; ++i) {
            output[i] = byte(data[i]);
        }
        return output;
    }

    function analyze(bytes program, uint programLength) internal pure returns (bool hasOutput, uint16 nBranches) {
        byte b;
        byte last;
        uint count;
        for(uint i = 0; i < programLength; ++i) {
            b = program[i];
            if(b == '.') hasOutput = true;
            else if(b == '[') nBranches++;
            else if(b < 0x2A) b = program[i] = '*';

            if(b == last && count < 0x2A) {
                count++;
            } else if(count > 1) {
                program[i-count] = byte(count);
                count = 1;
            }

            last = b;
        }
    }

    event E(byte, uint8);

    function runProgram(
        bytes program,
        bytes input,
        uint8[] data,
        uint oPtr,
        uint pPtr,
        uint iPtr,
        uint dPtr,
        uint maxProgramLength,
        uint[] memory programBegin
    )
        internal
        pure
        returns (uint)
    {
        uint pPtrMax;
        uint programBeginIndex;
        programBeginIndex--;

        while(pPtr < maxProgramLength) {
            byte cmd = program[pPtr];
            uint8 n;
            if(cmd < 0x2A) {
                n = uint8(cmd);
                cmd = program[pPtr+1];
                pPtr += n;
            } else {
               pPtr++;
               n = 1;
            }

            // Interpret
            if(cmd == '[') {
                while(n-- > 0) programBegin[++programBeginIndex] = (pPtr-n);
            } else if(cmd == ']') {
                if(data[dPtr] == 0) {
                    programBeginIndex -= n;
                } else {
                    pPtr = programBegin[programBeginIndex+1-n];
                }
            } else if(cmd == '>') {
                dPtr += n;
            } else if(cmd == '<') {
                dPtr -= n;
            } else if(cmd == '+') {
                data[dPtr] += n;
            } else if(cmd == '-') {
                data[dPtr] -= n;
            } else if(cmd == ',') {
                iPtr += n;
                data[dPtr] = uint8(input[iPtr-1]);
            } else if(cmd == '.') {
                while(n-- > 0) data[oPtr++] = data[dPtr]; // cheaper than storing to var
            }
        }

        return oPtr;
    }
}