Concurso de código C ofuscado em 2006. Por favor, explique sykes2.c

975

Como esse programa C funciona?

main(_){_^448&&main(-~_);putchar(--_%64?32|-~7[__TIME__-_/8%8][">'txiZ^(~z?"-48]>>";;;====~$::199"[_*2&8|_/64]/(_&2?1:8)%8&1:10);}

Compila como está (testado em gcc 4.6.3). Imprime o horário em que é compilado. No meu sistema:

    !!  !!!!!!              !!  !!!!!!              !!  !!!!!! 
    !!  !!  !!              !!      !!              !!  !!  !! 
    !!  !!  !!              !!      !!              !!  !!  !! 
    !!  !!!!!!    !!        !!      !!    !!        !!  !!!!!! 
    !!      !!              !!      !!              !!  !!  !! 
    !!      !!              !!      !!              !!  !!  !! 
    !!  !!!!!!              !!      !!              !!  !!!!!!

Fonte: sykes2 - Um relógio em uma linha , sugere o autor do sykes2

Algumas dicas: Não há avisos de compilação por padrão. Compilado com -Wall, os seguintes avisos são emitidos:

sykes2.c:1:1: warning: return type defaults to int [-Wreturn-type]
sykes2.c: In function main’:
sykes2.c:1:14: warning: value computed is not used [-Wunused-value]
sykes2.c:1:1: warning: implicit declaration of function putchar [-Wimplicit-function-declaration]
sykes2.c:1:1: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
sykes2.c:1:1: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
sykes2.c:1:1: warning: control reaches end of non-void function [-Wreturn-type]
brega
fonte
6
Depuração: adicionando printf("%d", _);ao início das mainimpressões: pastebin.com/HHhXAYdJ
corny
Inteiro, cada variável não int
digitada
18
Você leu a dica? ioccc.org/2006/sykes2/hint.text
nhahtdh 13/03
Se você executá-lo assim, ele trava:./a.out $(seq 0 447)
SS Anne

Respostas:

1819

Vamos ofuscar isso.

Recuo:

main(_) {
    _^448 && main(-~_);
    putchar(--_%64
        ? 32 | -~7[__TIME__-_/8%8][">'txiZ^(~z?"-48] >> ";;;====~$::199"[_*2&8|_/64]/(_&2?1:8)%8&1
        : 10);
}

Introduzindo variáveis ​​para desembaraçar essa bagunça:

