🦉 👩🏽‍🏫 🍪 GIFデコード 🔩 🏂🏽 ⛓️

前回、JPEGの仕組みを理解しました（ダミーのJPEGデコード）。 GIFが次の形式であったことは論理的です。ところで、それははるかに簡単です。 JPEGとは異なり、1枚の紙のペンのみでデコードできます。最初は、伝統を引き継ぎ、GoogleのGIFファビコンをエンコードしたかったのですが、ファイル全体のデコードプロセスを小さな画像にペイントする方が良いと判断しました。「そして類推によって...」なしで。私は長い間実験をしなければならなかったので、写真は見苦しくなりましたが、勉強するのに非常に視覚的でした。

だから、私たちはこの写真を選びます

。ほら :)それからまた10倍になります：

16進エディタの内部：

見出し

[47 49 46 38 37 61] GIF87a。
GIF89aがある場合があります。これらの形式は、オプションの追加セクションで区別されますが、これらについては考慮しませんが、仕様に記載されています。

セクションは次です

論理画面記述子

画像は論理的な画面に配置され、この画面の左上隅に対して移動できます。表示したすべてのファイルのサイズは画面と同じでした。

[04 00] [04 00] = 4x4（論理画面サイズ）
[91] = 10010001b
(1) =1。グローバルカラーテーブルが使用されます。
(001) =1。カラー解像度。色の数は2 ^{n + 1}で、この場合は4です。
(0) =0。色はソートされません。
(001) =1。カラーチャートのサイズ。 3 * 2 ^{n + 1}バイトかかります。 12。
[00] =0。背景色インデックス。透明性のため。
[00] =0。アスペクト比。（画像の大半はこのバイト0、つまり1：1です。それ以外の場合は、仕様を参照してください）

セクションは次です

グローバルカラーテーブル

12バイトを読み取り、そのようなプレートを形成します。
R G B
[04 02 04] -ほぼ黒（これはそのように決定されたエンコーダです）
[FC FE FC] -ほぼ白色
[FC 02 04] -ほぼ赤
[00 00 00] -この例では使用されていません。

バイト[2C]続いて、セクションが開始したことを意味します

画像記述子[2C]

[00 00] [00 00] =（0、0）。論理画面の左上隅の座標
[04 00] [04 00] = 4x4。画像サイズ
[00] = 00000000。
(0) = 0.ローカルカラーテーブルは使用されません。
(0) = 0.インターレースは使用されません（1の場合、行の順序が変更されます。仕様付録Eを参照）
(0) = 0.ローカルカラーテーブルはソートされません。
(00) = 0.予約済み
(000) = 0. 。ローカルカラーテーブル(000) = 0.色解像度。

さらにファイルには追加のセクションがあるかもしれませんが（定義方法を書いた以下）、それらはありません。エンコードされたデータにほとんど近づき、それらから分離されています。

さらに2バイト

圧縮には、Lempel-Ziv-Welchアルゴリズムが使用されます。以下に、彼の作品を簡単に説明します。

[02]ビット単位のLZWコードの最小長（+1）。
[07]データセクションの長さ。あなたは尋ねる：「どうやって！ 1バイトしかありません。つまり、最大長は255です？」本当ですが、そのようなセクションは無制限です。ファイルがまだ終了していない場合、セクションの終了後、次のセクションの長さのバイトが再び検出されます。コードはこのバイトでカットされる場合があります。次の場所を計算するために、それを覚えておく必要があります。

LZWエンコードされた画像データ。

LZWアルゴリズムには、この初期化された辞書が必要です。テーブルには4つの色があるため、4つの値を追加します（色のインデックスになります）。
0：{0}（黒）
1：{1}（白）
2：{2}（赤）
3：{3}（この例では使用されません）

LZWのgifバージョンの場合、最後にさらに2つの制御コードが追加されます（値は省略でき、場所を予約するだけです）。
4：{クリア}
5：{end}

続けましょう。次の7バイトは[84 62 18 2A 10 5D 00]です。それらをバイナリ表現に変換する必要があります

[84] 10000100
[62] 01100010
[18] 00011000
[2A] 00101010
[10] 00010000
[5D] 01011101
[00] 00000000

これらは、次々と単純に書かれたコードです。しかし、右から左へ！右側の目的のビット数を数えて、この数を取得します。そして、バイトが終わったら、前に部分的に取得した値に、2番目のバイトから（残りのビット数とともに）数を追加します。実際には、より明確になります。
LZWコードのビット単位の最小長は2であることがわかりました。しかし、さらに1を追加する必要があります。 3.これは、現在のコードサイズが3であり、最初は正確に何ビットかを読み取ることを意味します。

アルゴリズムの簡単な説明：

次のコードを読みます。
辞書では、コードに等しい数の下で、インデックスのリストを取得します。これらは事前定義されたカラーインデックスです。
前のステップで辞書から取得されたインデックスのリストが辞書に追加され、現在の段階で辞書から追加された最初のインデックスが追加されます。

(100) 4. .辞書番号4にはコードclearが含まれています。したがって、辞書を初期化し、現在のコードサイズを3に設定します（この例ではもちろん）。大きなファイルでは、このコードは一般的です。
(000) 0. 。ディクショナリの番号0は{0}で、これは既製のカラーインデックスです（左上隅）。辞書には何も追加しません。
(010) 2. .辞書番号2には{2}が含まれています。 {0} + {2} = {0.2}を番号6で追加します（以降、短いエントリを使用します：2：{2}、+ 6：{0.2}）
(001) 1. .辞書番号1には{1}が含まれています。 {2} + {1} = {2,1}を番号7で追加（+7：{2,1}）

辞書が3ビットコードの制限に達しました。現在のコードサイズは1増加します。
(0110) 6: {0,2} +8: {1,0}
(1000) 8: {1,0} +9: {0,2,1}
(0001) 1: {1} +10:{1,0,1}
(1010) 10:{1,0,1} +11:{1,1}
(0010) 2: {2} +12:{1,0,1,2}
(0000) 0: {0} +13:{2,0}
(0001) 1: {1} +14:{0,1}
(1101) 13:{2,0} +15:{1,2}

辞書が4ビットコードの制限に達しました。現在のコードサイズは1増加します（コード長は最大12まで増加します！辞書が4096に達すると、コード長は12のままであり、辞書に何も追加する必要はありません。通常、明確なコードが続きます）
(00101) 5:{end}終了

結果のインデックスを左から右、上から下に書き込みます（4x4画像のサイズが与えられた場合）

写真はすでに推測されています！各インデックスの背後に隠されている色を確認し、画面に表示するために残っていることはすでに明らかです。そして、あと2バイト残っています。
[00]もう一つの終わり。
[3B]まさに終わり:)

拡張機能

画像記述子セクションとLZWエンコードされた画像データの間には、さらにいくつかのセクションを配置できます。アニメーション、解説、アプリケーションデータなどに関する情報があります。それらはマーカーによって決定されます[21] [XX]。説明については、仕様を参照してください。最小限の説明のみを行いましたが、追加セクションの処理は問題ではなく、さらに、ほとんどを安全にスキップできます。

便利なリンク

レンペルのアルゴリズム_ — _ Ziva _ — _ Velcha
グラフィックス交換形式
GIF89a仕様

GIFデコード

見出し