Ylin's Blog
0%

发表于 更新于
本文字数： 24 阅读时长 ≈ 1 分钟

你好呀！

这里记录我的学习经历和内容

希望能够帮到你们

: )

发表于 更新于 分类于 ，
本文字数： 2.4k 阅读时长 ≈ 9 分钟

上一节中完成了对虚拟机的实现和初始化，还有指令集的定义，接下来就是对源文件的词法分析部分

词法分析

什么是词法分析

源文件的内容对于我们的解释器而言，本质上就是一系列ASCII字符串，是毫无意义的，我们需要通过语法分析将其解析为简单的指令，然后再执行。可是这样一来，这就使得语法分析的部分十分庞大。所以编译器一般会对整个过程进行前后端的分离。前端负责对源文件进行预处理，将其解析为一系列标识符流，如下：

1
2
3
2 + 3 * (4 - 5)
=>
(Number, 2) Add (Number, 3) Multiply Left-Bracket (Number, 4) Subtract (Number, 5) Right-Bracket

然后后端就可以根据直接对标识符流进行处理，就避免了中间处理过程臃肿的情况。

词法分析和编译器

词法分析从某种意义上来讲，本质上也是一种编译器，它以源代码作为输入流，然后输出标识符流：

1
2
3
                   +-------+                      +--------+
-- source code --> | lexer | --> token stream --> | parser | --> assembly
                   +-------+                      +--------+

直接从源代码编译成汇编代码是很困难的，因为输入的字符串比较难处理。所以我们先编写一个较为简单的编译器（词法分析器）来将字符串转换成标记流，而标记流对于语法分析器而言就容易处理得多了。

词法分析器的实现

这里我们就不用现有的词法分析器了，我们手动的实现这一部分。当然我们需要注意，词法分析并不是一次性的将所有的源码转换成标记流。因为在代码中的大多数操作符，和字符关键字都是和代码有上下文关系的。

所以实际的做法是，提供一个next()函数，每次调用这个函数就返回下一个标识。

支持的标识

我们的编辑器支持以下标识符：

1
2
3
4
5
enum {
	Num = 128, Fun, Sys, Glo, Loc, Id,
	Char, Else, Enum, If, Int, Return, Sizeof, While,
	Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak
};

这里之所以让标识符从128开始，是为了避免和前面设置的指令枚举变量发生冲突。

上面的运算符的枚举变量是有顺序的，实际上他们是按优先级进行排列的，之后的语法分析过程中会用到。现在我们就要进行token的匹配了。例如将==匹配成Eq，将=匹配成Assign。在下面的实现中，我们会分析这些匹配是怎么实现的。

当然这里还需要注意一些字符，他们自己就构成了标记，如右方括号]和波浪号~等，我们不需要对他们做额外的处理，因为他们不属于多字符的共同标记，也不参与运算（没有优先级关系）

框架

我们的next()的主体框架如下：

1
2
3
4
5
6
7
void next(){
    char *last_pos;
    while(*src){
        ++src;
	// 具体的匹配逻辑
    }
}

这里我们使用whlie来跳过我们分析过程中的遇到的空白字符和未知的符号。下面我们先把几个比较特殊的标识符进行一下处理：

换行符号

换行符也和空格类似，只不过遇到换行符号，我们需要将当前的行号+1：

1
if(token == '\n') {++line;}

宏定义

我们的解释器不支持宏定义所以直接跳过#后面部分的内容:

1
2
3
else if(token == '#'){
    while (*src == 0 || *src == ' ') {++src;}
}

标识符和符号表

标识符可以理解为变量名。对于语法分析而言，我们并不关心一个变量叫什么，而是在意这个变量的标识符，我们需要从它唯一的标识符中获取这个变量的信息。

基于这个理由，我们让词法分析器将扫描到的标识符保存在一张表中，每当我们遇到标识符，就去表中查找，如果标识符存在就返回它的唯一标识符，不存在则创建有一个新的标识符存放在表中。

我们用结构体来存放标识符的信息：

1
2
3
4
5
6
7
8
9
10
11
12
// 标识符信息
typedef struct _id{
    int token;
    int hash;
    char *name;
    int class;
    int type;
    int value;
    int Bclass;
    int Btype;
    int Bvalue;
} ID;

这里解释一下各个字段的具体含义：

  • token：该标识符返回的标记，这里主要是存储变量的信息，所以标记类型注意要是Id
  • hash： 这个标识符的hash值，用于快速比较标识
  • name：存放标识符的变量名
  • class： 存放标识符的类型，例如全局、局部、数字等
  • type： 标识符的类型，如果是个变量，可能是指针、int或者char
  • value： 存放这个标识符的值，如果标识符是函数的，则存放函数地址
  • BXXX： C语言的标识符中可能是全局的也是局部的，当我们局部标识符和全局标识符冲突时，这个字段用于保存全局变量的信息。

上面这些信息用于我们在语法分析部分进行解析，更加方便快捷：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int token_val;          // 当前标识符的值
ID *Symbols;            // 符号表
ID *current_id;         // 当前标识符

...
	else if(token>='a'&&token<='z' || token>='A'&&token<='Z' || (*src >= '0' && *src <= '9') || token=='_'){
            // 标识符处理
            last_pos = src - 1; // 标识符起始位置
            while(*src>='a'&&*src<='z' || *src>='A'&&*src<='Z' || *src>='0'&&*src<='9' || *src=='_')
                hash = hash * 147 + *(src++);
            // 查找符号表
            current_id = Symbols;
            while(current_id->token){
                if(current_id->hash == hash && !memcmp(current_id->name, last_pos, src - last_pos)){
                    token = current_id->token;
                    return;
                }
                current_id++;
            }
            // 新标识符
            token = current_id->token = Id;
            current_id->hash = hash;
            current_id->name = (int)last_pos;
            return;
        }  
...

我们通过以上形式实现对标识符的识别。

数字

当遇到数字时我们也需要，进行对应的解析，这一部分的难点在于不同进制的识别。然后将数字转换为对应的数据并求值，我们把它的值保存在token_value中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
else if(token>='0'&&token<='9'){
           // 数字处理
           token_val = token - '0';
           if(token_val > 0){
               while(*src>='0'&&*src<='9')
                   token_val = token_val *10 + *(src++) - '0';
           }else{
               if(*src == 'x' || *src == 'X'){
                   token = *(++src);
                   while((token>='0'&&token<='9') || (token>='a'&&token<='f') || (token>='A'&&token<='F')){
                       token_val = token_val *16 + (token&15) + (token>='A' ?9:0);
                       token = *(++src);
                   }
               }else{
                   while(*src>='0'&&*src<='7')
                       token_val = token_val *8 + *(src++) - '0';
               }
           }
           token = Num;
           return;
       }

字符串

在实际的分析过程中，当我们遇到字符串，我们需要将它的内容保存在data段中，然后返回它data段中的地址，之后我们对字符串的使用都指向这个地址。另一个特殊的地方在于，我们需要支持部分转义字符的实现，这里我们只对\n做一个支持，也支持\x表示字符x的语法。

在分析时，我们将单个字符'a'按Num的形式保存并返回，我们将"a string"按字符串的形式进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
else if(token=='"'||token=='\''){
          last_pos = data;
          while(*src!=token && *src!=0){
              token_val = *src++;
              if(token_val=='\\'){
                  token_val = *src++;
                  if(token_val=='n') token_val = 10;
                  else if(token_val=='t') token_val = 9;
                  else if(token_val=='r') token_val = 13;
                  else if(token_val=='\\') token_val = '\\';
              }
              if(token == '"')
                  *data++ = token_val;
          }
          src++;  // 跳过结束符
          if(token == '"') {
              *data++ = 0;
              token_val = (int)last_pos;
          }else {token = Num;}
          return;
      }

这一部分可能比较难理解，首先就是判断这个是单字符还是多字符的字符串。然后分别做不同的处理即可。

注释

在我们的C中，只支持//类型的注释，不支持多行/**/的注释方法。处理方式和前面对#的方式差不多，需要注意的是，这里要前瞻的观察下一位是什么/可能是除法，也可能是//注释

1
2
3
4
5
else if(token=='/'){
          if(*src=='/')
              while(*src!=0 && *src!='\n') ++src;
          else {token = Div; return;}
      }

这里我们利用src比token快一个字符的特点，实现了对多个字符的观察，我们称这个概念为前瞻（lookahead）

其他

其他的大多数是一些简单的操作符，我们简单的附上代码即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
else if(token=='='){
          if(*src=='='){++src; token = Eq;} 
          else {token = Assign;}
          return;
      }else if(token=='+'){
          if(*src=='+'){++src; token = Inc;} 
          else {token = Add;}
          return;
      }else if(token=='-'){
          if(*src=='-'){++src; token = Dec;} 
          else {token = Sub;}
          return;
      }else if(token=='!'){
          if(*src=='='){++src; token = Ne;} 
          return;
      }else if(token=='<'){
          if(*src=='='){++src; token = Le;} 
          else if(*src=='<'){++src; token = Shl;}
          else {token = Lt;}
          return;
      }else if(token=='>'){
          if(*src=='='){++src; token = Ge;} 
          else if(*src=='>'){++src; token = Shr;}
          else {token = Gt;}
          return;
      }else if(token=='|'){
          if(*src=='|'){++src; token = Lor;} 
          else {token = Or;}
          return;
      }else if(token=='&'){
          if(*src=='&'){++src; token = Lan;} 
          else {token = And;}
          return;
      }else if(token=='^'){
          token = Xor;
          return;
      }else if(token=='%'){
          token = Mod;
          return;
      }else if(token=='*'){
          token = Mul;
          return;
      }else if(token=='['){
          token = Brak;
          return;
      }else if(token=='?'){
          token = Cond;
          return;
      }else if(token=='~' || token==';' || token=='{' || token=='}' || token=='(' || token==')' || token==']' || token==',' || token==':')
          return;

基本的思想就是利用前瞻确定标记。

关键字和内置函数

完成了上述的词法分析之后，我们需要在正式开始词法分析之前，预处理我们的关键字和内置的函数。我们将它们加入符号表，并提前为他们赋予必要的信息。

我们在main函数中对其进行初始化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{
    ID *Symbols = current_id = malloc(poolsize);
    src = "char else enum if int return sizeof while "
          "open read close printf malloc memset memcmp exit void main";
    i=Char;
    while(i<While){
        next();
        current_id->token = i++;
    }
    i = OPEN;
    while(i<=EXIT){
        next();
        current_id->value = i++;
        current_id->class = Sys;
        current_id->type = INT;
    }
    next(); current_id->token = Char;
    next(); idmain = current_id;
}

至此我们就完成了对源代码的词法分析，程序会通过词法分析将我们的源代码转换成标记流。

发表于 更新于 分类于 ，
本文字数： 3.8k 阅读时长 ≈ 14 分钟

