30:T5d7, { let bb1 = toBinArr(b1); let bb2 = toBinArr(b2); let bb3 = toBinArr(b3); let b64d1 = fromBinArr([0, 0].concat(bb1.slice(0,6))); let b64d2 = fromBinArr([0, 0].concat(bb1.slice(6), bb2.slice(0, 4))); let b64d3 = fromBinArr([0, 0].concat(bb2.slice(4), bb3.slice(0, 2))); let b64d4 = fromBinArr([0, 0].concat(bb3.slice(2))); let b64_1 = b64_alphabet[b64d1]; let b64_2 = b64_alphabet[b64d2]; let b64_3 = b64_alphabet[b64d3]; let b64_4 = b64_alphabet[b64d4]; let b64_a = [b64_1, b64_2, b64_3, b64_4]; return html`

base64, start with all the bits:
${bb1}${bb2}${bb3}

break into sets of 6 bits:
${bb1.slice(0,6)} ${bb1.slice(6)}${bb2.slice(0, 4)} ${bb2.slice(4)}${bb3.slice(0, 2)} ${bb3.slice(2)}
Convert into numbers, then index into base64 alphabet
${b64d1} ${b64d2} ${b64d3} ${b64d4}
${b64_1} ${b64_2} ${b64_3} ${b64_4}
${b64_a.join("")}

` }31:T4ed,## What about proper base62 encoding/decoding? An actual base62 implementation would take the full number, and divide it by 62 to get its remainder, and carry this forward through all the remaining bytes. Effectively, this means if we see `b11111` (5 1's, aka 61), then we have to leave the remaining bit for the next character. (see [this example](https://github.com/odan/base62js/blob/master/jquery.base62.js#L200-L211)). It gets weird because you can have 6 bit numbers that are less, e.g. `b100001` aka `33` in decimal. So, sometimes a character holds 6 bits of information, and in a few cases, it holds only 5 bits. * `11111 1` == 63 * `11111 0` == 62 // lose a bit, encode as 61 * `11110 1` == 61 * `11110 0` == 60 // lose a bit, encode as 60 The implication is that the length of the output is dependent on the input. If you end up with strings of 1's, you'll end up with a longer output. Consider an example of 5 alphanumeric characters, (which causes an error in `atob`). Since each character can be represented with either 5 or 6 bits, the number of bits we would need to hold this would vary between ${5*5} and ${5*6} bits, which is definitely more than 3 bytes (24 bits) and less than 4 (32 bits), meaning we would need 4 bytes to hold it.32:T508,## Checking encoding stability for randomly generated strings In some cases, for alphanumeric IDs, you can randomly generate characters in an alphabet. This is often base62 or base58, but you could choose to try base64 for decoding these IDs into bytes. However, if you choose a number of characters that's not a multiple of 4, you won't necessarily get the same ID back without some special care. That's because Javascript's btoa functionality will drop some bits. From [the docs](https://infra.spec.whatwg.org/#forgiving-base64-decode) on when things don't line up (emphasis added): > If buffer is not empty, it contains either 12 or 18 bits. If it contains 12 bits, then discard the last four and interpret the remaining eight as an 8-bit big-endian number. **If it contains 18 bits, then discard the last two** and interpret the remaining 16 as two 8-bit big-endian numbers. Append the one or two bytes with values equal to those one or two numbers to output, in the same order. Put another way, if you have half or less of a byte, toss it. If you have more than half (i.e. 6 bits) then it's an error. (Step 3 earlier in that doc says "If data’s code point length divides by 4 leaving a remainder of 1, then return failure." which is when you would have a full 6 bits extra)33:T6ee,{ const input2 = s1; const input = s1; const height = 150; const rectWidth = 30; // const const r = []; for (let i = 0; i < input.length; i++) { r.push({txt: input[i], x: i, y: 0, color: 'green'}); } for (let i = 0; i < input.length; i++) { r.push({txt: b64_alphabet.indexOf(input[i]), x: i, y: 1, color: 'steelblue'}); } for (let i = 0; i < input2.length; i++) { r.push({txt: `${input[i]}^${input2[i]}`, x: i, y: 2, color: 'gray'}); } const toHex = (x) => { let hex = x.toString(16); if (hex.length == 1) { hex = "0" + hex;} return hex } for (let i = 0; i < input2.length; i++) { r.push({txt: toHex(atoi(input[i]) ^ atoi(input2[i])), x: i, y: 3, color: 'orange'}); } const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); const x = d3.scaleLinear() .domain([0, input.length]) .range([0, input.length*(rectWidth)]); // const x = d3.scaleBand() // .domain([0, input.length]) // .rangeRound([margin.left, width - margin.right]) // .padding(0.1) const y = d3.scaleLinear() .domain([0, 4]) .range([margin.top, margin.top + rectWidth*5]) svg.append("g") .selectAll("rect") .data(r) .join("rect") .attr("x", d => x(d.x)) .attr("width", rectWidth) .attr("y", d => y(d.y) - (rectWidth/2)) .attr("height", rectWidth) .attr('fill','none') .attr('stroke', '#aaa') svg.append("g") .selectAll("text") .data(r) .join('text') .text(d => d.txt) .attr('font-size', d => ((d.y == 2) ? "10pt": undefined)) .attr('fill', d => d.color) .attr("x", d => x(d.x) + 5) .attr("y", d => y(d.y)+(rectWidth*.25)) ; return svg.node() }34:[] 2e:{"title":"Base64 Encoding","cells":[{"id":4,"value":"# Base64 Encoding\n\nExploring how bits are represented in base64 format. The key realization is that 2^6 == 64, meaning that 6 bits can be encoded in a single character of the base64 alphabet. Since there are 8 bits in a byte, that conveniently maps to 3 bytes == 4 characters (8 bits/byte \\* 3 bytes = 24 bits, 6 bits/char \\* 4 chars = 24 bits).","pinned":false,"hidden":false,"mode":"md"},{"id":12,"value":"b64_alphabet = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"viewof b1 = Inputs.range([0, 255], {label: \"b1\", step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"viewof b2 = Inputs.range([0, 255], {label: \"b2\", step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":122,"value":"viewof b3 = Inputs.range([0, 255], {label: \"b3\", step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"b_a = [b1, b2, b3];","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"toHex = (x) => {\n let hex = x.toString(16);\n if (hex.length == 1) { hex = \"0\" + hex;}\n return hex\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":116,"value":"{\n let bb1 = toBinArr(b1).join(\"\");\n let bb2 = toBinArr(b2).join(\"\");\n let bb3 = toBinArr(b3).join(\"\");\n\n\n return html`

binary:
\n${bb1}\n${bb2}\n${bb3}\n

\n\n

hex:
\n${toHex(b1)}\n${toHex(b2)}\n${toHex(b3)}\n

\n`\n\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":142,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":198,"value":"btoa(b_s) // It matches!","pinned":true,"hidden":false,"mode":"ojs"},{"id":317,"value":"## What about base62 encoding with base64?\n\nFor some purposes, I want to only use alphanumeric characters, no slashes or equals. This is effectively base62 encoding.\n\nWe can take random alphanumeric strings and decode/re-encode them with base64 as long as we stay in multiples of 4 characters. If we're not in multiples of 4, we need special handling or we'll run into a bit discarding problem described below.\n\nNote this is a little strange because we're randomly generating _encoded_ strings, not randomly generating the raw bytes. Usually, you start from bytes, and want to encode them as text.\n\n","pinned":false,"hidden":false,"mode":"md"},{"id":335,"value":"b62_alphabet = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":319,"value":"b62_ex_1 = \"AbcD\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":322,"value":"btoa(atob(b62_ex_1))","pinned":true,"hidden":false,"mode":"ojs"},{"id":330,"value":"If we generate a bunch of random examples, we can see this works out.","pinned":false,"hidden":false,"mode":"md"},{"id":333,"value":"getExamples(20, () => randString(4, b62_alphabet))","pinned":true,"hidden":false,"mode":"ojs"},{"id":344,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":367,"value":"b62_ex_2 = \"99999\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":369,"value":"{\n const inp = b62_ex_2;\n\n const nums = b62_ex_2.split(\"\").map(c => b62_alphabet.indexOf(c));\n\n const bins = nums.map(toBinArr).map(a => a.slice(2))\n \n return {nums, bins}\n\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":352,"value":"parseInt(\"111100\", 2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":232,"value":"## Weird stuff with Javascript byte strings\n\nThe `btoa` function turns a \"byte string\" into base64 text (some more info [here](https://html.spec.whatwg.org/multipage/webappapis.html#dom-atob-dev)), but that means you need to get an array of ints into \"byte string\" format. That turns out to be easiest with:","pinned":false,"hidden":false,"mode":"md"},{"id":219,"value":"toByteStr = (a) => String.fromCharCode(...a)","pinned":true,"hidden":false,"mode":"ojs"},{"id":193,"value":"b_s = toByteStr(b_a)","pinned":true,"hidden":false,"mode":"ojs"},{"id":241,"value":"Similarly, if you are decoding, you want to be able to go from a byte string into an array of integers, and that's easiest with:","pinned":false,"hidden":false,"mode":"md"},{"id":205,"value":"\nfromByteStr = (s) => s.split(\"\").map(c => c.charCodeAt(0))","pinned":true,"hidden":false,"mode":"ojs"},{"id":245,"value":"[fromByteStr(b_s), fromByteStr(b_s).join(\"\") === b_a.join(\"\")]","pinned":true,"hidden":false,"mode":"ojs"},{"id":203,"value":"fromByteStr(atob(btoa(b_s)))","pinned":false,"hidden":false,"mode":"ojs"},{"id":213,"value":"fromByteStr(b_s)","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"## Other helpers","pinned":false,"hidden":false,"mode":"md"},{"id":160,"value":"fromBinArr = (x) => {\n let result = 0;\n \n for (let i = 0; i < 8; i += 1) {\n result |= x[7 - i] << i\n }\n \n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":112,"value":"toBinArr = (c) => { \n if (c > 255) {\n throw 'must be 8 bit byte';\n }\n \n let result = [];\n \n result[7] = (c & 1) > 0 ? 1 : 0; \n result[6] = (c & 2) > 0 ? 1 : 0; \n result[5] = (c & 4) > 0 ? 1 : 0; \n result[4] = (c & 8) > 0 ? 1 : 0; \n result[3] = (c & 16) > 0 ? 1 : 0; \n result[2] = (c & 32) > 0 ? 1 : 0; \n result[1] = (c & 64) > 0 ? 1 : 0; \n result[0] = (c & 128) > 0 ? 1 : 0; \n \n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"atoi = (a) => a.charCodeAt(0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":188,"value":"atob(\"s9Pp\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":270,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":283,"value":"ex1 = {\n let og = \"+3/\";\n// ^ we know \n \n return {in: og, roundtrip: btoa(atob(og))}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":286,"value":"ex1_bytes = atob(ex1.in)","pinned":true,"hidden":false,"mode":"ojs"},{"id":288,"value":"btoa(ex1_bytes)","pinned":true,"hidden":false,"mode":"ojs"},{"id":296,"value":"{\n let inp = ex1.in; // 18\n let out = btoa(atob(ex1.in));\n\n let inp_bs = atob(inp);\n let inp_ba = fromByteStr(inp_bs); // 16 bits, we lost 2 bits\n\n\n let getB64DecArray = (s) => s.split(\"\").map(c => b64_alphabet.indexOf(c));\n\n let b64_da_inp = getB64DecArray(inp);\n let b64_da_out = getB64DecArray(out);\n\n let inp_bits = b64_da_inp.map(c => toBinArr(c).slice(2).join(\"\"))\n let out_bits = b64_da_out.map(c => toBinArr(c).slice(2).join(\"\"))\n\n let enc_bits = inp_ba.map(c => toBinArr(c).join(\"\"))\n\n\n \n\n\n return {out, inp_bs, inp_ba, b64_da_inp, b64_da_out, inp_bits, out_bits, enc_bits};\n \n\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":50,"value":"randString = (length, chars) => {\n var result = '';\n for (var i = length; i > 0; --i) result += chars[Math.floor(Math.random() * chars.length)];\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"randb64 = (l) => randString(l, b64_alphabet)","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"getExamples(5, () => randb64(3))","pinned":true,"hidden":false,"mode":"ojs"},{"id":404,"value":"// TODO: make one that pads with an A if the modulo is 1, 2, 3, and then knows to trim it on the other side.\n// ^ does that work with base62?","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"getExamples = (n, fn1) => {\n let errors = [];\n for (let i = 0; i < n; i += 1) {\n let s = fn1();\n let d = atob(s);\n let e = btoa(d);\n\n e = e.replaceAll(\"=\", \"\");\n s = s.replaceAll(\"=\", \"\");\n\n if (s !== e) {\n errors.push([s, e]);\n }\n }\n\n return errors\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":411,"value":"ex2 = {\n let f1 = \"+\";\n let og = f1 + \"A\";\n // ^ we know there are 3 characters, so 18 bits.\n // we can add an \"A\" on there to get it to a multiple of 4, then crop it off later?\n \n return {in: og, roundtrip: btoa(atob(og))}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"s1 = \"xmqPi1Q5m6\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":97,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":229,"value":"## Resources\n\n- [Great explanation about base64 padding](https://stackoverflow.com/questions/4080988/why-does-base64-encoding-require-padding-if-the-input-length-is-not-divisible-by)\n- https://www.rfc-editor.org/rfc/rfc4648\n- ","pinned":false,"hidden":false,"mode":"md"},{"id":99,"value":"margin = ({top: 20, right: 20, bottom: 30, left: 40})","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}