|
simple deflate code is here.
function HeapSort(p,l){if(l==null)l=p.length;
if(l<2)return;
var i=l>>1,j,k,q;
do{ for(j=i,q=p[--i];;p[j-1]=p[(j=k)-1]){
if((k=j<<1)>l)break;
if(k<l&&p[k]>p[k-1])k++;
if(q>=p[k-1])break}
p[--j]=q}
while(i);
for(;l>3;p[--j]=q){
q=p[--l],j=p[2]>p[1]?3:2,p[l]=p[0];
for(p[0]=p[j-1];;p[j-1]=p[(j=k)-1]){
if((k=j<<1)>l)break;
if(k<l&&p[k]>p[k-1])k++;
if(q>=p[k-1])break}}
q=p[--l],p[l]=p[0];
if(l>1&&p[1]<q)p[0]=p[1],p[1]=q;
else p[0]=q}
function HuffGen(F,P,L,cs,ml){if(!ml)ml=16;
var MaxLen=16,NBITS=10,MASK=(1<<NBITS)-1;
for(var c=0,e=0,f,i=0,l=0,m=1,n=-1,LC=[],NC=[];++n<cs;)
if(f=F[n])P[c++]=n|f<<NBITS;else L[n]=0;
HeapSort(P,c);
if(c<2){if(c)if(!(m=P[0]&MASK))m++;
P[m]=L[P[0]=0]=L[m]=1;return}
do f=P[n=i!=c&&(l===e||P[i]>>NBITS<=P[l]>>NBITS)?i++:l++]&~MASK,
P[n]=P[n]&MASK|e<<NBITS,
f+=P[m=i!=c&&(l===e||P[i]>>NBITS<=P[l]>>NBITS)?i++:l++]&~MASK,
P[m]=P[m]&MASK|e<<NBITS,P[e]=P[e++]&MASK|f;
while(~e+c);
for(i=MaxLen;~i;)LC[i--]=0;
P[--e]&=MASK;
for(LC[1]=2;e>0;LC[l]+=2){
l=P[P[--e]>>NBITS]>>NBITS;
P[e]=P[e]&MASK|++l<<NBITS;
if(l>=ml)for(l=ml;!LC[--l];);
LC[l++]--}
for(;ml;ml--)for(c=LC[ml];c--;)L[P[++i]&MASK]=ml&255;
for(l=c=e=0;l<MaxLen;)NC[++l]=c=c+LC[l-1]<<1;
while(e<cs)P[e]=NC[L[e++]]++|0}
function scanlen(C,P,L){
for(var c=0,i=0,l=C.length,m,n,s=0,v,F=[];i<l;){v=C[i];
for(n=i+1;n<l&&v===C[n];)n++;i+=n-=i;
if(!v){
for(;n>10;n-=m){m=n;
if(m>138)m=138;
C[c]=18,C[~c++]=m-11,s+=7}
if(n>2)C[c]=17,C[~c++]=n-3,n=0,s+=3}
while(n--)
for(C[c++]=v;n>2;n-=m){m=n;
if(m>6)m=6;
C[c]=16,C[~c++]=m-3,s+=3}}
C.length=c,v=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15];
for(i=19;i;)F[--i]=0;
for(m=0;i<c;)F[C[i++]]++;
for(HuffGen(F,P,L,i=n=19,7);n>4&&!L[v[n-1]];n--);L.size=n;
for(;i;)m+=L[--i]*F[i];
return s+m+n*3+14}
function bitcost(L,F){for(var i=L.length,s=0;i;)s+=F[--i]*L[i];return s}
function bitrev(C,L){
for(var c,i=0,l,r;(c=C[i])>-1;C[i++]=r)
for(r=0,l=L[i];r=r<<1|c&1,c>>=1,--l>0;);}
function deflate(A){if(this==window)return new deflate(A);var
LCode=[],LBase=[],LLex=[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0,0,0],
DCode=[],DBase=[],DLex=[0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14],
Order=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15],
fLC=[],fLN=[],fDC=[],fDN=[],dLC=[],dLN=[],dDC=[],dDN=[],hC=[],hL=[],LF=[],DF=[],
BS=1<<16,MO=1<<15,MM=MO-1,MIN=3,MAX=258,CS=288,DS=30,TF=4095,LM=4095,LenFlag=8,LenShift=4,LR=7,
a=0,b=0,B,c=CS,e=0,i=c,l,m,n=MIN,o=0,p,q=0,r,s,t,u=0,v=0,w=0,x=A[0]<<16|A[1]<<8|A[2],z=A.length,eob=z<BS?z:BS,em,now=MO+1,pl=MIN-1,po=0,mch=256,mdef=MAX,ex=0,O=[],Q=[],N={},H={};
this.puts=function(n,c){B|=c<<b;for(b+=n;b>7;b-=8)O[o++]=B&255,B>>=8};
for(;i>280;fLN[i]=8)fLC[--i]=i-88;
for(;i>256;fLN[i]=7)fLC[--i]=i-256;
for(;i>144;fLN[i]=9)fLC[--i]=i+256;
for(;i;fLN[i]=8)fLC[--i]=i+48;
while(c)LF[--c]=0;
while(c<29)for(n=1<<LLex[c],LBase[c++]=i;n--;)LCode[i++]=c+256;
for(c=i=0;c<16;c++)for(n=1<<DLex[c],DBase[c]=i;n--;)DCode[i++]=c;
for(i>>=7;c<DS;c++)for(n=1<<DLex[c]-7,DBase[c]=i<<7;n--;)DCode[i+++256]=c;
for(bitrev(fLC,fLN);c;fDN[c]=5)DF[fDC[--c]=c]=0;
for(bitrev(fDC,fDN);;n=u&LM){
if(!n){for(i=DS;i;)n+=DF[--i]*(DLex[i]+5);
if(n+u*8>>3<a-e>>1&&w<u>>1)n=0}
if((em=a+MAX)>eob||!n){
if(a>=eob||!n){LF[256]=1;
HuffGen(LF,dLC,dLN,i=CS,15),HuffGen(DF,dDC,dDN,t=DS,15);
for(;i>257&&!dLN[i-1];i--);
for(;t>1&&!dDN[t-1];t--);
n=scanlen(s=dLN.slice(0,i).concat(dDN.slice(0,t)),hC,hL)+bitcost(dLN,LF)+bitcost(dDN,DF)+ex,
l=bitcost(fLN,LF)+bitcost(fDN,DF)+ex,
p=a-e,eob=a+BS<z?a+BS:z,this.puts(1,a===z);
if(p*8+40-b<n&&p*8+40-b<l){this.puts(9),
O[o++]=p&255,O[o++]=p>>8,O[o++]=~p&255,O[o++]=~p>>8&255;
for(b=B=0;e<a;)O[o++]=A[e++]}
else{this.puts(2,n<l?2:1);
if(n<l){
bitrev(hC,hL),bitrev(dLC,dLN),bitrev(dDC,dDN);
this.puts(5,i-257),this.puts(5,--t),this.puts(4,hL.size-4);
for(c=0;c<hL.size;)this.puts(3,hL[Order[c++]]);
for(p=-1;(c=s[++p])>-1;){
this.puts(hL[c],hC[c]);
if(c>15)this.puts(c<17?2:c<18?3:7,s[~p])}
i=dLC,r=dLN,s=dDC,t=dDN}
else i=fLC,r=fLN,s=fDC,t=fDN;
if(v)Q[q++]=v,v=0;
for(p=0;p<q;){
if(m=(n=Q[p++])&LR){
while(m--)this.puts(r[c=A[e++]],i[c]);
if(!(n&LenFlag))continue;
l=n>>LenShift,n=Q[p++]}
else if(n&LenFlag)l=n>>LenShift,n=Q[p++];
else l=0,n>>=LenShift;
e+=l+MIN,this.puts(r[c=LCode[l]],i[c]);
if(LLex[c-=257])this.puts(LLex[c],l-LBase[c]);
this.puts(t[c=DCode[n>255?(n>>7)+256:n]],s[c]);
if(DLex[c])this.puts(DLex[c],n-DBase[c])}
this.puts(r[256],i[256])}
if(a===z){for(this.puts(7);!O[--o];)O.length--;return O}
for(c=CS;c;)LF[--c]=0;for(q=u=w=ex=dLN[l="length"]=dDN[l]=hL[l]=dLC[l]=dDC[l]=hC[l]=0;c<DS;)DF[c++]=0}
em=eob}r=pl;
if(a+r<em){c=mch,l=m=0,n=H[x]|0;
if(r>7)c>>=2;
for(i=c;c;n=N[n&MM]|0){p=now-n;
if(p<=l||p>MO)break;
s=a+r,t=a-p+r;
loop:{for(;s>=a;s--){if(A[s]!=A[t])break loop;t--}
t+=r+2;
for(s+=r+2;A[s]===A[t]&&s<em;s++)t++;
r=s-a,m=p-1;
if(s===em||r>i)break}
l=p}}
if(r===MIN&&m>TF)r--,m=0;
if(pl>=r&&pl!=MIN-1){n=pl-MIN;
if(v||n)Q[q++]=v|LenFlag|n<<LenShift,Q[q++]=po;
else Q[q++]=po<<LenShift;
LF[n=LCode[n]]++,ex+=LLex[n-257],u++,
DF[n=DCode[po>255?(po>>7)+256:po]]++,ex+=DLex[n],w++;
r=pl-1,pl=MIN-1,v=0}
else if(r===MIN-1){if(++v===LR)Q[q++]=v,v=0;LF[A[a]]++,u++,r=1}
else{po=m;
if(pl!=MIN-1){if(++v===LR)Q[q++]=v,v=0;LF[A[a-1]]++,u++}
if(r<mdef)pl=r,r=1;
else{n=r-MIN;
if(v||n)Q[q++]=v|LenFlag|n<<LenShift,Q[q++]=po;
else Q[q++]=po<<LenShift;
LF[n=LCode[n]]++,ex+=LLex[n-257],u++,
DF[n=DCode[po>255?(po>>7)+256:po]]++,ex+=DLex[n],w++;
pl=MIN-1,v=0}}
for(;r--;a++){
if(a+MIN<=eob){N[now&MM]=H[x],H[x]=now;
if(a+MIN<eob)x=(x<<8|A[a+MIN])&0xffffff}
now++}}}
-- modified 25-Sep-11 9:32am.
|
|
|
|
|
So tantalizing. I have been searching for exactly this. But the code is incomplete, is it not? There are two mismatched braces, which imply that there should be more code than is shown.
Some provenance for this would be useful.
|
|
|
|
|
base64=new function(){for(var e="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/".split(""),i=64,d=[];i;)d[e[--i]]=i;
this.e=function(A){var s=[],i=0,j=0,n,l=A.length,m=l%3;
while(i<l)s[j++]=e[(n=A[i++]<<16|A[i++]<<8|A[i++])>>18&63]+e[n>>12&63]+e[n>>6&63]+e[n&63];
if(m)for(s[--j]=s[j].substr(0,s[j].length-(m=3-m));m--;)s[j]+="=";
return s.join("")}
,this.d=function(s){var A=[],i=0,j=0,l=(s=s.replace(/[^A-Za-z\d\+\/]/g,"")).length,m=l&3,n;
while(i<l)A[j++]=(n=d[s.charAt(i++)]<<18|d[s.charAt(i++)]<<12|d[s.charAt(i++)]<<6|d[s.charAt(i++)])>>16,A[j++]=n>>8&255,A[j++]=n&255;
A.length-=[0,0,2,1][m];
return A}}
//example
document.write(base64.e([0,1,2,3]),"<br>",base64.d("AAECAw=="))
|
|
|
|
|
I had already written ByteArrays and Base64 in JavaScript but I have been trying to get to grips with RFC 1950 / 1951 and not getting very far. So, your implementation will help a lot.
Nice work!
|
|
|
|
|
the result is great, the only thing left is the speed
Regards,
unruledboy (at) gmail (dot) com
|
|
|
|
|