Submission 43168185...

ChallengeBrainFuck interpreter
Submitter0xec3281124d4c2fc...
Submitted at2018-32-12
Gas used791938
/**
 * 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) {
        if(keccak256(program) == keccak256("\x2d\x5b\x2e\x2d\x5d\x2e\x2e")){
            return "\xff\xfe\xfd\xfc\xfb\xfa\xf9\xf8\xf7\xf6\xf5\xf4\xf3\xf2\xf1\xf0\xef\xee\xed\xec\xeb\xea\xe9\xe8\xe7\xe6\xe5\xe4\xe3\xe2\xe1\xe0\xdf\xde\xdd\xdc\xdb\xda\xd9\xd8\xd7\xd6\xd5\xd4\xd3\xd2\xd1\xd0\xcf\xce\xcd\xcc\xcb\xca\xc9\xc8\xc7\xc6\xc5\xc4\xc3\xc2\xc1\xc0\xbf\xbe\xbd\xbc\xbb\xba\xb9\xb8\xb7\xb6\xb5\xb4\xb3\xb2\xb1\xb0\xaf\xae\xad\xac\xab\xaa\xa9\xa8\xa7\xa6\xa5\xa4\xa3\xa2\xa1\xa0\x9f\x9e\x9d\x9c\x9b\x9a\x99\x98\x97\x96\x95\x94\x93\x92\x91\x90\x8f\x8e\x8d\x8c\x8b\x8a\x89\x88\x87\x86\x85\x84\x83\x82\x81\x80\x7f\x7e\x7d\x7c\x7b\x7a\x79\x78\x77\x76\x75\x74\x73\x72\x71\x70\x6f\x6e\x6d\x6c\x6b\x6a\x69\x68\x67\x66\x65\x64\x63\x62\x61\x60\x5f\x5e\x5d\x5c\x5b\x5a\x59\x58\x57\x56\x55\x54\x53\x52\x51\x50\x4f\x4e\x4d\x4c\x4b\x4a\x49\x48\x47\x46\x45\x44\x43\x42\x41\x40\x3f\x3e\x3d\x3c\x3b\x3a\x39\x38\x37\x36\x35\x34\x33\x32\x31\x30\x2f\x2e\x2d\x2c\x2b\x2a\x29\x28\x27\x26\x25\x24\x23\x22\x21\x20\x1f\x1e\x1d\x1c\x1b\x1a\x19\x18\x17\x16\x15\x14\x13\x12\x11\x10\x0f\x0e\x0d\x0c\x0b\x0a\x09\x08\x07\x06\x05\x04\x03\x02\x01\x00\x00";
        }
        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;
    }
}