前世紀の圧縮ライブラリに畏怖した話

前世紀の圧縮ライブラリに畏怖した話:

2018年が終わろうとしていますが、

前世紀、1999年のクリスマスに作成された圧縮ライブラリに触れて驚いた話をご紹介します。

後半で、いくつかのzlib系圧縮ライブラリとバイナリ用データ型の利用サンプルを紹介します。

経緯: PlantUMLを使っていて

開発でUMLを書く場合に、最近はPlantUMLを使うことが多くなりました。

PlantUMLはテキストベースでUMLを作図するツールで、簡易な記述で作図できるのが特徴です。

多くの記事を見つけることができますので、詳細は以下などを参照ください。

PlantUML (オフィシャルサイト)
PlantUML Cheat Sheet - Qiita

人気のあるツールなので、

PlantUMLをリアルタイムプレビューしながら記述できるプラグインが

だいたいの人気エディタには存在していますし、

GitHub上のMarkdownに記載されたPlantUMLソースを自動的に図に変換表示してくれる

Chrome拡張 Pegmatite がとても便利で愛用しています。

PlantUMLでの圧縮シーン

PlantUMLでは、UMLソースをDeflateアルゴリズムを用いて圧縮してパラメタに利用することができます。
PlantUML テキストエンコード

上記ページの説明内に、javascriptでの実装例があり、

その例では以下のライブラリを使用しています。
johan/js-deflate: RFC 1951 raw deflate/inflate for JavaScript

また、各種エディタプラグインなどPlantUML関連の派生プログラムでも、

同ライブラリが利用されているものが多々あると予想されます。

(私の愛用する、Chrome拡張Pegmatiteや、Vimプラグインでも利用していました。)

この johan/js-deflate のルーツを辿っていくと、大変興味深いものでした。

レジェントコードの系譜

dankogai/js-deflate (2009, Dan Kogai)

先の johan/js-deflate は、
dankogai/js-deflate からforkされていました。

作者は小飼弾氏。

Perl MongerとしてCGI時代からWebシーンを支えてきた方。

• 404 Blog Not Found:javascript - でデータを圧縮/伸張する
• dankogai/js-deflate: RFC 1951 raw deflate/inflate for JavaScript

dankogai/js-deflate は2009年にリリースされた deflate/inflate ライブラリで、

これは、後述する出雲さんのコードにスコープの配慮やパフォーマンス改善を施したものでした。

GitHubで公開され、johanさんを含め数多くforkされ、数多くの製品に同梱されています。

deflate.js (1999, Masanao Izumo)

dankogai/js-deflate の元となったのが、↓

• 高度な JavaScript 技集
• www.onicos.com/staff/iz/amuse/javascript/expert/deflate.txt

上記サイトでzlib.jsなど関連ライブラリも公開されています。

作者は出雲正尚氏。

氏のソフトウェアシンセサイザーTiMidity++にお世話になった方も多いのではないでしょうか。

オリジナルのコードに記載されているCopyrightは、

なんと ** LastModified: Dec 25 1999 **

19年前、20世紀のものでした！

しかも、12/25 クリスマス！！

当ライブラリの特徴的な関数名でGitHubのコード検索をしてみると、

実に 1,578件のコードがヒットしました。
Search · zip_DeflateTreeDesc

もちろん、DeflateアルゴリズムやそのC言語実装はもっと古くて未だに使い続けられていますが、

生き馬の目を抜くJavaScript界隈で、こんなに長寿のコードに直接触れることがあるとは思わなかったので、

この事実に大変驚き、偉大な諸先輩方に畏敬の念を抱きつつ、

オープンソースのダイナミズムを噛み締めました。

同時に、トレーサビリティって大事だな、と思いました。

package.jsonとか、GitHubのforkとか。

(昨今、依存ライブラリに悪意のあるコードを混入された、などのニュースもよく聞きますし。)

あと、BufferもUint8Arrayが無かった時代のコードが未だに動くという、

JavaScriptの後方互換性もすごいな、と。

注意

前述したMasanao Izumo氏由来のライブラリを利用する際には、

マルチバイト文字やバイナリデータを直接圧縮/伸張しないようにご注意ください。

(このお話は別の機会に)

Node.jsの場合は標準ライブラリのzlibを利用するのが良いでしょう。

ブラウザで圧縮/伸張の必要がある場合は、後述の他のzlib系ライブラリも検討ください。

他のzlib系ライブラリ

javascriptで書かれたdeflate, zlib系ライブラリ

• 
  nodeca/pako: high speed zlib port to javascript, works in browser & node.js
  
  
  • 2014年, とても高速なのが特徴。
• 
  imaya/zlib.js: compact zlib, deflate, inflate, zip library in JavaScript
  
  
  • 2012年, ファイルサイズが小さい。rawdeflate用やgzip用など細かく分けて提供。

Zopfli系ライブラリ

