Last active
August 19, 2020 14:38
-
-
Save tscholl2/bb7a03f71a7e22d2686e1039f285d9a7 to your computer and use it in GitHub Desktop.
Some types of compression in js
This file contains hidden or 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
| (function () { | |
| 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 }; | |
| })() |
This file contains hidden or 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
| (function(){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="",f="";for(let e of o)f=s+(c=t(e)),n.has(f)?s=f:(r.push(n.set(f,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 f=[s];for(let t of r.slice(1))f.push(c=t<n[e]?n[t]:s+s[0]),n.push(s+c[0]),s=c;const l=[];for(let t of f.join(""))l.push(t.codePointAt(0));return new Uint8Array(l)}}})(); |
This file contains hidden or 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
| 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); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment