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

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]

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ł.

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.

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.

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