Ylin's Blog
0%

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

今天简单的学习一下相关类的定义和作用

Vec3类

图形程序中需要一些用于存储几何向量和颜色的类，这里的话我们设置一个最简单的，只需要三个坐标就够了。我们使用相同的类vec3来表示颜色、位置、方向、偏移。所以我们会为这个类声明另外两个别名point3和color,但是要注意，不要将一个point3添加到一个color中

我们定义一个类文件：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#ifndef RENDER_C___VEC3_H
#define RENDER_C___VEC3_H

#include <cmath>
#include <iostream>
// 向量类
class vec3 {
public:
    double e[3];

    vec3(): e{0,0,0} {}
    vec3(double e0,double e1,double e2): e{e0,e1,e2} {}

    double x() const{ return e[0]; }
    double y() const{ return e[1]; }
    double z() const{ return e[2]; }

    vec3 operator-() const {return {-e[0],-e[1],-e[2]};}
    double operator[](int i) const { return e[i];}
    double & operator[](int i) {return e[i];}

    vec3& operator+=(const vec3& v){
        e[0] += v.e[0];
        e[1] += v.e[1];
        e[2] += v.e[2];
        return *this;
    }

    vec3& operator*=(double t){
        e[0] *= t;
        e[1] *= t;
        e[2] *= t;
        return *this;
    }

    vec3& operator/=(double t){
        return *this *= 1/t;
    }

    double length_squared() const{
        return e[0]*e[0]+e[1]*e[1]+e[2]*e[2];
    }

    double length() const {
        return std::sqrt(length_squared());
    }
};

// 设置别名
using point3 = vec3;

// 设置内联函数
inline std::ostream& operator<<(std::ostream& out,const vec3& v){
    return out << v.e[0] << ' ' << v.e[1] << ' ' << v.e[2];
}

inline vec3 operator+(const vec3& u,const vec3& v){
    return {u.e[0]+v.e[0],u.e[1]+v.e[1],u.e[2]+v.e[2]};
}

inline vec3 operator-(const vec3& u,const vec3& v){
    return {u.e[0]-v.e[0],u.e[1]-v.e[1],u.e[2]-v.e[2]};
}

inline vec3 operator*(const vec3& u,const vec3& v){
    return {u.e[0]*v.e[0],u.e[1]*v.e[1],u.e[2]*v.e[2]};
}

inline vec3 operator*(double t,const vec3& v){
    return {t*v.e[0],t*v.e[1],t*v.e[2]};
}

inline vec3 operator*(const vec3& v,double t){
    return t*v;
}

inline vec3 operator/(const vec3& v,double t){
    return (1/t)*v;
}

inline double dot(const vec3& u,const vec3& v){
    return u.e[0]*v.e[0] + u.e[1]*v.e[1] + u.e[2]*v.e[2]; 
}

inline vec3 cross(const vec3& u,const vec3& v){
    return {u.e[1]*v.e[2]-u.e[2]*v.e[1],u.e[2]*v.e[0]-u.e[0]*v.e[2],u.e[0]*v.e[1]-u.e[1]*v.e[0]};
}

inline vec3 uint_vector(const vec3& v){
    return v/v.length();
}

#endif //RENDER_C___VEC3_H

其中大量应用了函数的重载，不过对着《c++ primer plus》还是看的差不多了。

这里的小数我们使用了double数据类型，因为它更加的准确，不过还是以自己使用的机器为主，看你内存空间咯

vec3类在颜色中的应用

基于vec3类，定义一个color.h，并向里面定义一个写入像素的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#ifndef RENDER_C___COLOR_H
#define RENDER_C___COLOR_H

#include "vec3.h"

using color = vec3;

void write_color(std::ostream& out,const color& pixel_color){
    auto r = pixel_color.x();
    auto g = pixel_color.y();
    auto b = pixel_color.z();

    int rbyte = int (255.999 * r);
    int gbyte = int (255.999 * g);
    int bbyte = int (255.999 * b);
    
    out << rbyte << ' ' << gbyte << ' ' << bbyte << '\n';
}

#endif //RENDER_C___COLOR_H

现在我们可以用我们定义的类去实现我们昨天手搓出来的图片了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "color.h"
#include "vec3.h"

#include <iostream>

int main(){
    int image_width = 256;
    int image_height = 256;

    std::cout << "P3\n" << image_width << ' ' << image_height << "\n255\n";
    for (int j=0;j<image_height;j++){
        std::clog << "\rScanlines remaining: "<< (image_height-j) << '\r' << std::flush;
        for(int i =0;i<image_width;i++){
            auto pixel_color = color(double(i)/(image_width-1),double(j)/(image_height-1),0);
            write_color(std::cout,pixel_color);
        }
    }
    std::clog << "\rDone\n";
}

虽然没有节省多少内容，但是在后续的过程中，这个简便性会慢慢体现出来。

基于vec3实现射线类

我们需要一个光线类，来实现对光线的计算。我们可以用函数P(t) = A + bt来实现光线路径的模拟。其中A指的是射线的起点，b指的是射线的方向，t是光线的延伸。我们将这个射线的概念封装为一个类，其中用于计算的函数P(t)用函数ray::at(t)表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef RENDER_C___RAY_H
#define RENDER_C___RAY_H

#include "vec3.h"

class ray{
public:
    ray(){}

    ray(const point3& origin,const vec3& direction): orig(origin),dir(direction){}

    const point3& origin() const {return orig;}
    const vec3& direction() const {return dir;}

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

#endif //RENDER_C___RAY_H

这里将射线的起点和方向进行了封装，只能通过接口访问以确保程序的完整与安全

现在我们接下来要用到几个类就设置完成啦

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

最近对图形学比较感兴趣，虽然感觉找不到工作，但是帅，我花点时间学一下，刚好练习一下C++

输出一个图像

ppm

当我们启动一个渲染器时，我们需要一种方式来查看我们的图像。最简单的方式就是将它写入文件中，这里我们使用PPM格式（因为它比较简单）

image.png

这是PPM文件格式在维基中的表现：

  • 第一行是文件描述子 什么P1 P2 P3代表了不同的图像类型，这里我们使用P3——像素图
  • 第二行是像素的宽高 先宽后高
  • 第三行表示每个像素分量的最大值 255 即8位色彩深度
  • 下面是像素的信息，每一行的最后用换行符结尾

图形学的Hello World

我们可以用简单的代码实现一个这样的图片：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
int main(){
    int image_width = 256;
    int image_height = 256;

    std::cout << "P3\n" << image_width << " " << image_width << "\n255\n";

    for (int j =0 ;j<image_height;j++){
        for(int i=0;i<image_width;i++){
            auto r = double (i)/(image_width-1);
            auto g = double (j)/(image_height -1);
            auto b = 0.0;

            int ir = int (255.999 *r);
            int ig = int (255.999 *g);
            int ib = int (255.999 *b);
			// 255.999确保在浮点数计算中的极小误差在转换为整数的过程中不会被放大，可以理解成这是一种技巧，用来避免色彩的丢失
            std::cout << ir << ' ' << ig << ' ' << ib << '\n';
        }
    }
}

我们将输入定向到一个文件中，然后更改后缀名打开

image.png

可以看到我们生成的图片啦

添加一个程序进度指示器

有时候长时间渲染需要进行跟踪，以判断是否陷入死循环中，或者查看渲染进度。

我们可以通过添加日志输出流来实现这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
int main(){
    int image_width = 256;
    int image_height = 256;

    std::cout << "P3\n" << image_width << " " << image_width << "\n255\n";

    for (int j =0 ;j<image_height;j++){
        std::clog << "\rScanlines remaining: " << (image_height - j) << ' ' << std::flush;
        for(int i=0;i<image_width;i++){
            auto r = double (i)/(image_width-1);
            auto g = double (j)/(image_height -1);
            auto b = 0.0;

            int ir = int (255.999 *r);
            int ig = int (255.999 *g);
            int ib = int (255.999 *b);

            std::cout << ir << ' ' << ig << ' ' << ib << '\n';
        }
    }
    std::clog << "\rDone                    \n";
}

这样就可以啦

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

你真的喜欢你现在正在做的事情吗？这真是你想学的吗？你以后还会继续喜欢它吗？

我和一位学艺术的同学聊到这个话题，我们都很喜欢自己正在做的事情。他说 “我很怕自己以后突然有一天不喜欢画画了” ，我听得很难过，因为我已经开始不喜欢我正在做得事情了。好不容易找到自己想做的事，难道仅仅也是因为新鲜感吗？他接着说 “我觉得很多人并不是喜欢这件事，而是喜欢它为你带来的价值。真的有人喜欢数学吗？有但是少数，可是为什么那么多人说自己喜欢数学呢？因为在数学上他比别人更强，数学能够为他带来优越感，和各种荣誉。”我又何尝不是这样呢？我学的大多数知识已经是为比赛开始服务了，我喜欢的是这些知识，还是比赛为我带来的荣誉呢？

我突然很害怕，这是我早就意识到的一个问题。大概是新生赛时期拿到过一次第一吧，大多数人对我的印象是一个很优秀很有潜力的CTFer，我也这么觉得，我觉得就该这么下去，以后一定会越来越强。大概是从这个时候开始我就变了吧，我搞丢了我的初心。我可以拿CTF为由去拒绝学习其他我不想学的东西，即使我不上课，不写作业，文化课乱成一团，我也觉得情有可原。别人也很“理解”我，“没关系，你看你技术学的那么好”。真的是如此吗？

我一点也不喜欢这样，我可以肯定。这些我都不在乎，我想得到的不是这些，我想知道的是计算机背后的细节，一个个门电路是怎么搭建出的计算机，程序是怎么链接加载的，电脑是怎么运行的。我想写自己的东西，不是给别人看的东西，不是为了比赛而匆匆赶制的作品。很多人说不好就业，这样焦虑那样焦虑，并不重要，我是在做我喜欢的事情，很多人一辈子都不知道自己想做什么，只顾着养活自己。但是我有我自己想做的事情，我不甘心被这些东西阻挠，这些那些放做一旁。我有很多想做的事情，想学的知识。

当然，无论怎么做总有人质疑你，我以前总是被这个困扰，我想做出最好的选择，让所有人都认可。但从来都不是这样的，你有理想，别人嫉妒你，说理想不能当饭吃，你还是得养活自己。你现实，别人忌惮你，说别只知道学习，别太功利，不然会很累。大多数人是见不得别人好的，见不得别人有自己的事情要做。巴不得所有人和自己一样过的迷茫错误。上了大学才发现，这种人到处都是。

我的同学是一个很纯粹的艺术生，喜欢素描和速写，他追求的是真正的艺术，能让自己满意，能让他人开心的艺术，我很羡慕他。其实我和他也一样，我追求纯粹的知识，我想知道的，能让我说出原来如此的知识，仅此而已。希望之后的学习之旅，能够不忘初心，慢慢加油。

发表于 更新于 分类于
本文字数： 21k 阅读时长 ≈ 19 分钟

项目地址 https://www.jmeiners.com/lc3-vm/#running-the-vm

什么是虚拟机

虚拟机是一种像计算机一样的程序。它模拟CPU和一些其他的硬件组件的功能，使其能够实现算术运算，内存读写，还有与I/O设备的交互。最重要的是，你可以理解你为其定义的机器语言，然后用它来编程。

LC-3架构

这次编写的虚拟机将模拟LC-3架构。和X86架构相比，它的指令集更加简单

内存

LC-3中有65536个内存位置（这是16位无符号整数能表示的最大地址），每个位置存储一个16位的值。这意味它只能存储128KB的值，我们将其存储在一个数组中

1
2
3
// Memory Storage
#define MEMORY_MAX (1<<16)
uint16_t memory[MEMORY_MAX];	//65536个16位的内存空间

寄存器

LC-3共有10个寄存器，每个寄存器都为16位的。其功能分布如下：