我们将尝试构建一个C语言的解释器，这个项目也是我C语言的大作业。现在回顾看来，当时对整个项目都是知其然不知其所以然，从现在的眼光来看，当时很多做法都是很稚嫩的。尤其是对于这个项目结构的理解也远远不足，所以打算重构一遍。

构建流程

首先是整个编译器的构建流程，一般来讲，编译器的编写有三个步骤：

  1. 词法分析器，用于将文本文件转换为内部的表示结构
  2. 语法分析器，在词法分析得到的标记的基础之上，构建一棵语法树
  3. 目标代码的生成，将语法树转换成目标代码

但是由于这里我们编写的是一个解释器，所以我们自定义自己的虚拟机框架和指令。我们通过语法分析词法分析之后得到的语法树，来生成使用自定义虚拟机框架的指令的目标代码。

编译器的框架

仿照c4编译器的写法：

这里我们的解释器主要包括4个函数：

  • next() 用于词法分析，获取下一个标记
  • program() 用于语法分析，分析整个C语言的程序
  • expression(level) 用于解析一个表达式
  • eval() 虚拟机的入口，用于执行目标代码

可能在此基础之上我会做出一点自己的改动，但是总体框架还是确定的，首先是实现对要解释的文件的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 源文件全局变量
int line;       // 当前行数
char *src;      // 源文件内容
char *old_src;  // 源文件备份

int main(int argc, char *argv[]) {
    int i, fd;

    argc--;
    argv++;

    int poolsize = 256*1024; // 内存池大小
    line = 1;

    // 读取源文件
    {
        if((fd = open(*argv,0)) < 0){
        printf("Could not open %s\n", *argv);
        exit(1);
        }

        if(!(src = old_src = malloc(poolsize))){
            printf("Could not malloc %d bytes\n", poolsize);
            exit(1);
        }

        if((i=read(fd, src, poolsize-1)) <= 0){
            printf("Could not read %s\n", *argv);
            exit(1);
        }
        src[i] = 0; // 文件结束符
        close(fd);
    }

    program();
    return eval();
}

我们将读取到的文件内容复制到src内存空间中。

现在我们就需要开始模拟一台计算机应有的功能了，我们的指令需要运行在我们的虚拟机上。那么首先，我们就需要定义一个自己的虚拟机，一台机器必须要有以下几个部分：

  • 内存： 这是用来存放数据的主要空间，我们的代码段数据 还有函数调用时的栈段都存放在这里
  • 寄存器：我们需要寄存器帮助我们实现各种命令，同时也需要程序计数器指向我们的指令
  • CPU：本来这一部分应该是一大堆电路，但是这里我们可以通过操作指针和寄存器的方式，用一系列程序，简单的模拟它

计算机内部实现

内存

首先是内存部分，一般情况下，内存会被分成几个段。由于我们是简单实现的理想模型，我们只需要设置几个最基本的部分就可以了：

  • 代码段： 我们分析得到的指令就被存放在这里
  • 数据段： 这里用来存放我们源程序中用的数据，通常和token信息绑定
  • 栈段： 我们处理函数调用将会用到它，存放栈帧和局部变量等数据

现在我们就可以简单的对我们的模拟的计算机内存进行初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
......
// 内存布局
int *text;          // 代码段
int *old_text;      // 代码段备份
int *stack;         // 栈
char *data;         // 数据段

int main(int argc, char *argv[]) {
	......
    // 内存初始化
    {
        if(!(text = old_text = malloc(poolsize))){
            printf("Could not malloc %d bytes for text\n", poolsize);
            exit(1);
        }
        if(!(stack = malloc(poolsize))){
            printf("Could not malloc %d bytes for stack\n", poolsize);
            exit(1);
        }
        if(!(data = malloc(poolsize))){
            printf("Could not malloc %d bytes for data\n", poolsize);
            exit(1);
        }
        memset(text, 0, poolsize);
        memset(stack, 0, poolsize);
        memset(data, 0, poolsize);
    }

    program();
    return eval();
}

寄存器

寄存器用来存放计算机的运行状态，我们的虚拟机中只简单的使用四个寄存器，分别是：

  • PC程序计数器，用于存放一个内存地址，该地址中用于存放下一条要执行的指令
  • SP寄存器，永远指向当前的栈顶（注意这里的栈是从高地址向低地址增长的）
  • BP基址寄存器，用于指向栈底，当我们在函数调用解析参数时需要用到它
  • AX通用寄存器，用来存放一条指令执行后的结果

我们对他们进行简单的初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
......
// 寄存器
int *pc;            // 程序计数器
int *bp;            // 基址指针
int *sp;            // 栈指针
int ax;             // 通用寄存器
int cycle;          // 时钟周期

int main(int argc, char *argv[]) {
	......
    // 寄存器初始化
    {
        bp = sp = (int*)((char*)stack + poolsize);
        ax = 0;
        cycle = 0;
    }

    program();
    return eval();
}

指令

现在我们的虚拟机已经有了基本的骨架，我们可以开始尝试实现我们我们虚拟机最基本的指令集。不过首先我们需要明确我们需要用到哪些指令。这里我们直接照搬C4的指令集就行了：

1
2
3
4
5
6
7
enum {
       LEA, IMM, JMP, CALL, JZ, JNZ, ENT, ADJ, LEV,
       LI, LC, SI, SC, PUSH,
       OR, XOR, AND, EQ, NE, LT, GT, LE, GE,
       SHL, SHR, ADD, SUB, MUL, DIV, MOD,
       OPEN, READ, CLOS, PRTF, MALC, MSET, MCMP, EXIT 
};

这些指令顺序是有意的，带有参数的指令在前，没有参数指令的放在后面，为了方便我们之后打印调试信息。

MOV

MOV dest,srcx86中最基础重要的一个公式，它将SOURCE中的内容放在DEST中。但在我们的虚拟机中只提供了一个通用寄存器AX，加上由于对参数类型的识别是一件复杂的事情，所以我们将MOV拆分成五个子操作来实现：

  • IMM <num> 将num放入寄存器ax中
  • LC 将对应地址中的字符载入ax中，要求ax中存放地址
  • LI 将对应地址中的整数载入ax中，要求ax中存放地址
  • SC将ax中的数据作为字符存放入地址中，要求栈顶存放地址
  • SI将ax中的数据作为整数存放入地址中，要求栈顶存放地址

这样的拆分，极大程度上的减小了指令实现的复杂度，现在我们可以开始具体的实现了：

1
2
3
4
5
6
7
8
9
10
11
int eval() {
    int op, *tmp;
    while(1){
        if(op == IMM) {ax = *pc++;}
        else if(op == LC) {ax = *(char*)ax;}
        else if(op == LI) {ax = *(int*)ax;}
        else if(op == SC) { *(char*)*sp++ = ax;}
        else if(op == SI) { *(int*)*sp++ = ax;}
    }
    return 0;
}

这里得*sp++实际上就是一个退栈操作，将值存储到弹出得地址中。

这里我之前一直没有搞懂，为什么LI/LC要将对应地址中的字符载入ax中，因为我们的默认的计算结果是存储在ax中的，也就是我们指令计算出的地址，可以直接被LI/LC所使用，这样就很高效。

PUSH

PUSH的作用很简单，就是将值或者寄存器压入到栈中。在这里我们PUSH的作用给就是将ax的值压入栈中，因为我们只有这一个寄存器：

1
else if(op == PUSH) {*--sp = ax;}

JMP

JMP <addr>是跳转指令，无条件的将当前的PC寄存器设置为指定的<addr>，实现如下：

1
else if(op == JMP) {pc = (int*)*pc;}

pc始终指向的是下一条指令，所以此时它存放的存放的是JMP指定的参数，即<addr>的值

JZ/JNZ

为了实现if语句 我们也需要条件判断相关的指令。这里我们只需要实现两个最简单的条件判断，即ax==0/ax!=0的情况下的跳转：

1
2
else if(op == JZ) {pc = ax ? pc+1 : (int*)*pc;}
else if(op == JNZ) {pc = ax ? (int*)*pc : pc+1;}

子函数调用

这个是比较重要的一部分，我很大程度上也是为了这一部分重新回头别写这个编译器。这里我们将根据子函数调用约定，用几个最简单的指令来实现这个过程，我们要引入的指令有CALL ENT ADJ LEV。

首先我们介绍CALL，它用于跳转到一个子函数的开始地址。程序将会跳转到地址<addr>，并将当前的位置信息保存起来，以用于函数调用后的返回。这里我们将返回的PC存放在栈中：

1
else if(op == CALL) {*--sp = (int)(pc+1); pc = (int*)*pc;}

现在我们能进入调用函数了，那么我们便需要进一步的规范我们的函数调用规则。在实际的函数调用中，我们不仅要考虑函数的地址，也要考虑如何传递参数和返回结果，这里我们将每次的返回结果保存在ax中，对于参数传递，我们需要遵循C语言的调用标准：

  • 由调用者将参数入栈
  • 调用结束时，由调用者将参数出栈
  • 参数逆序入栈（因为先进后出）

我们可以看下面的这个例子：

1
2
3
4
5
6
7
8
int callee(int, int, int);

int caller(void){
	int i, ret;
	ret = callee(1, 2, 3);
	ret += 5;
	return ret;
}

会生成下面的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
caller:
; make new call frame
push    ebp
mov     ebp, esp
sub     1, esp       ; save stack for variable: i
; push call arguments
push    3
push    2
push    1
; call subroutine 'callee'
call    callee
; remove arguments from frame
add     esp, 12
; use subroutine result
add     eax, 5
; restore old call frame
mov     esp, ebp
pop     ebp
; return
ret

但是我们的虚拟机难以解决其中的几个问题：

  • push ebp 我们的PUSH无法指定寄存器
  • mov ebp,esp 我们的MOV也无法直接指定源和目的
  • add esp,12 我们的ADD也无法直接实现两个操作数的加法

所以我们需要额外的指令来代替这几个的功能，所以我们需要定义以下几个指令：

ENT

ENT <size>指的是enter我们用它实现make new call frame的操作，即保存当前的栈指针，并在栈上保留一定的空间，用来存放局部变量，汇编代码的表现形式如下：

1
2
3
4
; make new call frame
push    ebp
mov     ebp, esp
sub     size, esp       ; save stack for variable

我们可以通过以下形式实现它：

1
else if(op == ENT) {*--sp = (int)bp; bp = sp; sp = sp - *pc++;}

ADJ

ADJ <size>用于实现remove argument from frame。用于将调用子函数时压入栈中的数据清楚，之所以单独定义这个指令，是对我们ADD功能局限做出的妥协。其汇编实现如下：

1
2
; remove arguments from frame
add     esp, size

我们可以通过以下形式实现它：

1
else if(op == ADJ) {sp = sp + *pc++;}    // add esp <size>

LEV

