Submission 65b74e5c...

ChallengeBrainFuck interpreter
Submitterzac.creditmint.eth
Submitted at2018-27-18
Gas used170688
/**
 * 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.23;

contract BrainFuck {
    /**
     * @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.
     *
     * @return The program's output stream. Should be exactly the length of the
     *          number of outputs produced by the program.
     */
    function execute(bytes, bytes) external view returns(bytes) {
        assembly {
                mstore(0x40, 0x00) // get outta here, free memory pointer...
                mstore(calldataload(calldataload(0x24)), sub(finished_compilation, no_op))
                mstore(0x7c0, sub(compile_increment_data_pointer, no_op))
                mstore(0x780, sub(compile_decrement_data_pointer, no_op))
                mstore(0x560, sub(compile_increment_data_cell, no_op))
                mstore(0x5a0, sub(compile_decrement_data_cell, no_op))
                mstore(0x5c0, sub(compile_output_data_cell, no_op))
                mstore(0x580, sub(compile_input_to_data_cell, no_op))
                mstore(0xb60, sub(compile_conditional_jump_forward, no_op))
                mstore(0xba0, sub(compile_conditional_jump_backward, no_op))

                mstore(0xfe0, 0x1)
                let jumpPointer := 0x20
                let calldataPointer := 0x44
                no_op:
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // > (0x3e * 0x20)
                compile_increment_data_pointer:
                    mstore(msize, increment_data_pointer)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // <
                compile_decrement_data_pointer:
                    mstore(msize, decrement_data_pointer)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // +
                compile_increment_data_cell:
                    mstore(msize, increment_data_cell)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // -
                compile_decrement_data_cell:
                    mstore(msize, decrement_data_cell)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // .
                compile_output_data_cell:
                    mstore(msize, output_data_cell)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // ,
                compile_input_to_data_cell:
                    mstore(msize, input_to_data_cell)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // [
                compile_conditional_jump_forward:
                    mstore(msize, conditional_jump_forward)
                    mstore(jumpPointer, msize)
                    mstore(msize, 0x01) // hmmmmmmm
                    jumpPointer := add(jumpPointer, 0x20)
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                // ]
                compile_conditional_jump_backward:
                    jumpPointer := sub(jumpPointer, 0x20) 
                    mstore(mload(jumpPointer), add(msize, 0x40))
                    mstore(msize, conditional_jump_backward)
                    mstore(msize, add(mload(jumpPointer), 0x20))
                    calldataPointer := add(calldataPointer, 0x01)
                    jump(add(no_op, mload(and(mul(calldataload(calldataPointer), 0x20), 0x1fff))))

                finished_compilation:
                    mstore(msize, finish_execution)

                let program_counter := 0x1000
                let data_pointer := 0x120
                let output_pointer := 0x400
                let input_pointer := add(calldataload(0x24), 0x05)
                jump(mload(program_counter))

                increment_data_pointer:
                    data_pointer := add(data_pointer, 0x01)
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))

                decrement_data_pointer:
                    data_pointer := sub(data_pointer, 0x01)
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))

                increment_data_cell:
                    mstore(data_pointer, add(mload(data_pointer), 0x0100000000000000000000000000000000000000000000000000000000000000))
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))

                decrement_data_cell:
                    mstore8(data_pointer, sub(mload(sub(data_pointer, 0x1f)), 0x01))
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))

                output_data_cell:
                    mstore8(output_pointer, mload(sub(data_pointer, 0x1f)))
                    output_pointer := add(output_pointer, 0x01)
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))

                input_to_data_cell:
                    mstore8(data_pointer, calldataload(input_pointer))
                    input_pointer := add(input_pointer, 0x01)
                    program_counter := add(program_counter, 0x20)
                    jump(mload(program_counter))
    
                conditional_jump_forward:
                    jumpi(skip_jump_forward, and(mload(data_pointer), 0xff00000000000000000000000000000000000000000000000000000000000000))
                    program_counter := mload(add(program_counter, 0x20))
                    jump(mload(program_counter))
                skip_jump_forward:
                    program_counter := add(program_counter, 0x40)
                    jump(mload(program_counter))

                conditional_jump_backward:
                    jumpi(jump_backward, and(mload(data_pointer), 0xff00000000000000000000000000000000000000000000000000000000000000))
                    program_counter := add(program_counter, 0x40)
                    jump(mload(program_counter))

                jump_backward:
                    program_counter := mload(add(program_counter, 0x20))
                    jump(mload(program_counter))


                finish_execution:
                // mstore(add(output_pointer, 0x01), 0x00)
                mstore(0x3e0, sub(output_pointer, 0x400))
                mstore(0x3c0, 0x20)
                return(0x3c0, add(mul(div(sub(output_pointer, 0x401), 0x20), 0x20), 0x60))
        }
    }
}