  • 通用寄存器（R0-R7）—— 8：执行程序计算
  • 程序计数器（PC）—— 1：表示内存中将要执行的下一条指令
  • 条件寄存器（COND）—— 1：计算的信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Registers
enum{
    R_R0 = 0,
    R_R1,
    R_R2,
    R_R3,
    R_R4,
    R_R5,
    R_R6,
    R_R7,
    R_PC,
    R_COND,
    R_COUNT
};

我们也将其保存在一个数组中

1
2
// Register Storage
uint16_t reg[R_COUNT];

指令集

LC-3中只有16个操作指令，我们将用他们实现计算机中的各种内容。每个指令的长度是16位，我们用左边的4位用来存储操作码（操作指令对应的机器码）,其它位置用来存放参数

接下来定义操作码，并分配对应的枚举值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Opcodes
enum{
    OP_BR = 0, 	//条件分支
    OP_ADD,		//加
    OP_LD,		//加载数据
    OP_ST,		//存储数据
    OP_JSR,		//子程序调用
    OP_AND,		//按位与
    OP_LDR,		//基址加载
    OP_STR,		//基址存储
    OP_RTI,		//不使用
    OP_NOT,		//按位或
    OP_LDI,		//间接加载
    OP_STI,		//间接存储
    OP_JMP,		//跳转
    OP_RES,		//不使用
    OP_LEA,		//加载有效地址
    OP_TRAP		//系统调用
};

条件标志

R_COND寄存器存储条件标志，这些标志提供了最近的计算的信息，使得程序能检查逻辑条件。这里LC-3至使用3个条件标志，这些条件标志指示前一次的计算符号

1
2
3
4
5
6
// Condition Flags
enum{
    FL_POS = 1 << 0,	//P
    FL_ZRO = 1 << 1,	//Z
    FL_NEG = 1 << 2,	//N
}

现在我们已经完成虚拟机中硬件组件的设置。可以进一步尝试虚拟机的实现了，此时文件结构应该是这样

1
2
3
4
5
@{Includes}

@{Registers}
@{Condition Flags}
@{Opcodes}

汇编示例

现在我们尝试写一个LC-3汇编的程序，以了解虚拟机上发生的事情

1
2
3
4
5
6
.ORIG x3000			;程序将被加载到内存的这个位置
LEA R0,HELLO_STR	 ;将字符串加载到R0中
PUTs				;将R0指向的字符串输出
HALT				;中断
HELLO_STR .STRINGZ "Hello,World!"	;程序中字符串存储于此
.END				;结束标记
  • 这个指令是线性执行的，和C语言以及其他语言中的{}作用域不同
  • .ORIG和.STRINGZ是汇编器指令，用于生成一段代码或数据（像宏一样）

尝试循环和条件语句的使用通常使用类似goto的指令实现。比如计数到10：

1
2
3
4
5
AND R0, R0, 0		;清空R0
LOOP				;设置跳转标签
ADD R0, R0, 1		;R0 = R0 + 1
ADD R1, R0, -10		 ;R1 = R0 - 10
BRn LOOP			;若为负数则跳转

执行程序

上面的例子让你大致理解了这个虚拟机的功能。使用LC-3的汇编语言，你甚至能在你的虚拟机上浏览网页，或者Linux系统

过程

以下是我们编写程序的步骤：

  • 从PC寄存器存储的内存地址中加载一条指令
  • 递增PC寄存器
  • 查看指令的操作码以确定它执行那种类型的指令
  • 使用指令中的参数执行指令
  • 返回第一步

当然我们也需要while和if之类的指令，帮我们实现指令的跳转，不然编程量会很大。所以在这里我们会通过类似于goto的指令来跳转PC从而改变执行流程，我们开始编写：

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
// Main Loop
int main(int argc,const char * argv[]){
    @{Load Arguments}
    @{Setup}
    
    //无论何时都应该设定一个条件标志，这里设置Z标志
    reg[R_COND] = FL_ZRO;
    
    //为PC设置一个起始的内存加载地址，0x3000为默认
    enum{PC_START = 0x3000};
    reg[R_PC] = PCSTART;
    
    int running = 1;
    while (running){
        //读取
        uint16_t instr = mem_read(reg[R_PC]++);
        uint16_t op = instr >> 12;
        
        switch(op){
            case OP_ADD:
                @{ADD}
                break;
            case OP_AND:
                @{AND}
                break;
            case OP_NOT:
                @{NOT}
                break;
            case OP_BR:
                @{BR}
                break;
            case OP_JMP:
                @{JMP}
                break;
            case OP_JSR:
                @{JSR}
                break;
            case OP_LD:
                @{LD}
                break;
            case OP_LDI:
                @{LDI}
                break;
            case OP_LDR:
                @{LDR}
                break;
            case OP_LEA:
                @{LEA}
                break;
            case OP_ST:
                @{ST}
                break;
            case OP_STI:
                @{STI}
                break;
            case OP_STR:
                @{STR}
                break;
            case OP_TRAP:
                @{TRAP}
                break;
            case OP_RES:
            case OP_RTI:
            default:
                @{BAD OPCADE}
                break;
        }
    }
    @{Shutdown}
}

我们在主循环中，处理命令行参数，使我们的程序可用。我们期望输入的参数是一个虚拟机镜像，如果不是的话，则给出参数输入的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
// Load Arguments
if(argc < 2){
    //展示用法
    printf("lc3 [image-file1] ...\n");
    exit(2);
}

for(int j = 1;j < argc; ++j){
    if(!read_image(argv[j])){
        printf("failed to load image: %s\n",argv[j]);
        exit(1);
    }
}

指令实现

我们现在需要将每个操作码情况都填充为正确的实现，我们可以在LC-3中找到指令的正确实现。下面会演示两个指令的实现

ADD

ADD指令取两个数字相加，并将结果存储在寄存器中。其规范如下：

image.png

编码显示了两行，因为这条指令有两种模式。可以看到前四位（这里是小端序）都是一样的，0001是OP_ADD的操作码。接下来3位都是DR，这代表目标寄存器。目标寄存器是用来存储加和的位置。再接下来3位是SR1,这是包含第一个要加的数字的寄存器。

区别在于最后五位，注意第5位，这个位表示ADD是立即数模式还是寄存器模式，在寄存器模式中，则是将两个寄存器相加，第二个寄存器被标记为SR2。其使用方法如下：

1
ADD R2 R0 R1	;R2 = R0 + R1

立即数模式则是将第二个值嵌入指令本身，如图中所示标识为imm5，消除了编写将值从内存中读取的需要。不过限于指令的长度，数字最多25 = 32（无符号），这使得即时模式主要用于递增和递减，其使用如下：

1
ADD R0 R0 1		;R0 = R0 + 1

其具体规范如下：

If bit [5] is 0, the second source operand is obtained from SR2. If bit [5] is 1, the second source operand is obtained by sign-extending the imm5 field to 16 bits. In both cases, the second source operand is added to the contents of SR1 and the result stored in DR. (Pg. 526)

这里的话和我们刚刚分析的差不多，但是在于它提到的"sign-extending"。这是啥用的呢？要知道，我们的加法是16位的，但我们的立即数是5位的，所以我们需要将它拓展到16位以匹配另一个数字。对于正数我们只需要补充0即可，但是对于负数我们需要用1填充，从而保持原始值

1
2
3
4
5
6
7
// Sign Extend
uint16_t sign_extend(uint16_t x, int bit_count){
    if((x>>(bit_count-1))&1){
        x |= (0xFFFF << bit_count);
    }
    return x;
}

规范中还有一句填充：

The condition codes are set, based on whether the result is negative, zero, or positive. (Pg. 526)

条件码根据结果是否为负，0，正来设置。我们之前定义了一个条件标志枚举，现在我们需要用到他们。每当有一个值被写入寄存器中，我们需要更新条件标志寄存器来标识它的符号。我们写一个函数来进行这个过程： 

1
2
3
4
5
6
7
8
9
// Update Flags
void update_flags(uint16_t r){
    if(reg[r] == 0)
        reg[R_COND] = FL_ZRO;
    else if(reg[r] >> 15)	//当1是最高位时说明这是一个负数
        reg[R_COND] = FL_NEG;	
    else
        reg[R_COND] = FL_POS
}

至此我们可以编写ADD了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// ADD
{
    //目标寄存器
    uint16_t r0 = (instr >> 9) & 0x7;
    //第一操作数
    uint16_t r1 = (instr >> 6) & 0x7;
    //是否是立即数
    uint16_t imm_flag = (instr >> 5) & 0x1;
    
   if(imm_flag){
       uint16_t imm5 = sign_extend(instr & 0x1F,5);
       reg[r0] = reg[r1] + imm5;
   }else{
       uint16_t r2 = instr & 0x7;
       reg[r0] = reg[r1] + reg[r2];
   }
    update_flags[r0]
}

至此，我们的ADD指令编写完成了，接下来我们将使用符号拓展，不同模式和更新标志的组合去实现其他的指令

LDI

LDI的话是间接加载的意思。这个指令将内存地址中的值加载到寄存器中，下面是它的指令样式：

image.png

可以看到前面的结构和ADD差不多，一个操作码，加上一个目标寄存器，剩余的位被标记为PCoffset9。这是一个嵌入在指令中的立即值（类似imm5）。由于这个指令从内存中读取，所以推测这个数字是一个地址，告诉我们从哪里加载：

An address is computed by sign-extending bits [8:0] to 16 bits and adding this value to the incremented PC. What is stored in memory at this address is the address of the data to be loaded into DR. (Pg. 532)

大概的意思是，我们需要将这个9位的值进行符号拓展，将其加到当前的PC上,结果之和则是一个内存的地址，这个地址包含另一个值，也就是我们将要加载的值的地址

这种方式读取内存可能很绕，但实际上这是必不可少的。LD指令仅限于9位地址偏移量，但是内存需要16位寻址，LDI对于加载存储在离当前PC位置较远的数据时更有用。与之前一样，将值放到DR后需要更新标志，其实现如下：

1
2
3
4
5
6
7
8
9
10
// LDI
{
    //目标寄存器
    uint16_t r0 = (instr >> 9) & 0x7;
    //初始化PCoffset
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    //将偏移值与PC相加，并读取对应的内存中的值到寄存器中
    reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset));
    update_flags(r0);
}