本质上这个指令并不是必需的而且我们的指令集中并没有POP的指令，所以为了简洁的进行函数的退出操作，我们专门定义了LEV的封装。对应的汇编操作如下：

1
2
3
4
5
; restore old call frame
mov     esp, ebp
pop     ebp
; return
ret

我们用以下形式实现：

1
else if(op == LEV) {sp = bp; bp = (int*)sp++; pc = (int*)*sp++;}

LEA

上述的指令解决了调用帧的问题，解决了我们函数的运行和返回的问题。现在，为了进一步的执行调用函数，我们需要想办法获取先前压入的参数。在此之前，我们首先需要了解当参数调用时，栈中的调用帧是什么样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sub_function(arg1, arg2, arg3);

|    ....       | high address
+---------------+
| arg: 1        |    new_bp + 4
+---------------+
| arg: 2        |    new_bp + 3
+---------------+
| arg: 3        |    new_bp + 2
+---------------+
|return address |    new_bp + 1
+---------------+
| old BP        | <- new BP
+---------------+
| local var 1   |    new_bp - 1
+---------------+
| local var 2   |    new_bp - 2
+---------------+
|    ....       |  low address

我们首先将参数压入栈中，然后进行调用，调用会将返回地址压入栈中，然后保存当前的栈基址（我们将这个保存的栈帧称为old_bp），准备创建下一个栈帧。当前视图就是进行push rbp; mov rbp,rsp;之后的栈帧状态。此时如果我们想要访问函数的第一个参数，我们就需要访问new_bp+4地址上的内容。

但是这里有一个问题，我们的ADD指令无法对bp进行运算，所以我们需要设置一个新的指令，用于访问栈帧上的地址LEA <offset>。我们具体的实现如下：

1
else if(op == LEA) {ax = (int)(bp + *pc++);}

现在，我们就完成了实现函数调用的所有指令了。

运算符指令

我们在C语言中支持的各种运算符号都是二元的，所以我们指令的参数也应该是由两个的，但是我们只有一个通用寄存器，这就导致我们需要将其中一个参数放在栈上，另一个参数存放在ax中，我们通过指令计算出来的结果也存放在ax上。

我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
else if (op == OR)  ax = *sp++ | ax;
else if (op == XOR) ax = *sp++ ^ ax;
else if (op == AND) ax = *sp++ & ax;
else if (op == EQ)  ax = *sp++ == ax;
else if (op == NE)  ax = *sp++ != ax;
else if (op == LT)  ax = *sp++ < ax;
else if (op == LE)  ax = *sp++ <= ax;
else if (op == GT)  ax = *sp++ >  ax;
else if (op == GE)  ax = *sp++ >= ax;
else if (op == SHL) ax = *sp++ << ax;
else if (op == SHR) ax = *sp++ >> ax;
else if (op == ADD) ax = *sp++ + ax;
else if (op == SUB) ax = *sp++ - ax;
else if (op == MUL) ax = *sp++ * ax;
else if (op == DIV) ax = *sp++ / ax;
else if (op == MOD) ax = *sp++ % ax;

内置命令

有很多由系统支持的函数，我们往往难以在机器上支持实现，所以这里我们简单的对函数进行封装，设置为内置的指令，用来支持一些常用的库函数调用。

这里我们就简单的对exit open close read printf malloc memset指令进行封装以确保我们的程序有基本的能力：

1
2
3
4
5
6
7
8
else if(op == EXIT) {printf("exit(%d)", *sp); return *sp;}
      else if(op == OPEN) {ax = open((char *)sp[1], sp[0]);}
      else if(op == CLOS) {ax = close(*sp);}
      else if(op == READ) {ax = read(sp[2], (char*)sp[1], *sp);}
      else if(op == PRTF) {tmp = sp+pc[1]; ax = printf((char*)tmp[-1],tmp[-2],tmp[-3],tmp[-4],tmp[-5],tmp[-6]);}
      else if(op == MALC) {ax = (int)malloc(*sp);}
      else if(op == MSET) {ax = (int)memset((char*)sp[2], sp[1], *sp);}
      else if(op == MCMP) {ax = memcmp((char*)sp[2], (char*)sp[1], *sp);}

这里我们的参数在函数调用时是顺序入栈，所以看起来比较反直觉，结合栈是自顶向下索引的，所以我们最终可以很好的理解我们的参数调用顺序。

最后在加上一个错误判断，我们的虚拟机指令就完成了：

1
2
3
4
else {
            printf("unknown instruction:%d\n", op);
            return -1;
        }

测试

现在我们的虚拟机指令就完成了，我们可以做一个简单的测试，来看我们的机器能否正确的运行：

1
2
3
4
5
6
7
8
9
10
11
12
i = 0;
pc = text;
text[i++] = IMM;
text[i++] = 12;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 5;
text[i++] = DIV;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 1;
text[i++] = EXIT;

程序执行的结果是：

1
2
ylin@Ylin:~/Program/c4$ ./a.out
exit(2)

至此我们的虚拟机以及指令架构就完成了

发表于 更新于 分类于 ，
本文字数： 1.6k 阅读时长 ≈ 6 分钟

自从上个学期之后，就怎么接触过图形学了。但是仔细感受下来，图形学是最让人有收获感的方向。它通过模拟真实的物理规则，通过计算模拟出真实的模拟场景，十分有趣，就是给人一种融汇贯通的感觉，学到的知识能结合在一起，我感觉这才是最有意义的地方。

然后进度的话是接着上一次”图形学(12)“最终的场景，在此之前，我把之前的项目代码熟悉了一下，在WSL环境上重构了一遍，感觉效率相对于原来还是快了一点。现在就正式开始吧

运动模糊

在真实的世界中，当我们按下快门，相机会接受一段时间内的光线信息，在此期间内，世界中的物体可能会发生移动，这样排除来的照片，我称之为运动模糊。为了真实的再现这个效果，需要对我们现有的程序进行补充：

简介

我们可以在快门开启的期间随机选择一个时间点发射一条射线从而得到，这条射线上的光子信息。只要我们能够知道在那个随机时间点上，场景中每个物体的位置和姿态。我们就可以像处理静态场景一样，计算这条光线与物体的交点、着色等。这样，这条光线就能准确反映那个特定瞬间的光照情况。

因此光线追踪的过程只需要，在处理每条光线时，更新物体的位置，就可以是实现对物体动态的追踪了。为了实现这一点，我们需要让每条线携带时间信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ray {
public:
    ray() {}
    ray(const point3& origin, const vec3& direction, double time)
        : orig(origin), dir(direction), tm(time) {}
	// 默认初始化时间为0
    ray(const point3& origin, const vec3& direction)
        : orig(origin), dir(direction), tm(0.0) {}

    point3 origin() const { return orig; }
    vec3 direction() const { return dir; }
    double time() const { return tm; }

    point3 at(double t) const {
        return orig + t * dir;
    }

private:
    point3 orig;
    vec3 dir;
    double tm;
};

时间管理

真实世界中的快门时间是由两部分决定的：

  • 帧间隔：连续两帧画面之间的时间间隔
  • 快门开启时长：在每一帧的帧间隔中，快门实际打开、允许光线进入的时间长度（一般情况下开启时间越长，运动模糊越明显）

但是这里为了简化光线追踪的实现，我们只对一帧的画面进行捕捉。当然，如果想要渲染一个完整的动画，只需要设置好适当的快门时间就可以了。如果世界是静态的，只有相机的位置在移动，那么我们的代码无需做出改变。但如果世界中的物体在进行运动，那么我们需要为hittable设置一种方法，使得每个物体都能感知到当前帧的时间周期，并更新他们此时的位置。

为了简化墨香，我们只渲染一帧，我们把时间设置为从时间t=0到t=1。我们将让相机在时间[0,1]之间随机发射光线，并更新我们的球体类。

更新相机

我们更新相机，使其在开始和结束时间之间随机生成光线，这里我们通过相机类来对光线信息进行管理和生成：

1
2
3
4
5
6
7
8
ray get_ray(int i, int j){
    auto offset = sample_pixel_offset();
    auto pixel_sample = pixel_origin + (i + offset.x()) * pixel_delta_u + (j + offset.y()) * pixel_delta_v;
    auto ray_origin = (defocus_angle > 0.0) ? defocus_disk_sample() : camera_origin;
    auto ray_direction = pixel_sample - ray_origin;
    auto ray_time = random_double();
    return ray(ray_origin, ray_direction, ray_time);
}

球体运动属性

现在我们要让我们的世界动起来，我们需要更新球体类，使其中心在t=0到t=1的时间中，从center1线性速度的移动到center。我们将center属性修改成一个从t=0时刻指向t=1时刻的射线向量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class sphere: public hittable {
public:
    // 静态球体
    sphere(const point3& center, double radius, shared_ptr<material> mat)
        : center(center,vec3(0,0,0)), radius(radius), mat(mat) {}
    // 动态球体
    sphere(const point3& center1, const point3& center2, double radius, shared_ptr<material> mat)
        : center(center1,center2-center1), radius(radius), mat(mat) {}
	...

private:
    ray center;
    double radius;
    shared_ptr<material> mat;
};

然后我们需要更新hit方法，需要需要在更新动画中心的位置之后，也能正确的进行相交判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool hit(const ray& r, interval t_range, hit_record& rec) const override {
    point3 cur_center = center.at(r.time());
    vec3 oc = r.origin() - cur_center;
    auto a = r.direction().length_squared();
    auto half_b = dot(oc, r.direction());
    auto c = oc.length_squared() - radius * radius;
    auto discriminant = half_b * half_b - a * c;
    if (discriminant < 0) {
        return false;
    }
    auto sqrtd = std::sqrt(discriminant);
    auto root = (-half_b - sqrtd) / a;
    if (!t_range.contains(root)) {
        root = (-half_b + sqrtd) / a;
        if (!t_range.contains(root)) {
            return false;
        }
    }
    rec.t = root;
    rec.p = r.at(rec.t);
    vec3 outward_normal = (rec.p - cur_center) / radius;
    rec.set_face_normal(r, outward_normal);
    rec.mat = mat;
    return true;
}

我们只需要根据射线携带的时间信息，更新我们的球心位置，然后正常的进行计算就行了，如果r.time()等于0，就说明位置不变。就算变了，我们也不需要花费额外的计算开销。

追踪光线的相交时间

现在光线有了时间属性，我们也需要记录每次光线和世界相交的时间信息，我们只需要简单的更新一下相交光线的信息就行了：

1
scattered = ray(rec.p, scatter_direction, r_in.time());

最终效果

现在我们想世界中添加球体的运动属性，以实现最终的动态渲染效果，让我们看看怎么样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include "utils.h"
#include "hittable_list.h"
#include "sphere.h"
#include "camera.h"
#include "material.h"

int main(){
    // 世界场景
    hittable_list world;

    auto ground_material = make_shared<lambertian>(color(0.5, 0.5, 0.5));
    world.add(make_shared<sphere>(point3(0,-1000,0), 1000, ground_material));

    for (int a = -8; a < 8; a++) {
        for (int b = -8; b < 8; b++) {
            auto choose_mat = random_double();
            point3 center(a + 0.9*random_double(), 0.2, b + 0.9*random_double());

            if ((center - point3(4, 0.2, 0)).length() > 0.9) {
                shared_ptr<material> sphere_material;

                if (choose_mat < 0.5) {
                    // diffuse
                    auto albedo = color::random() * color::random();
                    sphere_material = make_shared<lambertian>(albedo);
                    auto center2 = center + vec3(0, random_double(0,0.2), 0);
                    world.add(make_shared<sphere>(center, center2, 0.2, sphere_material));
                } else if (choose_mat < 0.8) {
                    // metal
                    auto albedo = color::random(0.5, 1);
                    auto fuzz = random_double(0, 0.1);
                    sphere_material = make_shared<metal>(albedo, fuzz);
                    world.add(make_shared<sphere>(center, 0.2, sphere_material));
                } else {
                    // glass
                    sphere_material = make_shared<dielectric>(1.5);
                    auto center2 = center + vec3(0, random_double(0,0.1), 0);
                    world.add(make_shared<sphere>(center, center2, 0.2, sphere_material));
                }
            }
        }
    }

    auto material1 = make_shared<dielectric>(1.5);
    world.add(make_shared<sphere>(point3(0, 1, 0), 1.0, material1));

    auto material2 = make_shared<lambertian>(color(0.4, 0.2, 0.1));
    world.add(make_shared<sphere>(point3(-4, 1, 0), 1.0, material2));

    auto material3 = make_shared<metal>(color(0.7, 0.6, 0.5), 0.0);
    world.add(make_shared<sphere>(point3(4, 1, 0), 1.0, material3));
    
    // 相机
    camera cam;
    cam.aspect_ratio = 25.0 / 16.0;
    cam.image_width = 1250;
    cam.samples_per_pixel = 100;
    cam.max_depth = 30;


    cam.vfov     = 20;
    cam.lookfrom = point3(13,2,3);
    cam.lookat   = point3(0,0,0);
    cam.vup      = vec3(0,1,0);

    cam.defocus_angle = 0.6;
    cam.focus_distance = 10;

    cam.render(world);
}

可以看到较为明显的运动痕迹：

image.png

发表于 更新于 分类于 ，
本文字数： 8.9k 阅读时长 ≈ 32 分钟

MAKEFILE教程

之后要尝试做一些项目，在加上前一段时间接触PA，发现自己对自动构建项目一类的操作实在是一知半解，而且之后也需要要尝试自动化编译一些大型的源码，所以学习一下makefile的基本使用，完善一下自己对工具链的认知。这里我看的教程是廖雪峰的makefile入门

Makefile基础

在Linux中我们使用make命令时，他就会在当前目录下找一个名为Makefile的文件，并根据里面的内容进行自动化的执行。我们以下面这个需求为例子：

1
2
a.txt + b.txt -> m.txt
m.txt + c.txt -> x.txt

上述逻辑我们编写makefile

规则

Makefile由各种规则构成，每一条规则需要指出一个目标文件和若干个依赖文件，以及用于生成目标文件的命令，例如我们想要生成m.txt则规则如下：

1
2
3
# 目标文件: 依赖文件1 依赖文件2 依赖文件...
m.txt: a.txt b.txt
	cat a.txt b.txt > m.txt

其中#用来注释，一条规则的格式如上，Tab后使用命令来实现目标文件

现在我们就可以完整的实现上述的规则：

1
2
3
4
5
x.txt: m.txt c.txt
	cat m.txt c.txt > x.txt

m.txt: a.txt b.txt
	cat a.txt b.txt > m.txt

我们可以尝试执行一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
ylin@Ylin:~/Program/test$ make
cat a.txt b.txt > m.txt
cat m.txt c.txt > x.txt
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile  m.txt  x.txt
ylin@Ylin:~/Program/test$ cat x.txt
I am a.txt
I am b.txt
I am c.txt
ylin@Ylin:~/Program/test$ cat m.txt
I am a.txt
I am b.txt
ylin@Ylin:~/Program/test$

make默认执行第一条规则，也就是创建x.txt，但是由于x.txt依赖的文件m.txt不存在（另一个依赖c.txt已存在），故需要先执行规则m.txt创建出m.txt文件，再执行规则x.txt。执行完成后，当前目录下生成了两个文件m.txt和x.txt。

所以我们可以知道，实际上Makefile就是一堆规则(即你些的目标文件和依赖)，当满足规则时，就调用规则后的命令，创建出一个新的目标文件

把默认的规则放在第一条，其他规则的顺序makefile会自动判断依赖。make会把每次执行的命令输出出来，便于我们观察调试。

如果我们在不对任何目标文件进行修改的情况下，我们在此使用make就会得到：

1
2
ylin@Ylin:~/Program/test$ make
make: 'x.txt' is up to date.

make会根据文件的创建和修改时间来判断是否应该更新一个目标文件，例如我们这里只修改c.txt，并不会触发对m.txt的更新，因为他的依赖文件没有发生改变：

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ make
cat m.txt c.txt > x.txt
ylin@Ylin:~/Program/test$ cat x.txt
I am a.txt
I am b.txt
I am c.txt (modified)
ylin@Ylin:~/Program/test$

make只会重新编译那些依赖被修改，或者是尚未完成的部分，重新编译的过程并不是每一条命令都会执行，make只会选择必要的部分执行，我们称这种编译为增量编译。能否正确的实现增量编译，取决于我们编写的规则。

伪目标

为了进一步的便于自动化的构建，有时候我们会需要定义一些常用的规则。例如在我们使用make之后，我们自动生成了m.txt和x.txt，现在我们可以定义一个规则用于清理这些生成的文件:

1
2
3
clean:
	rm -f m.txt
	rm -f x.txt

然后我们可以通过make clean来调用这个规则：

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile  m.txt  x.txt
ylin@Ylin:~/Program/test$ make clean
rm -f m.txt
rm -f x.txt
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile

但是make这里实际上是把clean当作一个目标文件，我们使用make clean规则时，make检查到没有目标文件clean，于是调用命令尝试构建目标文件，但是clean文件不会被生成，所以我们总可以使用它。可是如果目录中有一个clean文件怎么办呢？make认为clean已经被构建了，就不会再使用命令。为了解决这个问题，我们希望make不要将clean视作文件，我们可以添加一个标识：

1
2
3
4
.PHONY: clean
clean:
	rm -f m.txt
	rm -f x.txt

此时，clean就不再被视作一个文件，而是伪目标。一般大型项目会有clean，install一类的常用的伪目标规则，方便用户快速的构建一些任务

执行多条命令

一个规则可以有多条命令：

1
2
3
4
cd:
	pwd
	cd ..
	pwd

运行结果如下： 

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make cd
pwd
/home/ylin/Program/test
cd ..
pwd
/home/ylin/Program/test

我们发现命令cd ..并没有修改当前目录，导致每次输出的pwd都是一样的，这是因为make针对每条指令都会创建一个独立的shell环境，所以命令之间无法互相影响。但是我们可以用以下方法实现

1
2
cd_ok:
	pwd; cd ..; pwd;		# 使用;可以将多个命令写在一行(顺序执行,不管成功还是失败)

我们查看新的执行结果：

1
2
3
4
ylin@Ylin:~/Program/test$ make cd_ok
pwd; cd ..; pwd;
/home/ylin/Program/test
/home/ylin/Program

当然也可以再;后加\便于分行阅读：

1
2
3
4
cd_ok:
	pwd; \
	cd ..; \
	pwd

我们需要注意，在shell中;代表无论当前命令是否生效，都会执行下一个命令。与其相反的一个执行多条命令的语法是&&，当前面的命令执行失败时，后续的命令就不会再继续执行了

控制打印

默认情况下，make会打印出执行的每一条命令，如果我们不想打印某一条命令，我们只需要在命令前面加上@，告诉make不打印该命令：

1
2
3
no_output:
	@echo 'no display'
	echo 'will display'

执行结果如下：

1
2
3
4
ylin@Ylin:~/Program/test$ make no_output
not display
echo 'will display'
will display

控制错误

make在执行命令时，会检查每一条命令的返回值，如果返回值错误，就会中断执行。

例如我们手动构建一个错误（用rm删除一个不存在的文件）：

1
2
3
has_error:
	rm zzz.txt
	echo 'OK'

会发生：

1
2
3
4
ylin@Ylin:~/Program/test$ make has_error
rm zzz.txt
rm: cannot remove 'zzz.txt': No such file or directory
make: *** [Makefile:25: has_error] Error 1

但是有时候我们希望忽略错误，我们可以在特定的指令前面加上-用来忽略错误的命令：

1
2
3
ignore_error:
	-rm zzz.txt
	echo 'ok'

输出结果如下：

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make ignore_error
rm zzz.txt
rm: cannot remove 'zzz.txt': No such file or directory
make: [Makefile:29: ignore_error] Error 1 (ignored)
echo 'ok'
ok

对于执行可能出错，但是不影响逻辑的命令，可以使用-忽略

编译C程序

现在我们尝试一下编译一个简单的C语言程序，其依赖文件如下：

1
2
3
main.c + hello.h -> main.o
hello.c -> hello.o
hello.o + main.o -> a.out

文件内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// main.c
#include "hello.h"
#include <stdio.h>

int main() {
    printf("starting main\n");
    hello();
    printf("ending main\n");
    return 0;
}

// hello.h
int hello();

// hello.c
#include <stdio.h>
int hello() {
    printf("Hello, World!\n");
    return 0;
}

我们可以编写以下规则，用于自动构建可执行程序：

1
2
3
4
5
6
7
8
a.out: main.o hello.o
	cc -o a.out main.o hello.o
main.o: main.c hello.h
	cc -c main.c
hello.o: hello.c hello.h
	cc -c hello.c
clean:
	rm -f a.out main.o hello.o

同时也可以通过make clean来删除中间文件：

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ ls
a.out  hello.c  hello.h  hello.o  main.c  main.o  Makefile
ylin@Ylin:~/Program/test$ make clean
rm -f a.out main.o hello.o
ylin@Ylin:~/Program/test$ ls
hello.c  hello.h  main.c  Makefile

我们可以看到完整的命令流程如下：

1
2
3
4
5
ylin@Ylin:~/Program/test$ make clean && make
rm -f a.out main.o hello.o
cc -c main.c
cc -c hello.c
cc -o a.out main.o hello.o

隐式规则

为了编译这个项目，我们一共编写了三条规则，现在我们尝试删除两个.o文件的规则，然后再编译试试：

1
2
3
4
5
a.out: main.o hello.o
	cc -o a.out main.o hello.o

clean:
	rm -f a.out main.o hello.o

然后我们执行make，输出如下：

