使用 Perl6 Grammars 解压缩 Zelda 3 GFX

grammars

Grammar 结合 actions 可以解析字符串并从字符串中产生一些东西。如果说任何压缩后的数据遵循可能由相应的解压缩算法“解析”的结构,那就不足为奇了。

那么为什么不使用 Perl 6 Grammar 进行这类工作呢?特别是我熟悉的压缩。

深入研究任天堂压缩

任天堂在他们的 SNES 游戏中使用了相同的基本压缩格式,并根据游戏使用了一些变体。这非常简单,在 ~2Mhz 的 SNES CPU 上很容易。

它是这样的:

1
2
3
4
5
6
<a byte that contains an header>
the header is split into 2 parts :
the 3 left most bits form a command number
The 5 other bits code the lenght associated with the command
<An arbitrary number of bytes associated with the command>
<repeat until the header is \xFF>

命令取决于游戏,但是 Zelda 3 的命令非常简单

  • 0 复制:基本上是无压缩命令:复制以下字节
  • 1 字节重复:重复以下字节 length 次
  • 2 单词重复:重复以下单词(SNES为2个字节)length/2 次
  • 3 字节增量:重复相同的字节 length 次,但也增加它
  • 4 重复现有:从给定的偏移量(2字节)复制已经未压缩的数据

其他游戏添加了变体,如最后一个,但对数据执行 OR/XOR/AND。

Grammar

当我向你展示压缩时,它很容易转换为这种 grammar

1
2
3
4
5
6
7
TOP : <chunk>+? <end>
end : \xFF
chunk : <header> <data>
header : <command> <lenght>
command : 0 | 1 | 2 | 3 | 4
lenght : \d
data : ???

这有一些问题:

  • data 的大小取决于 command 和 length
  • 如何在首部的位级工作
  • 为了更有趣一点,如果 command 是 7,header 是2个字节(更长的长度)
  • Perl 6 Grammar 适用于字符串而非二进制数据

使用二进制数据

由于 Grammar 并不真正支持纯二进制数据,因此你必须将最初存储在 buf 中的数据作为 latin1 编码字符串传递。与 MyGrammar.parse($buf.decode("latin1")) 一样,你可以通过对字符串的字符执行 .ord 来访问 ‘byte’ 的值。

验证 header 格式

Grammars 是使用正则表达式创建的,因此我们需要查看是否可以将值与条件匹配。这很简单,你在匹配后添加 <?{ some condition }>,发生匹配就检查条件是否成立。

1
2
3
token normal-header {
<mheader> . <?{ $/.ord < 0b11100000}>
}

扩展的 header 有点冗长

1
2
3
token extended-header {
$<mheader> = . ** 2 <?{ ($/.comb[0].ord +& 0b11100000) == 0b11100000 }>
}

你可以注意到我没有验证这两个 token 中的可能命令,稍后会完成。

给 ast 添加值

可以使用 {} 在 token 中添加代码,例如你可以添加 { say "I am in token foo" } 进行某种调试(但使用适当的模块)。你也可以用这个给 ast 添加值。这部分解决了解析数据的问题,因为我们需要捕获 command 和 length 才能正确验证 data token。

1
2
3
4
5
6
7
token normal-header {
$<mheader> = . <?{ $/.ord < 0b11100000 }>
{ make {
cmd => Command($<mheader>.ord +> 5),
lenght => $<mheader>.ord +& 0b00011111 + 1;
} }
}

make 将哈希中的2个条目添加到 normal-header token 中。我为命令定义了一个枚举,使它们更具可读性。你可以注意到我给 length 加1,因为0是1。

然后,你还需要将这些添加的条目填充到 header token 中,因为我们将在 chunk token 中使用它们。

