云风的 BLOG

花了三天时间搞定了困扰了我半年的事情，心情非常之好。

是这样的。我们的 3d engine 中的骨骼动画的插值融合总有点问题。如果是两个变化比较大的动画想从一个过度到另外一个，效果总是不太对。对于图形程序，很难用测试驱动的方式开发的缘故之一，就是因为对与不对有很大程度是人的视觉感受，而不是可以简单校验的数值。想写一个判定正确与否的程序，估计不比把代码写正确简单。

所谓不对呢，问题其实老早也想明白了。现象就是有些动作之间过度像纸片一样，而不是直觉中，人物用合理的方式运动。这时，只显示骨骼动画信息中的关键帧反而效果更好。（这些关键帧，是美术人员在 max 这样的软件中制作出来并导出的：或是用动作捕捉而来的）

其问题在于，没能对骨骼的变换信息做正确的插值。

原来这部分代码写的很脏乱，且原作者已经离开。后继人员要么知其然而不知其所以然的在上面修补，要么就没心思把这个东西真的弄对。（毕竟暂时看起来，这并不是迫切需要解决的问题。它不会引起程序崩溃，也不影响开发进度。）

我倒是一直很想自己来重新设计制作这一块，可一直忙于更多别的事情。加上，大学线形代数也没学好，把其中的数学基础知识补上，还是颇要些精力的。

拖了这么久，终于，这周一咬牙，求人不如求己。还是自己弄吧。

早期的 3d 实时渲染，都是简单的把顶点连成面，然后附上贴图把模型显示出来的。若是想让模型动起来，就制作若干动作下的模型，在文件中记录下动作每帧的模型造型的顶点信息。简单说，一个动作，就是一系列的独立模型。这就是所谓的顶点动画。Quake 的前几个版本都是这么干的。这样干主要是因为早期的硬件条件有限，让硬件去处理顶点，渲染多边形就已经够吃力了，没多余的计算力去干别的事情。

后来，随着游戏的视觉内容急剧增加，把丰富的动画全部输出成一帧一帧的模型，数据量上已经不太吃的消。慢慢的，还加入一些和环境互动的动作，单纯的用预生成好的帧顶点动画已经不再满足要求。

人们想出一个办法，把 3d 模型抽象成一组关键点的集合。（这个抽象就好比从 2D 到 3D ，把一堆的像素构成的图象，抽象到少一个数量级的三角型上）整个模型的运动，可以想象成这些关键点的运动，而构成模型的顶点及面，都是受这些关键点的影响而已。

这些关键点被称为骨骼，非常之形象，而且在人物动画中，这些点通常也正好在人物关节的位置。

和 max 里制作不同。这种建模软件展现给美术人员的骨骼真的是有体积的实体。而程序处理的时候，所谓的骨骼却是一个个的点，更准确点说，是一组组空间变换。点只是表达了空间位置而已，并没有表达出自身的转动和缩放变换。

使用这些骨骼信息非常简单。只需要把模型上的点，根据它们和骨骼间的关系（被称为皮肤的东西），乘上对应骨骼的变换矩阵即可得到在骨骼摆成特定姿势下的正确空间位置。

这样，我们只需要把骨架摆成特定姿势，就可以计算出蒙皮上所有相关点的空间坐标，并通过显卡硬件渲染出来。在现代显卡中，GPU 甚至可以帮你做最后一步矩阵变换的乘法。

剩下的工作，就是怎样得到骨架的信息了。

3d 人物做任何动作，都可以在 3d 软件里制作好，输出整个动作每个时间点的骨架空间信息。这些是些离散的数据。按我们游戏的制作标准，是一秒 12 到 15 帧。（另一种纸娃娃系统暂且不谈）

当游戏的实际渲染帧率更高，或由于特殊需要，想放慢动作运动速度时。预做好的骨架信息就不够用了。

当然，你可以让动作一格格跳，也不太所谓。只是在不同的动作切换时，会比较奇怪。更好的方法是在两帧动作间做插值处理。

这就是我这几天工作的重点。其实这是项很老的技术。谁让我精力实现有限，直到今天才真正卖力研究它呢。

如上所述，当我们不插值，直接把美术输出的数据来用的时候，一切都是很简单的。无非是在渲染前，把那些顶点数据乘上个骨骼变换矩阵而已。如果我们需要知道两帧图象的中间状态呢？马上能想到的是，对每个骨骼点，两帧的对应变换矩阵做插值。

可惜的是，变换矩阵中的每一项并不可以正交分解，独立插值的。

而且，虽然最后我们用到的变换数据是每根骨骼在绝对空间中的绝对变换。但实际上在制作这些数据时，骨骼之间是有相互关系，相互影响，最后把各级骨骼的空间变换叠加起来的。

综合这两个问题来看，我们需要做的工作，一是尽量把变换矩阵正交分解成可以独立插值的元素。二是将骨骼的变换行为还原到影响到它的上一级骨骼的局部空间内。比如两组动画间要做过度，可能手的位置差别很大，但是对指关节的运动的插值，却只应该考虑指头相对手掌的运动，而不需要考虑手指在绝对空间中的变化量。

假设手指的绝对变换矩阵为 M1 ，手腕的变换矩阵为 M2 。那么可求得手指在手腕空间中的变换为 M1 * M2' 。（哎，上大学时光顾着玩程序去了，线形代数没好好学。这几天补习这方面的时候真累。不过经过自己的推导搞明白后，想忘都比较难了。）

这一步是相对简单的，但是不是要把整个变换还原到父节点呢？经过一番思考后，我的结论是否。

我们先看另一个问题：做美术制作过程中，如果数据来源是动作捕捉仪，那么骨骼做变换无非是自旋和位移。就我目前看到的动作捕捉设备，无非是若干照相器材布置在空房间中，演员穿上特制的衣服，衣服上的关节处安装有若干反射光的小球。照相机拍摄到这些小球在空间中的变化，把数据输出到计算机。所以，我们用这套设备得到的骨骼信息，就是一些点的空间移动和自己朝向的改变了。（小球是否能被感知方向暂时我还没能确认，有空我去公司的捕捉室实地研究一下）

如果是美术在建模软件里手工制作的话，因为骨骼被抽象为有体积的实体了。在美术看来，每次操作的是一段骨头，而数据上，被影响的是骨头的两端。最原始的变换行为，其实是旋转和伸缩。但对应到端点上，就成了位移和旋转（对父节点是旋转，对子节点是位移）以及少量的缩放。据我的美术同事讲，缩放其实是很少用的，因为很难控制。btw, 据我所知，暴雪到目前为止，都是手调动画，没有使用动作捕捉设备。

综上，骨骼的变换矩阵，其实是有若干次的缩放，旋转，和位移变换叠加的结果。

其中，缩放属于形变；而旋转和位移都属于自身在空间中状态的变化。我们应该分开看这个问题，形变往往是不因骨骼的连接关系而继承的，如果有复杂形变，（多次旋转和拉伸的反复叠加）我们就无法从最终的变换矩阵中分离出一个缩放矩阵。好在，一般不会有人刻意去制造这种变换方式（用动作捕捉更是不可能得到这种变换）。所以，我第一步就从全局变换矩阵中分离出缩放矩阵来。这个变换是不受骨骼层级连接而传递其影响的。

剩下的，就只有若干旋转和位移信息包含其中。

我们知道，一个带方向的点（一个向量）在空间中，无论以什么次序，做多少旋转和位移，最终都可以表达为一次旋转加一次位移。

即，我们分离缩放变换后，计算得到的子节点在父节点空间中的相对变换（M1 * M2'）中一定可以把这个矩阵表示为某个旋转变换 R * 另个位移变换 T 。

固然，这里的 M1 和 M2' 中也可分解为R1 * T1 以及 T2' * R2'。但是我尝试找到最终结果 R 和 T 用 R1 T1 R2 T2 的简单表达形式，却失败了。这都怪大学里的线性代数没好好学啊。不过既然我知道最终的结果矩阵中只包旋转和位移，分离结果函数很容易的。他们分别是 4*4 的变换矩阵中的 3*3 项（旋转部分）以及一行位移部分。

对于旋转变换的插值，是不能直接对 3*3 的矩阵线性插值的。正确的方法是把矩阵表达为四元数。话说，搞明白四元数这个东西又颇费了我一些时间，这里就不展开讲了。简单的说，对矩阵旋转插值不可行是因为它的 9 个数值并不正交。而四元数则是的四个部分则是相对独立的。正如在 2D 空间中，2 个数字（复数）可以表达一种旋转，旋转的表达在 3D 空间则扩展到了四个数字。四元数的插值和计算方法，网上能搜出许多。读到这里，我们只需要知道，这是一种方便做插值的描述旋转变换的表达形式即可。

