Submission 4a98c59e...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-42-12
Gas used1460995
/**
 * 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.
     */


// 1508385

//                        Adds 3 and 5   24749
//                       Adds 9 and 17   35639
//                 Prints Hello World!  409336
//                       Far brackets.  106310
//               Test integer overflow   16831
//              Test integer underflow   15758
//   Allocate nearly 1024 memory cells  360883
//               Output lots of values  372650
// Total gas for BrainFuck: 1342156
// Real gas: 1474322

    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 bracestack;
        // 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++) {
            uint char = uint(program[i]);
            // 0x280000001000400000000000 == (1 << 91 | 1 << 93 | 1 << 46 | 1 << 60)
            if ((1 << char) & 0x000000001000400000000000 != 0) {
                if (char == 46) {
                    outpointer |= 1;
                } 
                else if (char == 60) {
                    outpointer |= 2;
                }
            }
        }
        if (outpointer & 1 == 0) {
            return new bytes(0);
        }
        if (outpointer & 2 == 0) {
            mask = 7;
        }
        outpointer = 0;
        match_lbrace = 0;

        for (i = 0; i < prog_len; i++) {
            char = uint(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) { // >
                    if (mask == 7) {
                        mem_curr = 0;
                    } else {
                        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);
                    }
                }
                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);
                }
                else if (char == 93) { // ]
                    if (mem_curr == 0) {
                        bracestack /= 0x100;
                    } else {
                        i = bracestack & 0xff;
                    }
                } else if (char == 91) {
                    bracestack = bracestack * 0x100 + i;
                }
            }
        }

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


    }
}