1
2
3
4
ylin@Ylin:~/Program/test$ make
cc    -c -o main.o main.c
cc    -c -o hello.o hello.c
cc -o a.out main.o hello.o

然后可以发现 我们并没有制定相关的规则，可是程序还是正常的进行了编译，这是make中的隐式规则，因为make本来就是为了编译C程序设计的，所以为了避免重复的编译.o文件，在一开始没有找到对应的规则时，会自动的调用隐式规则。对于C C++ ASM ...等程序，都有内置的隐式规则，这里不展开叙述。

使用变量

我们在编译时难免会遇到许多重复的文件名，为了方便使用，我们引入变量用来解决重复的问题。我们以上一节的Makefile为例：

1
2
3
4
5
a.out: main.o hello.o
	cc -o a.out main.o hello.o

clean:
	rm -f a.out main.o hello.o

我们可以定义一个变量来替换它：

1
2
3
4
5
6
7
TARGET = a.out

$(TARGET): main.o hello.o
	cc -o $(TARGET) main.o hello.o

clean:
	rm -f $(TARGET) main.o hello.o

对于变量定义，我们使用变量名 = 值，变量名通常使用大写。在引用变量时通常使用$(变量名)

当然，对于我们的依赖文件列表，也可以使用变量进行替换：

1
2
3
4
5
6
7
8
TARGET := a.out
OBJS := main.o hello.o

$(TARGET): $(OBJS)
	cc -o $(TARGET) $(OBJS)

clean:
	rm -f $(TARGET) $(OBJS)

但是对于依赖文件很多的情况下，我们可能需要一个自动化的方式，来将我们的源文件批量编译成目标文件。我们注意到每个.o文件都是由对应的.c文件编译产生的，我们可以让make先获取.c文件列表再替换生成得到.o文件列表：

1
2
3
4
5
6
7
8
9
10
TARGET := a.out
# wildcard意为通配符,即使用通配符去匹配*.c
# patsubst是pattern substitute的缩写,即模式替换,参数为(源模式,目标模式,文件列表)
OBJS := $(patsubst %.c,%.o,$(wildcard *.c))

$(TARGET): $(OBJS)
	cc -o $(TARGET) $(OBJS)

clean:
	rm -f $(TARGET) $(OBJS)

内置变量

为了方便我们使用，make也内置了很多的内置变量，例如我们可以用$(CC)替换命令cc:

1
2
$(TARGET): $(OBJS)
	$(CC) -o $(TARGET) $(OBJS)

这样方便我们在交叉编译时，指定编译器。诸如此类的内置变量还有很多，遇到了再学吧。

自动变量

在makefile中，经常会看到$@、$<之类的变量，这种变量称为自动变量，它们在一个规则中自动指向某个值。例如$@标识目标文件，$^表示所以依赖文件，所以我们也可以这样写：

1
2
3
4
5
a.out: hello.o main.o
	@echo '$$@ = $@' # 变量 $@ 表示target
	@echo '$$< = $<' # 变量 $< 表示第一个依赖项
	@echo '$$^ = $^' # 变量 $^ 表示所有依赖项
	cc -o $@ $^

模式规则

我们前面提到隐式转换可以在必要时自动创建.o文件，但实际上隐式规则的命令是固定的：

1
$(CC) $(CFLAGS) -c -o $@ $<

我们只能修改编译器变量和编译选项变量，但没办法运行多条命令。

此时我们就要引入自定义模式规则，它使用make的匹配模式规则，如果匹配上了，就自动创建一条模式规则，我们可以把我们的makefile写成以下内容：

1
2
3
4
5
6
7
8
9
10
11
12
TARGET := a.out
OBJS := $(patsubst %.c,%.o,$(wildcard *.c))

$(TARGET): $(OBJS)
	$(CC) -o $(TARGET) $(OBJS)

%.o: %.c
	@echo "Compiling $< to $@"
	$(CC) -c $< -o $@

clean:
	rm -f $(TARGET) $(OBJS)

当程序执行a.out: hello.o main.o时，发现没有hello.o，于是查找以hello.o为目标文件的规则，结果匹配到模式规则*.o : *.c，于是模式规则会动态的创建以下规则：

1
2
3
hello.o: hello.c
	@echo "Compiling $< to $@"
	$(CC) -c $< -o $@

我们可以尝试执行一下make:

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make
Compiling hello.c to hello.o
cc -c hello.c -o hello.o
Compiling main.c to main.o
cc -c main.c -o main.o
cc -o a.out hello.o main.o

这样他可以比隐式的规则更灵活。但是我们现在也遇到一个问题，就是当我们修改hello.h头文件时，不会触发main.c重新编译的问题，我们之后在解决。

自动完成依赖

我们刚刚提到，在我们可以解决自动把.c编译成.o文件，但是难以解决.c文件对.h文件的依赖规则。因为要想知道.h的依赖关系，我们需要分析文件内容才能做到，并没有一个简单的文件名映射规则。

好在我们可以使用gcc提供的-MM参数，自动分析我们所需要的.h文件参数：

1
2
ylin@Ylin:~/Program/test$ cc -MM main.c
main.o: main.c hello.h

因此，我们可以利用这个功能，为每个.c文件都生成一个依赖项，并把它保存到.d(中间文件中)，再使用include将其导入makefile中，这样我们就精准的实现了.c文件的依赖分析。

我们可以更新我们的makefile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TARGET := a.out
SRCS := $(wildcard *.c)
OBJS := $(SRCS:.c=.o)
DEPS := $(SRCS:.c=.d)

$(TARGET): $(OBJS)
	$(CC) -o $@ $^

%.d: %.c
	rm -f $@; \
	$(CC) -MM $< >$@.tmp; \
	sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.tmp > $@; \
	rm -f $@.tmp

%.o: %.c
	$(CC) -c $< -o $@

clean:
	rm -f $(TARGET) $(OBJS) $(DEPS)

include $(DEPS)

当我们运行时，通过include会引入.d文件，但是一开始.d文件并不存在，这时会通过模式规则匹配到%.d: %.c。这里用了一个复杂的sed将.d文件创建了出来。我们运行make结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
ylin@Ylin:~/Program/test$ make
rm -f main.d; \
cc -MM main.c >main.d.tmp; \
sed 's,\(main\)\.o[ :]*,\1.o main.d : ,g' < main.d.tmp > main.d; \
rm -f main.d.tmp
rm -f hello.d; \
cc -MM hello.c >hello.d.tmp; \
sed 's,\(hello\)\.o[ :]*,\1.o hello.d : ,g'< hello.d.tmp > hello.d; \
rm -f hello.d.tmp
cc -c hello.c -o hello.o
cc -c main.c -o main.o
cc -o a.out hello.o main.o

我们可以看到.d文件中类似：

1
main.o main.d : main.c hello.h

现在，我们文件的依赖就加入了头文件，当我们对头文件进行修改时，就会触发重新编译

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ make
rm -f main.d; \
cc -MM main.c >main.d.tmp; \
sed 's,\(main\)\.o[ :]*,\1.o main.d : ,g' < main.d.tmp > main.d; \
rm -f main.d.tmp
cc -c main.c -o main.o
cc -o a.out hello.o main.o

完善Makefile

我们现在对项目目录进行整理，我们将源码放入src目录，将编译生成的文件放入build目录：

1
2
3
4
5
6
7
8
ylin@Ylin:~/Program/test$ tree .
.
├── build
├── Makefile
└── src
    ├── hello.c
    ├── hello.h
    └── main.c

现在我们可以使用我们上述的操作，更新我们的makefile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
SRC_DIR := ./src
BUILD_DIR := ./build
TARGET = $(BUILD_DIR)/a.out

CC = gcc
CFLAGS = -Wall

