JavaScript: Polar code

情報圧縮編、今回はPolar codeを紹介します。適応型huffman符号より圧縮性能が少しだけ劣り、少しだけ遥かに高速らしいっぽいそうですが…。
実際に試してた所、速度については疑問が残ります…。詳細は[作者のpage](http://ezcodesample.com/prefixer/prefixer_article.html)をご覧下さい。
## 実装
例によってJavaScriptで書き殴っておきます。本家とは一味違います。
```js
// log2
function l2b(a,b,c){
	c=(65535<a)<<4,c|=b=(255<(a>>>=c))<<3,c|=b=(15<(a>>=b))<<2;
	return(c|=b=(3<(a>>=b))<<1)|a>>b>>1
}
//this is entropy coder
function Hit(){}
function Sym(){}
function CLen(){}
!function(o,p,q,r){for(;o;r[o]=8)p[q[--o]=o]=0}(256,Hit.prototype,Sym.prototype,CLen.prototype);

function init(cs){
	var i=cs--,p=CLen.prototype;
	for(PolarCode.prototype.ml=cs=l2b(cs)+1;i;)p[--i]=cs
}
/*
@cs: 記号種類
@n: 記号頻度への加算値
@max: 記号頻度最大値
@d: 真ならdecode
*/
function PolarCode(cs,n,max,d){
	if(n)this.n=n;
	if(max)this.max=max;
	this.size=cs;
	this.F=new Hit;
	this.S=new Sym;
	this.Inv=new Sym;
	this.code=new Sym,
	this.cLen=new CLen;
	//for decode only
	if(d)this.shift=[0],this.offset=[0],this.lowC=[0],this.fLen=[cs]
}
PolarCode.prototype={
n:2,cnt:16,max:800,ml:8,tsize:1,asize:16,maxSA:4096,
update:function(v){
	for(var F=this.F,I=this.Inv,S=this.S,p,r=this.n;r--;){
		if(++F[v]>this.max)
			for(i=this.size;i;)F[--i]-=F[i]>>1; // may be F[i]>>=1
		if(p=S[v]){
			for(var n=-1,i=p,f=F[v];i&&f>F[I[--i]];)n=i;
			if(~n)f=S[i=I[p]],S[i]=S[p=I[p]=I[n]],S[p]=f,I[n]=i}}
},
BuildTree:function(d){
	for(var F=[],C=this.F,L=this.Inv,c,l=this.size,n=0,i=l,s=0,p=0,t=1,T;i;p+=F[i]=1<<l2b(t))
		s+=t=C[L[--i]]||1;
	T=1<<l2b(s);
	for(T<<=T<s;t;)for(t=0,i=n;i<l;)
		if(p+F[i]<=T)p+=F[i],F[i++]<<=t=1;
		else n=++i;
	for(C=this.code,L=this.cLen,s=C[0]=i=0;i<l;L[i++]=n){
		for(n=1,t=T,p=F[i];(t>>=1)>p;)++n;
		if(n>s)s=n}
	for(i=1;i<l;)C[i]=C[i-1]+1<<L[i++]-L[i-2];
	if(!d)return;
	for(n=1,--i;i;)L[i]^L[--i]&&++n;
	this.ml=s;this.tsize=n;F=this.fLen,T=this.offset;
	for(c=C[n=p=s=0],t=L[0];i<l;++i)
		if(L[i]^t)
			F[s]=n,this.lowC[s]=c,T[s]=p,
			this.shift[s++]=this.ml-L[i-1],
			n=1,t=L[p=i],c=C[i];
		else++n;
	F[s]=n,this.lowC[s]=c,T[s]=p,this.shift[s]=this.ml-L[--l]
}};
/*
@In: Array. 圧縮元配列
@cs: 記号最大値(0-255)
@up: 記号頻度への加算値(0-15)
@max: 記号頻度最大値(0-15)
@mo: 文脈の次数(0-2)
@done: 終了時のcallback関数. 省略時は圧縮結果を返す関数になる
@rate: 進捗用callback関数
@return: @done実行結果
*/
function POLARe(In,cs,up,max,mo,done,rate){
	PolarCode.prototype.encode=function(c,s){
		s=this.S[c];this.update(c);c=this.code[s];
		for(s=this.cLen[s];s>=b;b=8)O[o++]=B|(1<<b)-1&c>>(s-=b),B=0;
		B|=((1<<s)-1&c)<<(b-=s);
		if(!--this.cnt)
			this.BuildTree(),
			this.cnt=this.asize<<=this.asize<this.maxSA
	};
	var sync="function"!=typeof rate,a=In.length,b=6,B=(mo&=3)<<6,o=3,m=(1<<mo*8)-1,x=0,z=a,O=[a&31,cs&=255,(up&=15)<<4|(max&=15)],P=[];
	done=done||function(O){return O};
	rate=rate||function(){};
	if(!a)return done([0],0,1);
	for(a-=a&31,a/=32;a;a/=256)a-=O[o++]=a&255,O[0]+=32;
	max=++max*100,++up,++cs^256&&init(cs);
	function F(){
		var c,d=sync?-1:4095,p,t=sync?1/0:+new Date;
		for(rate(a,z);a<z&&(a&d||new Date-t<200);p.encode(c=In[a++]),x=x<<8|c)
			p=P[x&=m]||(P[x]=new PolarCode(cs,up,max));
		if(a==z){if(b<8&&B)O[o++]=B;return done(O,a,o)}
		setTimeout(F,0)
	}return F()
}
/*
@In: Array. 伸長元配列
@done: 終了時のcallback関数. 省略時は伸長結果を返す関数になる
@rate: 進捗用callback関数
@return: @done実行結果
*/
function POLARd(In,done,rate){
	PolarCode.prototype.decode=function(p){
		var c=this.ml,i=-1,s=0;
		if(b<c)B=B<<16|In[a++]<<8|In[a++],b+=16;
		for(c=(1<<c)-1&B>>>b-c;;){
			p=(c>>this.shift[++i])-this.lowC[i];
			if(p<this.fLen[i]){
				s=this.Inv[p+this.offset[i]];
				b-=this.ml-this.shift[i];
				break}}
		this.update(s);
		--this.cnt||this.BuildTree(this.cnt=this.asize<<=this.asize<this.maxSA);
		return s
	};
	if(!In[0])return done([],1,0);
	done=done||function(O){return O};
	rate=rate||function(){};
	var sync="function"!=typeof rate,a=In[2],b=In[0],cs=In[1],B=32,y=In.length,z=b&31,m,o=0,x,up=a+16>>4,max=((a&15)+1)*100,P=[],O=[];
	for(a=3,b>>=5;b--;B*=256)z+=In[a++]*B;
	B=In[a++],b=6,m=(1<<(B>>6)*8)-1,++cs^256&&init(cs);
	function F(){
		var d=sync?-1:4095,p,t=sync?1/0:+new Date;
		for(rate(a,y);o<z&&(o&d||new Date-t<200);x=x<<8|(O[o++]=p.decode()))
			p=P[x&=m]||(P[x]=new PolarCode(cs,up,max,1));
		if(o==z)return done(O,y,o);
		setTimeout(F,0)
	}return F()
}
```
codepen実践

<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="XWwzzpW" data-pen-title="Polar Code" data-user="xezz" style="height:300px;box-sizing:border-box;display:flex;align-items:center;justify-content:center;border:2px solid;margin:1em 0;padding:1em"> <span>See the Pen <a href="https://codepen.io/xezz/pen/XWwzzpW">Polar Code</a> by xezz (<a href="https://codepen.io/xezz">@xezz</a>) on <a href="https://codepen.io">CodePen</a>.</span></p><script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>