바이트 스트림에 포함 된 수축 바이트 시퀀스를 통과하는 방법?

Question

나는 각 섹션이 압축 된 바이트 스트림과 함께 헤더로 구성된 섹션들의 연결 인 바이트 스트림을 가지고있다.

이 바이트 스트림 섹션을 분할해야하지만 헤더에는 압축되지 않은 형식의 데이터에 대한 정보 만 포함되어 있으므로 압축 된 데이터 길이에 대한 힌트가 없으므로 스트림에서 제대로 진행하고 다음 섹션을 구문 분석 할 수 있습니다.

지금까지 내가 deflated byte sequece를 지나서 진행하는 유일한 방법은 this specification에 따라 해석하는 것입니다. 사양을 읽음으로써 내가 이해 한 것으로부터, 수축 된 흐름은 압축 된 블록 또는 리터럴 블록이 될 수있는 블록으로 구성됩니다.

리터럴 블록에는 쉽게 지나칠 수있는 크기 헤더가 있습니다.

압축 된 블록은 '접두사 코드'로 구성되며, 이는 가변 길이의 비트 시퀀스로, 수축 알고리즘과 특별한 의미가 있습니다. 나는 압축 된 스트림의 길이를 알아내는 것에 만 관심이 있기 때문에 찾아야 할 유일한 코드는 사양에 따라 블록의 끝을 알리는 '0000000'입니다.

:

은 그래서 폐의 스트림 (내가 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 

가 나는 간단한 모카 테스트 케이스를 작성, 확인하려면 구문 분석이 커피 스크립트 기능을 함께했다

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

수축 된 스트림 또는 심지어 수축 된 블록의 끝을 찾는 유일한 방법은 포함 된 모든 허프만 코드를 디코딩하는 것입니다. 스트림에서 더 일찍 표시 할 수없는 검색 할 수있는 비트 패턴이 없습니다.