分类目录归档:Rust

OpenPAL3:做一个开源版本的仙剑三

《仙剑奇侠传三》是我小时候最喜欢的游戏之一了(另一个是《新剑侠情缘》),沉迷神鬼妖怪世界无法自拔,只有发烧卧床不起才能阻挡我玩游戏的热情。ummm 当时发烧算是原因之一吧,另一个重要原因是玩到锁妖塔四层过不去了_(:з」∠)_

前一阵大概是因为偶然刷到 OpenDiablo2 让我突然想到,为什么不来做一个 OpenPAL3 呢?让自己喜欢的游戏重新活一次,也是很有意思的一件事。如果顺利的话,说不定还能扩展一点私货,比如做个战棋战斗模式?不过这都是后话了,得先把基本的原始游戏功能做出来才行。

所以我就踏上了收集当前前沿科技进展的旅途。首先发现的是 @zhangboyang/PAL3patch 这个仓库,虽然名字叫仙剑三分辨率补丁,其实还包含了相当多的其他功能。最关键的是,这里提供了一个便捷的脱壳工具,为我们分析程序扫除了障碍,可行度++。

另外一个值得一提地方是仙剑三高难度贴吧。贴吧不愧是互联网中文社区的扛把子,这个高难度吧里面聚集了很多做仙剑三 mod 的神犇,全都是人肉编辑二进制的资源文件,拷来改去还能不出错。贴吧里有一些分析目录结构的帖子,是入门上手的好地方。还有一些关于游戏机制和数值的分析,但对文件格式的解析比较少见。

另外还搜罗到几篇零散的文章,其中一个是看雪论坛的一篇帖子,分析了仙剑三剧情文件的格式以及压缩包的压缩格式。另一个是一个转贴,原博客已经年久失修找不到了,这个帖子简单分析了仙剑三的一种模型文件的格式,不过尚不全面。最后一个是开源的仙剑三解包工具,实际试用一下,还有一些 Bug,解压出来的文件可能会有不正确的地方。

最后的最后,是藏在仙剑三游戏资源里面的意外惊喜。解包出来的文件当中,有个别文件是游戏开发过程中误打包进来的,比如剧情脚本的源代码(一种非常简单的类似于汇编的语言),还有少许说明性的文本文件,不过提供的信息并不是很多。

这些就是目前巨人肩膀的高度了,剩下的就得靠自己了。首先是先定一个小目标,否则步子太大容易扯到蛋:目标就定为能够播放游戏开头景天跟雪见登场的那一小段剧情好了。

为了实现这个目标,我们得需要:

  • 本着自娱自乐的原则,引擎肯定是要自撸的,所以至少得有一个能凑活用的引擎
  • 模型文件格式的解析,能加载模型是最基本的要求了
  • 场景文件格式的解析,得能把景天的小屋子搭出来
  • 剧情脚本文件可以暂时不用完全读出来,毕竟那一小段剧情不长,把剧情脚本硬编码一下也是可以的

大概就需要这么多的工作吧,这样就可以实现第一个小目标了。从过年前后开始开工算起,到现在大概做了两个半月了,如果从撸引擎开始算要更早一点——现在我已经完成第一个小目标啦!虽然这篇文章发在四月一号,但这不是愚人节忽悠,不是愚人节忽悠,不是愚人节忽悠!

https://zhuanlan.zhihu.com/p/122532099

各位放心,你们的耳机没有坏,是我还没有加声音;文本框也是临时用 Imgui 默认的框框对付了一下,立绘表情也还没贴,场景的环境光也还没有设置(本来应该是烛光烁烁的夜晚😅)……目前还只是 Demo 的程度,非常多的硬编码,相当多的技术债,还有很多文件格式上的问题没有弄清楚。不过不管怎么说,小目标算是勉强达成了,就把它叫做 v0.1 吧。

在达成小目标期间,也是要做一点辅助工具的,比如模型浏览器:

永安当场景静态模型
景天 – 人物顶点动画

场景浏览器:

渝州西南

那么接下来的第二个小目标的话,就定为能够跑出永安当吧。要达成第二个小目标,需要解决的问题非常多,输入控制、声音、碰撞、事件触发机制还都没做,大概没有几个月搞不定,道阻且长 _(:з」∠)_

仓库在此,欢迎 Star 🧐 https://github.com/dontpanic92/OpenPAL3​

0

Rust 面向对象 FFI

说到 FFI,FFI to C 大概算得上是事实标准了。Rust 也提供了 to C 的 FFI,但如果我们想把 Rust 结构包装成对象提供给其他语言使用,事情就没那么简单了。


