【转】Fabrice Bellard其人

pqiankui

有些计算机科学家的名字耳熟能详：阿兰·图灵(Alan Turing)、高纳德(Donald Knuth)、艾兹赫尔·戴克斯特拉(Edsger Dijkstra)，这些人的名气甚至大于他们突破性的成就。阿兰图灵的影响力是如此之大，以至于他的名字永久和计算机协会(ACM)最著名的奖项(也可 以说是计算机科学中最著名的奖项)绑定在一起。在奖项的另一边，Kunth 和 Dijkstra 在算法和数据结构方面的革命也是众所周知的。这些计算机科学家变的如此有名，赢得了全球的尊重，有时甚至是盲目的崇拜。另外一些人也在进行类似令人印象深 刻和有影响的工作，却没有收获如此大的名气，Fabrice Bellard 走的是不同的路：他是过去20年中最闪亮和最有影响力的程序员之一，但他的名声远远却低于他的贡献。

Fabrice 1972年在法国格勒诺布尔出生，却在法国南部的蒙彼利埃成长，许多计算机科学家在年轻时就在相关领域显现超凡的智力或兴趣，比如数学或技术。例如 Edsger Dijkstra 是一个化学家和一个数学家的孩子，这些背景对他有非常大的影响。从早期对数学和物理的兴趣，到后来在这个领域的职业生涯。在这方面，Fabrice Bellard 没有什么不同。但 Dijkstra 偏爱数学和物理，而 Bellard 却钟情于电子设备，他的第一个词语是“magn ́etophone” (录音机)。也是对电子设备的兴趣引导他献身计算机科学。

作为年轻的孩子，Fabrice Bellard 可以通过从中上层家族获得的知识和技术来表达他对电子系统的激情。在 9 岁时，他通过为他的 TI－59 科学计算器编程开始了程序设计的体验，TI－59 是第一个可编程计算器，由德州仪器2年前建造。TI－59 有一个图灵完备的语言，但是由于它的10个数字的显示设备和只有字母数字的字符集，这个语言有某些限制。例如，因为没有缩进符号，直接在计算器上编写 C 风格的程序非常的困难－－必须在输入TI－59之前在纸上(“代码本”)上规划出他们的程序。尽管如此，这个语言还是比汇编要简单很多，有更直观的概念， 例如循环。无疑这个语言的困难和现代的语言比较促进了在底层代码的早期杰出工作。这也是他后来工作的一个课题。

后来，在他11岁时，他的家庭给他买了一台家用电脑，TI-49/4A，也是德州仪器生产的。TI-49/4A 是第一个 16 位私人电脑，虽然德州仪器的一些限制导致很多处理都要进行 16位到8 位的复用，丢失了附加位的功能。这个计算机包含一个 TI BASIC 解释器，一个只可以在 TI-49/4A 上使用的语言，虽然这个语言和当时流行的 Microsoft BASIC 不兼容，但有助于德州仪器保留家用电脑市场，TI BASIC 很容易学，它让用户很容易的访问常用的功能，让基本的程序很容易编写，每行只包含一条命令，类似于 Bellard 先前在 TI－59 上编写的程序，这让从计算器上获得的程序设计经验可以轻易的转移到更全面的电脑上。

在编写 TI BASIC 的过程中，Bellard 学习了程序设计技能，但实际上只看到特定机器的实现最终将限制他的发展。在 15 岁时，Bellard 收到了他自己的私人电脑：Amstrad PC1512，更强大的规格，全 qwerty 键盘，这台电脑更加刺激了他的激情。

为 PC1512 编程意外的变成了他的第一个主要成就。由于在当时给他只有很有限的磁盘空间，Bellard 看到需要一个有效的压缩方法，这个结果就是 LZEXE，针对私人电脑的第一个可执行文件压缩方法，它允许被压缩的可执行文件在后续的启动时不需要明确的解压缩。

他从 LZSS 得到压缩方法的灵感，LZSS 是一个无丢失的数据压缩算法，那时在 Okumura 发布的各种自由和开源软件中实现。利用他先前编写低级语言的经验，他用 8086 汇编语言(PC1512的机器语言)重写了LZSS，改善了程序的结构，允许非常快速的解压缩。用机器语言编写是本质上的解决方案，它允许 Bellard 保持解压缩器令人难以置信的小，确保它占用少于从压缩可执行文件第一个位置得到的空间。通过发布 LZEXE 给几个朋友和投递到各种 BBS (进化为现代的WEB论坛)，LZEXE 立即获得成功。在展示了他的创造力和编程能力之后，Bellard 为到世界著名的法兰西学院，高等理工学院学习而继续发展他的技能。

