なぜzip?

言わずと知れたファイルがちっちゃくなるフォーマット
ブラウザ上で生成したファイルをダウンロードしたい場合zipでまとめてダウンロードするのはよくある
フォルダごとダウンロードするのは私の知る限り無理だからである
他のフォーマットでも良いがiOSのファイルマネージャが標準でzip解凍に対応しているなどどこでも使えるフォーマットとして確固たる地位を確立している

ライブラリでいいじゃん

zipファイルの生成にはjszip等のライブラリがよく使われるが、解凍もできたり圧縮もできたり90kBもあったり色々と大きすぎる

使用目的はファイルをまとめるだけなのでもはや圧縮の必要もない
どんなに頑張ってプログラム本体を減らしてもライブラリがその数十倍のサイズというのは気分が良くない

目標

blobとパスの配列を受け取ってzipのblobを返す
- zip([{blob,path},...]) → blob
できれば1kBで

作る

以前に.midファイル読み書きを経験しているので同じノリで進めていく

ファイル構造の理解

以下の三つの記事を参考に理解を進めた

表記のブレが激しい
ヘッダ
- 3種類ある
- 正式な名前ではないかも(この記事での略称)
- ローカルファイルヘッダ(LFH)
  - 付箋みたいな感じで各データの先頭に存在する
  - 0x504B0304(PK0304)から始まる
  - この直後にファイルの内容が続きそれが終わるとまた次のファイルのLFH
- セントラルディレクトリヘッダ(CDH)
  - 索引みたいな感じで後ろにまとまって存在する
  - 0x504B0102(PK0102)から始まる
  - 対応するLFHの位置が記録されている
  - これのおかげでデータを読まずに構造がわかる
- セントラルディレクトリ終端レコード(EOCD)
  - 奥付みたいな感じで一番最後に1つだけ存在する
  - 0x504B0506(PK0506)から始まる
  - CHDの集合の位置が記録されている
  - なんでこれだけレコード？
- 必ずこの順である必要はないようだがこれは慣例？
階層構造はファイル名にパスを入れて表現できる

wikipediaの図がわかりやすい
各ヘッダの細かな内容についてはgistのリンクに細かく書かれているので割愛
基本的にjsでの実装に焦点を当てる

ファイルに擬態したディレクトリ

実物を見ないで書き始めるのはしんどいので、7zipでzipを作成してバイナリエディタで覗いてみた
"folder"ディレクトリに"aiu\neo"を書いた"a.txt"を入れて圧縮した
元データが小さいので結果として圧縮されていない

50 4b 03 04 // PK0304
14 00 // v2.0
00 00 // no flag
00 00 // cps stored
4b 6a 8e 55 // date
00 00 00 00 // crc32
00 00 00 00 // cps size
00 00 00 00 // raw size
07 00 // name l
00 00 // ex l
66 6f 6c 64 65 72 2f // name "folder/"

50 4b 03 04
0a 00 // v1.0
00 00
00 00
4f 6a 8e 55
33 5e b9 72
06 00 00 00
06 00 00 00
0c 00
00 00
66 6f 6c 64 65 72 2f 61 2e 74 78 74 // name "folder/a.txt"
61 69 75 0a 65 6f // content "aiu\neo"

50 4b 01 02 // PK0102
3f 00 // v created
14 00 // v required
00 00 // no flag
00 00 // cps stored
4b 6a 8e 55 // date
00 00 00 00 // crc32
00 00 00 00 // cps size
00 00 00 00 // raw size
07 00 // name l
00 00 // ex l
00 00 // cmt l
00 00 // disk start no
00 00 // in attr
10 00 00 00 // out attr
00 00 00 00 // rpos
66 6f 6c 64 65 72 2f // name "folder/"


50 4b 01 02
3f 00
0a 00
00 00
00 00
4f 6a 8e 55
33 5e b9 72
06 00 00 00
06 00 00 00
0c 00
00 00
00 00
00 00
00 00
20 00 00 00
25 00 00 00
66 6f 6c 64 65 72 2f 61 2e 74 78 74 // name "folder/a.txt"

