Submission d3ff70db...

ChallengeBrainFuck interpreter
Submitterhyszeth.eth
Submitted at2018-53-13
Gas used2398642
/**
 * 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(uint[]);

    /**
     * @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,
            uint[] memory jumpTable
        ) = analyze(program, programLength);
        if(!hasOutput) return;
        //return program;

        // Run
        uint[] memory data = new uint[](2048);    // store output at end of data
        programLength = runProgram(
            program,
            input,
            data,
            jumpTable,
            0,
            1024,
            0,
            0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
            0,
            programLength
        );

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

    function analyze(bytes program, uint programLength) internal pure returns (bool hasOutput, uint[] memory jumpTable) {
        // 1. Check for output
        // 2. Count unique instructions
        uint16 nBranches;
        //uint instructions;
        for(uint i = 0; i != programLength; ++i) {
            b = program[i];
            if(b == '.')  hasOutput = true;
            else if(b == '[') nBranches++;
            //else if(isValid(b)) instructions++;
        }
        if(!hasOutput) return (hasOutput, jumpTable);

        //sanitizedProgram = new uint[](2 * instructions);

        ///uint pPtr;

        // 2. Analyze program.
        //    - Replace bad characters with `*`. This helps with the next step.
        //    - Re-encode N consecutive instances of the same character (c) with [N][c]
        //    - Record branch beginnings and endings
        bool[256] memory lookup;
        lookup[uint8(byte('.'))] = true;
        lookup[uint8(byte(','))] = true;
        lookup[uint8(byte('+'))] = true;
        lookup[uint8(byte('-'))] = true;
        lookup[uint8(byte('<'))] = true;
        lookup[uint8(byte('>'))] = true;
        lookup[uint8(byte('['))] = true;
        lookup[uint8(byte(']'))] = true;

        byte b;
        byte last;
        uint count;
        uint16 balance;
        jumpTable = new uint[](programLength);
        uint[] memory branchBalances = new uint[](nBranches);
        uint branchEndI;
        nBranches = 0;
        for(i = 0; i != programLength; ++i) {
            b = program[i];
            if(b == '[') {
                branchBalances[balance++] = i;
            } else if(b == ']') {
                uint jumpLocation = branchBalances[--balance];
                jumpTable[jumpLocation] = i+1; // next instruction after ]
                jumpTable[i] = jumpLocation+1;
            } else if(!lookup[uint8(b)]) {
                b = (program[i] = '*');
            }

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

            last = b;
        }
    }

    function isInValid(byte b) internal pure returns (bool) {
        // Ordered by likely precedence, based on test data.
        return b & 8 != 8 && b != '>' && // 58 instances
               b != ',' && // 53 instances
               b != '+' && // 48 instances
               b != '-' && // 27 instances
               b != '.' && // 23 instances
               b != '<';// || // 14 instances
             //  b == '[' || // 7 instances
              // b == ']';   // 7 instances
    }


    function runProgram(
        bytes memory program,
        bytes memory input,
        uint[] memory data,
        uint[] memory jumpTable,
        uint16 oPtr,
        uint16 dPtr,
        uint16 jPtr,
        uint iPtr,
        uint pPtr,
        uint programLength
    )
        internal
        pure
        returns (uint16)
    {
        uint jumpTableLength = jumpTable.length;
        uint8 dCache;
        while(pPtr != programLength) {
            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(dCache != 0) pPtr = jumpTable[pPtr-n];
            } else if(cmd == '+') {
                dCache += n;
            } else if(cmd == '-') {
                dCache -= n;
            } else if(cmd == '>') {
                data[dPtr] = dCache;
                dPtr += n;
                dCache = uint8(data[dPtr]);
            } else if(cmd == '<') {
                data[dPtr] = dCache;
                dPtr -= n;
                dCache = uint8(data[dPtr]);
            } else if(cmd == ',') {
                iPtr += n;
                dCache = uint8(data[dPtr] = uint8(input[iPtr]));
            } else if(cmd == '.') {
                while(n-- != 0) data[oPtr++] = dCache; // cheaper than storing to var
            } else if(cmd == '[') {
                if(dCache == 0) pPtr = jumpTable[pPtr-n];
            }
        }

        return oPtr;
    }
}