Submission bb263b18...

ChallengeBrainFuck interpreter
Submitterhyszeth.eth
Submitted at2018-20-11
Gas used2612692
/**
 * 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/
 *
 *
 *
 * Author: Greg Hysen (@hysz)
 * Date: 05/2018
 *
 */

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,
            1024,
            0,
            0,
            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 == '+' || b == '-' || b == '>' || b == '<' || b == ',' || b == ']' ) {}
            else 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,
        uint16 oPtr,
        uint16 dPtr,
        uint pPtr,
        uint iPtr,
        uint maxProgramLength,
        uint[] memory programBegin
    )
        internal
        pure
        returns (uint)
    {
        uint pPtrMax;
        uint programBeginIndex;
        programBeginIndex--;
        iPtr -= 1;

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

        return oPtr;
    }
}