GIFのLZWを展開してみます。トリッキーなことをするため、圧縮よりも展開の方が難しいです。

シリーズの記事です。

GIFのバイナリを読んでみた
GIFのLZW圧縮を調べてみた
GIFのLZWを展開してみた ← この記事

テーブルの構築

展開しながらテーブルを作ります。これがなかなかトリッキーで、圧縮のログを見ながら考えます。

圧縮での入力値が展開での出力値となるため、ログから入力値を隠して、出力値からテーブルの値を再現する方法を考えます。

ログから抜粋

Table   Output  Desc.
-----   ------  -----
0x104           - add 'ff ff 28' to table
        0x103   - output code for previous string
                '28' initialize local string
                '28 ff' 0x102 found in table
                '28 ff ff' not found in table
0x105           - add '28 ff ff' to table
        0x102   - output code for previous string

0x103: ff ff と 0x102: 28 ff が定義済みです。0x104: ff ff 28 を求めるには 0x103 に 0x102 の最初の1バイトをくっ付けます。

まとめると次のようになります。Dが確定してからAをテーブルに追加するという処理順です。

A       ← A = B + D[0] テーブルに追加
    B

C       ← 無関係
    D

次のケースはもう少し複雑です。

ログから抜粋

Table   Output  Desc.
-----   ------  -----
0x106           - add 'ff ff ff' to table
        0x103   - output code for previous string
                'ff' initialize local string
                'ff ff' 0x103 found in table
                'ff ff ff' 0x106 found in table
                'ff ff ff ff' not found in table
0x107           - add 'ff ff ff ff' to table
        0x106   - output code for previous string

直前の 0x103 と後続の 0x106 の最初の1バイトから 0x106 を作ろうとしても、そもそも 0x106 が未定義です。しかし A = B + D[0] の関係から 0x106（A）と 0x103（B）の前半は一致するため、0x103 の最初の1バイトで代用できることが分かります。

このことがWikipediaでは結果だけ説明されています。

GIF - Wikipedia

Is incoming code found in table?
YES: add string for local code followed by first byte of string for incoming code
NO: add string for local code followed by copy of its own first byte

コード列からの展開

まずビットストリームから取り出されたコード列からの展開を実装します。

試行錯誤の過程を掲載してもあまり参考にはならないと思うので、完成したコードを説明します。

LZWExtract.fsx

前回の出力結果を入力とします。

let src = [| 0x100; 0x28; 0xff; 0x103; 0x102; 0x103; 0x106; 0x107; 0x101 |]

コマンド類は clr のみ定義して、その他は計算で求めます。

let clr = 0x100

ログを4列で出力します。

入力（圧縮データ）
テーブルに追加したタイミングでインデックスを出力、テーブルに追加したデータは説明に出力
展開結果が確定したタイミングでデータを出力
説明

printfn "Input\tTable\tOutput\tDesc."
printfn "-----\t-----\t------\t-----"

ログ表示用にバイナリを16進数化する関数を定義します。

let hex (bin:byte seq) =
    bin |> Seq.map (sprintf "%02x") |> String.concat " "

展開結果の出力先を定義します。出力するタイミングでログを出力するため、出力用の関数を定義します。

let data = System.Collections.Generic.List<byte>()
let output (vs:byte[]) =
    printfn "\t\t%s" (hex vs)
    data.AddRange vs

テーブルを定義します。テーブルに追加するタイミングでログを出力するため、テーブル追加用の関数を定義します。

let table = System.Collections.Generic.List<byte[]>()
let add codes =
    let n = clr + 2 + table.Count
    printfn "\t0x%03x\t\t%s" n (hex codes)
    table.Add codes

ループで入力データを読みます。終了コードが来れば抜ける必要がありますが、F#にはbreakがないためforでは書けません。そのため再帰関数で実装します。ループのパラメータ（現在位置と直前に出力したデータ）を引数で受け取り、先頭で終了条件を確認します。

let rec extract i prev =
    if i >= src.Length then () else

現在の入力値を読み、ログを出力します。

    let d = src.[i]
    printf "0x%03x" d

clr が来ればテーブルを消去して、再帰呼び出しによりループを次に進めます。直前データもクリアします。

    if d = clr then
        printfn "\t\t\tClear"
        table.Clear()
        extract (i + 1) [||]

終了コードが来れば抜けます。再帰呼び出しをしないことがループから抜けることを意味します。

    elif d = clr + 1 then
        printfn "\t\t\tEnd"

値またはテーブル参照の処理です。出力データを vs に束縛します。値であれば配列で包んで（[|d|]）、テーブル参照であれば中身を取得します。その際に前述のトリッキーなケース（A = D）に該当する条件が table.Count = n です。

    else
        let vs =
            if d < clr then [|byte d|] else
                let n = d - clr - 2
                if n < table.Count then table.[n] else
                    Array.append prev [|prev.[0]|]