现在我们实现了两个主要的指令，接下来的用差不多的方式就可以写出来了

其他

RTI & RES

并不使用

1
2
// BAD OPCODE
abort();

AND

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// AND
{
	uint16_t r0 = (instr >> 9) & 0x7;
	uint16_t r1 = (instr >> 6) & 0x7;
	uint16_t imm_flag = (instr >> 5) & 0x1;

	if(imm_flag){
    	uint16_t imm5 = sign_extend(instr & 0x1F,5);
	    reg[r0] = reg[r1] & imm5;
	}else{
    	uint16_t r2 = instr & 0x7;
	    reg[r0] = reg[r1] & reg[r2];
	}
	update_flags(r0)
}

NOT

1
2
3
4
5
6
7
8
// NOT
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    
    reg[r0] = ~reg[r1];
    update_flags(r0);
}

BR

1
2
3
4
5
6
7
8
// BR
{
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    uint16_t cond_flag = (instr >> 9) & 0x7;
    if(cond_flag & reg[R_COND]){	//cond_flag设置了跳转的条件
        reg[R_PC] += pc_offset;
    }
}

JMP

这里我们将RET视作JMP的一种特殊情况

1
2
3
4
5
// JMP
{
    uint16_t r1 = (instr >> 6) & 0x7;
    reg[R_PC] = reg[r1];
}

JSR

1
2
3
4
5
6
7
8
9
10
11
12
// JSR
{
    uint16_t long_flag = (instr >> 11) & 1;
    reg[R_R7] = reg[R_PC];
    if(long_flag){
        uint16_t long_pc_offset = sign_extend(intstr & 0x7FF,11);
        reg[R_PC] += long_pc_offset;	//JSR,加上偏移值
    }else{
        uint16_t r1 = (instr >> 6) & 0x7;
        reg[R_PC] = reg[r1];			//JSRR，跳转到寄存器指定地址
    }
}

LD

1
2
3
4
5
6
7
// LD
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    reg[r0] = mem_read(reg[R_PC] + pc_offset);	//在PC上偏移
    update_flags(r0);
}

LDR

1
2
3
4
5
6
7
8
// LDR
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(instr & 0x3F,6);
    reg[r0] = mem_read(reg[r1] + offset);
    update_flags(r0);
}

LEA

1
2
3
4
5
6
7
// LEA
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    reg[r0] = reg[R_PC] + pc_offset;
    update_flags(r0);
}

ST

1
2
3
4
5
6
// ST
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    mem_write(reg[R_PC] + pc_offset,reg[r0]);
}

STI

1
2
3
4
5
6
// STI
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
    mem_write(mem_read(reg[R_PC] + pc_offset),reg[r0]);
}

STR

1
2
3
4
5
6
7
// STR
{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(intstr & 0x3F,6);
    mem_write(reg[r1] + offset,reg[r0])
}

中断例程 Trap routines

LC-3中提供了一些预定的例程，用来执行常见的任务，以及与I/O间的设备交互。例如，从键盘获取输入和向控制台显示字符串的中断例程。可以将其作为LC-3的操作系统API理解。每个例程分配了一个中断码，我们定义一个枚举来实现他们，下面是TRAP指令的格式

image.png

其中的0~7位用于存放中断码，我们据此来实现他们：

1
2
3
4
5
6
7
8
9
// TRAP Codes
enum{
    TRAP_GETC = 0x20,		//从键盘中读取输入，但是不打印至终端
    TRAP_OUT = 0x21,		//输出字符
    TRAP_PUTS = 0x22,		//输出字符串（双字节单字符）
    TRAP_IN = 0x23,			//从键盘中读取输入，且打印至终端
    TRAP_PUTSP = 0x24,		//输出字符串（单字节单字符）
    TRAP_HALT = 0x25		//中断程序
};

中断例程并不是指令，但是它为LC-3的运行提供了各种快捷的方式。在LC-3中，这些例程实际上是使用汇编编写的，当中断例程被调用了，程序被跳转到这里，执行后返回程序。（为什么程序从0x3000开始加载而不是0x0也是因为这个原因，需要一部分空间用来存储中断例程的代码）

在LC-3中我们直接使用C语言进行中断例程的编写，而不是汇编。我们不用从汇编开始写自己的I/O设备，我们可以发挥虚拟机的优势，使用更好的更搞层次的设备去仿真这个过程

我们在TRAP中使用一个switch来进一步的编写这个指令：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// TRAP
reg[R_R7] = reg[R_PC];
switch(instr & 0xFF){
    case TRAP_GETC:
        @{TRAP_GETC}
        break;
    case TRAP_OUT:
        @{TRAP_OUT}
        break;
    case TRAP_PUTS:
        @{TRAP_PUTS}
        break;
    case TRAP_IN:
        @{TRAP_IN}
        break;
    case TRAP_PUTSP:
        @{TRAP_PUTSP}
        break;
    case TRAP_HALT:
        @{TRAP_HALT}
        break;
}

接下来进一步的实现例程中的内容

PUTS

功能的话类似于C语言中的printf，但是我们字符串和C中的有所不同，LC-3中的字符并不是被单独存储为一个字节，而是被存储为一个内存位置。LC-3中的内存位置并不是16位，所以字符串中的每个字符都是16位的。为了用C的方法将其打印出来，我们需要将它转换为一个字符并单独输出

1
2
3
4
5
6
7
8
9
10
// TRAP PUTS
{
    // 每个字符占一个字(16bits)
    uint16_t *c = memory + reg[R_R0];
    while(*c){
        putc((char)*c,stdout);	//强制类型转换
        ++c;
    }
    fflush(stdout);
}

以这个为例，我们可以进一步的编写其他的例程

GETC

1
2
3
4
5
6
// TRAP GETC
{
    // 读取一个ASCII字符
    reg[R_R0] = (uint16_t)getchar();
    update_flags(R_R0);
}

OUT

1
2
3
4
5
// TRAP OUT
{
    putc((char)reg[R_R0],stdout);
    fflush(stdout);
}

IN

1
2
3
4
5
6
7
8
9
// TRAP IN
{
    printf("Enter a character: ");
    char c = getchar();
    putc(c,stdout);
    fflush(stdout);
    reg[R_R0] = (uint16_t)c;
    update_flags(R_R0);
}

PUTSP

1
2
3
4
5
6
7
8
9
10
11
12
13
// TRAP PUTSP
{
    //刚刚的字符串打印是适用于双字节单字符的情况，现在是单字节单字符的情况
    uint16_t *c = memory + reg[R_R0];
    while(*c){
        char char1 = (*c) & 0xFF;
        putc(char1,stdout);
        char char2 = (*c) >> 8;
        if(char2) putc(char2,stdout);
        ++c;
    }
    fflush(stdout);
}

HALT

1
2
3
4
5
6
//HALT	
{
    puts("HALT");
    fflush(stdout);
    running = 0;
}

程序加载

我们也许可以注意到指令是从内存中加载和进行执行的，但是指令是怎么进入内存的呢？当汇编被转换为机器指令时，它变成了一个包含了一系列的数据与指令的文件，可以将它复制到内存中进行加载。

16位的程序文件头指出了程序在内存中起始的地址。这个地址被称之为起始地址(origin)。它首先被读取，然后从起始地址开始将其余数据从文件读入内存。以下是LC-3中加载内存的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Reas Image File
void read_image_file(FILE * file){
    //起始地址让我们知道内存从什么地方开始加载
    uint16_t origin;
    fread(&origin,sizeof(orgin),1,file);
    origin = swap16(origin);
    
    //由于我们有最大的内存范围，所以我们可以通过起始位置，确定加载范围
    uint16_t max_read = MEMORY_MAX - origin;
    uint16_t *p = memory + origin;
    size_t read = fread(p,sizeof(uint16_t),max_read,file);
    
    //转换为小端序
    while(read-- > 0){
        *p = swap16(*p);
        ++p;
    }
}

注意这里swap16被调用于每一个数据块，这是因为LC-3是大端序结构，但是大多数现代计算机采用的是小端序结构，所以我们需要将每个uint16数据都转换一遍

1
2
3
uint16_t swap16(uint16_t x){
    return (x << 8)|(x >> 8);
}

我们进一步的封装read_image_file()程序：

1
2
3
4
5
6
7
int read_image(const char * image_path){
    FILE *file = fopen(image_path,"rb");
    if(!file){return 0;};
    read_image_file(file);
    fclose(file);
    return 1;
}

内存映射寄存器

有一些特殊的寄存器是不能通过普通的寄存器组去访问的。相反，在内存中为其保留了特殊的地址。要读写这些寄存器只需要读写他们的内存地址。这个过程便被称为内存映射寄存器。这通常用于一些特殊的硬件设备操作

LC-3有两个内存映射寄存器需要实现。一个是键盘状态寄存器（KBSR），一个是键盘数据寄存器（KBDR）。KBSR用来指示按键是否被按下，KBDR用来指示哪个按键被按下了

虽然可以使用GETC来完成对键盘输入的读取，但是在读取到输入之前，它会一直阻塞程序的执行。而KBSR和KBDR则可以实现对键盘设备的轮询，以确保程序在等待输入的时候持续执行

