メインコンテンツまでスキップ

10. デコードアルゴリズム (Decoding Algorithm)

10. デコードアルゴリズム (Decoding Algorithm)​

非圧縮データを生成するデコードアルゴリズム (Decoding Algorithm) は次のとおりです:

ウィンドウサイズを読み取る
do
   ISLAST ビットを読み取る
   if ISLAST
      ISLASTEMPTY ビットを読み取る
      if ISLASTEMPTY
         ループから抜ける
   MNIBBLES を読み取る
   if MNIBBLES がゼロ
      予約ビットがゼロであることを確認
      MSKIPLEN を読み取る
      次のバイト境界までのビットをスキップ
      MSKIPLEN バイトをスキップ
      次のメタブロックに続行
   else
      MLEN を読み取る
   if not ISLAST
      ISUNCOMPRESSED ビットを読み取る
      if ISUNCOMPRESSED
         次のバイト境界までのビットをスキップ
         MLEN バイトの圧縮データをリテラルとしてコピー
         次のメタブロックに続行

   3 つのブロックカテゴリそれぞれでループ (i = L, I, D)
      NBLTYPESi を読み取る
      if NBLTYPESi >= 2
         ブロックタイプのプレフィックスコード HTREE_BTYPE_i を読み取る
         ブロックカウントのプレフィックスコード HTREE_BLEN_i を読み取る
         ブロックカウント BLEN_i を読み取る
         ブロックタイプ BTYPE_i を 0 に設定
         最後から 2 番目と最後のブロックタイプを 0 と 1 に初期化
      else
         ブロックタイプ BTYPE_i を 0 に設定
         ブロックカウント BLEN_i を 16777216 に設定
   NPOSTFIX と NDIRECT を読み取る
   リテラルコンテキストモード配列 CMODE[] を読み取る
   NTREESL を読み取る
   if NTREESL >= 2
      リテラルコンテキストマップ CMAPL[] を読み取る
   else
      CMAPL[] をゼロで埋める
   NTREESD を読み取る
   if NTREESD >= 2
      距離コンテキストマップ CMAPD[] を読み取る
   else
      CMAPD[] をゼロで埋める
   リテラルプレフィックスコード配列 HTREEL[] を読み取る
   挿入コピー長プレフィックスコード配列 HTREEI[] を読み取る
   距離プレフィックスコード配列 HTREED[] を読み取る
   do
      if BLEN_I がゼロ
         HTREE_BTYPE_I を使用してブロックタイプを読み取り、BTYPE_I を設定
            前のブロックタイプを保存
         HTREE_BLEN_I を使用してブロックカウントを読み取り、BLEN_I を設定
      BLEN_I をデクリメント
      HTREEI[BTYPE_I] を使用して挿入コピー長シンボルを読み取る
      挿入長 ILEN とコピー長 CLEN を計算
      ILEN の間ループ
         if BLEN_L がゼロ
            HTREE_BTYPE_L を使用してブロックタイプを読み取り、BTYPE_L を設定
               前のブロックタイプを保存
            HTREE_BLEN_L を使用してブロックカウントを読み取り、BLEN_L を設定
         BLEN_L をデクリメント
         コンテキストモード CMODE[BTYPE_L] を検索
         最後の 2 つの非圧縮バイトからコンテキスト ID CIDL を計算
         HTREEL[CMAPL[64*BTYPE_L + CIDL]] を使用してリテラルを読み取る
         リテラルを非圧縮ストリームに書き込む
      if このメタブロックのループで生成された非圧縮バイト数が MLEN なら
         ループから抜ける (この場合、コピー長は無視され、任意の値を
         持つことができます)

      if 挿入コピーコードからの距離コードが暗黙のゼロ
         後方距離を最後の距離に設定
      else
         if BLEN_D がゼロ
            HTREE_BTYPE_D を使用してブロックタイプを読み取り、BTYPE_D を設定
               前のブロックタイプを保存
            HTREE_BLEN_D を使用してブロックカウントを読み取り、BLEN_D を設定
         BLEN_D をデクリメント
         CLEN からコンテキスト ID CIDD を計算
         HTREED[CMAPD[4*BTYPE_D + CIDD]] を使用して距離コードを読み取る
         距離ショートコード置換により距離を計算
         if 距離コードがゼロでなく、
            距離が静的辞書参照でない場合、
            距離を最後の距離のリングバッファにプッシュ
      if 距離が最大許容距離 + 1 未満
         非圧縮データで後方に距離バイト移動し、
         この位置から CLEN バイトを非圧縮ストリームにコピー
      else
         静的辞書単語を検索し、指示に従って単語を変換し、
         結果を非圧縮ストリームにコピー
   while このメタブロックの非圧縮バイト数 < MLEN
while not ISLAST

最後のメタブロックが完了する前にストリームが終了した場合、ストリームは無効として拒否されるべきです。

重複文字列参照は、前のメタブロック内の文字列を参照する場合があることに注意してください。つまり、後方距離は 1 つ以上のメタブロック境界を越える場合があります。ただし、後方コピー距離は、非圧縮ストリームの始まりまたはウィンドウサイズより過去を参照することはありません。そのような距離は、静的辞書単語への参照として解釈されます。また、参照される文字列は現在の位置とオーバーラップする場合があることに注意してください。たとえば、デコードされた最後の 2 バイトの値が X と Y である場合、<length = 5, distance = 2> の文字列参照は、非圧縮ストリームに X,Y,X,Y,X を追加します。

出典 (Source): RFC 7932, Section 10
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

に最終更新