那么，我们分离出一次旋转和一次位移后，分别做插值就可以了吗？

我认为是不完全正确的。尤其是在动作幅度较大，或两个关系疏远的动作之间。

设想一下，如果一个肢势下，手指向左边；而另一个姿势，同一只胳膊，指向了右边。从旋转角度看，胳膊上的变换，方向转了 180 度。如果人的以人的中轴线为 0 看，位置从负变到正。假若我们分别对旋转和位移插值，过度出中间状态。正中间的位置，手就会萎缩到几乎没有，而不是我们直觉中的旋转过来。这也是，我们早先的版本，有时人会变纸片的缘故。

问题出在哪里？

旋转变换和位移依然不是正交的。

我们直觉上正确的骨架，其实，关节之间的距离是几乎不变的，也就是一个刚性的骨架。各个关节其实要么在做自旋，要么在围绕父节点公转。自旋和公转则是相互正交。如果偶尔有距离改变，那么其运动也是沿着公转轴方向靠近或远离，和旋转变换也是正交的。

如果我们可以把每个骨骼变换，分解为相对父亲的公转，相对自己的自转，以及公转轴上的伸缩，那么就可以正确的做插值了。既把一个变换表示为形为 R1 * T * R2 的形式，且这个 T 只有一根轴上的变换。

之前，我们已经可以把变换分解为 R * T ，剩下的工作就是把这个转换一种形式。

这个转换不算太复杂，但需要使用一点点空间几何知识和少许线性代数。推导过程就不详述了。只写写大概思路：取一个坐标轴做主方向，比如 X 轴。如果原来 T 里的位移不仅仅包含 X 分量，就把它和 X 轴做叉乘，得到一个垂直的法向量。以这个向量做旋转轴，以 T 和 x 轴的夹角为旋转角（可以很简单的得到这个角的 cos 值），构造一个旋转变换 R1 ，那么 T 就能表示为 R1' * T1 * R1 ，其中 T1 只包含了 X 分量，值为 T 中位移向量的长度。它的几何意义就是这个骨头到父节点的距离。

整个变换即为 R * R1' * T1 * R1 ，前两个旋转变换可以合并为一个旋转。其几何意义就是骨骼的自转量。后一个 R1 是它绕父亲的公转量。

最后，我们可以放心的做各种混合和插值处理了。看起来貌似很多运算，几乎都是在开发期预生成好的。最终运行时需要计算的东西并不多。

简单谈一下动画数据的压缩。

3D MMORPG 里，动画数据很容易吃掉大量的硬盘。如果非要考虑压缩这些数据了，可以考虑这样几个方面。上面的思路，每个骨骼点，在每个关键帧上需要保存两个旋转和一个轴向位移。这个位移往往在动画中是不变的，所以就是两个旋转变换。保存两个四元数即可。

由于四元数是归一化过的，其实就是三个绝对值小于等于一的数字加一个符号位。我们对旋转的精度要求其实不会特别的高。可以考虑使用定点数。我大致想到的方案是使用一个 32bit 数字保存一个四元数，第四个可计算的量的符号位占用 1bit ，另外三个量分别占用 10 bit 。分摊开来等价于在每个旋转方向上，可以分出 1024 个角度，足够满足一般需求。由于骨骼动画中，大量的旋转都是相对不变的。我们可以简单的做一个 hash 表 cache 这些 32bit 压缩的四元数到四个 float 的转换。应该不需要多大的 cache 就能得到比较高的命中率。

关于骨骼动画模块的设计。

我个人认为不需要太关注单次插值计算的时间效率。

插值和混合应该是一个可选项，对动画模块外做成黑盒子。我们只需要至少能提供关键帧信息即可。关键帧的最终变换也可以预运算好。

对于模块对外的接口，只需要简单的一个：给定指定的动画名字和帧号，返回骨骼变换信息。并允许提供混合帧的动画名及帧号，以及混合比。

真正的性能热点应该在 cache 管理上，而不在生成这些变换信息的计算上。

今天太晚了，就随便写写到这里了。把预想的程序完成真是一大快事。

Posted by 云风 at 03:14 AM | Permalink | Comments (29)

