Submission a705b288...
/**
* 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 {
// event E(string);
// event B(byte);
// event P(byte,byte);
event E(uint256);
/**
* @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) {
// Optimize
//emit E(string(program));
(bool hasOutput, uint16 nBranches) = optimize(program);
if(!hasOutput) return;
//emit E(string(program));
// Run
uint8[] memory data = new uint8[](1024); // store output at end of data
uint[] memory programBegin = new uint[](nBranches); // max stack depth
return runProgram(
program,
input,
data,
0,
0,
0,
0,
program.length,
programBegin
);
}
function optimize(bytes program) internal pure returns (bool hasOutput, uint16 nBranches) {
byte s;
byte last;
uint8 count; // Q: What happens if count > 255?
uint maxProgramLength = program.length;
int8 lastIsValid = -1;
//bool stateChanged;
for(uint pPtr = 0; pPtr < maxProgramLength; pPtr++) {
s=program[pPtr];
int8 isValid;
bool same = false;
if(s == '[') {
nBranches++;
isValid = 1;
same = (s == last);
} else if(s == ']' || s == '>' || s == '<') {
isValid = 1;
same = (s == last);
} else if(s == '+' || s == '-' || s == ',') {
//stateChanged = true;
isValid = 1;
same = (s == last);
} else if(s == '.') {
hasOutput = true;
isValid = 1;
same = (s == last);
} else if(uint8(s) <= 0x29){
// isValid == false and it's in our "repeate instruction" range
// So, we'll switch it to be *
program[pPtr] = s = '*';
// loses efficiency if(lastIsValid == 0) same = true;
} else {
// loses efficiency if(lastIsValid == 0) same = true;
}
if(same && count < 0x29) { // 0x29 is last char before our special characters start
count++;
} else if(count == 1) {
count = 0;
} else if(count > 1) {
program[pPtr-count-1] = byte(count+1);
count = 0;
}
last = s;
lastIsValid = isValid;
}
if(count > 1 && count < 0x29) {
program[pPtr-count] = byte(count);
}
}
function runProgram(
bytes program,
bytes input,
uint8[] data,
uint oPtr,
uint pPtr,
uint iPtr,
uint dPtr,
uint maxProgramLength,
uint[] memory programBegin
)
internal
pure
returns (bytes memory sanitizedOutput)
{
bytes memory output = new bytes(1024);
uint programBeginIndex;
byte s = program[pPtr];
byte last = byte(uint8(s)+1); // just need it to not equal s
uint8 n = 1;
while(true) {
if(s == '[') {
if(data[dPtr] == 0) {
// Just skip it
n = 1;
while(n > 0) {
s = program[++pPtr];
if(s == '[') n++;
else if(s == ']') n--;
}
pPtr++;
} else {
while(n-- > 0) programBegin[programBeginIndex++] = ++pPtr;
}
} else if(s == ']') {
if(data[dPtr] == 0) {
programBeginIndex -= n;
pPtr += n;
} else {
pPtr = programBegin[programBeginIndex-n];
}
} else if(s == '>') {
dPtr += n;
pPtr += n;
} else if(s == '<') {
dPtr -= n;
pPtr += n;
} else if(s == '+') {
data[dPtr] += n;
pPtr += n;
} else if(s == '-') {
data[dPtr] -= n;
pPtr += n;
} else if(s == ',') {
pPtr += n;
data[dPtr] = uint8(input[(iPtr+=(n-1))]);
iPtr++;
} else if(s == '.') {
pPtr += n;
last = byte(data[dPtr]); // recycle last
while(n-- > 0) output[oPtr++] = last;
} else if(uint8(s) <= 0x29){
// Repeat next instruction
n = uint8(s);
s = program[pPtr+1];
continue;
} else {
pPtr += n;
}
if(pPtr == maxProgramLength) break;
s = program[pPtr];
n = 1;
}
sanitizedOutput = new bytes(oPtr);
dPtr = 0; // recycle dPtr
while(dPtr < oPtr) {
sanitizedOutput[dPtr++] = output[dPtr];
}
return sanitizedOutput;
}
}