algorithm - 如何超越字节流中包含的压缩字节序列？

Question

我有一个字节流，它是多个部分的串联，其中每个部分都由一个 header 和一个缩小的字节流组成。

我需要拆分此字节流部分，但 header 仅包含有关未压缩形式的数据的信息，没有有关压缩数据长度的提示，因此我可以在流中正确前进并解析下一部分。

到目前为止，我发现超越压缩字节序列的唯一方法是根据 this specification 解析它。 .根据我阅读规范的理解，deflate 流由 block 组成，这些 block 可以是压缩 block 或文字 block 。

文字 block 包含一个 size header ，可用于轻松前进。

压缩 block 由“前缀码”组成，“前缀码”是可变长度的位序列，对 deflate 算法具有特殊含义。由于我只对找出缩小的流长度感兴趣，我想我需要查找的唯一代码是“0000000”，根据规范，它表示 block 结束。

所以我想出了这个 coffeescript 函数来解析 deflate 流(我正在处理 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()

问题是这个测试失败了，不知道怎么调试。我接受任何指出我在解析算法中遗漏的内容或包含上述函数的任何语言的正确版本的任何答案。

Answer 1

找到压缩流甚至压缩 block 末尾的唯一方法是解码其中包含的所有霍夫曼代码。没有可以搜索的位模式不能出现在流的较早位置。