Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Comment on

( #3333=superdoc: 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));

In reply to Static analyzer for brainfuck code. by ohcamacj

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others perusing the Monastery: (15)
    As of 2014-07-23 16:10 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (146 votes), past polls