Submission 1af9feff...

ChallengeBrainFuck interpreter
Submitter0xec3281124d4c2fc...
Submitted at2018-47-09
Gas used1952428
/**
 * 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 memory program, bytes memory input) public pure returns(bytes) {
        uint ipp = 0;
        uint opp = 0;
        uint dp = 0;
        bytes memory mem = new bytes(1024);
        bytes memory output = new bytes(1024);
        assembly {
            let programStart := add(program, 0x20)
            for {let ip := programStart } lt(ip, add(programStart, mload(program))) {ip := add(ip, 1)} {
                switch byte(0, mload(ip))
                case 0x2B {
                    let dest := add(add(mem, 0x20), dp)
                    mstore8(dest, add(byte(0, mload(dest)), 1))
                }
                case 0x2D {
                    let dest := add(add(mem, 0x20), dp)
                    mstore8(dest, sub(byte(0, mload(dest)), 1))
                }
                case 0x3E {
                    dp := add(dp, 1)
                }
                case 0x3C {
                    dp := sub(dp, 1)
                }
                case 0x2E {
                    mstore8(add(add(output, 0x20), opp), byte(0, mload(add(add(mem, 0x20), dp))))
                    opp := add(opp, 1)
                }
                case 0x2C {
                    mstore8(add(add(mem, 0x20), dp), byte(0, mload(add(add(input, 0x20), ipp))))
                    ipp := add(ipp, 1)
                }
                case 0x5B {
                    switch byte(0, mload(add(add(mem, 0x20), dp)))
                    case 0 {
                        let depth := 1
                        for {let i := add(ip, 1)} lt(i, add(programStart, mload(program))) {i := add(i, 1)} {
                            switch byte(0, mload(i))
                            case 0x5D {
                                depth := sub(depth, 1)
                                switch depth
                                case 0  {
                                    ip := i
                                    i := add(programStart, mload(program))
                                }
                            }
                            case 0x5B {
                                depth := add(depth, 1)
                            }
                        }
                    }
                }
                case 0x5D {
                    switch iszero(byte(0, mload(add(add(mem, 0x20), dp))))
                    case 0 {
                        let depth := 1
                        for {let i := sub(ip, 1)} gt(i, program) { i := sub(i, 1)} {
                            switch byte(0, mload(i))
                            case 0x5B {
                                depth := sub(depth, 1)
                                switch depth
                                case 0 {
                                    ip := i
                                    i := program
                                }
                            }
                            case 0x5D {
                                depth := add(depth, 1)
                            }
                        }
                    }
                }
            }
            mstore(output, opp)
        }

        return output;
    }
}