通过链接编译复杂的软件(一)—— 主要步骤和要解决的问题

从汇编的角度理解程序中我们了解到,程序主要是执行汇编指令来操作数据。这些汇编指令和大部分数据,除了其自身的外,也都有固定的运行时内存位置。这些值和内存位置,由程序源码通过编译链接而确定下来,并全部被保存在磁盘上的可执行文件中。操作系统把文件中的指令和数据值加载到内存中对应的位置,再把 PC 寄存器设置到 main 函数指令的开始内存位置,从而开始执行程序。
在编译时,源代码(.c文件)首先通过预处理器来处理宏、注释等编程语言语法上的问题,形成 ASCII 中间件文件(.i文件)。之后,编译器把编程语言翻译成 ASCII 码的汇编语言文件(.s)。最后,汇编器把汇编语言文件翻译成二进制的可执行文件。
理论上来说,只需要编译这一个步骤就能确定汇编指令和变量的值和内存位置了,但是在实际工程中运行时内存位置却是在链接时最终确定的。更详细点说,就是每份源码单独编译成一个 ELF 文件(Executable and Linkable Format,意即可被执行又可被链接),其中只包含了该份源码本身的指令和变量的值,然后通过把所有的 ELF 文件链接在一起,为所有的指令和变量生成独特的运行时内存位置。
这样的好处是,当我们修改一个源代码文件后,只需要重新编译一个文件,再链接所有的文件。而且这种方式还附赠了一个便利:链接第三方库编译出来的 ELF 文件就能使用库提供的功能,免去了获取源码和编译源码的烦恼。
但是这些好处不是免费的,有两个明显的和内存位置相关的问题需要解决:

  • 对于在此处引用但是在其它源码中定义的变量和函数,怎么找到他们?
  • 怎么为每个 ELF 文件中的变量和函数生成独特且不彼此覆盖的内存位置?

解决方案分别可以用关键词概括:符号表重定位

Read More

从汇编的角度理解程序(四)—— 复杂数据结构

这篇文章是我《从汇编的角度理解程序》系列的第四篇。
在前面的三篇文章里,第一篇文章介绍了寄存器和按顺序执行的汇编指令,第二篇文章分析了按顺序执行的指令如何通过跳转实现分支和循环,第三篇文章分析了如何借助寄存器和栈内存实现有复杂状态的函数调用。
这一篇文章将会分析如何通过规范的内存布局和访问规则实现复杂的数据结构——数组(array)、结构体(struct)和联合(union)。

Read More

从汇编的角度理解程序(三)—— 函数调用

我们已经知道,程序是按顺序执行的指令流水线(PipeLine)。分支和循环逻辑,可以通过在流水线中往后跳或往前跳实现。
其实,函数调用也不过是在跳转。调用某个函数,就跳转到那个函数的指令流的开始位置,函数执行完成后,再跳转回来。
函数能获取外部写入的数据(输入),能持有自己独特的数据(本地状态),还能向外部写数据(输出)。而理论上程序所拥有的函数数量是无限的,但是寄存器的数量却很少,无限的函数怎么通过有限的寄存器数量来保存它们各自的数据呢?

Read More

从汇编的角度理解程序(二)—— 分支和循环控制

在上一节 从汇编的角度理解程序(一)—— 操作数据的指令流 中提到,程序其实就是按顺序执行的操作寄存器数据的指令流。
不过,按顺序执行的指令流是如何实现程序中常见的分支和循环功能的呢?
简单地说,就是有条件的跳转 —— 依据条件寄存器和跳转指令实现,非常类似 C 语言里面的 goto

Read More

从汇编的角度理解程序(一)—— 通过寄存器进行数据操作的指令流

我打算就汇编程序写一个系列博客。不过,其目的不是为了弄明白怎么写汇编语言,甚至不是为了弄明白如何读懂汇编程序。
它的目的只是为了揭秘黑魔法,披露计算机程序更深层本质:

  • 程序其实就是对数据进行操作的有序指令流
  • 有序的指令流能通过跳转实现程序分支和循环
  • 还能通过跳转和 stack 内存模式实现函数调用
  • 通过规范的内存布局和读写操作实现复杂的数据结构

