一段代码的分析

xiaoee posted @ 2011年9月20日 22:20 in Coding My Mind with tags 思考 情书 算法 编程 代码 分析 , 4671 阅读

M67的那篇文章在这:http://www.matrix67.com/blog/archives/1598
很久之前就转到自己博客上来了,在这里,当时也没细看,当然也没看明白。
今天仔细分析了下,终于明白怎么回事了。
先用字符串“I love you to death! You are the cutest and sweetest girl I've ever met.”生成程序为:

     #include      <stdio.h>
   main(t ,_,a)  char*a;{return
 t<1?main(*a,a[-t],"=a-1kj3gnm:q\
ebh_cf*<r.d>i^+?,()[?qzyrjuvcdefg\
h,!kbpolwxs'.t main(")&&a[-t]&&main
(t-1,_,a):t/2?_==*a?putchar(32[a])
  :_%115<36||main(t,_,a+1):main(
    0,t,")?r<g:?1<3?+<#?#m:}(\
      w+b_?1<}3?tt(yk:?+|b:\
        ?n3+:>+?([m?>.::+\
          :>+?e)kr?)ig{\
            :?y:~g:k?\
              ,:+^")
                ;}

是一个很漂亮的心形,用gcc编译执行输出:

i love you to death! you are the cutest and sweetest girl i've ever met.#

上面的代码很漂亮,但不是很容易看明白,我们把程序代码简单整理一下:

main(int t, int _, char *a)
{
    return t<1 ? main(*a,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(")&&a[-t]&&main(t-1,_,a):
                 t/2 ? _==*a ? putchar(32[a]): _%115<36||main(t,_,a+1):
                       main(0,t,")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#")
        ;
}
 

最开始的程序用了c的old style声明函数,没有类型的参数默认为整型。
分析程序的执行过程:
开始执行:t=1,_和a不确定,因为t为参数个数所以恒等于1。
因此接下来会执行第二个条件语句的后面的分支:

main(0,t,")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#");

递归调用之后:

t=0,
_=1,
a=")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#"

 

由于t<1,所以会执行:

main(*a,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(")&&a[-t]&&main(t-1,0,a)

 

首先是递归调用:

t=')'=41,
_=')',
a="=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main("

由于t>0且t/2!=0所以会执行:

_==*a ? putchar(32[a]): _%115<36||main(t,_,a+1);
 

如果_!=*a,则递归调用,同时t和_不变,a加1,直到_等于*a为止,然后输出a之后的第32个字符。
接着递归一层层返回,到最开始执行:

main(*a,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(")
 

的结束,因为没有指定返回类型,从运行结果上看每次都返回真,于之后就执行:

a[-t]&&main(t-1,0,a)
 

首先判断a[-t]是否为0,否则递归调用main(t-1,0,a),也就是转到下一个字符。
很明显这个字符串就是一个密码表。我们注意到在生成程序的时候,只有最后那个字符串在变,也就是生成的密码,生成的程序实际上就是用来解密的。

为了更清楚的理解过程,我们再对程序做进一步的变形:
我们发现

main(0,0,")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#");

这句只会执行一次,就是开始进入的时候,因为之后之后t要么<=0,要么>1。

main(int t, int _, char *a)
{
    if (t==1) {//start
       main(0,t,")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#");
    }
    if (t<=0) {
        main(*a,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(");
        if (a[-t])
            main(t-1,_,a);
    }else {
        if (_==*a) {
            putchar(a[32]);
        }else if(_%115>=36) {
            main(t, _, a+1);
        }
    }
}
 

由于第一个递归只调用一次,所以可以单独拿出来,再又发现_参数只在

main(*a,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(");

这一句中有实际意义,其它地方可以随意指定。
于是再把代码变形:

void
show(int t, int _, char *a)
{
    if (t<=0) {
        show(1,a[-t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(");
        if (a[-t]) {
            show(t-1,_,a);
        }

    }else {
        if (_==*a) {
            putchar(a[32]);
        }else if(_%115>=36) {
            show(t, _, a+1);
        }
    }
}

int
main(int argc, char *argv[])
{
    show(0,0,")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#");
    return 0;
}

我们最后再把递归也消除了:

void
disp(int _, char *a)
{
    char *p=a;
    while (_!=*p) {
        if (_%115<36)return;
        p++;
    }
    putchar(p[32]);
}

void
show2(char *a)
{
    int t=0;
    while (a[t]) {
        disp(a[t],"=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main(");
        t++;
    }
}

int
main(int argc, char *argv[])
{
    show2(")?r<g:?1{<3?+<?vm:(+b_?1<v3?(k:?!+uvb:?nt3+:>{+?([m?>.::+:>+#?e)kr?)ig:?:!g:k?,:+^z#");
    return 0;
}
 

到此程序流程就一清二楚了,最后再来看看这程序怎么生成的,前面已经说过,只有密码是在变的,所以生成程序中主要就是生成密码。

这是生成程序的js代码:http://www.matrix67.com/data/scripts/ioccc.js

里面定义了三个字符数组:

var m=new Array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ',',','.','\'','!','?');
var c=new Array('(','f','n','m',':','q','e','b',')','j','c','r',',','[','<','*','a','k','>','+','3','g','.','d','1','-','?','h','^','i','_','=');
var r=new Array("s","t","u","v","w","x","y","z","{","|","}","~","!","#");
 

其中mc大小为32m是输入字符串中可以出现的,其它被忽略。m可以说是明文字符,c就是与之对应的密文。r中的字符可以出现在密文中,但是没有与之对应的明文,这就是为什么生成的程序中有个_%115<36的判断,就是忽略这部分字符。程序生成程序其实就是按顺序生成密文,其中随机插入一些r中的干扰字符。

C是根据m和生成程序中的

“=a-1kj3gnm:qebh_cf*<r.d>i^+?,()[?qzyrjuvcdefgh,!kbpolwxs'.t main("

这个密码表字符串推导出来的,从第一个=开始数,第32个就是与之对应的m中字符,依次数32个就完成了c字符串。这样看来,其实密码表和密文字符串都是可以动态生成的。

结束。。

Avatar_small
llhuii 说:
2011年10月06日 06:24

分析得不错。
看了40分钟,终于明白了。:)
ps:输出的结尾怎么有个#号?

Avatar_small
xiaoee 说:
2011年10月10日 19:11

'#'是putchar()输出到终端的。原因我也不太清楚。。

Avatar_small
xiaoee 说:
2011年10月11日 00:59

错了,这个是shell的问题,有些shell会强制换行,如果最后没有输出换行的话,会强制换行,然后显示高亮的#号。
比如bash配置不强制换行的话,就不会显示#,或者你最后输出一个'\n'的话,也不会显示#。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter