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

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

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

這段C代碼的運(yùn)行過程如下：

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

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

3. 查看下匯編代碼

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

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);這語句可以分解成
因?yàn)檫\(yùn)行到當(dāng)前分支t=0,這其實(shí)是遞歸函數(shù)
6.6) putchar(31[a]),注意31[a]，中括號[]代表C語言的數(shù)組，因?yàn)閍[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])，此時(shí)t應(yīng)滿足-50>t>=-72。源碼遞歸調(diào)用main(-65,_,a+1)直到(_==*a)，然后打印解密后的31[a]字符。用來解密的密鑰如下

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

解密后的原文如下,

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

運(yùn)行程序輸出如下:

改寫t==0時(shí)用遞歸方式輸出字符串為正常調(diào)用函數(shù),并注意到t<-72時(shí)，交換t和_且把a(bǔ)固定為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 ',可以明白對運(yùn)行t>=-50這個(gè)分支遞歸調(diào)用main,此時(shí)t表示'/'的個(gè)數(shù)。

繼續(xù)改寫代碼,將以上三個(gè)遞歸改成函數(shù)調(diào)用。程序從t=1開始運(yùn)行，遞歸調(diào)用t=2,_=2,打印完"On a day A."第一句后main(2,_+1,"%s %d %d\n")遞歸調(diào)用main,將_值加1變成3，運(yùn)行。打印"On b day",因?yàn)閠=2,_=3,遞歸調(diào)用main(t+1,_,a),此時(shí)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." 明白這點(diǎn)后,將t>1的遞歸改成函數(shù)調(diào)用。最后去掉沒用的代碼，結(jié)構(gòu)化改寫原碼，簡單的邏輯打印出結(jié)果。

• 《暗喻幻想：ReFantazio》尤法社群等級提升作用介紹
• 【長城守望】新服開啟！沖榜就送非遺城磚
• 《寶可夢大集結(jié)》路卡利歐技能圖鑒
• 《塞爾達(dá)傳說 智慧的再現(xiàn)》螺旋甜味冰沙怎么制作
• 《仙劍世界》黑蜘蛛森林寶箱開啟方法