Submission ffcb1fa7...

ChallengeBrainFuck interpreter
Submittersggc.yuetloo.eth
Submitted at2018-33-26
Gas used5678554
/**
 * 
 * Author: Yuet Loo Wong
 *
 * This is a modified version of the original contract from
 *   https://github.com/arachnid/sggc.git
 *
 * 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 {
   struct Map {
     uint      cachedIndex;
     uint      count;
     Bracket[] list;
   }

   struct Bracket {
      uint start;
      uint end;
   }

    /**
     * @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) {
        uint ipp = 0;
        uint opp = 0;
        uint dp = 0;
        bytes memory mem = new bytes(1024);
        bytes memory output = new bytes(1024);
        Map memory map = Map(0, 0, new Bracket[](program.length/2));

        for(uint ip = 0; ip < program.length; ip++) {
            byte instruction = program[ip];
            if(instruction == '+') {
                mem[dp] = byte(uint(mem[dp]) + 1);
            } else if(instruction == '-') {
                mem[dp] = byte(uint(mem[dp]) - 1);
            } else if(instruction == '>') {
                dp++;
            } else if(instruction == '<') {
                dp--;
            } else if(instruction == '.') {
                output[opp++] = mem[dp];
            } else if(instruction == ',') {
                mem[dp] = input[ipp++];
            } else if(instruction == '[') {
                if(mem[dp] == 0) {
                    ip = lookup(program, ip, map);
                }
            } else if(instruction == ']') {
                if(mem[dp] != 0) {
                    ip = lookup(program, ip, map);
                }
            }
        }

        bytes memory ret = new bytes(opp);
        for(uint i = 0; i < opp; i++) {
            ret[i] = output[i];
        }
        return ret;
    }

    function lookup(bytes program, uint index, Map map) internal pure returns (uint retIndex)
{
    if( map.count == 0 ) loadMap(map, program);

    Bracket memory cached = map.list[map.cachedIndex];
    if( cached.start != index && cached.end != index )
    {
       for( uint i = 0; i < map.count; i++ )
       {
          if( map.list[i].start == index || map.list[i].end == index )
          {
             cached = map.list[i];
             map.cachedIndex = i;
             break;
          }
       }
    }

    uint ret = 0;
    byte instruction = program[index];
    if(instruction == '[') { 
       ret = cached.end;
    } else if (instruction == ']') {
       ret = cached.start;
    }
    return ret;
}

function loadMap(Map map, bytes program) internal pure {

    uint endIndex = 0;
    for(uint i = 0; i < program.length; i++ )
    {
        byte instruction = program[i];
        if( instruction == '[' ) {
           map.list[map.count] = Bracket(i, 0);
           endIndex = map.count;
           map.count++;
        } else if( instruction == ']') {
           for(uint j=endIndex; j >= 0; j--){
              if(map.list[j].end == 0)
              {
                 map.list[j].end = i;
                 endIndex = j-1;
                 break;
              }
           } 
        }
    }
}

}