Submission d7c4a6db...

ChallengeBrainFuck interpreter
Submitter0xec3281124d4c2fc...
Submitted at2018-32-11
Gas used1464427
/**
 * 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 {
    /**
     * @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.
     */
    function execute(bytes program, bytes input) public pure returns(bytes) {
        bytes memory outputJumpCacheTape = new bytes(1024); // 0x0-0x01f length, 0x020-0x11F output, 0x120-0x31F jumpCache, 0x320-onward tape
        assembly {
            let inputCounter := 0
            let outputCounter := 0
            let tapePointer := 0
            let programStart := add(program, 0x20)
            {
                let jumpCachePointer := add(outputJumpCacheTape, 0x120)
                for {let programPointer := programStart } lt(programPointer, add(programStart, mload(program))) {programPointer := add(programPointer, 1)} {
                    switch byte(0, mload(programPointer))
                    case 0x5B {
                        mstore(jumpCachePointer, programPointer)
                        jumpCachePointer := add(jumpCachePointer, 0x40)
                        let depth := 1
                        for {let innerI := add(programPointer, 1)} lt(innerI, add(programStart, mload(program))) {innerI := add(innerI, 1)} {
                            switch byte(0, mload(innerI))
                            case 0x5D {
                                depth := sub(depth, 1)
                                switch depth
                                case 0 {
                                    mstore(sub(jumpCachePointer, 0x20), innerI)
                                    innerI := add(programStart, mload(program))
                                }
                            }
                            case 0x5B {
                                depth := add(depth, 1)
                            }
                        }
                    }

                }
            }
            for {let programPointer := programStart } lt(programPointer, add(programStart, mload(program))) {programPointer := add(programPointer, 1)} {
                switch byte(0, mload(programPointer))
                case 0x2B {
                    let dest := add(add(outputJumpCacheTape, 0x320), tapePointer)
                    mstore8(dest, add(byte(0, mload(dest)), 1))
                }
                case 0x2D {
                    let dest := add(add(outputJumpCacheTape, 0x320), tapePointer)
                    mstore8(dest, sub(byte(0, mload(dest)), 1))
                }
                case 0x3E {
                    tapePointer := add(tapePointer, 1)
                }
                case 0x3C {
                    tapePointer := sub(tapePointer, 1)
                }
                case 0x2E {
                    mstore8(add(add(outputJumpCacheTape, 0x20), outputCounter), byte(0, mload(add(add(outputJumpCacheTape, 0x320), tapePointer))))
                    outputCounter := add(outputCounter, 1)
                }
                case 0x2C {
                    mstore8(add(add(outputJumpCacheTape, 0x320), tapePointer), byte(0, mload(add(add(input, 0x20), inputCounter))))
                    inputCounter := add(inputCounter, 1)
                }
                case 0x5B {
                    switch byte(0, mload(add(add(outputJumpCacheTape, 0x320), tapePointer)))
                    case 0 {
                        for {let i := add(outputJumpCacheTape, 0x120)} lt(i, add(outputJumpCacheTape, 0x320)) {i := add(i, 0x40)} {
                            if eq(mload(i), programPointer) {
                                programPointer := mload(add(i, 0x20))
                                i := add(outputJumpCacheTape, 0x320)
                            }
                        }
                    }
                }
                case 0x5D {
                    switch iszero(byte(0, mload(add(add(outputJumpCacheTape, 0x320), tapePointer))))
                    case 0 {
                        for {let i := add(outputJumpCacheTape, 0x140)} lt(i, add(outputJumpCacheTape, 0x320)) {i := add(i, 0x40)} {
                            if eq(mload(i), programPointer) {
                                programPointer := mload(sub(i, 0x20))
                                i := add(outputJumpCacheTape, 0x320)
                            }
                        }
                    }
                }
            }
            mstore(outputJumpCacheTape, outputCounter)
        }
        return outputJumpCacheTape;
    }
}