Zip에 사용된 Deflate Compressed Data Format 의 세부 사항

프로젝트 시작후 개인적인 관심 사항을 남는 시간에 짬짬히 개발을 하자니 예상 보다 시간이 많이 소모 되네요.

이글 Zip에서 사용중인 알고리즘 중 Deflate Compressed 된, 압축 푸는것에 관한 글을 기술 하고 있습니다.

먼저 작성한 글(http://free1234.tistory.com/entry/압축-풀때-사용되는-Deflate-알고리즘)에서 Fixed Hoffman Tree 로 압축된 Data를 어떻게 푸는가에 관해 포괄적으로 기술 하였습니다.

이제 어느 정도 세부적으로 설명을 드려야 할꺼 같습니다.

일단 Fixed Hoffman은 Fixed 된 Tree를 사용 합니다.

여기서 Tree는 간단하게 배열로 구성 되어 있으며, Compressed된 파일을 bit & Shift 연산을 통해서 얻어진 값을 얻습니다.

Tree 배열에 위에 얻어진 값을 통해 실제 reserved 된 값을 얻은후 비트 연산을 통해서 ASCII 코드를 얻게 됩니다.

순서 
1 - 처음 3 비트를 읽어서 간략한 정보를 얻습니다. 
2 - 압축된 바이트중 7비트를 읽습니다. (순서는 2진수 계산의 반대 입니다 ex - 3 => 0000 0011(X), 3 => 1100 0000(O) )
3 - 읽은 7비트를 비트 연산을 통해서 int 형으로 return 합니다. 
4 - 리턴된 값을 reserved 된 tree의 배열의 index로 활용 하여 실제 압축 해체시 사용될 값(0-255)을 얻습니다.
5 - 얻은 값을 토대로 조건별 루틴을 통과( 루틴 통과시 추가로 1 비트를 더 읽습니다) 한후 바이트 또는 < Len, Distance > 형태의 값을 얻습니다.





이제 압축된 data를 놓고 이야기 하겠습니다.
Hex editor를 활용하여서 압축된 파일을 열어 보게 되면, 간략한 파일 정보와 파일 이름이 보입니다.
저의 경우 test.txt 파일을 압축 하니, test.txt 다음 바이트 부터 압축된 데이터 이더군요.

압축된 데이터 첫 바이트 중 3 비트는 Last block 정보와 어떤 압축 방식을 사용 하였나를 보여 줍니다. 
제 경우는 75 즉 1101 0010 의 경우 (2진수로 변환후, 비트의 순서를 바꾸지 않고 바로 읽어 들이는 방식)
1 1 0  이렇게 3 비트를 읽습니다.( 순서 1 )

위의 첫번째 비트 1 의 결과 값은 reserve 된 배열을 통해서 얻어진 값 과 비트 연산을 하여서 "1" 이란 값이 나옵니다.
즉 , 현재의 데이터 블럭이 마지막 데이터 블럭이다란 뜻입니다.

그후 두번째, 세번째 비트 1 과 0 을 읽어 들인후 위의 동일한 연산을 하게 되면 "1" 이란 값이 나옵니다.

이것은 현재 Fixed Hoffman Tree 방식을 사용 한다란 뜻이지요.

그후 1 0010 이렇게 5비트를 읽고 더 이상 읽을 비트가 없으니 7비트를 더 읽습니다( 순서 2 )
이렇게 계속 읽은후 순서 3,4,5를 통해서 32k (Slide dictionary) 란 버퍼에 저장이 안된 캐릭터는 바로 출력 시키며,
버퍼에 있는 캐릭터는 <Length , Distance>는 Slide dictionary를 통해서 Length 만큼 반복해서 출력을 하게 됩니다.




그럼 최초 3 비트를 통해서 정보를 얻은 후 7 비트를 읽은 후 압축된 코드가 어떻게 해체가 되나 보여 드리겠습니다.

test.zip

위의 Zip 파일이 제가 테스트 한 파일 이며 안의 바이트 배열을 쭈욱 들여다 보시면 이런 부분이 있습니다.

압축된 파일 이름은 test.txt 이며 안의 내용은

aabbbccccdddd12345612321

위의 한줄로 된 String 입니다.
.....

ReadBlock : 116   offset : 30  BitStart : 0  BitEnd : 30  Char : t
00101110
ReadBlock : 101   offset : 31  BitStart : 0  BitEnd : 31  Char : e
10100110
ReadBlock : 115   offset : 32  BitStart : 0  BitEnd : 32  Char : s
11001110
ReadBlock : 116   offset : 33  BitStart : 0  BitEnd : 33  Char : t
00101110
ReadBlock : 46   offset : 34  BitStart : 0  BitEnd : 34  Char : .
01110100
ReadBlock : 116   offset : 35  BitStart : 0  BitEnd : 35  Char : t
00101110
ReadBlock : 120   offset : 36  BitStart : 0  BitEnd : 36  Char : x
00011110
ReadBlock : 116   offset : 37  BitStart : 0  BitEnd : 37  Char : t
00101110
ReadBlock : 75   offset : 38  BitStart : 0  BitEnd : 38  Char : K
11010010
ReadBlock : 76   offset : 39  BitStart : 0  BitEnd : 39  Char : L
00110010
ReadBlock : 76   offset : 40  BitStart : 0  BitEnd : 40  Char : L
00110010
ReadBlock : 74   offset : 41  BitStart : 0  BitEnd : 41  Char : J
01010010
......

위의 파란 부분은 현재 압축된 파일의 파일 이름이며, 빨간 부분은 압축된 data중 일부 입니다.

110 10010 00110010 00110010 01010010 이 압축 DATA block 의 정보 이며, 처음 3 비트는 간략한 정보 이며 그 뒤의 7비트부터 압축 data입니다.

위의 보라색 7 비트를 연산을 통과 시키면 9 라는 값이 나옵니다 (연산에 관한 알고리즘은 따로 다루겠습니다).

나온 9를 배열을 통해서 보게 되면,  Reserved 된 배열 [9] = 144 란 값이 나오게 되고,  ( 순서 4 )


이후 루틴을 수행 하며 1 비트를 더 읽어 들여서 0 일 경우 와 1 일 경우로 구분이 되는데요.    ( 순서 5 )

0 일 경우 리턴된 값 144 를 사용 하며, 1 일 경우 or 연산을 통해 145를 사용하게 됩니다.

보라색 처음 7 비트 값을 통해서 144가 얻어 지고, 그 후 나온 빨간 색 비트 1 을 이용하여 145란 값이 나오게 됩니다.

그후 145 - 48 연산을 하게 되면 97이 나오고 ASCII 값 97은  "a" 가 되어 압축이 풀리게 됩니다.

다시 뒤에 보라색 7 비트를 연산 하게 되면 9 가 return되고 144 를 얻은후 or연산을 통해 145 가 나옵니다.

145 - 48 은 97로 a 가 나오지요.   그 뒤의 비트  10010 010  이렇게 된 부분은 146 이 나오게 되며 추가 비트가 0 이므로 146 - 48 즉 98이 되어 b가 됩니다.

현재까지는 8비트를 사용하여 알파벳을 하나씩 압축 해제 하므로, 압축률 0% 이네요.


그럼 다시 쭈욱 내려 가서, 원본에 저장된

aabbbccccdddd12345612321

중 반복 되는 cccc 를 찾아 보겠습니다. 

...........
ReadBlock : 74   offset : 43  BitStart : 0  BitEnd : 43  Char : J
010 10010

ReadBlock : 6   offset : 44  BitStart : 0  BitEnd : 44  Char :
01100000

ReadBlock : 130   offset : 45  BitStart : 0  BitEnd : 45  Char : ?
01000001

ReadBlock : 20   offset : 46  BitStart : 0  BitEnd : 46  Char :
00101000

ReadBlock : 32   offset : 47  BitStart : 0  BitEnd : 47  Char : 
00000100

ReadBlock : 48   offset : 48  BitStart : 0  BitEnd : 48  Char : 0
00001100
.........


XXX 10010 01 100000 01000001 00101000 00000100 00001100

위의 비트 스트링중 보라색 처음 7 비트를  연산을 통과 시키면   [73] = 146 이란 값이 나오며 추가 비트가 1 이 므로 147 - 48 = 99 즉 c가 됩니다.

이후 00000 01 이 비트를 통해서 3번 추가로 반복되는 c의 정보를 얻게 됩니다.
00000 01의 경우 연산을 통해 1이 나오게 되며, 다시 257 로 됩니다.

255 까지 ASCII Code 이므로 단순 치환을 하면 되지만, 그 이후의 값은 각 코드가 따로 정해져 있습니다.
256 = EOF
257 은 < Length, Distance > 에서 Length를 의미 합니다.

RFC1951에서 257의 값은 Extra Bit 0 이며, Length 가 3을 의미 합니다.

그래서 이번에는 257 값이 치환된후 ExtraBit을 0 개 읽어 들어서 다음 연산을 수행 하여 Distance를 얻게 됩니다.

Distance를 얻기 위해서는 총 5개의 비트( 00000 )를 읽어 들입니다. 이 값은 연산을 통해서 0 이 나오고 Distance를 제공하는 배열에 [0] = 1 이 되므로 총 1 distance 만큼 Slide dictionary 에서 Backward로 향해서 c를 참조 하게 됩니다.

< Length , Distance > = < 3 , 1 > 이 되는 것이지요. 총 변환을 위해서 읽은 비트는 7 + 1 + 7 + 5 = 20 bits 이지만 12 비트( 32 bits - 20 bits ) 를 줄여서 압축률이 37.5% 정도 됩니다.

표준적으로 나올순 없는 비율 이지만 최대 적은 비트로 압축을 할 경우 (RFC1951 참조)

< 258 , 0 > 가 되어 7 비트를 사용 하여  2064 (258 * 8 ) bits를 대체 할 수 있습니다.


이것으로 ZIP 에서 사용되는 Fixed Hoffman Tree를 사용하여 deflate 하는 방법에 관해서 적어 보았습니다.

다음에는 이 알고리즘에서 사용되는 부수적인 연산 과 Fixed Hoffman Tree 및 Distance 배열 , Length 배열에 사용 하여 어떻게 압축된 코드를 해체 하는지에 관해 글을 적어 보겠습니다.


참고 자료 : zlib 의 open source.