Skip to content

Instantly share code, notes, and snippets.

@bryc
Last active October 18, 2019 08:22
Show Gist options
  • Save bryc/f1c0f28ae850d347f91bead9565e2876 to your computer and use it in GitHub Desktop.
Save bryc/f1c0f28ae850d347f91bead9565e2876 to your computer and use it in GitHub Desktop.
proof of concept tiny compression
// 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());
// 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