The Design Philosophy of the DARPA Internet Protocols 论文阅读报告

本文介绍了Internet中最基本的协议——TCP/IP协议的设计思想。由David.D Clack所著，他作为整个TCP/IP协议设计的参与者，见证了协议从1973年最初的版本，逐渐被改进，到最终成型的一系列尝试。在文章中，作者总结了设计中的一系列目标，以及存在的问题。让我们得以窥见这一段艰辛的摸索之路。

各种协议的设计，其基本目标无非两个： 1) 能够尽可能的兼容协议发布之前已存在的硬件设施； 2)能够尽可能的有利于协议发布之后的因特网发展。这些基本目标不仅为我们理解TCP/IP的后续发展有帮助，也能够让我们知道，为什么在计算机科学领域，很多的实现都是建立在“协议”上的。

在基本目标之上，人们基于对于因特网的畅想，设计出了一系列有严格层次关系的次级目标，如稳定性，经济性，可解释性等。由于Internet协议的设计流程过于复杂，常常会遇到两种不同实现方式的权衡取舍，由于实现确立了稳定性、经济性这一类不同目标的重要性排序，故可以基于此进行取舍。这种目标导向的协议构建，一方面确实省去了非常多的试错的时间，另一方面，却会缺少一些长远的考虑（例如由于对性能的要求并没有卸载目标中，导致性能在早期完全没有被重视等等，又例如一对多的信息传递没有在早期协议中支持，导致在长时间无法实现）。

互联网协议的稳定性作为最重要的目标，毫无疑问来自于互联网历史上的军方背景。也在之后的普及中发现其局限性，报文协议(UDP)的诞生或多或少的解决了这个尴尬的境地。不过UDP能够成功诞生还是算非常幸运的了，通常来说协议的修改总是耗时耗力，有时还会和原来的协议冲突，诸如一对多的广播就一直没有能够成功的引入。总之，协议设计者的远见与用心真的是非常的重要。而TCP/IP协议的设计流程，从文中提到的寥寥几句可以推测出，确实不是设计者拍脑袋的结果，而是无数次试验，并用一篇篇论文推动而来的。反观现在良莠不齐的学术论文，我觉得在协议设计中的这种，基于某个具体目标驱动的研究，才是能让学术界向前推进的正确方法。

由于网络的协议的更改需要兼容之前的功能，而论文写作至今又过去了接近30年，TCP/IP协议在30年前存在的缺陷，随着互联网体量的增大，在现在解决更需要花费巨大的人力财力。IPV6协议的创立可能会解决少量表层问题，但是很多结构上的缺陷仍然无从修复。可能这是计算机网络领域的一大难题。期待在未来，能有技术上的爆炸性突破，其力量，能够足以颠覆计算机领域坚守了三十余年的TCP/IP协议。也许量子通信就是这样的潜力吧。

原创文章地址：【The Design Philosophy of the DARPA Internet Protocols 论文阅读报告】转载时请注明出处mhy12345.xyz！

Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍

摘要

这篇论文讲的是在高维空间的最近点搜索问题（ANN)的一个实现算法，该算法继承自 乘积量化（Product Quantization） 算法。在该算法中，提出了如下几点：

  • 将原来的乘积量化算法进行分层，使用树形结构减少向量的比较次数
  • 提出了一个重排序算法，该算法有更好的并行度

简介

最近点搜索问题(NN)就是在D维空间中，对于一个向量y，找寻样本集合\mathcal{X}中，最近点的问题，形式化表达——

(1)   \begin{equation*} N(y) =\mathop{\arg\min}_{x \in \mathcal{X}} d(y,x) \end{equation*}

在视觉识别的领域的很多课题中，该问题的维数D变得非常大，引入了一种称之为 “维数灾难” 的现象。形象的解释这个问题，对于一个体积a^128的128维高维立方体，一个体积0.1 \times a^128的立方体，边长也是0.1^{\frac{1}{128}} = 0.982\times a。从这个例子可以看到，由于高维立方体体积增长速度过于迅速，我们基本不可能通过遍历区域的方式进行搜索。例如，在128维空间中，即使我们只要访问10%的体积，这些体积分配到单维度上也超过了98%。

给予上述瓶颈，大多数应用中，我们都是用了临近点搜索的方式(ANN)，搜索一个相对较近的邻居。对于该问题，人们已经研究出了很多基于CPU的实现，从KD树(KD-tree)，到随机KD森林(Randomized KD forest)，和KD-mean Trees。这一系列算法都试图将搜索空间缩减到一个包含询问点的尽量小的邻域。

另一个截然不同的实现方式是局部敏感哈希算法(Local Sensitive Hashing)，这个方法将整个数据库的向量的一系列随机投影使用哈希表储存，在询问中，对于和询问向量落在了同一个哈希项中的样本向量进行额外的距离检查。

上述基于CPU的ANN算法在像GPU迁移的时候都会遇到或多或少的问题，而基于GPU的算法则很多都是纯粹暴力算法。而在这篇文章中提出的算法，不仅高效利用了GPU，甚至其CPU版本都和上述算法匹敌。

在效率评估上，由于在实际生产中，存在一个“离线预处理”阶段计算所有询问无关的数据，以及一个“在线计算”阶段，实时处理询问相关的计算。因此，最科学的方式应该是将两个阶段的用时分别测量。

向量量化(Vector Quantization)是一个简单的ANN算法，它将样本集\mathcal{X}中所有的向量进行聚类。对于某个询问向量，距离其最近的聚类中心所对应的样本集子集\mathcal{X}_k \subset \mathcal{X}是最有可能存在最近点的。然而倘若询问点恰好位于两个聚类的边界上，则算法就不那么容易找到最近点了。另一方面，一个聚类簇在V图上的相邻聚类簇的个数随着维数的增加指数级增长。

乘积量化(Product Quantization)算法是当下很多最前沿ANN算法的核心，一般来说，基于PQ的算法都有如下几步

  1. 通过一个高效但是低精度的算法，选出一系列候选点集。
  2. 在重排序过程(re-ranking step)中，使用近似距离将候选点集进一步排序。
  3. 排序后的前面K个候选点重新计算实际距离并取最近者。

在PQ类算法的基础上，我们平行提出了一个称之为Product Quantization Tree的算法(PQT)，这个算法的贡献点有

  1. 二级乘积和树形结构，减少计算量
  2. 引入Dijkstra算法的松弛操作
  3. 一个O(P)复杂度的近似排序算法，其中P为询问向量的分段数

背景

向量量化与乘积量化

由于我们的算法是基于PQ算法的，因此下面将介绍PQ算法。

首先，乘积算法(Product Quantization)的鼻祖是向量量化(Vector Quantization)算法。已知最初的样本集合\mathcal{X} = \{x_1,x_2,x_3,\dots,x_n\}，以及一个码表(codebook)\mathcal{C} = \{c_1,c_2,\dots,c_k\}，我们可以定义映射c(x) = \arg \min _{c \in \mathcal{C}} d(x,c)，将每个样本点映射到最近的码字。同时，对于每个码字也控制了一系列样本点，令这些点集为C_k，C_k =\ {x \in \mathbb{R}^D | c(x) = c_k\}，这个点集也成为簇(cluster)或盒子(bin)。直接使用码字代表样本点，虽然引入了一些距离上的不精确，但是在后续寻找相似向量中很有用。在上述算法中，关键点集合可以通过一个叫Lloyd Iteration的算法得到。

在PQ算法中，高维的向量空间可以等价于若干低维向量空间的乘积，假设D = P \cdot m，那么对于所有的样本向量都可以进行分解，x \in ([x]_1,[x]_2,\dots,[x]_p)^T, [x]_i \in \mathbb{R}^m. 对于x \in \mathbb{R}^D，我们可以将该高维空间中的码表定义为C = C_1 \times C_2 \times \dots \times C_P，这个集合里面实际上包含了k^P个D维码字，但是却只需要k \cdot P个m维码字。由于码字变得非常非常多，我们可以对于高维向量进行更加精细的匹配。最终，一个向量的编码(Canonical Projection)定义为其P个独立组成部分的码字组合而成——

    \[c_p : \mathcal{X} \rightarrow \mathcal{C}_p, x\mapsto c_p(x) := \mathop{\arg \min}_{c \in C_p} d([x]_p,c)\]

    \[c(x) = (c_1(x),c_2(x), c_3(x), \dots, c_p(x))^T\]

从上式可以发现，对于P个部分的量化操作使用了不同的码书，这些码书和VQ一样，都可以使用Lloyd Iteration生成。