1
2
3
4
5
token header { 
[ <normal-header> | <extended-header> ]
{ make ($<normal-header> // $<extended-header> ).ast
}
}

Grammar 允许我们使用这种语法 <token(arguments)> 将参数传递给 token 。我们的 chunk token 看起来像这样。

1
2
3
4
5
token chunk {
<header>
{}
<data(|$<header>.ast<cmd lenght>)>
}

空的 {}是需要的,否则,ast 显然不会刷新。

验证命令

由于我们可以使用关键字 multi 像类中的方法一样重载 token ,我们只需要为每个命令生成一个以类似方式工作的 data token 。

1
2
3
4
5
6
7
8
9
multi token data(CMD_Copy, $lenght) {
. ** {$lenght}
}
multi token data($cmd where $cmd == CMD_ByteRepeat | CMD_ByteInc, $lenght) {
.
}
multi token data($cmd where $cmd == CMD_WordRepeat | CMD_CopyExisting, $lenght) {
. ** 2
}

测试

我已经为我的C实现编写了一些测试(你可以在https://github.com/Skarsnik/sneshacking/tree/master/src找到它们)。我尝试了其中一些,但这里是一个使用当前 grammar 运行的例子。

1
2
my $buf = buf8.new(BUILD_SHEADER(CMD_ByteRepeat, 3), 42, BUILD_SHEADER(CMD_Copy, 4), 1, 2, 3, 4, BUILD_SHEADER(CMD_WordRepeat, 2), 11, 22, 0xFF);
say AlttpDecompression.parse($buf.decode("latin1"));

这输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
「"*Aÿ」
chunk => 「"*」
header => 「"」
normal-header => 「"」
mheader => 「"」
data => 「*」
chunk => 「」
header => 「」
normal-header => 「」
mheader => 「」
data => 「」
chunk => 「A 」
header => 「A」
normal-header => 「A」
mheader => 「A」
data => 「 」
stop => 「ÿ」

除了查看 token 是否被正确解析之外,这不是很有用,所以我在 chunk token 的末尾添加了 {say $<header>.ast<cmd lenght>, $<data>.Str.chars}

1
2
3
(CMD_ByteRepeat 3)1
(CMD_Copy 4)4
(CMD_WordRepeat 2)2

解压缩数据

现在我们有一个可以验证 Zelda 3 压缩数据的 grammar,让我们继续解压缩它们,因为它只是验证数据并不是真的有用。

我们可能已经使用 {} 和 make 块在 grammar 中完成了这个,我选择使用 Action。 Action 很容易实现,你只需使用 grammar 中 token 命名的方法创建一个类。我们不需要为每个 token 都搞一个方法,在我们的例子中,只有 ‘chunk’ token 是我们感兴趣的,因为它包含构建解压缩数据的所有信息。

由于我不确定你应该如何返回除了带有 action 的修改过的 ast 之外的其他东西,我只是添加了一个 result 属性并将一个实例化的 Action 传递给 grammar 而不仅仅是类。

1
2
3
4
5
class DecompressAction {
has buf8 $.result .= new;
method chunk($/) {
self.process-cmd($/<header>.ast<cmd>, $/<header>.ast<lenght>, $/<data>.Str.encode("latin1"));
}

然后每个 process-cmd multi 方法将数据构建到 result 中。

拷贝非常简单。

1
2
3
multi method process-cmd(CMD_Copy, $lenght, $data) {
$!result.append($data)
}
1
2
3
multi method process-cmd(CMD_CopyExisting, $lenght, $data) {
$!result.append($!result.subbuf($data.read-uint16(0, LittleEndian), $lenght))
}

这是一个更有趣的因为如果我们想要解压缩地图数据,我们只需要更改用于解码偏移的字节序而不改变解压缩的其余部分。 (并且,是的,ROM 上有相同的解压缩程序的2个副本,只有2个指令已更改…)

让我们尝试使用之前展示的压缩字符串。

1
2
3
4
my $buf = buf8.new(BUILD_SHEADER(CMD_ByteRepeat, 3), 42, BUILD_SHEADER(CMD_Copy, 4), 1, 2, 3, 4, BUILD_SHEADER(CMD_WordRepeat, 2), 11, 22, 0xFF);
my $data = AlttpDecompression.parse($buf.decode("latin1"), :actions(DecompressAction.new)).actions.result;
my $testdata = buf8.new(42, 42, 42, 1, 2, 3, 4, 11, 22);
say $data eq $testdata;

我添加了一些调试,以便我们可以看到它如何流动

1
2
3
4
5
6
7
8
9
10
11
12
13
skarsnik@DESKTOP-UIA12T1:/mnt/f/Project/Perl6/grammar$ perl6 alttpcompression.p6
To decompress : Buf[uint8]:0x<22 2a 03 01 02 03 04 41 0b 16 ff>
Decompressed : Buf[uint8]:0x<2a 2a 2a 01 02 03 04 0b 16>
(CMD_ByteRepeat 3)1
Chunk : CMD_ByteRepeat 3 : Blob[uint8]:0x<2a>
$.result : Buf[uint8]:0x<2a 2a 2a>
(CMD_Copy 4)4
Chunk : CMD_Copy 4 : Blob[uint8]:0x<01 02 03 04>
$.result : Buf[uint8]:0x<2a 2a 2a 01 02 03 04>
(CMD_WordRepeat 2)2
Chunk : CMD_WordRepeat 2 : Blob[uint8]:0x<0b 16>
$.result : Buf[uint8]:0x<2a 2a 2a 01 02 03 04 0b 16>
True

真实数据

使用精心设计的数据进行测试很不错,但让我们看看这种解压缩如何与真实游戏数据一起执行。我已经有一个工具从ROM文件中提取和注入包含此压缩的GFX。通常你应该看一张表,告诉你GFX(tileset)的每个部分在rom中的位置(使用SNES地址,而不是文件地址),但为了简单起见,我将从已知位置获取数据。这是tileset,用于一些Link动作和他的盾牌。

img [at 0xc0d64, 3bpp]

这是真正的规模和假灰色调色板。压缩数据位于0xC0D64 + 0x200(某些ROM文件有一个特殊的首部),并且是1500字节。大小应该无关紧要,因为我们有办法知道压缩字符串的结尾,但 grammar 不会验证。

这是打开此脚本生成的输出时,我的工具中的结果。它和以前完全一样,所以我猜它是成功的:)

img

结论

是的,你可以使用 Perl 6 grammar 解析二进制格式,但是你可以看到访问原始二进制数据的大量解决方法。这是一个有趣的迷你项目,它让我修复了与SNES GFX一起使用的工具上的一些错误(打开独立的 gfx 文件很糟糕)

但是,如果我必须在 Perl 6 中编写更多与 snes 相关的软件,我可能会将我已经在 C 中编写的内容与 NativeCall 绑定,因为它已经经过了很好的测试。

你可以在 https://gist.github.com/Skarsnik/b2850dbebabeb4c539444598419d0248 找到整个代码。

用于查看 GFX 的工具可以在SNESTilesKitten找到。