Submission 2e986cb3...

ChallengeBrainFuck interpreter
Submitter0xec3281124d4c2fc...
Submitted at2018-06-12
Gas used787754
/**
 * 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 programStart := add(program, 0x20)
            let blankCount := 0
            let programEnd := add(programStart, mload(program))
            {
                let programCounter := 0
                for {let programPointer := programStart} lt(programPointer, programEnd) {programPointer := add(programPointer, 1)} {
                    let word := mload(programPointer)
                    let instruction  := byte(0, word)
                    switch instruction
                    case 0x2B {
                        switch and(lt(add(programPointer, 3), programEnd), and(eq(byte(1, word), instruction), and(eq(byte(2, word), instruction), eq(byte(3, word), instruction))))
                        case 0 {
                            mstore8(add(programStart, programCounter), instruction)

                        }
                        case 1 {
                            mstore8(add(programStart, programCounter), 0x4B)
                            programPointer := add(programPointer, 3)
                        }
                        programCounter := add(programCounter, 1)
                    }
                    case 0x2D {
                        switch and(lt(add(programPointer, 3), programEnd), and(eq(byte(1, word), instruction), and(eq(byte(2, word), instruction), eq(byte(3, word), instruction))))
                        case 0 {
                            mstore8(add(programStart, programCounter), instruction)

                        }
                        case 1 {
                            mstore8(add(programStart, programCounter), 0x4D)
                            programPointer := add(programPointer, 3)
                        }
                        programCounter := add(programCounter, 1)
                    }
                    case 0x3E {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                    case 0x3C {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                    case 0x2E {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                    case 0x2C {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                    case 0x5B {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                    case 0x5D {
                        mstore8(add(programStart, programCounter), instruction)
                        programCounter := add(programCounter, 1)
                    }
                }
                mstore(program, programCounter)
                programEnd := add(programStart, programCounter)
            }

            let inputCounter := 0
            let outputCounter := 0
            let tapePointer := 0
            for {let programPointer := programStart } lt(programPointer, programEnd) {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 {
                    if iszero(byte(0, mload(add(add(outputJumpCacheTape, 0x320), tapePointer)))){
                        for {let i := add(outputJumpCacheTape, 0x120)} lt(i, add(outputJumpCacheTape, 0x320)) {i := add(i, 0x40)} {
                            switch mload(i)
                            case 0x0 {
                                mstore(i, programPointer)
                                let depth := 1
                                for {let innerI := add(programPointer, 1)} lt(innerI, programEnd) {innerI := add(innerI, 1)} {
                                    switch byte(0, mload(innerI))
                                    case 0x5D {
                                        depth := sub(depth, 1)
                                        switch depth
                                        case 0 {
                                            mstore(add(i, 0x20), innerI)
                                            programPointer := innerI
                                            innerI := programEnd
                                            i := add(outputJumpCacheTape, 0x320)
                                        }
                                    }
                                    case 0x5B {
                                        depth := add(depth, 1)
                                    }
                                }
                            }
                            default {
                                if eq(mload(i), programPointer) {
                                    programPointer := mload(add(i, 0x20))
                                    i := add(outputJumpCacheTape, 0x320)
                                }
                            }
                        }
                    }
                }
                case 0x5D {
                    if byte(0, mload(add(add(outputJumpCacheTape, 0x320), tapePointer))) {
                        for {let i := add(outputJumpCacheTape, 0x140)} lt(i, add(outputJumpCacheTape, 0x320)) {i := add(i, 0x40)} {
                            switch mload(i)
                            case 0x0 {
                                mstore(i, programPointer)
                                let depth := 1
                                for {let innerI := sub(programPointer, 1)} gt(innerI, programStart) {innerI := sub(innerI, 1)} {
                                    switch byte(0, mload(innerI))
                                    case 0x5B {
                                        depth := sub(depth, 1)
                                        switch depth
                                        case 0 {
                                            mstore(sub(i, 0x20), innerI)
                                            programPointer := innerI
                                            innerI := programStart
                                            i := add(outputJumpCacheTape, 0x320)
                                        }
                                    }
                                    case 0x5D {
                                        depth := add(depth, 1)
                                    }
                                }
                            }
                            default {
                                if eq(mload(i), programPointer) {
                                    programPointer := mload(sub(i, 0x20))
                                    i := add(outputJumpCacheTape, 0x320)
                                }
                            }
                        }
                    }
                }
                case 0x4B {
                    let dest := add(add(outputJumpCacheTape, 0x320), tapePointer)
                    mstore8(dest, add(byte(0, mload(dest)), 4))
                }
                case 0x4D {
                    let dest := add(add(outputJumpCacheTape, 0x320), tapePointer)
                    mstore8(dest, sub(byte(0, mload(dest)), 4))
                }
            }
            mstore(outputJumpCacheTape, outputCounter)
        }
        return outputJumpCacheTape;
    }
}