3

セクションの連結であるバイトストリームがあります。各セクションは、ヘッダーと収縮したバイトストリームで構成されています。

このバイトストリームセクションを分割する必要がありますが、ヘッダーには非圧縮形式のデータに関する情報のみが含まれ、圧縮データの長さに関するヒントは含まれていないため、ストリームを適切に進めて次のセクションを解析できます。

これまでのところ、デフレートされたバイトシーケンスを超えて進むことがわかった唯一の方法は、この仕様に従って解析することです。仕様を読んで理解したところによると、デフレートストリームはブロックで構成されており、圧縮ブロックまたはリテラルブロックにすることができます。

リテラルブロックには、それを簡単に通過するために使用できるサイズヘッダーが含まれています。

圧縮されたブロックは、「プレフィックスコード」で構成されます。これは、deflateアルゴリズムにとって特別な意味を持つ可変長のビットシーケンスです。収縮したストリームの長さを調べることだけに興味があるので、探す必要があるコードは「0000000」だけだと思います。これは、仕様によれば、ブロックの終わりを示します。

そこで、deflateストリームを解析するためにこのcoffeescript関数を思いつきました（私はnode.jsで作業しています）

# The job of this function is to return the position
# after the deflate stream contained in 'buffer'. The
# deflated stream begins at 'pos'.
advanceDeflateStream = (buffer, pos) ->
  byteOffset = 0
  finalBlock = false
  while 1
    if byteOffset == 6
      firstTypeBit = 0b00000001 & buffer[pos]
      pos++
      secondTypeBit = 0b10000000 & buffer[pos]
      type = firstTypeBit | (secondTypeBit << 1)
    else
      if byteOffset == 7
        pos++
      type = buffer[pos] & (0b01100000 >>> byteOffset)
    if type == 0
      # Literal block
      # ignore the remaining bits and advance position
      byteOffset = 0
      pos++
      len = buffer.readUInt16LE(pos)
      pos += 2
      lenComplement = buffer.readUInt16LE(pos)
      if (len ^ ~lenComplement)
        throw new Error('Literal block lengh check fail')
      pos += (2 + len) # Advance past literal block
    else if type in [1, 2]
      # huffman block
      # we are only interested in finding the 'block end' marker
      # which is signaled by the bit string 0000000 (256)
      eob = false
      matchedZeros = 0
      while !eob
        byte = buffer[pos]
        for i in [byteOffset..7]
          # loop the remaining bits looking for 7 consecutive zeros
          if (byte ^ (0b10000000 >>> byteOffset)) >>> (7 - byteOffset)
            matchedZeros++
          else
            # reset counter
            matchedZeros = 0
          if matchedZeros == 7
            eob = true
            break
          byteOffset++
        if !eob
          byteOffset = 0
          pos++
    else
      throw new Error('Invalid deflate block')
    finalBlock = buffer[pos] & (0b10000000 >>> byteOffset)
    if finalBlock
      break
  return pos

これが機能するかどうかを確認するために、簡単なmochaテストケースを作成しました。

zlib = require 'zlib'

test 'sample deflate stream', (done) ->
  data = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' # length 30   
  zlib.deflate data, (err, deflated) ->
    # deflated.length == 11
    advanceDeflateStream(deflated, 0).shoudl.eql(11)
    done()

問題は、このテストが失敗し、デバッグ方法がわからないことです。私は、構文解析アルゴリズムで見逃したことを指摘する、または上記の関数の正しいバージョンを任意の言語で含む回答を受け入れます。

4

1 に答える 1

2

deflate ストリームまたは deflate ブロックの最後を見つける唯一の方法は、含まれているすべてのハフマン コードをデコードすることです。ストリームの前に表示されない検索可能なビット パターンはありません。

于 2013-01-08T14:27:51.320 に答える