Submission 475de349...

ChallengeBrainFuck interpreter
Submitter0x888888417655103...
Submitted at2018-53-30
Gas used1850940
pragma solidity 0.4.24;

contract BrainFuck {

    function execute(
        bytes program,
        bytes input
    ) public pure returns(bytes output) {
        uint progLen = remove_invalid(program);
        uint8[] memory ram = new uint8[](1024);
        uint outIdx = brainfuck(program, input, progLen, ram);
        output = new bytes(outIdx-progLen);
        for (uint i = 0; i < output.length; i++) {
            output[i] = byte(ram[progLen+i]);
        }
    }

    function remove_invalid(
        bytes program
    ) private pure returns(uint progLen) {
        assembly {
            let pgLen := mload(program)
            let pgBegin := add(program, 0x01)
            let pgEnd := add(pgBegin, pgLen)
            let pgEndNew := add(program, 0x20)
            for { let idx := pgBegin }
                lt(idx, pgEnd)
                { idx := add(idx, 0x01) } {
                let v := and(mload(idx), 0xff)
                if and(0x280000005000780000000000, exp(0x02, v)) {
                    mstore8(pgEndNew, v)
                    pgEndNew := add(pgEndNew, 0x01)
                }
            }
            progLen := sub(sub(pgEndNew, pgBegin), 0x1f)
        }
    }

    function brainfuck(
        bytes program,
        bytes input,
        uint progLen,
        uint8[] ram
    ) private pure returns(uint outIdx) {
        outIdx = progLen;
        uint inIdx = 0;
        uint progIdx = 0;
        byte token;
        uint[] memory stack = new uint[] (16);
        uint stackIdx = 0;
        uint ramIdx = 0;
        while (progIdx < progLen) {
            token = program[progIdx++];
            if (token < 0x30) {
                if (token < 0x2d) {
                    if (token == 0x2b) {
                        ram[ramIdx] += 1;
                        continue;
                    }
                    ram[ramIdx] = uint8(input[inIdx++]);
                    continue;
                }
                if (token == 0x2d) {
                    ram[ramIdx] -= 1;
                    continue;
                }
                ram[outIdx++] = ram[ramIdx];
                continue;
            }
            if (token < 0x40) {
                if (token == 0x3c) {
                    ramIdx -= 1;
                    continue;
                }
                ramIdx += 1;
                continue;
            }
            if (token == 0x5b) {
                if (ram[ramIdx] == 0) {
                    while (program[progIdx++] != 0x5d) {}
                    continue;
                }
                stack[stackIdx++] = progIdx - 1;
                continue;
            }
            if (ram[ramIdx] == 0) {
                stackIdx -= 1;
                continue;
            }
            progIdx = stack[stackIdx-1] + 1;
        }
    }
}