2c:null 2d:["$","title",null,{"children":"LZ78 compressed B64 | Job van der Zwan | Observable"}] 32:Tbfe,LZ78 = ({ compress(bytes) { // assumes bytes is not empty and less than 4 GiB, // uses Elias Gamma encoding to store the length const byteBits = 32 - Math.clz32(bytes.length); if (!byteBits) return new Uint8Array(0); const stream = new ByteStream(); stream.strOut(0, byteBits - 1); stream.strOut(bytes.length, byteBits); const dictionary = new Trie(); // Dictionary always has these "escape" tokens: // 0 - "stop" token, // 1 - "new byte" token let dictSize = 2, node = null, byte = bytes[0], i = 0; while (i < bytes.length) { if (node = dictionary.get(byte)) { // known substring, go to end of it while (++i < bytes.length) { byte = bytes[i]; const nextNode = node.get(byte); if (!nextNode) break; node = nextNode; } stream.phaseOut(node.val, dictSize); node.addNode(byte, dictSize++); } else { // new byte, emite + add new byte to dictionary. stream.phaseOut(1, dictSize); stream.strOut(byte, 8); node = dictionary.addNode(byte, dictSize++); // if we reach the end of the bytes array this will never be accessed anyway byte = ++i < bytes.length ? bytes[i] : 0x100; node.addNode(byte, dictSize++); } } // write end-of-stream marker stream.phaseOut(0, dictSize++); stream.flush(); return stream.stream.sliceTA(); }, decompress(compressedBytes){ const stream = new ByteStream(compressedBytes); let bits = 0; while(!stream.strIn(1) && bits < 33) bits++; if (bits > 32) throw new Error ("Elias Gamma decoding fail"); const length = (1 << bits) + stream.strIn(bits); const bytes = new Uint8Array(length); if (!length) return bytes; // word index and word length let wIdx = 0, wLength = 0; // dictionary consists of index, length pairs. Since tokens zero and one are // "escape" tokens they are stored as NaN values. const indices = [NaN, NaN]; const lengths = [NaN, NaN]; let i = 0; while (i < length) { let val = stream.phaseIn(indices.length); if (val === 0) { // end of stream token ++i; if (i !== length) throw new Error(`decompressed size mismatch. i: ${i}, length: ${length}`); break; } else if (val === 1) { // new byte token bytes[i] = stream.strIn(8); // add byte to dictionary, then add byte + next byte indices.push(i, i); lengths.push(1, 2); wIdx = i; wLength = 1; } else { // known dictionary word token const byteStart = i; wIdx = indices[val]; wLength = lengths[val]; for (let j = 0; j < wLength; j++) { bytes[byteStart + j] = bytes[wIdx + j]; } // update word starting index, and add starting index of word + 1 indices[val] = indices[indices.length] = wIdx = byteStart; lengths[lengths.length] = wLength + 1; } i += wLength; } return bytes; } })33:T110c,// Demonstration of a stream object that generates an array of bytes. // Can be used in a variant of LZString, for example class ByteStream { constructor(bytes) { this.stream = new CircularU8(bytes && bytes.length); if (bytes) { for (let i = 0, {data} = this.stream; i < bytes.length; i++) data[i] = bytes[i]; } this.valOut = 0; this.remainingOutBits = 8; this.valInPos = 0; this.valIn = 0; this.remainingInBits = 0; } clear() { this.stream.data.fill(0); this.stream.length = 0; this.valOut = 0; this.remainingOutBits = 8; this.valInPos = -1; this.valIn = 0; this.remainingInBits = 0; return this; } getNextVal() { return this.stream.data[this.valInPos++]; } /** * @param {number} value * @param {number} valueBits */ strOut(value, valueBits) { // First handle all bits that fill up valOut and move to the next // char in the stream until all the remaining value bits fit in valOut if (valueBits > this.remainingOutBits) { valueBits -= this.remainingOutBits; let valueChunk = value >>> valueBits; this.valOut = this.valOut | valueChunk; this.stream.push(this.valOut); // while there are more valueBits left than can be fit into // a full charCode, stream bit by charCode sized chunks while (valueBits >= 8) { valueBits -= 8; this.stream.push((value >>> valueBits) & 0xFF); } this.valOut = 0; this.remainingOutBits = 8; } // At this point valueBits < remainingvalOutBits. If there are bits left // to stream, put them into valOut if (valueBits > 0) { var valueMask = (1 << valueBits) - 1; this.remainingOutBits -= valueBits; this.valOut = this.valOut | ((value & valueMask) << this.remainingOutBits); } // if we filled up our valOut, stream it. if (this.remainingOutBits === 0) { this.stream.push(this.valOut); this.valOut = 0; this.remainingOutBits = 8; } return this; } flush() { if (this.remainingOutBits < 8) { this.stream.push(this.valOut); this.valOut = 0; this.remainingOutBits = 8; } return this; } /** * @param {number} valueBits */ strIn(valueBits) { // Move to next valIn value if this one is finished if (this.remainingInBits === 0) { this.remainingInBits = 8; this.valIn = this.getNextVal(); } // // only get a valIn if still inside data // if (streamIdx >= this.stream.length) return null; let value = 0; // while more bits are asked than current valIn has remaining, // put bit chunks into the output value and get new char values if (valueBits > this.remainingInBits) { let valueMask = (1 << this.remainingInBits) - 1; valueBits -= this.remainingInBits; this.remainingInBits = 8; value = (this.valIn & valueMask) << valueBits; while (valueBits > 8) { valueBits -= 8; value = value | (this.getNextVal() << valueBits); } this.valIn = this.getNextVal(); } // If there are still required bits left, get them from valIn // Note: valueBits < remainingBits is ensured due to above if+while section if (valueBits > 0) { let valueMask = (1 << valueBits) - 1; this.remainingInBits -= valueBits; value = value | ((this.valIn >>> this.remainingInBits) & valueMask); } return value; } /** * @param {number} value * @param {number} totalValues */ phaseOut(value, totalValues) { value = value; let valueBits = 32 - Math.clz32(totalValues - 1); const nextPow2 = (1 << valueBits) >>> 0; // Once we have this power of two we can determine the treshold value. // Any value below the treshold will require one fewer bit. const treshold = nextPow2 - totalValues; if (value < treshold) { valueBits--; } else { value += treshold; } this.strOut(value, valueBits); return this; } /** * @param {number} totalValues */ phaseIn(totalValues) { const valueBits = 32 - Math.clz32(totalValues - 1); const nextPow2 = (1 << valueBits) >>> 0; const treshold = nextPow2 - totalValues; let value = this.strIn(valueBits - 1); if (value >= treshold) value = ((value << 1) + this.strIn(1) - treshold) >>> 0; return value; } }34:Tb82,// Stripped version of my circular typed array generator // (since we don't need pop/shift/unshift/etc) function makeCircularPrototype(arrayConstructor, name) { // Using a computed property lets us give a custom name // to a generated prototype. const { [name]: circularTA } = { [name]: function (length, capacity) { if (length === undefined) length = 0; if (!Number.isInteger(length) || length < 0) throw new Error("length must be a positive integer"); // Force capacity to a power of two, because using bitmasks for modulo is faster if (capacity === undefined) capacity = Math.max(16, 2 ** Math.ceil(Math.log2(length + 1))); else capacity = 2 ** (Math.ceil(Math.log2(capacity))); if (!Number.isInteger(capacity) || capacity < length) throw new Error("Initial capacity must be a positive integer equal or greater to length"); const data = new arrayConstructor(capacity); this.data = data; this.length = length; this.offset = 0; } }; circularTA.from = function (array) { const cta = new circularTA(array.length); for (let i = 0; i < array.length; i++) { cta.data[i] = array[i]; } return cta; }; Object.assign(circularTA.prototype, { push(...args) { if (args.length === 0) args = [0]; this.maybeGrow(args.length); let { length } = this; const mod = this.data.length - 1; for (const val of args) { this.data[(this.offset + length++) & mod] = val; } return (this.length += args.length); }, slice(begin = 0, end = this.length) { begin = Math.max(begin | 0, 0); end = Math.min(end | 0, this.length); const ret = []; const { offset, data } = this; const mod = data.length - 1; for (let i = begin; i < end; i++) { ret.push(data[(i + offset) & mod]); } return circularTA.from(ret); }, // copy a typed array from the data sliceTA(begin = 0, end = this.length) { begin = Math.max(begin | 0, 0); end = Math.min(end | 0, this.length); const ret = []; const { offset, data } = this; const mod = data.length - 1; for (let i = begin; i < end; i++) { ret.push(data[(i + offset) & mod]); } return arrayConstructor.from(ret); }, maybeGrow(newLength) { if (newLength + this.length > this.data.length) { const { data, length, offset } = this; const nData = new arrayConstructor(data.length * 2); const mod = data.length - 1; for (let i = 0; i < length; i++) { nData[i] = data[(i + offset) & mod]; } this.data = nData; this.offset = 0; } }, [Symbol.iterator]: function* () { const { data, length, offset } = this; const mod = data.length - 1; for (let i = 0; i < length; i++) { yield data[(i + offset) & mod]; } } }); return circularTA; }35:[] 30:{"id":"83949b341a52c742","slug":null,"title":"LZ78 compressed B64","thumbnail":"c26d219edebbf8cd899ba45c26875b31d2bb9d29f0c1c11d272d8ab682e9d599","access_level":"unlisted","create_time":"$D2023-01-18T13:39:59.610Z","update_time":"$D2023-01-18T15:06:34.772Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024"},"version":152,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}],"members":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"LZ78 compressed B64","cells":[{"id":0,"value":"# LZ78 compressed B64","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":115,"value":"lzb64 = ({\n compress: string => u8ArrToB64(LZ78.compress(utf.encode(string))),\n decompress: string => utf.decode(LZ78.decompress(b64toU8array(string)))\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"UriSafeChars = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-\".split(\"\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"charToU6 = {\n const t = {};\n UriSafeChars.map((char, i) => t[char.charCodeAt(0)] = i);\n return t;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"function u8ArrToB64(bytes) {\n const u6 = new Uint8Array(Math.ceil(bytes.length * 4 / 3))\n let i = 0, b0 = 0, b1 = 0, b2 = 0;\n let str = \"\";\n while (i + 3 < bytes.length) {\n b0 = bytes[i];\n b1 = bytes[i+1];\n b2 = bytes[i+2];\n str +=\n UriSafeChars[(b0 >> 2) & 63] +\n UriSafeChars[((b0 << 4) + (b1 >> 4)) & 63] +\n UriSafeChars[((b1 << 2) + (b2 >> 6)) & 63] +\n UriSafeChars[b2 & 63];\n i += 3;\n }\n\n b0 = i < bytes.length ? bytes[i] : 0;\n b1 = i + 1 < bytes.length ? bytes[i + 1] : 0;\n b2 = i + 2 < bytes.length ? bytes[i + 2] : 0;\n str +=\n UriSafeChars[(b0 >> 2) & 63] +\n UriSafeChars[((b0 << 4) + (b1 >> 4)) & 63] +\n UriSafeChars[((b1 << 2) + (b2 >> 6)) & 63] +\n UriSafeChars[b2 & 63];\n\n return str;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"function b64toU8array(str) {\n const u6 = utf.encode(str);\n // this might result in extra zeroes at the end, which are ignored by the decompressor\n const u8 = new Uint8Array(Math.ceil(u6.length * 3 / 4));\n let j = 0, i = 0, u6_0 = 0, u6_1 = 0, u6_2 = 0, u6_3 = 0;\n while (j + 4 < u6.length) {\n u6_0 = charToU6[u6[j]];\n u6_1 = charToU6[u6[j+1]];\n u6_2 = charToU6[u6[j+2]];\n u6_3 = charToU6[u6[j+3]];\n // Let Uint8Array handle truncation\n u8[i] = (u6_0 << 2) + (u6_1 >> 4);\n u8[i+1] = (u6_1 << 4) + (u6_2 >> 2);\n u8[i+2] = (u6_2 << 6) + u6_3;\n j += 4;\n i += 3;\n }\n u6_0 = charToU6[j < u6.length ? u6[j] : 0];\n u6_1 = charToU6[j+1 < u6.length ? u6[j+1] : 0];\n u6_2 = charToU6[j+2 < u6.length ? u6[j+2] : 0];\n u6_3 = charToU6[j+3 < u6.length ? u6[j+3] : 0];\n u8[i] = (u6_0 << 2) + (u6_1 >> 4);\n u8[i+1] = (u6_1 << 4) + (u6_2 >> 2);\n u8[i+2] = (u6_2 << 6) + u6_3;\n return u8\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"u8ArrToB64([1,2,3,4,5,6,7,8])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"b64toU8array(u8ArrToB64([1,2,3,4,5,6,7,8]))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"t = LZ78.compress([1,2,2,2,2,2,2,1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"class Trie extends Map {\n constructor(key, val, ...args) {\n super(...args);\n this.key = key; // the byte that pointed to this node\n this.val = val; // the token value associated with the substring\n }\n\n addNode(char, val) {\n // Don't replace existing nodes, just overwrite their values\n let child = this.get(char);\n if (child) {\n child.val = val;\n } else {\n child = new this.constructor(char, val);\n this.set(char, child);\n }\n return child;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"CircularU8 = makeCircularPrototype(Uint8Array, \"CircularU8\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"// A simple object wrapping TextEncoder/TextDecoder functions to conver strings to utf-8 byte representations\n// For more info, see:\n// https://developer.mozilla.org/en-US/docs/Web/API/TextEncoder\n// https://developer.mozilla.org/en-US/docs/Web/API/TextDecoder\nutf = {\n const encoder = new TextEncoder(\"utf-8\");\n const decoder = new TextDecoder(\"utf-8\");\n return {\n encode: (...args) => encoder.encode(...args),\n encodeInto: (...args) => encoder.encodeInto(...args),\n decode: (...args) => decoder.decode(...args)\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 31:"$30:body"