30:T1528,encodedExamples = md`# Phase-in Codes *(Also known as economy codes or [truncated binary codes](https://en.wikipedia.org/wiki/Truncated_binary_encoding))* Imagine you have an array of integer values, and we know for a fact that they all are between 0 and 63 (inclusive). That means there are exactly 64 values to choose from, meaning we will never need more than five bits to express those values. Therefore, we could "pack" these values into a "stream" of bytes in chunks of five bits. The code required to do that would be a bit fiddly: it would require bit-shifting, keeping track of where in the byte the next chunk is stored, and dealing with the occasional chunk that is split across two bytes. Finding a value at an arbitrary index would be a hassle, and much slower than for arrays that store 8, 16, 32 or 64 bit values. On the other hand, the space savings can be quite significant: if the original array would have been stored as \`Uint8\` values, we save 3 bits per value for a 1.6x size reduction. JavaScript uses doubles by default, so would have probably used 64 bits; we would save 59 bits, for a 12.8x size reduction! So for *storage* purposes this is probably quite useful. But what if your total number of values is not a clean power of two? For example, what if the numbers range from 0 to 64 inclusive, so 65 in total? That means that one (and *only one*) of your values needs six bits. When handled naively, *all* your values need to be encoded in six bits, even though for 64 out of 65 possible values (roughly 98,5% of the time, assuming they are equally likely to appear) the first bit will be \`0\`. It would be nice if there was a way to use five bits most of the time, and only six bits when absolutely necessary. A first thought might be _"I'll just use another bit as a flag to say if we need more bits!"_, but hopefully that would be immediately followed by _"wait a minute..."_ The key trick is that we need a way to tell from the first five bits whether or not we need that extra sixth bit. Phase-in coding (also known as "economy coding") is a way to do that. Below is a table showing the bit strings for phase-in encoded values, each row representing a different number of total values: ${table} As one might expect the maths behind it are a bit tricky to explain. I'll try to do so in a way that gives some intuitive feeling for it. Alternatively, you can try the mathematically more rigorous [blog post on the subject by Steven Pigeon](https://hbfs.wordpress.com/2008/09/02/phase-in-codes/), which is where I first learned about phase-in codes. Or try making direct sense of the code examples below. (***Update September 2022:*** if we interpret the binary representation of numbers as a binary tree to walk down, it actually becomes visually intuitive. I implemented [an interactive notebook](https://observablehq.com/@jobleonard/an-intuitive-explanation-of-phase-in-codes) to demonstrate) First note how integer powers of two in the table behave like "normal" values. We can also see that the highest value on each row is a bit string with all bits set. That gives away the basic idea for phase-in codes: the highest possible value is encoded as the bitstring with all bits set, and we count backwards from that until we can unambiguously determine the values with a bit-string of one bit less. Let's work through a few examples to build some intuition for how that works. First, look at the row with five total values. We have to encode values 0, 1, 2, 3 and 4. In plain binary, that would be \`00\`, \`01\`, \`10\`, \`11\` and \`100\`. So values 0 to 3 fit into two bits, but we need three for the value 4. So 4 is encoded as \`111\` here. Now this immediately makes \`11\` unavailable as a bitstring, since we would not be able to determine whether it was a complete value, or \`111\` with the last bit missing. Since 3 is \`11\` in plain binary we must encode it as something else, which leaves us no other option but the three-bit \`110\`. However, values 0, 1 and 2 are encoded as \`00\`, \`01\`, \`10\` in plain binary, and since we don't need any \`000\`, \`010\`, \`100\` or \`101\` bitstrings we don't have to worry about ambiguities there. Therefore, the phase-in code sequence for 0 to 4 is \`00\`, \`01\`, \`10\`, \`110\` and \`111\`. Now let's try the sequence 0 to 5. We *have* to encode 5 and 4 in three bits at least, so as \`111\` and \`110\` respectively. Since 4 now uses \`110\`, 3 will now have to use \`101\`. But *that* in turn means we cannot determine if the bit-string \`10\` is complete or a partial \`101\` with the last bit missing, so 2 must now also be encoded as a three-bit string: \`100\`. The result is that we can encode the sequence 0 to 5 with \`00\`, \`01\`, \`100\`, \`101\`, \`110\` and \`111\`. Another way to look at it is this: each time the number of total values goes up by, the amount of values we can encode in one bit less goes down by one as well. Four unique values can be encoded in two bits for all four. For five unique values, we can encode only three values in two bits. Six unique values can only encode two values in two bits, seven unique values only one. Eight unique values can't encode any value in two bits, instead having to encode every value in three. The algorithm to do this automatically is written below, I think at this point the code is easier to follow than any textual description: `31:T4f3,// Note: this function coverts the phase- // encoded bits to a string of 1 and 0 // charactes, which works for demonstration //purposes but obviously is rather inefficient. //A real-world application of phase-in codes //would place the actual bits into a stream of //bytes of some sort. function toBitString(value, totalValues) { // First we have to find the number of bits // required to fit totalValues. This tells // us the power of two bigger or equal to // totalValues (bet you've never seen // Math.clz32() in JavaScript before, did // you? It returns the number of leading zero // bits in the 32-bit binary representation // of a number. Yes, we could also use // Math.ceil(Math.log2(totalValues-1)), // but where's the fun in that?). let length = 32 - Math.clz32(totalValues - 1); const nextPow2 = (1 << length) >>> 0; // Once we have this power of two we can // determine the treshold value. Values // below it will require one bit less. const treshold = nextPow2 - totalValues; let returnString = ""; if (value < treshold) { length--; } else { value += treshold; } returnString = value.toString(2); while (returnString.length < length) { returnString = "0" + returnString; } return returnString; }32:T1492,// Demonstration of a stream object that generates a string that encodes 15 bits per character. // Can be used in a variant of LZString, for example class Stream { constructor() { this.stream = ""; // use string as bitstream, this.charOut = 0; this.remainingOutBits = 15; this.charInPos = 0; this.charIn = 0; this.remainingInBits = 0; } clear() { this.stream = ""; // use string as bitstream, this.charOut = 0; this.remainingOutBits = 15; this.charInPos = -1; this.charIn = 0; this.remainingInBits = 0; } /** * Integer to safe UTF16 character * Only gives sensible output for values in the range 0 to 57017 (or 0xDEBA) * @param {number} i */ itou(i) { return String.fromCharCode(i + (i > 55225 ? 8518 : i > 8163 ? 70 : i > 91 ? 68 : i > 9 ? 35 : i > 5 ? 34 : i > 1 ? 33 : 32)); } /** * UTF16 charCode to integer * @param {number} i */ utoi(i) { return i - (i > 63743 ? 8518 : i > 8233 ? 70 : i > 159 ? 68 : i > 44 ? 35 : i > 39 ? 34 : i > 34 ? 33 : 32) | 0; } getNextChar() { return this.utoi(this.stream.charCodeAt(this.charInPos++)); } /** * @param {number} value * @param {number} valueBits */ strOut(value, valueBits) { // First handle all bits that fill up charOut and move to the next // char in the stream until all the remaining value bits fit in charOut if (valueBits > this.remainingOutBits) { valueBits -= this.remainingOutBits; let valueChunk = value >>> valueBits; this.charOut = this.charOut | valueChunk; this.stream += this.itou(this.charOut); // while there are more valueBits left than can be fit into // a full charCode, stream bit by charCode sized chunks while (valueBits >= 15) { valueBits -= 15; this.stream += this.itou((value >>> valueBits) & 0x7FFF); } this.charOut = 0; this.remainingOutBits = 15; } // At this point valueBits < remainingCharOutBits. If there are bits left // to stream, put them into charOut if (valueBits > 0) { var valueMask = (1 << valueBits) - 1; this.remainingOutBits -= valueBits; this.charOut = this.charOut | ((value & valueMask) << this.remainingOutBits); } // if we filled up our charOut, stream it. if (this.remainingOutBits === 0) { this.stream += this.itou(this.charOut); this.charOut = 0; this.remainingOutBits = 15; } } flush() { if (this.remainingOutBits < 15) { this.stream += this.itou(this.charOut); this.charOut = 0; this.remainingOutBits = 15; } } /** * @param {number} valueBits */ strIn(valueBits) { // Move to next charIn value if this one is finished if (this.remainingInBits === 0) { this.remainingInBits = 15; this.charIn = this.getNextChar(); } // // only get a charIn if still inside data // if (streamIdx >= this.stream.length) return null; let value = 0; // while more bits are asked than current charIn 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 = 15; value = (this.charIn & valueMask) << valueBits; while (valueBits > 15) { valueBits -= 15; value = value | (this.getNextChar() << valueBits); } this.charIn = this.getNextChar(); } // If there are still required bits left, get them from charIn // 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.charIn >>> this.remainingInBits) & valueMask); } return value; } /** * @param {number} value * @param {number} totalValues */ phaseOut(value, totalValues) { value = totalValues - 1 - 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); } /** * @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 totalValues - 1 - value; } }33:T1173,// Demonstration of a stream object that generates an array of bytes. // Can be used in a variant of LZString, for example class ByteStream { constructor() { this.stream = new CircularU8(); this.valOut = 0; this.remainingOutBits = 8; this.valInPos = 0; this.valIn = 0; this.remainingInBits = 0; } clear() { this.stream = []; // use string as bitstream, this.valOut = 0; this.remainingOutBits = 8; this.valInPos = -1; this.valIn = 0; this.remainingInBits = 0; } 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; } } flush() { if (this.remainingOutBits < 8) { this.stream.push(this.valOut); this.valOut = 0; this.remainingOutBits = 8; } } /** * @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 = totalValues - 1 - 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); } /** * @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 totalValues - 1 - value; } }34:T711,testStream = { const plain = { stream: new ByteStream(), inputs: [], outputs: [], mismatches: [], }; const phased = { stream: new ByteStream(), inputs: [], outputs: [], mismatches: [], }; const totalSamples = 10000 ; const totalVals = [] for(let i = 0; i < totalSamples; i++) { // Note: the savings really depends on the distribution of value, // because how they are biased to large or small values affects // how often we can save a bit. // make totalValues scale up with i const totalValues = i + 2; totalVals.push(totalValues); // // a random value between 0 and 1, but biased towards 1 const rndVal = (1 - Math.abs(Math.random()-Math.random()+Math.random()-Math.random()+Math.random()-Math.random()+Math.random()-Math.random())/4); let value = rndVal * totalValues | 0; let bits = 32 - Math.clz32(totalValues-1); plain.stream.strOut(value, bits); plain.inputs.push(value); phased.stream.phaseOut(value, totalValues); phased.inputs.push(value); } plain.stream.flush(); phased.stream.flush(); plain.streamLength = plain.stream.stream.length; phased.streamLength = phased.stream.stream.length; for(let i = 0; i < totalSamples; i++) { const totalValues = totalVals[i] let bits = 32 - Math.clz32(totalValues-1); plain.outputs.push(plain.stream.strIn(bits)); if (plain.inputs[i] !== plain.outputs[i]) plain.mismatches.push({i, original: plain.inputs[i], streamed: plain.outputs[i]}); phased.outputs.push(phased.stream.phaseIn(totalValues)); if (phased.inputs[i] !== phased.outputs[i]) phased.mismatches.push({i, original: phased.inputs[i], streamed: phased.outputs[i]}); } return {plain, phased, ratio: phased.streamLength/plain.streamLength}; }35:[] 2e:{"title":"Phase-in Codes","cells":[{"id":124,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":109,"value":"function fromBitString(str, totalValues) {\n const value = +(\"0b\"+str);\n const length = 32 - Math.clz32(totalValues-1);\n const nextPow2 = (1<>> 0;\n\n const treshold = nextPow2 - totalValues;\n return value < treshold ? value : (value - treshold) >>> 0;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":258,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":405,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":448,"value":"import {CircularU8} from \"@jobleonard/circular-buffers\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":263,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"table = {\n let tableSize = 12;\n let table = \"| |\";\n let row = \"\\n|\";\n for(let i = 0; i < tableSize; i++) table += i + \" | \";\n table += row;\n for(let i = 0; i < tableSize; i++) table += \" --- |\";\n \n for(let i = 2; i <= tableSize; i++) {\n const b = ((2**Math.floor(Math.log2(i))) === i) ? \"**\" : \"\"; // bold power of two rows\n row = \"\\n| \" + b + \"total: \" + i + b + \" |\";\n for (let j = 0; j < tableSize; j++){\n row += \" \" + \"`\" + (j < i ? toBitString(j, i) : \".\") + \"`\" + \" |\";\n }\n table += row;\n }\n return table;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":102,"value":"[0,1,2,3,4,5,6,7,8,9].map(v => toBitString(v, 10)).map(v => fromBitString(v, 10))","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"[0,1,2,3,4,5,6,7,8,9,10].map(v => toBitString(v, 11)).map(v => fromBitString(v, 11))","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"[0,1,2,3,4,5,6,7,8,9,10, 11].map(v => toBitString(v, 12)).map(v => fromBitString(v, 12))","pinned":false,"hidden":false,"mode":"ojs"},{"id":186,"value":"{\n const mismatches = [];\n let allMatch = true;\n for(let i = 1; i < 0x100000000; i += (1 + Math.random() * i * 0.1 | 0)) {\n const value = i;\n const converted = fromBitString(toBitString(value, 32), 32);\n const same = value === converted;\n allMatch = allMatch && same;\n if (!same) {\n mismatches.push({same: value === converted, value, converted});\n }\n }\n if (!allMatch) {\n return mismatches;\n } else {\n return \"all conversions went well!\"\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"// Not actually used\n/*\nfunction nextPow2(v) {\n return v >= 0xFFFFFFFF ?\n 0x100000000 * (1<<(32-Math.clz32((v-1) * 2.3283064365386963e-10))) :\n (1<<(32- Math.clz32(v-1))) >>> 0;\n}\n*/","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}