12天圣誕節(jié)程序的神奇運行

1988年，一段令人印象深刻且令人敬畏的C代碼，代號為xmas.c，在國際混淆C代碼競賽中獲勝。這個程序甚至比其輸出的“壓縮”類型還要小，代表了文本壓縮標準的全新方式。評委們認為，這個程序像是隨意敲擊鍵盤所得到的。但該程序神奇地打印出12天圣誕節(jié)的歌詞，僅僅幾句話的C代碼！

“圣誕節(jié)的十二天”是一首英國圣誕特別頌歌，于1780年代左右出版，據(jù)說它是在英國女王伊麗莎白一世受迫害期間躲藏起來的天主教徒寫的。它的創(chuàng)作是為了在不引起政府官員注意的情況下幫助教給孩子們關于天主教信仰的文章，使用形象化描述作為工具以幫助孩子們記憶。這首歌代表了在圣誕節(jié)十二天的每一天逐漸給予的盛大禮物。圣誕節(jié)的十二天是從圣誕節(jié)（12月25日）開始的快樂節(jié)日。這也被也稱為圣誕節(jié)節(jié)期（Christmastide and Twelvetide）。

這段C代碼的運行過程如下：

1. 作者源代碼,一些亂字符的感覺,好幾個main~

2. 編譯，運行，看看結(jié)果，嗯，小看這幾個亂亂的代碼了，這是12天圣誕節(jié)(The Twelve Days Of Christmas)的歌詞，好神奇^@^

3. 查看下匯編代碼

4. 源碼斷句，源碼基于？/，/操作進行格式重排.用匯編代碼輔助判斷斷句是否與原碼執(zhí)行一致。為方便理解將二個字符串用宏替換。第一個是明文，第二個字符串是用來加密的密鑰。

5. 用C語言的if-then-else語句解析

6. 源碼分析
6.1) !0為常數(shù)1
6.2) main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a));
這語句為嵌套，可以分解為
6.3) A,B語句中的逗號(,),表示執(zhí)行完A，繼續(xù)執(zhí)行B
6.4) main(-94,-27+t,a) && t==2?A:B這語句可以分解成
6.5) return *a=='/'||main(0,main(-61,*a,strEnc),a+1);這語句可以分解成
因為運行到當前分支t=0,這其實是遞歸函數(shù)
6.6) putchar(31[a]),注意31[a]，中括號[]代表C語言的數(shù)組，因為a[31]等同與*(a+31),31[a]等同與*(31+a),所以31[a]等同于a[31]。

7. 整理代碼
7.1) 根據(jù)if-then-else源碼，整理代碼前面根據(jù)t的偽代碼
if(t>1) Do2();
else if(t<0) DoN();
else if(t>0) Do1(); //滿足t<=1&&t>=0&&t>0的t值只能為1
else Do0(); //以上都不滿足的t只能為0
7.2) 按t從大到小整理偽代碼
if(t>1) Do2();
else if(t==1)Do1();
else if(t==0)Do0();
else DoN();
7.3) 按t從大到小整理偽代碼整理源碼

8. 輸出分析
源碼輸出語句只有一句putchar(31[a])，此時t應滿足-50>t>=-72。源碼遞歸調(diào)用main(-65,_,a+1)直到(_==*a)，然后打印解密后的31[a]字符。用來解密的密鑰如下

所以序號為1字符‘e'對應的原字符’u'序號為32=1+31,序號為2字符'k'的加密前原字符為'w'，序號為33=2+31。注意'!'(序號為0)對應于加密前的換行‘\n'序號31。用這種解密文本

解密后的原文如下,

代碼中字符'/'沒有加密，用來分隔之子字符串，比加first,second。改寫不加密的源碼,為避免換行'\n'中有字符'\'，將換行符用'!'，輸出字符中對'!'當成換行處理。為了更好理解原代碼，將'/'分隔的子字符用一個字母表示。比如"first"用字符'a'代替,"second"用'b'代替，等等。簡化代碼如下

運行程序輸出如下:

改寫t==0時用遞歸方式輸出字符串為正常調(diào)用函數(shù),并注意到t<-72時，交換t和_且把a固定為strDeText遞歸調(diào)用main.代碼比較清晰了，可以注意到int m1=main(0,-86,strDeText)輸出"On ",int m2=main(1-_,-87,strDeText)輸出'a'或者'b'或者’c'等等，main(-13,-79,strDeText)輸出' day ',可以明白對運行t>=-50這個分支遞歸調(diào)用main,此時t表示'/'的個數(shù)。

繼續(xù)改寫代碼,將以上三個遞歸改成函數(shù)調(diào)用。程序從t=1開始運行，遞歸調(diào)用t=2,_=2,打印完"On a day A."第一句后main(2,_+1,"%s %d %d\n")遞歸調(diào)用main,將_值加1變成3，運行。打印"On b day",因為t=2,_=3,遞歸調(diào)用main(t+1,_,a),此時t=3,_=3，返回后調(diào)用funOut(-27+t,-94,strDeText)打印出"B,A."，繼續(xù)調(diào)用main(2,_+1,"%s %d %d\n")將_值加1變成4,...,直到_=13完成輸出"L,K,J,I,H,G,F,E,D,C,B,A." 明白這點后,將t>1的遞歸改成函數(shù)調(diào)用。最后去掉沒用的代碼，結(jié)構(gòu)化改寫原碼，簡單的邏輯打印出結(jié)果。

• 異色邊緣龍局北辰卡組詳解
• 《怪化貓》系列第二章《火鼠》近日公開諸多新情報
• steam特賣頁面出現(xiàn)神秘粉發(fā)女孩 引發(fā)網(wǎng)友熱烈討論
• 大雪節(jié)氣活動：桃源深處有人家雪盛冬藏
• 游俠晚報：《絕地潛兵2》口碑上升 Fami通一周評分