50 4b 05 06 // PK0506
00 00 // disk no this
00 00 // disk no 0304 starts
02 00 // cnt 0102 on this disk
02 00 // cnt 0102 all
6f 00 00 00 // 0102 size
55 00 00 00 // 0102 rpos
00 00 // cmt l

驚いたのはフォルダがファイルのふりをして居座っていること
これはバージョン2.0で追加された機能の模様
確認のためにこれを消して正常に解凍できるか試す
対応するCHDの削除と、EOCDのCDHサイズ、CHD位置の再計算が必要なのであらかじめ自身の理解が正しいことを確認してから消した

Object.assign(
	document.createElement('a'),
	{
		download:'test.zip',
		href:URL.createObjectURL(
			new Blob([
				new Uint8Array(`

50 4b 03 04
0a 00 // v1.0
00 00
00 00
4f 6a 8e 55
33 5e b9 72
06 00 00 00
06 00 00 00
0c 00
00 00
66 6f 6c 64 65 72 2f 61 2e 74 78 74 // name "folder/a.txt"
61 69 75 0a 65 6f // content "aiu\neo"

50 4b 01 02
3f 00
0a 00
00 00
00 00
4f 6a 8e 55
33 5e b9 72
06 00 00 00
06 00 00 00
0c 00
00 00
00 00
00 00
00 00
20 00 00 00
00 00 00 00
66 6f 6c 64 65 72 2f 61 2e 74 78 74 // name "folder/a.txt"

50 4b 05 06 // PK0506
00 00 // disk no this
00 00 // disk no 0304 starts
01 00 // cnt 0102 on this disk
01 00 // cnt 0102 all
3a 00 00 00 // 0102 size 再計算
30 00 00 00 // 0102 rpos 再計算
00 00 // cmt l

				`.replace(/\/\/.*$/gm,'').match(/[\da-f]{2}/g).map(x=>parseInt(x,16))
				).buffer
			])
		)
	}
).click();

結果、問題なく解凍できた
これでパスからmkdirする必要のあるディレクトリを列挙する必要がないことがわかった

TypedArrayのエンディアン

zipのパラメータは全てリトルエンディアンで格納する必要がある
リトルエンディアンは一見面倒なように見えるが配列と相性が良かったりする
整数を4byteにして使う場面が多かったので整数を受け取り、長さ4のuint8arrayにして返す関数を作成した

const le32=x=>new Uint8Array(new Int32Array([x]).buffer);

このコードは一つ問題がある
typedarrayのエンディアンはjsエンジン側が自由に決められるのだ
つまりこのコードはx86上で動かすと問題なく動作するがスマホなどarm上で動かすとビッグエンディアンで返ってくるのだ
(2023/09/09追記: 久しぶりに確認したらiOS Safariでもリトルエンディアンになっていた jsではリトルエンディアンを使うように規格で定められているらしい?)
エンディアンを気にしつつarraybufferを扱う必要がある場合はdataviewを使うのが最善なようである
しかしdataviewはただでさえパフォーマンスの良くないtypedarrayよりもさらにパフォーマンスが悪い
大した用途でもないため最終的に愚直にビットシフトで実装した

const le32=x=>new Uint8Array(4).map((_,i)=>x>>>(i*8));

CRC32を美しく実装する

crd32は主にファイル内容に誤りがないことを確認する用途に使われる簡便なハッシュの一種
今回は圧縮しないがLFHとCDHにcrc32を計算して書き込む必要がある
(CRC32を生成するためだけにファイルを読み込む必要があるのは正直面倒)
gistのリンクからもリンクされているrfc1952の実装例の通りに実装する
https://www.rfc-editor.org/rfc/rfc1952
基本的に初期値があってそれをループで操作するだけなのでjsではreduce一本で実装できる
なおjsの整数ビット演算は実質32bitなので0xffffffffは-1で代用可能であり>>は>>>にする必要がある

const
crct=[...Array(256)].map((_,n)=>[...Array(8)].reduce((c,_,k)=>(c&1)?0xedb88320^(c>>>1):c>>>1,n)),
crc=(buf,crc=0)=>buf.reduce((c,x)=>crct[(c^x)&0xff]^(c>>>8),crc^-1)^-1;

le32(crc(new Uint8Array(await fileBlob.arrayBuffer())));

