miércoles, 21 de julio de 2010

ROT 13, Brainfuck y Ook! (+traductor)

Hoy presento uno de los desavarios mas preocupantes que he escrito últimamente, unos programas en Brainfuck (muy sencillos, eso sí)... pero empezemos por el principio.

Actualizado: el traductor ahora también soporta interpretes de Ook! que no permitan comentarios.

Brainfuck

Como dice la Wikipedia:

Brainfuck (jodecerebros), es un lenguaje de programación esotérico, diseñado por Urban Müller en 1993, con el objetivo de hacer un lenguaje que fuera a la vez muy simple, Turing completo y que requiriese un compilador pequeño. Müller basó Brainfuck en la máquina de Turing y le sirvió de inspiración el compilador de 1024 bytes de tamaño del lenguaje FALSE.
La distribución clásica es la versión 2 escrita por el propio Müller, conteniendo un compilador para el ordenador Amiga, un intérprete, programas de ejemplo y un documento "readme".

Brainfuck tiene solo 8 instrucciones:
  • >   Incrementa el puntero, en C sería p++ 
  • <   Decrementa el puntero, en C sería p--
  • + Incrementa el byte al que apunta el puntero, en C p*++
  • - Decrementa el byte al que apunta el puntero, en C p*--
  • [ Salta hasta el ], si el byte apuntado es 0, en C  while (p*){
  • ] Salta hasta el [, si el byte apuntado es distinto de 0, en C sería el } del while
  • . Muestra por pantalla el valor apuntado, en C putchar(p*);
  • , Acepta un valor por STDIN y lo guarda en el byte apuntado, p*=getchar();

El resto de caracteres se ignora, el Hola mundo, por ejemplo, sería (sacado de Wikipedia):

++++++++++
[              Bucle para iniciar las memorias (se repite 10 veces)
 >+++++++>++++++++++>+++++++++++>+++>+<<<<<-
      70        100       110      30  10
]
>++.              imprime 'H'   (72) 1
>>+.              imprime 'o'  (111) 3
---.                      'l'  (108) 3
<---.                     'a'   (97) 2
>>++.                   espacio (32) 4
<+.                       'm'  (109) 3
++++++++.                 'u'  (117) 3
-------.                  'n'  (110) 3
<+++.                     'd'  (100) 2
>+.                       'o'  (111) 3
>+.                       '!'   (33) 4
>.                   nuevalínea (10) 5

Ook!

Además, este lenguaje dio lugar a otro, llamado Ook!, un lenguaje "diseñado para orangutanes":

Ook! (con el signo de exclamación) es un lenguaje de programación esotérico Turing completo. Este lenguaje es una parodia de Brainfuck, del que toma su conjunto completo de comandos (ver tabla). Deriva su completitud Turing de esta relación.
Según su diseñador, David Morgan-Mar, el lenguaje está diseñado para orangutanes. Tiene 3 palabras reservadas (Ook., Ook?, y Ook!); que pueden combinarse en ocho maneras diferentes para formar el repertorio de instrucciones del lenguaje. Ook! pretende ser fácil de aprender para los orangutanes y evitar cualquier mención de la palabra «mono». [Wikipedia]

Comparten el set de instrucciones, cambiando solo su nombre, esta es la relación de los comandos Brainfuck - Ook!
  • > : Ook. Ook?   Incrementa el puntero, en C sería p++ 
  • < : Ook? Ook.   Decrementa el puntero, en C sería p--
  • + : Ook. Ook. Incrementa el byte al que apunta el puntero, en C p*++
  • - : Ook! Ook! Decrementa el byte al que apunta el puntero, en C p*--
  • [ : Ook! Ook? Salta hasta el ], si el byte apuntado es 0, en C  while (p*){
  • ] : Ook? Ook! Salta hasta el [, si el byte apuntado es distinto de 0, en C sería el } del while
  • . : Ook! Ook. Muestra por pantalla el valor apuntado, en C putchar(p*);
  • , : Ook. Ook! Acepta un valor por STDIN y lo guarda en el byte apuntado, p*=getchar();

