Submission 5edcc295...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-38-01
Gas used692683
/**
 * 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_end = program.length;
        uint[] memory tape = new uint[](32);
        uint[] memory output = new uint[](32);
        bytes memory outputstart;
        uint[] memory bracestack = new uint[](4); // assume max 4 braces deep
        uint divisor    = 0x0100000000000000000000000000000000000000000000000000000000000000;
        uint mask       = 0xff00000000000000000000000000000000000000000000000000000000000000;

        assembly {
            outputstart := output
            let mem_curr := 0
            bracestack := add(bracestack, 0x20)

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

            program := add(program, 0x20)
            prog_end := add(prog_end, program)

            let j := program
            for { let i := program } lt(i, prog_end) { i := add(i, 1) } {
                let char := div(mload(i), divisor)

                mem_curr := exp(2, char)
                // mask := or(mask, mem_curr)
                if and(mem_curr, 0x280000005000780000000000) {
                    mstore8(j, char)
                    j := add(j, 1)
                }
            }

            mem_curr := 0
            prog_end := j

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

                // switch char
                switch char
                case 43 {
                    mem_curr    := add(mem_curr, divisor)
                }
                case 44 {
                    mem_curr := mload(input)
                    input := add(input, 1)
                }
                case 45 {
                    mem_curr := sub(mem_curr, divisor)
                }
                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 {
                    switch and(mem_curr, mask) case 0 {
                        bracestack := sub(bracestack, 0x20)
                    } default {
                        i := mload(bracestack)
                    }
                }
                case 91 {
                    bracestack := add(bracestack, 0x20)
                    mstore(bracestack, i)
                }
            }
            mstore(outputstart, sub(output, add(outputstart, 0x20)))
        }
        return outputstart;
    }
}