Last active
October 18, 2019 08:22
-
-
Save bryc/f1c0f28ae850d347f91bead9565e2876 to your computer and use it in GitHub Desktop.
proof of concept tiny compression
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// tiny simple hash (TSH) | |
TSH=s=>{for(var i=0,h=6,c=5;i<s.length;)h=Math.imul(h^s[i],9**9),c=Math.imul(c^s[i++],7**9);return 2**32*(2097151&(c^c>>>9))+(h^h>>>9)} | |
// LZB minified 512 bytes. | |
LZB={e:(e,f)=>{for(var r,l,o,i,s,a=0,g=0,h=128,n=[],t=e.length;a<t;)if(256==(h<<=1)&&(h=1,l=g,f[g++]=0),a>t-3)f[g++]=e[a++];else if(i=a-n[s=66*e[a]^33*e[a+1]^e[a+2]]&1023,n[s]=a,(r=a-i)!=a&&e[a]==e[r]&&e[a+1]==e[r+1]&&e[a+2]==e[r+2]){for(o=3;o<66&&e[a+o]==e[r+o];o++);a+=o,f[l]|=h,f[g++]=o-3<<2|i>>8,f[g++]=i&255}else f[g++]=e[a++]},d:(e,f)=>{for(var r,l,o,i=0,s=0,a=128;i<e.length;)if(256==(a<<=1)&&(a=1,l=e[i++]),l&a)for(r=s-(1023&(e[i]<<8|e[i+1])),o=3+(e[i]>>2),i+=2;o>0;o--)f[s++]=f[r++];else f[s++]=e[i++]}} | |
var sum = [], packed = [], unpacked = [], data = [0,0,0,0,0,0,0,0,9,0,255,79,127,191,191,191,143,5,4,7,129,0,0,0,0,0,0,0,0,0,3,1,0,0,0,1,0,103,60,84,47,53,27,26,30,2,0,0,0,0,0,0,68,65,7,109,0,0,0,0,0,0,0,0,9,0,255,79,127,191,191,191,143,5,4,7,129,0,0,0,0,0,0,0,0,0,3,1,0,0,0,1,0,103,60,84,47,53,27,26,30,2,0,0,0,0,0,0,68,65,7,109,0,0,0,0,0,0,0,0,0,0,0,1,32,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,68,65,0,168,0,0,0,0,0,0,0,0,0,0,0,1,32,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,68,65,0,168,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,68,65,0,133,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,68,65,0,133,10,1,11,99,3,219,2,65,31,16,255,207,127,255,255,255,255,127,127,127,255,127,255,127,207,255,127,129,1,1,3,1,1,1,1,129,0,118,132,104,116,136,109,117,113,105,102,115,119,102,110,109,68,65,23,19,10,1,11,99,3,219,2,65,31,16,255,207,127,255,255,255,255,127,127,127,255,127,255,127,207,255,127,129,1,1,3,1,1,1,1,129,0,118,132,104,116,136,109,117,113,105,102,115,119,102,110,109,68,65,23,19,42,169,85,89,0,0,0,0,21,86,170,166,63,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0,72,73,7,9,42,169,85,89,0,0,0,0,21,86,170,166,63,255,255,255,0,0,0,0,0,0,0,0,0,0,0,0,72,73,7,9]; | |
sum[0] = TSH(data); | |
LZB.e(data, packed); | |
LZB.d(packed, unpacked); | |
sum[1] = TSH(unpacked); | |
console.log("Original/Compressed size", data.length, packed.length); | |
console.log("Hash compare", sum[0]===sum[1], sum[0].toString(16).toUpperCase(), sum[1].toString(16).toUpperCase()); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Original source for reference. This is a slightly modified version of LZJB. Essentially the hashtable differs. | |
LZB = { | |
e: (I, out) => { | |
var S = 0, D = 0, C, cmp, cmk = 128, i, ofs, hp, tbl = [], len = I.length; | |
while (S < len) { | |
if ((cmk <<= 1) == 256) { cmk = 1, cmp = D, out[D++] = 0; } | |
if (S > len-3) { out[D++] = I[S++]; continue; } | |
hp = ((I[S]*66) ^ (I[S+1]*33) ^ I[S+2]); // simplified hashcode | |
ofs = S-tbl[hp] & 1023; | |
tbl[hp] = S; | |
C = S - ofs; | |
if (C != S && I[S] == I[C] && I[S+1] == I[C+1] && I[S+2] == I[C+2]) { | |
for(i = 3; i < 66 && I[S+i] == I[C+i]; i++); S += i; | |
out[cmp] |= cmk; | |
out[D++] = i-3 << 2 | ofs >> 8; | |
out[D++] = ofs & 255; | |
} else { out[D++] = I[S++]; } | |
} | |
}, | |
d: (I, out) => { | |
var S = 0, D = 0, C, cmp, cmk = 128, i; | |
while (S < I.length) { | |
if ((cmk <<= 1) == 256) { cmk = 1, cmp = I[S++]; } | |
if (cmp & cmk) { | |
C = D - ((I[S]<<8 | I[S+1]) & 1023); | |
i = (I[S]>>2) + 3; | |
S = S + 2; | |
for(; i > 0; i--) { out[D++] = out[C++]; } | |
} else { out[D++] = I[S++]; } | |
} | |
} | |
}; | |
// Original LZJB | |
// This version matches output of https://github.com/cscott/lzjb/blob/master/doc/compress.c | |
var LZJB = { | |
e: (I) => { | |
var out = [], S = 0, D = 0, C, cmp, cmk = 128, i, ofs, hp, tbl = [], len = I.length; | |
while (S < len) { | |
if ((cmk <<= 1) == 256) { cmk = 1, cmp = D, out[D++] = 0; } | |
if (S > len-3) { out[D++] = I[S++]; continue; } | |
hp = I[S] << 16 | I[S+1] << 8 | I[S+2]; | |
hp ^= hp >> 9; hp = (I[S] ^ hp + (hp >> 5)) & 1023; | |
ofs = S-tbl[hp] & 1023; | |
tbl[hp] = S; | |
C = S - ofs; | |
if (C != S && I[S] == I[C] && I[S+1] == I[C+1] && I[S+2] == I[C+2]) { | |
for(i = 3; i < 66 && I[S+i] == I[C+i]; i++); S += i; | |
out[cmp] |= cmk; | |
out[D++] = i-3 << 2 | ofs >> 8; | |
out[D++] = ofs & 255; | |
} else { out[D++] = I[S++]; } | |
} | |
return out; | |
}, | |
d: (I) => { | |
var out = [], S = 0, D = 0, C, cmp, cmk = 128, i; | |
while (S < I.length) { | |
if ((cmk <<= 1) == 256) { cmk = 1, cmp = I[S++]; } | |
if (cmp & cmk) { | |
C = D - ((I[S]<<8 | I[S+1]) & 1023); | |
i = (I[S]>>2) + 3; | |
S = S + 2; | |
for(; i > 0; i--) { out[D++] = out[C++]; } | |
} else { out[D++] = I[S++]; } | |
} | |
return out; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment