perl brainf*ck, 7 kb

#!/usr/bin/perl -w
use strict;

sub escape_newline {
    my $val = shift();
    $val =~ s/\n/\\n/g;
    return $val;
}

my ($bf_code, $bf_input) = split(/!/, join("", <>), 2);
printf("Bf code is:\n%s\nEND, length %d bytes.\n", $bf_code, length($bf_code));

printf("Bf input is:\n%s\nEND, length %d bytes.\n", $bf_input, length($bf_input));


#While studying some existing brainfuck code, I've observed a few
#common idioms, that look very easy to speed up by using static analysis.
#Basically, any loop that contains balanced numbers of < and > characters,
#could probably be statically analyzed.

#Storage.
#  ( [offset, net_incr], [offset, net_incr] )
my $bf_output = "";

my @s = ();
my $p = 0;
my $in_idx = 0;

my @j_table = ();
my @add_table = ();
my @s_table = ();
my @s_table_baselen = ();

#Static anaylze time.

my $num_add_unique = 0;
my $num_add_all = 0;

my $num_s_loops = 0;
my $num_s_alllen = 0;
for(my $i = 0; $i < length($bf_code); $i++){
    my $firstchar = substr($bf_code, $i, 1);
    if($firstchar eq "+" || $firstchar eq "-"){
        $num_add_unique++;
        my $runlen = 1;
        for(my $j = $i + 1; $j < length($bf_code) && substr($bf_code, $j, 1) eq $firstchar; $j++){
            $runlen = $j - $i + 1;
        }
        $add_table[$i] = $runlen;
        $num_add_all += $runlen;

        #overwrite with whitespace for clarity.
        substr($bf_code, $i + 1, $runlen - 1, " " x ($runlen - 1));

        $i += $runlen - 1; #skip forward to next.
    }

    if($firstchar eq "["){
        my $next_open = index($bf_code, "[", $i + 1);
        my $next_close = index($bf_code, "]", $i + 1);

        #open before close, not simple.
        #no open at all, simple.
        if( $next_open == -1 || $next_close < $next_open){

            my $loop_inner = substr($bf_code, $i + 1, $next_close - $i - 1);
            my $ok = $loop_inner =~ /^[<>+\-]*$/;
            my $num_left = 0;
            my $num_right = 0;
            $loop_inner =~ s/(<)/$num_left++; $1/eg;
            $loop_inner =~ s/(>)/$num_right++; $1/eg;


            if($num_left == $num_right && $loop_inner =~ /^[<>+\s\-]*$/){
                # a simple loop
                $num_s_loops++;
                $num_s_alllen += length($loop_inner) + 2;
                $s_table_baselen[$i] = length($loop_inner) + 2;

                printf("Found simple loop [%s]\n", escape_newline($loop_inner));
                my %unique_offsets = ();
                my $off_p = 0;
                for(my $k = 0; $k < length($loop_inner); $k++){
                    my $li_char = substr($loop_inner, $k, 1);
                    if($li_char eq "<"){
                        $off_p--;
                    }
                    if($li_char eq ">"){
                        $off_p++;
                    }
                    if($li_char eq "+"){
                        $unique_offsets{$off_p}++;
                    }
                    if($li_char eq "-"){
                        $unique_offsets{$off_p}--;
                    }
                }
                my @s_loop_packed = ();
                print("  Result is (");
                for(sort({$a <=> $b} keys(%unique_offsets))){
                    next if $_ == 0;
                    push(@s_loop_packed, [$_, $unique_offsets{$_} ]);
                    printf("[%d,%d], ", $_, $unique_offsets{$_});
                }
                print(")\n");
                if($unique_offsets{0} == -1){
                    #everything's ok.
                    $s_table[$i] = [@s_loop_packed];
                    substr($bf_code, $i, 1, "S"); #to indicate start.
                    substr($bf_code, $next_close, 1, "s"); #erase closing bracket.
                    #overwrite with whitespace for clarity.
                    substr($bf_code, $i + 1, length($loop_inner), " " x length($loop_inner));

                }else{
                    print("  Warning: exotic loop [$loop_inner].\n");
                    #roll back changes made so far.
                    $num_s_loops--;
                    $num_s_alllen -= length($loop_inner) + 2;
                    $s_table_baselen[$i] = undef;
                }

            }


        }
    }
}

