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/]!0123456789

    Both 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; }} 
    if(charval >= 97 && charval <= 122){ charval += 13; if(charval > 122){charval -= 26; }}
    become so many orders of magnitude slower?

     

    (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 C
    		
    		This 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.


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.