IOCCC-科学计算器代码解析

本文是对IOCCC赛事中来自Qiming Hou老师的科学计算器的简单代码解析。该代码来自赛事IOCCC 20th，Hou老师获得奖项Best self documenting。

事先声明

由于本人能力欠缺，本代码仍在继续解析中，因此如果分析出现了偏差，请及时联系本人更正。

代码概览

源代码如下。

#include <stdio.h>
#include <math.h>
#define clear 1;if(c>=11){c=0;sscanf(_,"%lf%c",&r,&c);while(*++_-c);}\
  else if(argc>=4&&!main(4-(*_++=='('),argv))_++;g:c+=
#define puts(d,e) return 0;}{double a;int b;char c=(argc<4?d)&15;\
  b=(*_%__LINE__+7)%9*(3*e>>c&1);c+=
#define I(d) (r);if(argc<4&&*#d==*_){a=r;r=usage?r*a:r+a;goto g;}c=c
#define return if(argc==2)printf("%f\n",r);return argc>=4+
#define usage main(4-__LINE__/26,argv)
#define calculator *_*(int)
#define l (r);r=--b?r:
#define _ argv[1]
#define x

double r;
int main(int argc,char** argv){
  if(argc<2){
    puts(
      usage: calculator 11/26+222/31
      +~~~~~~~~~~~~~~~~~~~~~~~~calculator-\
      !                          7.584,367 )
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! clear ! 0 ||l   -x  l   tan  I (/) |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 1 | 2 | 3 ||l  1/x  l   cos  I (*) |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 4 | 5 | 6 ||l  exp  l  sqrt  I (+) |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 7 | 8 | 9 ||l  sin  l   log  I (-) |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(0
    );
  }
  return 0;
}

可以看到，这里在main函数中绘制了一个十分形象的计算器，而且它是可以编译通过的！这么神奇的现象是由前面的宏定义实现的。抛开这些不谈，我们先来看一下运行结果。

赛事官方提供了如下的makefile。

#!/usr/bin/env make
#
# 2011 makefile
#
# Copyright (C) 2011, Landon Curt Noll, Simon Cooper, and Leonid A. Broukhis.
#
# Creative Commons Attribution-ShareAlike 3.0 Unported License.
# See: http://creativecommons.org/licenses/by-sa/3.0/


################
# tool locations
################
#
SHELL= /bin/bash
CP= cp
CPP= cpp
GUNZIP= gunzip
LD= ld
MAKE= make
RM= rm
SED= sed
TAR= tar
TRUE= true

# optimization
#
# Most compiles will safely use -O2.  Some can use only -O1 or -O.
# A few compilers have broken optimizers or this entry make break
# under those buggy optimizers and thus you may not want anything.
#
OPT= -O2

# bitness
#
# Some entries require 32-bitness,
# other entries require 64-bitess.
# By default we assume nothing.
#
ARCH=

# default flags for ANSI C compilation
#
CFLAGS= -Wall -W -ansi -pedantic ${ARCH} ${OPT} -lm

# ANSI compiler
#
# Set CC to the name of your ANSI compiler.
#
CC= cc


##############################
# Special flags for this entry
##############################
#
ENTRY= hou
DATA=


#################
# build the entry
#################
#
all: ${ENTRY} ${DATA}
	@${TRUE}

${ENTRY}: ${ENTRY}.c
	${CC} ${CFLAGS} ${ENTRY}.c -o ${ENTRY}

# alternative executable
#
alt:
	@${TRUE}


###############
# utility rules
###############
#
everything: all alt

clean:
	${RM} -f ${ENTRY}.o

clobber: clean
	${RM} -f ${ENTRY}

nuke: clobber
	@echo gnab gib!

install:
	@echo "Surely you're joking Mr. Feynman!"

# backwards compatibility
#
build: all


##################
# 133t hacker rulz
##################
#
love:
	@echo 'not war?'

haste:
	$(MAKE) waste

waste:
	@echo 'waste'

easter_egg:
	@echo you expected to mis-understand this $${RANDOM} magic
	@echo chongo '<was here>' "/\\oo/\\"
	@echo Readers shall not be disallowed from being unable to partly misunderstand this final echo.
	@${TRUE}

简单阅读可以知道，直接运行make得到的结果和gcc hou.c -o hou类似，仅仅是编译选项有所不同。

对于得到的二进制文件hou，有如下运行结果。

