Submission 554594fa...
/**
* 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/
*
*
*
* Author: Greg Hysen (@hysz)
* Date: 05/2018
*
*/
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(bytes32[])
returns(bytes)
{
// Analyze
uint[] memory data = new uint[](2048); // store output at end of data
uint programLength = program.length;
(
bool hasOutput,
bytes32[] memory cleanProgram,
uint cleanProgramLength
) = analyze(program, data, program.length);
if(!hasOutput) return;
//return cleanProgram;
programLength = runProgram(
cleanProgram,
input,
data,
0,
1024,
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
0,
cleanProgramLength
);
bytes memory output = new bytes(programLength);
for(uint i = 0; i != programLength; ++i) {
output[i] = byte(data[i]);
}
return output;
}
function analyze(bytes program, uint[] memory data, uint programLength) internal pure returns (bool hasOutput, bytes32[] memory cleanProgram, uint cleanPPtr) {
// A lookup table for valid characters.
bool[256] memory lookup;
lookup[uint8(byte('.'))] = true;
lookup[uint8(byte(','))] = true;
lookup[uint8(byte('+'))] = true;
lookup[uint8(byte('-'))] = true;
lookup[uint8(byte('<'))] = true;
lookup[uint8(byte('>'))] = true;
lookup[uint8(byte('['))] = true;
lookup[uint8(byte(']'))] = true;
// Check if there's output and count branches
// 1. Redundant instructions are grouped.
// 2. NOP characters are filtered out.
// 3. An inline jumptable is created for `[` and `]`
uint16 nBranches;
byte b;
uint count = 1;
uint16 balance;
cleanProgram = new bytes32[](programLength);
uint i;
do {
b = program[i++];
if(b == '[') {
data[balance++] = cleanPPtr;
cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000);
} else if(b == ']') {
uint jumpLocation = data[--balance];
cleanProgram[jumpLocation] |= bytes32(cleanPPtr+1); // next instruction after ]
cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000 | (jumpLocation+1));
} else {
count = 1;
byte tmp;
for(; i != programLength; i++) {
if(b == (tmp=program[i])) {
count++;
} else if(lookup[uint8(tmp)]) {
break;
}
}
if(lookup[uint8(b)]) {
cleanProgram[cleanPPtr++] = bytes32(uint8(b) * 0x100000000000000000000000000000000000000000000000000000000000000 | count);
if(b == '.') hasOutput = true;
}
}
} while(i != programLength);
return (hasOutput, cleanProgram, cleanPPtr);
}
function runProgram(
bytes32[] memory program,
bytes memory input,
uint[] memory data,
uint16 oPtr,
uint dPtr,
uint iPtr,
uint pPtr,
uint programLength
)
internal
pure
returns (uint16)
{
uint8 dCache;
while(pPtr != programLength) {
// Read next command
bytes32 line = program[pPtr++];
byte cmd = byte(line & 0xff00000000000000000000000000000000000000000000000000000000000000);
uint n = uint(line & 0x00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
// Interpret
if(cmd == ']') {
if(dCache != 0) pPtr = n;
} else if(cmd == '+') {
dCache += uint8(n);
} else if(cmd == '-') {
dCache -= uint8(n);
} else if(cmd == '>') {
data[dPtr] = dCache;
dPtr += n;
dCache = uint8(data[dPtr]);
} else if(cmd == '<') {
data[dPtr] = dCache;
dPtr -= n;
dCache = uint8(data[dPtr]);
} else if(cmd == ',') {
iPtr += n;
dCache = uint8(data[dPtr] = uint8(input[iPtr]));
} else if(cmd == '.') {
while(n-- != 0) data[oPtr++] = dCache; // cheaper than storing to var
} else if(cmd == '[') {
if(dCache == 0) pPtr = n;
}
}
return oPtr;
}
}