これでファイルをuint8arrayに読んでcrc()に投げれば無事crc32を得ることができる
実際に7zipで生成したzipに含まれるcrc32と一致したうえ、jszipの実装もreduceこそ使っていないが流れは同じだったのでこれで正解だと思われる

MS-DOS date/time format

個人的にはこれが資料が少なくて一番厄介だった
多くの資料では時刻2byte+日付2byte としている
しかし整数を4byteに整形する処理を作った手前、まとめて4byteにした方が扱いやすいのでここではまとめて扱う
順番に関してはリトルエンディアンなのでこのままで問題ない

/*
まずビッグエンディアンで考える

MSB <-- --> LSB
YYYYYYYM MMMDDDDD hhhhhmmm mmmsssss

ここで
YYYYYY=年-1980 MMMM=月 DDDDD=日
hhhhh=時 mmmmmm=分 sssss=秒/2

注意: new Date().getMonth()は0~11

リトルエンディアンに直す

MSB <-- --> LSB
mmmsssss hhhhhmmm MMMDDDDD YYYYYYYM
*/
const d=new Date();

le32(
    ((d.getFullYear()-1980)<<25)|
    ((d.getMonth()+1)<<21)|
    (d.getDate()<<16)|
    (d.getHours()<<11)|
    (d.getMinutes()<<5)|
    (d.getSeconds()>>1)
);

7zで作成したzipとwindowsのプロパティ表示を使って比較した
どうやら2秒ずれているようだがぶっちゃけどうでも良いのですスルー
どう考えたって合ってるでしょ()

awaitな.reduce()

zip生成の処理の流れとして

並列で処理できる操作を終わらせる
- ここではpreと呼ぶ
- ファイル毎に独立した変数の用意
  - CRC32
  - 最終更新日時の計算
  - ファイル名のエンコード
データ位置を計算してファイルを配列に格納する
- ここではpostと呼ぶ
- データ位置は前のデータに依存するので並列処理不可

つまりreduceの中身の関数をawaitを使って数珠状に繋げることができれば全ての処理を一本のreduceに収めることができるのである

const sleep=x=>new Promise(f=>setTimeout(f,x*1000));

//直感で実装
[1,2,3].reduce(async(a,x)=>(console.log(x),await sleep(1),x),0);
//一気に1,2,3と表示されてしまう

//正しくは
[1,2,3].reduce(async(a,x)=>(await a,console.log(x),await sleep(1),x),0);

//つまり
arr.reduce(async(a,x)=>(pre(),a=await a,post(),a),{});

第一引数にある前の実行結果をawaitする必要がある
なぜならasyncの返値はpromiseでありこれ自体は即時返されるからである
つまり前の実行結果のawaitより前にある処理は並列して実行され、awaitの後の処理は直列で実行されるということである
ところでreduceの初期値がawaitに渡されているがawaitはpromiseでない場合はそのまま中の値を返してくれるので心配する必要はない

パフォーマンス

最初にLFHとCDH格納用のarrayをそれぞれ作りそこにファイル本体のデータを含めて直接0~255を流し込んでuint8array→arraybuffer→blobの流れで変換する実装をした
結果は80MBで十数分かかるという様であった
ところでarray.prototype.flat()は中身のuint8arrayを展開できないという気付きを得たのでここで共有する

blobのコンストラクタが引数に取るのはarrayでありその中身として

ArrayBuffer、TypedArray、DataView、Blob、文字列などのオブジェクト、またはそのようなオブジェクト

が挙げられている
そして返値のblobは

引数 array で与えられた値を連結したものから構成

される
(これだけでファイルをまとめることができてしまうのではないかとソワソワしながら読む)

つまりいちいちarrayに値展開するのではなくてblobとかuint8arrayそのまま入れてくれた方が助かるということである
この場合実際はarraybufferのアドレスの配列を渡すことになるのでパフォーマンスが改善されることは容易に想像がつく
スプレッド演算子の減少でコピー回数が減ることも大きい
そもそもなぜ最初からこう実装しなかったんだ

パフォーマンス改善の方針として

計算値は全てuint8arrayに入れる
- le32()の結果がuint8arrayなのでそのままで良い
- 最初の実装でスプレッド演算子を使ったのが悪かった
ファイル本体はblobのまま扱う
ヘッダーで使い回す定数のuint8arrayは都度作らずにあらかじめ用意しておく