printf("Found %d runs of +/-, totalling %d +/-, average length %.2f\n",
    $num_add_unique, $num_add_all, $num_add_all / $num_add_unique);

printf("Found %d simple loops, totalling %d bytes, average length %.2f\n",
    $num_s_loops, $num_s_alllen, $num_s_alllen / $num_s_loops);

#Now print it out.
print("Table (+/-) is:\n");
for(my $idx = 0; $idx < $#add_table + 1; $idx++){
    if($idx % 30 == 0){
        print("  ");
    }
    print(" " . (defined($add_table[$idx]) ? $add_table[$idx] : " "));
    if($idx % 30 == 29){
        print("\n");
    }
}
print("\n\n");

print("Table (s_loop_baselen) is:\n");
for(my $idx = 0; $idx < $#s_table_baselen + 1; $idx++){
    if($idx % 30 == 0){
        print("  ");
    }
    print(" " . (defined($s_table_baselen[$idx]) ? $s_table_baselen[$idx] : " "));
    if($idx % 30 == 29){
        print("\n");
    }
}
print("\n\n");

printf("After transformation, bf code is:\n%s\nEND, length %d bytes.\n", $bf_code, length($bf_code));

for (my $i = 0; $i < length($bf_code); $i++){
    my $command = substr($bf_code, $i, 1);
    if(! defined($s[$p])){
        $s[$p] = 0;
        print("Lengthening tape forwards by one.\n") if 0;
    }
    if($command eq "<"){
        $p--;
    }
    if($command eq ">"){
        $p++;
    }
    if($command eq "+"){
        $s[$p] += $add_table[$i]; $s[$p] %= 256;
        $i += $add_table[$i] - 1;
    }
    if($command eq "-"){
        $s[$p] -= $add_table[$i]; $s[$p] %= 256;
        $i += $add_table[$i] - 1;
    }
    if($command eq "["){
        if($s[$p] == 0){
            #jump forward.
            my $orig_i = $i;
            if(defined($j_table[$i])){
                $i = $j_table[$i];
            }else{
                my $d = 1;
                while($d > 0 && $i < length($bf_code)){
                    $i++;
                    $d++ if substr($bf_code, $i, 1) eq "[";
                    $d-- if substr($bf_code, $i, 1) eq "]";
                }
                $j_table[$orig_i] = $i;
            }
            printf("Jumping forward by %d bytes.\n", $i - $orig_i) if 0;
        }
    }
    if($command eq "]"){
        if($s[$p] != 0){
            #jump backwards.
            my $orig_i = $i;
            if(defined($j_table[$i])){
                $i = $j_table[$i];
            }else{
                my $d = 1;
                while($d > 0 && $i > 0){
                    $i--;
                    $d++ if substr($bf_code, $i, 1) eq "]";
                    $d-- if substr($bf_code, $i, 1) eq "[";
                }
                $j_table[$orig_i] = $i;
            }
            printf("Jumping backwards by %d bytes.\n", $orig_i - $i) if 0;
        }
    }
    if($command eq ","){
        print("Loading 1 byte of input.\n") if 0;
        if($in_idx >  length($bf_input)){
            last;
        }
        $s[$p] = ord(substr($bf_input, $in_idx++, 1));
    }
    if($command eq "."){
        print("Outputing a single byte.\n") if 0;
        $bf_output .= chr($s[$p]);
    }
    if($command eq "S"){
        my $incrval = $s[$p];
        my @to_incr = @{$s_table[$i]};
        for my $spec (@to_incr){
            (my $offset, my $incrmul) = @$spec;
            $s[$p + $offset] += $incrmul * $incrval;
            $s[$p + $offset] %= 256;
        }

        $s[$p] = 0;
        $i += $s_table_baselen[$i] - 1;
    }
    if($p == -1){
        print("Lengthing tape backwards by one.\n") if 0;
        $p = 0;
        unshift(@s, 0);
    }
}


printf("Bf code loaded %d bytes of input.\n", $in_idx);
printf("Output of bf code was:\n%s\nEND, length %d bytes.\n", $bf_output, length($bf_output));