概要
file圧縮でお馴染みのLZMA。2000年代に入り、登場して以来それはどの家庭にも転がっている程度に普及し、これ無しには生活できない程になりませんでした。
実装編
LZMA-JSを書き直して高速化しようという魂胆が丸出しかどうかは定かではないかもしれません。その本家はBigIntもどきを模倣しているような実装のせいで、それなりに速度が犠牲になっています。そういうのは排除します。
それからobjectや整数が要素のArrayをTypedeArrayに置き換える事でも高速化。
ちなみに本記事の実装ではheaderが9 bytes分欠落しているので、真の本家LZMA SDKとは互換性がありません。ついでに-eosも常に有効という仕様です。
const LZMA=function(){
"use strict";
const doComp=1,doDecomp=2,doProgress=3,wait="function"===typeof setImmediate?setImmediate:"function"===typeof wait0?wait0:setTimeout,
Fp=function(A){
for(var i=A[1]=1,j,c=2;i<21;)for(j=1<<(++i>>1)-1;j--;)A[c++]=i;
return A}(new Uint8Array(2048)),
CRC=function(A){
for(var i=256,j,r;i;A[i]=r)for(r=--i,j=8;j--;)r&1?r=r>>>1^-306674912:r>>>=1;
return A}(new Uint32Array(256)),
PP=function(p,i,j,k){for(;i;)for(j=1<<9-i--,k=1<<9-i;j<k;)p[j]=(i<<6)+(k-j++<<6>>8-i);return p}(new Uint16Array(512),9);
function updateProgress(rate,cbn){
postMessage({action:doProgress,cbn:cbn,result:rate})
}
function getc(I){return I[I.pos++]}
function Stream(){
this.Stock=[];
this.Save=new Uint8Array((this.split=1023)+1);
this.Bc=this.bc=0
}
function write(O){
if(O.Bc)
O.Stock.push(O.Save.subarray(0,O.Bc)),O.Bc=0,
O.Save=new Uint8Array(1024)
}
function writes(O,B,o,l){
write(O);
O.Stock.push(new Uint8Array(B.subarray(o,o+l)));
O.bc+=l
}
function toU8a(O){
write(O);
for(var i=0,p=0,A=new Uint8Array(O.bc),B;B=O.Stock[i++];p+=B.length)A.set(B,p);
return A
}
function put(O,b){
O.bc++;
O.Save[O.Bc++]=b;
O.Bc<O.split||write(O)
}
function SetModel(P,n){
for(;n;P.C[n]=P.size)setPrices(P,--n,P.size,P.P,n*272)
}
function Compressor(data,mode){
var e=new Encoder,op=e.Rc.srm=e.output=new Stream,l=1<<(mode.s&31)%19+12,h=65536,i=data.length,P=new Uint8Array(5);
if(i<l)l=i;
for(i=0;l>1<<i;)++i;
e.dts=i*2;e.fb=(mode.f&511)%271+3;e.ftype=mode.m;
e.lp=mode.lp%5&7;
e.lc=mode.lc%9&15;
e.pb=mode.pb%5&7;
e.pm=(1<<e.pb)-1;
e.LitModel=new LitCoder(e.lp,e.lc);
P[0]=(e.pb*5+e.lp)*9+e.lc&255;
for(i=4;i;)P[i--]=l>>8*i;
writes(op,P,0,5);op.Bc=-1;
i=e.ftype?4:2,P=e.lzM={HASH_ARRAY:i>2,o:0,p:0,cp:0,sp:0,eof:0};
if(i>2)P.hn=0,P.min=4,P.hs=66560;
else P.hn=2,P.min=3,P.hs=0;
if(l<1073741567){
P.lmax=i=e.fb;
P.cv=16+(mode.depth||i>>1);
P.S=new Int32Array((P.cbs=l+1)*2);
if(P.HASH_ARRAY)
h=l-1,h|=h>>1,h|=h>>2,h|=h>>4,h|=h>>8,h>>=1,h|=65535,
h>16777216&&(h>>=1),
P.hm=h++,
h+=P.hs;
P.H=new Int32Array(P.hs2=h);
P.ksb=l+=4096;
P.ksa=i+=274;
P.p2lsp=l+=(l+i>>>1)+256;
P.B=new Uint8Array(P.bs=l+i)
}
setDistCost(e),
setAlignCost(e),
e.Len.size=e.RepMLen.size=e.fb-1,
SetModel(e.Len,1<<e.pb),
SetModel(e.RepMLen,1<<e.pb),
e.alive=1,e.srm=data;
data.pos=0;l=data.bc=e.size=data.length;
if(l<-1||l>=0x100000000)throw new Error("invalid length"+l);
return e
}
function Decompressor(data){
var d=new Decoder,l=0,i=0,P=d.W;
if(!data.subarray)data=new Uint8Array(data);
data.pos=0;
data.bc=data.length;
for(;i<5;P[i++]=r){
r=getc(data);
if(r==-1)throw new Error("truncated input")
}
var n=P[0],r=n/9|0,lc=n%9,lp=r%5,pb=r/5|0;
for(i=4;i;)l+=P[i--]<<i*8;
//NOTE:If the input is bad,it might call for an insanely large dictionary size,which would crash the script.
if(l>99999999||l<0||lc>8||lp>4||pb>4)throw new Error("corrupted input");
d.LitModel=new LitCoder(lp,lc);
Create(d.Len,n=1<<pb);
Create(d.RepLen,n);
d.m=n-1;
P.B=new Uint8Array(P.ws=Math.max(d.ds2=Math.max(d.ds=l,1),4096));
d.size=d.alive=1;
d.Rc.srm=data;
d.W.srm=d.output=new Stream;
for(i=4;i--;)n=n<<8|getc(data);d.Rc.Code=n>>>0;
return d
}
function BitTree(n){
var P=new Int16Array(1<<n).fill(1024);P.bn=n;
return P
}
function Create(P,n){
for(P.ps=n;n;P.M[n]=BitTree(3))P.L[--n]=BitTree(3)
}
function LitCoder(lp,lc){
this.m=(1<<lp)-1;this.pb=lc;
for(var i=1<<lc+lp,a=new Int16Array(i*768).fill(1024),b=0;i;)this[--i]=a.subarray(b,b+=768)
}
function LenCoder(){
this.F=new Int16Array([1024,1024]);
this.L=[];this.M=[];this.H=BitTree(8)
}
function LenPriceCoder(){
LenCoder.call(this);
for(var i=16;i;this.M[i]=BitTree(3))this.L[--i]=BitTree(3);
this.P=[];this.C=[]
}
function Model(){
var a=new Int16Array(546).fill(1024),i=192;
this.Match=a.subarray(0,i);
this.Rep0Long=a.subarray(i,i+=192);
this.Pos=a.subarray(i,i+=114);
this.Rep=a.subarray(i,i+=12);
this.Rep0=a.subarray(i,i+=12);
this.Rep1=a.subarray(i,i+=12);
this.Rep2=a.subarray(i);
this.PosSlot=[];
this.PosAlign=BitTree(i=4);
for(;i;)this.PosSlot[--i]=BitTree(6)
}
function Encoder(i){
this.Rc={Range:-1,Low:0,p:0,n:this.ftype=1,c:0};
this.R=new Int32Array(4);
this.RepDist=new Int32Array(4);
this.RepLen=new Int32Array(4);
this.RepMLen=new LenPriceCoder;
this.Len=new LenPriceCoder;
this.Dist=new Int32Array(548);
this.SlotPrice=new Int32Array(256);
this.DistPrice=new Int32Array(512);
this.AlignPrice=new Int32Array(16);
this.Prices=new Int32Array(128);
this.O={State:new Int8Array(i=4096),Prev1IsChar:new Int8Array(i),Prev2:new Int8Array(i),Price:new Uint32Array(i),PosPrev:new Uint32Array(i),PosPrev2:new Uint32Array(i),BackPrev:new Int32Array(i),BackPrev2:new Uint32Array(i),Backs:new Uint32Array(i*4)};
this.longest=this.dn=this.backRes=this.Done=this.now=this.s=this.pc=this.foundBest=this.optEnd=this.optIdx=this.ao=0
Model.call(this)
}
function Decoder(){
this.W={p:0,sp:0};
this.Rc={Range:-1,Code:0};
this.Len=new LenCoder;
this.RepLen=new LenCoder;
this.s=this.r0=this.r1=this.r2=this.r3=this.now=this.pc=0
Model.call(this)
}
function flush(M,n){
if(n=M.p-M.sp)writes(M.srm,M.B,M.sp,n),M.p<M.ws||(M.p=0),M.sp=M.p
}
function processDecoderChunk(d){
var result=CodeOneChunk(d);
if(result==-1)throw new Error("corrupted input");
if(result)
flush(d.W),
d.W.srm=d.Rc.srm=d.alive=0
}
function processEncoderChunk(e){
CodeOneBlock(e);
if(e.done)
e.Rc.srm=e.alive=0
}
function decLen(P,Rc,s){
return dBit(Rc,P.F,0)?dBit(Rc,P.F,1)?16+dBits(P.H,Rc):8+dBits(P.M[s],Rc):dBits(P.L[s],Rc)
}
function CodeOneChunk(D){
var Rc=D.Rc,W=D.W,P,b,c,d,i,l,n,p,s=D.now&D.m;
if(dBit(Rc,D.Match,(D.s<<4)+s)){
if(dBit(Rc,D.Rep,D.s)){
if(dBit(Rc,D.Rep0,D.s)){
if(dBit(Rc,D.Rep1,D.s)){
if(dBit(Rc,D.Rep2,D.s))d=D.r3,D.r3=D.r2;
else d=D.r2;
D.r2=D.r1
}else d=D.r1;
l=0;D.r1=D.r0;D.r0=d
}else if(l=!dBit(Rc,D.Rep0Long,(D.s<<4)+s))
D.s=D.s<7?9:11
if(!l)
l=decLen(D.RepLen,Rc,s)+2,
D.s=D.s<7?8:11
}else{
D.r3=D.r2;D.r2=D.r1;D.r1=D.r0;
l=decLen(D.Len,Rc,s)+2;
D.s=D.s<7?7:10;
p=dBits(D.PosSlot[l<6?l-2:3],Rc);
if(p>3){
n=p>>1;c=p;p=(2|p&1)<<--n;
if(c<14){i=0;P=D.Pos;s=p+~c;
for(c=1;i<n;c+=c+b)b=dBit(Rc,P,s+c),p+=b<<i++
}else{
for(c=i=0;3<--n;c+=c-b)
Rc.Range>>>=1,
b=Rc.Code-Rc.Range>>>31,
Rc.Code-=Rc.Range&--b,
Rc.Range>>24||(Rc.Range*=256,Rc.Code=(Rc.Code<<8|getc(Rc.srm))>>>0);
P=D.PosAlign;n=P.bn;
for(s=1;i<n;s+=s+b)b=dBit(Rc,P,s),p+=b<<i++;
p+=c<<4;if(p<0)return p>-2?1:-1
}
}D.r0=p
}
if(D.r0>=D.now||D.r0>=D.ds2)return-1;
p=W.p+~D.r0;if(p<0)p+=W.ws;
for(D.now+=l;l--;W.p<W.ws||flush(W)){
if(p>=W.ws)p=0;
W.B[W.p++]=W.B[p++]
}
p=W.p-1;if(p<0)p+=W.ws;
D.pc=W.B[p]
}else{
d=D.LitModel;c=1;
d=d[((D.now&d.m)<<d.pb)+(D.pc>>8-d.pb)]
if(D.s<7)
for(;(c+=c+dBit(Rc,d,c))<256;);
else{
p=W.p+~D.r0;if(p<0)p+=W.ws;p=W.B[p];
do{
n=p>>7&1;p<<=1;
l=dBit(Rc,d,(1+n<<8)+c);
c+=c+l;
if(n^l){
while(c<256)c+=c+dBit(Rc,d,c);
break
}
}while(c<256)
}
W.B[W.p++]=D.pc=c&255;
W.p<W.ws||flush(W);
i=D.s;D.s=4>i?0:10>i?i-3:i-6;
D.now++
}
}
function ReadBlock(M){
if(!M.eof)for(var l,S=M.srm;l=M.bs-M.sp-M.o;){
if(S.pos>=S.bc){
M.l=M.sp;l=M.o+M.l;
if(l>M.p2lsp)M.l=M.p2lsp-M.o;
return M.eof=1
}
l=Math.min(l,S.bc-S.pos);
M.B.set(S.subarray(S.pos,S.pos+=l),M.o+M.sp);
M.sp+=l;
if(M.sp>=M.p+M.ksa)M.l=M.sp-M.ksa
}
}
//NOTE:This is only called after reading one whole gigabyte.
function NormalizeLinks(I,n,v,i){for(;n;I[n]=i>v?i-v:0)i=I[--n]}
function movePos(M,o){
++M.cp<M.cbs||(M.cp=0);
if(++M.p>M.l){
if(M.o+M.p>M.p2lsp)
o=M.o+M.p-M.ksb,o>0&&--o,
M.B.set(M.B.subarray(o,M.o+M.sp),0),
M.o-=o;
ReadBlock(M)
}
if(M.p>1073741822)
NormalizeLinks(M.S,M.cbs*2,o=M.p-M.cbs),
NormalizeLinks(M.H,M.hs2,o),
M.o+=o,M.l-=o,M.p-=o,M.sp-=o
}
function Skip(B,M,n){
var a,b,c,m,cp,h,l,max,mp,p,p0,p1,H=M.H,S=M.S;
do{
if((max=M.lmax)>M.sp){
max=M.sp-M.p;
if(max<M.min){movePos(M);continue}
}
(mp=M.p-M.cbs)<0&&(mp=0);c=M.o+M.p;
if(M.HASH_ARRAY)
h=CRC[B[c]]^B[c+1],
H[h&1023]=M.p,
h^=B[c+2]<<8,
H[1024+(h&65535)]=M.p,
h=(h^CRC[B[c+3]]<<5)&M.hm;
else h=B[c]^B[c+1]<<8;
m=H[h+=M.hs];H[h]=M.p;
p0=M.cp<<1;p1=p0++;
a=b=M.hn;
for(h=M.cv;;){
if(m<=mp||!h--){S[p0]=S[p1]=0;break}
cp=M.cp-M.p+m;cp<0&&(cp+=M.cbs);cp+=cp;
p=M.o+m;l=a<b?a:b;
if(B[p+l]===B[c+l]){
while(++l<max&&B[p+l]===B[c+l]);
if(l===max){
S[p1]=S[cp];
S[p0]=S[cp+1];
break
}
}
if(B[p+l]<B[c+l])S[p1]=m,m=S[p1=cp+1],b=l;
else S[p0]=m,m=S[p0=cp],a=l
}movePos(M)
}while(--n)
}
function Backward(e,c,O){
var bc,bm=O.BackPrev[e.optEnd=c],pm=O.PosPrev[c],pp;
do{
if(O.Prev1IsChar[c]){
O.BackPrev[pm]=-1;
O.Prev1IsChar[pm]=0
O.PosPrev[pm]=pm-1;
if(O.Prev2[c])
O.Prev1IsChar[pm-1]=0,
O.PosPrev[pm-1]=O.PosPrev2[c],
O.BackPrev[pm-1]=O.BackPrev2[c]
}
bc=bm;
bm=O.BackPrev[pp=pm];
pm=O.PosPrev[pp];
O.PosPrev[pp]=c;
O.BackPrev[c=pp]=bc
}while(c>0);
e.backRes=O.BackPrev[0];
return e.optIdx=O.PosPrev[0]
}
function eFlush(e,p){
var r=e.Rc;p&=e.pm,
eBit(r,e.Match,(e.s<<4)+p,1),
eBit(r,e.Rep,e.s,0),
e.s=e.s<7?7:10,
eBits0(e.Len,r,0,p),
eBits2(e.PosSlot[0],r,63),
eBits3(r,67108863,26),
eBitsR(e.PosAlign,r,15);
for(p=5;p--;)ShiftLow(r);
e=r.srm.Save;
for(p=r.srm.Bc;r.srm.bc--,p&&!e[--p];)r.srm.Bc--
}
function CodeOneBlock(e){
var D=e.Dist,Rc=e.Rc,M=e.lzM,O=e.O,B=M.B,cs,b,c,d,i,l,l2ps,p,s,ps,start=e.now;
e.done=1;
if(e.srm)
M.srm=e.srm,
ReadBlock(M),
M.o--,M.l++,M.p++,M.sp++,
e.srm=0;
if(e.Done)return;
e.Done=1;
if(!e.now&&M.sp^M.p)
MatchDist(e,B,D,M),
eBit(Rc,e.Match,0,0),
eBits1(e.LitModel[0],Rc,e.pc=B[0]),
--e.ao,e.now++;
if(M.sp==M.p)return eFlush(e,e.now);
for(;;){
l=GetOptimum(e,e.now,B,D,M,O);
p=e.backRes;
ps=e.now&e.pm;
cs=(e.s<<4)+ps;
if(l<2&&p<0){
eBit(Rc,e.Match,cs,0);
s=B[M.o+M.p-e.ao];
p=GetSubCoder(e.LitModel,e.now,e.pc);
if(e.s<7)eBits1(p,Rc,s);
else for(i=8,c=l2ps=1,cs=B[M.o+M.p-e.ao+~e.RepDist[0]];i;c+=c+b){
b=s>>--i&1;d=c;
if(l2ps)ps=cs>>i&1,d+=1+ps<<8,l2ps=ps===b;
eBit(Rc,p,d,b)}
e.pc=s;
i=e.s;e.s=4>i?0:10>i?i-3:i-6
}else{
eBit(Rc,e.Match,cs,1);eBit(Rc,e.Rep,e.s,i=p<4);
if(i){
eBit(Rc,e.Rep0,e.s,p);
if(!p)eBit(Rc,e.Rep0Long,cs,l>1);
else{eBit(Rc,e.Rep1,e.s,i=p>1);
i&&eBit(Rc,e.Rep2,e.s,p-2);
for(d=e.RepDist[p];p;)e.RepDist[p]=e.RepDist[--p];e.RepDist[p]=d}
if(l<2)e.s=e.s<7?9:11;
else eBits0(e.RepMLen,Rc,l-2,ps),e.s=e.s<7?8:11
}else{
e.s=e.s<7?7:10;p-=4;
eBits0(e.Len,Rc,l-2,ps);
eBits2(e.PosSlot[l2ps=l<6?l-2:3],Rc,s=2048>p?Fp[p]:2097152>p?Fp[p>>10]+20:Fp[p>>20]+40);
if(s>3){
i=s>>1;b=(2|s&1)<<--i;d=p-b;
if(s<14)eBitsR2(e.Pos,b+~s,Rc,i,d);
else++e.apc,eBits3(Rc,d>>4,i-4),
eBitsR(e.PosAlign,Rc,d&15)
}
for(i=3;i;)e.RepDist[i]=e.RepDist[--i];
e.RepDist[0]=p;++e.mpc
}
e.pc=B[M.o+M.p+l+~e.ao]
}
e.ao-=l;e.now+=l;
if(!e.ao){
e.mpc>127&&setDistCost(e);
e.apc>15&&setAlignCost(e);
if(M.sp==M.p)return eFlush(e,e.now);
if(e.now-start>4095)return e.Done=e.done=0
}
}
}
function setAlignCost(e){
for(var i=16,b,c,n,p,s,P=e.PosAlign;i;e.AlignPrice[i]=p)
for(n=P.bn,c=1,p=0,s=--i;n--;c+=c+b)b=s&1,p+=PP[(P[c]-b^-b)>>2&511],s>>>=1;
e.apc=0
}
function setDistCost(e){
for(var l=e.dts,b,c,f,i=4,n,p,s,P=e.Pos;i<128;e.Prices[i++]=p)
for(p=Fp[i],f=p>>1,s=(2|p&1)<<--f,n=s+~p,s=i-s,c=1,p=0;f--;c+=c+b)b=s&1,s>>>=1,p+=PP[(P[n+c]-b^-b)>>2&511];
for(P=e.SlotPrice;f<3;){
s=++f<<6;c=e.PosSlot[f];
for(i=l;i;)P[s+--i]=getPrice2(c,i);
for(p=14;p<l;)P[s+p]+=(p++>>1)-5<<6;
for(p=f<<7;i<4;)e.DistPrice[p+i]=P[s+i++];
for(;i<128;)e.DistPrice[p+i]=P[s+Fp[i]]+e.Prices[i++]
}e.mpc=0
}
function GetMatch(B,M,i,d,l){
if(M.eof&&M.p+i+l>M.sp)l=M.sp-M.p-i;
var p=M.o+M.p+i;d=p+~d;
for(i=0;i<l&&B[p++]===B[d++];)i++;
return i
}
function MatchDist(e,B,D,M){
var a=0,b=0,c,cp,d,h,i=M.p,l,m,max=M.lmax,mp,ml=1,o=0,p,p0,p1,H,S;
if(i+max>M.sp){
max=M.sp-i;
if(max<M.min){
movePos(M);
++e.ao;return e.dn=0
}
}
mp=i>M.cbs?i-M.cbs:0;
c=M.o+i;
if(M.HASH_ARRAY)
h=CRC[B[c]]^B[c+1],a=h&1023,
h^=B[c+2]<<8,b=h&65535,
h=(h^CRC[B[c+3]]<<5)&M.hm;
else h=B[c]^B[c+1]<<8;
H=M.H;m=H[h+=M.hs];
if(M.HASH_ARRAY){
p=H[a];l=H[1024+b];
H[a]=H[1024+b]=i;
if(p>mp&&B[M.o+p]===B[c])
D[o++]=ml=2,D[o++]=i+~p;
if(l>mp&&B[M.o+l]===B[c]){
if(l===p)o-=2;p=l;
D[o++]=ml=3;D[o++]=i+~l
}
if(o&&m===p)o-=2,ml=1
}
S=M.S;H[h]=i;
p0=M.cp<<1;p1=p0++;
a=b=M.hn;
if(M.hn&&m>mp&&B[M.o+m+M.hn]^B[c+M.hn])
D[o++]=ml=M.hn,D[o++]=i+~m;
for(h=M.cv;;){
if(m<=mp||!h--){
S[p0]=S[p1]=0;
break
}
d=i-m;
cp=M.cp-d;cp<0&&(cp+=M.cbs);cp+=cp;
p=M.o+m;l=a<b?a:b;
if(B[p+l]===B[c+l]){
while(++l<max&&B[p+l]===B[c+l]);
if(ml<l){
D[o++]=ml=l;D[o++]=d-1;
if(l===max){
S[p1]=S[cp];S[p0]=S[cp+1];
break}
}
}
if(B[p+l]<B[c+l])S[p1]=m,m=S[p1=cp+1],b=l;
else S[p0]=m,m=S[p0=cp],a=l
}
movePos(M);
if(e.dn=o){o=D[o-2];
if(o===e.fb)o+=GetMatch(B,M,o-1,D[e.dn-1],273-o)
}
++e.ao;return o
}
function GetOptimum(e,p,B,D,M,O){
if(e.optEnd^e.optIdx){
p=O.PosPrev[e.optIdx]-e.optIdx;
e.backRes=O.BackPrev[e.optIdx];
e.optIdx=O.PosPrev[e.optIdx];
return p
}
var a,b,c=3,d,c1p,clp,cb,i=4,l,lx,m,mp,nl,bn,bn2,dn,o,pp,ps,ps2,rmp,rmp2,sl,s,s2,R=e.R,iM;
e.optIdx=e.optEnd=0;
if(e.foundBest)s=e.longest,e.foundBest=0;
else s=MatchDist(e,B,D,M);
bn=M.sp-M.p+1;
if(bn<2){e.backRes=-1;return 1}
if(bn>273)bn=273;
for(dn=e.dn;i;)if((e.RepLen[--i]=GetMatch(B,M,-1,R[i]=e.RepDist[i],273))>e.RepLen[c])c=i;
if(e.RepLen[c]>=e.fb){
l=e.RepLen[e.backRes=c];
if(l>1)Skip(B,M,l-1),e.ao+=l-1;
return l
}
if(s>=e.fb){
e.backRes=D[dn-1]+4;
if(s>1)Skip(B,M,s-1),e.ao+=s-1;
return s
}
b=B[a=M.o+M.p-1];
m=B[a+~e.RepDist[0]];
if(s<2&&b^m&&e.RepLen[c]<2){
e.backRes=-1;
return 1
}
var{State,Prev1IsChar,Prev2,Price,PosPrev,PosPrev2,BackPrev,BackPrev2,Backs}=O;
State[0]=e.s;
ps=p&e.pm;iM=e.Match;
Price[1]=PP[iM[(e.s<<4)+ps]>>>2]+getPrice(GetSubCoder(e.LitModel,p,e.pc),e.s>6,m,b);
BackPrev[1]=-1;
Prev1IsChar[1]=0;
mp=PP[2048-iM[(e.s<<4)+ps]>>>2];
rmp=mp+PP[2048-e.Rep[e.s]>>>2];
if(m===b){
i=rmp+PP[e.Rep0[i=e.s]>>>2]+PP[e.Rep0Long[(i<<4)+ps]>>>2];
if(i<Price[1])
Price[1]=i,BackPrev[1]=Prev1IsChar[1]=0
}
lx=e.RepLen[c],s<lx||(lx=s);
if(lx<2){
e.backRes=BackPrev[1];
return 1
}
PosPrev[1]=0;
Backs[0]=R[0];
Backs[1]=R[1];
Backs[2]=R[2];
Backs[3]=R[3];
for(l=lx;Price[l]=268435455,--l>1;);
for(i=-1;i<3;)if((c=e.RepLen[++i])>1){
b=rmp+getPrice4(e,i,e.s,ps);
do{
clp=b+e.RepMLen.P[ps*272+c-2];
if(clp<Price[c])
Price[c]=clp,
PosPrev[c]=Prev1IsChar[c]=0,
BackPrev[c]=i;
}while(--c>1)
}
pp=mp+PP[e.Rep[e.s]>>>2];
l=e.RepLen[0],l>1?++l:l=2;
if(l<=s){
for(i=0;l>D[i];)i+=2;
for(;;++l){
clp=pp+getPrice3(e,d=D[i+1],l,ps);
if(clp<Price[l])
Price[l]=clp,
PosPrev[l]=Prev1IsChar[l]=0,
BackPrev[l]=d+4;
if(l===D[i]&&(i+=2)===dn)break
}
}
for(c=0;;){
if(++c===lx)return Backward(e,c,O);
nl=MatchDist(e,B,D,M);
if(nl>=e.fb){
e.longest=nl;
e.foundBest=1;
return Backward(e,c,O)
}
dn=e.dn;
pp=PosPrev[c];
if(Prev1IsChar[c])--pp,s=Prev2[c]?(s=State[PosPrev2[c]],BackPrev2[c]<4?s<7?8:11:s<7?7:10):State[pp],s=4>s?0:10>s?s-3:s-6;
else s=State[pp];
if(pp===c-1)s=BackPrev[c]?4>s?0:10>s?s-3:s-6:s<7?9:11;
else{
if(Prev1IsChar[c]&&Prev2[c])
pp=PosPrev2[c],
i=BackPrev2[c],
s=s<7?8:11;
else s=(i=BackPrev[c])<4?s<7?8:11:s<7?7:10;
pp*=4;
if(i>3)R[0]=i-4,R[1]=Backs[pp],R[2]=Backs[pp+1],R[3]=Backs[pp+2];
else if(!i)R[0]=Backs[pp],R[1]=Backs[pp+1],R[2]=Backs[pp+2],R[3]=Backs[pp+3];
else if(i<2)R[0]=Backs[pp+1],R[1]=Backs[pp],R[2]=Backs[pp+2],R[3]=Backs[pp+3];
else if(i<3)R[0]=Backs[pp+2],R[1]=Backs[pp],R[2]=Backs[pp+1],R[3]=Backs[pp+3];
else R[0]=Backs[pp+3],R[1]=Backs[pp],R[2]=Backs[pp+1],R[3]=Backs[pp+2]
}
State[c]=s;
Backs[o=c*4]=R[0];
Backs[o+1]=R[1];
Backs[o+2]=R[2];
Backs[o+3]=R[3];
b=B[a=M.o+M.p-1];
m=B[a+~R[0]];
ps=++p&e.pm;
mp=Price[c];
c1p=mp+PP[iM[(s<<4)+ps]>>>2]+getPrice(GetSubCoder(e.LitModel,p,B[a-1]),s>6,m,b);
if(sl=c1p<Price[o=c+1])
Price[o]=c1p,
PosPrev[o]=c,
BackPrev[o]=-1,
Prev1IsChar[o]=0;
mp+=PP[2048-iM[(s<<4)+ps]>>>2];
rmp=mp+PP[2048-e.Rep[s]>>>2];
if(m===b&&!(PosPrev[o]<c&&!BackPrev[o])){
i=rmp+PP[e.Rep0[s]>>>2]+PP[e.Rep0Long[(s<<4)+ps]>>>2];
if(i<=Price[o])
Price[o]=i,
PosPrev[o]=sl=c,
BackPrev[o]=Prev1IsChar[o]=0
}
bn2=M.sp-M.p+1;
bn=4095-c<bn2?bn2=4095-c:bn2;
if(bn<2)continue;
if(bn>e.fb)bn=e.fb;
if(!sl&&m^b&&(m=GetMatch(B,M,0,R[0],Math.min(bn2-1,e.fb)))>1){
s2=4>s?0:10>s?s-3:s-6;
ps2=p+1&e.pm;
rmp2=c1p+PP[2048-iM[(s2<<4)+ps2]>>>2]+PP[2048-e.Rep[s2]>>>2];
for(b=c-~m;lx<b;)Price[++lx]=268435455;
rmp2+=e.RepMLen.P[ps2*272+m-2]+getPrice4(e,0,s2,ps2);
if(rmp2<Price[b])
Price[b]=rmp2,
PosPrev[b]=c+1,
BackPrev[b]=Prev2[b]=0,
Prev1IsChar[b]=1
}
for(i=-1,sl=2;i<3;)if((l=GetMatch(B,M,-1,R[++i],bn))>1){
b=l;
do{
for(o=c+b;lx<o;)Price[++lx]=268435455;
clp=rmp+e.RepMLen.P[ps*272+b-2]+getPrice4(e,i,s,ps);
if(clp<Price[o])
Price[o]=clp,
PosPrev[o]=c,
BackPrev[o]=i,
Prev1IsChar[o]=0
}while(--b>1);
if(!i)sl=l+1;
if(l<bn2&&(m=GetMatch(B,M,l,R[i],Math.min(bn2+~l,e.fb)))>1){
s2=s<7?8:11;
ps2=p+l&e.pm;
rmp2=rmp+e.RepMLen.P[ps*272+l-2]+getPrice4(e,i,s,ps)+PP[iM[(s2<<4)+ps2]>>>2]+getPrice(GetSubCoder(e.LitModel,p+l,B[a+l-1]),1,B[a+l+~R[i]],B[a+l]);
s2=4>s2?0:10>s2?s2-3:s2-6;
ps2=p+l+1&e.pm;
rmp2+=PP[2048-iM[(s2<<4)+ps2]>>>2]+PP[2048-e.Rep[s2]>>>2];
for(b=l-~m+c;lx<b;)Price[++lx]=268435455;
rmp2+=e.RepMLen.P[ps2*272+m-2]+getPrice4(e,0,s2,ps2);
if(rmp2<Price[b])
Price[b]=rmp2,
PosPrev[b]=c+l+1,
BackPrev[b]=0,
Prev1IsChar[b]=Prev2[b]=1,
PosPrev2[b]=c,
BackPrev2[b]=i
}
}
if(nl>bn){
for(dn=0;bn>D[dn];)dn+=2;
D[dn]=nl=bn;dn+=2
}
if(nl>=sl){
for(pp=mp+PP[e.Rep[s]>>>2];lx<c+nl;)Price[++lx]=268435455;
for(i=0;sl>D[i];)i+=2;
for(l=sl;;++l){
o=c+l;clp=pp+getPrice3(e,cb=D[i+1],l,ps);
if(clp<Price[o])Price[o]=clp,PosPrev[o]=c,BackPrev[o]=cb+4,Prev1IsChar[o]=0;
if(l===D[i]){
if(l<bn2&&(m=GetMatch(B,M,l,cb,Math.min(bn2+~l,e.fb)))>1){
s2=s<7?7:10;
ps2=p+l&e.pm;
rmp2=clp+PP[iM[(s2<<4)+ps2]>>>2]+getPrice(GetSubCoder(e.LitModel,p+l,B[a+l-1]),1,B[a+l+~cb],B[a+l]);
s2=4>s2?0:10>s2?s2-3:s2-6;
ps2=p+l+1&e.pm;
rmp2+=PP[2048-iM[(s2<<4)+ps2]>>>2]+PP[2048-e.Rep[s2]>>>2];
for(b=l-~m+c;lx<b;)Price[++lx]=268435455;
rmp2+=e.RepMLen.P[ps2*272+m-2]+getPrice4(e,0,s2,ps2);
if(rmp2<Price[b])
Price[b]=rmp2,
PosPrev[b]=c+l+1,
BackPrev[b]=0,
Prev1IsChar[b]=Prev2[b]=1,
PosPrev2[b]=c,
BackPrev2[b]=cb+4
}
if((i+=2)===dn)break
}
}
}
}
}
function GetSubCoder(P,p,pc){
return P[((p&P.m)<<P.pb)+(pc>>8-P.pb)]
}
function eBit(Rc,P,i,s){
var p=P[i],n=(Rc.Range>>>11)*p;
if(s)Rc.Low+=n,Rc.Range-=n,P[i]-=p>>5;
else Rc.Range=n,P[i]+=2048-p>>5;
Rc.Range>>24||ShiftLow(Rc,Rc.Range<<=8)
}
function eBits0(P,Rc,s,p,b){
eBit(Rc,P.F,0,b=s>7),
b?(eBit(Rc,P.F,1,b=s>15),b?eBits2(P.H,Rc,s-16):eBits2(P.M[p],Rc,s-8)):eBits2(P.L[p],Rc,s),
--P.C[p]||(setPrices(P,p,P.size,P.P,272*p),P.C[p]=P.size)}
function eBits1(P,Rc,s){
for(var i=8,b,c=1;i;c+=c+b)eBit(Rc,P,c,b=s>>--i&1)
}
function eBits2(P,Rc,s){
for(var i=P.bn,b,c=1;i;c+=c+b)eBit(Rc,P,c,b=s>>>--i&1)
}
function eBits3(Rc,v,n,r){
for(;n;){r=Rc.Range>>>=1;
if(v>>>--n&1)Rc.Low+=r;
r>>24||ShiftLow(Rc,Rc.Range<<=8)
}
}
function eBitsR(P,Rc,s){
for(var i=P.bn,b,c=1;i--;c+=c+b)eBit(Rc,P,c,b=s&1),s>>=1
}
function eBitsR2(P,i,Rc,n,s){
for(var b,c=1;n--;c+=c+b)eBit(Rc,P,i+c,b=s&1),s>>=1
}
function dBit(Rc,P,i){
var p=P[i],n=(Rc.Range>>>11)*p>>>0;
if(Rc.Code<n)Rc.Range=n,P[i]+=2048-p>>5,p=0;
else Rc.Range-=n,Rc.Code-=n,P[i]-=p>>5,p=1;
Rc.Range>>24||(Rc.Range*=256,Rc.Code=(Rc.Code<<8|getc(Rc.srm))>>>0);
return p
}
function dBits(P,Rc){
for(var i=P.bn,b=i,c=1;i--;)c+=c+dBit(Rc,P,c);
return c^1<<b
}
function getPrice(P,m,mb,s){
var i=8,b,c=1,p=0;
if(m)for(;i;){
m=mb>>--i&1;b=s>>i&1;
p+=PP[(P[(1+m<<8)+c]-b^-b)>>2&511];
c+=c+b;
if(m^b)break}
for(;i;c+=c+b)b=s>>--i&1,p+=PP[(P[c]-b^-b)>>2&511];
return p
}
function getPrice2(P,s){
for(var i=P.bn,b,c=1,p=0;i;c+=c+b)b=s>>>--i&1,p+=PP[(P[c]-b^-b)>>2&511];
return p
}
function getPrice3(e,p,l,s){
var lp=l<6?l-2:3;
return(p<128?e.DistPrice[lp*128+p]:e.SlotPrice[(lp<<6)+(131072>p?Fp[p>>6]+12:134217728>p?Fp[p>>16]+32:Fp[p>>26]+52)]+e.AlignPrice[p&15])+e.Len.P[s*272+l-2];
}
function getPrice4(e,i,s,p){
if(!i)return PP[e.Rep0[s]>>>2]+PP[2048-e.Rep0Long[(s<<4)+p]>>>2];
p=PP[2048-e.Rep0[s]>>>2];
return p+=i<2?PP[e.Rep1[s]>>>2]:PP[2048-e.Rep1[s]>>>2]+PP[(e.Rep2[s]-i+2^-i+2)>>2&511];
}
function setPrices(P,p,n,Q,s){
for(var i=0,a=PP[P.F[0]>>>2],b=PP[2048-P.F[0]>>>2];i<8;Q[s+i]=a+getPrice2(P.L[p],i++))
if(i>=n)return;
for(a=b+PP[P.F[1]>>>2];i<16;Q[s+i]=a+getPrice2(P.M[p],i++-8))
if(i>=n)return;
for(b+=PP[2048-P.F[1]>>>2];i<n;)Q[s+i]=b+getPrice2(P.H,i++-16)
}
function ShiftLow(Rc){
var c,h=0;
if(Rc.Low<0xFF000000||(h=Rc.Low>0xffffffff)){
for(c=Rc.c;put(Rc.srm,c+h),--Rc.n;)c=255;
Rc.c=Rc.Low>>>24
}
++Rc.n;Rc.Low=Rc.Low<<8>>>0
}
function compress(A,mode,onDone,onDoing){
var C=Compressor(A.buffer?A:new Uint8Array(A),mode<9?getMode(mode):mode),u,sync=onDone===u&&onDoing===u,
cbn;// A callback number should be supplied instead of onDone()if we are using Web Workers.
if("function"!==typeof onDone)cbn=onDone,onDone=onDoing=0;
onDoing=onDoing||function(rate){
if(cbn!==u)return updateProgress(rate,cbn)
};
onDone=onDone||function(r,e){
if(cbn!==u)return postMessage({action:doComp,cbn:cbn,result:r,error:e})
};
if(sync){
while(processEncoderChunk(C),C.alive);
return toU8a(C.output)
}
try{onDoing(0,0,0)}catch(e){return onDone(null,e)}
function doAction(){
try{
for(var s=+new Date;processEncoderChunk(C),C.alive;)
// If about 200 miliseconds have passed,update the progress.
if(Date.now()-s>200){
onDoing(s=C.now,C.size);
return wait(doAction,0)
}
onDoing(C.now,C.size);s=toU8a(C.output);
// delay so we don't catch errors from the onDone handler
wait(onDone.bind(u,s,C.size,s.length),0)
}catch(e){onDone(u,e)}
}
//NOTE:We need to wait to make sure it is always async.
wait(doAction,0)
}
function decompress(A,onDone,onDoing){
var D=Decompressor(A),S=D.Rc.srm,u,hasProgress,len,sync=onDone===u&&onDoing===u,
cbn;// A callback number should be supplied instead of onDone()if we are using Web Workers.
if("function"!==typeof onDone)cbn=onDone,onDone=onDoing=0;
onDoing=onDoing||function(rate){
if(cbn!==u)return updateProgress(hasProgress?rate:-1,cbn)
};
onDone=onDone||function(r,e){
if(cbn!==u)return postMessage({action:doDecomp,cbn:cbn,result:r,error:e})
};
if(sync){
while(processDecoderChunk(D),D.alive);
return toU8a(D.output)
}
try{
len=S.bc;
//NOTE:If the data was created via a stream,it will not have a length value,and therefore we can't calculate the progress
hasProgress=len>-1;
onDoing(0,0,0)
}catch(e){return onDone(null,e)}
function doAction(){
try{
for(var s=+new Date,i=0;processDecoderChunk(D),D.alive;)
if(!(++i&1023)&&Date.now()-s>100){
hasProgress&&onDoing(S.pos,len);
return wait(doAction,0)
}
onDoing(S.pos,len);s=toU8a(D.output);
wait(onDone.bind(u,s,S.pos,s.length),0) // delay so we don’t catch errors from the onDone handler
}catch(e){onDone(u,e)}
}
wait(doAction,0) //NOTE:We need to wait to make sure it is always async.
}
var getMode=function(){
var modes=[
{s:16,f:64,m:0},// dictionarySize, fastByte, matchFinder, lc:3, lp:0, pb:2
{s:20,f:64,m:0},
{s:19,f:64,m:1},
{s:20,f:64,m:1},
{s:21,f:128,m:1},
{s:22,f:128,m:1},
{s:23,f:128,m:1},
{s:24,f:255,m:1},
{s:25,f:255,m:1}];
return function(n){return modes[n]||modes[6]}
}();
// If we're in a Web Worker,create the onmessage() communication channel
//NOTE:This seems to be the most reliable way to detect this
if(typeof onmessage!="undefined"&&(typeof window=="undefined"||typeof window.document=="undefined"))
// Create the global onmessage function
onmessage=function(e){
if(e&&e.data)
e.data.action==doDecomp?
LZMA.decompress(e.data.data,e.data.cbn):
e.data.action==doComp&&
LZMA.compress(e.data.data,e.data.mode,e.data.cbn)
};
return{compress:compress,decompress:decompress}}()
関数の説明的解説
// 圧縮処理
LZMA.compress(A,mode,onDone,onDoing)
- A: 圧縮元配列(
Array/Uint8Array) - mode: 圧縮設定
//objectの場合 { s: 辞書のbit数(0-30) m: 最長一致検索法(0-1) f: 最長一致の成功とみなす長さ(0-270)。小さいと高速、大きいと高圧縮かも lc: literal符号化の文脈として使用する前のbyteの上位bitの数(0-8) lp: literal_pos_stateに含める辞書位置の下位bit数(0-4) pb: pos_stateに含める辞書位置の下位bit数(0-4) depth: 探索深度(0-0xffffffff)。大きくなるにつれ低速化 } //数値の場合 0-8。定義済みの設定が指定される。上記のs, m, fが増減、他は固定 - onDone: 後処理の関数
- 第一引数: 圧縮された配列
- 第二引数: error発生時に受け取った文字列
// example function(result){ console.log(result) }
- onDoing: 進捗処理の関数
- 第一引数: 進捗位置
- 第二引数: 終端位置
// example function(index,last){ console.log(index/last,"%") }
- return:
onDoneとonDoingがundefinedの場合、同期処理となり、圧縮された配列を返却
// 展開処理
LZMA.decompress(A,onDone,onDoing)
- A: 圧縮された配列(
Array/Uint8Array) - onDone: 後処理の関数
- 第一引数: 展開された配列
- 第二引数: error発生時に受け取った文字列
// example function(result){ console.log(result) }
- onDoing: 進捗処理の関数
- 第一引数: 進捗位置
- 第二引数: 終端位置
// example function(index,last){ console.log(index/last,"%") }
- return:
onDoneとonDoingがundefinedの場合、同期処理となり、展開された配列を返却
利用例
const data=Uint8Array.from({length:3e6},(a,b)=>b);
// 非同期
LZMA.compress(data,2,a=>console.log(a.length))
LZMA.compress(data,2,a=>console.log(a.length),(a,b)=>console.log((a/b*1e4|0)/100,"%"))
// 同期
var a=LZMA.compress(data,2)
console.log(a.length)
a=LZMA.compress(data,{lc:8,lp:0,pb:0})
console.log(a.length)
codepenで遊んでみる。
See the Pen LZMA compressor by xezz (@xezz) on CodePen.
参考文献
- 本家様と互換性がある小型decoder
- LZMA at Wikipedia
- LZMA at Wikipedia(日本語)