Pertanyaan Kontes Kode C Terkelusi 2006. Tolong jelaskan sykes2.c


Bagaimana cara kerja program C ini?

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

Ini mengkompilasi seperti apa adanya (diuji pada gcc 4.6.3). Ini mencetak waktu ketika dikompilasi. Di sistem saya:

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

Sumber: sykes2 - Jam dalam satu baris, petunjuk sykes2 penulis

Beberapa petunjuk: Tidak ada peringatan kompilasi per default. Dikompilasi dengan -Wall, peringatan berikut ini dipancarkan:

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]

917
2018-03-13 18:22


asal


Jawaban:


Mari de-mengaburkan itu.

Indentasi:

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

Memperkenalkan variabel untuk menguraikan kekacauan ini:

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

Perhatikan itu -~i == i+1 karena berpasangan. Karena itu, kami punya

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

Sekarang, perhatikan itu a[b] sama dengan b[a], dan terapkan -~ == 1+ ubah lagi:

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

Mengubah rekursi ke loop dan menyelinap dengan sedikit lebih banyak penyederhanaan:

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

Ini menghasilkan satu karakter per iterasi. Setiap 64 karakter, ini menghasilkan baris baru. Jika tidak, ia menggunakan sepasang tabel data untuk mencari tahu apa yang harus dikeluarkan, dan menempatkan salah satu karakter 32 (spasi) atau karakter 33 (a !). Tabel pertama (">'txiZ^(~z?") adalah sekumpulan 10 bitmap yang menjelaskan tampilan setiap karakter, dan tabel kedua (";;;====~$::199") memilih bit yang sesuai untuk ditampilkan dari bitmap.

Meja kedua

Mari kita mulai dengan memeriksa tabel kedua, int shift = ";;;====~$::199"[(i*2&8) | (i/64)];. i/64 adalah nomor baris (6 hingga 0) dan i*2&8 adalah 8 iff i adalah 4, 5, 6 atau 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8 memilih digit oktal tinggi (untuk i%8 = 0,1,4,5) atau digit oktal rendah (untuk i%8 = 2,3,6,7) dari nilai tabel. Meja shift berakhir seperti ini:

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

atau dalam bentuk tabel

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Perhatikan bahwa penulis menggunakan terminator null untuk dua entri tabel pertama (licik!).

Ini dirancang setelah tampilan tujuh segmen, dengan 7sebagai kosong. Jadi, entri di tabel pertama harus menentukan segmen yang menyala.

Meja pertama

__TIME__ adalah makro khusus yang ditentukan oleh preprocessor. Ini memperluas ke string konstan yang berisi waktu di mana preprocessor dijalankan, dalam bentuk "HH:MM:SS". Amati bahwa itu berisi tepat 8 karakter. Perhatikan bahwa 0-9 memiliki nilai ASCII 48 hingga 57 dan : memiliki nilai ASCII 58. Outputnya adalah 64 karakter per baris, sehingga meninggalkan 8 karakter per karakter __TIME__.

7 - i/8%8 demikian indeks __TIME__ yang saat ini sedang keluaran (the 7- diperlukan karena kami sedang melakukan iterasi i ke bawah). Begitu, t adalah karakter __TIME__ menjadi output.

a berakhir sama dengan yang berikut dalam biner, tergantung pada input t:

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

Setiap angka adalah a bitmap menggambarkan segmen yang menyala dalam tampilan tujuh segmen kami. Karena semua karakter adalah 7-bit ASCII, bit yang tinggi selalu dihapus. Demikian, 7 di tabel segmen selalu mencetak sebagai kosong. Tabel kedua terlihat seperti ini dengan 7sebagai kosong:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

Jadi, misalnya, 4 aku s 01101010 (bit 1, 3, 5, dan 6 set), yang dicetak sebagai

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

Untuk menunjukkan bahwa kami benar-benar memahami kode, mari sesuaikan sedikit hasilnya dengan tabel ini:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Ini dikodekan sebagai "?;;?==? '::799\x07". Untuk tujuan artistik, kita akan menambahkan 64 ke beberapa karakter (karena hanya 6 bit rendah yang digunakan, ini tidak akan mempengaruhi output); ini memberi "?{{?}}?gg::799G" (perhatikan bahwa karakter ke-8 tidak digunakan, jadi kita benar-benar dapat membuatnya apa pun yang kita inginkan). Letakkan tabel baru kami di kode asli:

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

kita mendapatkan

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

seperti yang kami harapkan. Ini tidak tampak solid seperti aslinya, yang menjelaskan mengapa penulis memilih untuk menggunakan meja yang dia lakukan.


1768
2018-03-13 19:46



Mari kita format ini agar lebih mudah dibaca:

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

Jadi, menjalankannya tanpa argumen, _ (argc secara konvensional) adalah 1. main() akan secara rekursif menyebut dirinya, melewati hasil -(~_) (bitwise negatif TIDAK _), jadi benar-benar akan pergi 448 rekursi (Hanya kondisi di mana _^448 == 0).

Mengambil itu, itu akan mencetak 7 64-karakter garis lebar (kondisi terner luar, dan 448/64 == 7). Jadi mari kita tulis ulang sedikit lebih bersih:

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

Sekarang, 32 adalah desimal untuk ruang ASCII. Itu mencetak ruang atau '!' (33 adalah '!', Maka itu '&1' pada akhirnya). Mari fokus pada gumpalan di tengah:

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

Seperti yang dikatakan poster lain, __TIME__ adalah waktu kompilasi untuk program, dan merupakan string, jadi ada beberapa string aritmatika yang terjadi, serta mengambil keuntungan dari sebuah array subscript yang bidirectional: a [b] adalah sama dengan b [a] untuk array karakter.

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

Ini akan memilih salah satu dari 8 karakter pertama di __TIME__. Ini kemudian diindeks ke dalam [">'txiZ^(~z?"-48] (0-9 karakter adalah 48-57 desimal). Karakter dalam string ini harus dipilih untuk nilai ASCII mereka. Manipulasi kode ASCII karakter yang sama ini terus berlanjut melalui ekspresi, untuk menghasilkan cetakan baik '' atau '!' tergantung pada lokasi di dalam mesin terbang karakter.


97
2018-03-13 21:11



Menambah solusi lain, -~x adalah sama dengan x+1 karena ~x setara dengan (0xffffffff-x). Ini sama dengan (-1-x) dalam 2s pelengkap, jadi -~x aku s -(-1-x) = x+1.


46
2018-03-14 23:54



Saya de-mengaburkan aritmatika modulo sebanyak yang saya bisa dan menghapus reccursion tersebut

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

Memperluasnya sedikit lebih banyak:

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

3
2018-04-21 14:48