36 캐비닛, MSZIP, deflate

36.1 캐비닛 배치 [spec: MS-CAB]#

CFHEADER (예약 필드가 없으면 36바이트):
  "MSCF", u32 0, u32 캐비닛 크기, u32 0, u32 첫 CFFILE 오프셋, u32 0,
  u8 부판 3, u8 주판 1, u16 폴더 수, u16 파일 수, u16 플래그(0),
  u16 세트 id, u16 캐비닛 번호(0)
CFFOLDER (각 8바이트):
  u32 폴더의 첫 CFDATA 오프셋, u16 CFDATA 블록 수, u16 압축
  (0 = 없음, 1 = MSZIP)
CFFILE (파일마다):
  u32 압축 전 크기, u32 폴더의 압축 전 데이터 속 오프셋, u16 폴더 번호,
  u16 날짜, u16 시각, u16 속성, NUL 로 끝나는 이름
CFDATA (블록마다):
  u32 체크섬, u16 압축 바이트 수, u16 압축 전 바이트 수(최대 32768), 데이터

• MSI 에서 캐비닛 속 파일 이름은 File 표의 키이고 ASCII 다.
• DOS 날짜 (year - 1980) << 9 | month << 5 | day, 시각 hour << 11 | minute << 5 | second / 2. 고정된 날짜(rubrapack 은 1980-01-01 00:00 을 쓴다)가 출력을 결정적으로 지킨다. 속성은 0x20.
• 폴더 하나에는 블록이 65535개(약 2 GiB)까지 든다. 데이터가 더 많으면 폴더나 캐비닛을 더 쓴다.

블록 체크섬 [spec]#

checksum(bytes, seed):
  바이트 속 온전한 리틀엔디언 u32 를 모두 seed 에 xor 한다;
  남은 1~3바이트는 u32 하나를 이루되 남은 바이트 가운데 첫째가 쓰인 자리 가운데 가장 높은 곳에 온다
  (3개 남음: b0<<16 | b1<<8 | b2; 2개: b0<<8 | b1; 1개: b0). 그것도 xor 한다.
블록 체크섬 = checksum(저장된 대로의 4바이트 "압축 크기, 압축 전 크기",
                       checksum(블록 데이터, 0))

체크섬 0 은 "계산하지 않음"을 뜻하고 판독기는 그것을 받는다.

36.2 MSZIP [spec: MS-MCI]#

압축 형식이 1 인 폴더의 CFDATA 블록마다 다음이 든다:

"CK" (43 4B), 그다음 이 블록의 압축 전 바이트(최대 32768)에 대한 온전한 원시 deflate 스트림
(RFC 1951) 하나, 마지막 블록으로 끝남.

압축 해제기는 같은 폴더의 앞 블록들을 사전으로 간직하므로, 인코더는 앞 블록을 되돌아 가리켜도 된다. 그러지 않는 인코더(블록마다 따로 압축)도 올바른 MSZIP 을 만든다. rubrapack 은 블록마다 앞 블록의 압축 전 32 KiB 를 미리 준 사전으로 쓴다(섞인 자료에서 블록을 따로 압축할 때보다 약 9% 작다). 그 사전은 출력이 아니라 입력이므로 블록을 여러 스레드에서 동시에 압축할 수 있고, 스레드 수와 상관없이 바이트가 같다. 폴더는 65535블록이 되기 전에 파일 경계에서 새로 시작하고, 사전은 폴더를 넘지 않는다. Windows 는 이것을 모두 풀어낸다: 폴더 열두 개짜리 패키지가 설치·복구·제거되고 모든 파일이 바이트까지 같다. [observed]

36.3 LZX [spec: MS-PATCH 2, MS-CAB]#

압축 형식이 3 | w << 8(w = 15 .. 21)인 폴더는 창이 2^w 바이트인 LZX 스트림 하나이고, 출력 32768바이트씩 프레임으로 잘린다(마지막은 더 짧다). 프레임 하나가 CFDATA 블록 하나다. 창, 되풀이 오프셋 셋, 부호 길이는 프레임을 넘어 이어지고, 프레임마다 끝에서 비트 스트림을 16비트 경계로 채운다.