上次谈到了一个常用的 ADT ，sequence 的 C 实现。通常，我们不会直接使用 sequence ，而是用它来实现满足最终需要的数据结构。比如消息队列，比如指令堆栈，等等。一个实现的优秀的 seq 的好处在于，即使你只用到其中一部分功能，也不会因为那些没用的部分损失太多的（时间和空间上的）性能。

今天我想谈另一个更为实用的 ADT ，动态数组。这个在传世神作《C 语言接口与实现》中也提到过，我不是想说其写的不对，或是讲述的不周全，实现的不漂亮。只是以我的观点来展开相关的问题。

为什么要有数组？C 语言内置了数组、在 C99 中更是允许在堆栈上声明非固定长度的数组。C++ 里以 STL 的形式提供了 vector 模块供程序员使用。

我们面临的问题，不是语言和库为我们提供了多少可能。而是我们无法确定，我们到底至少需要什么？

通常，数组让我们可以随机（以 O(1) 的时间复杂度）访问其内的数据。但是，随机访问不是目的，而是手段。我们究竟需要一个数组解决怎样的问题？面对怎样的问题，需要处理的数据需要以数组方式组织？我这几年始终不敢说自己得到了确切的答案。往往，我们只是直觉上感觉，用一个 vector （使用 C++ ）非常方便，所以就用了。当我在用 C 的时候，我总是随手写上一个 realloc ，来扩展我的数据块。最近一段时间，我觉得有必要归纳一下需求，设计一个通用模块来统一解决问题了。

思考的结果就是：当我们周期性的聚合一堆数据时，我们需要一个数组，且这个数组的长度是不确定的，应该可以动态增长。

数组最重要的特性是可以最高效的遍历，即依次处理数组内部的元素。在 C 语言的层面考虑这个问题时，就应该更细致考虑实现的差别引起的性能差异。比如链表的遍历同样是 O(N) ，但是时间和空间的开销都是大于连续内存空间的数组的。

我们需要快速的清空数组，方便下一个周期聚合新的数据。

我们需要对数据排序，使得按我们的需要的次序去依次处理（遍历）数组中的元素。

有时候，我们需要相对快速的查找。一旦数据是有序的，二分查找可以让时间复杂度减少到 O(log n) 。

其它，我们不再需要。

注：我们往往混淆了另一个需求。很多时候，我们把数组当成了一个高性能却有局限性的 key-value 字典。这个 key 就是数组内数据的数字索引。对于用一个 key （可能是数，也可能不是）快速索引到值的需求，应该放到另一个地方去考虑。

最终，我为 array 这个 ADT 提供了如下的方法：

struct array * array_create(int atom_size);
void array_release(struct array *);
void array_clear(struct array *);
void array_push(struct array *, void *atom);
void array_iterator(struct array *, seqi iter);
void array_sort(struct array *, int (*compar)(void *,void *));

这里，暂时没有提供 binarysearch 方法，因为暂时我还没有用到。我还不确定是不是真的有意义，以及最佳的接口定义应该是怎样。

在实现时，我开辟了一整块连续内存保存数据。当使用者 push 一个元素时，采用值复制的方式，复制到 array 内部。然后用 seq 来管理对内部元素的引用（指针）。

当数据区不够大时，采用 realloc 扩展数据区内存。一旦内存地址发生变化，则修改对应的 seq 里的指针。把索引和数据分开存放，可以提高排序的效率（数据交换量比较小）。

sort 函数提供了一个类似 qsort 接口的比较函数。但是，由于和 qsort 的定义有所不同，所以不能直接去调用 qsort 。在 glibc 中，有另一个 qsort_r 可以满足需求。不过我考虑到性能，自己重新实现了一个快速排序。反正，也没几行代码。

这里，由于数据在内存中的位置并不固定。从 seqi 中拿到的指针是不可以被传递保存到别的数据结构体中的。包括 seqi 这个迭代子，根据上篇关于 sequence 实现的描述，也不允许长期保留。你可以认为，这是这个 ADT 的局限性。不过我个人认为，我们每设计一个东西，只应该解决有限的，定义好的需求。而不应该包罗万象。

只做一件事，并把它做好。

Posted by 云风 at 01:51 PM | Permalink | Comments (11)

自从上次我们组队下地城（Descent 这个游戏）以来，主位面的时间又过去了一个月。

每周都想去一洗被 DM 灭团的耻辱，可每次都碰到别的事情。出差、音乐节、Erlang 大会…… 这次大家下定了决心一定要去桌游了，所以周六就约好了时间。