诚然，查询任意一个向量处于哪一个簇是非常简单的。但是任意向量所归属的簇在大部分情况下都是空的，这是因为数据分布的稀疏性。不过，在实际使用中，查询向量通常和样本有相同分布，在这个条件下，我们确实可以成功的依照簇找到最近的向量。即使如此，我们还是需要考虑最坏的情况。

一些研究者为了实现更加精确的乘积量化方式，找到了一些解决方式，比如对于所有询问x，统一使用一个线性变换R修饰。及每次查询Rx。不过这个方法在GPU上并不怎么方便。

右图的四部分就分别介绍了“向量量化(Vector Quantization)”和“乘积量化(Product Quantization)”对应的中心点分布图。下层的两幅图则尝试按照不同的“粒度”实现树状查询，在之后会详细讨论。

 

倒排文件系统

对于一个询问y \in \mathbb{R}^D，有的文章使用了含“非对称距离计算”的倒排系统实现。在这个实现中，首先一次VQ，在规模k的码书中提取一系列候选码字（原文中是在8192个向量中，提取0.05%，即64个候选）。不过，即使是64个候选码字也廊括了524288个样本向量。

在这个实现中，选择一组合理的码字消耗了k个D维向量距离运算，在计算了k次距离之后，其中最近的w个码字对应的样本集合的并集\mathcal{L}_c \in \mathcal{X}就是“极有可能包含答案的向量集合”。这一系列向量进一步在基于PQ算法的重排序(re-ranking)。按照中心向量c_w与y的距离r_w = y-c_w，从小到大排序，在之前文章中，由于询问向量y事先知道，所以这个距离被放在了查找表(lookup-table)中。

询问向量y和其最近的候选向量可以在集合\mathcal{L}_c中使用相似的方式查找到。只不过这一次，候选集合\mathcal{L}_c小了很多，而码书包含了更多(k_2个词).通过新的码书对应的距离函数，重排序得到更加靠谱的候选集合\mathcal{L}_s，最终，在\mathcal{L}_s中，选择前几个进行最精确的距离计算。

上述步骤意味着共有k_1 + w \cdot k_2次距离计算，在论文默认的规模中，意味着24576次高维向量距离计算每询问。

一个层次化的实现会将总共的距离计算次数将至200，不过，在NVIDIA Titan X架构下，16k的向量距离计算比256次计算慢62倍，因此，在这个问题上，就近多少次距离计算是运行效率的瓶颈。

多索引倒排

相比于之前，在整个数据及上使用VQ，多层次倒排索算法使用了PQ算法，减少了询问向量与中心向量的距离计算次数，而增加了Cluster的总数。

对于y的每一部分，都给定了其到k个中心向量的距离。这些距离经过排序生成如下表格——

(2)   \begin{align*} [y]_1 \rightarrow \{i_{10}, i_{11}, i_{12}, \dots, i_{1k-1}\} \\ [y]_2 \rightarrow \{i_{20}, i_{21}, i_{22}, \dots, i_{2k-1}\} \\ \vdots \\ [y]_P \rightarrow \{i_{P0}, i_{P1}, i_{P}, \dots, i_{Pk-1}\} \\ \end{align*}

上面式子中i_{23}指的是询问向量第二部分的第三近的向量。在此基础上的NN搜索，使用启发式算法，从i=(i_{10},i_{20},\dots,i_{P0})开始。可以使用优先队列，一次访问最近的一个簇中的向量，直到足够多的向量被访问。

讨论

上述的基于VQ和基于PQ的查询算法都能达到很好的精准度。基于VQ的算法需要很大的内含D维向量的码书，即使基于PQ算法的码书会小一些，但是从总量上也非常大。另一方面，两个算法都需要与询问相关的离线初始化操作。这在实时的查询中是不可行的。

对于之前提到的诸多问题，在接下来一章中，我们将使用乘积量化树(Product Quantization Tree)来解决上述的问题，并提出不同的Cluster选择算法，和基于投影的重排序算法。最后，我们将讨论该算法如何在GPU上面运算。

参考文章

理解 product quantization 算法

K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

原创文章地址：【Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍】转载时请注明出处mhy12345.xyz！

Separating Style and Content for Generalized Style Transfer 阅读笔记

【由于笔者在尝试优化这个模型，因此在一些步骤中会加入自己的一些点评，以方括号指示，读者尽可无视他们】

