Konkurs zaciemnionego kodu C 2006. Proszę wyjaśnić sykes2.c

974

Jak działa ten program C?

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

Kompiluje się tak, jak jest (testowane gcc 4.6.3). Drukuje czas po skompilowaniu. W moim systemie:

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

Źródło: sykes2 - Zegar w jednej linii , wskazówki autora sykes2

Kilka wskazówek: Brak domyślnych ostrzeżeń dotyczących kompilacji. Po kompilacji -Wallemitowane są następujące ostrzeżenia:

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]
staromodny
źródło
6
Debugowanie: dodawanie printf("%d", _);na początku mainwydruków: pastebin.com/HHhXAYdJ
corny
Liczba całkowita, każda nietypowa zmienna ma domyślną wartośćint
drahnr
18
Czy czytałeś podpowiedź? ioccc.org/2006/sykes2/hint.text
nhahtdh
2
Przeczytaj także stackoverflow.com/questions/10321196/…
Xofo
Jeśli uruchomisz go w ten sposób, nastąpi awaria:./a.out $(seq 0 447)
SS Anne

Odpowiedzi:

1819

Usuńmy z tego zaciemnienie.

Wcięcie:

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

Przedstawiamy zmienne, aby rozwiązać ten bałagan:

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

Zauważ, -~i == i+1że z powodu dwóch uzupełnień. Dlatego mamy

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

Teraz zauważ, że a[b]to samob[a] , i zastosuj -~ == 1+zmianę ponownie:

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

Przekształcanie rekurencji w pętlę i skradanie się w nieco większym uproszczeniu:

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

Daje to jeden znak na iterację. Co 64 znak wypisuje nowy wiersz. W przeciwnym razie używa pary tabel danych, aby dowiedzieć się, co wyprowadzić, i umieszcza znak 32 (spację) lub znak 33 (a !). Pierwsza tabela ( ">'txiZ^(~z?") to zestaw 10 map bitowych opisujących wygląd każdego znaku, a druga tabela ( ";;;====~$::199") wybiera odpowiedni bit do wyświetlenia z mapy bitowej.

Drugi stół

Zacznijmy od zbadania drugiej tabeli int shift = ";;;====~$::199"[(i*2&8) | (i/64)];. i/64jest numerem linii (od 6 do 0) i i*2&8wynosi 8 iff ito 4, 5, 6 lub 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8wybiera albo wysoką liczbę i%8ósemkową (dla = 0,1,4,5), albo niską liczbę i%8ósemkową (dla = 2,3,6,7) wartości tabeli. Tabela zmian wygląda następująco:

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

lub w formie tabelarycznej

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Zauważ, że autor użył zerowego terminatora dla pierwszych dwóch wpisów tabeli (podstępne!).

Zostało to zaprojektowane po siedmiosegmentowym wyświetlaczu z 7pustymi literami s. Tak więc wpisy w pierwszej tabeli muszą definiować podświetlane segmenty.

Pierwszy stół

__TIME__to specjalne makro zdefiniowane przez preprocesor. Rozwija się do stałej łańcuchowej zawierającej czas, w którym uruchomiono preprocesor, w formie "HH:MM:SS". Zauważ, że zawiera dokładnie 8 znaków. Zauważ, że 0-9 ma wartości ASCII od 48 do 57 i :ma wartość ASCII 58. Dane wyjściowe to 64 znaki w wierszu, więc pozostawia 8 znaków na znak __TIME__.

7 - i/8%8jest zatem wskaźnikiem tego, __TIME__który jest obecnie generowany ( 7-jest potrzebny, ponieważ iterujemy w idół). Więc tjest charakter __TIME__bycia wyjściem.

akończy się w następujący sposób binarnie, w zależności od danych wejściowych t:

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

Każda liczba jest bitmapą opisującą segmenty podświetlane na naszym siedmiosegmentowym wyświetlaczu. Ponieważ wszystkie znaki są 7-bitowymi kodami ASCII, wysoki bit jest zawsze usuwany. Tak więc 7w tabeli segmentów zawsze drukuje się jako puste. Drugi stół wygląda tak z 7pustymi literami s:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

Na przykład 4jest 01101010(zestaw bitów 1, 3, 5 i 6), który wypisuje jako

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

