Submission b1e154ce...

ChallengeBrainFuck interpreter
Submitterricmoo.firefly.eth
Submitted at2018-51-29
Gas used1355175
/**
 * 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: Richard Moore <[email protected]>
 *  Date: May 29, 2018
 */

pragma solidity 0.4.24;

/**
 *  >>> for x in "><+-.,[]": print bin(ord(x))
 * > 0011 1110
 * < 0011 1100
 * + 0010 1011
 * - 0010 1101
 * . 0010 1110
 * , 0010 1100
 * [ 0101 1011
 * ] 0101 1101
 *
 * < 0011 1100
 * - 0010 1101
 *
 * > 0011 1110
 * + 0010 1011
 *
 */

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.
     */

/*
              if (op == 0x2b || op == 0x3e) {                     // "+" or ">"
                op = op & 0x30;
                if (ipp != op) {
                    program[eof++] = byte(op);
                    ipp = op;
                }
                ptrCache[eof - 1]++;
*/

/*
            } else if (op == 0x2d || op == 0x3c) {                            // "-"
                op = op & 0x30;
                if (ipp != op) {
                    ipp = op;
                    program[eof++] = byte(op);
                }
                ptrCache[eof - 1]--;
*/

    function execute(bytes program, bytes input) public pure returns(bytes ret) {

        // Input Pointer
        uint ipp = 0;

        // Output Pointer
        uint opp = 1024;

        // Data Pointer
        uint dp = 0;

        //byte[] memory mem = new byte[](1024);
        //byte[] memory output = new byte[](1024);
        byte[] memory scratch = new byte[](2048);

        // Operation
        uint op = 0;

        // End-of-file (of the transcoded source)
        uint eof = 0;

        // Transcode the source code into 2 concise streams: an "ops" (bytes) and a "values" (int16)
        //    - "[" and "]" link to their jumping maes
        //    - "+" and "-" link to the total value of ops (e.g. "++-+" = 2)
        //    - "<" and ">" link to the total distance (e.g. ">><>" = 2)
        //    - "." and "," remain
        //    - anything else is removed
        // Note: Hijacked the ipp as the lastOp
        // Note: Hijacked dp as the lastOpenIndex
        // Note: This may fail if the program is longer than 32kb of meaningful bytes
        uint16[] memory ptrCache = new uint16[](program.length);
        for(uint i = 0; i < program.length; i++) {
            op = uint(program[i]);

            if (op == 0x3e) {                     // ">"
                if (ipp != 0x30) {
                    program[eof++] = 0x30;
                    ipp = 0x30;
                }
                ptrCache[eof - 1]++;
            } else if (op == 0x3c) {                     // "<"
                if (ipp != 0x30) {
                    program[eof++] = 0x30;
                    ipp = 0x30;
                }
                ptrCache[eof - 1]--;
            } else if (op == 0x2b) {                     // "+"
                if (ipp != 0x20) {
                    program[eof++] = 0x20;
                    ipp = 0x20;
                }
                ptrCache[eof - 1]++;
            } else if (op == 0x2d) {                            // "-"
                if (ipp != 0x20) {
                    program[eof++] = 0x20;
                    ipp = 0x20;
                }
                ptrCache[eof - 1]--;
            } else if (op == 0x5b) {                     // "["
                ptrCache[eof] = uint16(dp);
                dp = eof;
                program[eof++] = 0x80;
                ipp = 0x0;
            } else if (op == 0x5d) {                     // "]"
                uint16 tmp = ptrCache[dp];
                ptrCache[dp] = uint16(eof);
                ptrCache[eof] = uint16(dp);
                dp = uint(tmp);
                program[eof++] = 0x81;
                ipp = 0x0;
            } else if (((op - 0x2c) | 0x02) == 0x02) {     // "," or "."
                program[eof++] = byte(op);
                ipp = 0x0;
            }
        }

        dp = 0;
        ipp = 0;

        for(uint pc = 0; pc < eof; pc++) {
            op = uint(program[pc]);
            if (op == 0x80) {
                if (scratch[dp] == 0) {
                    pc = uint(ptrCache[pc]);
                }
            } else if (op == 0x81) {
                if (scratch[dp] != 0) {
                    pc = uint(ptrCache[pc]);
                }
            } else if (op == 0x20) {
                scratch[dp] = byte(uint8(scratch[dp]) + uint8(ptrCache[pc]));
            } else if (op == 0x30) {
                dp = uint(int16(dp) + int16(ptrCache[pc]));
            } else if (op == 0x2e) {
                scratch[opp++] = scratch[dp];
            } else { //if (op == 0x2c) {
                scratch[dp] = input[ipp++];
            }
/*
            } else {
                if ((mem[dp] == 0) == (op == 0)) {
                    pc = uint(ptrCache[pc]);
                }
*/
//            }
        }

        ret = new bytes(opp - 1024);
        for(i = 1024; i < opp; i++) {
            ret[i - 1024] = scratch[i];
        }
    }
}