Skip to content

Instantly share code, notes, and snippets.

@tscholl2

tscholl2/LZW.js

Last active August 19, 2020 14:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tscholl2/bb7a03f71a7e22d2686e1039f285d9a7 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tscholl2/bb7a03f71a7e22d2686e1039f285d9a7 to your computer and use it in GitHub Desktop.
Download ZIP
Some types of compression in js
Raw
LZW.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 };
})()
Raw
LZW.min.js
(()=>{const t=String.fromCodePoint,e="length";return{compress:function(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:function(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)}}})();
Raw
png.js
async function encode(input) {
// TODO: handle unicode?
const canvas = document.createElement("canvas");
canvas.width = Math.ceil(Math.sqrt(input.length / 3));
canvas.height = canvas.width;
const ctx = canvas.getContext('2d');
const imgData = ctx.createImageData(canvas.width, canvas.height);
for (let i = 0, j = 0; i < 7; i++)
imgData.data[i] = i % 4 == 3 ? 255 : (input.length >>> (8 * j++)) & 0xff;
for (let i = 7, j = 0; i < 4 * canvas.width * canvas.height; i++)
imgData.data[i] = i % 4 == 3 ? 255 : input.charCodeAt(j++) || 0;
ctx.putImageData(imgData, 0, 0);
return canvas.toDataURL('image/png', 0);
}
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; i < 7; i++)
length |= i % 4 == 3 ? 0 : (imgData.data[i] << (8 * j++));
let output = "";
for (let i = 7; i < imgData.data.length; i++)
output += i % 4 == 3 ? "" : String.fromCharCode(imgData.data[i]);
return output.substr(0, length);
}
Raw
png.min.js
(()=>{return{encode:async function(t){const e=document.createElement("canvas");e.width=Math.ceil(Math.sqrt(t.length/3)),e.height=e.width;const a=e.getContext("2d"),n=a.createImageData(e.width,e.height);for(let e=0,a=0;e<7;e++)n.data[e]=e%4==3?255:t.length>>>8*a++&255;for(let a=7,h=0;a<4*e.width*e.height;a++)n.data[a]=a%4==3?255:t.charCodeAt(h++)||0;return a.putImageData(n,0,0),e.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=e.height;const n=a.getContext("2d");n.drawImage(e,0,0);const h=n.getImageData(0,0,e.width,e.height);let o=0;for(let t=0,e=0;t<7;t++)o|=t%4==3?0:h.data[t]<<8*e++;let d="";for(let t=7;t<h.data.length;t++)d+=t%4==3?"":String.fromCharCode(h.data[t]);return d.substr(0,o)}}});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment