Submission c12d9ac2...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-56-02
Gas used577231
/**
 * 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.
     */


// 0x16
// 0x34
// 0x38a
// 0x0
// 0x6
// 0x5
// 0x422
// 0x301

//                        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 returns(bytes) {
        // [62 60 43 45 46 44 91 93]
        //  >  <  +  -  .  ,  [  ]

        uint prog_end = program.length;
        uint[] memory tape;
        uint[] memory output;
        bytes memory outputstart;
        uint[] memory bracestack; // assume max 4 braces deep
        uint divisor    = 0x0100000000000000000000000000000000000000000000000000000000000000;
        uint mask       = 0xff00000000000000000000000000000000000000000000000000000000000000;

        assembly {
            let prog_mask := 0

            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)

                let charbit := exp(2, char)
                if and(charbit, 0x280000005000780000000000) {
                    mstore8(j, char)
                    j := add(j, 1)
                }
                prog_mask := or(prog_mask, charbit)
            }
            prog_end := j

            if iszero(and(prog_mask, 0x400000000000)) {
                divisor := 1
            }
        }

        if (divisor == 1) {
            return new bytes(0);
        }

        tape = new uint[](32);
        output = new uint[](32);
        bracestack = new uint[](4); // assume max 4 braces deep

        assembly {
            bracestack := add(bracestack, 0x20)
            outputstart := output
            input := add(input, 0x20)
            output := add(output, 0x20)
            tape := add(tape, 0x20)

            let mem_curr := 0

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

                jumpi(tag_sub50, lt(char, 50))
                jumpi(tag_62, eq(char, 62))
                jumpi(tag_60, eq(char, 60))
                jumpi(tag_93, eq(char, 93))
                jump(tag_91)

                tag_sub50:
                    jumpi(tag_gt44, gt(char, 44))
                    jumpi(tag_43, eq(char, 43))
                    jumpi(tag_44, eq(char, 44))
                    tag_gt44:
                        jumpi(tag_45, eq(char, 45))
                        jump(tag_46)
                tag_43:
                    mem_curr    := add(mem_curr, divisor)
                    jump(loop_end)
                tag_44:
                    mem_curr := mload(input)
                    input := add(input, 1)
                    jump(loop_end)
                tag_45:
                    mem_curr := sub(mem_curr, divisor)
                    jump(loop_end)
                tag_46:
                    mstore8(output, div(mem_curr, divisor))
                    output := add(output, 1)                    
                    jump(loop_end)
                tag_62:
                    mstore8(tape, div(mem_curr, divisor))
                    tape := add(tape, 1)
                    mem_curr := mload(tape)
                    jump(loop_end)
                tag_60:
                    mstore8(tape, div(mem_curr, divisor))
                    tape := sub(tape, 1)
                    mem_curr := mload(tape)
                    jump(loop_end)
                tag_93:
                    switch and(mem_curr, mask) case 0 {
                        bracestack := sub(bracestack, 0x20)
                    } default {
                        i := mload(bracestack)
                    }
                    jump(loop_end)
                tag_91:
                    bracestack := add(bracestack, 0x20)
                    mstore(bracestack, i)
                    jump(loop_end)
                loop_end:
            }
            // mstore(outputstart, 0x20)
            // mstore(add(outputstart, 0x20), count)
            mstore(outputstart, sub(output, add(outputstart, 0x20)))
        }
        return outputstart;
    }
}