改善の結果80Mbであれば4秒ほどで終わるようになった
驚異の200倍速である

完成

例の如く変数宣言は全てデフォルト引数に詰め込んであったりreturn省略のためにカンマ繋ぎになっていたりと読み辛い
注意点として

u=Uint8Arrayで省略
le32()→le() byte数の指定に対応
reduceの初期値に入っているメソッドを最後に実行してEOCD作成
進捗表示用のコールバック関数を引数に追加

const
    zip=async(w=[],f=_=>_)=>await(async(
        u=Uint8Array,zz=new u([0,0]),v10=new u([10,0]),pk=[...Array(3)].map((_,i)=>new u([80,75,(i*=2)+1,i+2])),stat={pre:[0,w.reduce((a,x)=>a+x.blob.size,0)],post:[0,w.length]},
        cnt=x=>x.reduce((a,y)=>a+(y.byteLength||y.size||0),0),le=(x,l=4)=>new u(l).map((_,i)=>x>>>(i*8)),te=new TextEncoder(),
        crct=[...Array(256)].map((_,n)=>[...Array(8)].reduce((c,_,k)=>(c&1)?0xedb88320^(c>>>1):c>>>1,n)),crc=(buf,crc=0)=>buf.reduce((c,x)=>crct[(c^x)&0xff]^(c>>>8),crc^-1)^-1// https://www.rfc-editor.org/rfc/rfc1952
    )=>(f(stat),await w.reduce(async(a,{path:n,blob:b,date:d=new Date()},x)=>(
        x={
            n:te.encode(n),c:le(crc(new u(await new Response(b).arrayBuffer()))),
            d:le(((d.getFullYear()-1980)<<25)|((d.getMonth()+1)<<21)|(d.getDate()<<16)|(d.getHours()<<11)|(d.getMinutes()<<5)|(d.getSeconds()>>1))// mmmsssss hhhhhmmm MMMDDDDD YYYYYYYM // Y-=1980;s/=2;
        },
        x.x=[v10,zz,zz,x.d,x.c,...(_=>[_,_])(le(b.size)),le(x.n.byteLength,2),zz],// vReq flag cpsType date CRC32 ...[cpsSize rawSize] nameLength extLength
        stat.pre[0]+=b.size,f(stat),a=await a,
        a.cd.push(pk[0],v10,...x.x,zz,zz,zz,zz,zz,le(cnt(a.lf)),x.n),// PK0102 vMade X cmtLength 0304disk intAttr extAttrLSB extAttrMSB 0304pos name
        a.lf.push(pk[1],...x.x,x.n,b),// PK0304 X name content
        stat.post[0]++,f(stat),a
    ),{lf:[],cd:[],_(){return new Blob([...this.lf,...this.cd,
        pk[2],zz,zz,...(_=>[_,_])(le(w.length,2)),le(cnt(this.cd)),le(cnt(this.lf)),zz// PK0506 disk 0304startDisk ...[cnt0102disk cnt0102all] 0102size 0102pos cmtLength
    ],{type:'application/zip'});}}))._())();


console.log(
    await zip([
        {path:'hello/world.txt',blob:new Blob(['Hello world!'])},
        {path:'hello/hoge.txt',blob:new Blob(['Hello hoge!'])},
        {path:'hello/hoge/fuga.txt',blob:new Blob(['Hello hoge fuga!'])}
    ],x=>console.log(
        `pre: ${(x.pre[0]/x.pre[1]*100).toFixed(2)} %, post: ${(x.post[0]/x.post[1]*100).toFixed(2)} %`
    )
);

ここで関数本体のみminifyした結果1071byteという結果だった
1kBとまではいかなかったが十分小さくできた

これを作った目的であるgithubの自家製ディレクトリダウンローダー

jszipを使った類似のアプリで160MBほどあるディレクトリをダウンロードしてzip生成部分のみ速度を比較した
今回の圧縮コードが若干遅い結果となったが、webWorkerを使った高速化すらしていないのでまだまだ改善の余地はある

幸せなzipライフを

追記: ライブラリにして公開