Submission 75beda2e...

ChallengeBrainFuck interpreter
Submitterzac.creditmint.eth
Submitted at2018-53-18
Gas used137356
/**
 * 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, 0x60)
                mstore(0x20, sub(strike_faustian_bargain, no_op))
                mstore(0x00, 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)
                0x44
                strike_faustian_bargain:        // stack state c
                    0x20 add
                    0x20
                    dup2 calldataload           // w c
                    dup1 0 byte 0x20 mul 0xfc0 mstore
                    0x20 mul dup1 0xfe0 mstore     // w c
                    0x1fff and                  // 0 c
                    0xfdf mload 0x1fe0 and
                    0xfde mload 0x1fe0 and
                    0xfdd mload 0x1fe0 and
                    0xfdc mload 0x1fe0 and
                    0xfdb mload 0x1fe0 and
                    0xfda mload 0x1fe0 and
                    0xfd9 mload 0x1fe0 and
                    0xfd8 mload 0x1fe0 and
                    0xfd7 mload 0x1fe0 and
                    0xfd6 mload 0x1fe0 and
                    0xfd5 mload 0x1fe0 and
                    0xfd4 mload 0x1fe0 and
                    0xfd3 mload 0x1fe0 and
                    0xfd2 mload 0x1fe0 and
                    0xfd1 mload 0x1fe0 and
                    0xfd0 mload 0x1fe0 and
                    0xfcf mload 0x1fe0 and
                    0xfce mload 0x1fe0 and
                    0xfcd mload 0x1fe0 and
                    0xfcc mload 0x1fe0 and
                    0xfcb mload 0x1fe0 and
                    0xfca mload 0x1fe0 and
                    0xfc9 mload 0x1fe0 and
                    0xfc8 mload 0x1fe0 and
                    0xfc7 mload 0x1fe0 and
                    0xfc6 mload 0x1fe0 and
                    0xfc5 mload 0x1fe0 and
                    0xfc4 mload 0x1fe0 and
                    0xfc3 mload 0x1fe0 and
                    0xfc2 mload 0x1fe0 and
                    0xfc0 mload

                no_op:
                    mload no_op add jump

                // > (0x3e * 0x20)
                compile_increment_data_pointer:
                    mstore(msize, increment_data_pointer)
                    0x1fe0 and mload no_op add jump

                // <
                compile_decrement_data_pointer:
                    mstore(msize, decrement_data_pointer)
                    0x1fe0 and mload no_op add jump

                // +
                compile_increment_data_cell:
                    mstore(msize, increment_data_cell)
                    0x1fe0 and mload no_op add jump

                // -
                compile_decrement_data_cell:
                    mstore(msize, decrement_data_cell)
                    0x1fe0 and mload no_op add jump

                // .
                compile_output_data_cell:
                    mstore(msize, output_data_cell)
                    0x1fe0 and mload no_op add jump

                // ,
                compile_input_to_data_cell:
                    mstore(msize, input_to_data_cell)
                    0x1fe0 and mload no_op add jump

                // [
                compile_conditional_jump_forward:
                    mstore(msize, conditional_jump_forward)
                    0x40 mload msize dup2 mstore
                    0x20 add 0x40 mstore
                    gas msize mstore // hmmmmmmm
                    0x1fe0 and mload no_op add jump

                // ]
                compile_conditional_jump_backward:
                    0x20 0x40 mload sub dup1 0x40 mstore mload
                    conditional_jump_backward msize mstore
                    0x20 dup2 add msize mstore
                    msize swap1 mstore
                    0x1fe0 and mload no_op add jump    

                finished_compilation:
                    mstore(msize, finish_execution)

                add(calldataload(0x24), 0x05) // i
                0x400                         // o
                0x120                         // d
                0x1000                        // p
                dup1 mload jump

                increment_data_pointer:     // p d o i
                    swap1 0x01 add swap1
                    0x20 add dup1
                    mload jump

                decrement_data_pointer:
                    0x01 dup3 sub swap2 pop
                    0x20 add dup1
                    mload jump

                increment_data_cell:
                    0x0100000000000000000000000000000000000000000000000000000000000000
                    dup3 mload add dup3 mstore
                    0x20 add dup1
                    mload jump

                decrement_data_cell:
                    0x0100000000000000000000000000000000000000000000000000000000000000
                    dup3 mload sub dup3 mstore
                    0x20 add dup1
                    mload jump

                output_data_cell:
                    dup2 mload dup4 0x01 add swap4 mstore
                    0x20 add dup1
                    mload jump

                input_to_data_cell:
                    dup4 0x01 add swap4 calldataload dup3 mstore8
                    0x20 add dup1
                    mload jump
    
                conditional_jump_forward:
                    0xff00000000000000000000000000000000000000000000000000000000000000
                    dup3 mload and skip_jump_forward jumpi
                    0x20 add mload dup1
                    mload jump
                skip_jump_forward:
                    0x40 add dup1
                    mload jump

                conditional_jump_backward:
                    0xff00000000000000000000000000000000000000000000000000000000000000
                    dup3 mload and jump_backward jumpi
                    0x40 add dup1
                    mload jump
                jump_backward:
                    0x20 add mload dup1
                    mload jump

                finish_execution:
                0x00 dup4 mstore
                0x400 dup4 sub 0x3e0 mstore
                mstore(0x3c0, 0x20)
                0x60 0x20 0x20 0x401 dup7 sub div mul add 0x3c0 return
                
        pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop pop
        }
    }
}