Read More

对 ANS 算法的简单介绍

ANS 算法来自于 Jagiellonian University 的 Jarek Duda 在 2014 年发表的一篇论文:Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding。
从标题来看,ANS 算法是一个既有 AC 算法的压缩率又有 Huffman 算法的压缩速度的无损压缩算法。我最近一直在研究怎么优化用户在移动端加载 3D 模型的体验。如果 ANS 算法所言非虚,那么我就可以通过不多的 CPU 资源(解压时间)来换大量的流量资源(下载时间),从而降低用户在手机端加载模型的时间。
事实证明 ANS 算法确实很厉害,在权衡流量和 CPU 资源后,我们使用 ANS 把模型体积压缩到了上一代模型格式的 25%。20 万面的模型体积从 4 M(gzip后) 降低到了 1 M,在高通 610 CPU 的手机上,用微信浏览器解压大概需要 1.5~2 秒( 660 为 1秒)。也就是用 6 秒 的下载时间(根据我们的统计用户手机普遍下载速度为 500k/s) 换取了 2 秒的解压时间。而这只是非常低配的 610 处理器上面的表现。而且 CPU 性能的稳定性比网络性能的稳定性高得多。
在体验到 ANS 的巨大威力后,我实在按捺不住自己的好奇心,想去探究一下它的基本原理。

Read More

为什么要有那么多种 3D 格式?

STL、PLY、AMF、3MF、OBJ、FBX、DAE、VRML、X3D、IEGS、STEP、JT…… 目前已发布的 3D 格式文件数量,往少了说至少有二三十种。
通过对十多种最流行的 3D 格式做了一些调查,我发现大量规范和特性各异的 3D 格式共存的原因可以归纳于三点:

  1. 不同的应用领域孵化了少数简单但是理念各异的初始 3D 格式
  2. 不断产生的新需求导致了基于几种初始格式的衍变格式
  3. 组织之间的博弈造成解决同种需求的多种“竞争”格式共存

Read More

C 拓展 Python 实战(四)—— 类的高级属性

在之前的示例中我们使用了大量的 Py_INCREFPy_DECREF 来管理 Python Object 的引用计数。 Emptyvalue_setter 里也使用了一种非常啰嗦的语法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int record_object_set_value(record_object *self, PyObject *value, void *closure) {
PyObject *tmp;
if (value == NULL) {
PyErr_SetString(PyExc_TypeError, "Cannot delete value");
return -1;
}

// 使用了一个非常啰嗦的临时变量
tmp = self->value;
Py_INCREF(value);
self->value = value;
Py_DECREF(tmp);

return 0;
}

这一切都是为了内存管理。
本章我们将回顾 Python 的垃圾回收机制,包括引用计数、循环检测和弱引用这些概念;
在这个基础上,我们再来讨论在设计我们的类的时候要如何做才能避免内存泄漏;
接着,我们给类添加继承和被继承的功能,并展示如何复写特定的属性和函数;
最后,我们给类添加那些锦上添花的高级功能,比如静态属性、静态方法、类方法,以及一些 __magic_function__

Read More

C 拓展 Python 实战(三)—— 类的基本属性

我们将用两章探索如何实现内置的 Python 类,并尝试去了解一些 Python 编程语言的底层实现。
和之前一样,我们先从一个简单的例子开始,再逐步添加更多的特性。
我们要实现的第一个类为 Empty,就像它的名字一样,这个类没有任何 membermethod。在实现这个类的过程中我们将学习到创建一个类的基本流程。
我们要实现的第二个类为 Record, 它有两个成员属性 name(公开,string) 和 __value(私有,任意值), 以及 printset_value 两个成员方法,并且有一个 value property
由于 Recordvalue 可以设置为任意值(包括自己),我们就得再深入考虑一下引用计数、deallocweak refrence 这些涉及到内存管理的问题。
接着我们给 Record 添加类方法(class method) get_count、静态方法(static method) get_purpose 以及 __repr__, __str____eq__
最后,我们创建一个 StringRecord 类,它是 Record 的子类,但是它的 value 只能是 str 类型的数据。

本章我们先掌握类的基本属性。

Read More