本周人数较多，（三个同事+两个家属+我）一共六人。且其中一个家属玩的比较少。我们还是没能组队下地城。桌游店的老板给我们推荐了 ACQUIRE 。我们玩的很欢乐。

三盘过后，就已经是晚上 23 点。以往有家属同行的时候，这就意味着该散场了。没有 mm 肯和我们一起通宵的。不过这次有点不同，连女生都比较投入。大家很为难的相互支吾了一下，然后很开心的决定再战一局。凌晨一点多才喧闹的离开。

btw, 桌游店周六的生意真不错，这个时候还坐满了人。

回家的路上，我们讨论着游戏的策略，突然想自己 DIY 一套玩。想想觉得其实道具很简单的，卡片也可以很方便的用扑克代替。只不过数量比较多，要买七副扑克。

半路碰到临检。半夜两点大马路上，一堆人挤在一辆小破车里，肯定去那里 High 过了。警察叔叔一定这么想。让试吹了两次后，只好承认我的身体里没一点酒精这个事实。还真是让人失望啊…… 不过我们超载了，其他几个人只好去拦 Taxi 。

今天睡到 3 点起来，到了公司，Sean 同学也在。我们开始在办公室翻箱倒柜找各种材料。最后我相中了那些公司发的旧台历，量了下尺寸，刚好够做一套 ACQUIRE 。

这是我们的材料及工具：

台历的面板用料很实在，做小拼板很不错。切割它们绝对是项体力+技术活。Sean 同学拿出学校做金工实习的劲头，和我两人交替着切割。那玩意很硬，用切纸铡刀根本切不动（而且容易卷边）。只能拿美工刀去反复划成一条条的，然后再用铡刀切。

用多余的台历纸做了个收纳盒，装起来。

棋盘用胶带包了边后很漂亮。然后拿 OpenOffice 制作了盘面粘上去。记分表则是我手写的一个 CSS / HTML 打印出来的。

Sean 同学拿零食的包装盒制作了支架台。我用新买来的扑克牌剪开装饰了一下小拼板做成的道具。

最后大功告成后大约是这样的：

玩的时候铺开是这个样子的：

感觉还不错 :D

ACQUIRE 是个历史颇为悠久的游戏。反应了在万恶的资本主义社会中，贪得无厌的资本家们是怎样金融运作，操作一家家公司上市、退市，从中讹诈劳动人民的剩余价值。

它的第一版是 1962 年发行的。已经快 50 年了。每隔几年都会再版，各个版本都非常漂亮，比如

或是非常华丽的 99 年版：

想想人家 50 年前就对资本运作的理解如此深刻，可以抽象出这样有趣的游戏。果然，我们今天还只能算是停留在资本主义的初级阶段啊。

Posted by 云风 at 01:37 AM | Permalink | Comments (13)

这段时间一直在写代码，大约一周三四千行的样子。所以没有什么闲余时间写 blog 。可能再过段时间可以总结一些想法吧。

我这几年一直用 C 在做设计和编码（当然还写了许多 Lua 程序）。也一直在纠结，到底，我们在系统编程中，最少的需求是什么。C++ 给了我们太多，但是 C 又给的太少。如果常年用 C 写程序，那么必须多一点。

比如基础数据类型，在《C语言接口与实现》中叫作 ADT 的东西。给出了许多。我还是觉得多了点，其实用不了那么些。

其中 atom 是必须的，在我的系统中，给了个不恰当的命名，但是本质是一样的。以前写过一篇 blog 讨论过。

因为 Lua 用的太多，感觉字典是个很有用的东西，所以我实现了一个基本的 hash map 。

然后，用的比较多的是变长数组，以及用于收发消息的队列。这个东西实在是太简单了，我一直没有单独实现成一个独立模块，都是随用随写。也不大容易写错。但是写了这么多年，我还是想把它抽象出来。和同事讨论的时候，Soloist 同学提醒我，其实我想要的 ADT 就是 sequence 。

一个可以方便的从两头插入，从两头删除，可变长，可以高效随机访问的 sequence 。在 《C语言接口与实现》里把这个东西简写为 seq ，在 Haskell 里也是。

为什么我一直从心里排斥把 seq 做成独立模块，我想是我的追求高效的坏习惯在作祟。虽然这个习惯很不好，但是我总觉得明明可以用一个原生数组来做这件事情，用个指针就可以遍历了，何必多几次函数调用，和数据访问的间接性呢。