对于那些只熟悉美国式教育的人将发现法国高等教育明显的和通常规则不同。法国学生在中学呆四年而不是三年，然后在法国国立高校呆三年，从高校毕业需 要通过学士学位，类似于 SATs 和 ACTs 的测试。从国立高校毕业后，学生参加两个高等教育学校中的一个：大学或者巴黎高等学校。不象美国大学有 1,000 到 50,000 本科生的任何规模，法国大学很小，连中等规模的城市也有多个不同领域的大学。在法国文科学校是罕见的，大学通常只学习单个领域的知识。和大多数美国学生一 样，中等教育毕业后直接进入大学。

可是，如果学生的成绩在班里总是排在前面，那么他可以尝试进入巴黎高等学校，一个负盛名的大学，在法国排名最高，并跻身于世界一流大学。 ［Ecole des Mines de Paris］在入学前，学生必须花两到三年时间准备课程，以通过严格的入学考试，也就是 Classe Preparatories aux Grandes Ecoles (CPGE).

巴黎高等学校传统上是难以置信的选择，每个班级有 300 到 500 名学生，其中，高等理工学院被认为是最负盛名的，当进入 X 后，X 是高等理工学院的别名，一个学生需要花 5 年时间来获得一个工程师学位，这相当于一个美国大学的科学硕士学位。X 和美国大学的进一步区别是它是一所工程专业的军校，所有学生在他的求学生涯中必须完成最少一年的军事服务，不同于美国大学的学生传统上可以在第二年改变专 业，X 讲究的是广度而非深度。虽然大学是工程专业，但学生必须学习体育和人文。学生在军事服务前必须花费 4 年学习本科课程，然后剩下的时间专门学习他们的专业知识。因为学校在技术领域非常突出，大量的学习资源，并且为学生提供了慷慨的津贴，Bellard 找到了程序的自由。他也注意到军事服务是不重要的，因为当时军事服务对所有法国人都是必须的。

X 课程的目标是培养学生的批判性的思维能力，而不是为工程职业做准备。结果是，从 Fabrice Bellard 身上可以看到，一个擅长各个领域的人。Bellard 在计算机科学上的贡献跨越了广阔的不相关的领域：从数字信号处理到处理器仿真到数学创新，以及之间的一切。

他在程序设计方面的早期教育以及他在理工学院受到的教育对他认识计算机科学的整体面貌有很大的影响。他觉得计算机科学最重要的两个方面是学习计算机 如何工作，以及通过学习计算本身，开发语言，用各种不同的方法让计算机有效的工作[Gocke and Pizzolato]。首先，他基于原始程序设计经验进行开发，从一个非常靠近机器的语言开始，慢慢发展为高级的语言。他对计算原理的细心源于他受到的良 好教育。他觉得有抱负的计算机科学家通过汇编语言和计算机硬件来深度理解计算机是如何工作是必不可少的。

Bellard 的工作中有一项非常突出的方面是数学，尤其是数字信号处理。在 1995 年，他建立了他的第一个进军世界的数值算法–用 C 语言编写了 Pollard 的 FFT 快速乘法。

FFT 是快速傅立叶变换的缩写，这是一个在数字信号处理中非常常用和有效的算法，也是 Bellard 工作中反复出现的主题。FFT最初是用来计算离散傅立叶变换的极其快速的方式。离散傅立叶变换是转换采样复杂函数到频率域表现的 方法。这种表现在离散傅立叶转换在离散(有限的)点操作的前提下，描述在原始函数中出现的频率[Weinsstein] 。你马上就可以看到，这个数学理 论有巨大的影响 — 计算机不能在连续的函数上操作，所以有些函数，例如视频和音频，离散为称为‘采样’的过程。奈奎斯特-香农采样定理指出，输入函数的两倍频率的采样率可以 得到完美的信息转换[Nyquist 1928; Shannon 1949]。这意味着尽管存在有限数据点的限制，计算机还是可以准确的表示连续的函数(例如声音)。因此，离散傅立叶转换可以用这个离散点来收集关于原始 函数的信息，例如分解波为复合频率–这是数字信号处理的宝贵信息。

可是研究人员很快明白 FFT 可以应用到除离散傅立叶转换之外的事情。John Pollard，一位欧洲数学家，发现用在 FFT 中的一个类似的过程可以用做有效的乘法，他的工作成果是有效的乘大数序列以及分解大合数。可是它的数学原理是声音，Pollard 的工作很少有任何实际完整的代码实现，这就是 Bellard 出现的原因–在1995年，他用 C 语言实现 Pollard 的工作。他用 Salamin的二次方程计算了 Pi 的几百万位数字证明了他的成功，进一步巩固了作为一个有敏捷和娴熟的数学头脑的主力程序员的地位[Salamin 1976]。

这个主题在他的工作中一而再，再而三的发生，但也许最显著的是他的第一个突破性成就。在 1997 年 1 月 20 日，Fabrice Bellard 发布了一个迄今为止最快的公式，用来在计算机上计算 Pi 的第 n 位二进制数字，这个公式是先前 1995 年已知最快的 Bailey-Borwein-Ploue 公式的一个变体。Bailey-Borwein-Ploue 公式计算 Pi 的二进制数字在 O (n3 (log n)3)，Bellard 改进这个算法只需要 O (n2)，从而提高令人印象深刻的 43% 的二进制计算速度，在数学界赢得人们新的尊重。

年复一年，Bellard 的许多学生项目担任了巨大事情的基础。例如，在 1998 年，Bellard 开始一个叫做 VReng (虚拟现实引擎)的项目，这是一个分布式 3D 应用程序，运用多播技术，允许通过 Internet 连接在虚拟世界中导航。在建立 VReng 之后，Bellard 注意到有效的 OpenGL 后端是基于软件的，比实际需要的慢很多。作为修改 Mesa 项目(一个交叉平台的 OpenGL 开源实现)的替代，Bellard 决定从 VReng 的代码来编写一个更小和更快的 3D 光栅。在 2002 年，Bellard 发布了 TinyGL，一个 OpenGL 的子集的小型实现，TinyGL 比 Mesa 和 Solaris 的 OpenWin OpenGL 快很多，是平台独立的，并且是数量级的小于它们中的任一个，总共才 400KB，而不是数十或百 MB。再一次，Bellard 证明了他编写有效的 C 代码的相当的技能，比竞争对手占用少得多的资源(Mesa 3D 由 Tungsten 图形公司维护，最近被虚拟化领导商 VMWare 收购)。

在 2000 年， Bellard 启动了他最重要以及使用最广泛的项目，FFMPEG。FFMPEG 由 Bellard 以假名 “Gerard Lanta” 启动，最后将 Bellard 在电信和数字信号处理方面的专长带到了最前沿。FFMPEG 是数字视频和音频方面名副其实的“瑞士军刀”，允许你录制，流，以及在许多不同的格式之间进行转换。FFMPEG 分割成几个部分，由 libavcodec 和 libformat 构成，他们都发布为自由的软件库。Libavcodec 收集音频和视频编解码库，Libavformat 提供音频和视频容器复用及解复用库，结合起来，这两个模块提供了解析和在不同格式之间进行转换的方法。

要理解 Bellard 的设计，首先必须理解数字音频和视频的格式，这些数据的表示可能有很大的不同。我们说不同是指媒体的格式。对于原始的媒体流，它们主要是布局上的区别。例 如，PCM(Pulse Code Modulation)是原始音频数据采样、量化、编码的标准数字表示法。可能你会奇怪为什么对于同一媒体数据有多种不同的格式。答案主要在于存储和播放 特定格式的费用。例如，PCM 通常是“未压缩”的格式，它线性的存储所有它得到的数据。对于音频和视频，这是非常昂贵的，尤其是数据的大小。为了减少占用的磁盘空间，不同的格式提供压 缩算法，用来节省磁盘空间的同时不降低图像的品质，或者需要强大的计算机能力。写数据到这些格式的过程叫做“编码”，读则称为“解码”，因此，知道如何针 对特定的格式做这两件事情的文件或程序的名字称为“codec”(enCODe dECode)。可是有时不同的媒体片段，或者“流”，需要进行组合。例如，一部电影由两个流组成 — 一个视频流和一个音频流。混合多个输入得到单个输出的过程称为“multiplexing”，相反的过程称为“demultiplexing”。在数字媒 体中，multiplexing 的流写到称为“容器”或者“封装”的新格式中，它包含了数据是如何存储的信息，但是不包含编码信息。

FFMPEG 是组合这两个功能到单个包的系统，Libavcodec收集了针对各种多媒体格式的codec(现在有上百个)，Libavformat 提供了针对各种容器格式的 mux/demux。结合起来，它们可以从任何支持的格式转化为有效的，由 Bellard 设计的中间格式，然后输出到相应的支持格式。Bellard 的结构让这个项目变得非常灵活和容易扩展，这允许它被纳入其它各种不同的项目中。例如，FFMPEG 当前包含数十个，也许上百个多媒体工具和播放器，例如 VLC。VCL 从它的主页上被下载了上亿次，当前还是以 5.5 次/秒的速度被下载。

在 2000 和 2001 年，在成立 FFMPEG 之后不久，Bellard 提交了 2 个作品给国际混淆C代码大赛(IOCCC)，IOCCC 是最具创造力的混淆 C 代码竞赛，竞赛由 Landon Curt Noll 和 Larry Bassel 在 1984 年成立开始。年复一年，赢得 IOCCC 大赛几乎是所有 C 程序员的荣誉勋章，反应了他们取得的成就的自豪感。Bellard 赢得了两次大赛。

