Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Static analyzer for brainfuck code.

by ohcamacj (Sexton)
on Jan 13, 2014 at 05:23 UTC ( #1070379=CUFP: print w/ replies, xml ) Need Help??

I recently spent a while staring at some brainfuck code (in particular, the rot13 decoder on the oldest http://golf.shinh.org brainfuck challenge), trying to understand how it worked.

I didn't succeed, but ended up writing a static analyzer to eliminate simple loops like [<+>-] which occur fairly often.

The static analyzer,
#!/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($b +f_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 analys +is. #Basically, any loop that contains balanced numbers of < and > charact +ers, #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($loo +p_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 clos +ing 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[$i +dx] : " ")); 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) i +f 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_outp +ut, length($bf_output));

Comment on Static analyzer for brainfuck code.
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://1070379]
Approved by davido
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (10)
As of 2014-12-18 05:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (42 votes), past polls