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

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]

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.

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.

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.

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');
}