12天圣诞节程序的神奇运行

1988年，一段令人印象深刻且令人敬畏的C代码，代号为xmas.c，在国际混淆C代码竞赛中获胜。这个程序甚至比其输出的“压缩”类型还要小，代表了文本压缩标准的全新方式。评委们认为，这个程序像是随意敲击键盘所得到的。但该程序神奇地打印出12天圣诞节的歌词，仅仅几句话的C代码！

“圣诞节的十二天”是一首英国圣诞特别颂歌，于1780年代左右出版，据说它是在英国女王伊丽莎白一世受迫害期间躲藏起来的天主教徒写的。它的创作是为了在不引起政府官员注意的情况下帮助教给孩子们关于天主教信仰的文章，使用形象化描述作为工具以帮助孩子们记忆。这首歌代表了在圣诞节十二天的每一天逐渐给予的盛大礼物。圣诞节的十二天是从圣诞节（12月25日）开始的快乐节日。这也被也称为圣诞节节期（Christmastide and Twelvetide）。

这段C代码的运行过程如下：

1. 作者源代码,一些乱字符的感觉,好几个main~

2. 编译，运行，看看结果，嗯，小看这几个乱乱的代码了，这是12天圣诞节(The Twelve Days Of Christmas)的歌词，好神奇^@^

3. 查看下汇编代码

4. 源码断句，源码基于？/，/操作进行格式重排.用汇编代码辅助判断断句是否与原码执行一致。为方便理解将二个字符串用宏替换。第一个是明文，第二个字符串是用来加密的密钥。

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

6. 源码分析
6.1) !0为常数1
6.2) main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a));
这语句为嵌套，可以分解为
6.3) A,B语句中的逗号(,),表示执行完A，继续执行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,这其实是递归函数
6.6) putchar(31[a]),注意31[a]，中括号[]代表C语言的数组，因为a[31]等同与*(a+31),31[a]等同与*(31+a),所以31[a]等同于a[31]。

7. 整理代码
7.1) 根据if-then-else源码，整理代码前面根据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。源码递归调用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时用递归方式输出字符串为正常调用函数,并注意到t<-72时，交换t和_且把a固定为strDeText递归调用main.代码比较清晰了，可以注意到int m1=main(0,-86,strDeText)输出"On ",int m2=main(1-_,-87,strDeText)输出'a'或者'b'或者’c'等等，main(-13,-79,strDeText)输出' day ',可以明白对运行t>=-50这个分支递归调用main,此时t表示'/'的个数。

继续改写代码,将以上三个递归改成函数调用。程序从t=1开始运行，递归调用t=2,_=2,打印完"On a day A."第一句后main(2,_+1,"%s %d %d\n")递归调用main,将_值加1变成3，运行。打印"On b day",因为t=2,_=3,递归调用main(t+1,_,a),此时t=3,_=3，返回后调用funOut(-27+t,-94,strDeText)打印出"B,A."，继续调用main(2,_+1,"%s %d %d\n")将_值加1变成4,...,直到_=13完成输出"L,K,J,I,H,G,F,E,D,C,B,A." 明白这点后,将t>1的递归改成函数调用。最后去掉没用的代码，结构化改写原码，简单的逻辑打印出结果。