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

シリーズの記事です。

  1. GIFのバイナリを読んでみた
  2. GIFのLZW圧縮を調べてみた
  3. 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 ff0x102: 28 ff が定義済みです。0x104: ff ff 28 を求めるには 0x1030x102 の最初の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

コード列からの展開

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

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

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

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

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

let clr = 0x100

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

  1. 入力(圧縮データ)
  2. テーブルに追加したタイミングでインデックスを出力、テーブルに追加したデータは説明に出力
  3. 展開結果が確定したタイミングでデータを出力
  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

動作結果

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

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からデータを展開するにはビットストリームからコード列を取り出す必要があります。

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

読み込み

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

データは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)

       *#       
       #**      
      #  #      
     #   **     
    **    #     
    #     #     
   #      **    
 *#####*   #    
  #    ****#****
 **        **   
 #          #   
 #          #   
**          **  
             #  

元画像 gif1.gif

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

GIFファイルからの展開

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

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

ヘッダ

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を用意します。

Lenna.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

Lenna.png

うまく表示できました。

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