固然，C++ 的 STL 提供了一个折中的方案，把代码都写到 .h 里（使用 template ），利用编译器去优化 inline 代码。但是却在源代码中暴露了数据结构的实现细节。今天的我看来，这是更不可以容忍的事情。（不同意这个观点的同学请原谅我的偏执）

从昨天开始，我又一次仔细考虑了这个问题，并花了今天一天的时间，实现了一个让我还算满意的 seq 模块。

隐藏内部细节，总会有一些性能损失。那么，哪部分我所关注，而哪些是可以容忍的？

IMHO ，我希望让 seq 的遍历可以最到最高效，就同用一个 for 循环以及 int 类型的 i 去迭代它一样高效。读写 seq 里的数据也希望是高效的。而从两头插入和删除数据，则是可以承担性能损失。

seq 的内部数据结构应该隐藏起来。大部分操作也仅以 C API 形式提供。seq 要可以可变长。并在内存上连续（读写性能最好）。

最终的设计，我用一个数组模拟了一个循环队列。并暴露了一个迭代器的数据结构。这个迭代器大多数情况下能够也只允许在栈上构造。这里使用了 C 的一个小技巧，是学习的 jmp_buf 的定义。这样，这个被我称为 seqi 的数据类型，就可以直接在栈上声明，并以指针形式传递了。

struct seq;

struct _seq_iterator {
    struct seq *seq;
    void **begin;
    int offset;
    int length;
};

typedef struct _seq_iterator seqi[1];

由于 seq 是可变长的，迭代的过程又需要足够高效。我选择在 seq 本身变化的时候再去通知迭代器，而不是在迭代的时候去查询。所以迭代都需要向 seq 本身登记。

另外，我在迭代器里记录了一块连续内存空间，迭代器在这个区间内是可以自由前移后移，读写数据的（用 inline 函数或宏来实现）。只有超出这个范围，才需要调用更重量的 api 。

由于 seq 的内部实现中，数据区是由两块连续空间构成（循环利用），这个维护工作稍显重量，幸运的是，大多数情况下，我们不会进到这个分支。

这几个相关函数被我定义成：

void seq_head(struct seq *s , seqi iter);
void seq_tail(struct seq *s , seqi iter);
void seq_close(seqi iter);
void seq_update(seqi iter);

static inline void
seq_inc(seqi iter)
{
    ++iter->offset;
    if (iter->offset >= iter->length) {
        seq_update(iter);
    }
}

static inline void
seq_dec(seqi iter)
{
    --iter->offset;
    if (iter->offset<0) {
        seq_update(iter);
    }
}

static inline bool
seq_isvalid(seqi iter)
{
    return iter->begin != 0;
}

static inline void*
seq_read(seqi iter)
{
    return *(iter->begin + iter->offset);
}

static inline void*
seq_write(seqi iter, void *v)
{
    *(iter->begin + iter->offset) = v;
    return v;
}

使用起来比较方便，看起来就是一个 for 循环，而且在性能上也非常接近原生数组：

seqi iter;
for (seq_head(s,iter);seq_isvalid(iter);seq_inc(iter)) {
    printf("%p\n",seq_read(iter));
}

一个简化设计的约定是，一旦一个 seqi 变得无效（比如迭代到 seq 一端，或是引用的数据被 pop 出去），那么永远就不可能再使它有效。我就可以简单的在 seqi 中标记出这种情况（使用 seq_close 把 begin 字段置空，且在 seq 内部注销）

我们同时保有的 seq 迭代器不会太多，在 seq 结构中开辟有限空间存放引用即可。

剩下的一些 api 列在下面：

struct seq * seq_create(int hint);
void seq_release(struct seq *s);
void seq_pushhead(struct seq *s, void *v);
void seq_pushtail(struct seq *s, void *v);
bool seq_empty(struct seq *s);
void* seq_pophead(struct seq *s);
void* seq_poptail(struct seq *s);
void seq_clear(struct seq *s);
int seq_size(struct seq *s);

主要就是用来从两端压入和弹出数据的，或者清空整个结构（同时注销所有正在使用的 seqi ）。对于 release 方法，除了使用相关内存外，还可以附带检查所有迭代器使用注销。这可以帮助派错。我觉得，约定所有的迭代行为都比较进行完整（从一端都另一端）是比较合理的。实在要破坏这个约定，可以自己调用 seq_close 方法。

