[{"_1":2,"_170":-5,"_171":-5},"loaderData",{"_3":4,"_92":93},"root",{"_5":6,"_35":36,"_65":66},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20,"_34":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","isTeamOrgMember","ENV",{"_37":38,"_39":40,"_41":42,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":54,"_55":56,"_57":58,"_59":60,"_61":62,"_63":64},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","5c349ef9e7d7333839a0634dd567aae2d49623a6","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_67":68},"__internal_clerk_state",{"_69":70,"_71":46,"_72":73,"_74":73,"_75":20,"_76":73,"_77":73,"_78":73,"_79":73,"_80":81,"_90":20,"_91":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_82":20,"_19":20,"_83":73,"_84":85,"_86":73,"_87":46,"_88":20,"_89":73},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_94":95,"_96":97,"_98":99,"_100":101,"_149":150,"_167":168,"_169":-5},"handle","maxm","name","huffmanEncoding","path","main.tsx","project",{"_102":103,"_96":97,"_104":105,"_106":-5,"_107":108,"_109":110,"_111":-5,"_112":-5,"_12":113,"_114":-5,"_115":108,"_116":-5,"_117":-5,"_118":32,"_14":119,"_120":121,"_122":121,"_123":124,"_125":124,"_126":124,"_127":121,"_128":121,"_23":129,"_132":133,"_135":136,"_148":20},"id","0bdfe270-252d-11f0-8a67-569c3dd06744","createdAt",["D",1745953585144],"deletedAt","legacyEnvVars",true,"privacy","public","description","imageUrl","418c1e39-eb48-4f2f-8c97-122ece94631c","pinnedFileId","pinPreview","pinMigrated","screenshotVersion","likeCount","c1e7642a-74cc-4d69-8652-20abbdeaa94e","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_94":95,"_130":131},"profileImageUrl","https://img.clerk.com/eyJ0eXBlIjoicHJveHkiLCJzcmMiOiJodHRwczovL2ltYWdlcy5jbGVyay5kZXYvdXBsb2FkZWQvaW1nXzJnTEtkSHlOMWxWZm1GRHdKYUVTNklYM3FpdiJ9","org",{"_94":95,"_134":131,"_12":113},"avatar","branch",{"_137":138,"_96":44,"_102":139,"_140":103,"_141":-5,"_142":-5,"_143":-5,"_144":-5,"_145":-5,"_146":97,"_147":95},"version",10,"0be031da-252d-11f0-8a67-569c3dd06744","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_102":151,"_96":99,"_152":153,"_154":-5,"_155":139,"_156":138,"_157":108,"_104":158,"_137":159,"_160":161,"_162":163,"_164":20,"_165":-5,"_98":166},"0c1900d2-252d-11f0-8a67-569c3dd06744","fileId","0be235f2-252d-11f0-8a67-569c3dd06744","parentId","branchId","branchVersion","latest",["D",1715818085533],9,"fileType","script","content","type FrequentieTable = Record;\ntype IntermediaryNode = [string, number, Node[]];\ntype LeafNode = [string, number];\ntype Node = IntermediaryNode | LeafNode;\ntype HuffmanTree = [IntermediaryNode];\ntype Encoding = number[];\ntype EncodedData = number[];\ntype EncodingTable = Record;\n\nexport class BinaryReader {\n protected chunk: number;\n protected pos: number;\n protected bitPos: number;\n protected bitCount: number;\n\n view: DataView;\n\n constructor(arrayBuffer: ArrayBuffer) {\n this.view = new DataView(arrayBuffer);\n this.pos = 0;\n this.bitPos = -1;\n this.chunk = 0;\n this.bitCount = 0;\n }\n\n protected getData(type = \"Uint8\") {\n if (this.view.byteLength > this.pos) {\n this.bitPos = -1;\n\n // @ts-ignore\n return this.view[`get${type}`](this.pos++);\n }\n\n throw new RangeError();\n }\n\n get buffer() {\n return this.view.buffer;\n }\n\n getBytePosition() {\n return this.pos;\n }\n\n seek(pos: number) {\n const oldPos = this.pos;\n\n this.pos = pos;\n\n return oldPos;\n }\n\n peak(index = this.pos + 1) {\n if (this.view.byteLength > index && index > -1) {\n return this.view.getUint8(index);\n }\n\n return null;\n }\n\n peakBit() {\n const chunk = this.chunk;\n const pos = this.pos;\n const bitPos = this.bitPos;\n const bitCount = this.bitCount;\n const bit = this.getBit();\n\n this.bitPos = bitPos;\n this.chunk = chunk;\n this.pos = pos;\n this.bitCount = bitCount;\n\n return bit;\n }\n\n getPadSize() {\n if (this.chunk === null) {\n return 0;\n } else {\n const bitCount = getBitCount(this.chunk);\n\n return 8 - bitCount;\n }\n }\n\n getBitPos() {\n return getBitCount(this.chunk) - 1 + this.getPadSize();\n }\n\n getBit() {\n if (this.bitPos === -1) {\n this.chunk = this.getData();\n\n this.bitPos = this.getBitPos();\n this.bitCount = getBitCount(this.chunk);\n }\n\n if (this.chunk === null) return null;\n\n const bitCount = this.bitCount;\n const bit = this.bitPos >= bitCount ? 0 : (this.chunk >> this.bitPos) & 1;\n\n this.bitPos--;\n\n return bit;\n }\n\n getUint32() {\n return (\n (this.getData() << 24)\n | (this.getData() << 16)\n | (this.getData() << 8)\n | this.getData()\n );\n }\n\n getUint16() {\n return (this.getData() << 8) | this.getData();\n }\n\n getUint8() {\n return this.getData();\n }\n}\n\nexport class BinaryWriter extends BinaryReader {\n constructor(length: number) {\n super(new ArrayBuffer(length));\n }\n\n private setData(data: number, type = \"Uint8\") {\n let advance = 0;\n\n switch (type) {\n case \"Uint16\":\n advance = 2;\n break;\n case \"Uint32\":\n advance = 4;\n break;\n default:\n advance = 1;\n }\n\n if (this.view.byteLength > this.pos) {\n this.bitPos = -1;\n\n // @ts-ignore\n this.view[`set${type}`](this.pos, data);\n\n this.pos += advance;\n\n return this;\n }\n\n return this;\n }\n\n setUint32(data: number) {\n return this.setData(data, \"Uint32\");\n }\n\n setUint16(data: number) {\n return this.setData(data, \"Uint16\");\n }\n\n setUint8(data: number) {\n return this.setData(data);\n }\n}\n\nconst traverseHuffmanTree = (node: Node, char: string, encoding: Encoding = []): Encoding => {\n /* We don't need the count, so will only be using the characters and children */\n const [characters, _count, children] = node;\n\n if (char === characters) return encoding;\n\n if (children) {\n const [left, right] = children;\n\n /* If left node matches go left and add 0 to the encoding */\n if (left[0].includes(char)) return traverseHuffmanTree(left, char, [...encoding, 0]);\n\n /* If right node matches go right and add 1 to the encoding */\n if (right[0].includes(char)) return traverseHuffmanTree(right, char, [...encoding, 1]);\n }\n\n throw Error(`No match found for: ${char}`);\n};\n\nconst getCharacterEncoding = (huffmanTree: HuffmanTree) => (char: string) => {\n const [rootNode] = huffmanTree;\n\n return traverseHuffmanTree(rootNode, char);\n};\n\nconst createEncodingTable = (frequentieTable: FrequentieTable, huffmanTree: HuffmanTree): EncodingTable =>\n Object.keys(frequentieTable).reduce((table, char) => {\n table[char] = getCharacterEncoding(huffmanTree)(char);\n\n return table;\n }, {} as EncodingTable);\n\nconst createFrequentieTable = (input: string) => {\n const frequentieTabel: FrequentieTable = {};\n\n for (let i = 0, l = input.length; i < l; i++) {\n const char = input.charAt(i);\n\n if (frequentieTabel[char] !== undefined) {\n frequentieTabel[char]++;\n } else {\n frequentieTabel[char] = 1;\n }\n }\n\n return frequentieTabel;\n};\n\nconst getNewIndex = (entries: Node[], count: number) => {\n let index = entries.length - 1;\n\n while (index > 0) {\n if (count <= entries[index][1]) return index;\n\n index--;\n }\n\n return 0;\n};\n\nconst getSortedEntries = (frequentieTable: FrequentieTable): Node[] =>\n Object.entries(frequentieTable).sort((a, b) => b[1] - a[1]);\n\nconst createHuffmanTree = (frequentieTable: FrequentieTable): HuffmanTree => {\n const entries = getSortedEntries(frequentieTable);\n\n while (entries.length > 1) {\n const left = entries.pop() as Node;\n const right = entries.pop() as Node;\n\n const [charLeft, countLeft] = left;\n const [charRight, countRight] = right;\n\n const newCount = countLeft + countRight;\n const newIndex = getNewIndex(entries, newCount);\n\n const intermediaryNode: IntermediaryNode = [`${charLeft}${charRight}`, newCount, [left, right]];\n\n entries.splice(newIndex, 0, intermediaryNode);\n }\n\n return entries as HuffmanTree;\n};\n\nconst encodeData = (encodingTable: EncodingTable) => (input: string): EncodedData =>\n input\n .split(\"\")\n .flatMap(char => encodingTable[char]);\n\nconst getBitCount = (bits: number) => {\n let bitCount = 0;\n\n while (bits) {\n /* Shift one bit off and assign result */\n\n bits >>= 1;\n\n /* For every shift add a one to the total count */\n\n bitCount++;\n }\n\n return bitCount;\n};\n\nconst getCharacterCode = (char: string) => char.charCodeAt(0);\n\nconst mapCodeToInteger = (code: Encoding) => code.reduce((acc, bit) => (acc << 1) | bit, 0);\n\nconst getByteCount = (bitCount: number) => {\n const remainder = bitCount % 8;\n\n /* Round to whole bytes*/\n\n return (bitCount + (remainder ? 8 - remainder : 0)) / 8;\n};\n\nconst mapEncodingTable = (encodingTable: EncodingTable) => {\n let lengthEncodingTable = 0;\n\n const entries = Object.entries(encodingTable).map(([char, code]) => {\n const { length } = code;\n\n /*\n We add 2 bytes for the length and character and 1 or 2 for the code depending\n on wether it's code length is bigger then 8 bits\n */\n\n lengthEncodingTable += 2 + (length > 8 ? 2 : 1);\n\n /* For each code, return a triplet [ number, number, number ] */\n\n return [length, getCharacterCode(char), mapCodeToInteger(code)];\n });\n\n return [entries, lengthEncodingTable] as const;\n};\n\nconst getPaddingSizeEncodedData = (bitCount: number) => {\n const remainder = bitCount % 8;\n\n if (remainder) return 8 - remainder;\n\n return 0;\n};\n\nconst toArrayBuffer = (data: EncodedData, encodingTable: EncodingTable) => {\n const BYTE_COUNT_LENGTH_ENCODING_TABLE = 2;\n const BYTE_COUNT_LENGTH_ENCODED_DATA = 4;\n const PADDING_ENCODED_DATA = 1;\n\n const [entries, lengthEncodingTable] = mapEncodingTable(encodingTable);\n\n const { length: bitCount } = data;\n const byteCount = getByteCount(bitCount);\n const paddingSizeEncodedData = getPaddingSizeEncodedData(bitCount);\n\n const binaryWriter = new BinaryWriter(\n byteCount\n + BYTE_COUNT_LENGTH_ENCODING_TABLE\n + BYTE_COUNT_LENGTH_ENCODED_DATA\n + PADDING_ENCODED_DATA\n + lengthEncodingTable,\n );\n\n binaryWriter.setUint16(lengthEncodingTable);\n\n entries.forEach(([length, charCode, code]) => {\n binaryWriter.setUint8(length);\n binaryWriter.setUint8(charCode);\n\n if (length > 8) binaryWriter.setUint16(code);\n else binaryWriter.setUint8(code);\n });\n\n let chunk = 0;\n let index = 0;\n\n binaryWriter.setUint32(byteCount);\n binaryWriter.setUint8(paddingSizeEncodedData);\n\n while (index < bitCount) {\n if (index % 8 === 0 && index !== 0) {\n binaryWriter.setUint8(chunk);\n\n chunk = 0;\n }\n\n /* Shift chunk one bit to the left and add current bit */\n\n chunk = (chunk << 1) | data[index];\n\n index++;\n }\n\n if (chunk) {\n /* We add padding to fill out the last chunk to a whole byte */\n\n for (let padding = 0; padding < paddingSizeEncodedData; padding++) chunk = chunk << 1;\n\n binaryWriter.setUint8(chunk);\n }\n\n return binaryWriter.buffer;\n};\n\nexport const encode = (input: string) => {\n const frequentieTable = createFrequentieTable(input);\n const huffmanTree = createHuffmanTree(frequentieTable);\n const encodingTable = createEncodingTable(frequentieTable, huffmanTree);\n\n const encodedData = encodeData(encodingTable)(input);\n\n return toArrayBuffer(encodedData, encodingTable);\n};\nconst getDecodedData = (binaryReader: BinaryReader) => (huffmanTree: HuffmanTree, bitCountEncodedData: number) => {\n const [root] = huffmanTree;\n\n let bitsRead = 0;\n\n const traverse = (node: Node, binaryReader: BinaryReader): string => {\n if (bitsRead > bitCountEncodedData) return \"\";\n\n const nodes = node[2];\n\n if (!nodes) return node[0];\n\n const bit = binaryReader.getBit();\n\n bitsRead++;\n\n if (bit !== null) {\n if (nodes) return traverse(nodes[bit], binaryReader);\n else return node[0];\n } else {\n return \"\";\n }\n };\n\n let decodedData = \"\";\n\n while (bitsRead < bitCountEncodedData && binaryReader.peakBit() !== null) {\n decodedData += traverse(root, binaryReader);\n }\n\n return decodedData;\n};\n\nconst decodeHuffmanTree = (binaryReader: BinaryReader): HuffmanTree => {\n const root: IntermediaryNode = [\"\", 0, []];\n\n const huffmanTreeLength = binaryReader.getUint16();\n\n let indexHeader = 0;\n\n while (indexHeader < huffmanTreeLength) {\n let lengthCode = binaryReader.getUint8();\n let indexCode = lengthCode - 1;\n\n const char = String.fromCharCode(binaryReader.getUint8());\n const code = lengthCode > 8 ? binaryReader.getUint16() : binaryReader.getUint8();\n\n let entry: Node = root;\n\n while (indexCode > -1) {\n const bit = (code >> indexCode) & 1;\n\n entry[0] += char;\n entry[1] += 1;\n\n const nodes = entry[2] as Node[];\n const node = nodes[bit];\n\n if (node) {\n if (indexCode === 0) {\n nodes[bit] = [char, 1];\n } else {\n entry = node;\n }\n } else if (indexCode === 0) {\n nodes[bit] = [char, 1];\n } else {\n const newEntry: IntermediaryNode = [\"\", 0, []];\n\n nodes[bit] = newEntry;\n\n entry = newEntry;\n }\n\n indexCode--;\n }\n\n indexHeader += 2 + (lengthCode > 8 ? 2 : 1);\n }\n\n return [root];\n};\n\nconst getBitCountEncodedData = (byteCountEncodedData: number, paddingSizeEncodedData: number) =>\n byteCountEncodedData * 8 - paddingSizeEncodedData;\n\nexport const decode = (buffer: ArrayBuffer) => {\n const binaryReader = new BinaryReader(buffer);\n\n const huffmanTree = decodeHuffmanTree(binaryReader);\n\n const byteCountEncodedData = binaryReader.getUint32();\n const paddingSizeEncodedData = binaryReader.getUint8();\n\n return getDecodedData(binaryReader)(\n huffmanTree,\n getBitCountEncodedData(byteCountEncodedData, paddingSizeEncodedData),\n );\n};\nconsole.log(decode(encode(\"asdfasdfasf\")));","deleted","label",[99],"permalink","https://www.val.town/x/maxm/huffmanEncoding/code/main.tsx","extension","actionData","errors"]