[解決済み] 難読化Cコードコンテスト2006。sykes2.cの解説をお願いします。

質問

このCプログラムはどのように動作するのですか？

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

そのままコンパイルされます（テストは gcc 4.6.3 ). コンパイル時に時刻を表示します。私のシステムでは

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

出典 sykes2 - 一列に並んだ時計 , sykes2作者のヒント

いくつかのヒントがあります。デフォルトではコンパイル時の警告はありません。コンパイル時に -Wall の場合、以下のような警告が表示されます。

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]

解決方法は？

難読化を解除しよう。

インデントしています。

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

この混乱を解くために変数を導入する。

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

なお -~i == i+1 というのは、二項補欠だからです。したがって、次のようになります。

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

さて、ここで注目したいのは a[b] と同じです。 b[a] を適用し -~ == 1+ を再度変更します。

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

再帰をループに変換して、もう少し単純化する。

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

これは1回の繰り返しで1文字出力します。64文字ごとに改行を出力します。それ以外の場合は、2つのデータテーブルを使って何を出力するかを決定し、32文字目（スペース）または33文字目 ! ). 最初のテーブル( ">'txiZ^(~z?" ) は、各文字の外観を記述した10枚のビットマップのセットであり、2番目のテーブル ( ";;;====~$::199" )は、ビットマップから適切なビットを選択して表示する。

2つ目のテーブル

まずは2つ目のテーブルから検証してみましょう。 int shift = ";;;====~$::199"[(i*2&8) | (i/64)]; . i/64 は行番号（6～0）であり i*2&8 が8であれば i は4,5,6または7のmod 8です。

if((i & 2) == 0) shift /= 8; shift = shift % 8 は、8進数の上位桁を選択します。 i%8 = 0,1,4,5)または8進数の下位桁( i%8 = 2,3,6,7)のテーブル値です。シフト表は最終的にこのようになります。

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

または表形式で

00005577
11775577
11775577
11665577
22773377
22773377
44443377

作者は、最初の2つのテーブル・エントリにヌル・ターミネータを使っていることに注意してください（ずるい！）。

これは、7セグメントディスプレイを想定したデザインで 7 をブランクとして使用します。したがって、最初のテーブルの項目は、点灯するセグメントを定義する必要があります。

最初のテーブル

__TIME__ はプリプロセッサーで定義された特殊なマクロです。これは、プリプロセッサが実行された時刻を含む文字列定数に展開され、次のような形式になります。 "HH:MM:SS" . ちょうど8文字で構成されていることに注意してください。0-9はASCII値48から57であることに注意。 : はASCII値58です。出力は1行64文字なので、1文字あたり8文字の __TIME__ .

7 - i/8%8 は、このように __TIME__ は、現在出力されている( 7- を反復しているので必要なのです。 i を下方向へ)。だから t は、その文字が __TIME__ が出力されます。

a は、入力に応じて、2進数で次のように等しくなります。 t :

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

各数字は ビットマップ は、7セグメントディスプレイで点灯しているセグメントを記述しています。文字はすべて7ビットASCIIなので、上位ビットは常にクリアされます。したがって 7 は常に空白として印刷されます。2つ目のテーブルは次のようになります。 7 を空白とする。

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

だから、たとえば 4 は 01101010 (ビット1、3、5、6をセット)と印刷されます。

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

このコードを本当に理解していることを示すために、この表で出力を少し調整しましょう。

  00  
11  55
11  55
  66  
22  33
22  33
  44

これは次のようにエンコードされます。 "?;;?==? '::799\x07" . 芸術的な目的のために、いくつかの文字に64を追加します（下位6ビットしか使用しないので、出力には影響しません）。 "?{{?}}?gg::799G" (8文字目は未使用なので、実際には好きなように作ることができます）。新しいテーブルを元のコードに入れる。

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

となる。

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

予想通りです。しかし、原文のようにしっかりした見た目ではないので、作者がなぜこのような表を選んだのかがよくわかる。