Aby pokazać, że naprawdę rozumiemy kod, dostosujmy nieco wynik za pomocą tej tabeli:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Jest to zakodowane jako "?;;?==? '::799\x07". Do celów artystycznych dodamy 64 do kilku znaków (ponieważ używane są tylko niskie 6 bitów, nie wpłynie to na wynik); daje to "?{{?}}?gg::799G"(zauważ, że ósma postać jest nieużywana, więc możemy zrobić to, co chcemy). Umieszczenie naszej nowej tabeli w oryginalnym kodzie:

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

dostajemy

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

tak jak się spodziewaliśmy. Nie jest tak solidnie wyglądający jak oryginał, co tłumaczy, dlaczego autor postanowił skorzystać ze stołu, który zrobił.

nneonneo
źródło
2
@drahnr - Technicznie jest to zarówno *(dereferencja), jak i +: P
detly
18
@ АртёмЦарионов: Około 30 minut, ale wracam i trochę je edytuję. Często używam C i wcześniej zrobiłem kilka deobfuskacji IOCCC dla własnego zainteresowania (ostatnia, którą zrobiłem, tylko dla osobistego zainteresowania, to ten piękny raytracer ). Jeśli chcesz zapytać, jak to działa, chętnie bym się zobowiązał;)
nneonneo
5
@ АртёмЦарионов: około dnia IIRC (liczy się również czas poświęcony na zrozumienie geometrii raytracer). Ten program jest również bardzo sprytny, ponieważ nie używa słów kluczowych .
nneonneo
178
C .. cała moc języka asemblera połączona z czytelnością języka asemblera
wim 14'13
6
Aby dowiedzieć się więcej w tym stylu, sprawdź „Obfuscated C and Other Mysteries”, autor: Don Libes. Uczy technik C, analizując zaciemnione wpisy C Konkursu.
Chris N
102

Sformatujmy to dla łatwiejszego czytania:

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

Tak więc, uruchamiając go bez argumentów, _ (argc konwencjonalnie) jest 1 . main()wywoła się rekurencyjnie, przekazując wynik -(~_)(ujemne bitowe NIE _), więc naprawdę przejdzie 448 rekurencji (tylko warunek gdzie _^448 == 0).

Biorąc to pod uwagę, wypisze 7 linii o szerokości 64 znaków (warunek zewnętrznej trójki i 448/64 == 7). Więc przepiszmy to trochę czystsze:

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

Teraz 32jest dziesiętny dla przestrzeni ASCII. Drukuje spację lub „!” (33 to „!”, Stąd „&1 ” na końcu). Skupmy się na kropli na środku:

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

Jak powiedział inny plakat, __TIME__ jest to czas kompilacji programu i jest on ciągiem, więc zachodzi pewna arytmetyka ciągu, a także wykorzystanie dwukierunkowego indeksu tablicowego: a [b] jest takie samo jak b [a] dla tablic postaci.

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

Spowoduje to wybranie jednego z pierwszych 8 znaków w __TIME__. Jest to następnie indeksowane do [">'txiZ^(~z?"-48](0-9 znaków ma 48-57 miejsc dziesiętnych). Znaki w tym ciągu muszą zostać wybrane dla ich wartości ASCII. Ten sam znak manipulacji kodem ASCII jest kontynuowany przez wyrażenie, co powoduje wydrukowanie „” lub „!” w zależności od położenia w glifie postaci.

chmeee
źródło
49

Dodanie do innych rozwiązań -~xjest równe, x+1ponieważ ~xjest równoważne z (0xffffffff-x). Jest to równe (-1-x)uzupełnieniu do 2s, podobnie -~xjest -(-1-x) = x+1.

Thomas Song
źródło
5
Ciekawy. Przez pewien czas wiedziałem, że ~ x == -x - 1, ale nie znałem matematycznego uzasadnienia.
ApproachingDarknessFish
3
Ey, Cole, (-1-x) jest taki sam jak (-x-1), nie musisz go „naprawiać” !!
Thomas Song
7
Ten sam powód, dla którego jeśli ktoś ma -1338, to NIE JEST 1337.
Andrew Mao
4

Usunąłem zaciemnienie arytmetyki modulo, jak mogłem, i usunąłem rekursję

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

Rozwijając to trochę bardziej:

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.
źródło