brainfucked.py

#!/usr/bin/python

"""
brainfucked.py a simple (and hopefully easy to understand) Brainfuck interrupter
written in Python.

Official page:   http://www.muppetlabs.com/~breadbox/bf/
Wikipedia:       http://en.wikipedia.org/wiki/Brainfuck
Program archive: http://esoteric.sange.fi/brainfuck/bf-source/prog/

Only one program confirmed not working:
 * Ben Olmstead 99 Bottles of Beer.  Appears to be caused by non-wrapping 8bit
   cells (after 91 bottles, cell becomes -1 and then enters infinte loop)


Copyright (C) 2007  Matthew Davey  <buzzard AT project DASH 2501 DOT net>

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
"""


from time import time
import sys
import re
import os


"""
Find matching '[' and ']' brackets.  Use a FIFO stack to keep brackets matched,
and a dictionary to map both left->right and right->left.
"""
def find_matching_brackets(program_data):

    stack = []
    brackets = {}

    program_length = len(program_data)
    program_pointer = 0

    while program_pointer < program_length:

        if program_data[program_pointer] == '[':
            stack.append(program_pointer)

        elif program_data[program_pointer] == ']':
            if len(stack) == 0:
                raise Exception("Unmatched brackets, extra closing ']'")

            # Pull the location of the last open bracket from the stack
            val = stack.pop()

            # Creating a mapping left->right as well as right->left
            brackets[val] = program_pointer;
            brackets[program_pointer] = val;

        program_pointer += 1

    if len(stack) > 0:
        raise Exception("Unmatched brackets, too many opening '['")

    return brackets



"""
Runs a Brainfuck program, passed as a string.  All comments are striped out at
start.

 * use_stdout flag indicates is we should print after each '.'
 * strict_eight_bit_cell indicates if we should enforce each cells range to be 0
   to 255 inclusive with no wrapping

Function returns outputted characters as a string (even if use_stdout is True)
"""
def run_program(program, use_stdout = False, strict_eight_bit_cell = False):

    # Remove all non-instructions
    program = re.findall("[[\]<>+-.,]", program)

    # Contains all printed characters
    output = ''

    # Points to the location of the current instruction
    instruction_pointer = 0
    program_length = len(program)

    # Memory or Tape.  Initialised to a single cell with the value 0
    tape = [0]

    # Pointer to the 'head' running over the tape
    tape_pointer = 0

    # Returns a dictionary of matching left->right and right->left brackets
    brackets = find_matching_brackets(program)

    # Until end of the program
    while instruction_pointer < program_length:

        current_operator = program[instruction_pointer]


        # Move to next cell
        if current_operator == '>':

            tape_pointer += 1

            # We are going passed the end of the tape
            if tape_pointer > len(tape)-1:
                tape.append(0)


        # Move to previous cell
        elif current_operator == '<':

            # Test for leaving the start of the tape
            if tape_pointer <= 0:
                raise Exception("Tried to move left 1 cell at position 0")

            tape_pointer -= 1


        # Decrement current cell
        elif current_operator == '+':
            tape[tape_pointer] += 1

            if strict_eight_bit_cell and tape[tape_pointer] > 0xff:
                raise Exception("Tried to increment past 255")


        # Increment current cell
        elif current_operator == '-':
            tape[tape_pointer] -= 1

            if strict_eight_bit_cell and tape[tape_pointer] < 0:
                raise Exception("Tried to decrement below 0")


        # Open bracket  
        elif current_operator == '[':
            if tape[tape_pointer] == 0:
                # We know the left bracket, so jump to the right one
                instruction_pointer = brackets[instruction_pointer]


        # Close bracket
        elif current_operator == ']':
            if tape[tape_pointer] != 0:
                # We know the right bracket, so jump to the left one
                instruction_pointer = brackets[instruction_pointer]


        # Read a single character, set current cell to '0' on EOF
        elif current_operator == ',':
            char = sys.stdin.read(1)

            if char == '':
                tape[tape_pointer] = 0
            else:
                # Remember to turn character 'A' into it's ASCII number
                tape[tape_pointer] = ord(char)


        # Record outputted character, and if use_stdout is True, output the
        # character as well (to stdout)
        elif current_operator == '.':
            output += chr(tape[tape_pointer])

            if use_stdout:
                sys.stdout.write(chr(tape[tape_pointer]))


        instruction_pointer += 1

    return output



if __name__ == '__main__':

    usage = "Usage: %s <filename> [enable_timer: True | False]" % (sys.argv[0],)
    timer = False

    if len(sys.argv) not in [2,3] or sys.argv[1] == 'help':
        print usage
        sys.exit(1)


    if not os.path.exists(sys.argv[1]):
        print usage
        print "File not found"
        sys.exit(1)


    try:
        program = open(sys.argv[1]).read()
    except Exception, e:
        print usage
        print "Unable to open file: %s" % (e.__str__(),)
        sys.exit(1)


    if len(sys.argv) == 3:
        if sys.argv[2] not in ['True', 'False']:
            print usage
            print "Second argument must be 'True' or 'False'"
            sys.exit(1)

        if sys.argv[2] == 'True':
            timer = True


    if timer:
        start_time = time()


    run_program(program, use_stdout = True, strict_eight_bit_cell = False)


    if timer:
        print
        print "Elapsed time: %0.2f" % (time() - start_time,)