日別アーカイブ: 2013年10月6日

データ圧縮 zlib と gzip と zip (zlib で zip にアクセスする)

Windows を除いてほとんどのプラットフォームには zlib が入っており、
データの圧縮に利用することが出来ます。

zlib

メモリ上のイメージを圧縮するだけなら下記のとおり。

// [1]
// 圧縮データが入るバッファの確保
uLong  buffer_size= compressBound( src_size );
Bytef* buffer= memory_alloc( buffer_size );

// 圧縮
compress( buffer, &buffer_size, src_memory, src_size );

// 圧縮後のサイズ
compressed_size= buffer_size;

圧縮率を指定するなら compress() の代わりに compress2() を使います。
展開も同様。

// [2]
uLong buffer_size= uncompressed_size;
uncompress( buffer, &buffer_size, src_memory, src_size );

解凍時は展開後の元のサイズ (src_size) が必要になるので、
圧縮時に保存しておく必要があります。

●ヘッダと動作モード

圧縮されたデータには、先頭にフォーマットを表す最小限のヘッダ、
最後にチェックサム Adler-32 が付加されます。
このヘッダ形式は zlib 独自のもので、gzip や zip 等とは互換性がありません。
チェックサムも一般的な CRC とは異なっています。

ただし圧縮アルゴリズム自体は広く使われている Deflate で、
ヘッダ&フッタが違うだけでデータ本体は gzip/zip などと同じです。
そのため zlib には、gzip のヘッダを用いて読み書きを行うモードがあります。

[1]/[2] の compress()/uncompress() 相当を低レベルな API で書きなおしたのが
下記の例です。

// [3] Compress (zlib)
size_t Compress_zlib( void* dest_memory, size_t dest_size, const void* src_memory, size_t src_size )
{
   z_stream  stream;
   memset( &stream, 0, sizeof(z_stream) );
   stream.next_in= (Bytef*)src_memory;
   stream.avail_in= src_size;
   stream.next_out= (Bytef*)dest_memory;
   stream.avail_out= dest_size;

   deflateInit2( &stream, COMPRESS_LEVEL, Z_DEFLATED, MAX_WBITS, 5, 8, Z_DEFAULT_STRATEGY );
   int result= deflate( &stream, Z_FINISH )
   if( result != ZSTREAM_END && result != Z_OK ){
      // error
      return  0;
   }
   deflateEnd( &stream );

   return  stream.total_out;  // compressed_size
}
// [4] Uncompress (zlib)
size_t Uncompress_zlib( void* dest_memory, size_t dest_size, const void* src_memory, size_t src_size )
{
   z_stream  stream;
   memset( &stream, 0, sizeof(z_stream) );
   stream.next_in= (Bytef*)src_memory;
   stream.avail_in= src_size;
   stream.next_out= (Bytef*)dest_memory;
   stream.avail_out= dest_size;

   inflateInit2( &stream, MAX_WBITS );
   int result= inflate( &stream, Z_FINISH )
   if( result != ZSTREAM_END && result != Z_OK ){
      // error
      return  0;
   }
   inflateEnd( &stream );

   assert( dest_size == stream.total_out );

   return  stream.total_out;  // uncompressed_size
}

deflateInit2() / inflateInit2() の引数のうち、上の [3]/[4] で
MAX_WBITS が入っている所が windowBits の指定場所になります。
windowBits には下記の特殊な用法があります。

(1) windowBits       =   8~15    zlib format
(2) windowBits + 16  =  24~31    gzip format
(3) windowBits + 32  =  40~47    zlib/gzip format (inflate のみ)
(4) -windowBits      =  -8~-15   raw format

(2) のようにパラメータに 16 を加えると gzip フォーマットになります。
チェックサムも CRC-32 です。
例えば上の例 [3]/[4] だと MAX_WBITS の代わりに (MAX_WBITS+16) を与える
ことになります。

(3) inflateInit2() の場合 windowBits に 32 を加えると zlib/gzip の
自動判別ができるようになります。

(4) のように負数を入れると余計なデータが出力されません。
ヘッダも付かずにチェックサム計算も省かれます。
zip のように互換性のないファイル構造でも、データ部分の圧縮と解凍に
zlib を利用出来るようになります。( Method 8 )

まとめると下記の通り。zlib には 3種類の動作モードがあります。

               windowBits      header       checksum
-----------------------------------------------------
zlib format    MAX_WBITS       zlib 形式    Adler-32
gzip format   (MAX_WBITS|16)   gzip 形式    CRC-32
raw format    -MAX_WBITS       無し         無し

● Windows

zlib は Windows でも利用できますが、64bit (x64) では少々問題があります。

zlib のサイズ値に uLong (unsigned long) 型が用いられているので、
同じ 64bit OS でも Windows とそれ以外で型のサイズが変わっています。
Windows は LLP64 なので 32bit、Linux x64, OSX, IOS arm64 は LP64 なので
64bit になります。

例えば上の [3]/[4] のコードは size_t を使用しています。
size_t は x64 で 64bit なので、Windows x64 のみ zlib API に渡すときに
32bit への変換が必要になってしまいます。
互換性の意味でも long はできるだけ避けたいのですが、
Windows x64 では諦めてキャストを使っています。

● zip の構造とデータアクセス

zip はデータ圧縮だけでなくアーカイバの機能も含まれています。
tar + gzip の組み合わせはアーカイブした後に一度に圧縮しますが、
zip は個々のファイルを個別に圧縮しています。

また圧縮はファイルの中身だけで、ヘッダや含まれるファイル情報
(Local Header, Central Directory など) は含まれません。
そのため小さいファイルが大量に含まれるケースでは zip の効率は落ちます。

反面、ファイル単位でランダムアクセスが可能で、必要なファイルだけを
取り出すことができます。
アクセスするためには下記の手順が必要になります。

(1) EOR を検索して、Central Directory の位置を特定する
(2) Central Directory を読み込んで必要なファイルを検索する
(3) (2) からファイルの Local Header の位置が求まるので読み込む
(4) Local Header からデータの位置を求めて特定する。

End of Central Directory record (EOR) の位置は不定なので、
ファイルの終端から逆方向に読み込んで SIGNATURE の検索が必要。
EOR が特定できれば Central Directory の位置とサイズがわかるので
まとめて読み込むことが出来ます。

Central Directory 内の個々の情報は不定長なので、一度先頭から
読み進める必要があります。
Local Header の位置、ファイル名、圧縮前後のファイルサイズ、CRC、
圧縮メソッドなどはここに含まれます。
ディレクトリも個別エントリとして含まれており、サイズは 0 で
ファイル名の最後に ‘/’ が付きます。

Local Header はファイル本体の前に挿入されています。
こちらも長さ不定で、読み込んでみるまでデータの位置が厳密に求まりません。
適当なサイズを指定してとりあえず読み込みます。

Local Header からデータの位置が特定できるので、
実際のデータ部分を zip ファイルからロードできます。
Method が 8 なら圧縮されているため zlib の raw format として解凍できます。
解凍後に zlib の crc32() 等を使って CRC チェックを行います。

デフォルトで用いられている圧縮 Method は 0 と 8 です。
Method 8 が Deflate で Method 0 は非圧縮となっています。

下記の資料を参考にしました。

APPNOTE.TXT – .ZIP File Format Specification

簡単にデータ位置を特定できない点は少々やっかいですが、
Central Directory は先キャッシュ出来ますし、Local header も
データと同時に多めにサイズを指定してまとめて読み込んでしまうことも出来ます。
解凍も zlib が使えますし、広く使われているだけあって zip の
データアクセスは比較的容易にできます。