ROT 13

Y por último, ROT 13, este no es un lenguaje de programación, solo un sistema clásico de cifrado de tipo césar ("movía" las letras n veces hacia la derecha) con la peculiaridad de que al mover las letras 13 veces, el cifrado y el descifrado se hacían igual.Así de simple, si quieres ver más -> https://secure.wikimedia.org/wikipedia/es/wiki/ROT13

Al tema...

Bien, el "reto" era escribir un programa en Brainfuck que cifrase con ROT-13 y otro que convirtiese un código en ese lenguaje a Ook!, para empezar, como base y para entender mejor el lenguaje, escribí un programa que guardase lo que el usuario dijera y lo devolviese despues por pantalla.

Este es el código,el caracter para detener la entrada es Enter, más que nada porque es más fácil de utilizar:

Guarda lo que dice el usuario, hasta que pulse enter
>+[>,----------]
Vuelve al principio de la cadena
+++
[<]>>
Muestra los caracteres
[++++++++++.>]
Salta a una nueva linea
++++++++++.

Por muy críptico que parezca, en realidad es bastante sencillo si se lee paso a paso:

{Línea 1}
Primero se salta a un nuevo puntero ( > ), para dejar este intacto (con valor 0), y que sirva como limitador de la cadena, después se suma 1 al valor apuntado, para poder entrar en el while.
Una vez en el while se vuelve a incrementar ( > ) el puntero, esto se hace para conseguir un byte diferente por cada letra que el usuario introduzca, en ese byte se introduce lo que usuario mande ( , ), y a este valor se le resta 10 ( ---------- ) para hacer que si es un salto de línea, que tiene el valor 10, se quede a 0, en el resto de valores se revertirá. y se acabe el bucle, por último se cierra el while ( ] ).

{Línea 2}
Se suman 3 al valor apuntado ( +++ ), este byte corresponde al Enter del usuario, se podría pensar que hay que dejarlo a 0, para que luego al sumar 10 a todo para recuperar los valores originales se muestre el enter, el problema es que no debe estar a 0, ya que sino no podremos "entrar" en el siguiente while, así que añadiendo 3, más los 10 posteriores se convierte en un retorno de carro, y no molesta por el medio.

{Línea 3}
Se vuelve al principio, haciendo while ( [ ) y retrocediendo el puntero ( < ) , hasta que finalmente se encuentre con el valor 0 que dejamos al principio, y que hará que el programa salga del bucle ( ] ), una vez ahí avanzamos 2 veces el puntero ( > ) y ( > ), uno por el valor nulo y otro por el 1 que dejamos para poder entrar en el bucle del principio.

{Línea 4}
Solo queda ir leyendo carácter a carácter con un bucle ( [ ), sumando 10 para recuperar los valores originales ( ++++++++++ ) , mostrarlos por pantalla ( . ) y saltar al siguiente carácter ( > ), el bucle acabará ( ] ) con el último carácter, que será un 0

{Línea 5}
Solo queda hacer el salto de línea que cambiamos por un retorno de carro, simplemente añadiendo 10 al valor nulo actual ( ++++++++++ )  y mostrandolo por pantalla ( . ) .

Si te parece extraño (que lo es, para que nos vamos a engañar), piensa que pinta tendría el código solo:
>+[>,----------]+++[<]>>[++++++++++.>]++++++++++.

Aunque también se podría hacer por la vía fácil:
+[,.----------]
¿Pero que gracia tendría así?

"Cifrando" y "descifrando" (con ROT 13)

Por cosas de la vida, no se pueden aprovechar las facilidades del ROT 13, ya que la aritmética es nula, así que habrá que conformarse con hacer un par de programas, uno que añada 13 y otro que los reste, esto se puede hacer sencillamente aprovechando el programa que repite lo que dice el usuario, solo hay que añadir una parte que añada 13 antes de mostrar el valor "cifrado" y que los reste antes del "descifrado",  el añadido es obvio, lo único que merece la pena comentar es que el movimiento adicional de punteros es para evitar que queden caracteres feos por el medio con las rotariones (el 13 es invisible, pero el 26, 13+13, no siempre ) :