$ ./hou 11/26+222/31
7.584367
$ ./hou 'log((21701-19937)-(23209-21701))/log(2)'
8.000000
$ ./hou 'sin(1.5708)+0.04321+log(sqrt(exp(1*1*1)))+(1+2*3)-0.4-0.6+(4+6)*(2-1+2*3)-tan(0.785398)+2*10/3*6*sqrt(16/2/2)*10+10000-1000'
9876.543210

这里体现出了题目科学计算器的功能了，调用这个看起来很像计算器的程序可以进行科学计算。它是如何实现的呢？

宏展开

第一步是要抛开宏的伪装，看清楚代码的真实逻辑。

使用如下指令可以获得宏展开后的代码结果。

1	`$ gcc -E hou.c > hou-expanded.c`

对新的文件进行部分整理，得到如下结果。

#include <stdio.h>
#include <math.h>
double r;
int main(int argc,char** argv){
  if(argc<2){
    if(argc==2)printf("%f\n",r);return argc>=4+ 0;}{double a;int b;char c=(argc<4?main(4-19/26,argv): *argv[1]*(int) 11/26+222/31 +~~~~~~~~~~~~~~~~~~~~~~~~*argv[1]*(int)- ! 7.584)&15; b=(*argv[1]%21 +7)%9*(3*367>>c&1);c+=
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 1;if(c>=11){c=0;sscanf(argv[1],"%lf%c",&r,&c);while(*++argv[1]-c);} else if(argc>=4&&!main(4-(*argv[1]++=='('),argv))argv[1]++;g:c+= ! 0 ||(r);r=--b?r: - (r);r=--b?r: tan (r);if(argc<4&&*"/"==*argv[1]){a=r;r=main(4-23/26,argv)?r*a:r+a;goto g;}c=c |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 1 | 2 | 3 ||(r);r=--b?r: 1/ (r);r=--b?r: cos (r);if(argc<4&&*"*"==*argv[1]){a=r;r=main(4-25/26,argv)?r*a:r+a;goto g;}c=c |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 4 | 5 | 6 ||(r);r=--b?r: exp (r);r=--b?r: sqrt (r);if(argc<4&&*"+"==*argv[1]){a=r;r=main(4-27/26,argv)?r*a:r+a;goto g;}c=c |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
      ! 7 | 8 | 9 ||(r);r=--b?r: sin (r);r=--b?r: log (r);if(argc<4&&*"-"==*argv[1]){a=r;r=main(4-29/26,argv)?r*a:r+a;goto g;}c=c |
      +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(0
    );
  }
  if(argc==2)printf("%f\n",r);return argc>=4+ 0;
}

直接编译这个文件依然可以得到想要的结果。

然后注意如下事实：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~的结果是0。这需要在类型转换下才能成立，否则会编译报错。
针对argc的大小进行分析，去除不需要的代码。

我们可以将代码整理成为

#include <stdio.h>
#include <math.h>
double r;
int depth = 0;
int main(int argc,char** argv){
    ++depth;
    if(argc<2){ --depth; return 0; }
    if (argc <= 3)
    {
        double a=0;int b;
        for(int jj = 0; jj < depth; ++jj) putchar(' ');
        printf("Enter with argc=%d, argv[1]=%s\n", argc, argv[1]);
        char c=1;
        b=0;
        for(int jj = 0; jj < depth; ++jj) putchar(' ');
        printf("Now a=%f, b=%d, c=%d, r=%f\n" ,a, b, c, r);
        main(4, argv);
    g1:c+= 1;
        if(*"/"==*argv[1]){
            a=r;
            main(4, argv);
            r=r*a;
            goto g1;
        }
        if(*"*"==*argv[1]){
            a=r;
            main(4, argv);
            r=r*a;
            goto g1;
        }
        if(*"+"==*argv[1]){
            a=r;
            main(3, argv);
            r=r+a;
            goto g1;
        }
        if(*"-"==*argv[1]){
            a=r;
            main(3, argv);
            r=r+a;
            goto g1;
        }
    if(argc==2)printf("%f\n",r);
    printf("End with a=%f, b=%d, c=%d, r=%f, ret=%d\n" ,a, b, c, r, 0);
    --depth;
    return 0;
    }

    if (argc == 4)
    {
        double a=0;int b;
        for(int jj = 0; jj < depth; ++jj) putchar(' ');
        printf("Enter with argc=%d, argv[1]=%s\n", argc, argv[1]);
        char c=(*argv[1]*(int) 11/26+7)&15; // number:>=11, else < 11
        b=(*argv[1]%21 +7)%9*(3*367>>c&1); // number:0, else, hash
        for(int jj = 0; jj < depth; ++jj) putchar(' ');
        printf("Now a=%f, b=%d, c=%d, r=%f\n" ,a, b, c, r);
        if(c>=11){ // number
            c=0;
            sscanf(argv[1],"%lf%c",&r,&c); // read number and operator, x+
            while(*++argv[1]-c);
        } else if(!main(4-(*argv[1]++=='('),argv)) // is operator or (
            argv[1]++;
        r=--b?r: - (r);
        r=--b?r: tan (r);
        
        r=--b?r: 1/ (r);
        r=--b?r: cos (r);
        
        r=--b?r: exp (r);
        r=--b?r: sqrt (r);
        
        r=--b?r: sin (r);
        r=--b?r: log (r);
        
    if(argc==2)printf("%f\n",r);
    printf("End with a=%f, b=%d, c=%d, r=%f, ret=%d\n" ,a, b, c, r, 1);
    --depth;
    return 1;
    }
}