seq 的实现要点还在于，在迭代过程中，向两端的任意一边压如数据要保证安全。否则就没什么实用价值了。

还可以考虑的功能是对 seq 进行排序以及二分查找。

嗯，实现代码不难写，就不列出了。不过想实现的高效还是挺麻烦的，也容易写错。优化是万恶之源啊。

这两天，我们办公室里讨论 google 的新语言相当热闹，不过我还没有想好该写点什么。我们创建了一个 wave(不再提供链接，昨天有人放了个 twitter 机器人把帖子弄坏了，投票丢了:( ) 来讨论这它。悲剧的是 Go 的官网 http://golang.org 被墙了 :( 。

暂时看来 Go 还是一个实验性的语言，不过它满足了我对系统编程语言几乎所有的梦想：快速编译，可链接，Coroutine、Closure （这两个东西是用 Goroutine 实现的），静态类型，鸭子类型，原生的 string 、map 类型，完善的包依赖机制，gc …… 并没有特别花哨多余的东西。Ken Thompson 大神和 Rob Pike 大神杵在那里，绝对是品质保证啊。

好吧，还说漏了一个优点：不支持 Windows 。

Posted by 云风 at 11:26 PM | Permalink | Comments (22)

最近几天，我的几台台式机的 Ubuntu 都顺利从 9.04 升到了9.10 。在这里继续表扬一下网易以及负责的同事，mirrors.163.com 的源在我们这里相当快，可以轻松达到办公室的出口带宽峰值（1MB/s）。这样，升级的时间长短就取决于 cpu 的速度了。

周末，我计划有两件事。

其一，有个程序想写；其二，升级我的本的 Ubuntu 系统。

昨天犹豫了一下，做了个正确的决定。先把想写的程序写完，今天再来折腾本本。果然，这是个明智的决定。否则，一天若是搞不定，会坏了心情，程序就没得写了。

担心的事情终归是要发生的。我的预感没错，这次升级又折腾了我一把。记录下来，有 sony vaio p 的用户搜到这里，希望我的记录可以给你们帮助。

vaio p 的显卡需要单独安装 psb 驱动，否则用不了硬件加速。这点，我在上次装机 就经历过了。既然 psb 驱动一直没有合到 ubuntu 的官方源，我预感这次也不会顺利。

事情比我想的更糟，这次驱动都起不起来了。屏幕一直在 console 模式下闪。

用修复模式进去，一开始没看出什么问题。一筹莫展的时候，肚子饿了。背上本出去觅食。在点完餐等待的过程中，我反复启动了几次看 log 也没发现什么地方不对。后来，手动 startx 了一下，发现一些异常。然后自己检查了一下 /etc/X11/xorg.conf ，发现不知道为啥，屏幕分辨率被改成了 1600 1536 。修改成标准的 1600 768 ，重新启动，成功进入系统。

不过这时还没有正确安装显卡驱动（旧版本已被卸载），速度巨慢。老的驱动暂时没更新到 9.10 。所以得另外寻找方案。

经过我亲身体验，HardwareSupportComponentsVideoCardsPoulsbo 这个方案是可行的。

不过不需要自己手工去打那个 lucazade 的那个 patch 。

再加一个 lucazade 提供的源，然后用 apt-get 打 patch 就好了。参考这个帖子即可： New GMA 500 Poulsbo drivers for the Ubuntu 9.10 Karmic Koala

btw, Ubuntu 9.10 比 9.04 漂亮多了 :) 不过 9.10 下 vaio p 的 micphone 依然不能正常工作 :(

Posted by 云风 at 09:37 PM | Permalink | Comments (14) | TrackBacks (1)

几个月前， Mike Pall 就在 lua 的 mailling list 里叫嚣他的 luajit 2.0 用的新算法将会大幅度提升性能。还记得 Soloist 同学当初就是眉飞色舞的跟我说这个事。所以 luajit 2.0 还真是万众期待啊。至少 lua 社区的人都等着呢。

昨晚，Mike Pall 同学终于放出了 beta 版。那个性能测试结果真是很吓人啊。

ps. 我昨天刚把项目里的几个命令行工具用 lua 改写，并把 srlua 加到了 makefile 框架里。嗯，可以考虑做一个带 jit 的 srlua 。

Posted by 云风 at 06:13 PM | Permalink | Comments (9)