首先，用 4KB 实现了一个严格受限的 C 编译器子集，这个作品不仅赢得了 2000 年大赛，也作为 Bellard 的 TinyCC 的一个起点。TinyCC 是一个 ANSI C99 编译器，比其它 C 编译器（例如 gcc）小数量级。9 年之后仍然被许多人使用。作为一个演示，Bellard 写了一个工具用 TinyCC 在 15 秒之内编译和启动 Linux 内核。

他的第二个获奖作品是 2001 年一个 475 字节的程序用于计算和打印最大已知的素数(26972593 – 1，有成百万的数字)。计算素数的常规方法比 Bellard 提交的慢很多，所以他没有采纳一个熟悉的算法，整数快速傅立叶转换，在数分钟之内打印结果。

后来，在 2005 年，Bellard 发布了也可以说是他最重要的项目：QEMU。QEMU 是一个处理器仿真，意味着用软件来模拟不同处理器体系(ISAs)，允许为一个特定处理器编译的程序，通过软件仿真在另外一个体系上运行。Rellard 可以这样做是基于邱奇-图灵理论，这个理论间接指出任何图灵完备语言配合图灵机可以仿真其它的图灵机。QEMU 加入了大量它自己的成就，它不简单是一个处理器仿真器，它用动态翻译来提高性能，这在 Usenix paper 中有解释[Bellard 2005]。QEMU 在 ISA 中使用了新方法，它不是一次翻译一条指令，QEMU 一次收集多条指令到一个 “chunk” 中，然后再翻译这个“chunk”，之后 QEMU 记住这些“chunk”，在一个程序代码中，特定的“chunk”经常会多次出现，作为分开为它们花时间翻译的替代，QEMU 存储 chunk 和关联的本土翻译，下次只是简单的执行本土翻译，而不是再次翻译 chunk。因此，Bellard 发明了第一个可以在特定情形下接近真实机器的速度的处理器仿真器。

这不是 QEMU 的终结，近年来，虚拟化在计算机科学中变得越来越多，时下最大的硬件和软件厂商(SUN 和 Microsoft) 支出大量资源来开发他们自己的虚拟化引擎(分别是 VirtualBox 和 Hyper-V)。市场领导者 VMWare 在 2008 年赚了 $1 亿多[VMWare 2009]，除了仿真处理器，QEMU 也支持一系列设备接口。从这个意义上来说，QEMU 可以被看作是 hosted 虚拟机监视器，其中它允许在其它操作系统中完整的仿真完整的系统。最后，因为它的速度，它被包含在其它各种主要的虚拟化技术中，包括 VirtualBox，Xen，以及 Linux Kernel-based 虚拟机(KVM)，直到 2009 年， Fabrice Bellard 还是 QEMU 的领导开发人。

Bellard 相信 FFMPEG 和 QEMU 是他工作中的最重要的两个项目[Gocke and Pizzolato]–却不是因为传统的金钱的理由。事实上，Fabrice Bellard 这么多重要事情中的一个是，他在自由软件授权协议保护下发布所有这些主要项目，这不仅意味着所有人可以自由的下载他的程序，也意味着任何人可以下载和修改 程序的源代码。自由软件(尤其是 copyleft 软件)背后的哲学是复杂的，可是 Bellard 的理由不同，他对金钱和名誉没有兴趣(他的假名是这方面的证据)，他只是简单的喜欢在他感兴趣和有用的项目上工作。当问他为什么决定在这样宽广的领域中工 作时，他回答说：“这也不是决定，只是往往我做同样的事情时感觉很无聊，所以我尝试一次又一次的转换项目…”，当 Bellard 在这些项目上工作时，他希望与全世界共享他的工作，也希望他的工作对他人有帮助或者有用。这也是他不屑于行政管理和社交任务的因素。Bellard 是一个了不起的程序员，他喜欢做好的，感兴趣的事情。

从他的观点来看，计算机科学分为两个部分：首先是计算机及其使用的实践探索，第二部分是理论–计算的数学基础，可以“计算”什么问题，以及计算特定 的问题有多快。不夸张的说，Fabrice Bellard 推动了这些领域的进步，不可思议的在多个领域里真正功成名就。他在给将来的计算机科学家中强调：多获取计算机科学的基础知识。对于理论他推荐 D.E. Knuth—他编著了精湛的数据结构和算法，计算机程序设计艺术。在计算机系统方面，他相信所有计算机科学家应该具备计算机硬件，以及在之上运行的低级软件的知识。这之后，一个计算机科学家就有了所有学习和建立任何他想要的软件的工具。

他也还没有停下来的意思，他当前的项目旨在在数字信号处理中有效的利用多核，尤其是软件定义的无线设备。跟随他的历史，看看他下一步将带来什么惊喜。