基本介绍

这里添加了相当数量的调试代码。总之这时候代码的主要逻辑就清晰明了了。可以看出，这里的表达式解析算法基本上符合表达式的BNF形式。

作者将表达式分为两类，分别代表了exp_additive加法表达式和exp_multiplicative乘法表达式。然后利用了如下关系。

1 2	`exp_additive -> exp_multiplicative ( "+"\|"-" ) exp_multiplicative exp_multiplicative -> exp_cast ( "*"\|"/"\|"%" ) exp_cast`

其中exp_cast为类型转换表达式。本计算器不支持这一功能，可以认为是单纯的数值。

在这一基础上，作者还将exp_multiplicative添加了一元运算符的支持。这体现在main(4, argv)函数中对于r的一系列函数操作。使得计算器和编译器不同，可以跳过一元函数调用直接解析表达式。

详细分析

`argc`是什么

argc是用来判断当前处理表达式的类型的标志量。

`argc`	含义
2	当前处理`exp_additive`，处理完成后结果保存在`r`，并输出
3	当前处理`exp_additive`，处理完成后结果保存在`r`
4	当前处理`exp_multiplicative`，处理完成后结果保存在`r`

表达式解析的基本结构

参阅相关材料，并且对照本文代码，得到如下的解析结构。

void exp_additive(){
       char op;
       exp_multiplicative();
       while(
           (op = OPERATOR( '+' )) ||
            (op = OPERATOR( '-' )) ){
            get_token();
            exp_multiplicative();
            ...
       }
   }

    void exp_multiplicative(){
        char op;
        exp_cast();
        while(
            (op = OPERATOR( '*' )) ||
            (op = OPERATOR( '/' )) ||
            (op = OPERATOR( '%' )) ){
            get_token();
            exp_cast();
            ...
        }
    }

本文代码基本符合。

标志量a,b,c的含义

标志量a主要作用是暂存全局运算结果r，在计算得到新的r之后需要和先前的值合并，得到正确的计算值。比如

if(*"/"==*argv[1]){
    a=r;
    main(4, argv); // 更新r的值，为新表达式的值。
    r=r*a;          // 因为使用了*/，所以需要进行乘法运算。
    // 没有使用除法的原因是，在main(4,argv)中将/解析成了一个一元运算符。
    goto g1;
}

b,c的作用是使用两个hash表判断当前的字符是数字还是字母或者运算符。

/*
char   ASCII   c
0      48      11
1      49      11
2      50      12
3      51      12
4      52      13
5      53      13
6      54      14
7      55      14
8      56      15
9      57      15
(      40      7
)      41      8
*      42      8
+      43      9
-      45      10
/      47      10
*/
/*
if c >= 11, that is number, b = 0;
else
char   ASCII   b
(      40      8
)      41      0
*      42      7
+      43      8
-      45      1
a      97      2
/      47      3
o      111     4
p      112     5
q      113     6
i      105     7
g      103     8
*/

在b的解析式中使用了一个magic number(3*367>>c&1),作用是进一步限定了代码的范围，让不合适的字母的非零b值归零。具体作用举例如下。

sin-> s i n
s -> 8*0 -> 0
i -> 7
n -> 3*0 -> 0

所以sin的关键字符是i，而s的作用被设为0，防止和cos解析混淆。

`main`函数的返回值

简单而言，main(3,argv)的返回值为0，main(4,argv)的返回值为1。

这是为了在某些时候简化代码。

第一部分的解析

main(3,argv)对应exp_additive的解析。

我们暂时去掉调试代码。

