焉知非鱼 ❚
Wait the light to fall

使用 Raku Grammars 解压缩 Zelda 3 GFX

— 焉知非鱼

grammars

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

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

深入研究任天堂压缩 #

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

它是这样的：

<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

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个字节（更长的长度）
  • Raku Grammar 适用于字符串而非二进制数据

使用二进制数据 #

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

验证 header 格式 #

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

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

扩展的 header 有点冗长

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

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

给 ast 添加值 #

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

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 中使用它们。

token header { 
    [ <normal-header> | <extended-header> ]
    { make ($<normal-header> // $<extended-header> ).ast 
    }
}

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

token chunk {
        <header> 
        {}
        <data(|$<header>.ast<cmd lenght>)>
}

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

验证命令 #

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

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 运行的例子。

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"));

这输出：

｢"*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}

(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 而不仅仅是类。

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 中。

拷贝非常简单。

multi method process-cmd(CMD_Copy, $lenght, $data) {
    $!result.append($data)
}

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

这是一个更有趣的因为如果我们想要解压缩地图数据，我们只需要更改用于解码偏移的字节序而不改变解压缩的其余部分。 （并且，是的，ROM 上有相同的解压缩程序的2个副本，只有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);
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;

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

skarsnik@DESKTOP-UIA12T1:/mnt/f/Project/Raku/grammar$ raku 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

结论 #

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

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

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

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

⮉
⮋
Back to top
back to top
« 开关 使用rotor操作列表 »