3

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

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

到目前为止，我发现超越压缩字节序列的唯一方法是根据本规范对其进行解析。根据我阅读规范的理解，deflate 流由块组成，可以是压缩块或文字块。

文字块包含一个大小标头，可用于轻松超越它。

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

所以我想出了这个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()

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

4

1 回答 1

2

找到 deflate 流甚至是 deflate 块结尾的唯一方法是解码其中包含的所有 Huffman 代码。没有您可以搜索的位模式不能出现在流的早期。

于 2013-01-08T14:27:51.320 回答