今天开始开启了人生新阶段，从学生身份转变为社会人儿了。

也从 3 年的 CVer 即将变成 Coder 了。

3 年的 CV 生涯可以说是毫无建树，希望在未来的两年能够有所收获，成为一名工程师。

码农界流传着一种说法，想要获得长足的发展，基础一定要牢固。所以我决定花半年左右的时间学习《操作系统》这门课程，至于为什么是操作系统，因为 jyywiki.cn 的教程制作精良，不学有些可惜了。

本系列的博客主要为 jyywiki.cn 的示例代码作笔记，以便于加深印象。

Today marks the beginning of a new chapter in my life, transitioning from a student to a member of the working world.

I’m also about to go from a CVer of 3 years to a Coder.

My 3 years of CV research can hardly be said to have accomplished anything. I hope to gain something in the next two years and become an engineer.

There’s a saying among coders: to achieve long-term growth, you must have a solid foundation. So I’ve decided to spend about half a year studying the Operating Systems course. Why operating systems? Because the tutorials on jyywiki.cn are so well-made that it would be a shame not to study them.

This blog series mainly serves as notes on the example code from jyywiki.cn, to help deepen my understanding.

绪论

Demo: 数学概念的探索与发现

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
# Life is short; you need Python.
import z3
import numpy as np
import sympy as sp
import matplotlib.pyplot as plt

x = sp.symbols('x')

def plot(f, points, draw_label=True, draw_points=True):
    """Plot a sympy symbolic polynomial f."""

    xmin = min([x_ for x_, _ in points], default=-1) - 0.1
    xmax = max([x_ for x_, _ in points], default=1) + 0.1

    xs = np.arange(xmin, xmax, (xmax - xmin) / 100)
    ys = [f.subs(x, x_) for x_ in xs]

    plt.grid(True)
    plt.plot(xs, ys)
    if draw_points:
        plt.scatter(
            [x_ for x_, y_ in points],
            [y_ for x_, y_ in points],
        )
    if draw_label:
        for x_, y_ in points:
            plt.text(x_, y_, f'$({x_},{y_})$', va='bottom', ha='center')
        plt.title(f'$y = {sp.latex(f)}$')

这是一段 Python 的代码，用于画一个函数的图像，其中 z3 库可以用于解方程（就先这么认为吧）， numpy 很熟悉了，现代人工智能的基石，sympy 与 numpy 不同，它是用于符号计算（而不是数值计算）的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def interpolate(n, xs, ys):
    """Return a polynomial that passes through all given points."""
    n = max(n, len(xs), len(ys))
    if len(xs) == 0: xs = [sp.symbols(f'x{i}') for i in range(n)]
    if len(ys) == 0: ys = [sp.symbols(f'y{i}') for i in range(n)]
    vs = [sp.symbols(f'a{i}') for i in range(n)]
    power = list(range(n))
	
    # 1
    cons = [
        sum(
            v * (x_ ** k) for v, k in zip(vs, power)
        ) - y
            for x_, y in zip(xs, ys)
    ]
    # end 1
    # 2
    sol = list(sp.linsolve(cons, vs))[0]
    # end 2
    f = (sum(
        v * (x ** k) for v, k in zip(sol, power)
    ))
    return f

第二个代码比第一个更加晦涩一些，主要涉及库的使用方法。这个函数的目的是给定一些点，找到一条多项式曲线能够穿过这些点。# 1 的部分构建了一系列关于系数的线性方程组，这可以说是大学线性代数的知识，也可以说是初中的解方程组知识，# 2 的部分是求解方程组获得系数，最后 f 返回符号方程。

其实我看的也很晕。

于是调试了一下看看输出的都是什么东西。

1
2
3
4
5
6
7
8
9
10
11
xs = [-1, 0, 1, 2, 3]
ys = [-1, 2, 1, 4, 5]
f = interpolate(0, xs, ys)

print(cons)
# [a0 - a1 + a2 - a3 + a4 + 1, a0 - 2, a0 + a1 + a2 + a3 + a4 - 1, a0 + 2*a1 + 4*a2 + 8*a3 + 16*a4 - 4, a0 + 3*a1 + 9*a2 + 27*a3 + 81*a4 - 5]
print(sol)
# (2, -3/2, -17/12, 5/2, -7/12)
print(f)
# -7*x**4/12 + 5*x**3/2 - 17*x**2/12 - 3*x/2 + 2

Demo: 模拟数字系统

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
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>

typedef bool wire; // Wires
typedef struct {
  bool value;
  wire *in, *out;
} reg; // Flip-flops

// Circuit constructs
#define CLOCK       for (; ; END_CYCLE)
#define NAND(X, Y)  (!((X) && (Y)))
#define NOT(X)      (NAND(X, 1))
#define AND(X, Y)   (NOT(NAND(X, Y)))
#define OR(X, Y)    (NAND(NOT(X), NOT(Y)))

// Circuit emulation helpers
#define END_CYCLE ({ end_cycle(); putchar('\n'); fflush(stdout); sleep(1); })
#define PRINT(X) printf(#X " = %d; ", X)

// Wire and register specification
wire X, Y, X1, Y1, A, B, C, D, E, F, G;
reg b1 = {.in = &X1, .out = &X};
reg b0 = {.in = &Y1, .out = &Y};

// Dump wire values at the end of each cycle
void end_cycle() {
  PRINT(A); PRINT(B); PRINT(C); PRINT(D);
  PRINT(E); PRINT(F); PRINT(G);
}

int main() {
  CLOCK {
    // 1. Wire network specification (logic gates)
    X1 = AND(NOT(X), Y);
    Y1 = NOT(OR(X, Y));
    A = D = E = NOT(Y);
    B = 1;
    C = NOT(X);
    F = Y1;
    G = X;

    // 2. Lock data in flip-flops and propagate output to wires
    b0.value = *b0.in;
    b1.value = *b1.in;
    *b0.out = b0.value;
    *b1.out = b1.value;
  }
}

这是一个模拟数码管的程序，嗯… 记得单片机课程上学过数码管啥的，但是忘没了啊。这段代码实际上就是 VHDL 的写法。

但是这里有一个我已经遗忘了的 C 语言语法，结构体初始化的时候使用.符号来指定初始化成员。

1
reg b1 = {.in = &X1, .out = &X};

为了验证这段程序是正确的，写一个 Python 脚本来解析一下上个程序的输出。

这里涉及到了 Unix 哲学，“管道”。

1
./a.out | python3 seven-seg.py  # The UNIX Philosophy

seven-seg.py 的写法如下：

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
import fileinput
 
DISPLAY = '''
     AAAAAAAAA
    FF       BB
    FF       BB
    FF       BB
    FF       BB
     GGGGGGGG
   EE       CC
   EE       CC
   EE       CC
   EE       CC
    DDDDDDDDD
''' 

# STFW: ANSI Escape Code
CLEAR = '\033[2J\033[1;1f'
BLOCK = {
    0: '\033[37m░\033[0m',
    1: '\033[31m█\033[0m',
}

for line in fileinput.input():
    # Load "A=0; B=1; ..." to current context
    exec(line)

    # Render the seven-segment display
    pic = DISPLAY
    for seg in set(DISPLAY):
        if seg.isalpha():
            val = globals()[seg]  # 0 or 1
            pic = pic.replace(seg, BLOCK[val])

    # Clear screen and display
    print(CLEAR + pic)

这里有一个很有趣的想法，是我没有想到的。当看到DISPLAY 的时候我大概知道是要进行替换，我的想法自然是从 a.out 输出的字符串中进行解析，获得 A - G 的值。

而这段代码却直接把 a.out 的输出直接作为 Python 代码执行了。exec(line)，然后再通过 globals() 字典获得 A - G 的值。

demo2

Demo: 模拟 RISC-V 指令执行

这个Demo就更难了，作了一个模拟指令执行的程序来求解鸡兔同笼问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//@file_name: uncore.c
static inline bool inst_fetch(inst_t *in) {
  union {
    inst_t i;
    u32 u;
  } u;
  int r = scanf("%x", &u.u);
  *in = u.i;
  return r > 0;
}

static inline void ebreak(CPUState *cpu) {
  switch (cpu->x[10]) {
    case 1: { putchar(cpu->x[11]); break; }
    case 2: { printf("%d", cpu->x[11]); break; }
    case 3: { cpu->on = false; break; }
    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
45
46
47
48
49
50
//@file_name: rvemu.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef uint32_t u32;

typedef struct { u32 op:7, rd:5, f3:3, rs1:5, rs2:5, f7:7; } inst_t;
typedef struct {
  u32 on, x[32];
} CPUState;

// Uncore:
//   inst_fetch - read an instruction from stdin
//   ebreak - hyper call: putchar/putd/exit
#include "uncore.c"

static inline u32 sext(u32 val, u32 n) {
  // Sign extend n-bit integer val to 32-bit
  u32 mask = ~((1 << n) - 1);
  u32 set = (val >> (n - 1)) & 1;
  u32 ret = set ? (val | mask) : val;
  return ret;
}

int main(int argc, char *argv[]) {
  CPUState cpu = {.on = 1, .x = { 0 }}; // The RESET state
  for (int i = 0; argv[i + 1] && i < 8; i++) {
    cpu.x[10 + i] = atoi(argv[i + 1]); // Set a0-a7 to arguments
  }

  inst_t in;
  while (cpu.on && inst_fetch(&in)) {
    // For each fetched instruction, execute it following the RV32I spec
    u32 op = in.op, f3 = in.f3, f7 = in.f7;
    u32 imm = sext((f7 << 5) | in.rs2, 12), shamt = in.rs2;
    u32 rd = in.rd, rs1_u = cpu.x[in.rs1], rs2_u = cpu.x[in.rs2], res = 0;

    #define __ else if // Bad syntactic sugar!
    if (op == 0b0110011 && f3 == 0b000 && f7 == 0b0000000) res = rs1_u + rs2_u;
    __ (op == 0b0110011 && f3 == 0b000 && f7 == 0b0100000) res = rs1_u - rs2_u;
    __ (op == 0b0010011 && f3 == 0b000)                    res = rs1_u + imm;
    __ (op == 0b0010011 && f3 == 0b001 && f7 == 0b0000000) res = rs1_u << shamt;
    __ (op == 0b0010011 && f3 == 0b101 && f7 == 0b0000000) res = rs1_u >> shamt;
    __ (op == 0b1110011 && f3 == 0b000 && rd == 0 && imm == 1) ebreak(&cpu);
    else assert(0);
    if (rd) cpu.x[rd] = res;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@file_name: ji_tu.txt
00050713
00151793
40f587b3
0017d793
00200513
40f705b3
00100073
00100513
02000593
00100073
00200513
00078593
00100073
00100513
00a00593
00100073
00300513
00100073
0000006f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a.out: rvemu.c uncore.c
# RTFM: Automatic variables
	gcc -ggdb -Wall $<

run: a.out
	@echo 2 Head, 4 Feet:
	@cat ji-tu.txt | ./a.out 2 4
	@echo 2 Head, 6 Feet:
	@cat ji-tu.txt | ./a.out 2 6
	@echo 2 Head, 8 Feet:
	@cat ji-tu.txt | ./a.out 2 8
	@echo 35 Head, 94 Feet:
	@cat ji-tu.txt | ./a.out 35 94

clean:
	rm -f a.out

这个 Demo 实在看不懂，不过也有所收获，就是这段代码也有一个我遗忘的 C 语法，用 : 来指定结构体的默认值。

1
typedef struct { u32 op:7, rd:5, f3:3, rs1:5, rs2:5, f7:7; } inst_t;

看来我的 C 基础不行啊。

Introduction

Demo: Exploring and Discovering Mathematical Concepts

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
# Life is short; you need Python.
import z3
import numpy as np
import sympy as sp
import matplotlib.pyplot as plt

x = sp.symbols('x')

def plot(f, points, draw_label=True, draw_points=True):
    """Plot a sympy symbolic polynomial f."""

    xmin = min([x_ for x_, _ in points], default=-1) - 0.1
    xmax = max([x_ for x_, _ in points], default=1) + 0.1

    xs = np.arange(xmin, xmax, (xmax - xmin) / 100)
    ys = [f.subs(x, x_) for x_ in xs]

    plt.grid(True)
    plt.plot(xs, ys)
    if draw_points:
        plt.scatter(
            [x_ for x_, y_ in points],
            [y_ for x_, y_ in points],
        )
    if draw_label:
        for x_, y_ in points:
            plt.text(x_, y_, f'$({x_},{y_})$', va='bottom', ha='center')
        plt.title(f'$y = {sp.latex(f)}$')

This is a piece of Python code used to plot the graph of a function. The z3 library can be used to solve equations (let’s just think of it that way for now). numpy is very familiar — it’s the cornerstone of modern AI. sympy is different from numpy: it is used for symbolic computation (rather than numerical computation).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def interpolate(n, xs, ys):
    """Return a polynomial that passes through all given points."""
    n = max(n, len(xs), len(ys))
    if len(xs) == 0: xs = [sp.symbols(f'x{i}') for i in range(n)]
    if len(ys) == 0: ys = [sp.symbols(f'y{i}') for i in range(n)]
    vs = [sp.symbols(f'a{i}') for i in range(n)]
    power = list(range(n))
	
    # 1
    cons = [
        sum(
            v * (x_ ** k) for v, k in zip(vs, power)
        ) - y
            for x_, y in zip(xs, ys)
    ]
    # end 1
    # 2
    sol = list(sp.linsolve(cons, vs))[0]
    # end 2
    f = (sum(
        v * (x ** k) for v, k in zip(sol, power)
    ))
    return f

The second piece of code is more obscure than the first, mainly involving the usage of the libraries. The purpose of this function is: given some points, find a polynomial curve that passes through them. The # 1 part builds a series of linear equations about the coefficients — this is college linear algebra knowledge, or you could say it’s middle-school equation solving. The # 2 part solves the equations to obtain the coefficients, and finally f returns the symbolic equation.

To be honest, I was quite confused looking at it too.

So I did some debugging to see what the outputs actually are.

1
2
3
4
5
6
7
8
9
10
11
xs = [-1, 0, 1, 2, 3]
ys = [-1, 2, 1, 4, 5]
f = interpolate(0, xs, ys)

print(cons)
# [a0 - a1 + a2 - a3 + a4 + 1, a0 - 2, a0 + a1 + a2 + a3 + a4 - 1, a0 + 2*a1 + 4*a2 + 8*a3 + 16*a4 - 4, a0 + 3*a1 + 9*a2 + 27*a3 + 81*a4 - 5]
print(sol)
# (2, -3/2, -17/12, 5/2, -7/12)
print(f)
# -7*x**4/12 + 5*x**3/2 - 17*x**2/12 - 3*x/2 + 2

Demo: Simulating a Digital System

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
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>

typedef bool wire; // Wires
typedef struct {
  bool value;
  wire *in, *out;
} reg; // Flip-flops

// Circuit constructs
#define CLOCK       for (; ; END_CYCLE)
#define NAND(X, Y)  (!((X) && (Y)))
#define NOT(X)      (NAND(X, 1))
#define AND(X, Y)   (NOT(NAND(X, Y)))
#define OR(X, Y)    (NAND(NOT(X), NOT(Y)))

// Circuit emulation helpers
#define END_CYCLE ({ end_cycle(); putchar('\n'); fflush(stdout); sleep(1); })
#define PRINT(X) printf(#X " = %d; ", X)

// Wire and register specification
wire X, Y, X1, Y1, A, B, C, D, E, F, G;
reg b1 = {.in = &X1, .out = &X};
reg b0 = {.in = &Y1, .out = &Y};

// Dump wire values at the end of each cycle
void end_cycle() {
  PRINT(A); PRINT(B); PRINT(C); PRINT(D);
  PRINT(E); PRINT(F); PRINT(G);
}

int main() {
  CLOCK {
    // 1. Wire network specification (logic gates)
    X1 = AND(NOT(X), Y);
    Y1 = NOT(OR(X, Y));
    A = D = E = NOT(Y);
    B = 1;
    C = NOT(X);
    F = Y1;
    G = X;

    // 2. Lock data in flip-flops and propagate output to wires
    b0.value = *b0.in;
    b1.value = *b1.in;
    *b0.out = b0.value;
    *b1.out = b1.value;
  }
}

This is a program that simulates a seven-segment display. Hmm… I remember learning about seven-segment displays in the microcontroller course, but I’ve forgotten it all. This code is actually written in the style of VHDL.

But there’s a C syntax here that I had forgotten: when initializing a struct, the . symbol is used to specify the members being initialized.

1
reg b1 = {.in = &X1, .out = &X};

To verify that this program is correct, I wrote a Python script to parse the output of the previous program.

This involves the Unix philosophy — the “pipe”.

1
./a.out | python3 seven-seg.py  # The UNIX Philosophy

seven-seg.py is written as follows:

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
import fileinput
 
DISPLAY = '''
     AAAAAAAAA
    FF       BB
    FF       BB
    FF       BB
    FF       BB
     GGGGGGGG
   EE       CC
   EE       CC
   EE       CC
   EE       CC
    DDDDDDDDD
''' 

# STFW: ANSI Escape Code
CLEAR = '\033[2J\033[1;1f'
BLOCK = {
    0: '\033[37m░\033[0m',
    1: '\033[31m█\033[0m',
}

for line in fileinput.input():
    # Load "A=0; B=1; ..." to current context
    exec(line)

    # Render the seven-segment display
    pic = DISPLAY
    for seg in set(DISPLAY):
        if seg.isalpha():
            val = globals()[seg]  # 0 or 1
            pic = pic.replace(seg, BLOCK[val])

    # Clear screen and display
    print(CLEAR + pic)

There’s a very interesting idea here that I hadn’t thought of. When I saw DISPLAY, I roughly knew that replacement was needed; my natural idea was to parse the string output from a.out to obtain the values of A - G.

But this code instead directly executes a.out’s output as Python code. It calls exec(line), and then obtains the values of A - G through the globals() dictionary.

demo2

Demo: Simulating RISC-V Instruction Execution

This Demo is even harder — it’s a program that simulates instruction execution to solve the classic “chickens and rabbits in the same cage” problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//@file_name: uncore.c
static inline bool inst_fetch(inst_t *in) {
  union {
    inst_t i;
    u32 u;
  } u;
  int r = scanf("%x", &u.u);
  *in = u.i;
  return r > 0;
}

static inline void ebreak(CPUState *cpu) {
  switch (cpu->x[10]) {
    case 1: { putchar(cpu->x[11]); break; }
    case 2: { printf("%d", cpu->x[11]); break; }
    case 3: { cpu->on = false; break; }
    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
45
46
47
48
49
50
//@file_name: rvemu.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef uint32_t u32;

typedef struct { u32 op:7, rd:5, f3:3, rs1:5, rs2:5, f7:7; } inst_t;
typedef struct {
  u32 on, x[32];
} CPUState;

// Uncore:
//   inst_fetch - read an instruction from stdin
//   ebreak - hyper call: putchar/putd/exit
#include "uncore.c"

static inline u32 sext(u32 val, u32 n) {
  // Sign extend n-bit integer val to 32-bit
  u32 mask = ~((1 << n) - 1);
  u32 set = (val >> (n - 1)) & 1;
  u32 ret = set ? (val | mask) : val;
  return ret;
}

int main(int argc, char *argv[]) {
  CPUState cpu = {.on = 1, .x = { 0 }}; // The RESET state
  for (int i = 0; argv[i + 1] && i < 8; i++) {
    cpu.x[10 + i] = atoi(argv[i + 1]); // Set a0-a7 to arguments
  }

  inst_t in;
  while (cpu.on && inst_fetch(&in)) {
    // For each fetched instruction, execute it following the RV32I spec
    u32 op = in.op, f3 = in.f3, f7 = in.f7;
    u32 imm = sext((f7 << 5) | in.rs2, 12), shamt = in.rs2;
    u32 rd = in.rd, rs1_u = cpu.x[in.rs1], rs2_u = cpu.x[in.rs2], res = 0;

    #define __ else if // Bad syntactic sugar!
    if (op == 0b0110011 && f3 == 0b000 && f7 == 0b0000000) res = rs1_u + rs2_u;
    __ (op == 0b0110011 && f3 == 0b000 && f7 == 0b0100000) res = rs1_u - rs2_u;
    __ (op == 0b0010011 && f3 == 0b000)                    res = rs1_u + imm;
    __ (op == 0b0010011 && f3 == 0b001 && f7 == 0b0000000) res = rs1_u << shamt;
    __ (op == 0b0010011 && f3 == 0b101 && f7 == 0b0000000) res = rs1_u >> shamt;
    __ (op == 0b1110011 && f3 == 0b000 && rd == 0 && imm == 1) ebreak(&cpu);
    else assert(0);
    if (rd) cpu.x[rd] = res;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@file_name: ji_tu.txt
00050713
00151793
40f587b3
0017d793
00200513
40f705b3
00100073
00100513
02000593
00100073
00200513
00078593
00100073
00100513
00a00593
00100073
00300513
00100073
0000006f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a.out: rvemu.c uncore.c
# RTFM: Automatic variables
	gcc -ggdb -Wall $<

run: a.out
	@echo 2 Head, 4 Feet:
	@cat ji-tu.txt | ./a.out 2 4
	@echo 2 Head, 6 Feet:
	@cat ji-tu.txt | ./a.out 2 6
	@echo 2 Head, 8 Feet:
	@cat ji-tu.txt | ./a.out 2 8
	@echo 35 Head, 94 Feet:
	@cat ji-tu.txt | ./a.out 35 94

clean:
	rm -f a.out

I really can’t understand this Demo, but I still gained something: this code also contains a C syntax I had forgotten — using : to specify the struct’s default values.

1
typedef struct { u32 op:7, rd:5, f3:3, rs1:5, rs2:5, f7:7; } inst_t;

It seems my C fundamentals are really weak.