在汉字风格迁移领域，有很多不同的尝试，学者在网络结构，损失计算等模块，都有不同的尝试。在之前的实现中，汉字的风格通常在训练过程中被记忆在了网络结构中，当需要生成一个新风格的字体时，网络需要在新的数据集下重新训练。而在本文中，汉字风格由给定的少数输入样本给定，由模型实时提取并输出。

文中的模型称之为EMD，在结构上包含风格编码器、内容编码器、混合器和解码器。训练数据集的每一项都是由R_S_i,R_C_j,I_{ij}组成，其中R_S_i和R_C_j分别是风格(Style)和内容(Content)的指示集合，而I_{ij}是目标图像。换句话来说，模型通过同一汉字不同风格的一组图像刻画了内容，又用同一风格不同汉字的一组图像刻画了风格，再将两个模块的特征向量组合，形成字体和内容的融合。

模型的详细结构如下图——

实际上，这张图片已经描述了几乎所有的细节。图中提及了down-sampling 和 up-sampling，这两个过程实际上就是图像的“压缩”和“放大”，在文中使用了经典的卷积层和反卷积层。

【反卷积层或许可以搞一些花样提高模型效果】

在Encoder模块，两个集合的所有输入数据，拼接在一起，每张图片作为一个Channel，传入后续的卷积层中。

【这里有一些小问题，不知道实现的时候有没有解决，由于输入的图片集合是无序的，而Channel本身是有序的，若将每一个图片都视为一个独特的Channel，则每一个不同位置的图片都会有不同的卷积层提取特征，这个情况本身就是不靠谱的。】

在Mixer模块，使用了BiLinear层。用数学语言来描述，设两个特征器提取出的向量分别是S_i和C_j，那么Mixer层的输出应该是S_i W C_j^T，其中W是一个形状(dim(S_i),dim(C_j))的向量。

Decoder模块使用了若干反卷积层。具体细节图片已经说得很明白了。上述的多层卷积和反卷积层中间都间隔了BatchNorm和LeakyReLU。

还有一些实现上的细节，诸如从Content Encoder的第一层连了一条通路到Decoder的最后一层。及Content Encoder进过粗特征可直接被答案的生成所运用。

【这一步骤会让人比较怀疑这条通路中间的东西是不是真的学到了东西，模型本身很容易直接学到“和输入一模一样”的输出（因为这样的输出只经过两层），而不容易学到风格信息（风格信息的传输至少会经过十多层）。】

 

原创文章地址：【Separating Style and Content for Generalized Style Transfer 阅读笔记】转载时请注明出处mhy12345.xyz！

Codewars C++练习：Insane Coloured Triangles

题目

题目链接：

This Kata is an insane step-up from Avanta’s Kata, so I recommend to solve it first before trying this one.

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

For example, different possibilities are:

1
2
Colour here:            G G        B G        R G        B R
Becomes colour here:     G          R          B          G

With a bigger example:

1
2
3
4
5
6
7
8
R R G B R G B B
R B R G B R B
  G G B R G G
   G R G B G
    B B R R
     B G R
      R B
       G

You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given ‘RRGBRGBB’, and you should return ‘G’.

1 <= length(row) <= 10 ** 5

题解

核心规律

找到所有递推方程的共性：“所有递推小三角形，都满足RGB的个数在模3意义下相同”。

1
2
Colour here:            G G        B G        R G        B R
Becomes colour here:     G          R          B          G

单独考虑任意一个大三角形的第一行和第二行，倘若我们知道了第一行RGB分别有多少个，我们也可以通过“RGB的个数在模3意义下相同”这个性质，计算出第二行分别有多少个RGB。这个是一个很有启发作用的思路，虽然这个思路无法解决更多的行，但是从该思路出发，我们可以得到如下的算法——

用三元组S_{x,y}=(r,g,b)表示一个位置的颜色。一方面，我们定义映射f来求任意三元组对应的颜色.

f = \{(r,g,b) r,g,b \in \mathbb{Z}\} \rightarrow \{\boldsymbol{R},\boldsymbol{G},\boldsymbol{B}\}

