해동기를 쓴다

요즈음의 몇 이야기는, bytes 처리 이야기의 부품을, 조립하지 않은 채 더해 왔다: ALU용 bitwise 연산자, 마스크가 명세대로 읽히기 위한 hex 리터럴, binary-safe한 파일 reader와 그 쓰는 쪽의 쌍둥이. 각각이 작은 probe에 강제되었고, 각각이 단독으로는 동작했다. 이 Part는, 그것들을 협동시킨 프로그램 —— 진짜 gzip 해동기 —— 이며, dogfood의 상례대로, 나간 용무보다 많은 것을 들고 돌아왔다.

세 block type을 하나의 디코더로

gzip 속의 알고리즘 DEFLATE는 크지 않지만 용서가 없다: 1비트 어긋나면 전 스트림이 노이즈가 되고, 부분점은 없다. 해동기는, 바이트 경계를 넘어 최하위 비트부터 뽑는 bit reader가 필요하다 —— 여기서는 3슬롯 상태 vector(위치·비트버퍼·비트수)를 입력의 int vector 위에 세웠다. 그 위에, 자랑할 만한 부분이 얹힌다: DEFLATE의 세 block type 전부를 처리하는 단일 canonical Huffman 디코더다. stored 블록은 날 바이트. fixed-Huffman 블록은 내장 코드표. dynamic 블록은 자기 코드 길이를, 또 다른 Huffman 코드로 압축해 나른다. 이것을 세 개가 아니라 하나의 디코더로 유지하는 통찰은, fixed의 표는 「특정」 코드 길이 집합에 불과하다는 것 —— 그래서 「길이 배열에서 디코더를 짠다」 「1 심볼을 decode한다」는 같은 함수가 fixed도 dynamic도 동일하게 처리하고, stored는 길이 전치 run을 복사하는 짧은 특례다. 전체는 둘레의 gzip 컨테이너도 읽고(임의의 name / comment / extra 필드를 건너뛰고), trailer의 CRC-32 —— 두 개 전 probe의 체크섬 example에서 그대로 재사용 —— 를 전개 후 출력에 대해 검증한다.

왜 지금 쓸 수 있었나, 그리고 무엇을 끌어냈나

멈춰 설 가치가 있는 것은, 이 프로그램이 일주일 전에는 쓸 수 없었다는 것이다. bit reader는 bitwise 시프트와 마스크를 요한다. 범위표가 hex로 읽히는 것은 hex 리터럴이 있기 때문. 입력이 read_file_bytes 경유로 오는 것은, NUL 종단 문자열이라면 압축 데이터를 첫 제로 바이트에서 truncate하기 때문이고, 출력은 write_file_bytes로 나간다. 각각이 자기 이야기를 가진 별개의 probe였다. 해동기는, 그것들이 드디어 협동해 system의 gzip/gunzip과 악수하는 무언가가 되는 곳이다. 그것들의 출력 —— 1바이트 파일, 1메가바이트 파일, stored도 fixed도 dynamic도 —— 매번 byte 단위로 동일하게 전개한다.

그리고 그다음, dogfood가 하는 일을 했다. 촘촘히 중첩되고, 깊이 재귀하고, capture가 많은 300줄을 쓰는 것은, 어느 테스트보다 훨씬 컴파일러의 closure 기구를 혹사하고, 먼저 세 개의 다른 코드 생성 버그를 끌어냈다 —— 어느 것도, 컴파일러가 emit한 C를 C 컴파일러에 건네야 비로소 나타나는 에러이고, interpreter는 한 번도 밟지 않았다. 그것이 다음 이야기다. 그다음 이야기는, 해동기가 인쇄한, 있을 수 없을 숫자에 대한 것이다: 1메가바이트를 전개하는 데 484메가바이트.