データを出力して、直前のデータがあれば（ないのは初回時のみ）テーブルにデータ（B + D[0]）を追加して、ループを次に進めます。<>は不等号、[||]は空の配列です。

        output vs
        if prev <> [||] then
            add (Array.append prev [|vs.[0]|])
        extract (i + 1) vs

再帰関数で定義したループは、初期値を与えて関数を呼び出すことで開始します。入力値の正当性はチェックしていないため、例外ハンドラを書いておきます（エラーを出力するだけですが）。

try extract 0 [||] with e -> printfn "%A" e

動作結果

入力値が圧縮されていて小さいため、圧縮のときよりもステップ数が少ないです。0x103と0x106と0x107が前方参照されているのがトリッキーな点です。

Input	Table	Output	Desc.
-----	-----	------	-----
0x100			Clear
0x028		28
0x0ff		ff
	0x102		28 ff
0x103		ff ff
	0x103		ff ff
0x102		28 ff
	0x104		ff ff 28
0x103		ff ff
	0x105		28 ff ff
0x106		ff ff ff
	0x106		ff ff ff
0x107		ff ff ff ff
	0x107		ff ff ff ff
0x101			End

ビットストリームからの展開

GIFからデータを展開するにはビットストリームからコード列を取り出す必要があります。

完成したコードを説明します。

LZWDecode.fsx

読み込み

バイトストリームから指定したビットずつ読み込むクラスを実装します。

データは255バイトごとのブロックに分割されています。ブロックサイズを先頭バイトから読み込みます。その後のデータはビット単位でのリトルエンディアンのため下位から読み込みます。ブロックの終わりまで到達すれば次のブロックのサイズを取得します。ブロックサイズが0であれば終了します。

※ ビットストリームの中にブロックサイズが割り込む形となります。

open System.IO

type BitReader(s:Stream) =
    let mutable i, max = 0, -1
    let next() =
        if max = 0 then -1 else
        if i >= max then
            i <- 0
            max <- s.ReadByte()
        if max = 0 then -1 else
        i <- i + 1
        s.ReadByte()
    let mutable cur = next()
    let mutable b = 0
    let mutable v = -1
    member x.Value = v
    member x.Read n =
        let rec f v sh n =
            if cur < 0 then -1 else
            let d = cur >>> b
            let left = 8 - b
            if n < left then
                b <- b + n
                v ||| ((d &&& ((1 <<< n) - 1)) <<< sh)
            else
                b <- 0
                cur <- next()
                let v = v ||| (d <<< sh)
                if n = left then v else f v (sh + left) (n - left)
        v <- f 0 0 n
        v >= 0

テスト

Wikipediaに掲載されているサンプルからコード列を取り出してみます。コード長はすべて9bitだと分かっているため決め打ちします。

let src1 = [|
    // block size
    11uy
    // data bytes
    0x00uy; 0x51uy; 0xFCuy; 0x1Buy; 0x28uy; 0x70uy; 0xA0uy; 0xC1uy
    0x83uy; 0x01uy; 0x01uy
    // Block Terminator
    0uy |]

seq {
    use ms = new MemoryStream(src1)
    let br = BitReader(ms)
    while br.Read(9) do yield br.Value }
|> Seq.map (sprintf "%03x")
|> String.concat " "
|> printfn "%s"

実行結果

100 028 0ff 103 102 103 106 107 101

うまく取り出せています。

展開

ビットストリームから展開する際にコード長は可変です。出現する可能性があるコードをすべて格納できるだけのサイズとなるため、最大値は今から追加しようとしているテーブルのインデックスとなります。ただし12ビットの制限があるため、正常なデータであれば制限を超えた所でclrが来てテーブルをクリアします。

先に実装したextractをベースに、BitReaderを使うように手直ししたdecodeを実装します。アルゴリズムは変えないため、動作を信用してログ出力は除去します。

let decode (br:BitReader) (data:List<byte>) lzwMin =
    let table = List<byte[]>()
    let clr = 1 <<< lzwMin
    let rec f blen next prev =
        let i = clr + 2 + table.Count
        if i >= next then f (blen + 1) (next <<< 1) prev
        elif not <| br.Read (min 12 blen) then () else
        let d = br.Value
        if d = clr then
            table.Clear()
            f 1 2 [||]
        elif d = clr + 1 then () else
        let vs =
            if d < clr then [|byte d|] else
                let n = d - clr - 2
                if n < table.Count then table.[n] else
                    Array.append prev [|prev.[0]|]
        data.AddRange vs
        if prev <> [||] then
            table.Add(Array.append prev [|vs.[0]|])
        f blen next vs
    f 1 2 [||]