1
2
3
4
5
//Memory Mapped Registers
enum{
    MR_KBSR = 0xFE00,
    MR_KBDR = 0xFE02
};

内存映射寄存器使得内存访问变得有点复杂，使得你不能直接对内存数组进行访问。所以我们需要编写函数以实现对内存的读写。当从KBSR读取内存时，读取函数将检查键盘并更新两个内存位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//Memory Access
void mem_write(uint16_t address,uint16_t val){
    memory[address] = val;
}

uint16_t mem_read(uint16_t address){
    if(address == MR_KBSR){
        if(check_key()){
            memory[MR_KBSR] = (1 << 15);
            memory[MR_KBDR] = getchar();
        }else{
            memory[MR_KBSR] = 0;
        }
    }
    return memory[address];
}

到此为止，VM的最后一个组件也模拟实现了，我们可以尝试运行它了。

平台特定信息

不同系统中的键盘读入和终端打印的实现可能有所不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Input Buffering
struct termios original_tio;

void disable_input_buffering(){
    tcgetattr(STDIN_FILENO,&original_tio);
    struct termios new_tio = original_tio;
    new_tio.c_lflag &= ~ICANON & ~ECHO;
    tcsetattr(STDIN_FILENO,TCSANOW,&new_tio);
}

void restore_input_buffering(){
    tcsetattr(STDIN_FILENO,TCSANOW,&original_tio);
}

uint16_t check_key(){
    fd_set readfds;
    FD_ZERO(&readfds);
    FD_SET(STDIN_FILENO,&readfds);
    
    struct timeval timeout;
    timeout.tv_sec = 0;
    timeout.tv_usec = 0;
    return select(1,&readfds,NULL,NULL,&timeout) != 0;
}

组合程序

我们利用刚刚写好的程序来对缓冲进行设置，以实现正确处理终端输入。

在main函数开头设置代码：

1
2
3
//Setup
signal(SIGINT,handle_interrupt);
disable_input_buffering();

当程序结束后，我们将中断设置为正常状态：

1
2
//Shutdown
restore_input_buffering();

设置也应该在接收到结束信号时恢复：

1
2
3
4
5
6
//Handle Interrupt
void handle_interrupt(int signal){
    restore_input_buffering();
    printf("\n");
    exit(-2);
}

OK 我们的程序将要实现，我们将其组合便可得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@{Memory Mapped Registers}
@{TRAP Codes}

@{Memory Storage}
@{Register Storage}

@{Input Buffering}
@{Handle Interrupt}
@{Sign Extend}
@{Swap}
@{Update Flags}
@{Read Image File}
@{Read Image}
@{Memory Access}

@{Main Loop}

完整代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
#include <stdio.h>
#include <stdint.h>
#include <signal.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/termios.h>
#include <sys/mman.h>

#define MEMORY_MAX (1<<16)


//Memory Mapped Registers
enum{
    MR_KBSR = 0xFE00,
    MR_KBDR = 0xFE02
};

enum{
    TRAP_GETC = 0x20,		//从键盘中读取输入，但是不打印至终端
    TRAP_OUT = 0x21,		//输出字符
    TRAP_PUTS = 0x22,		//输出字符串（双字节单字符）
    TRAP_IN = 0x23,			//从键盘中读取输入，且打印至终端
    TRAP_PUTSP = 0x24,		//输出字符串（单字节单字符）
    TRAP_HALT = 0x25		//中断程序
};
enum{
    OP_BR = 0, 	//条件分支
    OP_ADD,		//加
    OP_LD,		//加载数据
    OP_ST,		//存储数据
    OP_JSR,		//子程序调用
    OP_AND,		//按位与
    OP_LDR,		//基址加载
    OP_STR,		//基址存储
    OP_RTI,		//不使用
    OP_NOT,		//按位或
    OP_LDI,		//间接加载
    OP_STI,		//间接存储
    OP_JMP,		//跳转
    OP_RES,		//不使用
    OP_LEA,		//加载有效地址
    OP_TRAP		//系统调用
};
uint16_t memory[MEMORY_MAX];	//65536个16位的内存空间
enum{
    R_R0 = 0,
    R_R1,
    R_R2,
    R_R3,
    R_R4,
    R_R5,
    R_R6,
    R_R7,
    R_PC,
    R_COND,
    R_COUNT
};
// Register Storage
uint16_t reg[R_COUNT];
enum{
    FL_POS = 1 << 0,	//P
    FL_ZRO = 1 << 1,	//Z
    FL_NEG = 1 << 2,	//N
};

struct termios original_tio;

void disable_input_buffering(){
    tcgetattr(STDIN_FILENO,&original_tio);
    struct termios new_tio = original_tio;
    new_tio.c_lflag &= ~ICANON & ~ECHO;
    tcsetattr(STDIN_FILENO,TCSANOW,&new_tio);
}

void restore_input_buffering(){
    tcsetattr(STDIN_FILENO,TCSANOW,&original_tio);
}

uint16_t check_key(){
    fd_set readfds;
    FD_ZERO(&readfds);
    FD_SET(STDIN_FILENO,&readfds);
    
    struct timeval timeout;
    timeout.tv_sec = 0;
    timeout.tv_usec = 0;
    return select(1,&readfds,NULL,NULL,&timeout) != 0;
}

//Handle Interrupt
void handle_interrupt(int signal){
    restore_input_buffering();
    printf("\n");
    exit(-2);
}

uint16_t sign_extend(uint16_t x, int bit_count){
    if((x>>(bit_count-1))&1){
        x |= (0xFFFF << bit_count);
    }
    return x;
}

uint16_t swap16(uint16_t x){
    return (x << 8)|(x >> 8);
}

void update_flags(uint16_t r){
    if(reg[r] == 0)
        reg[R_COND] = FL_ZRO;
    else if(reg[r] >> 15)	//当1是最高位时说明这是一个负数
        reg[R_COND] = FL_NEG;	
    else
        reg[R_COND] = FL_POS;
}

void read_image_file(FILE * file){
    //起始地址让我们知道内存从什么地方开始加载
    uint16_t origin;
    fread(&origin,sizeof(origin),1,file);
    origin = swap16(origin);
    
    //由于我们有最大的内存范围，所以我们可以通过起始位置，确定加载范围
    uint16_t max_read = MEMORY_MAX - origin;
    uint16_t *p = memory + origin;
    size_t read = fread(p,sizeof(uint16_t),max_read,file);
    
    //转换为小端序
    while(read-- > 0){
        *p = swap16(*p);
        ++p;
    }
}

int read_image(const char * image_path){
    FILE *file = fopen(image_path,"rb");
    if(!file){return 0;};
    read_image_file(file);
    fclose(file);
    return 1;
}

void mem_write(uint16_t address,uint16_t val){
    memory[address] = val;
}

uint16_t mem_read(uint16_t address){
    if(address == MR_KBSR){
        if(check_key()){
            memory[MR_KBSR] = (1 << 15);
            memory[MR_KBDR] = getchar();
        }else{
            memory[MR_KBSR] = 0;
        }
    }
    return memory[address];
}

int main(int argc,const char * argv[]){
    if(argc < 2){
        //展示用法
        printf("lc3 [image-file1] ...\n");
        exit(2);
    }
    
    for(int j = 1;j < argc; ++j){
        if(!read_image(argv[j])){
            printf("failed to load image: %s\n",argv[j]);
            exit(1);
        }
    }
    signal(SIGINT,handle_interrupt);
    disable_input_buffering();
    
    //无论何时都应该设定一个条件标志，这里设置Z标志
    reg[R_COND] = FL_ZRO;
    
    //为PC设置一个起始的内存加载地址，0x3000为默认
    enum{PC_START = 0x3000};
    reg[R_PC] = PC_START;
    
    int running = 1;
    while (running){
        //读取
        uint16_t instr = mem_read(reg[R_PC]++);
        uint16_t op = instr >> 12;
        
        switch(op){
            case OP_ADD:
            {
                //目标寄存器
                uint16_t r0 = (instr >> 9) & 0x7;
                //第一操作数
                uint16_t r1 = (instr >> 6) & 0x7;
                //是否是立即数
                uint16_t imm_flag = (instr >> 5) & 0x1;
                
               if(imm_flag){
                   uint16_t imm5 = sign_extend(instr & 0x1F,5);
                   reg[r0] = reg[r1] + imm5;
               }else{
                   uint16_t r2 = instr & 0x7;
                   reg[r0] = reg[r1] + reg[r2];
               }
                update_flags(r0);
            }
                break;
            case OP_AND:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t r1 = (instr >> 6) & 0x7;
                uint16_t imm_flag = (instr >> 5) & 0x1;
            
                if(imm_flag){
                    uint16_t imm5 = sign_extend(instr & 0x1F,5);
                    reg[r0] = reg[r1] & imm5;
                }else{
                    uint16_t r2 = instr & 0x7;
                    reg[r0] = reg[r1] & reg[r2];
                }
                update_flags(r0);
            }
                break;
            case OP_NOT:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t r1 = (instr >> 6) & 0x7;
                
                reg[r0] = ~reg[r1];
                update_flags(r0);
            }
                break;
            case OP_BR:
            {
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                uint16_t cond_flag = (instr >> 9) & 0x7;
                if(cond_flag & reg[R_COND]){	//cond_flag设置了跳转的条件
                    reg[R_PC] += pc_offset;
                }
            }
                break;
            case OP_JMP:
            {
                uint16_t r1 = (instr >> 6) & 0x7;
                reg[R_PC] = reg[r1];
            }
                break;
            case OP_JSR:
            {
                uint16_t long_flag = (instr >> 11) & 1;
                reg[R_R7] = reg[R_PC];
                if(long_flag){
                    uint16_t long_pc_offset = sign_extend(instr & 0x7FF,11);
                    reg[R_PC] += long_pc_offset;	//JSR,加上偏移值
                }else{
                    uint16_t r1 = (instr >> 6) & 0x7;
                    reg[R_PC] = reg[r1];			//JSRR，跳转到寄存器指定地址
                }
            }
                break;
            case OP_LD:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                reg[r0] = mem_read(reg[R_PC] + pc_offset);	//在PC上偏移
                update_flags(r0);
            }
                break;
            case OP_LDI:
            {
                //目标寄存器
                uint16_t r0 = (instr >> 9) & 0x7;
                //初始化PCoffset
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                //将偏移值与PC相加，并读取对应的内存中的值到寄存器中
                reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset));
                update_flags(r0);
            }
                break;
            case OP_LDR:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t r1 = (instr >> 6) & 0x7;
                uint16_t offset = sign_extend(instr & 0x3F,6);
                reg[r0] = mem_read(reg[r1] + offset);
                update_flags(r0);
            }
                break;
            case OP_LEA:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                reg[r0] = reg[R_PC] + pc_offset;
                update_flags(r0);
            }
                break;
            case OP_ST:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                mem_write(reg[R_PC] + pc_offset,reg[r0]);
            }
                break;
            case OP_STI:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t pc_offset = sign_extend(instr & 0x1FF,9);
                mem_write(mem_read(reg[R_PC] + pc_offset),reg[r0]);
            }
                break;
            case OP_STR:
            {
                uint16_t r0 = (instr >> 9) & 0x7;
                uint16_t r1 = (instr >> 6) & 0x7;
                uint16_t offset = sign_extend(instr & 0x3F,6);
                mem_write(reg[r1] + offset,reg[r0]);
            }
                break;
            case OP_TRAP:
            {
                reg[R_R7] = reg[R_PC];
                switch(instr & 0xFF){
                    case TRAP_GETC:
                    {
                        // 读取一个ASCII字符
                        reg[R_R0] = (uint16_t)getchar();
                        update_flags(R_R0);
                    }
                        break;
                    case TRAP_OUT:
                    {
                        putc((char)reg[R_R0],stdout);
                        fflush(stdout);
                    }
                        break;
                    case TRAP_PUTS:
                    {
                        // 每个字符占一个字(16bits)
                        uint16_t *c = memory + reg[R_R0];
                        while(*c){
                            putc((char)*c,stdout);	//强制类型转换
                            ++c;
                        }
                        fflush(stdout);
                    }
                        break;
                    case TRAP_IN:
                    {
                        printf("Enter a character: ");
                        char c = getchar();
                        putc(c,stdout);
                        fflush(stdout);
                        reg[R_R0] = (uint16_t)c;
                        update_flags(R_R0);
                    }
                        break;
                    case TRAP_PUTSP:
                    {
                        //刚刚的字符串打印是适用于双字节单字符的情况，现在是单字节单字符的情况
                        uint16_t *c = memory + reg[R_R0];
                        while(*c){
                            char char1 = (*c) & 0xFF;
                            putc(char1,stdout);
                            char char2 = (*c) >> 8;
                            if(char2) putc(char2,stdout);
                            ++c;
                        }
                        fflush(stdout);
                    }
                        break;
                    case TRAP_HALT:
                    {
                        //刚刚的字符串打印是适用于双字节单字符的情况，现在是单字节单字符的情况
                        uint16_t *c = memory + reg[R_R0];
                        while(*c){
                            char char1 = (*c) & 0xFF;
                            putc(char1,stdout);
                            char char2 = (*c) >> 8;
                            if(char2) putc(char2,stdout);
                            ++c;
                        }
                        fflush(stdout);
                    }
                        break;
                }
            }
                break;
            case OP_RES:
            case OP_RTI:
            default:
                abort();
                break;
        }
    }
    restore_input_buffering();
}

至此为止，对LC-3的虚拟机仿真结束

发表于 更新于 分类于
本文字数： 13k 阅读时长 ≈ 12 分钟

最近一直在学习，但是却忽略了最基本的需求——想要有所反馈，所以的话找了几个项目来做一做，这里的话我挑选的是一个用C语言实现shell的项目，用的是Linux编程，刚好我还没有试过在WSL上的编程开发，所以试一试呀，顺便把这个英语博客翻译一遍，锻炼下水平。

项目地址：[brenns10/lsh: Simple shell implementation. Tutorial here ->]

LinuxShell

Shell 的生命周期

Shell 在其生命周期中主要有以下三个动作：

  • 初始化：

    在这一步中，一个典型的Shell会读取并执行它的配置文件，从而引导shell的行为。

  • 解释：

    接着shell会从标准输入(stdin)中读取并执行你的输入（这里的输入还可以是文件等内容）

  • 终端：

    当程序被执行之后，Shell需要负责关闭程序，释放内存，并将其终止

这几个步骤在许多程序开发中都是适用的，但是我们将使用他们作为我们的Shell程序的基础。我们的程序十分简单，不需要任何配置文件，也不需要任何关闭命令。实际上，我们只需要循环调用并终止它们。当然在我们的程序架构中，循环并不是最为重要的。

1
2
3
4
5
6
7
8
9
10
11
int main(int argc,char ** argv){
  //加载配置文件（如果有的话）

  //执行循环指令
  lsh_loop();

  //关闭清理操作
  
  return EXIT_SUCCESS;

}

这里你可以看到实际上就一个函数，它将不停的循环解释命令。我们接下来来完成lsh_loop()的实现

Shell中的基础循环

我们已经考虑完了程序的启动。现在，我们需要搞清楚程序的逻辑，在一次又一次的循环中，我们需要做什么？实际上，我们只需要实现三个步骤以处理这些命令：

  • 读取：从标准输入中读取命令
  • 解析：分割命令，将其分为程序与参数
  • 运行：运行解析后的命令

接下来，让我们一点点实现它： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void lsh_loop(){
  char *line;
  char **args;
  int status;

  do {
    printf("> ");
    line = lsh_read_line();
    args = lsh_spilt_line(line);
    status = lsh_execute(args);

    free(line);
    free(args);
  } while (status);
}

我们看这个程序，前几行是几个变量的声明。这个DO-WHILE循环则是用来方便用来对status变量的检查，因为在每次循环后都会检查一遍它的值。在循环中，我们打印一个提示符，然后读取一行，使用函数来将其划分为关键词，然后再去执行他们。最终我们释放读取的行字符和我们创建的参数变量。在这里我们利用lsh_execute()返回的的status来决定何时退出循环。

行读取

从标准输入中读取一行看起来很容易，但是在C里面实现起来很困难1，因为你并不知道用户会往里面输入多长的内容。你不能只是简单的分配一个内存块，然后祈祷用户的输入不会超出内存块的大小。相反，你需要从一个内存块开始，如果超出了它们，就再次分配一个空间给他们。这是在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
27
28
29
30
31
32
33
34
35
char *lsh_read_line(){
  int bufsize = LSH_RL_BUFSIZE;
  int position = 0;
  char *buffer = malloc(sizeof(char) * bufsize);
  int c;
  
  if(!buffer){
    fprintf(stderr,"lsh: allocation error\n");
    exit(EXIT_FAILURE);
  }

  while (1){
    //读取字符
    c = getchar();

    //确定结束条件
    if(c == EOF || c == '\n'){
      buffer[position] = '\0';
      return buffer;
    }else{
      buffer[position] = c;
    }
    position++；

    //如果超出缓冲区，则拓展新的缓冲区
    if (position >= bufsize){
      bufsize += LSH_RL_BUFSIZE;
      buffer = realloc(buffer,bufsize);
      if(!buffer){
        fprintf(stderr,"lsh: allocation error\n");
        exit(EXIT_FAILURE);
      }
    }
  }
}

前面是一些声明。不过你不用太过在意他们，我更喜欢使用旧的C语言风格——在代码块的前面声明变量。而这个函数的核心则是在循环部分。在循环中我们读取字符（我们将其存储为整数型，而不是一个字符，在比较EOF时，是整型的比较2这是C语言新手经常会犯的错误），如果是回车或者EOF，我们终止并返回它，反之则继续添加字符。

接着，我们需要知道接下来的字符会不会超出缓冲区的大小。如果会的话我们就重新申请一块空间，然后再继续（要注意是否声明出错哦），这样就解决了。

熟悉最新的C语言标准的读者可能注意到，我们写的这个程序实际上已经有实现的函数了getline()。这个函数是GNU对C语言库的拓展。用它实现会更加的容易，不过上面的程序能帮你更好的理解这个函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
char *lsh_read_line(){
  char *line = NULL;
  ssize_t bufsize = 0;
  if (getline(&line,&buffer,stdin) == -1){
    if (feof(stdin)){
      exit(EXIT_SUCCESS); //读取到了EOF
    }else{
      perror("readline");
      exit(EXIT_FAILURE);
    }
  }
  return line;
}

解析行

OK我们将目光放回循环中，我们已经实现了对它的读取，现在我们需要将其解释为一个参数列表。我们尽可能的简化它，所以在这里我们不支持引号和反斜杠转义在我们的命令行参数中。相反，我们将简单的使用空格来将参数一一分隔开来。所以命令echo "this message"并不会打印出this message，而是打印出this和message

通过这些简化，我们用空格将他们划分为token，我们可以用标准库中的strtok函数实现

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
#define LSH_TOK_BUFSIZE 64
#define LSH_TOK_DELIM " \t\r\n\a"

char **lsh_split_line(char *line){
  int bufsize = LSH_TOK_BUFSIZE,position = 0;
  char **tokens = malloc(bufsize * sizeof(char*));
  char *token;

  if(!token){
    fprintf(stderr,"lsh: allocation error\n");
    exit(EXIT_FAILURE);
  }

  token = strtok(line,LSH_TOK_DELIM);
  while(token != NULL){
    tokens[position] = token;
    position++;

    if (position >= bufsize){
      bufsize += LSH_TOK_BUFSIZE;
      tokens = realloc(tokens,bufsize * sizeof(char*));
      if(!tokens){
        fprintf(stderr,"lsh: allocation error\n");
        exit(EXIT_FAILURE);
      }
    }

    token = strtok(NULL,LSH_TOK_DELIM);

  }
  tokens[position] = NULL;
  return tokens;
}

也许你会发现这些代码长得很像，当然如此！我们使用相同的策略实现缓冲区的动态分配，不过这一次我们使用的是以NULL结尾的指针数组，而不是以’\0’结尾的字符数组

在函数的开始，通过对strtok()的调用，我们返回第一个标记的地址，实际上返回的是你给的字符串的地址。且用’\0’替换分隔符号，接着将每一个指针存放在指向字符的指针数组中

如果有必要的话，我们会重新分配指针数组的大小，直到没有token返回，此时终止读取

当我们得到了这些token和存储它的数组，我们要准备解析它了。接下来面临一个问题，我们该怎么做呢？

Shell如何启动进程

现在，我们已经来到了Shell的核心问题——启动进程。写一个Shell程序意味着你需要知道一个进程做了什么，以及怎么去启动它。接下来我们将简单的讨论一下类Unix系统中的进程

在Unix中只有两种方式去启动一个进程。第一种（几乎不算）是Init，当Unix系统启动时，它的内核被加载。当它的内核被加载并初始化时，内核将启动一个进程，即Init。这个进程一直运行在计算机的运行过程中，它负责加载那些其他的计算机所要用到的进程。

由于大多数进程并不是Init,所以实际上只剩下另一种启动进程的方法：系统调用。当调用一个函数时，操作系统复制进程并将他们运行。其中原来的进程被称之为“父进程”，新的进程被称之为“子进程”。将0返回给子进程并将子进程的PID返回给父进程。实际上，这意味着启动新进程的方式就是复制现有的进程。(fork)

这面临着一些问题。典型的，当你想要运行一个新的进程，你并不仅仅想要运行一个一样的进程，而是运行一个不一样的程序。这就是系统调用的意义所在。它用一个全新的程序替换当前正在运行的程序，这意味着当你调用时，操作系统将停止你的进程，加载新程序，并在其位置启该程序。进程不会从调用中返回（除非它发生了错误）(exec)

通过着两种系统调用，我们有了大多数程序在Unixs上运行的基本要素。首先一个现有的进程分成两个单独的部分。然后子进程将被替换成一个新的进程，父进程可以继续做其他的事情，甚至可以通过系统调用继续对子进程进行访问。

讲了这么多，现在，可以终于可以尝试编写一段启动代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lsh_launch(char **args){
  pid_t pid;
  int status;

  pid = fork();
  if(pid == 0){
    //子进程
    if(execvp(args[0],args) == -1){
      perror("lsh");
    }
    exit(EXIT_FAILURE);
  }else if(pid < 0){
    //错误的进程
    perror("lsh");
  }else{
    //父进程
    do{
      wpid = waitpid(pid,&status,WUNTRACED);
    }while (!WIFEXITED(status) && !WIFSIGNALED(status));
  }
  return 1;
}

现在这个函数将使用我们先前解析的参数列表。然后分叉这个进程，并保存返回值（PID）。当fork（）成功返回，此时我们有两个并发的进程。子进程将进入判断逻辑的第一种情况。

在子程序中我们希望能够运行用户的命令。所以我们使用exec系统调用的变种之一execvp。和exec的其他几个变种实现的效果有略微的不同。有的变种需要可变长度的字符串参数，有的则需要字符串列表，还有的需要指定进程使用的环境。而execvp()需要一个程序名称和一个字符串参数的列表（第一个参数必须是程序的名称，而不应该是程序的文件路径），当我们将程序名称传递给它，操作系统将在系统文件路径中去查询它

如果解析命令返回了-1(实际上可能返回其他的)，那么说明产生了错误。此时我们使用perror打印系统的错误信息，前面加上程序的名称，以便于用户知道错误产生于哪里。然后我们退出当前进程以确保程序能继续运行

第二种判断情况说明fork()产生了错误。如果确实如此我们向用户返回错误信息，并确认是否需要终止。

第三种判断情况意味着fork()的子进程创建很成功。此时父进程将待命，我们知道子进程正在运行当前进程，因此父进程需要等待命令的完成。我们使用waitpid()等待进程的状态改变。不过进程的改变可能是由于各种原因，不仅仅只是因为进程终止了，进程可能是因为正常退出了，也可能是因为错误的代码，或是因为信号的终止。所以我们使用waitpid()提供的宏定义等待程序的退出或终止。当函数最终返回1，这意味着我们继续读取命令并执行了

内置函数

你也许会注意到lsh_loop()调用了lsh_execute()，但是在上面，我却又命名了一个函数lsh_launch，这是故意的。你看，大多数的命令在Shell中被解析为程序，但并不是所有，有一些是直接写入Shell中的

原因很简单。如果你想要更改当前所在的目录。你需要使用函数chdir()，问题是文件目录是当前进程的一个属性，所以如果你要使用cd改变当前目录的话，它将改变你当前进程的文件目录，父进程的目录将会保持不变。相反的是，Shell进程本身需要调用chdir()来更新它的目录。然后再启动子进程，它将继承当前的文件目录

相似的，exit程序，它将无法退出调用它的Shell程序，所以这个程序也需要内置在Shell中。当然，许多Shell程序都是通过配置运行配置文件进行的，比如~/.bashrc这些脚本使用更改Shell操作的命令。不过这些命令只有在 shell 进程本身内部实现时才能更改 shell 的操作。

所以这意味着我们需要添加一些Shell本身的命令。这里我们添加cd,exit和help程序，以下是它的实现：

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
//内置函数
int lsh_cd(char **args);
int lsh_help(char **args);
int lsh_exit(char **args);
//内置指令
char *builtin_str[] = {
  "cd",
  "help",
  "exit"
};
//函数指针
int (*builtin_func[])(char **)={
  &lsh_cd,
  &lsh_help,
  &lsh_exit
};

int lsh_num_builtins(){
  return sizeof(builtin_str) / sizeof(char *);
}

int lsh_cd(char **args){
  if(args[1] == NULL){
    fprintf(stderr,"lsh: expected argument to \"cd\"\n");
  }else{
    if(chdir(args[1]) != 0){
      perror("lsh");
    }
  }
  return 1;
}

int lsh_help(char **args){
  int i;
  printf("Stephen Brennan's LSH\n");
  printf("Type program names and arguments,and hit enter.\n");
  printf("The following are built in:\n");

  for(i=0;i<lsh_num_builtins();i++){
    printf(" %s\n",builtin_str[i]);
  }

  printf("Use the man command for information on other programs.\n");
  return 1;
}

int lsh_exit(char **args){
  return 0;
}

这一部分的代码有三个部分，第一部分包含了对函数的声明。提供函数原型是为了你可以使用它（即不定义函数内容，但声明后可以使用）。这是因为我们我们使用lsh_help()时，用到了内置函数数组，这个函数中包含了lsp_help()，如果想要打破这个循环则需要一开始就提供函数原型。

第二部分则是一个字符串数组，存储了函数的名称。后面跟了对应的函数指针的数组。这样将来就可以通过编辑函数数组来实现向其中添加功能，而且可以避免编写大型的switch程序。如果你对builtin_func的作用有所疑惑的话，那没问题！我也是。这是一个函数指针数组（它们都需要提供一个字符串数组，然后返回一个整数型的数值）任何涉及C语言中函数指针的声明都会变得十分复杂。我每次都要搜一下怎么声明3

最终，我们实现了这几个函数功能。lsh_cd函数首先检查第二个参数是否存在，如果不存在的话就打印错误信息。然后调用chdir()检查是否有误并返回。而lsp_help函数则是打印了作品的信息，还有内置的函数功能。最后lsp_exit函数返回0，作为终止循环的信号

分析

最后的一部分就是实现lsh_execute(),这个函数将用来调用内置函数，或是用来启动Shell进程，如果你读到了这里，你就知道我们为自己设置了多么简单的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lsh_execute(char **args){
  int i;
  if(args[0] == NULL){
    //空指令，直接返回
    return 1;
  }
  for(i=0;i<lsh_num_builtins();i++){
    if(strcmp(args[0],builtin_str[i]) == 0)
      return (*builtin_func[i])(args);
  }

  return lsh_launch(args);
}

这些操作实际上是为了检查你输入的命令是否等于内置函数，如果是的话，就调用它，如果不是的话，将会调用lsh_launch()去启动这个进程。如果用户输入了一个空字符串，则会被警告参数为NULL。所以我们需要检查输入

整合

以上就是Shell所有的程序了。如果你耐心的读完了，那么你已经完全理解了Shell是怎么实现的了，快去试试吧。你只需要将这些代码复制到一个文件中，然后编译它。将你需要的文件头包含在里面。接下来我将提供我们从文件头中所用到的函数：

  • #include <sys/wait.h>
    • waitpid() and its macros
  • #include <unistd.h>
    • chdir()
    • fork()
    • exec()
    • pid_t
  • #include <stdlib.h>
    • malloc()
    • realloc()
    • free()
    • exit()
    • execvp()
    • EXIT_SUCCESS,EXIT_FAILURE
  • #include <stdio.h>
    • fprintf()
    • pintf()
    • stderr
    • getchar()
    • perror()
  • #include <string.h>
    • strcmp()
    • strtok()

你可以在开头的链接找到这篇文章的出处和源代码。

翻译加复现和学习差不多花了两天，感觉很有收获，很多地方翻译的不是很好，但是大致能理解。就我个人的感受而言，我感觉看英文的话勉强可以看懂是啥意思，但是翻译成中文的话总是不能很好的表达出来，可能这也和专业水平有关吧（加上我的英语不是很好）。我觉得这是一篇很好的文章，尤其是其中关于进程的部分让我学到了很多东西。我自己也跟着复现了一遍，为此我还配置了我的neovim（真的好帅）,不过由于语法检测没有配置好，所以最后编译的时候还是一堆问题，磕磕绊绊的，但是还是让它成功的跑起来了，很有成就感！

最后附上我完整的程序（作者的信息我并没有修改，毕竟是一次复现）

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

#define LSH_RL_BUFSIZE 1024
#define LSH_TOK_BUFSIZE 64
#define LSH_TOK_DELIM " \t\r\n\a"

//内置函数
int lsh_cd(char **args);
int lsh_help(char **args);
int lsh_exit(char **args);
//内置指令
char *builtin_str[] = {
  "cd",
  "help",
  "exit"
};
//函数指针
int (*builtin_func[])(char **)={
  &lsh_cd,
  &lsh_help,
  &lsh_exit
};

void lsh_loop();
char *lsh_read_line();
char **lsh_split_line(char *line);
int lsh_launch(char **args);
int lsh_execute(char **args);
int lsh_num_builtins();

int main(int argc,char ** argv){
  //加载配置文件（如果有的话）

  //执行循环指令
  lsh_loop();

  //关闭清理操作
  
  return EXIT_SUCCESS;
}

void lsh_loop(){
  char *line;
  char **args;
  int status;

  do {
    printf("> ");
    line = lsh_read_line();
    args = lsh_split_line(line);
    status = lsh_execute(args);

    free(line);
    free(args);
  } while (status);
}

char *lsh_read_line(){
  int bufsize = LSH_RL_BUFSIZE;
  int position = 0;
  char *buffer = malloc(sizeof(char) * bufsize);
  int c;
  
  if(!buffer){
    fprintf(stderr,"lsh: allocation error\n");
    exit(EXIT_FAILURE);
  }

  while (1){
    //读取字符
    c = getchar();

    //确定结束条件
    if(c == EOF || c == '\n'){
      buffer[position] = '\0';
      return buffer;
    }else{
      buffer[position] = c;
    }
    position++;

    //如果超出缓冲区，则拓展新的缓冲区
    if (position >= bufsize){
      bufsize += LSH_RL_BUFSIZE;
      buffer = realloc(buffer,bufsize);
      if(!buffer){
        fprintf(stderr,"lsh: allocation error\n");
        exit(EXIT_FAILURE);
      }
    }
  }
}

/*
//getline实现行读取
char *lsh_read_line(){
  char *line = NULL;
  ssize_t bufsize = 0;
  if (getline(&line,&buffer,stdin) == -1){
    if (feof(stdin)){
      exit(EXIT_SUCCESS); //读取到了EOF
    }else{
      perror("readline");
      exit(EXIT_FAILURE);
    }
  }
  return line;
}
*/

char **lsh_split_line(char *line){
  int bufsize = LSH_TOK_BUFSIZE,position = 0;
  char **tokens = malloc(bufsize * sizeof(char*));
  char *token;

  if(!token){
    fprintf(stderr,"lsh: allocation error\n");
    exit(EXIT_FAILURE);
  }

  token = strtok(line,LSH_TOK_DELIM);
  while(token != NULL){
    tokens[position] = token;
    position++;

    if (position >= bufsize){
      bufsize += LSH_TOK_BUFSIZE;
      tokens = realloc(tokens,bufsize * sizeof(char*));
      if(!tokens){
        fprintf(stderr,"lsh: allocation error\n");
        exit(EXIT_FAILURE);
      }
    }

    token = strtok(NULL,LSH_TOK_DELIM);

  }
  tokens[position] = NULL;
  return tokens;
}

int lsh_launch(char **args){
  pid_t pid;
  int status;

  pid = fork();
  if(pid == 0){
    //子进程
    if(execvp(args[0],args) == -1){
      perror("lsh");
    }
    exit(EXIT_FAILURE);
  }else if(pid < 0){
    //错误的进程
    perror("lsh");
  }else{
    //父进程
    do{
      waitpid(pid,&status,WUNTRACED);
    }while (!WIFEXITED(status) && !WIFSIGNALED(status));
  }
  return 1;
}

int lsh_num_builtins(){
  return sizeof(builtin_str) / sizeof(char *);
}

int lsh_cd(char **args){
  if(args[1] == NULL){
    fprintf(stderr,"lsh: expected argument to \"cd\"\n");
  }else{
    if(chdir(args[1]) != 0){
      perror("lsh");
    }
  }
  return 1;
}

int lsh_help(char **args){
  int i;
  printf("Stephen Brennan's LSH\n");
  printf("Type program names and arguments,and hit enter.\n");
  printf("The following are built in:\n");

  for(i=0;i<lsh_num_builtins();i++){
    printf(" %s\n",builtin_str[i]);
  }

  printf("Use the man command for information on other programs.\n");
  return 1;
}

int lsh_exit(char **args){
  return 0;
}

int lsh_execute(char **args){
  int i;
  if(args[0] == NULL){
    //空指令，直接返回
    return 1;
  }
  for(i=0;i<lsh_num_builtins();i++){
    if(strcmp(args[0],builtin_str[i]) == 0)
      return (*builtin_func[i])(args);
  }

  return lsh_launch(args);
}

  1. 在作者那个时候可能没有getline()不过后文有补充↩︎

  2. 我一开始不信，尝试并了解了一下确实如此，getchar()返回的是一个整数↩︎

  3. 作者在这里补充了一句，距离写这个文章之后过去了6年。期间他仍然是以写C语言为主，但是每次遇到函数指针的问题，他还是得谷歌一下（函数指针真的怪怪的）↩︎

发表于 更新于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

简单结束了数组和字符串的学习，现在来继续学习哈希表的内容

设计哈希表

设计哈希集合

哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

不使用任何内建的哈希表库设计一个哈希集合（HashSet），实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
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
class MyHashSet(object):
    def __init__(self):
        self.capacity = 1e5
        self.bucket = dict()

    def add(self, key:int)->None:
        if self.contains(key):
            return
        if key%self.capacity in self.bucket.keys():
            self.bucket[key%self.capacity].append(key)
        else:
            self.bucket[key%self.capacity] = [key]

    def remove(self, key:int)->None:
        if not self.contains(key):
            return 
        if key%self.capacity in self.bucket.keys():
            if key in self.bucket[key%self.capacity]:
                self.bucket[key%self.capacity].remove(key)

    def contains(self, key:int)->bool:
        if key % self.capacity in self.bucket.keys():
            if key in self.bucket[key%self.capacity]:
                return True
            else:
                return False
        else:
            return False

实际上这里是使用python的字典方法替代了链表的使用

设计哈希映射

哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

不使用任何内建的哈希表库设计一个哈希映射（HashMap），实现 MyHashMap 类，MyHashMap() 用空映射初始化对象

  • void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
  • int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
  • void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyHashMap(object):
    def __init__(self):
        self.capcity = 1e5
        self.bucket = dict()

    def put(self, key:int, value:int)->None:
        if not key%self.capcity in self.bucket.keys():
            self.bucket[key%self.capcity] = {key:value}
        else:
            self.bucket[key%self.capcity][key] = value

    def get(self, key:int)->int:
        if key%self.capcity in self.bucket.keys():
            if key in self.bucket[key%self.capcity].keys():
                return self.bucket[key%self.capcity][key]
        return -1
        

    def remove(self, key:int)->None:
        if not key%self.capcity in self.bucket.keys():
            return
        if key%self.capcity in self.bucket.keys():
            if key in self.bucket[key%self.capcity].keys():
                del self.bucket[key%self.capcity][key]

这里同样是使用字典实现的hash映射，要注意python中常见的用于处理字典的函数操作

哈希集合

哈希集合实际上是一个不包含重复元素的集合数据结构。它只存储元素本身，不存储与元素相关联的值。我们可以用python中的set()和dict()实现，他们实际上都是使用的hash存储结构

快乐数

哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def isHappy(self, n:int)->bool:
        temp = set()
        while n!=1:				# 用于确定计算新的平方和
            next = 0
            while n!=0:
                first = n%10
                next += first**2
                n //=10
            if next in temp:	 # 用于检查是否存在，如果存在说明不是快乐数
                return False	 
            else:
                temp.add(next)
                n = next		 # 记得要更新n的值
        return True

这里的考察实际上是对于hash存储结构的使用的考察，我们在这里用的是set()

两个数组的交集

哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

1
2
3
4
5
class Solution(object):
    def intersection(self, nums1:List[int], nums2:List[int])->List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return [x for x in set1 if x in set2]

由于python的for ... in ...查找操作相当于对hash表的查找操作，所以直接快捷方式结束了

哈希映射

哈希映射是用于存储键值对结构的，也就是python中的字典结构

同构字符串

哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

1
2
3
4
5
6
7
8
9
class Solution(object):
    def isIsomorphic(self, s:str, t:str)->bool:
        st,ts = {},{}
        for x,y in zip(s,t):
            if x in st and st[x] != y or y in ts and ts[y] != x:
                return False
            else:
                st[x],ts[y] = y,x
        return True

这里的zip()用于将多个可迭代对象（列表，数组等）打包成同一个对象，这里是将其打包为了一个字典对象

第一个唯一字符

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

1
2
3
4
5
6
7
class Solution:
    def firstUniqChar(self, s: str) -> int:
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return i
        return -1

？？？内置函数

我突然后悔了，我本来学算法是希望能学一点相关的算法知识，但是我报了Python 赛道，发现根本不是在学算法，感觉像是在学语法

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

信息安全法律基础的老师留了一个问题，和朋友石头剪刀布输了，所以是我来回答这个问题。那么

人生的价值是什么？

以前也想过这个问题，但更多是讲给别人听的，告诉他们要积极要向上。但是很少认真的考虑这个问题，拿出一个让我自己的满意的答案。寻寻觅觅，想了一段时间，感觉大概有能拿出来说一说的想法了吧。所以记录在这里：

一串数字，它可以是你的手机密码，可以是你暗恋的女生的生日，可以是路口第一辆车的车牌号，也可以是仅仅只是一串数字。不同的场景，不同的人看到它都会有着各种各样的理解与认识。我想这串数字本没有意义，它的“价值”是被人为的赋予的。就像是棋盒里的黑白棋子，它本来并不包含什么信息，但是当它落在棋盘中的瞬间，却被赋予各种各样的信息与“价值”；亦或是程序中的二进制，对于人类而言，杂乱无章毫无意义，但是在机器的眼中却是他们工作的金科玉律。

我想，人也大概如此。人生，剥离与外界的关系，无非是几句话加上几个动作，从本质来看也是这么一串”数字”。它的本身并没有什么意义，但是将它与外界联系起来，人生就有了无穷的意义。所以我认为，人生的价值更多是被”人”赋予的，你的行为和话语，会产生各种各样的影响，对不同的人产生不同的价值。可能一次无意间的囧事，陌生的人会嘲笑你，熟悉你的人会安慰你，爱你的人会包容你。这是因为大家对你的认识与理解不同，你的囧事本质上是一堆信息，但是被赋予的“价值”不同。想到这里，也许会觉得很恐怖吧，自己的价值依附于他人的评价。当然不！你还有自己，你也是“人”，你也可以为自己的行为赋予各种各样的意义。我想这就是这个问题的关键，价值是被人赋予的，这其中既有别人，也有自己，人生不仅被他人定义，也由自己决定。

外界的声音总是嘈杂的，就算是圣人也有人批判。所以人生的价值应从自己出发，《孟子》中有这么一句话“穷则独善其身，达则兼济天下”，我觉得人生的价值就是这样，从自己开始，由己及外，去探索自己的价值。首先是要对自己好一点，满足自我的价值。然后再去实现对于他人的价值，而不是好高骛远的，渴望所有人的认可。英国伦敦有一座教堂，旁边的碑石有这么一句话：

“当我年轻的时候，我梦想改变这个世界；

当我成熟以后，我发现我不能改变这个世界，我将目光缩短一点，打算只改变我的国家；

当我进入暮年以后，我发现我不仅不能改变我的国家，我的最后愿望仅仅是改变一下我的家庭，但是这也是不可能的

我现在躺在床上，行将就木之时，我突然意识到：

如果一开始我仅仅去改变自己，然后可能会改变我的家庭；

然后在家人的支持和帮助下，我可能会为国家做一点事；

然后，谁知道呢？我甚至可以改变这个世界”

