协慌网

登录 贡献 社区

混淆的 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));
        }
    }
}

每次迭代输出一个字符。每 64 个字符,它输出一个换行符。否则,它使用一对数据表来确定要输出的内容,并放置字符 32(空格)或字符 33(a ! )。第一个表( ">'txiZ^(~z?" )是一组描述每个字符外观的 10 个位图,第二个表( ";;;====~$::199" )选择从位图显示的适当位。

第二个表

让我们从检查第二个表开始, int shift = ";;;====~$::199"[(i*2&8) | (i/64)];i/64是行号(6 到 0), i*2&8是 8 iff i是 4,5,6 或 7 mod 8。

if((i & 2) == 0) shift /= 8; shift = shift % 8选择所述高八进制数字(为i%8 = 0,1,4,5)或低八进制数字(为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

请注意,作者对前两个表条目使用了 null 终止符(偷偷摸摸!)。

这是在七段显示器之后设计的,其中7秒为空白。因此,第一个表中的条目必须定义亮起的段。

第一个表

__TIME__是预处理器定义的特殊宏。它扩展为包含预处理器运行时间的字符串常量,格式为"HH:MM:SS" 。注意它包含正好 8 个字符。请注意,0-9 具有 ASCII 值 48 到 57,并且:具有 ASCII 值 58. 每行输出 64 个字符,因此每个字符__TIME__留下 8 个字符。

7 - i/8%8因此是当前正在输出的__TIME__的索引(需要7-因为我们向下迭代i )。所以, t是输出__TIME__的字符。

a取决于输入t ,以二进制结束等于以下内容:

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

每个数字都是一个位图,用于描述在七段显示中亮起的段。由于字符都是 7 位 ASCII,因此始终清除高位。因此,段表中的7始终作为空白打印。第二个表看起来像这样, 7秒作为空白:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433

因此,例如, 401101010 (位 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);}

我们得到

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

就像我们预期的那样。它不像原版那样结实,这解释了为什么作者选择使用他所做的表。

我们将其格式化以便于阅读:

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

因此,在没有参数的情况下运行它,_(传统的 argc)是1main()将递归调用本身,传递的结果-(~_)负位 NOT 的_ ),所以实际上它会去 448 个递归(唯一的条件,其中_^448 == 0 )。

考虑到这一点,它将打印 7 个 64 字符宽的行(外部三元条件, 448/64 == 7 )。所以让我们把它重写一点清洁:

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

现在, 32位是 ASCII 空间的十进制数。它要么打印一个空格,要么打印 '!' (33 是 '!',因此最后是 ' &1 ')。让我们关注中间的 blob:

-(~(7[__TIME__-argc/8%8][">'txiZ^(~z?"-48]) >>
     (";;;====~$::199"[argc*2&8|argc/64]) / (argc&2?1:8) % 8

正如另一张海报所说, __TIME__是程序的编译时间,并且是一个字符串,因此有一些字符串算法正在进行,并且利用数组下标是双向的:a [b] 与 b [a] 相同] 用于字符数组。

7[__TIME__ - (argc/8)%8]

这将选择__TIME__前 8 个字符之一。然后将其索引到[">'txiZ^(~z?"-48] (0-9 个字符是 48-57 十进制)。必须为其 ASCII 值选择此字符串中的字符。这个相同的字符 ASCII 码操作继续通过表达式,导致打印 '' 或'!',具体取决于字符字形内的位置。

添加到其他解决方案, -~x等于x+1因为~x等于(0xffffffff-x) 。这等于 2s 补码中的(-1-x) ,因此-~x-(-1-x) = x+1