Cifrar:
>+[>,----------]
Vuelve al principio de la cadena
+++
[<]>>>
Imprime la info
[<++++++++++ +++++++++++++.>>]
Imprime un espacio
++++++++++.

Descifrar:
>+[>,----------]
Vuelve al principio de la cadena
+++
[<]>>>
Imprime la info
[<++++++++++ -------------.>>]
Imprime un espacio
++++++++++.

Traduciendo a Ook!

Y Ook! ... tenía escrito un traductor de Brainfuck a Ook!, pero me lo cargué :(, a ver si lo reescribo, sinó habra que conformarse con este script en python.
EDIT (00:15): al final si que hay traductor, lo conseguí reescribir de 0, y la verdad... quedé contento con el resultado, está coloreado despues de las referencias o [aquí], como detalle comentar que los datos acaban con un "\0" , así que quiza sea mejor usarlo así:


(cat loquesea.b ;echo -e "\0")|./bf2ook > loquesea.ook



ps: Pygments es sorprendente, hasta colorea esto :P

Hasta otra, si es que queda alguien cuerdo por ahí... :)

[Referencias]
http://codegolf.com/brainfuck
https://secure.wikimedia.org/wikipedia/es/wiki/Brainfuck
https://secure.wikimedia.org/wikipedia/es/wiki/Ook!




(Primero se preparan las letras)
>           (Para uso posterior) (L 1)
>>> (Esta memoria me la reservo) (L 3)
O = 79
o = 111
k = 107
! = 33
? = 63
(punto) = 46
(espacio) = 32
++++++++++ (L 4)
[
      >++++++++ ( 8 )   (L  5)
      >+++++++++++ (11) (L  6)
      >+++++++++++ (11) (L  7)
      >+++ (3)          (L  8)
      >++++++ (6)       (L  9)
      >+++++ (5)        (L 10)
      >+++ (3)          (L 11)
      <<<<<<<-          (L  4)
]
>-     (L  5)
>+     (L  6)
>---   (L  7)
>+++   (L  8)
>+++   (L  9)
>----  (L 10)
>++    (L 11)
<<<<<<< (L 4)
<<< (Se vuelve al principio) (L 1)
,   (Se lee lo que el usuario dice)  (L 1)
[
    (Se copia por si no es codigo )
    (en el nivel 2 L = 2)
    [>+>+<<-]
    >>        (L 3)
    [-<<+>>]
    <<        (L 1)
    
    (Por defecto NO es codigo)
    >>>+ (L 4)
    <<<  (L 1)
    (El L = 3 se usa para buscar los valores)
    >>++++ (L 3)
    [<<---------- (L 1) >> -] (L 3)
    <<--- (L 1)
    [   (Si no es un mas)
        - (L 1)
        [   (Si no es una coma)
            -    (L 1)
            [   (Si no es un menos)
                -  (L 1)
                [   (Si no es un punto)
                    -------------- (Menos 14) (L 1)
                    [   (Si no es un menor que)
                        -- (L 1)
                        [   ( Si no es un mayor que )
                            <++++ (L 0)
                            [->-------<] (Se resta 28)
                            >     (L 1)
                            -     (L 1)
                            [   ( Si no abre corchetes )
                                -- (L 1)
                                [   ( Si no cierra corchetes )
                                    > (Anhade un punto si permite comentarios) (L 2) (No es codigo dice el caracter a secas)
                                    >> - (L 4) ( Parece que no pero es dificil no meter )
                                    <<< (L 1)  ( codigo sin querer en los comentarios )
                                    [-] (Pone el caracter actual a 0)
                                ]
                                >>> (L 4)
                                [   ( Si cierra corchetes )
                                    >.   (L  5)
                                    >.   (L  6)
                                    >.   (L  7)
                                    >>.   (L  9)
                                    >>.   (L 11)
                                    <<<<<<< (L 4)
                                    >.   (L  5)
                                    >.   (L  6)
                                    >.   (L  7)
                                    >.   (L  8)
                                    >>>.   (L 11)
                                    <<<<<<< (L 4)
                                    - (L 4)
                                ]
                                <<< (L 1)
                            ]
                            >>> (L 4)
                            [   ( Si abre corchetes
                                >.   (L  5)
                                >.   (L  6)
                                >.   (L  7)
                                >.   (L  8)
                                >>>.   (L 11)
                                <<<<<<< (L 4)
                                >.   (L  5)
                                >.   (L  6)
                                >.   (L  7)
                                >>.   (L 9)
                                >>.   (L 11)
                                <<<<<<< (L 4)
                                - (L 4)
                            ]
                            <<< (L 1)
                        ]
                        >>> (L 4)
                        [   ( Si es un mayor que )
                            >.   (L  5)
                            >.   (L  6)
                            >.   (L  7)
                            >>>. (L 10)
                            >.   (L 11)
                            <<<<<<< (L 4)
                            >.   (L  5)
                            >.   (L  6)
                            >.   (L  7)
                           >>.   (L 9)
                           >>.   (L 11)
                           <<<<<<< (L 4)
                           - (L 4)
                        ]
                        <<< (L 1)
                    ]
                    >>> (L 4)
                    [   (Si es un menor que)
                        >.   (L  5)
                        >.   (L  6)
                        >.   (L  7)
                        >>.   (L 9)
                        >>.   (L 11)
                        <<<<<<< (L 4)
                        >.   (L  5)
                        >.   (L  6)
                        >.   (L  7)
                        >>>. (L 10)
                        >.   (L 11)
                        <<<<<<< (L 4)
                        - (L 4)
                    ]
                    <<< (L 1)
                ]
                >>> (L 4)
                [   ( Si es un punto)
                    >.   (L  5)
                    >.   (L  6)
                    >.   (L  7)
                    >.   (L  8)
                    >>>.   (L 11)
                    <<<<<<< (L 4)
                    >.   (L  5)
                    >.   (L  6)
                    >.   (L  7)
                    >>>. (L 10)
                    >.   (L 11)
                    <<<<<<< (L 4)
                    - (L 4)
                ]
                <<< (L 1)
            ]
            >>> (L 4)
            [   ( Si es un menos)
                >.   (L  5)
                >.   (L  6)
                >.   (L  7)
                >.   (L  8)
                >>>.   (L 11)
                <<<<<<< (L 4)
            
                >.   (L  5)
                >.   (L  6)
                >.   (L  7)
                >.   (L  8)
                >>>.   (L 11)
                <<<<<<< (L 4)
                - (L 4)
            ]
            <<< (L 1)
        ]
        >>> (L 4)
        [   ( Si es una coma)
            >.   (L  5)
            >.   (L  6)
            >.   (L  7)
            >>>. (L 10)
            >.   (L 11)
            <<<<<<< (L 4)
            
            >.   (L  5)
            >.   (L  6)
            >.   (L  7)
            >.   (L  8)
            >>>.   (L 11)
            <<<<<<< (L 4)
            - (L 4)
        ]
        <<< (L 1)
    ]
    >>> (L 4)
    [   (Si es un mas)
        >.   (L  5)
        >.   (L  6)
        >.   (L  7)
        >>>. (L 10)
        >.   (L 11)
        <<<<<<< (L 4)
        >.   (L  5)
        >.   (L  6)
        >.   (L  7)
        >>>. (L 10)
        >.   (L 11)
        <<<<<<< (L 4)
        - (L 4)
    ]
    <<< (L 1)
    >[-] (Limpiando)  (L 2)
    >[-] (Limpiando)  (L 3)
    << (L 1)
    , (Se lee lo que el usuario dice)  (L 1)
]

2 comentarios: