第五章 优化程序性能(摘要与注解)

我错了,我明天一定把这一篇补完

我对了,我今天把这一篇补完了

感觉是本书最难理解和应用的一章, 所以得多花点功夫尽可能深入理解了然后写的好一点

第六章 存储器层次结构(摘要与注解)

这一章也很好理解, 重点解释一些不太好理解或者书上介绍不是很清楚的地方, 然后列大纲用于以后复习看。

(UPD 做完 cache lab 后: 还是不太好理解的, cache lab 难度不小)

链接(第七章 ALL)

这章内容很短, 就是书中和 15213 都有意隐去了很多细节, 自己去理解思考这些细节会很麻烦

另外 section 的翻译易引起歧义, 这里不作翻译

静态链接:

静态链接包括两个阶段, 符号解析和重定位:

符号解析

符号解析是要把每一个符号引用与符号定义联系起来

首先要理解可重定向文件的各个 section

在做 Codeforces Educational Round 169 D Colored Portals 时，需要找到 i 前面距离 i 最近的颜色不完全相同但也不完全不同的 j，我随手写了个

1
2
3
4
5
6
7
8
9
10
11
12
13

const vector<string> type = {"BG", "BR", "BY", "GR", "GY", "RY"};
map<string, int> m;
vector<int> lc(n, -1), rc(n, -1);

for (int i = 0; i < n; i++) {
    auto condi = m | filter([&](const auto &p) { return p.first != in[i] && has_same(p.first, in[i]); });
    if (auto lci = ranges::max_element(
                condi, [](const auto &a, const auto &b) { return a.second < b.second; });
            lci != ranges::end(condi)) {
            lc[i] = lci->second;
    }
    m[in[i]] = i;
}

整数的运算(第二章 Part2)

无符号数加法溢出

无符号的数的加法溢出规则很简单, 单纯截取后 \(w\) 位, 或称对 \(2^w\) 取模。因此:

\[ x\ +_w^u\ y = \begin{cases} x + y, & x + y < 2^w, \\ x + y - 2^w, & 2^w \leq x + y < 2^{w+1}. \end{cases} \]

(\(+_w^u\) 表示最多 \(w\) 位下的二进制无符号数加法。下文\(+_w^t\) 即 \(w\) 位补码加法)

检验无符号数加法溢出

若 \(s = x +_w^u y\), 当且仅当 \(s < x\) （或等价地 \(s < y\)） 时发生溢出。

(当然, 默认 \(x\) 和 \(y\) 本身不会溢出, 即在 \([0, UMax_w]\) 的范围内)

原理易证, 分别证明充分性必要性即可, 注意利用以上公式

整数的表示(第二章 Part1)

博客还没装 Mathjax 插件，所以下面的 \(\LaTeX\) 应该都是乱的 已修

整数表示

这一段如果没有目的和顺序地硬看会觉得关系很多很复杂，但其实只要按照一定的目的和顺序结构就会很清晰。

以设计者的视角思考如何设计

如果我们是设计用二进制表示整数的人，我们需要如何表示二进制？

利用 \(w\) 位二进制的最高位 $ x_{w-1} $ 为 \(1\) 代表这个数是负数，剩下的部分正常用二进制表示即 \(\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i\)

但显然光表示是完全不够的，我们还需要运算，而符号位由于不对具体数值做贡献，会导致运算错误。 因此我们需要让符号位也代表数值，用另一种映射方式计算，于是我们令最高位的符号位具有负的权重 \(-x_{w-1} \cdot 2^{w-1}\)，这样符号位也参与了计算。但是这样数值又对不上了，因此我们需要把后面的位也变一下。由于我们不是真的设计师，所以我们直接看答案：取反后面的每一位后再 +1。例如10010除符号位取反后变为11101， +1后是11110。这样的表示方法计算出的数值是 \(-x_{w-1}\cdot2^{w-1}+\displaystyle\sum_{i=0}^{w-2}x_i\cdot2^i\) 如何论证这样的数值是”对”的呢？

Phase 0x1

一个练手的，要求通过缓冲区栈溢出攻击来调用 touch1

gdb ctarget 然后 set args -q 防止与不存在的服务器通信（run -q 也可以) b Gets run -q

看一下栈信息:

1
2
3
4
5
6
7

────────────────────────[ STACK ]────────────────────────
00:0000│ rsp 0x5561dc70 —▸ 0x4017b4 (getbuf+12) ◂— movl $1, %eax
01:0008│ rdi 0x5561dc78 ◂— 0
... ↓        3 skipped
05:0028│     0x5561dc98 —▸ 0x55586000 ◂— 0
06:0030│     0x5561dca0 —▸ 0x401976 (test+14) ◂— movl %eax, %edx
07:0038│     0x5561dca8 —▸ 0x55685fe8 —▸ 0x402fa5 ◂— pushq $0x3a6971 /* 'hqi:' */