ZopfliはGoogleが開発したアルゴリズムで、より高い圧縮率が期待でき、

なおかつ、zlibで伸張できるという互換性が特徴です。(反面、ちょっと遅い。)

ZopfliのJS実装がいくつか公開されています。

• 
  imaya/zopfli.js: Porting Zopfli to JavaScript with Emscripten.
  
  
  • 2013年, 前述のimaya氏。オリジナルのCプログラムをEmscriptenで変換したものとのこと。
• 
  gfx/universal-zopfli-js: JavaScript binding to Zopfli with WebAssembly.
  
  
  • ２０１７年, Pure JavaScriptではなく、wasmを利用しているのでブラウザでも速そう。

バイナリの扱い方と圧縮ライブラリ利用のサンプル

JavaScriptで圧縮ライブラリでは

APIのI/Fとしては、だいたい以下の3種類のどれかでバイナリデータを扱うことが多いです。

• Buffer
• Uint8Array
• バイナリデータ文字列

以下では、utf8文字列をそれぞれのバイナリのデータ型に変換して利用するサンプルを例示します。

Buffer: Node.js の標準ライブラリ zlib

v7.xまでだと、<Buffer> or <string> のみですが、

新しいバージョンだと、<Buffer> | <TypedArray> | <DataView> | <ArrayBuffer> | <string> など

色々なデータ型を入力に利用できるようになっています。

でも、基本的にBufferを使えば良いと思います。

const zlib = require('zlib'); 
const str = 'あいうえお'; 
const buf = Buffer.from(str, 'utf8');           // utf8文字列 => Bufferに変換 
const deflated = zlib.deflateRawSync(buf);      // 圧縮 
const inflated = zlib.inflateRawSync(deflated); // 伸張 
const str2 = inflated.toString('utf8');         // Buffer => utf8文字列 
str === str2;                                   // true 

Uint8Array: ブラウザ系

ブラウザでも扱えるライブラリは大抵 TypedArrayを使うI/Fになっています。

新しいブラウザでは TextEncoder/TextDecoder を使うと

utf8文字列 <=> Uint8Array の相互変換が容易です。

以下は imaya/zlib.js の例です。

var str = 'あいうえお'; 
var arr = new TextEncoder().encode(str);                // utf8文字列 => Uint8Arrayに変換 
var deflated = new Zlib().RawDeflate(arr).compress();   // 圧縮 
var inflated = new Zlib().RawInflate(deflated).decompress();    // 伸張 
var str2 = new TextDecoder().decode(inflated);          // Uint8Array => utf8文字列 
str === str2;                                           // true 

TextEncoder()が使えない古い環境では、

以下のようなイメージでバイナリデータ文字列を1文字ずつ charCodeAt() でコードを取得して配列に詰めていくことになります。

var str = 'あいうえお'; 
var binstr = unescape(encodeURIComponent(str)); 
var arr = new Uint8Array([].map.call(binstr, function(c){return c.charCodeAt(0)})); 

binary data string: 古いライブラリ

古いブラウザはBufferやTypedArrayを使えなかったため、

Masanao Izumo氏由来のライブラリではI/Fはstring型を使っています。

ライブラリ内部ではデータを文字単位(正確にはJS内部表現であるUTF-16の処理単位)で処理しているため、

日本語などのマルチバイト文字列はそのままでは意図した動作をしません。

UTF8文字列をいわゆる「バイナリデータ文字列」に変換して、1文字=1byteとして扱えるようにしてから処理する必要がありました。

状態	データ	長さ
UTF8文字列	'あ'	JS内部表現(UTF-16)長=1
バイト表現	0xE3 0x81 0x82	3byte
バイナリデータ文字列	"\xE3\x81\x82"	JS内部表現(UTF-16)長=3

UTF8文字列をバイナリデータ文字列に変換するイディオムとして、以下があります。

UTF8文字列をバイナリデータ文字列に変換する

unescape(encodeURIComponent(str)) 

↑これは、Bufferを利用した以下の値と同値です。

UTF8文字列をバイナリデータ文字列に変換する(Buffer)

Buffer.from(str, 'utf8').toString('binary') 

dankogai/js-deflateの利用例は以下です。

var str = 'あいうえお'; 
var binstr = unescape(encodeURIComponent(str));         // utf8文字列 => バイナリデータ文字列に変換 
var deflated = RawDeflate.deflate(binstr);              // 圧縮 
var inflated = RawDeflate.inflate(deflated);            // 伸張 
var str2 = decodeURIComponent(escape(inflated));        // バイナリデータ文字列 => utf8文字列に変換 
str === str2;                                           // true 

ただし、Masanao Izumo氏由来のライブラリではバイナリデータ文字列を扱った場合に

特定のデータパターンで伸張できないデータを生成することがあるようですので、

ご注意ください。

最後に

オープンソースってすごいなと思いました。(小並感)

あと、記事公開が遅れて済みません。