LZ5仕様メモ

RLEパケット解析コード例

byte1 := input.ReadByte()

value := (byte1 & 0x1F)

count := (byte1 & 0xE0) >> 5

if count == 0 {

     // Long RLE Packetなので、次のバイトが必要

     byte2 := input.ReadByte()

     count = byte2 + 8

}

// 展開

for i := 0; i < count; i++ {

     output = append(output, value)

}

LZ copy

LZのデータは

• 既存データの末尾からnバイト手前に戻ったところから、
• mバイトを末尾以降に連結する

という形式です.

この既存展開済みデータから複製する処理をWikiだとLZ copyって言ってました

やりかた

begin := len(output) - offset

for i := 0; i < length; i++ {

    output = append(output, output[begin + i])

}

上記はGo言語っぽい何か. C言語版は公式Wikiにある('ω')

Short LZ Packet

1バイト、または2バイトで構成されているLZ符号化データ.

データ的には64バイトまでのバイトを256バイト範囲で複製するもので、1バイト目の下位6bitに長さを詰めている.

通常では2バイト目が複製開始位置…なんだけど、この2バイト目がないものが4回に1回ある.

というのも、1バイト目の上位2ビットは余っているわけではなく、4回合わせて8bit=1バイトとなるようにされている. 曰くRecycle bits.

パケット構造

Recycle Bits

Recycle BitsはShort LZ Packetの1バイト目上位2bitの集合で、4回集まると1バイト分のオフセットデータになり、4回目のShort LZ Packetはそのバイトが複製開始位置となる (そのため、4回目のものには2バイト目がない)

このRecycle Bitsは上位から順番に出現するようにできている. つまり、

• 1回目のRecycle Bits = 6, 7bit目
• 2回目のRecycle Bits = 4, 5bit目
• 3回目のRecycle Bits = 2, 3bit目
• 4回目のRecycle Bits = 0, 1bit目

である (Wikiにもそう書いてある)

Long LZ Packet

1024バイト前から最大258バイトを複製するLZ符号パケット.

バイト列構造

バイト列備考 (収まらなかった)

• 相対位置はデコード済みデータの末尾から先頭へ向かう. マイナスですね.
• 相対位置データは -1 されたものがあるので、使うときは +1 のゲタを履かせてあげて
• 複製バイト数のほうは -3 されているので、+3 のゲタを履かせよう

LZ展開コード例

// 先頭バイト

byte1 := input.ReadByte()

if (byte1 & 0x3F) == 0x00 {

    // Long LZ Packet

    byte2 := input.ReadByte()

    byte3 := input.ReadByte()

    offset := ((byte1 & 0xC0) << 2) + (byte2 + 1)

    length := (byte3 + 3)

} else {

    // Short LZ Packet

    length := (byte1 & 0x3F) + 1

    packcnt += 1      // Short LZパケット数

    recycle := (recycle << 2) + ((byte1 & 0xC0) >> 6)   // リサイクルビットを連結

    if packcnt % 4 == 0 {

        // 4回目のShort LZ Packetは次のバイトがなく、recycleを使う

        offset := recycle + 1

        recycle = 0

    } else {

        // 1～3回目のShort LZ Packetは次のバイトを使う

        byte2 := input.ReadByte()

        length := byte2 + 1

    }

}

// 複製する

begin := len(output) - offset

for i := 0; i < length; i++ {

    output = append(output, output[begin + i])

}

LZ展開時の注意

コード例でふつーにappendしてますが、これには理由がちょっとだけありまして.

というのも、LZパケットの性質上

• オフセット + 長さ > 展開済みデータ長

となる場合がありまして。普通にmemcpyとかしようものならバッファオーバーしかねないんですわ.

この、長さ以上の部分にはみ出るというのはつまり、順番に後ろに追加していけば前のバイトが繰り返される、ということです.

(この辺はNomenのソースだと隠れ仕様扱いでした)