main(int i) {
    if(i^448)
        main(-~i);
    if(--i % 64) {
        char a = -~7[__TIME__-i/8%8][">'txiZ^(~z?"-48];
        char b = a >> ";;;====~$::199"[i*2&8|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    } else {
        putchar(10); // newline
    }
}

Observe que, -~i == i+1devido ao complemento de dois. Portanto, temos

main(int i) {
    if(i != 448)
        main(i+1);
    i--;
    if(i % 64 == 0) {
        putchar('\n');
    } else {
        char a = -~7[__TIME__-i/8%8][">'txiZ^(~z?"-48];
        char b = a >> ";;;====~$::199"[i*2&8|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    }
}

Agora, observe que a[b]é o mesmo queb[a] e aplique a -~ == 1+alteração novamente:

main(int i) {
    if(i != 448)
        main(i+1);
    i--;
    if(i % 64 == 0) {
        putchar('\n');
    } else {
        char a = (">'txiZ^(~z?"-48)[(__TIME__-i/8%8)[7]] + 1;
        char b = a >> ";;;====~$::199"[(i*2&8)|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    }
}

Convertendo a recursão em um loop e esgueirando-se um pouco mais de simplificação:

// please don't pass any command-line arguments
main() {
    int i;
    for(i=447; i>=0; i--) {
        if(i % 64 == 0) {
            putchar('\n');
        } else {
            char t = __TIME__[7 - i/8%8];
            char a = ">'txiZ^(~z?"[t - 48] + 1;
            int shift = ";;;====~$::199"[(i*2&8) | (i/64)];
            if((i & 2) == 0)
                shift /= 8;
            shift = shift % 8;
            char b = a >> shift;
            putchar(32 | (b & 1));
        }
    }
}

Isso gera um caractere por iteração. Cada 64º caractere gera uma nova linha. Caso contrário, ele usa um par de tabelas de dados para descobrir o que produzir e coloca o caractere 32 (um espaço) ou o caractere 33 (a !). A primeira tabela ( ">'txiZ^(~z?") é um conjunto de 10 bitmaps que descrevem a aparência de cada caractere, e a segunda tabela ( ";;;====~$::199") seleciona o bit apropriado a ser exibido no bitmap.

A segunda mesa

Vamos começar examinando a segunda tabela int shift = ";;;====~$::199"[(i*2&8) | (i/64)];,. i/64é o número da linha (6 a 0) e i*2&8é 8 se i4, 5, 6 ou 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8seleciona o dígito octal alto (para i%8= 0,1,4,5) ou o dígito octal baixo (para i%8= 2,3,6,7) do valor da tabela. A tabela de turnos acaba assim:

row col val
6   6-7 0
6   4-5 0
6   2-3 5
6   0-1 7
5   6-7 1
5   4-5 7
5   2-3 5
5   0-1 7
4   6-7 1
4   4-5 7
4   2-3 5
4   0-1 7
3   6-7 1
3   4-5 6
3   2-3 5
3   0-1 7
2   6-7 2
2   4-5 7
2   2-3 3
2   0-1 7
1   6-7 2
1   4-5 7
1   2-3 3
1   0-1 7
0   6-7 4
0   4-5 4
0   2-3 3
0   0-1 7

ou em forma de tabela

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Observe que o autor usou o terminador nulo para as duas primeiras entradas da tabela (sorrateira!).

Isso foi desenvolvido após uma exibição de sete segmentos, com 7s como espaços em branco. Portanto, as entradas na primeira tabela devem definir os segmentos que serão iluminados.

A primeira mesa

__TIME__é uma macro especial definida pelo pré-processador. Ele se expande para uma constante de cadeia que contém o tempo em que o pré-processador foi executado, no formulário "HH:MM:SS". Observe que ele contém exatamente 8 caracteres. Observe que 0-9 tem valores ASCII 48 a 57 e :tem valor ASCII 58. A saída é de 64 caracteres por linha, de modo que deixa 8 caracteres por caractere __TIME__.

7 - i/8%8é, portanto, o índice do __TIME__que está sendo produzido atualmente ( 7-é necessário porque estamos iterando ipara baixo). Então, té o caráter de __TIME__ser produzido.

aacaba igualando o seguinte em binário, dependendo da entrada t:

0 00111111
1 00101000
2 01110101
3 01111001
4 01101010
5 01011011
6 01011111
7 00101001
8 01111111
9 01111011
: 01000000

Cada número é um bitmap que descreve os segmentos iluminados em nossa exibição de sete segmentos. Como os caracteres são todos ASCII de 7 bits, o bit alto é sempre limpo. Assim, 7na tabela de segmentos sempre imprime em branco. A segunda tabela fica assim com 7s como espaços em branco:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

Assim, por exemplo, 4é 01101010(bits 1, 3, 5 e 6 definidos), que imprime como

----!!--
!!--!!--
!!--!!--
!!!!!!--
----!!--
----!!--
----!!--

Para mostrar que realmente entendemos o código, vamos ajustar um pouco a saída com esta tabela:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Isso é codificado como "?;;?==? '::799\x07". Para fins artísticos, adicionaremos 64 a alguns dos caracteres (como apenas os 6 bits baixos são usados, isso não afetará a saída); isso dá "?{{?}}?gg::799G"(observe que o 8º caractere não é utilizado, para que possamos fazer o que quisermos). Colocando nossa nova tabela no código original:

main(_){_^448&&main(-~_);putchar(--_%64?32|-~7[__TIME__-_/8%8][">'txiZ^(~z?"-48]>>"?{{?}}?gg::799G"[_*2&8|_/64]/(_&2?1:8)%8&1:10);}

Nós temos

          !!              !!                              !!   
    !!  !!              !!  !!  !!  !!              !!  !!  !! 
    !!  !!              !!  !!  !!  !!              !!  !!  !! 
          !!      !!              !!      !!                   
    !!  !!  !!          !!  !!      !!              !!  !!  !! 
    !!  !!  !!          !!  !!      !!              !!  !!  !! 
          !!              !!                              !!   

assim como esperávamos. Não é tão sólido quanto o original, o que explica por que o autor optou por usar a tabela que usou.

nneonneo
fonte
2
@drahnr - Tecnicamente, é tanto a *(desreferência) quanto a +: P
detly
18
@ АртёмЦарионов: Cerca de 30 minutos, mas eu voltei e editou bastante. Eu uso muito C, e já fiz algumas ofuscações da IOCCC por interesse pessoal antes (a última que fiz, apenas por interesse pessoal, foi esse lindo rastreador de raios ). Se você quiser perguntar como ele funciona, eu ficaria feliz obrigar;)
nneonneo
5
@ АртёмЦарионов: cerca de um dia IIRC (também conta o tempo gasto na compreensão da geometria do raytracer). Esse programa também é muito inteligente, porque não usa palavras-chave .
Nneonneo
178
C .. todo o poder da linguagem de montagem combinada com a capacidade de leitura de linguagem assembly
wim
6
Para mais informações, consulte "Ofuscado C e outros mistérios", de Don Libes. Ele ensina técnicas de C analisando as entradas do concurso C ofuscadas.
Chris N
102

Vamos formatar isso para facilitar a leitura:

main(_){
  _^448&&main(-~_);
  putchar((--_%64) ? (32|-(~7[__TIME__-_/8%8])[">'txiZ^(~z?"-48]>>(";;;====~$::199")[_*2&8|_/64]/(_&2?1:8)%8&1):10);
}

Portanto, executando-o sem argumentos, _ (argc convencionalmente) é 1. main()chamará recursivamente a si mesmo, passando o resultado de -(~_)(NOT bit a bit negativo _), então, na verdade, ocorrerá 448 recursões (apenas condição onde _^448 == 0).

Levando isso, ele imprimirá 7 linhas largas de 64 caracteres (a condição externa ternária e 448/64 == 7). Então, vamos reescrevê-lo um pouco mais limpo:

main(int argc) {
  if (argc^448) main(-(~argc));
  if (argc % 64) {
    putchar((32|-(~7[__TIME__-argc/8%8])[">'txiZ^(~z?"-48]>>(";;;====~$::199")[argc*2&8|argc/64]/(argc&2?1:8)%8&1));
  } else putchar('\n');
}

Agora, 32é decimal para o espaço ASCII. Imprime um espaço ou um '!' (33 é '!', Daí o ' &1' no final). Vamos nos concentrar no blob no meio:

-(~(7[__TIME__-argc/8%8][">'txiZ^(~z?"-48]) >>
     (";;;====~$::199"[argc*2&8|argc/64]) / (argc&2?1:8) % 8

Como outro pôster disse, __TIME__é o tempo de compilação do programa e é uma string, portanto há alguma aritmética em andamento, além de tirar proveito de um índice de matriz sendo bidirecional: a [b] é o mesmo que b [a] para matrizes de caracteres.

7[__TIME__ - (argc/8)%8]

Isso selecionará um dos 8 primeiros caracteres em __TIME__. Isso é indexado em [">'txiZ^(~z?"-48](0-9 caracteres são 48-57 decimais). Os caracteres nessa sequência devem ter sido escolhidos para seus valores ASCII. A manipulação de código ASCII com o mesmo caractere continua através da expressão, resultando na impressão de um '' ou '!' dependendo da localização no glifo do personagem.

chmeee
fonte
49

Adicionando às outras soluções, -~xé igual a x+1porque ~xé equivalente a (0xffffffff-x). Isso é igual ao (-1-x)complemento 2s, assim -~xé -(-1-x) = x+1.

Thomas Song
fonte
5
Interessante. Eu sei há algum tempo que ~ x == -x - 1, mas eu não conhecia o raciocínio matemático por trás disso.
ApproachingDarknessFish
3
Ey, Cole, (-1-x) é o mesmo que (-x-1), você não precisa "consertar" isso !!
Thomas Canção
7
A mesma razão pela qual, se alguém está -1338, então eles são NÃO 1337.
Andrew Mao
4

Eu ofusquei a aritmética do módulo o máximo que pude e removi a reccursão

int pixelX, line, digit ;
for(line=6; line >= 0; line--){
  for (digit =0; digit<8; digit++){
    for(pixelX=7;pixelX > 0; pixelX--){ 
        putchar(' '| 1 + ">'txiZ^(~z?"["12:34:56"[digit]-'0'] >> 
          (";;;====~$::199"[pixel*2 & 8  | line] / (pixelX&2 ? 1 : 8) ) % 8 & 1);               
    }
  }
  putchar('\n');
}

Expandindo um pouco mais:

int pixelX, line, digit, shift;
char shiftChar;
for(line=6; line >= 0; line--){
    for (digit =0; digit<8; digit++){
        for(pixelX=7;pixelX >= 0; pixelX--){ 
            shiftChar = ";;;====~$::199"[pixelX*2 & 8 | line];
            if (pixelX & 2)
                shift = shiftChar & 7;
            else
                shift = shiftChar >> 3;     
            putchar(' '| (">'txiZ^(~z?"["12:34:56"[digit]-'0'] + 1) >> shift & 1 );
        }

    }
    putchar('\n');
}
Lefteris E
fonte