Verschleierter C-Code-Wettbewerb 2006. Bitte erklären Sie sykes2.c

Question 1

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 auf gcc 4.6.3). Es gibt die Uhrzeit beim Kompilieren aus. Auf meinem System:

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

Quelle: sykes2 – Eine Uhr in einer Zeile, sykes2 Autorenhinweise

Einige Hinweise: Keine Kompilierungswarnungen standardmäßig. Kompiliert mit -Wallwerden folgende 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]

Question 2

Lassen Sie es uns entschlüsseln.

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+1 wegen Zweierkomplement. Daher 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));
    }
}

Nun, beachten Sie das a[b] ist das gleiche wie b[a]und wenden Sie die an -~ == 1+ wieder ändern:

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

Die Rekursion in eine Schleife umwandeln und etwas mehr Vereinfachung einschleichen:

// 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 es einen Zeilenumbruch aus. Andernfalls verwendet es ein Paar Datentabellen, um herauszufinden, was ausgegeben werden soll, und fügt entweder das Zeichen 32 (ein Leerzeichen) oder das Zeichen 33 (ein !). Der erste Tisch (">'txiZ^(~z?") ist ein Satz von 10 Bitmaps, die das Aussehen jedes Zeichens beschreiben, und die zweite Tabelle (";;;====~$::199") wählt das entsprechende anzuzeigende 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/64 ist die Zeilennummer (6 bis 0) und i*2&8 ist 8 iff i ist 4, 5, 6 oder 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8 wählt entweder die hohe Oktalziffer (z i%8 = 0,1,4,5) oder die niedrige Oktalziffer (z i%8 = 2,3,6,7) des Tabellenwertes. Die Schichttabelle 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

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

Diese ist einer Sieben-Segment-Anzeige nachempfunden, mit 7s als Leerzeichen. Die Einträge in der ersten Tabelle müssen also die Segmente definieren, die aufleuchten.

Der erste Tisch

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

7 - i/8%8 ist somit der Index von __TIME__ die derzeit ausgegeben wird (die 7- wird benötigt, weil wir iterieren i nach unten). So, t ist der Charakter von __TIME__ ausgegeben werden.

a ergibt abhängig von der Eingabe binär Folgendes t:

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

Also zum Beispiel 4 ist 01101010 (Bits 1, 3, 5 und 6 gesetzt), was gedruckt wird als

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

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

Dies ist codiert als "?;;?==? '::799\x07". Aus künstlerischen Gründen fügen wir 64 zu einigen Zeichen hinzu (da nur die niedrigen 6 Bits verwendet werden, hat dies keinen Einfluss auf die Ausgabe); das gibt "?{{?}}?gg::799G" (Beachten Sie, dass das 8. Zeichen nicht verwendet wird, sodass wir es tatsächlich machen können, was wir wollen). Setzen Sie unsere neue Tabelle in den ursprünglichen Code:

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

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

so wie wir es erwartet haben. Es sieht nicht so solide aus wie das Original, was erklärt, warum der Autor sich für die von ihm gewählte Tabelle entschieden hat.

Question 3

Lassen Sie uns dies zum leichteren Lesen formatieren:

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() wird sich rekursiv selbst aufrufen und das Ergebnis von übergeben -(~_) (negativ bitweise NICHT von _), also werden wirklich 448 Rekursionen durchgeführt (nur Bedingung, wo _^448 == 0).

Wenn man das nimmt, werden 7 Zeilen mit einer Breite von 64 Zeichen 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, 32 ist dezimal für ASCII-Leerzeichen. Es druckt 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 anderer Poster sagte, __TIME__ ist die Kompilierzeit für das Programm und ist ein String, also gibt es einige String-Arithmetik, sowie die Nutzung eines Array-Index, der bidirektional ist: a[b] ist das gleiche wie b[a] für Zeichenfelder.

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

Dadurch wird eines der ersten 8 Zeichen in ausgewählt __TIME__. Diese wird dann indiziert [">'txiZ^(~z?"-48] (0-9 Zeichen sind 48-57 Dezimalstellen). Die Zeichen in dieser Zeichenfolge müssen aufgrund ihrer 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.

Question 4

Ergänzend zu den anderen Lösungen -~x ist gleich x+1 Weil ~x ist äquivalent zu (0xffffffff-x). Dies ist gleich (-1-x) im Zweierkomplement, also -~x ist -(-1-x) = x+1.

Question 5

Ich habe die Modulo-Arithmetik so weit wie möglich entschleiert 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');
}

Etwas weiter ausbauen:

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