テスト

テスト用に画像のサイズと最短ビット長と圧縮データを渡して展開結果を表示する関数を実装します。

let test w h lzwMin f (src:byte[]) =
    use ms = new MemoryStream(src)
    let data = List<byte>()
    decode (BitReader(ms)) data lzwMin
    printfn "%d * %d = %d (%d)" w h (w * h) data.Count
    let mutable en = data.GetEnumerator()
    for y = 0 to h - 1 do
        for x = 0 to w - 1 do
            if en.MoveNext() then
                printf "%s" (f en.Current)
        printfn ""

Wikipediaのデータを展開すると、うまく画像の形が取り出せました。

test 3 5 8 (sprintf "%02x ") src1

実行結果

3 * 5 = 15 (15)
28 ff ff 
ff 28 ff 
ff ff ff 
ff ff ff 
ff ff ff

GIFのバイナリを読んでみたで使用した画像の圧縮データを読み込んでみます。

test 16 16 2 (fun b -> string "#* ?".[int b]) [|
    0x2Buy  // block size
            // data bytes
    0x94uy; 0x8Fuy; 0xA9uy; 0x16uy; 0xB0uy; 0x0Buy; 0x42uy; 0x78uy
    0xC8uy; 0x09uy; 0x4Buy; 0xB1uy; 0xA4uy; 0xFBuy; 0x60uy; 0xF5uy
    0x5Duy; 0x4Fuy; 0x28uy; 0x74uy; 0x47uy; 0x03uy; 0xA4uy; 0x91uy
    0x07uy; 0x22uy; 0x92uy; 0x14uy; 0xBDuy; 0xE5uy; 0xB4uy; 0x98uy
    0x62uy; 0x56uy; 0x51uy; 0xF7uy; 0xACuy; 0xDBuy; 0xFAuy; 0xFEuy
    0x43uy; 0x14uy; 0x00uy
    0uy |]  // Block Terminator

実行結果

16 * 16 = 256 (256)
                
       *#       
       #**      
      #  #      
     #   **     
    **    #     
    #     #     
   #      **    
 *#####*   #    
  #    ****#****
 **        **   
 #          #   
 #          #   
**          **  
             #

元画像

きちんと形が取り出せていることが分かります。

GIFファイルからの展開

ヘッダやカラーパレットを読み込めばGIFファイルから画像が得られます。

完成したコードを説明します。

GIFDecode.fsx

ヘッダ

BinaryReader を使用します。

let decodeGIF (s:Stream) =
    use br = new BinaryReader(s, Encoding.ASCII)

シグネチャとバージョンを確認します。

データ

    // 17. Header.
    'G'B; 'I'B; 'F'B  // Signature
    '8'B; '7'B; 'a'B  // Version

読み込み

    match String(br.ReadChars 6) with
    | "GIF87a" | "GIF89a" -> ()
    | _ -> failwith "not gif file"

サイズを読み込みます。

データ

    // 18. Logical Screen Descriptor.
    16uy; 0uy  // Logical Screen Width
    16uy; 0uy  // Logical Screen Height

読み込み

    let width  = br.ReadUInt16() |> int
    let height = br.ReadUInt16() |> int

フラグを読み込みます。

データ

    0xA1uy     // <Packed Fields>
               //   Global Color Table Flag
               //   | Color Resolution
               //   | |   Sort Flag
               //   | |   | Size of Global Color Table
               //   1 010 0 001

読み込み

    let b = br.ReadByte() |> int
    let hasGCT  = (b &&& 0x80) <> 0
    let colRes  = (b >>> 4) &&& 7
    let sorted  = (b &&& 8) <> 0
    let sizeGCT =  b &&& 7

この要領でカラーパレットなども読み込んで、展開したインデックスデータをRGB値に変換すれば、画像が得られます。

実行結果

標準画像Lennaを256色に減色したGIFを用意します。

この記事で作ったデコーダーで読み込んで表示します。

[<EntryPoint; STAThread>] do
let f = new Form(Text = "GIF")
let p = new PictureBox(Dock = DockStyle.Fill,
                       SizeMode = PictureBoxSizeMode.CenterImage)
f.Controls.Add p
f.Load.Add <| fun _ ->
    use fs = new FileStream("Lenna.gif", FileMode.Open)
    let bmp = decodeGIF fs
    f.ClientSize <- bmp.Size
    p.Image <- bmp
Application.EnableVisualStyles()
Application.Run f

うまく表示できました。

アニメーションに対応するにはまだ作業が必要ですが、今回は実装を見送ります。