if (argc <= 3)
{
    double a=0;int b;
    char c=1;
    b=0;
    main(4, argv); // 解析exp_multiplicative
g1:c+= 1;
// 以下对应符号解析exp_additive
// 使用goto相当于代码范式中的while循环
    if(*"/"==*argv[1]){
        a=r;
        main(4, argv);      // 需要一个exp_multiplicative
        r=r*a;
        goto g1;
    }
    if(*"*"==*argv[1]){
        a=r;
        main(4, argv);      // 需要一个exp_multiplicative
        r=r*a;
        goto g1;
    }
    if(*"+"==*argv[1]){
        a=r;
        main(3, argv);      // 需要继续解析exp_additive
        r=r+a;
        goto g1;
    }
    if(*"-"==*argv[1]){
        a=r;
        main(3, argv);      // 需要继续解析exp_additive
        r=r+a;
        goto g1;
    }
    // 上文中解析新表达式的时候没有自增argv[1]，
    // 是为了将当前的符号作为一元运算符处理，
    // 以便简化/-的解析难度。
    if(argc==2)printf("%f\n",r);
    return 0;
}

第二部分的解析

main(4,argv)对应exp_multiplicative的解析。

    if (argc == 4) {
        double a=0;int b;
        char c=(*argv[1]*(int) 11/26+7)&15; // number:>=11, else < 11
        b=(*argv[1]%21 +7)%9*(3*367>>c&1); // number:0, else, hash
        if(c>=11){ // 当前解析的是数字
            c=0;
            sscanf(argv[1],"%lf%c",&r,&c); // 读取数字和运算符
            while(*++argv[1]-c); // 前移到运算符的位置
        } else if(!main(4-(*argv[1]++=='('),argv))
        // 如果运算符是(,需要解析一个exp_additive
        // 否则，将剩下的部分继续作为exp_multiplicative解析
        // 而且需要注意，main(4,argv)只能解析一元运算符
            argv[1]++;
            // 如果运算符是'(',需要跳过配套的')'。使用main的返回值简化代码

        // 下面是根据b的值判断一元运算符的类型，并且作用上去。
        r=--b?r: - (r);
        r=--b?r: tan (r);
        
        r=--b?r: 1/ (r);
        r=--b?r: cos (r);
        
        r=--b?r: exp (r);
        r=--b?r: sqrt (r);
        
        r=--b?r: sin (r);
        r=--b?r: log (r);
        return 1;
    }
}

代码混淆

代码混淆的重点在于头部的语句。

#define clear 1;if(c>=11){c=0;sscanf(_,"%lf%c",&r,&c);while(*++_-c);}\
  else if(argc>=4&&!main(4-(*_++=='('),argv))_++;g:c+=
#define puts(d,e) return 0;}{double a;int b;char c=(argc<4?d)&15;\
  b=(*_%__LINE__+7)%9*(3*e>>c&1);c+=
#define I(d) (r);if(argc<4&&*#d==*_){a=r;r=usage?r*a:r+a;goto g;}c=c
#define return if(argc==2)printf("%f\n",r);return argc>=4+
#define usage main(4-__LINE__/26,argv)
#define calculator *_*(int)
#define l (r);r=--b?r:
#define _ argv[1]
#define x

argv[1]是经常使用的值。#define _ argv[1] 进行一步混淆。
main(3,argv)还是main(4,argv)，使用行号4-__LINE__/26判断。
一元运算符的运算需要大量格式相似的语句，使用#define l (r);=__b?r:可以和表格内容结合直接生成。表格中有多余的x，使用#define x直接清除。
二元运算符的循环解析，就是那个goto和后面的语句，使用一个#define I(d)简化。
返回值需要针对argc的不同而不同，直接使用一个#define return语句完成了三种情况的展开，很精妙。
#define puts(d,e)将函数的头部定义体现了出来。注意这里的d是从usage到7.584的全部部分，e是简单的367。
代码中的magic number都很好的充当了hash函数的构造，而且magic number本身也是符合数学规律的，很精妙。
clear的作用是判断hash函数的结果，转向进一步的处理。
代码中充斥着的+ ~~~~ !在展开形式中充当了各表达式的构成部分。同时还可以把计算器的数字部分转化为不影响表达式的部分。比如! 1 | 2 | 3 || ...
calculator也是表达式的一部分，提供了强制类型转换。

总结

至此本份代码的解析基本完成。展开后的代码也可以得到正确的结果，分析部分也基本符合表达式的BNF定义。如果想要进一步得到代码构造的内在逻辑，就不得不更加深入的学习相关领域的知识。今天的分析就到此为止了。

算法

编程算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

简单理解Qt项目的CMakeLists.txt 上一篇

SCR,TRIAC,Photo TRIAC-四两拨千斤的光耦隔离电路下一篇