另一方面，不同的三元组有很多，但是颜色的种类总共就3种，所以我们需要对于该三元组建立若干“等价类”，规则如下:

  1. (1,0,0)\rightarrow \boldsymbol{R}，(0,1,0) \rightarrow \boldsymbol{G}，(0,0,1)\rightarrow \boldsymbol{B}
  2. f((r,g,b)) = f((r \bmod 3, g \bmod 3, b \bmod 3))
  3. f((r,g,b)) = f((r-v,g-v,b-v))

规则1定义了三元组到颜色的映射，而规则2和规则3将所有三元组分为了3类。

仔细理解一下这三条规则，我们很容易求出一个三元组对应的颜色，例如f((123,123,400)) = f((0,0,277))=f((0,0,1)) \rightarrow \boldsymbol{B}。当然，并不是所有三元组都可以通过这种方法计算出值，倘若一个三元组无法求出值，如(0,0,0)，那么在本题中，它就是不合法的。

但看三元组的定义或许会莫名其妙，但是我们可以将本题的规则引入，得到一个暴力的迭代方式——

对于整个三角形的第一行，可以直接按照定义式生成：

S_{0,y} = ([row[0]==\boldsymbol{R}],[row[0]==\boldsymbol{G}],[row[0]==\boldsymbol{B}])

例如，一个\boldsymbol{G}颜色可以用三元组(0,1,0)表示。

对于后续的行，我们可以按照递推式生成——

S_{x,y} = -S_{x-1,y} - S_{x-1,y+1}

例如，倘若S_{x-1,y} = (1,0,0) \rightarrow \boldsymbol{R}，S_{x-1,y+1} = (0,1,0) \rightarrow \boldsymbol{G}，那么S_{x,y} = (-1,-1,0) \equiv (0,0,1) \rightarrow \boldsymbol{B}

读者到这里应该就可以发现，实际上我们的三元组完全是为了反映递推方程中的等价信息而设计的。这里，我们已经可以设计出时间复杂度O(N^2)的算法了。

force.cpp
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
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
#include<iostream>
using namespace std;
#define MAXN 1010
 
char buf[MAXN];
 
class status {
private:
int v[3];
public:
status() {
v[0] = v[1] = v[2] = 0;
}
status(int x,int y,int z) {
v[0] = x%3;
v[1] = y%3;
v[2] = z%3;
}
static status createFromChar(char c) {
status num;
switch (c) {
case 'R':num.v[0] = 1;break;
case 'G':num.v[1] = 1;break;
case 'B':num.v[2] = 1;break;
}
return num;
}
char getChar() {
v[1] -= v[0];
v[2] -= v[0];
v[0] = 0;
v[1] = (v[1]%3+3)%3;
v[2] = (v[2]%3+3)%3;
if (v[1] == 2 && v[2] == 2)
return 'R';
if (v[1] == 1 && v[2] == 0)
return 'G';
if (v[1] == 0 && v[2] == 1)
return 'B';
return '?';
}
void show() {
printf("[% 3d % 3d % 3d]\t",v[0],v[1],v[2]);
}
friend status operator + (const status& a,const status& b);
friend status operator - (const status& a);
};
status operator + (const status& a,const status& b) {
return status(a.v[0]+b.v[0],a.v[1]+b.v[1],a.v[2]+b.v[2]);
}
status operator - (const status& a) {
return status(-a.v[0],-a.v[1],-a.v[2]);
}
 
status mat[MAXN][MAXN];
 
 
int main() {
freopen("input.txt","r",stdin);
scanf("%s\n",buf);
int n = (int)strlen(buf);
for (int i=0;i<n;i++) {
mat[0][i] = status::createFromChar(buf[i]);
}
for (int i=1;i<n;i++) {
for (int j=0;j<n-i;j++) {
mat[i][j] = -(mat[i-1][j]+mat[i-1][j+1]);
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n-i;j++) {
mat[i][j].show();
}
printf("\n");
}
printf("%c\n",mat[n-1][0].getChar());
}

既然我们已经借助三元组的加减运算，定义出了一个新的数域来解决这个问题，并且该数域很容易证明满足封闭性。反映到代码上，就是我们成功定义出了一个支持加操作和相反数操作的“数”status，那么我们完全可以不再考虑status类的实现细节。

所有细节略去之后，我们的代码实际上就是上面的65-69这5行。有一些编程基础的读者已经发现这里非常像一个组合数的递推方程（或者说是杨辉三角形的生成代码）。