一种方法是完全依赖于源语言的对象模型,典型的例子是 SWIG。SWIG 是一个 C/C++ 的 Wrapper Generator,通过 parse C/C++ 头文件、结合不同的后端,可以输出不同语言的绑定。它的思路是比较简单的:C++ 中的成员方法全部包装为 extern C 的普通函数,接收 C++ 对象的指针;目标语言这边的对象只携带一个 C/C++ 对象的指针就可以了。我之前用 SWIG 做过一个 Wrapper,wrap 了 wxWidgets(一个 C++ 库)给 golang 用,比较头疼的是:

  • 内存管理。一般的 C++ 类都不会自带引用计数,这时候怎么处理裸指针就很头疼,每个函数的返回值和参数都需要(人工)分析出对象的所有权是否转移,以便决定需不需要在 Go 这一侧调用 delete。同时,如果所有权在 C++ 一侧,如何判断对象是否已经释放,仍然比较难办。如果 C++ 一侧的库完全使用智能指针还好一些,但这件事情高度自由,不可强求。
  • ABI 问题。上面提到了这种方法依赖于源语言的对象模型;但不仅如此,我们还依赖于编译器所使用的 ABI。例如,如果库是 gcc 编译的,wrapper 也需要是 gcc;甚至 gcc 的 Library ABI 的变化,也会使我们受到影响。
  • SWIG 的前端后端都是在一起的,中间表示就是 AST,除了直接加代码也无法自行扩展。如果要做 wrapper,最好是能够自己控制 wrapper generator。比如,Go 语言不支持重载,那 C++ 的重载怎么办?如果我们想要的与 SWIG 的不同、或是有自己特殊的情况需要处理,就需要自己 fork 了——这时候,所有与后端不相干、但又不得不知道的东西,就会成为负担。
  • (改 SWIG 的那个 Go 后端真的很难受

目前 Rust 似乎还没有 SWIG 这样工具,只找到一个 cbindgen,可以生成 C/C++ 头文件。C++ 头文件的话,比较有特色的是能够支持模板,但 impl 之类的还是无法放进 class 里面去。


另一种方法是,在源语言一侧,先手工包装并导出为一个标准的、跨语言的对象模型。谈到跨语言的对象模型,跟我有过交集的也就两个:一个是 COM,一个是 GObject。

先聊一下 GObject 吧,由于用过 GtkSharp,对 GObject 多少有一些了解。Rust 的 Gtk 绑定 gtk-rs 提供了方便手段,可以让我们在 Rust 里面 subclass GObject 类型,但这还是不满足我们的需求,因为它并不能支持在 Rust 中定义并导出新的类型给其他语言使用。

能够实现这个目的的,是一个叫做 gnome-class 的库。(作者居然是 Gnome 的 Co-Founder 😮)它能够生成 GObject 规则的 C 语言导出函数,同时可以生成 GIR 文件(GObject Introspection Repository)。

GIR 描述了 GObject 的类型,很多动态类型语言都有 gobject-introspection 库的支持,它能够直接读取经过编译后的 GIR(叫做 typelib)。也就是说,只要有了 GIR,理论上不再需要任何的其他步骤就可以在 Python/Ruby/Lua/Javascript 里面使用了我们的库了。

对于静态类型的语言,还是需要有代码生成的步骤的。不过一般来说,只要这门语言有 Gtk3 的绑定,多半都会有代码生成器的,比如 Rust/Haskell/D 之类的语言。

我实际试了一下这个库,目前还远远谈不上可用,但在几经 hack 之后终于能够正常在 Python 里面 Subclass 一个 Rust 的 struct 了:

Rust 一侧,我们需要把 Wrapper 写在一个 macro 里。class/virtual 什么的语法稍稍显得有点奇怪;还有一点点我 hack 的痕迹:

gobject_gen! {
    #[generate("generated/application.rs")]
    #[generate("generated/application.gir")]
    class Application: GObject {
        application: GiApplication,
    }

    impl Application {
        pub fn initialize(&self) {
            self.get_priv().application.0.borrow_mut().callbacks_mut().g_object 
                = <Self as glib::translate::ToGlibPtr<'_, *mut ApplicationFfi,>>::to_glib_none(self).0;
            self.get_priv().application.0.borrow_mut().initialize();
        }

        virtual fn on_updated(&self, _delta_time: i32) {
            println!("in application on_updated");
        }

        pub fn run(&self) {
            self.get_priv().application.0.borrow_mut().run();
        }
    }
}

生成了 GIR 之后,使用 g-ir-compiler 把它编译为 typelib,就可以直接在 Python 里面导入了:

from gi.repository import Application

class App(Application.Application):
    def __init__(self):
        super().__init__()
   
    def do_on_updated(self, delta_time):
        print("delta_time " + str(delta_time))

a = App()
a.initialize()
a.run()

至于 COM,最常见的就是 DirectX 的 API 了。可能大家觉得它是 Windows-Only 的技术,但其实 COM 作为 Object Model 来说仍然是跨平台的。微软自己有一个 com-rs,还有一个支持跨平台的 intercom。大概是因为 COM 全部都是接口导出,要比 GObject 简单一点,所以只需要在 Rust struct 上加一个 Attribute Macro 就可以了。这是一个 intercom 的例子,相比于上面的 gnome-class 简直轻松了一个档次:

pub use intercom::*;

#[com_library(Calculator)]

#[com_class(Calculator)]
struct Calculator {
    value: i32
}

#[com_interface]
impl Calculator {
    pub fn new() -> Calculator { Calculator { value: 0 } }

    pb fn add(&mut self, value: i32) -> ComResult<i32> {
        self.value += value;
        Ok(self.value)
    }
}

还是有不少语言支持 COM 的,至少 .net 上的语言都会比较容易;其他的比如 D 也支持直接与 COM 组件交互。


一大圈下来,似乎导出为 COM 用起来最方便,只是在目标语言一侧支持力度没有 GObject 那么大,也不知道实际用起来有没有坑。FFI 终究是一件很繁琐的事啊😥

0

Brainfuck JIT Compiler in Rust

Hello JIT


JIT不是一个神秘的玩意。

—— Tondbal ik Ni

我们都知道,对于解释型的语言实现来说,性能是大家关注的焦点。比如,这位 Tondbal ik Ni 曾经还说过:

P*没上JIT,慢的一逼!

—— Tondbal ik Ni

似乎这句话总是隐含着另一层意思:实现JIT,难!而当我们再一联想到JVM这种庞然大东西的时候,很自然的就

然而!JIT原理并不复杂,做出一个玩具JIT Compiler更是非常轻松。之所以JVMs那么庞大而复杂,原因之一在于它们做了大大大量的优化工作。

我们今天就要来看看JIT究竟是个什么东西!

Just-in-Time Compiler


JIT Compiler,究其根本还是一个Compiler。一个Ahead-of-Time Compiler的编译过程往往会有这些(既不充分也不必要的)步骤:

  • 词法分析
  • 语法分析
  • 语法制导定义或翻译
  • 中间代码生成
  • 代码优化
  • 目标代码生成

对于解释器来说,往往将编译工作进行到中间某一步后就直接进行解释执行了,并不生成目标代码。而JIT Compiler却是要生成目标代码的,最终执行的是编译好后的Native Code。只不过,它将目标代码生成的部分推迟到了执行期才进行。这样的好处有:

  • 无需重新编译就可以实现跨平台
    参考Java,它将平台差异隔离在了中间代码部分(指Java ByteCode)。
  • 运行时优化
    当年大欢还在用Gentoo的时候曾经开过嘲讽:本地编译,优化开的细,比你Arch强多了(然而后来还是倒戈到了Arch 666666)而一个JIT Compiler不仅知道目标平台的信息,更知道程序的运行时信息,因此往往可以有更多的优化。
  • 解释/编译混合
    这其实也可以看作是一种优化措施,即执行次数多的代码JIT编译后执行,执行次数少的代码解释执行。因为JIT还是需要一步编译的过程,如果代码执行次数少,很可能抵消不了编译过程带来的时间开销。

所以,其实优化是JIT Compiler中相当重要的一部分。如果我们不要优化,那可是简单了很多哟。

Core of JIT


如果你能看懂这段代码,那就说明你已经掌握了JIT的精髓了:

#include <stdio.h> 
#include <string.h>
#include <sys/mman.h> 

char f[] = {0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00, 0xC3}; 

int main(){  
    int a = 5; memcpy(&f[3], &a, 4); 
    char* mem = mmap(NULL, sizeof(f), PROT_WRITE | PROT_EXEC, MAP_ANON | MAP_PRIVATE, -1, 0); 
    memcpy(mem, f, sizeof(f)); 
    printf("%dn", ((int (*)())mem)()); munmap(mem, sizeof(f)); 
    return 0;
 }

其中mmap的作用是申请按照PageSize对齐的内存,并可以修改页面保护属性。

所以一个JIT Compiler编译的主要步骤就是:

  • 申请一块可写、并且将来可以改成可执行的内存。
  • 生成机器代码,写入内存。
  • 修改内存页面属性,Call it!

So easy,下面进入脑残环节。

An interpreter for Brainf*ck


我们将实现一个Brainfuck的解释器,随后再实现一个JIT编译器。之所以选择Brainfuck,自然是因为它相当简单,完全可以当做中间代码进行处理,省去了词法语法分析、中间代码生成等与编译原理直接相关的部分。

解释器写起来就太简单了。Brainfuck预设我们有一块无限大的内存,初值均为0。数据指针指向第一个字节。它支持8种操作:

  • >
    数据指针右移一格
  • <
    数据指针左移一格
  • +
    数据指针指向的内存内容+1
  • -
    数据指针指向的内存内容-1
  • .
    putchar
  • ,
    getchar
  • [
    如果当前内存内容 == 0,则向后跳转至对应的]
  • ]
    如果当前内存内容 != 0,则向前跳转至对应的[

翻译器部分可以作为大一的C语言实验哈哈哈哈

A JIT Compiler for Brainf*ck


如果要手撸JIT Compiler,则需要对目标平台有一定的了解。我们这里的目标平台是x86_64,这个网址 可以在线将汇编生成为x86或x64的机器代码。

第一步:申请PageSize对齐的内存
这一步除了使用mmap,还可以使用posix_memalign。

第二步:生成函数框架
在这里我们将一整个Brainfuck程序编译成一个函数。这个函数接受一个参数,即我们事先申请好的一块内存作为数据区域。对于x64来说,Linux等类Unix系统遵循的调用约定是System V AMD64 ABI,函数的第一个参数由Rdi传递。因此我们生成的函数的开始与结束部分如下:

pub fn compile_and_run(&mut self, code: &str) {  
    self.jit_code.emit_push_r(Reg::Rbp); 
    self.jit_code.emit_mov_rr(Reg::Rbp, Reg::Rsp); 
    self.emit_push_regs(); //Save regs 
    self.jit_code.emit_mov_ri(Reg::Rbx, 0); //Rbx = data_pointer 
    self.jit_code.emit_mov_rr(Reg::Rdx, Reg::Rdi); //Rdx = memory_base 

    //more code here... 

    self.emit_pop_regs(); //Load regs that saved before 
    self.jit_code.emit_mov_rr(Reg::Rsp, Reg::Rbp);
    self.jit_code.emit_pop_r(Reg::Rbp);     self.jit_code.emit_ret(); 
}

上面的代码中,各个emit函数的作用是生成相应的机器代码,放入内存中。例如emit_push_r(Reg::Rbp)将生成机器码0x55,它对应的汇编为push rbp

接下来就是根据Brainfuck各个操作生成机器码了。例如>操作:

self.jit_code.emit_inc_r(Reg::Rbx);  

So easy. 需要额外说明的只有两点:

一是我们可能需要重定位操作。当我们的buffer空间不够的时候,需要对其进行扩大,这样的话我们代码所在的 地址就会变动。而有一些指令(比如Relative跳转、RelativeCall等)它的操作数是当前RIP(即程序计数器PC)与目标地址的 Offset,这就需要当我们最终结束生成这个函数时,再对这些指令的操作数进行计算。

二是对于[操作来说,需要一个patch back的过程。当我们在编译过程中遇到它的时候,我们并不知道跳转的目的地址是哪里。只有在遇到对应的]时,才能更新它的跳转地址。

第三步:Call it!

let mut memory: Vec<u8>= vec![0; 10000];  
let func: extern "C" fn(*mut u8) = unsafe { mem::transmute(self.jit_code.function()) };  
func(memory.as_mut_ptr());  

Performance Comparison


我找了一个用Brainfuck写的Mendelbrot程序进行测试,它会在控制台输出Mendelbrot的ASCII图(大神请受我一拜 )。除了上面自己实现的解释器和JIT编译器外,我还找了一个Brainfuck的编译器bfc进行测试。

测试结果大致如下:

Interpreter: ~1min
JIT: ~4.31s
bfc: ~4.21s

代码请参 https://github.com/dontpanic92/rainfuck

最后,由于将汇编翻译为机器码是一件体力活,我们还可以使用一些现成的工具。例如DynASM,通过预处理的方式将C + ASM混合代码处理为C语言代码(即省去了我们显示emit的部分)。或者,也可以考虑使用LibJIT或LibGCCJIT等库。

Reference


  1. http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html
  2. http://www.hydrocodedesign.com/2014/01/17/jit-just-in-time-compiler-rust/
  3. http://www.jonathanturner.org/2015/12/building-a-simple-jit-in-rust.html
0