次の実験室作業の一環として、同僚と私は16進ダンプファイルPNGを解析するタスクに直面しました。 RFC 2083標準によれば、PNG形式には、 Deflateアルゴリズムによって圧縮されたピクセルデータが格納されます 。 したがって、ダンプを解析するときは、Inflateアルゴリズムを使用して圧縮データを解凍する必要がありました。
分析は、次の4x4ピクセル画像で実行されます。
Deflate標準RFC 1951を使用して圧縮されたデータストリームは、 RFC 1950標準のzlib形式でPNGに格納されます。この標準を解析に使用します。 zlibヘッダーは、Deflate設定を定義します。 次の構造になっています。
| 1バイト
| 1バイト
| 4バイト
| |||
| CMF
| Flg
| 独裁者
| |||
| 4ビット
| 4ビット
| 2ビット
| 1ビット
| 5ビット
| |
| シンフォ
| SM
| FLEVEL
| フィクション
| Fcheck
| |
フィールドの詳細：
- CMF（圧縮方法とフラグ）。 このバイトは、それぞれ4ビットの2つのセル（CM（圧縮方式）、CINFO（圧縮情報））に分割されます。
- CM（圧縮方式）。 このフィールドは、ファイルで使用される圧縮方法を定義します。 CM = 8は、Deflateが最大32キロバイトのウィンドウサイズで使用されることを意味します。
- CINFO（圧縮情報）。 CM = 8の場合、CINFOは、ウィンドウサイズをマイナス8に設定する2を底とする対数です（CINFO = 7は、ウィンドウサイズを32キロバイトに設定します）。
- FLG（フラグ）。 このバイトは、FCHECK、FDICT、FLEVELの各部分に分割されます。
- FCHECK（CMFおよびFLGのチェックビット）。 式sum =（CMF * 256 + FLG）の値を16ビットの符号なし整数と見なします。 このフィールドはFLGを補完するため、合計は31の倍数になります。
- FDICT（プリセット辞書）。 このフラグが設定されている場合、DICT辞書記述子はFLGバイトの直後に続きます。 アンパッカーはこのフィールドの値を使用して、圧縮中に使用される辞書を判別できます。
- FLEVEL（圧縮レベル）。 このフィールドは、特別な圧縮アルゴリズムによって使用されます。 デフレート（CM = 8）：0-最速の圧縮、1-高速の圧縮、2-デフォルトの圧縮、3-最大の圧縮（最も遅い）。 このフィールドの値は、解凍時に考慮されません。 追加の圧縮が意味があるかどうかを示すために使用されます。
DICTの後に（FDICTがインストールされている場合）、圧縮データのストリームがあり、PNGの長さはIDAT構造体のCHUNK_LENGTHフィールドに依存します。 zlibバッチの最後には、Adler-32アルゴリズムを使用して非圧縮データから計算されたADLER-32チェックサムがあります。
この場合、zlibヘッダーは次のようになります。
| 78 DA
| 0111
| 1000
| 11
| 0
| 11010
|
| ウィンドウサイズ= 32K
| 圧縮方法=収縮
| 圧縮レベル=最速
| 辞書が使用されている= false
| チェックビット
|
ヘッダーから、辞書が使用されていないことがわかります（FDICT = 0）。
画像の圧縮データ：
63 F8 3F 93 E1 3F 03 C3 CC FF 20 1A C8 00 22 24 0E 58 12 85 33 D3 F8 3F 03 32 07 44 03 00 AA 05 23 77
その後、ビットはバイト単位で連続して読み取られます。 バイトでは、最後のビットから最初のビットに移動します（たとえば、データストリームで2バイトが連続して移動する場合：63 F8（0b01100011 0b11111000）。次のビットシーケンスを取得する必要があります：1100011000011111）。
読み取りシーケンスの最初のビットはBFINALフラグで、このデータが最後かどうかを示します。 次の2つのBTYPEビットは、圧縮のタイプを示します。00-圧縮なし、01-固定ハフマンコードによる圧縮、10-動的ハフマンコードによる圧縮、11-値は予約済みです。
固定ハフマンコードの表：
| アンパック値
| ビット数
| コード
| 拠点
|
| 0〜143
| 8
| 00110000から10111111
| 00110000
|
| 144〜255
| 9
| 110010000から111111111
| 110010000
|
| 256〜279
| 7
| 0000000から0010111
| 0000000
|
| 280〜287
| 8
| 11000000から11000111
| 11000000
|
オフセット表：
| コード
| 追加します。 ビット
| 距離
| コード
| 追加します。 ビット
| 距離
| コード
| 追加します。 ビット
| 距離
|
| 0
| 0
| 1
| 10
| 4
| 33〜48
| 20
| 9
| 1025〜1536
|
| 1
| 0
| 2
| 11
| 4
| 49〜64
| 21
| 9
| 1537 2048
|
| 2
| 0
| 3
| 12
| 5
| 65〜96
| 22
| 10
| 2049〜3072
|
| 3
| 0
| 4
| 13
| 5
| 97〜128
| 23
| 10
| 3073〜4096
|
| 4
| 1
| 5、6
| 14
| 6
| 129〜192
| 24
| 11
| 4097-6144
|
| 5
| 1
| 7、8
| 15
| 6
| 193〜256
| 25
| 11
| 6145-8192
|
| 6
| 2
| 9-12
| 16
| 7
| 257〜384
| 26
| 12
| 8193-12288
|
| 7
| 2
| 13〜16
| 17
| 7
| 385〜512
| 27
| 12
| 12289-16384
|
| 8
| 3
| 17-24
| 18
| 8
| 513-768
| 28
| 13
| 16385-24576
|
| 9
| 3
| 25〜32
| 19
| 8
| 769-1024
| 29日
| 13
| 24577-32768
|
長さ表：
| コード
| 追加します。 ビット
| 長さ
| コード
| 追加します。 ビット
| 長さ
| コード
| 追加します。 ビット
| 長さ
|
| 257
| 0
| 3
| 267
| 1
| 15、16
| 277
| 4
| 67〜82
|
| 258
| 0
| 4
| 268
| 1
| 17、18
| 278
| 4
| 83〜98
|
| 259
| 0
| 5
| 269
| 2
| 19〜22
| 279
| 4
| 99〜114
|
| 260
| 0
| 6
| 270
| 2
| 23〜26
| 280
| 4
| 115〜130
|
| 261
| 0
| 7
| 271
| 2
| 27〜30
| 281
| 5
| 131〜162
|
| 262
| 0
| 8
| 272
| 2
| 31〜34
| 282
| 5
| 163〜194
|
| 263
| 0
| 9
| 273
| 3
| 35〜42
| 283
| 5
| 195〜226
|
| 264
| 0
| 10
| 274
| 3
| 43〜50
| 284
| 5
| 227〜257
|
| 265
| 1
| 11、12
| 275
| 3
| 51〜58
| 285
| 0
| 258
|
| 266
| 1
| 13、14
| 276
| 3
| 59〜66
|
|
|
|
展開するとき、データは2つのタイプで表すことができます：固定値と逆バイアスの長さ。
読み取ったデータは、固定値に変換する必要があります。 以下は変換式です。
lit value = data-base + left bound、ここで
点灯値-固定値、
base-表1の列
左境界-表1のアンパックされた値の列の左の数値。
データを読み取るとき、各間隔のプレフィックスが異なるという事実に対応するテーブル1の固定値の間隔を明確に決定できます。
たとえば、シーケンスから2バイトのF8と3Fを選択してみましょう。 000 111111111 1100であることが判明したビットシーケンス。現在の読み取り位置を4とし、7ビット（最小ビット数）を読み取ると、間隔2に対応するプレフィックス1111111が得られます。これから、読み取りコードの長さは9になります。
0b111111111 = 0d511
上記の式を使用すると、エンコードされた数値は255 = 511-400（0b110010000）+ 144であることがわかります。
データストリームに固定値ではなく、長さと逆バイアスに関する情報が含まれている場合、つまり 読み取られた値は3番目の間隔になります。 このバージョンでは、これはサブシーケンスになります。
20 1A C8（ 0000010 0 01011000 00010011）。
間隔3に入る最初の7ビット（0b0000010）を読み取ります。式により、数値に変換します。 これは、257 = 1-0 + 256の数になります。次に、表3を使用します。コード257は、考慮する必要がある追加ビットの数が0であることを示します。3列目の長さは3です。 。 これらのビットは、長さに追加する数値を決定します。
次に、5ビット（0b00101 = 0d5）を読み取り、逆バイアスを決定します。 私たちの場合、これは5です。表2から、追加の1ビットを読み取る必要があることは明らかです。 逆順で読みます。 1（0d1）になりました。 この数値を列3からの最小距離に追加します。そして、逆バイアスは7 + 1 = 8になります。
これはどういう意味ですか？ たとえば、0 255 153 0 255 0 0 153 255の9つの値をカウントしました。戻り距離は、このストリームに戻す必要がある値の数を示します。つまり、 2番目の値-255になります。3に等しい長さは、データストリームから3つの値を取得する必要があることを示しています。 255 1530。長さがオフセットより大きい場合、開始位置に戻り、長さに等しい値の数をカウントするまで元の順序で再度読み取ります。 長さが7で、逆バイアスが2であるとします。2つの値でシフトされます。 最後から2番目の数字の位置は153です。判明したシーケンスは153 255 153 255 153 255 153です。最終的に、アンパッカーはゼロに等しい次の固定値を読み取ると、作業を終了します。
完全なダンプ分析：
| 01100 01 1ファイナルチャンク、固定ハフマン
11111 000 48-48 + 0 = 0-フィルター：なし 0011 1111 511-400 + 144 = 255 100 10011 409-400 + 144 = 153 111 00001 48-48 + 0 = 0 00 111111 511-400 + 144 = 255 00 000011 48-48 + 0 = 0 11 000011 48-48 + 0 = 0 1 1001100 409-400 + 144 = 153 11111111 511-400 + 144 = 255 0 0 100 000 2-0 + 256 = 258長さ= 4 000 1 1010 5距離= 7 + 1 = 8 1100 1000 1-0 + 256 = 257長さ= 3 00000 00 0 6距離= 9 + 0 = 9 0 01000 01 1-0 + 256 = 257長さ= 3、2距離= 3 0 0100100 9-0 + 256 = 265長さ= 11 + 0 = 11 00 00 1110 7距離= 13 + 0 = 13 010 11000 3-0 + 256 = 259長さ= 5 000100 10 9距離= 25 + 4 = 29 100 0 0101 10-0 + 256 = 266長さ= 13 + 0 = 13 0011 00 11 7距離= 13 + 0 = 13 110 10011 409-400 + 144 = 153 111 11000 99-48 + 0 = 51 00 111111 511-400 + 144 = 255 00 000011 48-48 + 0 = 0 00 1 10010 9-0 + 256 = 265長さ= 11 + 1 = 12 000 00 111 7距離= 13 + 0 = 13 0100 0100 2-0 + 256 = 258長さ= 4 000000 1 1 5 DISTANCE = 7 + 1 = 8 0000000 0 0-0 + 256 = 256 END 10101010 ADLER 00000101 ADLER 00100011 ADLER 01110111 ADLER | 0
255153 0 255 0 0 153 255 255153 0 255 255 0 0 255 0 0 0 153 255 255153 0 255 255 0 0 255 255153 0 255 0 255153 0 255 255 0 0 255 255153 0 255 0 153 51 255 0 255 0 0 255 255153 0 255 0 153 51 255 255153 0 255 |
同様の材料の検索は、最終的に標準につながりました。 この記事が、彼らの母国語で理解しやすいロシア語での努力を必要としている人々の助けになることを願っています。
ソース画像