云风的 BLOG

去年介绍过我在项目中实现的一个动态数组模块的接口。

实际上，我为它提供的接口要更多一些，比如删除一个元素。

  void array_erase(struct array *, seqi iter);

原来的语义就是删除 iter 引用的元素。但这里引出一个问题：删除后，iter 是否应该保持有效？

从语义上说，iter 应该在调用完毕后变成一个无效引用。但实际应用中，往往需要在迭代 array 的过程中，删除符合条件的元素。让迭代器失效的做法，用起来很不方便。

因为 array 其实是以一个双向队列的形式实现。以前我取了一个巧，删除这个操作实际上是把当前位置的元素和 array 头部的元素交换，然后将 array 头 pop 出去。

这样，iter 还是指向原地，只是指向的值是已经遍历过的元素。这样，循环则可以继续下去。

今天发现一个问题，如果 iter 一开始就指向头部。那么，在 pop 操作后，iter 还是被设置成无效了。这不是一个 bug ，但是实际效果非常讨厌。思考了一下，决定修改 array_erase 的定义。

array_erase 新的行为被定义成：删除 iter 引用的元素，并将 iter 向后移动。（如果已经到尾部，则变成空引用）

btw, C++ 在处理这个问题时， remove 算法不会做删除操作，而是把符合条件的元素交换到容器尾部，再调用 erase 方法真正删除。也是为了回避类似问题。不过我不太喜欢 remove/remove_if 那种用法。在函数式语言中，那很自然；但对函数式编程支持不足的 C++ 中，使用蹩脚的 template 方法，就不太讨人喜爱了。

Posted by 云风 at 04:14 PM | Permalink | Comments (10)

美术同学给我们的游戏做了段片头视频，正要加到产品中去时，才发现我们的引擎居然没有提供视频播放的功能。我想这个东西开源库一大堆，那做起来还不是小菜一碟。可没想到还是折腾了一整天才搞定。

第一件事是考察 License 。结果用的人做多的 ffmpeg 是 GPL 的，不适合我这种商业应用。虽然有一部分功能可以以 LGPL 的方式使用，但是遵守起来也是麻烦一大堆。想了一下还是做罢。我可不想学暴风影音和 QQ Player 那样上耻辱榜。

最终考察结果，居然没太多的选择。还是 google 的 vp8 最好。License 最为宽松，所以就去下载了一份 libvpx 的最新版试用。

README 有点老旧，里面说在 Windows 下编译必须 cygwin ，我很听话的在 cygwin 下 build 了一份出来。反正就是个 libvpx.a ，打算复制到 Mingw 里去用。可在 Mingw 里链接却出了问题，缺少 pthread 库。mingw32 是不带这个库的，虽然在网上找了一份 pthread-win32 ，但是看了几眼，被那一大坨 dll 吓怕了，犹豫了一下还是没继续尝试。

重新回头研究了一下 libvpx 的 source ，发现它并不一定要使用 pthread 的 api ，貌似在 windows 下还可以使用 win32 原生 api ，看起来是为 vs 编译准备的。我估摸着 mingw 也能搞定，接着装了份 msys 试了一下，果然 ok。

现在写个玩具播放器还需要一个以 vp8 格式压缩的数据文件。看了一下， libvpx 里带了 ivfenc 。输入是 yuv 格式，输出是 ivf 格式。而 libvpx 主页上没看到 api 文档，只好去读它自带的 simple decode 的代码。看了一眼发现很好理解，用起来还是很简单的。只是这个测试用的 ivf 文件怎么生成略有头痛。

yuv 格式似乎是一种不压缩的 YUV 色彩空间的位图序列。ffmpeg 可以生成。又下了一份 ffmpeg 编译出来，把美术交过来的视频编码成了 .yuv 文件。然后在用 ivfenc 转换成了 .ivf 。

本来想播放一下转换的成果看看先。google 了一下，没有什么现成的软件可以播放之。无奈之下，只好闷头先写播放程序。写出来后怎么都不对，非常郁闷。

开始怀疑是不是 .ivf 压缩错了。好在我曾经有过 jpeg 的编解码经验，对这块有点感觉。猜测到可能是 yuv 文件不对。想了一下，原来 .yuv 文件应该只是一个纯粹的数据流，里面没有任何格式信息。比如视频的帧率，视频的尺寸等等。所以网上很难找到所谓 .yuv 的播放器。而且 ivfenc 在压缩时也必须在命令行指定视频的大小。因为 .yuv 的输入流里根本就没这个信息。一开始还想当然的以为 ivfenc 会根据命令行指定尺寸对数据源做缩放，后来手工计算了一下视频应该有的帧数和实际压缩后帧数严重不符，才发现问题。

同理，.ivf 也仅仅是一图象压缩流。并非完整的视频文件。所以也没有所谓 ivf 的 codec 了。完整的视频文件格式还需要额外的描述信息以及音频流数据等。

明白了这些就知道该怎么做了。用 ffmpeg 输入 .yuv 数据时，可以加上 -f yuv4mpegpipe 生成指定的 yuv 信息，并且指定 -pix_fmts 为 yuv420p ，这个是 ivfenc 认的 yuv 格式。（yuv 有多种组合方式，在 jpeg 的压缩中也是如此）。之后，使用 ivfenc 时指定正确的宽高，就能生成有效的 ivf 文件了。

播放视频的时候通常需要把像素数据从 YUV 转到 RGB 。这个程序我十年前用 MMX 优化过，今天再翻出来用用即可。C 的优化版本也还凑合。今天还 google 到一篇 paper 专门谈这个优化的。有兴趣的同学可以参考一下。

不过在 3d engine 里还有更好的方法：就是利用 GPU 。只需要为 YUV 各创建一张单通道帖图，然后在 ps 里做转换即可。之所以不用一张三通道帖图干这事，是因为默认的 ivf 展开的数据，YUV 是 4:1:1 储存的。

当然单纯播放视频的话，也可以用 YUV 格式的覆盖表面来做。在 DirectX 里容易实现，我还不清楚 OpenGL 里该怎么干。

今天一开始有同学建议我嵌一个媒体播放器或是 Flash player 的控件在 Engine 中。我很不愿意考虑这种方案。不解释了。其实用开源库的方法，实际消耗的人力也没有预想的大。

Posted by 云风 at 01:19 AM | Permalink | Comments (26)

今天周末，桌游店里却没客人，昨天打电话预约的朋友没来，所以我就奔到办公室测试上周写的代码。

上周的工作主要是设计了一个新的包格式，然后整合入前段时间实现的虚拟文件系统中。

这个工作和前段实现的 zipfs 有相似之处，所以做起来也很快。不过前面没仔细测试。今天比较闲，就设计了几组复杂的测试数据，感觉覆盖了各种边界情况。一测试果然发现了 Bug 。

这个 Bug 有点启发意义，所以在解决掉之后，决定记录一下。

和 zip 格式一样，我的包格式内部是平坦结构的，没有分目录。所有文件都是保存的完整的路径名聚合在一起。比如包里可能有如下文件：

bar.txt
bar/bar.txt
bar/foo.txt
foo/bar.txt
foo/foo.txt
foobar.txt

这个列表我经过了排序，是想在检索的时候可以快一点。有序的文件名可以二分检索。

我的虚拟文件系统的框架要求每个 fs 需要提供虚拟目录遍历的能力，比如在这个包内，如果需要遍历 bar 目录，就需要依次返回 bar.txt foo.txt 。如果需要遍历 / ，则返回 bar.txt bar foo foobar.txt 。

遍历的 api 形式上我用的一个 C 函数，叫做 enum_next 传入空指针的时候，返回第一项。传入非空指针的时候，返回下一项。若传入的是最后一项，则返回空。

这个 api 对实现上性能的要求并不算太高。因为在框架内，对遍历结果 cache 到了一张 hash 表内，下次查询的时候，是不用再次调用的。

