Submission 554594fa...

Challenge	BrainFuck interpreter
Submitter	hyszeth.eth
Submitted at	2018-30-15
Gas used	1493644

/**
 * 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 {
    /**
     * @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(bytes32[])
        returns(bytes)
    {
        // Analyze
        uint[] memory data = new uint[](2048);    // store output at end of data
        uint programLength = program.length;
        (
            bool hasOutput,
            bytes32[] memory cleanProgram,
	        uint cleanProgramLength
        ) = analyze(program, data, program.length);
        if(!hasOutput) return;
        //return cleanProgram;


        programLength = runProgram(
            cleanProgram,
            input,
            data,
            0,
            1024,
            0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
            0,
            cleanProgramLength
        );

        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[] memory data, uint programLength) internal pure returns (bool hasOutput, bytes32[] memory cleanProgram, uint cleanPPtr) {
        // A lookup table for valid characters.
        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;

        // Check if there's output and count branches
        // 1. Redundant instructions are grouped.
        // 2. NOP characters are filtered out.
        // 3. An inline jumptable is created for `[` and `]`
        uint16 nBranches;
        byte b;
        uint count = 1;
        uint16 balance;
        cleanProgram = new bytes32[](programLength);
        uint i;
        do {
            b = program[i++];
            if(b == '[') {
                data[balance++] = cleanPPtr;
                cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000);
            } else if(b == ']') {
                uint jumpLocation = data[--balance];
                cleanProgram[jumpLocation] |= bytes32(cleanPPtr+1); // next instruction after ]
                cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000 | (jumpLocation+1));
            } else {
                count = 1;
                byte tmp;
                for(; i != programLength; i++) {
                    if(b == (tmp=program[i])) {
                        count++;
                    } else if(lookup[uint8(tmp)]) {
                        break;
                    }
                }
                if(lookup[uint8(b)]) {
                    cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000 | count);
                    if(b == '.') hasOutput = true;
                }
            }
        } while(i != programLength);
        return (hasOutput, cleanProgram, cleanPPtr);
    }

    function runProgram(
        bytes32[] memory program,
        bytes memory input,
        uint[] memory data,
        uint16 oPtr,
        uint dPtr,
        uint iPtr,
        uint pPtr,
        uint programLength
    )
        internal
        pure
        returns (uint16)
    {
        uint8 dCache;
        while(pPtr != programLength) {
            // Read next command
            bytes32 line = program[pPtr++];
            byte cmd = byte(line & 0xff00000000000000000000000000000000000000000000000000000000000000);
            uint n = uint(line & 0x00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);

            // Interpret
            if(cmd == ']') {
                if(dCache != 0) pPtr = n;
            } else if(cmd == '+') {
                dCache += uint8(n);
            } else if(cmd == '-') {
                dCache -= uint8(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 = n;
            }
        }

        return oPtr;
    }
}