SRCS = $(wildcard $(SRC_DIR)/*.c)
OBJS = $(patsubst $(SRC_DIR)/%.c,$(BUILD_DIR)/%.o,$(SRCS))
DEPS = $(patsubst $(SRC_DIR)/%.c,$(BUILD_DIR)/%.d,$(SRCS))

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CC) -o $@ $^

$(BUILD_DIR)/%.d: $(SRC_DIR)/%.c
	@mkdir -p $(BUILD_DIR)
	rm -f $@; \
	$(CC) -MM $< >$@.tmp; \
	sed 's,\($*\)\.o[ :]*,$(BUILD_DIR)\1.o $@ : ,g' < $@.tmp > $@; \
	rm -f $@.tmp

$(BUILD_DIR)/%.o: $(SRC_DIR)/%.c
	@mkdir -p $(BUILD_DIR)
	$(CC) $(CFLAGS) -c -o $@ $<

clean:
	@echo "Cleaning up..."
	rm -rf $(BUILD_DIR)

include $(DEPS)

我们通过设置目录路径变量实现了对一个简单项目的自动化编译。至此我们的对makefile的基本使用就了解了

对于makefile，它还有很多的复杂的用法，但是之后我会更好的利用它去做更多的项目。

发表于 分类于
本文字数： 802 阅读时长 ≈ 3 分钟

上个月都没怎么学习，几乎每天都在发呆想事情，因为我和一个傻瓜的事情。前几天去北京和她在一起呆了很久呀，感觉她还是像以前一样对我很好。但是可能异地恋的负担对于她来说还是太大了，所以我也不强求什么了。只求我能努力一点，以后和她一起去北京读书。我和她约好了我会去找她，会陪着她。

她对我一直都很好，很爱我的一个女生，我们从高一在一起，到十月底我们就刚好在一起四年了。我们俩的感情很好，但是我感觉自己还总是没有考虑到她的感受，导致我们的感情总是她一个人承担，所以她真的好幸苦。现在她累累的，就轮到我来照顾她了。我打算好好学习，研究生去北京陪她一起，在她需要我的时候能一直在她身边。

然后这次去北京，听北理的老师和其他高校的学生交流，感觉触动还是很大的吧。感觉他们的眼里都是有光的，他们有自己想做的事，想要做到的事，和自己热爱的事情。而且他们的技术氛围也很好，我感觉自己一直是固步自封，偏于一隅，眼光和格局一直放的很小，总是安于当下。我感觉自己就像一个游魂，每天就是想干啥就干啥，以前我觉得这是一种坦然，现在我感觉这是一种迷茫吧。我应该好好接受生活，体验各种事情，学习各种事情，我想接受更多的东西，不仅仅是知识和技术上的内容。

要做的事情很多呀，确实会很辛苦，但是我认为这是一件很值得的事情。我想和我喜欢的女生在一起，希望自己优秀一点，以后能一直陪在她身边，保护她，我爱她。现在我也不知道应该做什么吧，先把这个学期要学的东西都先学起来，争取这个学期把绩点做好一点，如果有机会保研的话就保研，如果不行的话就考研。

这个月暂时就是整理一下自己，然后开始学一些概率论和离散数学好了，还有一些408的课程。以前我总是不太能接受这些干巴巴的知识，我也更喜欢自己亲自动手实践，但是现在也慢慢开始理解和去接受他们的重要性了。接下来的时间，重要的事情就是先把概率论和离散数学好好学一下。尤其是离散数学，其实我一直都很感兴趣，但是苦于不知道怎么开始学习。

有空的话我想把图形学捡起来好好学一下，打算重构一遍上个学期写的内容，然后进一步的学习一下。

感觉身体也很重要，要做的事情很多，我还要接着加油。

发表于 更新于 分类于 ，
本文字数： 2.9k 阅读时长 ≈ 11 分钟

这一篇博客中,我将完成PA1的收尾部分，我将完成完成对表达式求值的功能拓展，和程序监视点的实现，预计要花费较多的时间。可能很多内容也需要好好学习理解一下。

PA1 监视点

扩展表达式求值的功能

之前我们实现了算数表达式基本的求值（对整数的基本四则运算与结合律），但这些表达式都是常数组成的，他们的值不会发生变化，导致这样的表达式在监视点中没有任何意义，所以我们需要为我们的表达式拓展以下功能：

1
2
3
4
5
6
7
8
9
10
11
12
<expr> ::= <decimal-number>
  | <hexadecimal-number>    # 以"0x"开头
  | <reg_name>              # 以"$"开头
  | "(" <expr> ")"
  | <expr> "+" <expr>
  | <expr> "-" <expr>
  | <expr> "*" <expr>
  | <expr> "/" <expr>
  | <expr> "==" <expr>
  | <expr> "!=" <expr>
  | <expr> "&&" <expr>
  | "*" <expr>              # 指针解引用

那么首先我们就需要向框架中添加对应的解析，即更新程序的正则匹配逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
enum {
  TK_NOTYPE = 256, 
  TK_EQ, TK_NEQ, TK_AND,
  TK_HEX, TK_NUM, TK_REG,
};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {
  {" +", TK_NOTYPE},                // spaces
  {"==", TK_EQ},                    // equal
  {"!=", TK_NEQ},                   // unequal
  {"&&", TK_AND},                   // and
  {"\\+", '+'},                     // plus
  {"-", '-'},                       // minus
  {"\\*", '*'},                     // multi
  {"/", '/'},                       // div
  {"\\(", '('},                     // left brace
  {"\\)", ')'},                     // right brace
  {"0[xX][0-9a-fA-F]+", TK_HEX},    // hex number
  {"[0-9]+", TK_NUM},               // number
  {"\\$(zero|ra|sp|gp|tp|t[0-6]|s[0-9]|s1[0-1]|a[0-7])", TK_REG},   // reg
};

这里需要注意两个问题：

  • 一是 对于reg值得获取，框架代码在/src/isa/$ISA/reg.c中提供了isa_reg_str2val()作为接口，它将返回名字为s的寄存器的值，且设置success用于指示是否匹配成功。

  • 二是 我们需要注意到对指针解引用的识别，对于符号*它可能是乘号，也可能是对地址的解引用。实际上我们可以通过看其前一个标识的类型，我们就可以判断它的用法，所以可以给出框架代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    if (!make_token(e)) {
      *success = false;
      return 0;
    }

    /* TODO: Implement code to evaluate the expression. */
    for (i = 0; i < nr_token; i ++) {						// certain type 视具体情况而定
      if (tokens[i].type == '*' && (i == 0 || tokens[i - 1].type == certain type) ) {
        tokens[i].type = DEREF;
      }
    }

    return eval(?, ?);

现在我们开始进一步的拓展我们的表达式的能力：

寄存器接口完善

我们需要根据$后的寄存器名，来获取对应的寄存器的值，并设置success:

1
2
3
4
5
6
7
8
9
word_t isa_reg_str2val(const char *s, bool *success) {
  *success = true;
  if(!strcmp(s,"zero")) return 0;
  for(int i=0;i<32;i++){
    if(!strcmp(s,regs[i])) return cpu.gpr[i];
  }
  *success = false;
  return -1;
}

当发现寄存器返回值为-1时，则说明寄存器名称错误，我们要停止计算

表达式计算拓展

我们添加的功能有十六进制数的解析、寄存器的解析、还有部分简单逻辑运算的解析，我们依次分析，需要在哪些地方添加哪些功能：

首先是token的解析存储阶段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
switch (rules[i].token_type) {
          case TK_HEX:
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[nr_token].str[j] = substr_start[j];
            tokens[nr_token].str[substr_len]='\0';
            break;
          case TK_NUM:  
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[nr_token].str[j] = substr_start[j];
            tokens[nr_token].str[substr_len]='\0';
            break;
          case TK_REG:
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len-1;j++)
              tokens[nr_token].str[j] = substr_start[j+1];
            tokens[nr_token].str[substr_len-1]='\0';
            break;
        ...
}

我们添加了对十六进制标识符和寄存器的存储。

同时我们也要注意在eval()，由于我们引入了十六进制和寄存器进入表达式解析中，所以对于最小的子表达式

1
2
3
<expr> ::= <decimal-number>
  | <hexadecimal-number>   
  | <reg_name>

我们的解析应该展开为：

1
2
3
4
5
6
7
8
9
10
11
12
...
else if(start==end){
    if(tokens[start].type==TK_REG){
      bool success = false;
      word_t val = isa_reg_str2val(tokens[start].str,&success);
      if(success) return val;
      printf("Invalid register name: %s\n", tokens[start].str);
      return -1;
    }
    return strtol(tokens[start].str,NULL,0);
}
...

由于我们添加了逻辑表达式，所以我们还需要更新其对表达式的拆分和运算，首先是运算部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case TK_EQ: return (val1==val2);
      case TK_NEQ: return (val1!=val2);
      case TK_AND: return (val1&&val2);
      case '+': return val1+val2;
      case '-': return val1-val2; 
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
...

与之而来的问题是，在引入逻辑表达式之后，我们该怎么拆分我们的表达式呢？我们知道对于目前已有的运算符，我们有* / > + - >逻辑运算的优先级关系，所以我们可以根据上一节中的规则来更新我们的主运算符号的选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static int get_token(int start, int end){
  int token = -1;
  int par = 0;
  int min_priority = -1;
  for(int i=start;i<=end;i++){
    int tmp=tokens[i].type;
    if(tmp==TK_NUM) continue;
    if(tmp=='(') par++;
    else if(tmp==')'){
      par--;
      if(par<0) return -1;
    }
    if(par!=0) continue;
    switch (tmp){
    case TK_EQ: case TK_NEQ: case TK_AND:
      if(min_priority<=3){
        min_priority=3;
        token=i;
      }
      break;
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
  }
  if(token != -1){
    // Log("Main operator: %c at position %d\n", tokens[token].type, token);
  } else {
    printf("No operator found in range [%d, %d]\n", start, end);
  }
  return token;
}

至此，我们就完成了对于运算符的解析和拓展。

解引用分析

最后我们还需要解决的一个问题就是对于指针的解引用，我们根据框架代码，对负号和解引用的标识符进行替换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  for(int i=0;i<nr_token;i++){
    if((tokens[i].type=='*'||tokens[i].type=='-')&&
        (i==0||
        tokens[i-1].type=='+'||
        tokens[i-1].type=='-'||
        tokens[i-1].type=='*'||
        tokens[i-1].type=='/'||
        tokens[i-1].type=='('||
        tokens[i-1].type==TK_AND||
        tokens[i-1].type==TK_EQ||
        tokens[i-1].type==TK_NEQ)
      ){
        if(tokens[i].type == '*') tokens[i].type = DEREF;
        else tokens[i].type = NEGATIVE;
    }
  }
  word_t val = eval(0,nr_token-1);
  *success = (val!=-1);
  return val;
}

由于他们都是一元运算符，在计算的过程中拥有最高的优先级，所以我们需要更新搜索主运算符的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
...
switch (tmp){
    case DEREF: case NEGATIVE:
      if(min_priority<=0){
        min_priority=0;
        token=i;
      }
      break;
    case TK_EQ: case TK_NEQ: case TK_AND:
      if(min_priority<=3){
        min_priority=3;
        token=i;
      }
      break;
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
...

然后再最终的对表达式的整合中优先处理一元运算符号，再处理二元运算符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }

    if(tokens[op].type == DEREF || tokens[op].type == NEGATIVE) {
      word_t val = eval(op+1, end);
      if(val == -1) return -1;
      if(tokens[op].type == DEREF) return vaddr_read(val, 4);
      else return -val;
    }
    
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case TK_EQ: return (val1==val2);
      case TK_NEQ: return (val1!=val2);
      case TK_AND: return (val1&&val2);
      case '+': return val1+val2;
      case '-': return val1-val2; 
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
...

至此我们完成了对表达式运算符的拓展。

实现监视点

监视器允许我们设置监视点，当监视点中的表达式满足时，nemu就将nemu_state设置成NEMU_STOP，此时我们就可以对程序状态进行观察。

不过首先我们需要能够将所有监视点管理组织起来，在框架代码中已经定义好了监视点的结构和监视点池的结构：

1
2
3
4
5
6
7
8
9
10
typedef struct watchpoint {
  int NO;	// 监视器的编号
  struct watchpoint *next;

  /* TODO: Add more members if necessary */

} WP;

static WP wp_pool[NR_WP] = {};
static WP *head = NULL, *free_ = NULL;

我们需要管理两个链表head和free_。head用于存放使用中的监视点结构，free_用于组织空闲的监视点结构，我们可以使用init_wp_pool()函数，对两个链表进行初始化。

为了进一步的管理监视点池，我们需要两个函数：

  • WP* new_wp()：用于从空闲的监视点池中选择一个监视点进行使用，同时也要对剩余监视点的数量进行判断
  • void free_wp(WP* wp)： 用于将正在使用中的监视点存回空闲链表中

实现了对监视点池的管理之后，我们就需要实现监视点的相关功能了（以下是需要完成的要求）：

  • 当用户给出一个待监视表达式时, 你需要通过new_wp()申请一个空闲的监视点结构, 并将表达式记录下来. 然后在trace_and_difftest()函数(在nemu/src/cpu/cpu-exec.c中定义)的最后扫描所有的监视点, 每当cpu_exec()的循环执行完一条指令, 都会调用一次trace_and_difftest()函数. 在扫描监视点的过程中, 你需要对监视点的相应表达式进行求值(你之前已经实现表达式求值的功能了), 并比较它们的值有没有发生变化, 若发生了变化, 程序就因触发了监视点而暂停下来, 你需要将nemu_state.state变量设置为NEMU_STOP来达到暂停的效果. 最后输出一句话提示用户触发了监视点, 并返回到sdb_mainloop()循环中等待用户的命令.
  • 使用info w命令来打印使用中的监视点信息, 至于要打印什么, 你可以参考GDB中info watchpoints的运行结果.
  • 使用d命令来删除监视点, 你只需要释放相应的监视点结构即可.

监视点池的管理