对于一个稍微简单一些的例子，我们对于第一行的所有值赋予一个标号，看看最终结果长什么样的：

1
2
3
4
5
a          b          c          d          e
-a-b       -b-c       -c-d       -d-e
a+2b+c     b+2c+d     c+2d+e
-a-3b-3c-d -b-3c-3d-e
a+4b+6c+4d+e

上表中，a,b,c,d,e分别是我们读入的第一行的三元组表示，而最后一行就是答案！因此，假设读入三元组列表为s_i那么答案就是

ans =(-1)^{n-1}\sum_{i=0}^{n-1} C(n-1,i) \cdot S_i

最后一步比较tricky，需要一些较深的数论知识，最后一步我们需要求出C(n-1,i)在模3意义下的值。这一步有两个做法——

  • 有现成的Lucas定理专门用来计算这个问题。
  • 可以手工迭代求出C(n-1,0),\dots,C(n-1,n-1)的值，可以用递推式C(n-1,i+1) = C(n-1,i) \cdot (i+1) / (n-1-i)求，这其中又有两个要点
    • 在迭代的乘法需要将所有的因子3提出来
    • 在迭代的除法中需要计算除数在模3同余系下的逆元

在标程中使用了第二种做法。

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
#include<iostream>
using namespace std;
#define MAXN 101000
 
char buf[MAXN];
 
class status {
private:
int v[3];
public:
status() {
v[0] = v[1] = v[2] = 0;
}
status(int x,int y,int z) {
v[0] = x%3;
v[1] = y%3;
v[2] = z%3;
}
static status createFromChar(char c) {
status num;
switch (c) {
case 'R':num.v[0] = 1;break;
case 'G':num.v[1] = 1;break;
case 'B':num.v[2] = 1;break;
}
return num;
}
char getChar() {
v[1] -= v[0];
v[2] -= v[0];
v[0] = 0;
v[1] = (v[1]%3+3)%3;
v[2] = (v[2]%3+3)%3;
if (v[1] == 2 && v[2] == 2)
return 'R';
if (v[1] == 1 && v[2] == 0)
return 'G';
if (v[1] == 0 && v[2] == 1)
return 'B';
return '?';
}
void show() {
printf("[% 3d % 3d % 3d]\t",v[0],v[1],v[2]);
}
friend status operator + (const status& a,const status& b);
friend status operator - (const status& a);
friend status operator * (const status& a,int k);
};
status operator + (const status& a,const status& b) {
return status(a.v[0]+b.v[0],a.v[1]+b.v[1],a.v[2]+b.v[2]);
}
status operator - (const status& a) {
return status(-a.v[0],-a.v[1],-a.v[2]);
}
status operator * (const status& a,int k) {
return status(a.v[0]*k,a.v[1]*k,a.v[2]*k);
}
 
/*
int pow_mod(int x,int y,int mod) {
int ret = x%mod;
while (y) {
if (y&1)
ret = ret*x%mod;
x = x*x%mod;
y>>=1;
}
return ret;
}*/
 
char triangle(const string &buf)
{
int n = buf.length();
status res;
int k=1,b=0;//k*3^b
for (int i=0;i<n;i++) {
status s = status::createFromChar(buf[i]);
res = res + s * (b?0:k);
if (i == n-1)
break;
int x = i+1;
while (x%3 == 0)
x /= 3,b--;
k = k*x%3;
//k = k*pow_mod(x,1);
x = (n-1)-i;
while (x%3 == 0)
x /= 3,b++;
k = k*x%3;
}
if (n%2 == 0)
res = -res;
return res.getChar();
}

 

原创文章地址：【Codewars C++练习：Insane Coloured Triangles】转载时请注明出处mhy12345.xyz！

汇编解析C语言函数结构体struct参数的方式

本文介绍在x86汇编中没有加优化选项时的函数体struct传参和返回的方法。

结构体返回值

测试代码

我们先讲讲较为简单的函数返回结构体的方法——

ret_struct/cat main.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Type return_struct(int n) {
Type local_struct;
local_struct.aaa = 1*n;
local_struct.bbb = 2*n;
local_struct.ccc = 3*n;
local_struct.ddd = 4*n;
local_struct.eee = 5*n;
i = local_struct.eee + local_struct.aaa*2;
return local_struct;
}
int function1()
{
Type main_struct = return_struct(i);
i = main_struct.ddd;
return 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
51
52
53
00000000004004e0 <return_struct>:
  4004e0: 55                   push   %rbp
  4004e1: 48 89 e5             mov    %rsp,%rbp
  4004e4: 48 89 7d d8           mov    %rdi,-0x28(%rbp)
  4004e8: 89 75 d4             mov    %esi,-0x2c(%rbp)
  4004eb: 8b 45 d4             mov    -0x2c(%rbp),%eax
  4004ee: 89 45 e0             mov    %eax,-0x20(%rbp)
  4004f1: 8b 45 d4             mov    -0x2c(%rbp),%eax
  4004f4: 01 c0                 add    %eax,%eax
  4004f6: 89 45 e4             mov    %eax,-0x1c(%rbp)
  4004f9: 8b 55 d4             mov    -0x2c(%rbp),%edx
  4004fc: 89 d0                 mov    %edx,%eax
  4004fe: 01 c0                 add    %eax,%eax
  400500: 01 d0                 add    %edx,%eax
  400502: 89 45 e8             mov    %eax,-0x18(%rbp)
  400505: 8b 45 d4             mov    -0x2c(%rbp),%eax
  400508: c1 e0 02             shl    $0x2,%eax
  40050b: 89 45 ec             mov    %eax,-0x14(%rbp)
  40050e: 8b 55 d4             mov    -0x2c(%rbp),%edx
  400511: 89 d0                 mov    %edx,%eax
  400513: c1 e0 02             shl    $0x2,%eax
  400516: 01 d0                 add    %edx,%eax
  400518: 89 45 f0             mov    %eax,-0x10(%rbp)
  40051b: 8b 45 f0             mov    -0x10(%rbp),%eax
  40051e: 8b 55 e0             mov    -0x20(%rbp),%edx
  400521: 01 d2                 add    %edx,%edx
  400523: 01 d0                 add    %edx,%eax
  400525: 89 05 05 0b 20 00     mov    %eax,0x200b05(%rip)        # 601030 <i>
  40052b: 48 8b 45 d8           mov    -0x28(%rbp),%rax
  40052f: 48 8b 55 e0           mov    -0x20(%rbp),%rdx
  400533: 48 89 10             mov    %rdx,(%rax)
  400536: 48 8b 55 e8           mov    -0x18(%rbp),%rdx
  40053a: 48 89 50 08           mov    %rdx,0x8(%rax)
  40053e: 8b 55 f0             mov    -0x10(%rbp),%edx
  400541: 89 50 10             mov    %edx,0x10(%rax)
  400544: 48 8b 45 d8           mov    -0x28(%rbp),%rax
  400548: 5d                   pop    %rbp
  400549: c3                   retq
 
000000000040054a <function1>:
  40054a: 55                   push   %rbp
  40054b: 48 89 e5             mov    %rsp,%rbp
  40054e: 48 83 ec 20           sub    $0x20,%rsp
  400552: 8b 15 d8 0a 20 00     mov    0x200ad8(%rip),%edx        # 601030 <i>
  400558: 48 8d 45 e0           lea    -0x20(%rbp),%rax
  40055c: 89 d6                 mov    %edx,%esi
  40055e: 48 89 c7             mov    %rax,%rdi
  400561: e8 7a ff ff ff       callq  4004e0 <return_struct>
  400566: 8b 45 ec             mov    -0x14(%rbp),%eax
  400569: 89 05 c1 0a 20 00     mov    %eax,0x200ac1(%rip)        # 601030 <i>
  40056f: b8 00 00 00 00       mov    $0x0,%eax
  400574: c9                   leaveq
  400575: c3                   retq

分析

在上面的程序中，内层  return_struct 函数在被调用时，有两个有意义的寄存器，分别是 %rdi 记录了在function1中定义的那个结构体的位置， %rsi 记录传入的n。

在函数进入时，两个寄存器都被保存到了内存里面，接下来按部就班实现C++中的逻辑。重点部分在第30-35行，使用了三个位移操作赋值了五个值。最初理解代码，尝试寻找拷贝内存的语句时，将这三句话直接排除在外，实际上，由于结构体里面是5个整形，而使用64位寄存器，一次可以拷贝两个整数，因此三次拷贝恰好可以用最快的时间完成拷贝。

结论

因此，结构体返回的方式是将返回的结构体的起始位置指针放入 %rdi 寄存器，并在子程序中通过该寄存器定位修改结构体的内容。

结构体传参

测试代码

首先设计样例代码如下——

call_struct/main.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct{
int aaa; int bbb; int ccc; int ddd; int eee;
}Type;
int i= 2;
int input_struct(Type in_struct)
{
int ret = in_struct.eee + in_struct.aaa*2;
return ret;
}
 
int function2()
{
Type main_struct;
main_struct.aaa = i;
main_struct.bbb = 2*i;
main_struct.ccc = i;
main_struct.ddd = i;
main_struct.eee = i;
return input_struct(main_struct);
}

反汇编出的信息如下——

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
00000000004004d6 <input_struct>:
  4004d6: 55                   push   %rbp
  4004d7: 48 89 e5             mov    %rsp,%rbp
  4004da: 8b 45 20             mov    0x20(%rbp),%eax
  4004dd: 8b 55 10             mov    0x10(%rbp),%edx
  4004e0: 01 d2                 add    %edx,%edx
  4004e2: 01 d0                 add    %edx,%eax
  4004e4: 89 45 fc             mov    %eax,-0x4(%rbp)
  4004e7: 8b 45 fc             mov    -0x4(%rbp),%eax
  4004ea: 5d                   pop    %rbp
  4004eb: c3                   retq
 
00000000004004ec <function2>:
  4004ec: 55                   push   %rbp
  4004ed: 48 89 e5             mov    %rsp,%rbp
  4004f0: 48 83 ec 20           sub    $0x20,%rsp
  4004f4: 8b 05 36 0b 20 00     mov    0x200b36(%rip),%eax        # 601030 <i>
  4004fa: 89 45 e0             mov    %eax,-0x20(%rbp)
  4004fd: 8b 05 2d 0b 20 00     mov    0x200b2d(%rip),%eax        # 601030 <i>
  400503: 01 c0                 add    %eax,%eax
  400505: 89 45 e4             mov    %eax,-0x1c(%rbp)
  400508: 8b 05 22 0b 20 00     mov    0x200b22(%rip),%eax        # 601030 <i>
  40050e: 89 45 e8             mov    %eax,-0x18(%rbp)
  400511: 8b 05 19 0b 20 00     mov    0x200b19(%rip),%eax        # 601030 <i>
  400517: 89 45 ec             mov    %eax,-0x14(%rbp)
  40051a: 8b 05 10 0b 20 00     mov    0x200b10(%rip),%eax        # 601030 <i>
  400520: 89 45 f0             mov    %eax,-0x10(%rbp)
  400523: 48 83 ec 18           sub    $0x18,%rsp
  400527: 48 89 e0             mov    %rsp,%rax
  40052a: 48 8b 55 e0           mov    -0x20(%rbp),%rdx
  40052e: 48 89 10             mov    %rdx,(%rax)
  400531: 48 8b 55 e8           mov    -0x18(%rbp),%rdx
  400535: 48 89 50 08           mov    %rdx,0x8(%rax)
  400539: 8b 55 f0             mov    -0x10(%rbp),%edx
  40053c: 89 50 10             mov    %edx,0x10(%rax)
  40053f: e8 92 ff ff ff       callq  4004d6 <input_struct>
  400544: 48 83 c4 18           add    $0x18,%rsp
  400548: c9                   leaveq
  400549: c3                   retq

分析

有了上面的铺垫，我们可以迅速找到在30-35行有一段结构体的拷贝——将位于局部变量中的结构体拷贝到了在28行分配的一段连续空间中，而拷贝操作都是由 %rax 定位的。有意思的是，当我们认为 %rax 正是一个向子程序定位结构体的指针是，发现在子程序中 %rax 的寄存器中的值并没有被使用，反而是使用了 %rsp 进行定位。从另一个方面思考其实也并不奇怪，结构体参数本身是不能通过寄存器传参的，实际上，传参使用了最简单的方式——“通过压栈方式传参”，参数按照“从右到左”的顺序压栈，倘若遇到结构体，则压栈的内容变得多一些而已。

结论

结构体作为参数传入使用压栈方式传参，参数按照“从右到左”的顺序压栈，特别的，当参数为结构体，将结构体整体压栈。

原创文章地址：【汇编解析C语言函数结构体struct参数的方式】转载时请注明出处mhy12345.xyz！