Submission d3ff70db...
/**
* 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 {
// event E(string);
// event B(byte);
// event P(byte,byte);
event E(uint[]);
/**
* @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)
{
// Analyze
uint programLength = program.length;
(
bool hasOutput,
uint[] memory jumpTable
) = analyze(program, programLength);
if(!hasOutput) return;
//return program;
// Run
uint[] memory data = new uint[](2048); // store output at end of data
programLength = runProgram(
program,
input,
data,
jumpTable,
0,
1024,
0,
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
0,
programLength
);
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 programLength) internal pure returns (bool hasOutput, uint[] memory jumpTable) {
// 1. Check for output
// 2. Count unique instructions
uint16 nBranches;
//uint instructions;
for(uint i = 0; i != programLength; ++i) {
b = program[i];
if(b == '.') hasOutput = true;
else if(b == '[') nBranches++;
//else if(isValid(b)) instructions++;
}
if(!hasOutput) return (hasOutput, jumpTable);
//sanitizedProgram = new uint[](2 * instructions);
///uint pPtr;
// 2. Analyze program.
// - Replace bad characters with `*`. This helps with the next step.
// - Re-encode N consecutive instances of the same character (c) with [N][c]
// - Record branch beginnings and endings
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;
byte b;
byte last;
uint count;
uint16 balance;
jumpTable = new uint[](programLength);
uint[] memory branchBalances = new uint[](nBranches);
uint branchEndI;
nBranches = 0;
for(i = 0; i != programLength; ++i) {
b = program[i];
if(b == '[') {
branchBalances[balance++] = i;
} else if(b == ']') {
uint jumpLocation = branchBalances[--balance];
jumpTable[jumpLocation] = i+1; // next instruction after ]
jumpTable[i] = jumpLocation+1;
} else if(!lookup[uint8(b)]) {
b = (program[i] = '*');
}
if(b == last && count < 0x29) {
count++;
} else if(count > 1) {
program[i-count] = byte(count);
count = 1;
}
last = b;
}
}
function isInValid(byte b) internal pure returns (bool) {
// Ordered by likely precedence, based on test data.
return b & 8 != 8 && b != '>' && // 58 instances
b != ',' && // 53 instances
b != '+' && // 48 instances
b != '-' && // 27 instances
b != '.' && // 23 instances
b != '<';// || // 14 instances
// b == '[' || // 7 instances
// b == ']'; // 7 instances
}
function runProgram(
bytes memory program,
bytes memory input,
uint[] memory data,
uint[] memory jumpTable,
uint16 oPtr,
uint16 dPtr,
uint16 jPtr,
uint iPtr,
uint pPtr,
uint programLength
)
internal
pure
returns (uint16)
{
uint jumpTableLength = jumpTable.length;
uint8 dCache;
while(pPtr != programLength) {
byte cmd = program[pPtr];
uint8 n;
if(cmd < 0x2A) {
n = uint8(cmd);
cmd = program[pPtr+1];
pPtr += n;
} else {
pPtr++;
n = 1;
}
// Interpret
if(cmd == ']') {
if(dCache != 0) pPtr = jumpTable[pPtr-n];
} else if(cmd == '+') {
dCache += n;
} else if(cmd == '-') {
dCache -= 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 = jumpTable[pPtr-n];
}
}
return oPtr;
}
}