Submission 7424a196...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-13-27
Gas used1649303
/**
 * 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;

contract BrainFuck {
    event PointerMove (uint abc);
    /**
     * @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.
     */

//                        Adds 3 and 5   25361
//                       Adds 9 and 17   37007
//                 Prints Hello World!  425838
//                       Far brackets.  110458
//               Test integer overflow   16983
//              Test integer underflow   15878
//   Allocate nearly 1024 memory cells  100210
//               Output lots of values  401387
// Total gas for BrainFuck: 1133122

    function execute(bytes program, bytes input) public pure returns(bytes) {
        // [62 60 43 45 46 44 91 93]
        //  >  <  +  -  .  ,  [  ]

        uint prog_len = program.length;
        uint[] memory tape = new uint[](32);
        uint8[] memory output = new uint8[](1024);
        uint[] memory brace = new uint[](prog_len);
        uint pointer = 0;
        uint outpointer = 0;
        uint inpointer = 0;
        uint i = 0;
        uint match_lbrace = 0; // also reused as tape cache 
        uint8 mem_curr = 0;
        uint mask = 0x1;

        for (i = 0; i < prog_len; i++) {
            uint8 char = uint8(program[i]);
            if (char == 91) { // [
                brace[i] = match_lbrace;
                match_lbrace = i;
            }
            else if (char == 93) { // ]
                brace[i] = match_lbrace;
                match_lbrace = brace[match_lbrace];
            } else if (char == 46) {
                outpointer = 1;
            }
        }
        if (outpointer == 0) {
            return new bytes(0);
        }
        outpointer = 0;
        match_lbrace = 0;

        for (i = 0; i < prog_len; i++) {
            char = uint8(program[i]);

            if (char < 50) {
                if (char == 43) { // +
                    mem_curr++;  
                }
                else if (char == 45) { // -
                    mem_curr--;
                }
                else if (char == 44) { // ,
                    mem_curr = uint8(input[inpointer++]);
                }
                else if (char == 46) { // .
                    output[outpointer++] = mem_curr;
                }
            } else {
                if (char == 62) { // >
                    match_lbrace = (match_lbrace & ~(mask * 0xff)) | (mask * mem_curr);
                    mask *= 0x100;
                    if (mask == 0) {
                        tape[pointer] = match_lbrace;
                        match_lbrace = tape[++pointer];
                        mask = 1;
                    }
                    mem_curr = uint8((match_lbrace & (mask * 0xff)) / mask);
                }
                else if (char == 60) { // <
                    match_lbrace = (match_lbrace & ~(mask * 0xff)) | (mask * mem_curr);
                    mask /= 0x100;
                    if (mask == 0) {
                        tape[pointer] = match_lbrace;
                        match_lbrace = tape[--pointer];
                        mask = 0x0100000000000000000000000000000000000000000000000000000000000000;
                    }
                    mem_curr = uint8((match_lbrace & (mask * 0xff)) / mask);
                }
                else if (char == 93) { // ]
                    if (mem_curr != 0) {
                        i = brace[i];
                    }
                }
            }
        }

        // reuse program variable
        program = new bytes(outpointer);
        for (i = 0; i < outpointer; i++) {
            program[i] = byte(output[i]);
        }
        return program;


    }
}