这里我想监视点的结构中添加了一个used属性，用来判断当前监视点是否被启用，据此，我们就可以实现对监视点池中的监视点的使用和空闲的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
WP* new_wp(){
  if(free_==NULL){
    printf("No free watchpoint avilable\n");
    return NULL;
  }
  WP* wp = free_;
  free_ = free_->next;
  wp->used = 1;
  wp->next = head;
  head = wp;
  printf(ANSI_FMT("Create watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
  return wp;
}

void free_wp(WP* wp){
  if(wp==NULL||!wp->used) printf("Invalid watchpoint to free\n");
  if(head==wp){
    head = head->next;
  }else{
    WP* prev = head;
    while(prev!=NULL&&prev->next!=wp) prev = prev->next;
    if(prev!=NULL) prev->next = wp->next;
    wp->used=0;
    wp->next = free_;
    free_ = wp;
    printf(ANSI_FMT("Free watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
  }
}

现在我们需要进一步的完成监视点的功能，以及用于调用的接口

监视点功能实现

监视点的功能实际上就是在每一次执行之后，遍历一遍监视点链表，如果设置的表达式发生了改变，那么我们说监视点被触发了。所以我们要做的事情很简单，遍历计算表达式的值是否发生改变，如果是，则触发监视点：

1
2
3
4
5
6
7
8
9
10
11
12
13
void wp_diff(){
  WP* wp = head;
  while(wp){
    bool _;
    word_t new = expr(wp->expr,&_);
    if(wp->val!=new){
      printf(ANSI_FMT("Watchpoint #%d: %s\n Old value = 0x%08x\n New value = 0x%08x\n",ANSI_FG_BLUE),wp->NO,wp->expr,wp->val,new);
      wp->val = new;
      nemu_state.state = NEMU_STOP;
    }
    wp = wp->next;
  }
}

由于NEMU在每次执行时都会在execute()中调用trace_and_difftest()我们在这个程序中加入每次对监视点的判断wp_diff()

现在我们只需要进一步完成监视点的接口，使得我们可以方便的创建销毁查看他们：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
P* new_wp(){
  if(free_==NULL){
    printf("No free watchpoint avilable\n");
    return NULL;
  }
  WP* wp = free_;
  free_ = free_->next;
  wp->used = 1;
  wp->next = head;
  head = wp;
  return wp;
}

WP* NO2wp(int i){
  return &wp_pool[i];
}

void free_wp(WP* wp){
  if(wp==NULL||!wp->used){printf("Invalid watchpoint to free\n");return;}
  if(head==wp){
    head = head->next;
  }else{
    WP* prev = head;
    while(prev!=NULL&&prev->next!=wp) prev = prev->next;
    if(prev!=NULL) prev->next = wp->next;
    wp->used=0;
    wp->next = free_;
    free_ = wp;
  }
  printf(ANSI_FMT("Free watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
}

void wp_set(char* expr,word_t val){
  WP* wp = new_wp();
  strcpy(wp->expr,expr);
  wp->val = val;
  printf(ANSI_FMT("Create watchpoint #%d: %s\n",ANSI_FG_BLUE),wp->NO,wp->expr);
}

void wp_display(){
  WP* tmp = head;
  while(tmp!=NULL){
    tmp = tmp->next;
  }
}

我们在终端进行调用，实现info w，d NO，w EXPR等功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int cmd_w(char* args){
  bool success = false;
  word_t val = expr(args,&success);
  if(!success){
    printf("Invalid expression: %s\n",args);
  }else{
    wp_set(args,val);
  }
  return 0;
}

static int cmd_d(char* args){
  int NO = atoi(args);
  free_wp(NO2wp(NO));
  return 0;
}

void wp_display(){
  WP* tmp = head;
  while(tmp!=NULL){
    printf("Watchpoint #%d -> %s\n",tmp->NO,tmp->expr);
    tmp = tmp->next;
  }
}

至此我们就实现了监视点的功能。

对于断点我们可以通过w $pc=？的方式来让程序停止

发表于 更新于 分类于 ，
本文字数： 2.6k 阅读时长 ≈ 9 分钟

我们先前反复提到了一个式子EXPR，它代表着表达式含义，常见的表达式是通过操作符连接的。这里我们需要为我们的框架实现一个表达式求值的功能。我们要解决的问题是求值一个字符串表示的表达式。

PA1 表达式求值

为了简单起见，我们先从数学表达式求值实现开始。

数学表达式求值

如下的一个表达式的字符串：

1
"5 + 4 * 3 / 2 - 1"

我们应该怎么求出它的值？我们可以分成两个简单的步骤：

  • 首先识别出表达式中的单元
  • 根据表达式的归纳定义进行递归求值

词法分析

词法分析要做的事情就是识别出表达式中的单元，这里的单元指的就是有着独立含义的子串，我们称之为token。具体而言我们需要将表达式中所有的单元都赋予一个标签，方便之后根据标签来对表达式进行处理。这里我们使用正则表达式来对token进行处理。

出于简单起见，这里我们暂时只对以下的token类型进行处理：

  • 十进制整数
  • +，-，*，/
  • (，)
  • 空格串（一个或者多个空格）

首先我们需要使用正则表达式来编写用于识别这些token类型的规则，框架中演示了怎么对其进行匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"==", TK_EQ},        // equal
};

这些规则，在init_sdb()时调用了init_regex()来将其编译成正则结构体并存储在re中：

1
2
3
4
5
6
7
8
9
10
11
12
void init_regex() {
  int i;
  char error_msg[128];
  int ret;
  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

如果编译不通过，可能是你编写的token匹配的规则不符合正则表达式的语法。现在，我们可以给出一个待匹配的表达式，我们利用make_token()来识别出其中的token。用position变量指示当前待匹配的位置，然后按顺序对当前位置的字符串进行匹配。当一个规则匹配成功，并且匹配出的字串属于position指出的位置时，我们就成功的识别出了一个token。我们则使用Token结构体来将它的内容记录下来。

1
2
3
4
5
6
typedef struct token {
  int type;
  char str[32];
} Token;
static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

其中type成员用于记录token的类型，然后str用来保存token相应的字串。tokens数组用来保存识别出的token信息，而nr_token则用来指示被识别出的token数目。

现在我们需要向算数表达式中的各种tokens类型添加规则，在成功识别出tokenhi后，将token的信息一次记录到tokens数组之中。

1
2
3
4
5
6
7
8
9
10
11
12
rules[] = {
  // 这里需要注意对这些内容的匹配是有优先顺序的，从上到下
  {" +", TK_NOTYPE},    // spaces
  {"==", TK_EQ},        // equal
  {"\\+", '+'},         // plus
  {"-", '-'},           // minus
  {"\\*", '*'},         // multi
  {"/", '/'},       	// div
  {"\\(", '('},         // left brace
  {"\\)", ')'},         // right brace
  {"[0-9]+", TK_NUM},   // number
};

然后我们就需要将匹配到的token放入tokens中，并对它的各个字段进行赋值。对于大多数类型，我们只需要简单的保存它的类型就行了，但是对于有数据内容的token，我们需要保存它的data，在这里既是保存它的子串内容信息，方便我们进行进一步的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static bool make_token(char *e) {
  int position = 0;
  int i;
  int index=0;
  regmatch_t pmatch;
  nr_token = 0;
  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;
        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);
        position += substr_len;
        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        switch (rules[i].token_type) {
          case TK_NUM:  
            tokens[index].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[index].str[j] = substr_start[j];
            // printf("The num is %s\n",tokens[index].str);
            break;
          default:
            tokens[index].type = rules[i].token_type;
        }
        index++;
        break;
      }
    }
    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }
  return true;
}

我们可以看到整个识别token的过程，每当我们获取一个token时，我们都会使用Log()将它的匹配规则，子串下标，子串长度，和对应的子串信息打印出来。便于我们观察标识符匹配的中间过程。对于未匹配到的类型，我们也会将其内容进行返回。

中间部分则是我们对token信息的存储过程，目前我们只对十进制整数的内容进行了保存，对于其他的标识符号，则是简单的保存类型。现在我们可以进一步的进行表达式求值了。

递归求值

我们现在将求值表达式的token识别出来之后就可以进行求值了。我们现在是对token数组进行处理，方便起见，我们称其为token表达式。（将空格忽略）

接下来，根据表达式的归纳定义特性，我们可以使用递归来进行求值：

1
2
3
4
5
6
<expr> ::= <number>    # 一个数是表达式
  | "(" <expr> ")"     # 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>  # 两个表达式相加也是表达式
  | <expr> "-" <expr>  # 接下来你全懂了
  | <expr> "*" <expr>
  | <expr> "/" <expr>

这种表示方法就是我们常说的BNF，我们可以这里理解，长表达式是由短表达式构成的，那么我们可以先对短表达式进行求值，然后再进一步的对长表达式进行求值。

为了在token表达式中指示一个子表达式，我么可以使用两个整数p和q来指示子表达式的开始和结束位置，现在我们就可以写出一个求值函数的框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    /* We should do more things here. */
  }
}

其中check_parentheses()用于判断表达式是否被一堆匹配的括号所包围，同时检查表达式左右的括号是否匹配，如果不匹配，那么这个表达式就是非法的。我们以此来尝试实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
static int check_parentheses(int start, int end){
  int cond=0;
  if(tokens[start].type!='('||tokens[end].type!=')') return 0;
  for(int i=start;i<=end;i++){
    if(tokens[i].type=='(') cond++;
    if(tokens[i].type==')'){
      cond--;
      if(cond<0) return -1;
    }
    if(cond==0) return (i == end) ? 1 : 0;
  }
  return (cond==0)?1:-1;
}

现在我们的框架代码，已经可以处理BNF的开始两种情况啦。像现在我们需要进一步的考虑剩下的情况，即四则运算的处理。但是问题在于，我们怎么对一个长表达式处理，将其分解为各个小的短表达式，并保证语法的正确呢？

我们以下为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"4 + 3 * ( 2 - 1 )"
/*********************/
case 1:
    "+"
   /   \
"4"     "3 * ( 2 - 1 )"
case 2:
        "*"
       /   \
"4 + 3"     "( 2 - 1 )"
case 3:
              "-"
             /   \
"4 + 3 * ( 2"     "1 )"

我们可以看到只有第一种情况是正确的，第二种情况违背了算术符号的优先级，而第三种情况则使得表达式的括号不再匹配。通过以上的例子，我们就可以总结出寻找主运算符（可以将一个长表达式分解成两个短表达式的运算符号）的逻辑了：

  • 非运算符的token不是主运算符
  • 出现在一对括号中的token不是主运算符号
  • 主运算符的优先级在表达式中应该是最低的
  • 有多个运算符的优先级最低时，根据结合性，最后被结合的运算符为主运算符号

