Brainf*ck rot13 decoder comprehension help
-
Hi,
The oldest brainf*ck challenge on http://golf.shinh.org/, has 3 test programs.
Hello world.
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]
<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.Decode rot13.
+[,+[-[>+>+<<-]>[<+>-]+>>++++++++[<-------->-]<-[<[-]>>>+[<+<+>>-]<[>+<-]<[<++>
>>+[<+<->>-]<[>+<-]]>[<]<]>>[-]<<<[[-]<[>>+>+<<<-]>>[<<+>>-]>>++++++++[<-------
->-]<->>++++[<++++++++>-]<-<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<<<<+>>>>++++[<++++++++
>-]>-]<<-<-]>[<<<<[-]>>>>[<<<<->>>>-]]<<++++[<<++++++++>>-]<<-[>>+>+<<<-]>>[<<+
>>-]+>>+++++[<----->-]<-[<[-]>>>+[<+<->>-]<[>+<-]<[<++>>>+[<+<+>>-]<[>+<-]]>[<]
<]>>[-]<<<[[-]<<[>>+>+<<<-]>>[<<+>>-]+>------------[<[-]>>>+[<+<->>-]<[>+<-]<[<
++>>>+[<+<+>>-]<[>+<-]]>[<]<]>>[-]<<<<<------------->>[[-]+++++[<<+++++>>-]<<+>
>]<[>++++[<<++++++++>>-]<-]>]<[-]++++++++[<++++++++>-]<+>]<.[-]+>>+<]>[[-]<]<]!Ebg13-rapbqrq grkg tbrf urer.Ascii art.
>>>>+>+++>+++>>>>>+++[
>,+>++++[>++++<-]>[<<[-[->]]>[<]>-]<<[
>+>+>>+>+[<<<<]<+>>[+<]<[>]>+[[>>>]>>+[<<<<]>-]+<+>>>-[
<<+[>]>>+<<<+<+<--------[
<<-<<+[>]>+<<-<<-[
<<<+<-[>>]<-<-<<<-<----[
<<<->>>>+<-[
<<<+[>]>+<<+<-<-[
<<+<-<+[>>]<+<<<<+<-[
<<-[>]>>-<<<-<-<-[
<<<+<-[>>]<+<<<+<+<-[
<<<<+[>]<-<<-[
<<+[>]>>-<<<<-<-[
>>>>>+<-<<<+<-[
>>+<<-[
<<-<-[>]>+<<-<-<-[
<<+<+[>]<+<+<-[
>>-<-<-[
<<-[>]<+<++++[<-------->-]++<[
<<+[>]>>-<-<<<<-[
<<-<<->>>>-[
<<<<+[>]>+<<<<-[
<<+<<-[>>]<+<<<<<-[
>>>>-<<<-<-
]]]]]]]]]]]]]]]]]]]]]]>[>[[[<<<<]>+>>[>>>>>]<-]<]>>>+>>>>>>>+>]<
]<[-]<<<<<<<++<+++<+++[
[>]>>>>>>++++++++[<<++++>++++++>-]<-<<[-[<+>>.<-]]<<<<[
-[-[>+<-]>]>>>>>[.[>]]<<[<+>-]>>>[<<++[<+>--]>>-]
<<[->+<[<++>-]]<<<[<+>-]<<<<
]>>+>>>--[<+>---]<.>>[[-]<<]<
]
[Enter a number using ()-./0123456789abcdef and space, and hit return.
Daniel B Cristofani (cristofdathevanetdotcom)
http://www.hevanet.com/cristofd/brainfuck/]!0123456789Both the hello world and ascii art programs, are easy enough to evaluate; no matter how carelessly written the interpreter, they still run quickly.
But the rot13 decoder, is different. My first test (flogscript's built-in Sb command) decoded text at a rate of about 2 or 3 characters per second. After writing a perl brainf*ck interpreter, decryption speed rose to 12 characters per second (php/flogscript are slow?). Trying to understand what it was doing, noticed a lot of short loops like [-] and [<+>-] to zero cells or erase and copy values. Wrote a static analyzer for brainf*ck, enabling me to delete all loops like that without sacrificing correctness, and immediately got a 7-fold speedup in execution time, and a decryption speed of about 90 characters per second.
Faster . . . but since the original challenge had 42 kb of text to decode, and an execution time limit of about 4 seconds, 90 characters per second, is still 2 orders of magnitude too slow to solve the challenge "legitimately".
So far, no matter how long I've stared at the brainf*ck rot13 decoder, I still can't understand what it's doing or how it decrypts text. Thus, I ask, how does it work? How did a simple comparision like
if(charval >= 65 && charval <= 90){ charval += 13; if(charval > 90){ charval -= 26; }}become so many orders of magnitude slower?
if(charval >= 97 && charval <= 122){ charval += 13; if(charval > 122){charval -= 26; }}(Actually, there are 3 errors that make it difficult to solve the challenge "legitimately" even if the brainf*ck could be interpreted fast enough. The hello world bf prints "Hello World!", and the expected answer is "Hello, world!". There's a typo in the rot13 text, an extra newline about halfway down, that's not supposed to appear in the output. And, the brainf*ck rot13 decoder, has errors on [ and ~, characters which appear in the input, and decodes them as N and ^)
Static analysis brainf*ck interpreter, perl (http://ohcamacj.dyndns.org:8088/~jonathan/files-b604/try_static_analyze_v0.8_skip_exotic.pl)(http://pastebin.com/qhJ0TQLV)
Improved flogscript interpreter (http://ohcamacj.dyndns.org:8088/~jonathan/files-b604/FlogScript-jc.php.txt) (http://pastebin.com/STxPjLSt)
Flogscript bf interpreter (http://ohcamacj.dyndns.org:8088/~jonathan/files-b604/asdi-17.flog) (http://pastebin.com/0Hs2yXEX)
-
From a first look at the rot13 one, I notice it reads a character at the start (position 3) and writes it near the end (position 534 of 552). Also surprisingly the output is at a different nesting level, so it can sometimes write multiple output characters for one input.
My first conclusion from that is that the solution is generating its constants on-the-fly for each character. Probably a lot to be gained there. My brainfuck knowledge is very limited, but I think this is using more memory than you'd need.
-
@PleegWat said:
I notice it reads a character at the start (position 3) and writes it near the end
It's like an inverted schlemiel the painter?
-
@dhromed said:
@PleegWat said:
I notice it reads a character at the start (position 3) and writes it near the end
It's like an inverted schlemiel the painter?
How else would you do rot13, or any other caesar cypher?
-
@ohcamacj said:
How did a simple comparision like
if(charval >= 65 && charval <= 90){ charval += 13; if(charval > 90){ charval -= 26; }}
if(charval >= 97 && charval <= 122){ charval += 13; if(charval > 122){charval -= 26; }}become so many orders of magnitude slower?
Try doing that "simple" comparison without any binary operators, using "while" instead of "if".
-
@Faxmachinen said:
@ohcamacj said:
How did a simple comparision like
if(charval >= 65 && charval <= 90){ charval += 13; if(charval > 90){ charval -= 26; }}
if(charval >= 97 && charval <= 122){ charval += 13; if(charval > 122){charval -= 26; }}become so many orders of magnitude slower?
Try doing that "simple" comparison without any binary operators, using "while" instead of "if".
Also without using numeric constants other than +1 and -1
-
I've commented it for you. Sorry about the bad indentation, BFdev is a bit derpy in that regard.
+ [ loop until ASCII character 255 was input , read character to A from stdin +[- unless ASCII character 255 [>+>+<<-]>[<+>-] copy A to C + set B to one >>++++++++[<-------->-]<- subtract 65 from CThis loop sets B if the input is alphanum [ while C <[-] zero out B >>>+[<+<+>>-]<[>+<-]< increment E then add E to C [ while C <++ add two to B >>>+[<+<->>-]<[>+<-] increment E then subtract E from C ]> [<]< ] >>[-] zero out E <<< This loop performs ROT13 [ if B [-]< zero out B [>>+>+<<<-]>>[<<+>>-]> copy A to D >++++++++[<-------->-]<- subtract 65 from D >>++++[<++++++++>-]<-< add 31 to E This loop sets E to hold a case insensitive value and B the flag for lowercase [ while D >>>+<<[>+>[-]<<-]>[<+>-]> if E is zero then set G [ while G <<<<<+ add one to B >>>>++++[<++++++++>-] add 31 to E >- break ] <<-<- decrement D and E ] > [ if E <<<<[-]>>>> zero out A [<<<<->>>>-] movesub E from A ] <<++++[<<++++++++>>-]<<- add 31 to A to put it in the range zero to twentyfive [>>+>+<<<-]>>[<<+>>-]+ copy A to D and set C to one >>+++++[<----->-]<- subtract 26 from D Not sure what this does [ while D <[-] zero out C >>>+[<+<->>-]<[>+<-]< increment F then subtract F from D [<++>>>+[<+<+>>-]<[>+<-]]> add two to C then increment F then add F to D [<]< ] >>[-]<<< zero out F Subtract 13 and add 26 if negative Then recapitalize by adding 31 if B [ while C [-] zero out C <<[>>+>+<<<-]>>[<<+>>-]+> copy A to D and set C to one ------------ subtract 12 from D [ while D <[-] zero out C >>>+[<+<->>-]<[>+<-] increment F then subtract F from D <[<++>>>+[<+<+>>-]<[>+<-]]> increment F then add F to D [<]< ] >>[-]<<<<< zero out F ------------->> subtract 13 from A [[-]+++++[<<+++++>>-]<<+>>] if C then zero out C then add 26 to A IE wrap around <[>++++[<<++++++++>>-]<-]> if B then add 31 to A IE make lowercase ] <[-] zero out B ++++++++[<++++++++>-]<+> add 65 to A IE convert to character ] <. Print A [-]+>>+< Set A and C to one ] >[[-]<]< if C zero out C else break]
-. Print ASCII character 255
-
>>>> ++++ ++++
[<<<<++++>+++ +++> ++++ ++++ +++> ++++ ++++ ++++ + > - ]
+++
[ <<<< >>----.>.-------.+++++++++++++.---.<<<.
>>>++++++++++++++.----------.++++++.<<--.<.
>++>++++>---- ---- ---- - > -]
-
@ohcamacj said:
>>>> ++++ ++++
[<<<<++++>+++ +++> ++++ ++++ +++> ++++ ++++ ++++ + > - ]
+++
[ <<<< >>----.>.-------.+++++++++++++.---.<<<.
>>>++++++++++++++.----------.++++++.<<--.<.
>++>++++>---- ---- ---- - > -],,,,.+.,
,.,,+.++
.---.,,,
,,,+.,,+
.,,,,,,,
,---.,,-
.,,,,,,.
-
The version above, has several bugs.
Most visibly,
Corruption of chr(ord(Z) + 1) and chr(ord(z) + 1)
Less visibly,
Corruption of "high lowercase" chr(129 .. 192)
Corruption of chr(96)I also, didn't like the style of the O(N^2) zigzag method of checking to see if the input was within the range 65 .. 192.
So, I fixed the bugs, designed a O(N) method of checking to see if the input was within a given range, reintroduced lots and lots of bugs trying to copy the algorithm back to brainfuck, and removed all of the new bugs that I introduced.
The result is,
+
>>>>>>>>>+>+>+>+>+>+ <<<<< //initialize nopslide
<<<<<<<<<
[
>>>> [-]
<<<<
,
+ [ -
>>> [-]
+ //set is_alpha to 1
//copy input to test_up test_down
>> [-] > [-]
<<<<<< [ >>>> + > + > + <<<<<< - ]
>>>> [ <<<< + >>>> - ]
//subtract 65 from test_up test_down
++++++++
[ > -------- > -------- << - ]
> - > -
//set comflag if test_up or test_down
> [-]
<< [ >> + > ] >>> [<]
<< [ > + > ] >> [<]
< [ - > ] > [<]
< [ //while (comflag)
<<<< [-] //clear is_alpha
>> + //increment test_up
>> [-] //set comflag if test_up or test_down
<< [ >> + > ] >>> [<]
<< [ > + > ] >> [<]
< [ - > ] > [<]
< [ //if (comflag)
<<<< + //set is_alpha
>>> - //decrement test_down
> [-] //set comflag if test_up or test_down
<< [ >> + > ] >>> [<]
<< [ > + > ] >> [<]
< [ - > ] > [<]
]
> [<]
<
]
<<<< [ //128 character loop input was within 65 to 192
//subtract 65
> ++++++++
[ <<<< -------- >>>> - ]
<<<< -
//prepare for division
> [-]
> [-]
>>>>>>>>>>>>> [-]
<<<<<<<<<<<<<<< [ >>>> + >>>>>>>>>>> + <<<<<<<<<<<<<<< - ]
>>>> [ <<<< + >>>> - ]
++++
[ << ++++++++ >> - ] << -
//divide by 32
>>>>>>>>>>>>> [
> [-] +
<<<<<<<<<<<<<< [ >>>>>>>>>>>>>> - <<<<<<<< ] >>>>>> [<]
>>>>>>>> [
<<<<<<<<<<<<<<< +
>>> ++++
[ << ++++++++ >> - ]
>>>>>>>>>>>> -
]
<<<<<<<<<<<<<< - >>>>>>>>>>>>> -
]
//set input to 0 minus mod32inv plus 31
<<<<<<<<<<<<<<< [ - ]
>> [ << - >> - ]
>> ++++
[ <<<< ++++++++ >>>> - ]
<<<< -
//copy div32 to test_up test_down
>>>>> [-] > [-]
<<<<< [ >>> + > + > + <<<<< - ]
>>> [ <<< + >>> - ]
> - > -
> [-] //set comflag
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [ //same comparison loop as before
//except now checking for div32 being with 0 to 1
//instead of input being within 65 to 192
<<<< [-]
>>> -
> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [
<<<< +
>> +
>> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
]
> [<]
<
]
<<<< [ //64 character loop input was within 65 to 128
//copy input to test_up test_down
>> [-] > [-]
<<<<<< [ >>>> + > + > + <<<<<< - ]
>>>> [ <<<< + >>>> - ]
+++++
[ > ----- > ----- << - ]
>>> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [ //same comparison loop as before
//except now checking if input is within 0 to 25
<<<< [-]
>>> -
> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [
<<<< +
>> +
>> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
]
> [<]
<
]
<<<< [ //52 character loop input was within 65 to 128 and 0 to 25
>> [-] > [-]
<<<<<< [ >>>> + > + > + <<<<<< - ]
>>>> [ <<<< + >>>> - ]
> ------------
> ------------
> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [ //same comparison loop as before
//except now checking if input is within A to L
<<<< [-]
>>> -
> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
< [
<<<< +
>> +
>> [-]
<< [>> + > ] >>> [<]
<< [> + > ] >> [<]
< [ - > ] > [<]
]
> [<]
<
]
<<<<<<< ------------- //apply rot13
>>> [ //add 26 if A to L
[-]
> +++++
[<<<< +++++ >>>> - ]
<<<<+
>>>
]
] //end if 52 loop
] //end if 64 loop
//fix up all lowercase add 32 times div32
<< [
>>> ++++
[ <<<< ++++++++ >>>> - ]
<<< -
]
//add 65
>>> ++++++++
[ <<<< ++++++++ >>>> - ]
<<<< +
>>> //move pointer back to position at loop start
] //end if 128 loop
<<<
.
[-] //print out and zero cell
>>>> + //set continflag
<<<<
]
>>>> [ <<<< + >>>> - ] //copy continflag to input to stop if previous
<<<< //character was 255
]Cells used are labeled
0: input
1: div32
2: mod32inv
3: is_alpha, is_al
4: copybuf, tmpidx, continflag
5: test_up
6: test_down
7: comflag
8: zero
9 .. 14: nopslide
15: divtmp
16: wrapflag
Sorry for the length -- this forum could really use some spoiler or readmore tags.
