Mais um blog inútil.

Bem-vindos. Espicaçado pelas inutilidades que o falso e o Dcoder fizeram em malbolge, e ainda mais depois de o falso ter afirmado peremptoriamente que era impossível fazer uma arvorezinha à mão nesta linguagem diabólica, decidi, fatalmente, jogar mãos à obra.

O segredo do falso em relação ao malbolge é que todo o código dele é gerado por bruteforce. As optimizações do Dcoder limitaram-se a correr o bruteforce durante mais tempo para procurar soluções mais curtas. Neste post proponho um método real, analítico e bastante simples para criar um programa de malbolge que imprima qualquer sequência de caracteres, com a limitação de ser curta. E sim, a arvorezinha é suficientemente curta. ;-) Para facilitar a programação, criei vários utilitários, baseados no malbolge.c original, que constituem o malbolge SDK disponível aqui. Eis uma curta explicação de cada programa:

Um dos problemas da programação em malbolge é que que o code pointer e o data pointer começam ambos a 0 no início do programa, ou seja, estão sobrepostos. Por isso, o meu plano começa por separar claramente a zona de código da zona de dados. Assim sendo, a primeira coisa que faço é avançar o D para qualquer sítio mais à frente, com a instrução "j". Devido à obfuscação que a o malbolge obriga no input, esta instrução na posição 0 de memória corresponde a um salto do D para o valor 41. Temos agora 40 bytes de código disponíveis pela frente, sem mais complicações, antes de voltar a tropeçar nos dados.

Outro dos problemas é a alteração sofrida nas instruções depois de serem executadas, e também dos dados depois de serem usados pelos operadores. Para minimizar estes problemas optei por uma abordagem naïve mas suficientemente eficaz para o problema em questão, que consiste em ter todo o código e dados a correr linearmente, excepto a configuração inicial da área de dados descrita anteriormente.

Talvez a limitação mais severa seja a dos caracteres que podemos usar como input inicial no malbolge, o que dificulta tremendamente o uso de valores pré-definidos, como sejam os caracteres da nossa string. Isto obriga-nos a calcular praticamente todos os valores desejados e imprimi-los, um por um. O malbolge apenas oferece duas instruções de cálculo, o trinary rotate e a trinary op a.k.a. crazy operation. Felizmente para nós, qualquer valor ASCII é calculável usando estas operações com um máximo 3 operações seguidas com valores específicos nos dados (por vezes antecedidas de nops, é certo, para aceder aos dados necessários que, como é sabido, variam consoante a sua posição em memória). Para ajudar, não precisamos de ter o valor exacto no A, basta um A tal que A & 0xFF seja o caracter que queremos (os registos são unsigned short e o print só usa os primeiros 8 bits). Para descobrir a menor sequência de operações necessárias e respectivos valores nos dados fiz o malbolgeconstant (tal como referi acima, pertence ao SDK).

Para exemplificar, vamos criar um programa que imprima "Oi". Usaremos os símbolos reais para as instruções e não a versão executável, que depois compilaremos com o malbolgec. Primeiro avançamos o D para a posição 41:

jv

Agora calculamos o caracter "O" (ASCII 79) com o malbolgeconstant (tem como input o valor do D, o valor que procuramos e o valor actual do A, que no início do programa é zero):

./malbolgeconstant 41 79 0
EUREKA! code=p pos=42 data=p (r)
EUREKA! code=* pos=41 data=p (s)

OK, esta efusão de felicidade conta-nos que devemos usar as operações "*" e "p", com o input "p" e "p" respectivamente (que correspondem a "r" e "s" em código obfuscado, mas vamos aqui trabalhar com código normal). De notar que o pos (a posição de memória onde devem estar os dados) começa a 41, que foi a posição inicial que especificámos. Poderia ser 42 ou mais, o que significaria que precisávamos de inserir nops no código (e nos dados, mas aqui não é obrigatório serem nops) antes de executar as instruções especificadas. Por vezes os valores necessários às operações só estão disponíveis mais à frente na memória, devido à forma como o malbolge obriga a codificar as sores. Adiante, o nosso programa tem agora este aspecto:

j*p<voooooooooooooooooooooooooooooooooooopp

Recapitulando: avançamos o D, calculamos "O" (o seu valor fica no registo A) e imprimimo-lo com "< ", terminando o programa com o "v". A sequência de "o" (nops) no meio é apenas para encher choriços, já que não chegam a ser executados. Estão cá apenas para chegar à posição 41 e 42, onde temos o input necessário às nossas instruções. Vamos compilar este programa e corre-lo no malbolged para ver a evolução dos registos: ./malbolgec example.mbs example.mb && ./malbolged example.mb
CODE: j MEM: 040 (() A: 00000 C: 00000 D: 00000
CODE: * MEM: 115 (s) A: 00000 C: 00001 D: 00041
CODE: p MEM: 114 (r) A: 19721 C: 00002 D: 00042
CODE: < MEM: 29416 (è) A: 09807 C: 00003 D: 00043
O CODE: v MEM: 114 (r) A: 09807 C: 00004 D: 00044

mirage@arda ~/malbolge-sdk-1.0 $ cat example.mbs
j*p<*p<*pp<voooooooooooooooooooooooooooooppo/joiv*
mirage@arda ~/malbolge-sdk-1.0 $ ./malbolgec example.mbs example.mb
mirage@arda ~/malbolge-sdk-1.0 $ cat example.mb
(&<`#9]~65YF876543210/.-,+*)('&%$#"!~}|{zsrwIYt3!T
mirage@arda ~/malbolge-sdk-1.0 $ ./malbolge example.mb
Oi

Vamos agora à prova dos nove: a arvorezinha! Note-se que esta arvorezinha tem \n na última linha, como manda o RFC. Tal como as arvorezinhas anteriores em malbolge, não usa ciclos. Ocupa 99 caracteres (incluí no SDK uma versão sem a última newline com apenas 95 caracteres). Como verão, usei dois incrementos ao D, porque a arvorezinha não coube em 40 caracteres de código. Ainda assim, foi necessário usar o próprio valor em 44, que é um < , para imprimir um caracter da árvore, e simultaneamente servir de input para o segundo "j". Reparem: ./malbolgevalid 44 44
44: 037 (v) 054 (i) 055 (<) 073 (/) 089 (*) 090 (j) 112 (p) 118 (o)