• 비트는 16비트 리틀엔디언 워드에서, 가장 높은 비트부터 읽는다.
• 폴더는 비트 하나로 시작한다: 1 이면 E8 변환 이고 32비트 크기가 따른다. 압축기는 E8 바이트(x86 call) 뒤 4바이트를 상대 주소에서 절대 주소로 바꿔 되풀이되는 호출이 일치하게 했고, 풀개는 첫 32768 프레임에서만 그것을 되돌린다.
• 블록: 형식 3비트(1 verbatim, 2 aligned offset, 3 무압축), 무압축 크기 24비트. 블록과 일치는 프레임을 넘을 수 있다.
• verbatim 과 aligned 블록은 주 트리(리터럴 256개, 그다음 위치 슬롯 마다 기호 8개: w = 15 에 30개부터 w = 21 에 50개까지)와 길이 트리(기호 249개)를 보내는데, 범위마다 앞 블록의 길이와의 차(17로 나눈 나머지)를 기호 20개짜리 프리트리로 적는다(17·18: 0 의 연속, 19: 한 값의 짧은 연속). aligned 블록은 먼저 긴 오프셋의 낮은 3비트를 위한 기호 8개짜리 트리를 보낸다.
• 255 를 넘는 주 기호는 일치다: 낮은 3비트 = 길이 - 2(7 이면 길이 트리 기호를 더함, 최대 257), 나머지는 위치 슬롯. 슬롯 0-2 는 마지막 오프셋 셋을 다시 쓰고, 슬롯 s >= 3 은 오프셋 base[s] - 2 + 덧비트 를 주며, 새 오프셋은 되풀이 오프셋으로 들어간다.
• 무압축 블록은 16비트로 채우고(이미 맞으면 워드 하나 통째로), 되풀이 오프셋 셋을 32비트 리틀엔디언으로, 이어 바이트들을, 그 수가 홀수면 채움 바이트 하나를 담는다.

rubrapack 은 프레임마다 verbatim 블록 하나(더 작으면 무압축 블록)를 쓰고, 일치는 프레임을 넘지 않으며, 새 일치와 비슷하게 길면 되풀이 오프셋을 쓰고, 한 걸음 미뤄 보는(lazy) 일치를 쓰며, E8 변환은 쓰지 않는다. 읽기는 모든 블록 형식과 E8 변환을 다룬다. Windows 의 expand.exe 와 msiexec 가 그 캐비닛을 풀고, rubrapack 은 makecab.exe 가 E8 변환을 켜고 만든 캐비닛을 푼다. [observed]

36.4 deflate 인코더 간단히 [spec: RFC 1951]#

1. 일치 찾기(LZ77): 다음 3바이트를 해시하고, 32 KiB 안에서 같은 해시를 가진 앞 자리들의 체인을 따라가 가장 긴 일치(3..258바이트)를 고른다. 체인을 길게 따라갈수록 압축이 좋아진다. 다음 자리도 해 보고 그 일치가 더 길면 리터럴을 내보내는 "게으른" 단계가 눈에 띄게 도움이 된다.
2. 블록: 기호를 수만 개까지 묶는다. 블록마다 세 가지 인코딩의 크기를 계산해 가장 작은 것을 쓴다:
   • 고정 허프만 부호(리터럴/길이 0-143: 8비트, 144-255: 9, 256-279: 7, 280-287: 8; 거리 5비트);
   • 동적 허프만 부호: 부호 길이는 15비트로 제한(부호 길이 알파벳은 7). package-merge 가 제한된 최적 길이를 준다. HLIT, HDIST, HCLEN, 16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15 순서의 부호 길이 부호, 그다음 런렝스로 부호화한 길이들(16 = 앞 것 3-6번 반복, 17 = 0 을 3-10개, 18 = 0 을 11-138개)을 보낸다;
   • 저장(바이트 정렬한 LEN, NLEN, 원 바이트; 저장 블록 하나에 최대 65535).
3. 허프만 부호는 최상위 비트부터, 그 밖의 것은 최하위 비트부터 쓴다.
4. 늘 기호 둘 이상에 부호 길이를 준다(외톨이 기호는 가짜 기호와 짝지운다). 그래야 모든 부호가 완전하다 - 불완전한 부호를 거부하는 디코더가 있다.

인코더는 독립된 구현(예: zlib 라이브러리의 원시 deflate, window bits -15)으로 출력을 풀어 보고, 그것으로 지은 MSI 는 설치해서 설치된 파일의 해시를 비교해 확인한다(출력을 Windows 와 대조하기).

36.5 실제 예: 튜토리얼의 hello.msi#

튜토리얼 첫 패키지의 캐비닛은 스트림 cab1.cab, 6776 바이트다. CFHEADER:

0x24 의 CFFOLDER: 42 00 00 00 01 00 01 00 - 첫 CFDATA 는 66, 블록 1개, 압축 1(MSZIP).

CFFILE 항목 - 이름은 File 표의 키다:

66 의 첫 CFDATA: 체크섬 80 35 aa c0, 압축 6702 바이트가 풀면 17920 바이트. 데이터는 43 4b ed 5c 0d 74 로 시작한다: CK, 그리고 deflate. 첫 deflate 바이트 ed = 11101101 의 가장 낮은 비트가 BFINAL = 1, 다음 두 비트가 BTYPE = 2(동적 부호)다.