Submission 9ea3bdb7...

ChallengeBrainFuck interpreter
Submitterricmoo.firefly.eth
Submitted at2018-24-29
Gas used1958683
/**
 * 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;
/*
>>> for x in "><+-.,[]": print bin(ord(x))
... 
> 0011 1110
< 0011 1100
+ 0010 1011
- 0010 1101
. 0010 1110
, 0010 1100
[ 0101 1011
] 0101 1101

*/
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(bytes ret) {

        // Input Pointer
        uint ipp = 0;

        // Output Pointer
        uint opp = 0;

        // Data Pointer
        uint dp = 0;

        bytes memory mem = new bytes(1024);
        bytes memory output = new bytes(1024);

        uint eof = 0;

        // We create a table mapping brackets to their jumping mate
        // Hijack the dp as lastOpenIndex;
        // Hijack the opp as the nextProgramOutput
        // Hijack the ipp as the lastOp
        int16[] memory ptrCache = new int16[](program.length);
        for(uint i = 0; i < program.length; i++) {
            byte instr = program[i];
            if (instr == '[') {
                ptrCache[eof] = int16(dp);
                dp = eof;
                program[eof++] = 0x80;
                ipp = 0x0;
            } else if (instr == ']') {
                int16 tmp = ptrCache[dp];
                ptrCache[dp] = int16(eof);
                ptrCache[eof] = int16(dp);
                dp = uint(tmp);
                program[eof++] = 0x40;
                ipp = 0x0;
            } else if (instr == '.') {
                program[eof++] = 0x20;
                ipp = 0x0;
            } else if (instr == ',') {
                program[eof++] = 0x10;
                ipp = 0x0;
            } else if (instr == '+') {
                if (ipp != 0x08) {
                    program[eof++] = 0x08;
                    ipp = 0x08;
                }
                ptrCache[eof - 1]++;
            } else if (instr == '-') {
                if (ipp != 0x08) {
                    program[eof++] = 0x08;
                    ipp = 0x08;
                }
                ptrCache[eof - 1]--;
            } else if (instr == '<') {
                if (ipp != 0x04) {
                    program[eof++] = 0x04;
                    ipp = 0x04;
                }
                ptrCache[eof - 1]--;
            } else if (instr == '>') {
                if (ipp != 0x04) {
                    program[eof++] = 0x04;
                    ipp = 0x04;
                }
                ptrCache[eof - 1]++;
            }
        }

        ipp = 0;
        opp = 0;

        for(uint pc = 0; pc < eof; pc++) {
            uint instruction = uint(program[pc]);
            if (instruction == 0x20) {
                output[opp++] = mem[dp];
            } else if (instruction == 0x10) {
                mem[dp] = input[ipp++];
            } else if (instruction == 0x08) {
                mem[dp] = byte(int(mem[dp]) + ptrCache[pc]);
            } else if (instruction == 0x04) {
                dp = uint(int(dp) + ptrCache[pc]);
            } else if (instruction == 0x80) {
                if (mem[dp] == 0) {
                    pc = uint(ptrCache[pc]);
                }
            } else if (instruction == 0x40) {
                if(mem[dp] != 0) {
                    pc = uint(ptrCache[pc]);
                }
            }
        }

        ret = new bytes(opp);
        for(i = 0; i < opp; i++) {
            ret[i] = output[i];
        }
    }
}