Verschleierter C-Code-Wettbewerb 2006. Bitte erläutern Sie sykes2.c

Wie funktioniert dieses C-Programm?

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

Es wird so kompiliert, wie es ist (getestet am gcc 4.6.3). Es druckt die Zeit beim Kompilieren. Auf meinem System:

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

Quelle: sykes2 - Eine Uhr in einer Zeile , Hinweise des Sykes2-Autors

Einige Hinweise: Standardmäßig keine Kompilierungswarnungen. Zusammen mit -Wallwerden die folgenden Warnungen ausgegeben:

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]

Lassen Sie es uns verschleiern.

Einrücken:

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

Einführung von Variablen, um dieses Durcheinander zu entwirren:

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

Beachten Sie, dass -~i == i+1wegen Zweierkomplement. Deshalb haben wir

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

Beachten Sie nun, dass dies a[b]dasselbe ist wieb[a] , und wenden Sie die -~ == 1+Änderung erneut an:

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

Konvertieren Sie die Rekursion in eine Schleife und schleichen Sie sich etwas vereinfachter:

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

Dies gibt ein Zeichen pro Iteration aus. Jedes 64. Zeichen gibt eine neue Zeile aus. Andernfalls werden zwei Datentabellen verwendet, um herauszufinden, was ausgegeben werden soll, und entweder das Zeichen 32 (ein Leerzeichen) oder das Zeichen 33 (a !) eingefügt. Die erste Tabelle ( ">'txiZ^(~z?") besteht aus 10 Bitmaps, die das Erscheinungsbild jedes Zeichens beschreiben, und die zweite Tabelle ( ";;;====~$::199") wählt das entsprechende Bit aus der Bitmap aus.

Der zweite Tisch

Beginnen wir mit der Untersuchung der zweiten Tabelle int shift = ";;;====~$::199"[(i*2&8) | (i/64)];. i/64ist die Zeilennummer (6 bis 0) und i*2&8ist 8, wenn i4, 5, 6 oder 7 mod 8 ist.

if((i & 2) == 0) shift /= 8; shift = shift % 8wählt entweder die hohe Oktalstelle (für i%8= 0,1,4,5) oder die niedrige Oktalstelle (für i%8= 2,3,6,7) des Tabellenwerts aus. Der Schichttisch sieht am Ende so aus:

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

oder in tabellarischer Form

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Beachten Sie, dass der Autor den Null-Terminator für die ersten beiden Tabelleneinträge verwendet hat (hinterhältig!).

Dies ist nach einer Sieben-Segment-Anzeige mit 7s als Leerzeichen ausgelegt. Die Einträge in der ersten Tabelle müssen also die Segmente definieren, die beleuchtet werden.

Der erste Tisch

__TIME__ist ein spezielles Makro, das vom Präprozessor definiert wird. Es wird in der Form zu einer Zeichenfolgenkonstante erweitert, die den Zeitpunkt enthält, zu dem der Präprozessor ausgeführt wurde "HH:MM:SS". Beachten Sie, dass es genau 8 Zeichen enthält. Beachten Sie, dass 0-9 die ASCII-Werte 48 bis 57 und :den ASCII-Wert 58 haben. Die Ausgabe beträgt 64 Zeichen pro Zeile, sodass 8 Zeichen pro Zeichen von übrig bleiben __TIME__.

7 - i/8%8ist also der Index, der __TIME__gerade ausgegeben wird (der 7-wird benötigt, weil wir nach iunten iterieren ). So tist der Charakter der __TIME__Ausgabe.

aAbhängig von der Eingabe entspricht dies in Binärform dem Folgenden t:

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

Jede Zahl ist eine Bitmap , die die Segmente beschreibt, die in unserer Sieben-Segment-Anzeige leuchten. Da die Zeichen alle 7-Bit-ASCII sind, wird das High-Bit immer gelöscht. Daher wird 7in der Segmenttabelle immer als Leerzeichen gedruckt. Die zweite Tabelle sieht so aus, mit dem 7s als Leerzeichen:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

So zum Beispiel 4ist 01101010(Bits 1, 3, 5 und 6 gesetzt), die als Druck

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

Um zu zeigen, dass wir den Code wirklich verstehen, passen wir die Ausgabe mit dieser Tabelle ein wenig an:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Dies ist codiert als "?;;?==? '::799\x07". Für künstlerische Zwecke fügen wir einigen Zeichen 64 hinzu (da nur die niedrigen 6 Bits verwendet werden, wirkt sich dies nicht auf die Ausgabe aus). Dies gibt "?{{?}}?gg::799G"(beachten Sie, dass das 8. Zeichen nicht verwendet wird, so dass wir es tatsächlich machen können, was wir wollen). Fügen Sie unsere neue Tabelle in den Originalcode ein:

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

wir bekommen

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

genau wie wir erwartet hatten. Es sieht nicht so solide aus wie das Original, was erklärt, warum der Autor die Tabelle verwendet hat, die er gemacht hat.

Formatieren wir dies zum leichteren Lesen:

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

Wenn Sie es also ohne Argumente ausführen, ist _ (konventionell argc) 1. main()ruft sich rekursiv auf und übergibt das Ergebnis von -(~_)(negativ bitweise NICHT von _), so dass es wirklich 448 Rekursionen gibt (nur Bedingung wo _^448 == 0).

Wenn Sie das nehmen, werden 7 64 Zeichen breite Linien gedruckt (die äußere ternäre Bedingung und 448/64 == 7). Schreiben wir es also etwas sauberer um:

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

Jetzt 32ist dezimal für den ASCII-Raum. Es wird entweder ein Leerzeichen oder ein '!' (33 ist '!', Daher das ' &1' am Ende). Konzentrieren wir uns auf den Blob in der Mitte:

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

Wie ein anderes Poster sagte, __TIME__ist dies die Kompilierungszeit für das Programm und eine Zeichenfolge. Es wird also eine Zeichenfolgenarithmetik durchgeführt und ein bidirektionaler Array-Index wird ausgenutzt: a [b] ist dasselbe wie b [a] für Zeichenarrays.

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

Dadurch wird eines der ersten 8 Zeichen in ausgewählt __TIME__. Dies wird dann indiziert [">'txiZ^(~z?"-48](0-9 Zeichen sind 48-57 Dezimalstellen). Die Zeichen in dieser Zeichenfolge müssen für ihre ASCII-Werte ausgewählt worden sein. Dieselbe Zeichen-ASCII-Code-Manipulation wird durch den Ausdruck fortgesetzt, um entweder ein '' oder '!' abhängig von der Position innerhalb der Glyphe des Charakters.

Das Hinzufügen zu den anderen Lösungen -~xist gleich, x+1weil gleich ~xist (0xffffffff-x). Dies entspricht (-1-x)in 2s Ergänzung, so -~xist -(-1-x) = x+1.

Ich habe die Modulo-Arithmetik so weit wie möglich verschleiert und die Rekursion entfernt

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

Erweitern Sie es ein bisschen mehr:

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