现在我们根据以上规则来扫描出每个表达式中的主运算符号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static int get_token(int start, int end){
  int token = -1;
  int par = 0;
  int min_priority = -1;
  for(int i=start;i<=end;i++){
    int tmp=tokens[i].type;
    if(tmp==TK_NUM) continue;
    if(tmp=='(') par++;
    else if(tmp==')'){
      par--;
      if(par<0) return -1;
    }
    if(par!=0) continue;
    switch (tmp){
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
  }
  if(token != -1){
    // Log("Main operator: %c at position %d\n", tokens[token].type, token);
  } else {
    printf("No operator found in range [%d, %d]\n", start, end);
  }
  return token;
}

找到表达式的主运算符之后，事情就变得简单了，我们先对两个分裂出来的子表达式进行递归求值，然后根据主运算符号的两个子表达式进行计算即可，现在我们的框架代码更新如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    op = the position of 主运算符 in the token expression;
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);

    switch (op_type) {
      case '+': return val1 + val2;
      case '-': /* ... */
      case '*': /* ... */
      case '/': /* ... */
      default: assert(0);
    }
  }
}

现在，我们需要利用现有的规则和函数来填补实现我们的求值函数eval():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static int eval(int start, int end){
  if(start>end){
    printf("Unknown expression.\n");
    return -1;
  }else if(start==end){
    return atoi(tokens[start].str);
  }else if(check_parentheses(start,end)==1){
    return eval(start+1,end-1);
  }else if(check_parentheses(start,end)==-1){
    printf("parenthese mismatch error\n");
    return -1;
  }else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case '+': return val1+val2;
      case '-': return val1-val2;
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
}

经过测试，基本可以处理大多数情况了。我们现在可以将其封装在expr()中，然后实现p方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  word_t val = eval(0,nr_token-1);
  *success = (val!=-1);
  return val;
}

static int cmd_p(char* args){
  bool success;
  word_t val=expr(args,&success);
  if(success==true)
    printf("%d\n",val);
  return 0;
}

出于限制，我们只使用uint32_t作为我们的返回类型。

测试代码

按照PA的要求，我们现在应该测试一下我们这个函数，但是我就跳过这一部分了，因为赶时间。

发表于 分类于 ，
本文字数： 1.3k 阅读时长 ≈ 5 分钟

NEME是一个用于执行其他用户程序的虚拟计算机，对于运行在NEMU中的应用程序，外部的调试器难以获取其详细的信息，往往需要对引用程序内部下断点的方法来观察程序运行。

但是对于NEMU而言，应用程序的状态是可见的，因此我们需要一个简单有效的方法来观察并调试应用程序的内部状态，所以我们需要设计简易调试器，作为NEMU的基础设施，方便日后的进一步处理。

PA1 基础设施

我们需要在monitor中实现一个简单的sdb。相关的框架代码存放在src\monitor\sdb中，我们可以在cmd_table中查看目前已有的指令。

1
2
3
4
5
6
7
8
9
10
static struct {
  const char *name;
  const char *description;
  int (*handler) (char *);
} cmd_table [] = {
  { "help", "Display information about all supported commands", cmd_help },
  { "c", "Continue the execution of the program", cmd_c },
  { "q", "Exit NEMU", cmd_q },
  /* TODO: Add more commands */
};

在PA1中我们要实现的功能还有：

image.png

今天则从最基本的三个功能开始实现：

  • 单步执行
  • 打印寄存器状态
  • 扫描内存状态

解析命令

NEMU通过库对命令行输入进行处理。我们可以在函数rl_gets()中看到对readline()函数的包装。然后在sdb_mainloop()中通过调用其获取，命令行内容。后续对获取的命令行内容进行解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (char *str; (str = rl_gets()) != NULL; ) {
    char *str_end = str + strlen(str);

    /* extract the first token as the command */
    char *cmd = strtok(str, " ");
    if (cmd == NULL) { continue; }

    /* treat the remaining string as the arguments,
     * which may need further parsing
     */
    char *args = cmd + strlen(cmd) + 1;
    if (args >= str_end) {
      args = NULL;
}

这里程序将命令行内容解析为命令cmd和命令行参数args，我们接受cmd和args的指针，然后根据cmd调用对应的指令。不过这里需要注意。对于多参数的指令，我们需要对args进行额外的处理。

单步执行

现在我们开始进行单步执行的操作，首先我们需要向cmd_table中添加我们的指令和对应的处理函数：

1
{ "si", "si [N]", cmd_si},

然后对于si的执行逻辑我们写在处理函数cmd_si中。

对于单步执行的实现，我们希望CPU一次只执行一条指令，我们自然会想到先前的负责CPU执行的函数cpu_exec()，我们可以参考c/continue的实现来完成。

1
2
3
4
5
6
7
8
9
static int cmd_si(char *args) {
  if(args==NULL){
    cpu_exec(1);
    return 0;
  }
  int step = strtol(args,NULL,0);
  cpu_exec(step);
  return 0;
}

当使用si是默认步进一条指令，当给出指定参数时，不仅指定的步数。

显示寄存器

寄存器和ISA架构是相关的，所以框架中为我们在src/isa/$ISA/reg.c中设置了相应的接口isa_regs_display()，我们只需要完善这个接口。然后在处理函数中调用它就好了。

我们先向cmd_tale中添加对应的功能:

1
{ "info", "info [r/w]", cmd_info},

使用cmd_info()作为命令的处理函数。

1
2
3
4
5
6
7
8
9
static int cmd_info(char* args){
  if(strncmp(args,"r\0",1)){
    printf("Unknown arguments '%s'\n",args);
    return 0;
  }else{
    isa_reg_display();
    return 0;
  }
}

由于之后还要拓展所以需要对info的参数进行匹配。这里我们调用了框架提供的接口进行使用isa_regs_display():

1
2
3
4
5
6
7
8
void isa_reg_display() {
  for(int i=0;i<32;i+=4){
    printf("[%s]\t0x%08x |\t",regs[i],cpu.gpr[i]);
    printf("[%s]\t0x%08x |\t",regs[i+1],cpu.gpr[i+1]);
    printf("[%s]\t0x%08x |\t",regs[i+2],cpu.gpr[i+2]);
    printf("[%s]\t0x%08x\n",regs[i+3],cpu.gpr[i+3]);
  }
}

我们通过对应的格式打印cpu结构中的通用寄存器的值即可。

扫描内存

由于我们还没有实现对表达式的求值和解析，所以在指定内存时，我们暂时只支持十六进制。至于扫描内存，我们只需要从指定的位置起始，使用内存接口打印指定长度的字节即可。我们可以在src\memory\vaddr.c中找到我们可使用的接口。

由于我们的应用程序是运行在虚拟空间中的，所以我们使用的是虚拟内存读取vaddr_read()。现在我们可以尝试开始实现这个功能，首先我们需要向cmd_table()，添加功能函数：

1
{ "x", "x [N] EXPR", cmd_x}

由于这一部分我们需要使用两个参数，所以我们还需要对args进行预处理，用于为内存扫描提供参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char* arg1=strtok(args, " ");
if(arg1==NULL){
  printf("No argument1 , the format 'x [N] EXPR'\n");
  return 0;
}else{
  len = strtol(arg1,NULL,0);
}
char* arg2=strtok(NULL, " ");
if(arg2==NULL){
  printf("No argument2 , the format 'x [N] EXPR'\n");
  return 0;
}else{
  addr = strtol(arg2,NULL,0);
}

这里我们使用strtol来划分参数，然后使用strtol将参数转换为对应的数值，作为接口的参数，然后我们就可以通过访问接口，遍历打印指定位置的内存数数据了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static int cmd_x(char* args){
  int len;
  int addr;
  char* arg1=strtok(args, " ");
  if(arg1==NULL){
    printf("No argument1 , the format 'x [N] EXPR'\n");
    return 0;
  }else{
    len = strtol(arg1,NULL,0);
  }
  char* arg2=strtok(NULL, " ");
  if(arg2==NULL){
    printf("No argument2 , the format 'x [N] EXPR'\n");
    return 0;
  }else{
    addr = strtol(arg2,NULL,0);
  }
  for(int i=0;i<len;){
    printf(ANSI_FMT("0x%08x:  ",ANSI_FG_BLUE),addr);
    for(int j=0;i<len&&j<4;i++,j++){
      uint32_t data = vaddr_read(addr, 4);
      printf("0x%08x  ",data);
      addr += 4;	
    }
    printf("\n");
  }
  return 0;
}

至此，我们就完成了PA1中的基础设施。

发表于 分类于
本文字数： 793 阅读时长 ≈ 3 分钟

这个月发生了各种各样的事情，我特别累也特别疲惫。对于上次以后的总结，我几乎记不得中间都做了哪些事情。我不想对这一个月的经历过多谈论，我心里是十分难过的。

接下来一段时间会很忙，忙在哪些地方呢？

  • NJU PA实验，我要坚持写下去
  • 操作系统真象还原，我也要坚持看下去，我希望能通过这本书的指引，实现一个自己的操作系统。之后我想仿写xv6的源代码，实现一个基本的操作系统内核。
  • 最近新接的科研训练项目，主题是基于动态欺骗的主动网络防护技术，现在还在写文档阶段，非常无聊和痛苦
  • 这个学期冗杂的课程，还有各种活动

直白的说，我这个月是感情失利了。我和在一起四年的一个女生分开了。感觉就是很难过，不知道怎么用语言描述，我一开始天天躺着，天天打游戏来麻痹自己，但是感觉都没什么用。我不知道怎么办，我想各种办法去转移自己的注意力，但是无论做什么都没办法集中自己，这几天睡得也很晚，总之就是精神状态很差。

但是我也不该，也不愿意一直这么下去，我找各种各样得事情给自己，不知不觉就这么多事情了。现在已经过去了大半个月了，不想刚开始一样一想到就会好难过，但是偶尔还是会难过。我觉得生活还得继续，不能一直自暴自弃，继续走下去，也许我会遇到更好的女生，也许我会以更好的状态遇见她。我这么想着，慢慢开始忙碌起来，身体还是很疲惫，依然需要时间去习惯与适应。

可能十月份会非常忙吧，各种各样的事情，所以国庆也不能闲着，要抓紧时间。可能这个学期能玩游戏的时间会越来越少，但还是要坚持住。这也是我第一次参加科研训练，我对科研学习的过程也一直很感兴趣，我想好好体验一下这个过程。

还有PA实验和操作系统，本来操作系统是想跟着JYY老师的课程学习的，现在看来是没什么时间了。还要概率论、离散数学、密码学应用基础，这些课基本还没听过，也不知道怎么办。这个学期的408课程也是牢的没边，也不知道怎么办。

这么看了这个学期还真是坎坷，和我暑假时预想的一点也不一样。当然我也没想到会和她分手QAQ，不过现在她还是愿意陪我聊天的，说不定以后还有机会。事到如今只能，继续坚持下去。希望以后会越来越好，也希望我能在这段时间里慢慢获得成长。