zlib 분석

zlib 분석

H3X0R팀 소속 BoB 6기 ch4n3

---

1. zlib이 사용하는 알고리즘 : DEFLATE 알고리즘

 일단 zlib source를 분석하기 전에 zlib이 사용하는 알고리즘에 대해서 알아둘 필요가 있는 것 같다. 

 zlib은 ZIP 포맷을 사용하기 위해서 만들어졌다는 DEFLATE 알고리즘을 사용한다. 이 알고리즘은 단순하게 ZIP 알고리즘 외에도 PNG, DOCX, PPTX 등의 문서 포맷에서도 사용된다. 

 이 알고리즘을 구현한 소스 중에서, zlib이 가장 유명하다고 한다. 

1.1 zlib 알고리즘의 구성

 zlib알고리즘은 크게 두가지의 알고리즘으로 구성되어 있는데, 첫 번째가 LZ77 알고리즘이고, 두 번째가 Huffman coding 알고리즘이다. 일단 압축할 데이터를 LZ77 알고리즘으로 압축시킨 후에, 다시 허프만 부호화 방식(Huffman coding Algo.)으로 압축한다. 

1.2 LZ77 알고리즘

 일단 내가 이 자료(http://uzys2011.tistory.com/152)의 도움을 많이 받았기에, 먼저 링크를 제공한다. 알고리즘에 대한 설명은 이 링크로써 생략하겠다. 

1.3 Huffman 알고리즘

 이 알고리즘은 최고의 효율을 제공하는 현존 최고의 알고리즘이다. 짧게나마, 이 알고리즘을 설명하자면, 가장 많이 쓰이는 문자에 작은 bit를 할당하고 적게 쓰이는 문자에 큰 bit를 할당하는 것이다. 

======= Example =======

From. http://uzys2011.tistory.com/154

abcacbcdcbcacdcacddd 
라는 문자열을 압축해야 합니다.
총 글자수 20개, 총 20byte입니다.

허프만 압축 알고리즘은 이진트리(binary tree)를 기반으로 합니다.

우선 각 문자당 중복되는 글자수를 세어봅시다.

a : 4
b : 3
c : 8
d : 5

이제 이 값을 가지고 가장 효율적인 트리를 구성해야 합니다.

가장 작은 두 값을 골라냅시다.

a : 4
b : 3

↓

    [7]
     │
┌───┐
[a:4]   [b:3]


다시 가장 작은 두 값을 골라냅시다.

a+b : 7
d : 5

↓

          [12]
           │
     ┌───┐
    [7]        [d:5]
     │
┌───┐
[a:4]   [b:3]


또 골라냅시다.


a+b+d=12
c=8

↓

                 [20]
                  │
            ┌───┐
          [12]        [c:8]
           │
     ┌───┐
    [7]        [d:5]
     │
┌───┐
[a:4]   [b:3]




이제 트리가 완성되었습니다.

각 트리의 가지(edge)에, 왼쪽 가지에는 0, 오른쪽 가지에는 1을 부여합니다.

                 [20]
                  │
           0┌───┐1
          [12]        [c:8]
           │
    0┌───┐1
    [7]        [d:5]
     │
0┌───┐1
[a:4]   [b:3]


상위 노드부터 순차적으로 훑어(-_-)내립니다.


a = 000
b = 001
c = 1
d = 01

이제 되었습니다.
아까의 문자열을 압축합시다.

abcacbcdcbcacdcacddd 
=> 000001100010011011001100010110001010101 

총 47bit = 5byte 7bit.

20byte였던 문자열이 1/4로 줄어들었습니다!

======================

2. zlib 분석

2.1 deflate.h and deflate.c

 그럼 이렇게 알게된 background를 토대로 zlib의 소스를 분석해보도록 하자. 

 내가 찾고 있는 알고리즘이 어떻게 구현되었는지 확인하기 위해서 deflate.c와 deflate.h 를 분석하기 시작했다. 

 deflate.h의 내용이다. 여기서 이런 소스를 이용해서 TREE를 정의하고 있다. 구조체와 union을 이용해서 정의하는데, 나중에 접근하기 편하도록 #define을 이용해서 치환해주고 있다. 구조체를 #define으로 치환해서 programming 하는 방법을 알게 되었다. 이렇게 사용하게 된다면 구조체를 사용하면서 마치 변수의 효과도 같이 줄 수 있을 것 같다. 

 아까 설명했던 Huffman 알고리즘의 구성요소들이 모두 소스에 들어있는 것을 확인했다. 

 deflate.c 에서는 특이점이 존재한다. 거의 모든 요소들을 구조체로 정의하고 매크로 함수에서 구조체를 매개변수로 받아서 처리한다. 이런 코드는 배열을 based로 이용하는 것보다 명확한 코드가 될 것 같고, 매크로 함수들에 통일성이 생겨서 가독성이 늘어날 것 같다. 

visual studio를 안쓰시는 분들을 위해서..

보라색은 모두 전처리기로 선언 || 정의한 것이다. 이렇게 전처리기 매크로 함수에서 구조체를 매개변수로 받고 처리한다. 

내가 웹 쪽을 다른 분야보다 많이 공부했었는데 마치 그누보드의 소스와 굉장히 비슷한 점이 많다고 생각한다. 

[*] 참고 블로그 : http://wooyaggo.tistory.com/95 (허프만 알고리즘) 

: http://uzys2011.tistory.com/154 (허프만 알고리즘)

: http://uzys2011.tistory.com/152 (LZ77 알고리즘)