正如《礼记》中“修身，齐家，治国，平天下”的抱负，我们追求的人生价值大抵也该如此吧。

但是我真正想说的并不是这些，让一个十八岁的大学生去大谈人生价值就像是问四五岁的小朋友为什么想当科学家一样，没有什么参考价值。未来我还会经历各种各样的事情，而现在的我，知道的太多，经历的却太少。人生的价值？我也不太清楚。如果你问我人生的价值是什么，人生的意义是什么？我现在更想打会儿游戏，听听歌，和喜欢的女生聊聊天，吃点想吃的东西，学点想学的技术。

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

这是第二遍学KMP算法，第一遍学习的过程中，对他的原理理解的是云里雾里。现在回过头来，深度学习一下KMP算法

首先我们要清楚什么是KMP算法？

KMP

KMP算法的优点相较于暴力匹配算法(BF)更有效率。这是因为KMP算法会利用每次匹配得到的已有的信息，来进行回溯。从而开始一次新的匹配。而暴力算法由于重复的匹配，其复杂度为 O(m*n)；KMP算法的主串指针始终向前，所以复杂度为 O(m+n)

next数组

我看很多教程一开始都是先讲KMP算法的实现，只是提了一嘴next数组的大致内容，我觉得挺难懂的。所以这里先从next数组开始讲起：

要讲next数组，我们首先要从字符串的最大公共前后缀讲起，下面的图片很好的体现了这个概念。每次增大子串的长度，然后求得其对应的最大公共前后缀长度。

image.png

在求的子串的最大公共前后缀组后，我们便可以着手开始建立我们的next数组。

（1）首先我们需要明确next数组在这里的作用是什么？

当模式串的某个字符与主串的某个字符失配时，我们需要根据失配的位置 j,还有我们的 next数组，来确定下一次模式串开始匹配的位置。下一步用 next[j]处的字符继续与主串 i处的字符进行匹配。相当于将模式串向右移动了 j-next[j]的长度

（2）接下来的难点在于如何构建next数组

首先我们让 next[0] = -1作为一个标记，且我们容易得到 next[1] = 0，那么在此基础之上，我们需要结合现有的信息来递推下一个 next[j+1]的值。现在问题转换成了，如何利用已有信息，求下一个 next[j+1]的值？

对此我们需要分成两种情况进行判断：

  • 当p_k = p_j时，next[j+1] = next[j] + 1 = k+1,代表该字符前有最大长度为k+1的最大公共前后缀
image.png
  • 当p_k != p_j时，我们就需要寻找更短的最大公共前后缀，此时关键来了，怎么找寻更短的最大公共前缀？
image.png

​ 因为 P_k!=P_j，所以我们需要再次尝试 P_next[k]和 P_j的比较，如此一直递归下去。直到得到 P_next[next[...]]和 P_j相 等，从而令 next[j+1] = next[index[P_next[…]]] + 1 = k+1；或者始终不能成功配对，则令 next[j+1] = 0

现在我们可以写出next数组的递推算法：

1
2
3
4
5
6
7
8
9
10
11
12
void GetNext(char T[]){
    int j=0,k=-1;
    next[j] = k;
    while (T[j]!='\0'){
        if(k==-1||T[j]==T[k]){
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

这个程序还有一个递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
int GetNext(int j,char T[]){
    if(j==0)return -1;
    if(j>0){
        int k = GetNext(j-1,T);
        while(k>=0){
            if(T[j-1]==T[k])return k+1;
            else k=GetNext(k,T);
        }
        return 0;
    }
    return 0;
}

KMP算法

我们在得到next数组之后，便可以根据next数组的特性和简单的判断，来实现我们的KMP算法，以下是我们的算法流程：

  • 如果j = -1，则i++，j++，继续匹配下一个字符
  • 如果S[i] = T[j]，则i++，j++，继续匹配下一个字符
  • 如果j != -1，且S[i] != P[j]，则i不变，j = next[j]。这意味着失配，接下来模式串需要对主串相对右移j-next[j]的距离

现在我们可以写出完整的KMP算法：

1
2
3
4
5
6
7
8
9
10
11
12
int KMP(int start,char S[],char T[]){
    int i = start,j = 0;
    while(S[i]!='\0'&&T[j]!='\0'){
        if(j==-1||S[i]==T[j]){
            i++;		//下一个字符的比较
            j++;		//模式串右移
        }
        else j = next[j];
    }
    if(T[j]=='\0') return(i-j);		//匹配成功则返回下标（当前比较位-比较长度 = 起始下标）
    else return -1;
}

当然，在KMP的基础之上，还有很多优化之后的算法，在此就不过多赘述

Python版本

这个是python版本的KMP算法，基本上一样，只不过边界条件的判断改为使用长度判断。

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
class Solution(object):
    def strStr(self, haystack:str, needle:str)->int:
        next = self.getnext(needle)
        h,n = 0,0
        while h<len(haystack) and n<len(needle):
            if n==-1 or haystack[h] == needle[n]:
                h += 1
                n += 1
            else:
                n = next[n]
        if n == len(needle):
            return h-n
        else:
            return -1

    def getnext(self,T:str)->List[int]:
        j=0
        k=-1
        next = [0 for i in range(len(T))]
        next[j]=k
        while j <len(T)-1:
            if k==-1 or T[j]==T[k]:
                j+=1
                k+=1
                next[j] = k
            else:
                k = next[k]
        return next

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

继续算法的日常练习

字符串

最大公共前缀

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数来查找字符串数组的最大公共前缀；如果不存在，则返回 ""

1
2
3
4
5
6
7
8
9
10
11
12
def longestCommonPrefix(self, strs:List(str))->str:
        min_str = min(strs, key=len)
        result = ""
        p = 0
        while p < len(min_str):
            char = strs[0][p]
            for s in strs:
                if s[p] != char:
                    return result
            result += char
            p += 1
        return result

先纵向比对第一个字符，如果均为相同，则加入返回值中；若不正确，则直接返回

最长回文子串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字串s找到s中最长的子串,并返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def longestPalindrome(self, s:str)->str:
        ans = ""
        for i in range(len(s)):
            temp = self.search(s,i,i)
            if len(temp) > len(ans):
                ans = temp
            temp = self.search(s,i,i+1)
            if len(temp) > len(ans):
                ans = temp
        return ans

    def search(self,s,first,end):
        while first>=0 and end<len(s) and s[first] == s[end]:
            first -= 1
            end += 1
        return s[first+1:end]

首先构造一个中心回文的函数 search,先为两边设置边界条件，然后当中心索引两边的值相等时，则向外拓展。我们构造这个辅助函数之后，在主函数中调用。（需要考虑奇偶回文的情况）

翻转字符串里的单词

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字符串s，反转字符串中单词的顺序

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

1
2
def reverseWords(self, s:str)->str:
    return (" ").join(s.split()[::-1])

啊，因为python丰富的内置函数，直接做完了。可以稍微讲下这几个函数的用法：

  • ("拼接符号").join(待拼接数组)
  • (待分隔数组).split(分隔符号)

双指针

指针常用的两种用法：

  • 首尾指针
  • 快慢指针

反转字符串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题

1
2
3
4
5
6
7
def reverseString(self, s):
    i,j = 0,len(s)-1
    while i<j:
        s[i],s[j] = s[j],s[i]
        i += 1
        j -= 1
    return s

这里实际上是用了双指针的思想，相对移动然后互换位置。python中虽然没有指针，但是我们仍然可以通过数组去模拟这个过程，不过设置边界条件时一定要注意

数组拆分

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def arrayPairSum(self, nums:List[int])->int:
        ans = 0
        nums = self.quick_sort(nums)
        print(nums)
        for i in range(len(nums)//2):
            ans += nums[i*2]
        return ans

    def quick_sort(self,array):
        if len(array) <= 1:
            return array
        else:
            reference = array[0]
            small = [s for s in array[1:] if s < reference]
            equal = [e for e in array if e == reference]
            large = [l for l in array[1:] if l > reference]
        return self.quick_sort(small) + equal + self.quick_sort(large)

这道题主要在于分析怎么得到最大总和，观察可以发现先对数组进行排序，再将已排序数组的偶数位累加即可。排序的话要尽量使用，较快的排序，不然会超时（冒泡就超了），所以这里使用快速排序

两数之和

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

1
2
3
4
5
6
7
8
9
10
def twoSum(self, numbers:List[int], target:int)->List[int]:
	i,j = 0,len(numbers)-1
	while True:
		a = numbers[i]+numbers[j]
		if a>target:
			j -= 1
		elif a<target:
			i += 1
		else:
			return [i+1,j+1]

对于这类题可以用一种匹配方式，有效的减少重复的索引：

  • 双指针指向首尾，求和与target进行比较
  • 当值较小时，我们将首指针前移
  • 当值较大时，我们将尾指针后移

移除元素

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
  • nums 的其余元素和 nums 的大小并不重要。
  • 返回 k
1
2
3
4
5
6
7
def removeElement(self, nums:List[int], val:int)->int:
       slow = 0
       for fast in range(len(nums)):
           if nums[fast] != val:
               nums[slow] = nums[fast]
               slow += 1
       return slow

快慢指针，一个负责定位，一个负责向前索引匹配。这个思想十分常见

最大连续的1的个数

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数

1
2
3
4
5
6
7
8
9
10
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    a,b = 0,0  # 分别存储当前最大连续数与历史最大连续数
    for i in range(len(nums)):
        if nums[i] == 0:
            if a > b:
                b = a
            a = 0
        else:
            a += 1
    return max(a,b)

这里，我用了一个比较清晰的答案，同时这里也体现了快慢指针的思想，很优雅

长度最小的子数组

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
def minSubArrayLen(self, target:int, nums:List[int])->int:
    left,right = 0,0
    count = len(nums)+1
    sum = 0
    while right < len(nums):
        sum += nums[right]
        while sum >= target:
            count = min(count,right-left+1)
            sum -= nums[left]
            left += 1
        right += 1
    return 0 if count==len(nums)+1 else count

这里使用了尺缩法，其大致流程如下：

  • 右边界右移，直到和大于target，令左边界右移
  • 若和仍然大于target，左边界继续右移
  • 若和小于target，右边界右移

这种和上面的相对收缩有着异曲同工之妙，但是这里是追及收缩，要注意边界条件

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

互联今日

我本来有好多好多话想说啊

写着写着什么也写不下去了

很怀念以前在网上认识的朋友们

再看看如今的网络环境 唏嘘不已