Concurso de código C ofuscado 2006. Explique sykes2.c

975

¿Cómo funciona este programa C?

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

Se compila tal como está (probado gcc 4.6.3). Imprime la hora cuando se compila. En mi sistema:

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

Fuente: sykes2 - Un reloj en una línea , pistas del autor sykes2

Algunas sugerencias: No hay advertencias de compilación por defecto. Compilado con -Wall, se emiten las siguientes advertencias:

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]
cursi
fuente
66
Depurar: Agregar printf("%d", _);al comienzo de las mainimpresiones: pastebin.com/HHhXAYdJ
curny
Entero, cada variable sin tipo se int
configura por
18
¿Has leído la pista? ioccc.org/2006/sykes2/hint.text
nhahtdh
Si lo ejecuta así, se bloquea:./a.out $(seq 0 447)
SS Anne

Respuestas:

1819

Vamos a ofuscarlo.

Sangría:

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

Introduciendo variables para desenredar este desastre:

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
    }
}

Tenga en cuenta que -~i == i+1debido a dos complemento. Por lo tanto, tenemos

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

Ahora, tenga en cuenta que a[b]es lo mismob[a] y aplique el -~ == 1+cambio nuevamente:

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

Convirtiendo la recursión en un bucle y escabulléndose en un poco más de simplificación:

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

Esto genera un carácter por iteración. Cada 64 caracteres, genera una nueva línea. De lo contrario, utiliza un par de tablas de datos para determinar qué generar y coloca el carácter 32 (un espacio) o el carácter 33 (a !). La primera tabla ( ">'txiZ^(~z?") es un conjunto de 10 mapas de bits que describen la apariencia de cada carácter, y la segunda tabla ( ";;;====~$::199") selecciona el bit apropiado para mostrar desde el mapa de bits.

La segunda mesa

Vamos a empezar por el examen de la segunda tabla, int shift = ";;;====~$::199"[(i*2&8) | (i/64)];. i/64es el número de línea (6 a 0) y i*2&8es 8 iff ies 4, 5, 6 o 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8selecciona el dígito octal alto (para i%8= 0,1,4,5) o el dígito octal bajo (para i%8= 2,3,6,7) del valor de la tabla. La tabla de turnos termina luciendo así:

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

o en forma de tabla

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Tenga en cuenta que el autor utilizó el terminador nulo para las dos primeras entradas de la tabla (¡furtivo!).

Esto está diseñado después de una pantalla de siete segmentos, con 7s como espacios en blanco. Por lo tanto, las entradas en la primera tabla deben definir los segmentos que se iluminan.

La primera mesa

__TIME__es una macro especial definida por el preprocesador. Se expande a una constante de cadena que contiene el tiempo en que se ejecutó el preprocesador, en el formulario "HH:MM:SS". Observe que contiene exactamente 8 caracteres. Tenga en cuenta que 0-9 tiene valores ASCII 48 a 57 y :tiene un valor ASCII 58. La salida es de 64 caracteres por línea, por lo que deja 8 caracteres por carácter de __TIME__.

7 - i/8%8es, por lo tanto, el índice __TIME__que se está emitiendo actualmente ( 7-es necesario porque estamos iterando ihacia abajo). Entonces, tes el carácter de __TIME__ser salida.

atermina igualando lo siguiente en binario, dependiendo de la 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 es un mapa de bits que describe los segmentos que se iluminan en nuestra pantalla de siete segmentos. Como los caracteres son todos ASCII de 7 bits, el bit alto siempre se borra. Por lo tanto, 7en la tabla de segmentos siempre se imprime en blanco. La segunda tabla se ve así con la 7s como espacios en blanco:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

Entonces, por ejemplo, 4es 01101010(conjunto de bits 1, 3, 5 y 6), que se imprime como

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

Para mostrar que realmente entendemos el código, ajustemos un poco la salida con esta tabla:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Esto está codificado como "?;;?==? '::799\x07". Con fines artísticos, agregaremos 64 a algunos de los caracteres (ya que solo se usan los 6 bits bajos, esto no afectará la salida); esto da "?{{?}}?gg::799G"(tenga en cuenta que el octavo carácter no se usa, por lo que podemos convertirlo en lo que queramos). Poniendo nuestra nueva tabla en el 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);}

obtenemos

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

tal como lo esperábamos No es tan sólido como el original, lo que explica por qué el autor eligió usar la tabla que hizo.

nneonneo
fuente
2
@drahnr - Técnicamente es tanto una *(desreferencia) como una +: P
detly
18
@ АртёмЦарионов: Alrededor de 30 minutos, pero he regresado y lo he editado bastante. Utilizo mucho C, y he realizado algunas desofuscaciones de IOCCC por interés personal antes (la última que hice, solo por interés personal, fue este hermoso raytracer ). Si desea preguntar cómo funciona, me complacería hacerlo;)
nneonneo
55
@ АртёмЦарионов: aproximadamente un día IIRC (también cuenta el tiempo dedicado a comprender la geometría del trazador de rayos). Ese programa también es muy inteligente, porque no usa palabras clave .
nneonneo
178
C .. todo el poder del lenguaje ensamblador combinado con la legibilidad del lenguaje ensamblador
wim
66
Para obtener más información en este sentido, consulte "C y otros misterios ofuscados", de Don Libes. Enseña técnicas de C mediante el análisis de las entradas del concurso C ofuscado.
Chris N
102

Formateemos esto para una lectura más fácil:

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

Entonces, ejecutándolo sin argumentos, _ (argc convencionalmente) es 1. main()recursivamente se llamará a sí mismo, pasando el resultado de -(~_)(NO bit a bit negativo _), por lo que realmente irá 448 recursiones (solo condición donde _^448 == 0).

Tomando eso, imprimirá 7 líneas anchas de 64 caracteres (la condición ternaria externa, y 448/64 == 7). Así que reescribamos un poco más limpio:

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

Ahora, 32es decimal para el espacio ASCII. Imprime un espacio o un '!' (33 es '!', De ahí el ' &1' al final). Centrémonos en la burbuja en el medio:

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

Como dijo otro póster, __TIME__es el tiempo de compilación del programa, y ​​es una cadena, por lo que hay algo de aritmética de cadenas en curso, además de aprovechar un subíndice de matriz que es bidireccional: a [b] es lo mismo que b [a] para matrices de caracteres.

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

Esto seleccionará uno de los primeros 8 caracteres en __TIME__. Esto luego se indexa en [">'txiZ^(~z?"-48](0-9 caracteres son 48-57 decimales). Los caracteres de esta cadena deben haber sido elegidos por sus valores ASCII. La misma manipulación de código ASCII de caracteres continúa a través de la expresión, para dar como resultado la impresión de "o"! dependiendo de la ubicación dentro del glifo del personaje.

chmeee
fuente
49

Agregar a las otras soluciones -~xes igual a x+1porque ~xes equivalente a (0xffffffff-x). Esto es igual a (-1-x)en 2s complemento, también lo -~xes -(-1-x) = x+1.

Thomas Song
fuente
55
Interesante. He sabido por un tiempo que ~ x == -x - 1, pero no sabía el razonamiento matemático detrás de esto.
ApproachingDarknessFish
3
Ey, Cole, (-1-x) es lo mismo que (-x-1), ¡no necesitas "arreglarlo"!
Thomas Song
77
La misma razón por la cual si alguien es -1338, entonces NO es 1337.
Andrew Mao
4

Quité la ofuscación de la aritmética del módulo tanto como pude y eliminé la recursión.

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

Expandiéndolo un poco más:

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
fuente