Skip to content

Instantly share code, notes, and snippets.

@tscholl2
Last active Aug 19, 2020
Embed
What would you like to do?
Some types of compression in js
(() => {
const fcp = String.fromCodePoint;
const L = "length";
/**
* @param {Uint8Array} input
* @returns {Uint8Array}
*/
function compress(input) {
const codewords = [];
const dictionary = new Map();
for (let i = 0; i < 256; i++)
dictionary.set(fcp(i), i);
let buf = "", next = "", bufnext = "";
for (let x of input) {
next = fcp(x);
bufnext = buf + next;
if (dictionary.has(bufnext))
buf = bufnext;
else {
codewords.push(dictionary.set(bufnext, dictionary.size).get(buf));
buf = next;
}
}
codewords.push(dictionary.get(buf));
return ((input) => {
/**
* Condenses a byte array into an array of numbers.
* @param {Uint32Array} input
* @returns {Uint8Array}
*/
const max = input.reduce((p = 0, n) => n > p ? n : p);
const bits = 1 + Math.floor(Math.log2(max));
const output = new Uint8Array(1 + 4 + Math.ceil(input[L] * bits / 8));
output[0] = bits;
for (let i = 0; i < 4; i++)
output[1 + i] = (input[L] >> (i * 8)) & 0xff;
for (let i = 0; i < input[L]; i++)
for (let j = 0; j < bits; j++) {
const k = 8 * 5 + (i * bits + j);
output[k >> 3] |= (1 << ((k % 8))) * ((input[i] >> j) & 1);
}
return output;
})(codewords);
}
/**
* @param {Uint8Array} input
* @returns {Uint8Array}
*/
function decompress(input) {
const codewords = ((input) => {
/**
* Uncondenses a byte array into an array of numbers.
* @param {Uint8Array} input
* @returns {Uint32Array}
*/
const bits = input[0];
const length = input.slice(1, 5).reverse().reduce((p, n) => (p << 8) | n, 0);
const output = new Uint32Array(length);
for (let i = 0; i < input[L]; i++)
for (let j = 0; j < bits; j++) {
const k = 8 * 5 + (i * bits + j);
output[i] |= (1 << j) * ((input[k >> 3] >> (k % 8)) & 1);
}
return output;
})(input);
const dictionary = [];
for (let i = 0; i < 256; i++)
dictionary.push(fcp(i));
let prev = dictionary[codewords[0]], next = "";
const values = [prev];
for (let k of codewords.slice(1)) {
values.push(next = k < dictionary[L] ? dictionary[k] : prev + prev[0]);
dictionary.push(prev + next[0]);
prev = next;
}
const output = [];
for (let c of values.join(""))
output.push(c.codePointAt(0));
return new Uint8Array(output);
}
return { compress, decompress };
})()
(()=>{const t=String.fromCodePoint,e="length";return{compress:(o)=>{const r=[],n=new Map;for(let e=0;e<256;e++)n.set(t(e),e);let s="",c="",l="";for(let e of o)l=s+(c=t(e)),n.has(l)?s=l:(r.push(n.set(l,n.size).get(s)),s=c);return r.push(n.get(s)),(t=>{const o=t.reduce((t=0,e)=>e>t?e:t),r=1+Math.floor(Math.log2(o)),n=new Uint8Array(5+Math.ceil(t[e]*r/8));n[0]=r;for(let o=0;o<4;o++)n[1+o]=t[e]>>8*o&255;for(let o=0;o<t[e];o++)for(let e=0;e<r;e++){const s=40+(o*r+e);n[s>>3]|=(1<<s%8)*(t[o]>>e&1)}return n})(r)},decompress:(o)=>{const r=(t=>{const o=t[0],r=t.slice(1,5).reverse().reduce((t,e)=>t<<8|e,0),n=new Uint32Array(r);for(let r=0;r<t[e];r++)for(let e=0;e<o;e++){const s=40+(r*o+e);n[r]|=(1<<e)*(t[s>>3]>>s%8&1)}return n})(o),n=[];for(let e=0;e<256;e++)n.push(t(e));let s=n[r[0]],c="";const l=[s];for(let t of r.slice(1))l.push(c=t<n[e]?n[t]:s+s[0]),n.push(s+c[0]),s=c;const f=[];for(let t of l.join(""))f.push(t.codePointAt(0));return new Uint8Array(f)}}})();
/**
* Encode takes a string as input, encodes it as UTF8
* then embeds it into a PNG which has builtin compression.
* @param {string} input
* @returns {Promise<string>}
*/
async function encode(input) {
const bytes = new TextEncoder("utf-8").encode(input);
const canvas = document.createElement("canvas");
canvas.width = Math.ceil(Math.sqrt(bytes.length / 3 + 2));
canvas.height = canvas.width;
const ctx = canvas.getContext('2d');
const imgData = ctx.createImageData(canvas.width, canvas.height);
for (let i = 0, j = 0; j < 4; i++)
imgData.data[i] = i % 4 == 3 ? 255 : (bytes.length >> (8 * j++)) & 0xff;
for (let i = 5, j = 0; i < 4 * canvas.width * canvas.height; i++)
imgData.data[i] = i % 4 == 3 ? 255 : bytes[j++] || 0;
ctx.putImageData(imgData, 0, 0);
return canvas.toDataURL('image/png', 0);
}
/**
* Reverse of encode.
* @param {string} input
* @returns {Promise<string>}
*/
async function decode(input) {
const image = new Image();
image.src = input;
await new Promise(r => image.onload = r);
const canvas = document.createElement("canvas");
canvas.width = image.width;
canvas.height = image.height;
const ctx = canvas.getContext('2d');
ctx.drawImage(image, 0, 0);
const imgData = ctx.getImageData(0, 0, image.width, image.height);
let length = 0;
for (let i = 0, j = 0; j < 4; i++)
length |= i % 4 == 3 ? 0 : (imgData.data[i] << (8 * j++));
const output = imgData.data
.filter((_, i) => i > 4 && i % 4 != 3)
.slice(0, length)
return new TextDecoder("utf-8").decode(output);
}
(()=>{return{encode:async function(t){const e=new TextEncoder("utf-8").encode(t),a=document.createElement("canvas");a.width=Math.ceil(e.length/3+2),a.height=1;const n=a.getContext("2d"),c=n.createImageData(a.width,1);for(let t=0,a=0;a<4;t++)c.data[t]=t%4==3?255:e.length>>8*a++&255;for(let t=5,n=0;t<4*a.width;t++)c.data[t]=t%4==3?255:e[n++]||0;return n.putImageData(c,0,0),a.toDataURL("image/png",0)},decode:async function(t){const e=new Image;e.src=t,await new Promise(t=>e.onload=t);const a=document.createElement("canvas");a.width=e.width,a.height=1;const n=a.getContext("2d");n.drawImage(e,0,0);const c=n.getImageData(0,0,e.width,1);let o=0;for(let t=0,e=0;e<4;t++)o|=t%4==3?0:c.data[t]<<8*e++;const d=c.data.filter((t,e)=>e>4&&e%4!=3).slice(0,o);return new TextDecoder("utf-8").decode(d)}}})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment