Submission 93d49690...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-21-01
Gas used1451132
/**
 * 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   21544
//                       Adds 9 and 17   27916
//                 Prints Hello World!  234895
//                       Far brackets.  575199
//               Test integer overflow   16733
//              Test integer underflow   16112
//   Allocate nearly 1024 memory cells  278563
//               Output lots of values  180784
// Total gas for BrainFuck: 1351746

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

        uint prog_len = program.length;
        bytes memory tape = new bytes(1024);
        bytes memory output = new bytes(1024);
        bytes memory outputstart = output;
        uint[] memory brace = new uint[](prog_len);
        uint mem_curr = 0;
        uint divisor    = 0x0100000000000000000000000000000000000000000000000000000000000000;
        uint mask       = 0xff00000000000000000000000000000000000000000000000000000000000000;

        assembly {
            let match_lbrace := 0
            for { let i := 0 } lt(i, prog_len) { i := add(i, 1) } {
                let char := div(mload(add(program, add(i, 0x20))), divisor)
                switch char
                case 91 {
                    mstore(add(brace, add(mul(i, 0x20), 0x20)), match_lbrace)
                    match_lbrace := i
                }
                case 93 {
                    mstore(add(brace, add(mul(i, 0x20), 0x20)), match_lbrace)
                    match_lbrace := mload(add(brace, add(mul(match_lbrace, 0x20), 0x20)))
                }
            }

            input := add(input, 0x20)
            output := add(output, 0x20)
            tape := add(tape, 0x20)

            for { let i := 0 } lt(i, prog_len) { i := add(i, 1) } {
                let char := div(mload(add(program, add(i, 0x20))), divisor)

                switch char
                case 43 {
                    mem_curr := add(mem_curr, divisor)
                }
                case 45 {
                    mem_curr := sub(mem_curr, divisor)
                }
                case 44 {
                    mem_curr := mload(input)
                    input := add(input, 1)
                }
                case 46 {
                    mstore8(output, div(mem_curr, divisor))
                    output := add(output, 1)                    
                }
                case 62 {
                    mstore8(tape, div(mem_curr, divisor))
                    tape := add(tape, 1)
                    mem_curr := mload(tape)
                }
                case 60 {
                    mstore8(tape, div(mem_curr, divisor))
                    tape := sub(tape, 1)
                    mem_curr := mload(tape)
                }
                case 93 {
                    if and(mem_curr, mask) {
                        i := mload(add(brace, add(0x20, mul(i, 0x20))))
                    }
                }
            }
            mstore(outputstart, sub(output, add(outputstart, 0x20)))
        }
        return outputstart;
    }
}