我多年来养成的坏习惯，让我直觉上排斥愚笨的挨个比较的方法，（如果是这样，也不用排序了），而是采用了二分查找（这可以明显的提高检索性能一个数量级）。

由于有时候需要处理中间的子目录里的文件，在 enum_next 的时候就需要跳过。这就在跳过的时候再次使用一次二分查找。而且，这个跳过操作是需要二分查找返回一段数据，而不是一个的。

二分查找这件事，在 C++ 的 algorithm 模版中，是有 binary_search 来干这件事的。但是如果需要找到一个区间，则需要用 lower_bound 和 upper_bound ；而在 C 语言里，则有 bsearch 来做，我暂时不太清楚有没有对应的 lower_bound 等函数来获得区间的功能。

还是我的坏习惯，导致我第一反应就是自己来写这段查找代码。我对自己的编码能力非常自信，觉得完全不会出错。这样，我就不需要去编写那个比较用的回调函数了。甚至可以把整个复杂操作放在一个大循环里高效的完成。

可惜最终还是出了 bug ，倒不是出在二分查找的循环上，而是我想当然的认为，一个目录下的文件名，经过排序后，子目录里的文件名一定排在前面。然后在默认这个前提下，写了一大坨代码。最后出错了，回头又怀疑自己算法实现有误，前后查了一个多小时 :( 。比如在这个例子中，bar.txt 就排在了 bar/bar.txt 的前面。

其实这个 bug 是完全可以在编写的时候避免的。我犯了许多经典错误：

1. 过早优化（这个可以商榷，虽然不是热点，这种明显的优化我认为还是可以顺手做的。不然永远都不会有人做。即使在某种特定环境下，它变成了热点）

2. 没有尽可能的分解算法。（觉得这个问题足够简单，不需要分的太细。性能方面的思考作祟，想尽量减少不必要的层次）

3. 没有使用现成的算法库。这一点跟 C 库在这方面略显单薄有关。不过如果用 C++ ，估计我也会比较反感那些需要自定义比较函数的算法模板。

Posted by 云风 at 11:30 PM | Permalink | Comments (7)

9 年前，我设计了网易游戏的资源包以及补丁包的数据格式。

当初的设计目的是：方便解析，快速定位资源包内的文件，方便更新、每次更新尽可能的节约带宽。这些年来，虽然各个项目修修补补的改进了资源包的格式，但本质上并没有特别大的修改。

一开始我们直接把需要打包的文件连接起来，在文件末尾附上文件索引表。当初为了快速定位文件名，文件名做了 hash 处理，可以用 hash 值直接定位文件。而资源包里并没有储存文件名信息，而是保存在一个额外的 index 文件中。这个 index 文件并不对外发布。所以直接对资源包解包是无法准确还原文件名的。

btw, 暴雪的 mpq 文件也是作类似处理的。除非你猜测出文件名，否则也很难对文件名还原。网上许多 mpq 解包工具都针对特定游戏附了一个额外的文件名列表。

和许多其它游戏 Client （比如暴雪的 MPQ 文件）不同。我们的包格式里文件与文件之间是允许有空洞的。这是考虑到资源包文件都比较大。如果用传统的打包软件运作的方式：从包内删除一个文件，就重新打包或移动内部数据。在玩家更新资源的时候，就会有大量的文件 IO 操作。比如 WOW 或 SC2 在更新的时候，下载更新包的时间往往只占整个更新时间的一小部分，大部分时间花在把补丁打在已有的资源包上。

如果频繁更新客户端，对于用户，这会有很讨厌的等待。

所以当初考虑到这个因素，我们在删除包内文件时，并不移动资源包内的数据，而是把空间留下来。如果新增加的文件较之小，就重复利用这个空间。如果利用不上，就浪费在那里。这有点像内存管理算法，时间久了，资源包内会有一些空洞，但也是可以接受的。

同时，还有另一个方式更新新的资源。那就是将需要更新的文件单独打包，以相同文件名（后缀不同）保存在用户硬盘上。游戏引擎在读取资源的时候，优先在更新的资源包内检索。这个方式在 Id soft 的 Quake/Doom 系列中也有采用。

为了保证用户补丁更新速度。我们的补丁中并不是保存的资源包内的小文件。而是在开发机上以增量方式重新打包。补丁文件其实是整个资源包的 diff 文件。由于前面所述的打包方案，这个 2 进制 diff 文件其实可以做到很小。尤其对某些文件的局部修改，对整个资源包的影响很小。

在公司，有后来的同事质疑过这种方式，觉得其对减少补丁体积的作用不大。反而增量打包增加了许多制作补丁包的时间。主张直接在补丁中放入更新的小文件，然后让最最终用户机上以小文件为单位做 patching 。

的确，2 进制 diff 的作用有限，现在很多项目改用文本数据格式，很小的修改就会影响整个文件的 diff 结果。不过原始的设计也有其历史原因。因为 10 年前硬盘 I/O 速度很慢，而大话西游在设计时又需要实现无缝加载的大地图。所以地图文件的格式是经过特别设计的。这种方式很适合地图文件的修改和更新。另外，对于未压缩的图片文件的更新也有其意义。

总结完旧有设计后。我希望在新引擎中对资源包格式做一定的改进。

首先是加入内置的压缩。原有格式是只负责打包而不管压缩的。若数据需要压缩，由上层模块去负责。这么做跟大话西游中的地图文件需要随机访问有关。另外和增量打包也有点关系。如果对每个小文件统一做压缩，2 进制 diff 就几乎无效了。

这次希望以文件系统的方式来管理资源包，而不是简单的将文件连接起来。把大文件分块，以类似 FAT 表的形式来管理大文件。每个块则可以单独选择压缩或不压缩。这样即能压缩数据，又可以提供文件随机访问的能力。（能够方便的实现数据包的嵌套）

在资源包内支持链接功能。

开发期，我们可以让所有资源都不用理会复杂的引用关系，而是各自有独立的一份。比如模型文件引用的贴图都可以依附在模型文件的目录下。这样在开发期很方便管理这些数据。而打包时，可以比较所有需打包文件，把内容相同的文件剔除，只是做一个链接。同时引擎也能识别出引用关系，同样的资源只加载一次。

关于增量打包的问题，开发人员发布补丁的效率的确需要考虑。其实在开发期，有个简便快速的制作流程，也方便搭建每日构建。虽然按原有方式也有许多方法加快制作补丁的速度（比如预先计算所有文件的 md5 值保存起来，加块增量打包软件的分析速度）。我希望可以制作时直接生成补丁文件。这个补丁则可以是每个小文件的 diff 信息。另外再制作一个 patch 工具，将补丁打上去。

这个 patch 工具的工作流程可以是从旧的包中抽取出需要 patch 的小文件，和补丁中的 diff 信息合并，得到一个需要更新的包。然后将旧包中那些小文件删除，并向前压缩掉空洞。最后将新旧两个包连接起来。

压缩空洞的这个过程会占用用户机的一些文件 IO 时间。打补丁的速度会慢一些。不过我觉得影响不会太大。因为经常更新的文件会趋向于放在资源包的末尾（每次更新都抽取出来，并连接到末尾），所以压缩空洞时需要搬移的数据有很大机会并不多。

这样设计补丁包的格式，也会更干净一点。

Posted by 云风 at 01:40 AM | Permalink | Comments (11)

又仔细推敲了两天，把 lua 版的 protobuf 库完善了一下。主要是做了两个工作：

1. protobuf 本身的格式，google 是自描述的。定义为 google.protobuf.descriptor 。我先自己实现的 parser 图方便，用了自己的中间交换格式。为了日后更通用，稍微修改了一下，可以生成于官方相同的结构。解析的性能稍有下降，不过应该兼容性更好。

2. 一开始实现的 api 虽然性能非常好。（经简单测试，是 python 库的 30~40 倍，和 C++ 库性能相当）但若消息格式复杂，实现起来稍有麻烦。所以我做了点小封装。即为每个消息生成一对函数，可以用来打包和解包完整的消息，映射到 lua 的 table 结构上。lua 生成代码供自己调用的技巧在 lua 社区广泛使用。比如 kepler 项目。这使得 lua 可以用很短的代码行数完成很复杂的工作，不失性能。我这个封装层只有 100 行代码左右，一大半代码是为了解决消息展开时有递归定义的情况，否则更简短。（message 中有一些 field 的类型是自己，这是一种不多见的用法，但 protobuf 似乎并没有拒绝这种用法）

在性能非常重要的场合，使用原始的 api 对简单的数据包处理，加上 lua-jit ，应该可以达到和 C 相近的性能。而另一些情况下，需要定义比较复杂的数据结构，并序列化。这个时候用封装过的 api 就好了。

这两天还有些想法。想做一个类似 rings 的多 state 库，和 rings 不同，我希望 states 间交换数据更为高效。

考察了一下 lua 的源代码，我觉得稍做改动就可以让多个 states 间共享一个 string table 。这样，states 间传递 string 就能从 O(n) 变为 O(1) 。

另外，借助 debug hook 和 coroutine 机制，可以让 lua 代码运行一小段片段后自动交回控制权。不过在不修改 lua 代码之前暂时还不能这么干。这是因为 yield 有一些限制。比较期待 lua 5.2 的发布，以后 yield 的限制会少很多。

使用多 states 对长期运行的服务器程序非常有帮助。可以回避许多不谨慎造成的内存泄露问题。

Posted by 云风 at 12:09 AM | Permalink | Comments (3)

Google 的 Jeff Dean 同学说，设计分布式系统一定要有 Protocol Description Language。

Google Proto Buffers 的意义在于，定义了一个不错的 PDL 。protobuffers 的实现反而不那么重要了。

这几天我一直在倒腾 lua 下的 proto buffers 的支持。一直在思考，怎样的接口才是最适合 lua 使用的。

大多数语言下的 proto buffers 实现，都是将编码的数据块展开成本地语言的数据结构。对于 C/C++ ，这是最高效的形式。但对于动态语言，那就未必了。虽然 google 为 python 做的 proto buffers 的官方实现也是如此，但我依然想考虑一下，是否有更高效的方式来做这件事。

lua ，最高效的数据处理交换是利用语言的栈。虽然 table 也足够快，但复杂且深层次的 table 往往容易成为最终的性能瓶颈。btw, google 的 js V8 引擎，在部分场合表现的比 lua jit 更为出色，很大程度上是因为它极大的加快了 table 的查询。这几乎会成为所有解释型动态语言的性能热点。而且不断了生成临时 table ，还会给 gc 造成较大的负担。那么，能不能找到一种方式可以回避在 lua 中构造复杂数据结构，而又能方便的使用由 proto buffers 定义出来的结构化数据呢？

我花了三四天初步实现了一个 lua proto buffers 的库，全部是以 C 代码完成的。最终提供给 lua 的接口只有四个。

1. load 能加载一个 proto buffers 的元数据，对协议本身做一个描述。并生成一个 C 对象 (userdata) 返回到 lua state 中。这个 C 对象包含了一组 proto 描述信息，除了其中的字符串信息外，全部储存在一块连续的内存中。作为 lua 的 userdata ，不需要任何 gc 方法。其中引用的字符串全部记录在这个 userdata 的环境表中，在 C 对象里只记录字符串表里的序号。这个方式可以很大的提高 lua 运行时的字符串传递性能。

2. pattern 可以为某个 message 生成一个模式对象 (还是 C 对象)，这个模式对象可以用来解码或编码数据。pattern 的概念是整个库的核心概念。库会依据 pattern 来编码或解码数据。pattern 本身的生成比较重量，但在实际应用中，往往是一次性的，而不需要对每个数据包处理时都重新生成 pattern 。做一些小手脚，就可以在 lua 层面做进一步的简单封装。用字符串的形式来 cache 并索引 pattern 。

3. unpack 可以对一个数据块进行解包工作。unpack 必须提供数据块以及相应的 pattern 对象。它会按 pattern 的指示把结构化数据解到栈上。这种方式回避了每次解包都生成临时的 table 。当然，如果使用者还是喜欢构造一个 table 来表达数据块中的数据结构的话，依然可以通过几行 lua 封装代码来办到。

4. pack 可以根据一个 pattern 对数据块打包。同样从栈接收数据源。不需要构造临时的 table 用于打包。

我在做这个库之前，做了一些工作来解析 Google Proto Buffers 定义的协议描述文件。如上所说，我认为，协议定义及描述是整个 Proto Buffers 的核心，而其实现以及二进制编码规则则是次要的东西。

google 提供了开源工具，把文本协议描述文件编译成 proto buffers 自身形式的结构化数据。这做了很漂亮，也方便了对协议本身的解析。不过若是抛开二进制编码，若想让整套协议自举，而整个过程和具体编码形式无关的话，更有趣的做法是自己来实现文本协议描述的解析。

好在用 lua 来做这项工作并不太难，proto buffers 定义的语言也相当简单，容易解析。我大约写了 100 来行 lua 代码来完成基本的语义分析。当然，用了强大的 lpeg 库。话说，PEG 是个相当强大的东西，强烈推荐没学过的同学们好好学习一下。用顺手的话，为自己的项目定义 DSL 那是易如反掌。

整个解析的实际运行过程非常繁重，但最终只是生成一个很小的 C 数据对象。我用了一个有趣的方案来干这件事：单独开一个 lua State 来完成协议的解析。这个独立的 lua State 总共所消耗的内存可以事先预估，不会太大（跟 proto 文件的规模以及复杂度有关）。所以我为这个独立的 State 定制了一个只分配不释放的内存管理器。这个内存管理器工作在独立的系统内存页上，方便最后一次回收。这样，每次解析一个协议文件，只需要消耗一些临时内存，而在解析完后，能够绝对干净的清除痕迹。我统计了一下一个最终大约 70K 的 C 数据对象，处理过程消耗了大约 1.5M 内存。

灵活使用多个 lua State 应该是一个良好的习惯。尤其在较大规模的需要长期运行程序中，把各个模块分配到独立的 lua State 空间中运行，可以使任务完成后，内存得到准确的回收。

这几天做的这个东西，还很初步，所以就不细写了。等成熟后再考虑开源。

ps. 在 lua 社区，设计些小的模式语言来完成数据处理，似乎是一个很流行的做法。lua 自带的字符串匹配如此；cosmo 也是个有趣的小玩意；lpeg 也提供一个 The re Module 来模拟正则表达式的语法。等等这些启发我设计出这个 proto buffers 的 pattern 。

Posted by 云风 at 12:06 AM | Permalink | Comments (17)

今天跑昨天晚上写的一个小程序，莫名其妙的不能运行。开 gdb 调试没有任意异常，直接退出，连 main 函数都没有进。注释掉大量代码后依旧。把 gdb 从 6.3 升级到 6.8 后，再调试，捕获了一个不知名的异常。

又把代码注释干净，程序正常了。仔细考虑了一下，最后注释掉的代码间接 link 了 lua 的库。而 lua 的库引用了 lua 的动态库。程序运行时可能是因为没有找到 dll 而退出。

把 lua 的 dll 加到 path 中就正常了。但是奇怪的是，系统并没有弹出对话框提示。仔细想了一下，原来是我没有从 explore 启动控制台，而是在编辑器里启动的，可能是编辑器软件没有写好，把本应该系统弹出的缺少 dll 的对话框拦截了。

Soloist 同学说，他也碰到过一次 Total Commander 吃掉缺少 dll 无法启动程序的对话框。记录一下这个问题，祭奠我找问题逝去的半小时。

Posted by 云风 at 12:25 PM | Permalink | Comments (13)