JavaScript: LZ4圧縮補完計画

LZ4と呼ばれる圧縮法を改良しようという企画。ほぼ圧縮率を重点的に。圧縮速度は控え目であるが…気にしてはいけない。

改良法

巨大一致と巨大不一致の符号化を工夫する。本家は巨大な値nを n/255 bytes程度出力するが、私家版は log256(n) bytes程度の出力で収まる。スン、バラスィー。などと自画自賛しているようではprogrammerとして終わっている。
それはともかく、最長一致系列は全ての地点でくまなくもれなく徹底的に調べ上げ、符号化費用対効果を最適化しまくった挙句の果てに、何とか全てを出力する事に成功する。
言うまでもない事だが、本家との互換性は概ね皆無である。

実装編

/*compress
@In: input(Array / Uint8Array)
@done: call back of last process
	done(A,a,z)
	@A: compressed array of input
	@a: input size
	@z: compressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return:
	call with await: compressed array of @In
	without await: Promise object
*/
async function LZ4enc(In,done=a=>a,rate){
	var m,n=In.length,o=0,p=0;
	const W=1<<16,M=W-1,Out=[],
		// for match finder
		Hash=new Int32Array(1<<18).fill(-1), Tree=new Int32Array(W*2),
		// for optimal parser
		Cost=new Uint32Array(n*2), Len=Cost.subarray(n), Dist=new Uint16Array(n),
		pass=rate?32767:-1,fn=b=>wait0(c=>b(rate(p,n)));
	// Pass 1: Find all matches
	for(;p<n;p&pass||await new Promise(fn)){
		let v=0,m=n-p,d;
		if(m>3){// get matches used binary tree match finder
			let r=p&M,l=r|W,b=0,c=0,w=p<W?-1:p-W,
				h=(In[p]|In[p+1]<<8|In[p+2]<<16|In[p+3]<<24)*2097143>>>14, s=Hash[h];
			for(Hash[h]=p;s>w;){
				let i=b<c?b:c;
				if(In[s+i]===In[p+i]){
					for(;++i<m&&In[s+i]===In[p+i];);
					if(i>v){
						v=i;d=p-s;
						if(i===m)break
					}
				}
				if(In[s+i]<In[p+i])
					Tree[r]=s,s=Tree[r=s&M|W],c=i;
				else Tree[l]=s,s=Tree[l=s&M],b=i}
			Tree[l]=Tree[r]=-1
		}
		Len[p]=v;Dist[p++]=d
	}
	// Pass 2: Build the shortest path
	for(let s=15;--p>0;){
		let c=Cost[p+1]+1;--s||(s=255,++c);
		if(Len[p]>3){
			Cost[p]=1<<30;
			for(let l=Len[p];l>3;--l){
				let d=Cost[p+l]+3,i=l-4;
				if(i>14)++d,i-=15,i>252&&(i-=253,d+=i>>16?3:i>>8?2:1);
				if(d<Cost[p])Cost[p]=d,Len[p]=l
			}
			if(c<Cost[p])Cost[p]=c,Len[p]=0;
			else s=15
		}else Cost[p]=c
	}
	// Pass 3: Output the codes
	for(m=p=0;p<n;)
		if(Len[p]>3){
			let l=Len[p]-4,d=l<15?l:15;
			if(m<p){
				let r=p-m;
				if(r>14){
					Out[o++]=240+d;
					if((r-=15)<253)Out[o++]=r;
					else for(Out[o++]=(r-=253)<256?253:r<65536?254:255;Out[o++]=r&255,r>>=8;);
				}else Out[o++]=r<<4|d;
				for(;m<p;)Out[o++]=In[m++]
			}else Out[o++]=d;
			Out[o++]=Dist[p]>>8;Out[o++]=Dist[p]&255;
			if(l>14){
				if((l-=15)<253)Out[o++]=l;
				else for(Out[o++]=(l-=253)<256?253:l<65536?254:255;Out[o++]=l&255,l>>=8;);
			}
			m=p+=Len[p]
		}else++p;
	if(m<p){
		let r=p-m;
		if(r>14){
			Out[o++]=240;
			if((r-=15)<253)Out[o++]=r;
			else for(Out[o++]=(r-=253)<256?253:r<65536?254:255;Out[o++]=r&255,r>>=8;);
		}else Out[o++]=r<<4;
		for(;m<p;)Out[o++]=In[m++]
	}done&&done(Out,n,o);return Out
}
/*decompress
@In: input(Array / Uint8Array)
@done: call back of last process
	done(A,a,z)
	@A: decompressed array of @In
	@a: last position
	@z: decompressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return:
	call with await: decompressed array of @In
	without await: Promise object
*/
async function LZ4dec(In,done=a=>a,rate){
	var a=0,b,c,size=In.length,l,o=0,p;
	const MINMATCH=4,ML_BITS=4,ML_MASK=(1<<ML_BITS)-1,RUN_BITS=8-ML_BITS,RUN_MASK=(1<<RUN_BITS)-1,
		Out=[],pass=rate?32767:-1,fn=b=>wait0(c=>b(rate(a,size)));
	for(;;o&pass||await new Promise(fn)){
		c=In[a++];
		if(l=c>>ML_BITS){
			if(l===RUN_MASK)
				if((b=In[a++])<253)l+=b;
				else for(l+=253,b-=252,p=0;l+=In[a++]<<p,--b;)p+=8;
			for(;l--;)Out[o++]=In[a++]
		}
		p=o-(In[a++]<<8|In[a++]);
		if(a>size)return done(Out,size,o),Out;
		if((c&=ML_MASK)===ML_MASK)
				if((b=In[a++])<253)c+=b;
				else for(c+=253,l=0;c+=In[a++]<<l,--b>252;)l+=8;
		for(c+=MINMATCH;c--;)Out[o++]=Out[p++]
	}
}
// setImmediateもどき
(function(a){
	var F=[],hit="\0";
	a.wait0=function(fn){
		F[F.length]=fn;
		a.postMessage(hit,"*")
	};
	a.onmessage=function(e){
		if(e.source===a&&e.data===hit)
			e.stopPropagation(),
			F[0]&&F.shift()()
	}
})(this)

使用例

(async()=>{
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let rate=(a,b)=>{console.log((a/b*1e4|0)/100,"%")}, done=(a,b,c)=>{console.log(b,"->",c,a)};
let e=await LZ4enc(A,done,rate), d=await LZ4dec(e,done,rate);
console.log(e.length, String.fromCharCode(...d))

// without await
LZ4enc(A).then(a=>LZ4dec(a).then(b=>console.log(a.length,b.length,b)))
})()

file圧縮伸長実験

See the Pen LZ4 variant compressor by xezz (@xezz) on CodePen.

参考文献様

本家