From: Lady <redacted>
Date: Fri, 19 May 2023 07:20:39 +0000 (-0700)
Subject: Fix base64 implementation
X-Git-Tag: 0.3.0~4
X-Git-Url: https://git.ladys.computer/Pisces/commitdiff_plain/8d2beebdeea4000740fc3914f5d568f473629951?ds=sidebyside;hp=0752ef49a10befbfc3c3cb5aa0c194ad5dddef8a

Fix base64 implementation

I believe that the old implementation was just wrong, and it simply
wasn’t caught because Deno’s `assertEquals` doesn’t actually know what
to do with raw buffers. Wrapping them to build typed arrays creates
working tests, and this implementation matches observed behaviour with
`atob` and `btoa`.
---

diff --git a/binary.js b/binary.js
index 272775f..362161b 100644
--- a/binary.js
+++ b/binary.js
@@ -1,7 +1,7 @@
 // ♓🌟 Piscēs ∷ binary.js
 // ====================================================================
 //
-// Copyright © 2020–2022 Lady [@ Lady’s Computer].
+// Copyright © 2020–2023 Lady [@ Lady’s Computer].
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -68,6 +68,10 @@ const {
   setUint16: viewSetUint16,
 } = viewPrototype;
 
+/**
+ * Returns an ArrayBuffer for encoding generated from the provided
+ * arguments.
+ */
 const bufferFromArgs = ($, $s) =>
   $ instanceof Buffer
     ? $
@@ -128,7 +132,7 @@ const decodeBase64 = (source, safe = false) => {
         : -1;
       if (result < 0) {
         throw new RangeError(
-          `Piscēs: Invalid character in Base64: ${character}.`,
+          `Piscēs: Invalid character in Base64: ${ucsCharacter}.`,
         );
       } else {
         return result;
@@ -136,28 +140,37 @@ const decodeBase64 = (source, safe = false) => {
     },
   );
   const { length } = u6s;
-  const dataView = new View(new Buffer(floor(length * 3 / 4)));
-  for (let index = 0; index < length - 1;) {
-    const dataIndex = ceil(index * 3 / 4);
-    const remainder = index % 3;
-    if (remainder == 0) {
-      call(viewSetUint8, dataView, [
-        dataIndex,
-        (u6s[index] << 2) + (u6s[++index] >> 4),
-      ]);
-    } else if (remainder == 1) {
-      call(viewSetUint8, dataView, [
-        dataIndex,
-        ((u6s[index] & 0xF) << 4) + (u6s[++index] >> 2),
-      ]);
-    } else {
-      call(viewSetUint8, dataView, [
-        dataIndex,
-        ((u6s[index] & 0x3) << 6) + u6s[++index],
-      ]);
+  if (length % 4 == 1) {
+    throw new RangeError(
+      `Piscēs: Base64 string has invalid length: ${source}.`,
+    );
+  } else {
+    const dataView = new View(new Buffer(floor(length * 3 / 4)));
+    for (let index = 0; index < length - 1;) {
+      // The final index is not handled; if the string is not divisible
+      // by 4, some bits might be dropped. This matches the “forgiving
+      // decode” behaviour specified by WhatW·G for base64.
+      const dataIndex = ceil(index * 3 / 4);
+      const remainder = index % 4;
+      if (remainder == 0) {
+        call(viewSetUint8, dataView, [
+          dataIndex,
+          u6s[index] << 2 | u6s[++index] >> 4,
+        ]);
+      } else if (remainder == 1) {
+        call(viewSetUint8, dataView, [
+          dataIndex,
+          u6s[index] << 4 | u6s[++index] >> 2,
+        ]);
+      } else { // remainder == 2
+        call(viewSetUint8, dataView, [
+          dataIndex,
+          u6s[index] << 6 | u6s[++index, index++],
+        ]);
+      }
     }
+    return call(getViewBuffer, dataView, []);
   }
-  return call(getViewBuffer, dataView, []);
 };
 
 /**
@@ -186,21 +199,20 @@ const encodeBase64 = (buffer, safe = false) => {
     const codeUnitIndex = ceil(index * 4 / 3);
     const currentIndex = codeUnitIndex + +(
       index % 3 == 0 && resultingCodeUnits[codeUnitIndex] != 0x3D
-    );
+    ); // every third byte handles two letters; this is for the second
     const remainder = currentIndex % 4;
+    const currentByte = call(viewGetUint8, dataView, [index]);
+    const nextByte = remainder % 3 && ++index < byteLength
+      // digits 1 & 2 span multiple bytes
+      ? call(viewGetUint8, dataView, [index])
+      : 0;
     const u6 = remainder == 0
-      ? call(viewGetUint8, dataView, [index]) >> 2
+      ? currentByte >> 2
       : remainder == 1
-      ? ((call(viewGetUint8, dataView, [index++]) & 0x3) << 4) +
-        (index < byteLength
-          ? call(viewGetUint8, dataView, [index]) >> 4
-          : 0)
+      ? (currentByte & 0b00000011) << 4 | nextByte >> 4
       : remainder == 2
-      ? ((call(viewGetUint8, dataView, [index++]) & 0xF) << 2) +
-        (index < byteLength
-          ? call(viewGetUint8, dataView, [index]) >> 6
-          : 0)
-      : call(viewGetUint8, dataView, [index++]) & 0x3F;
+      ? (currentByte & 0b00001111) << 2 | nextByte >> 6
+      : (++index, currentByte & 0b00111111); // remainder == 3
     const result = u6 < 26
       ? u6 + 65
       : u6 < 52
@@ -246,6 +258,9 @@ const sourceFromArgs = ($, $s) =>
  *
  * This function can also be used as a tag for a template literal. The
  * literal will be interpreted akin to `String.raw`.
+ *
+ * ☡ This function throws if the provided string is not a valid base64
+ * string.
  */
 export const base64Binary = ($, ...$s) =>
   decodeBase64(sourceFromArgs($, $s));
@@ -266,6 +281,9 @@ export const base64String = ($, ...$s) =>
  *
  * This function can also be used as a tag for a template literal. The
  * literal will be interpreted akin to `String.raw`.
+ *
+ * ☡ This function throws if the provided string is not a valid
+ * filename‐safe base64 string.
  */
 export const filenameSafeBase64Binary = ($, ...$s) =>
   decodeBase64(sourceFromArgs($, $s), true);
diff --git a/binary.test.js b/binary.test.js
index 161f8db..be6c6a3 100755
--- a/binary.test.js
+++ b/binary.test.js
@@ -1,7 +1,7 @@
 // ♓🌟 Piscēs ∷ binary.test.js
 // ====================================================================
 //
-// Copyright © 2020–2022 Lady [@ Lady’s Computer].
+// Copyright © 2020–2023 Lady [@ Lady’s Computer].
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -24,42 +24,147 @@ import {
   isFilenameSafeBase64,
 } from "./binary.js";
 
-const base64s = {
-  "AGIAYQBzAGUANgA0": "base64",
-  "R/Q=": new Uint16Array([62535]),
-  "S0lCSQ==": new Uint8ClampedArray([75, 73, 66, 73]).buffer,
-  YmFzZTY0: new DataView(
-    new Uint8Array([98, 97, 115, 101, 54, 52]).buffer,
-  ),
-};
+// These tests assume a LITTLE‐ENDIAN environment.
+const data = new Map([
+  ["", {
+    base64: "",
+  }],
+  ["base64", {
+    base64: "AGIAYQBzAGUANgA0",
+  }],
+  [new Uint16Array([62535]), {
+    base64: "R/Q=",
+  }],
+  [new Uint8ClampedArray([75, 73, 66, 73]).buffer, {
+    base64: "S0lCSQ==",
+  }],
+  [new DataView(new Uint8Array([98, 97, 115, 101, 54, 52]).buffer), {
+    base64: "YmFzZTY0",
+  }],
+
+  // The following three examples are from RFC 3548.
+  [new Uint8Array([0x14, 0xFB, 0x9C, 0x03, 0xD9, 0x7E]), {
+    base64: "FPucA9l+",
+  }],
+  [new Uint8Array([0x14, 0xFB, 0x9C, 0x03, 0xD9]), {
+    base64: "FPucA9k=",
+  }],
+  [new Uint8Array([0x14, 0xFB, 0x9C, 0x03]), {
+    base64: "FPucAw==",
+  }],
+
+  // The following examples are from the Ruby base32 gem.
+  [new Uint8Array([0x28]), {
+    base64: "KA==",
+  }],
+  [new Uint8Array([0xD6]), {
+    base64: "1g==",
+  }],
+  [new Uint16Array([0xF8D6]), {
+    base64: "1vg=",
+  }],
+  [new Uint8Array([0xD6, 0xF8, 0x00]), {
+    base64: "1vgA",
+  }],
+  [new Uint8Array([0xD6, 0xF8, 0x10]), {
+    base64: "1vgQ",
+  }],
+  [new Uint32Array([0x0C11F8D6]), {
+    base64: "1vgRDA==",
+  }],
+  [new Uint8Array([0xD6, 0xF8, 0x11, 0x0C, 0x80]), {
+    base64: "1vgRDIA=",
+  }],
+  [new Uint16Array([0xF8D6, 0x0C11, 0x3085]), {
+    base64: "1vgRDIUw",
+  }],
+]);
 
 describe("base64Binary", () => {
   it("[[Call]] returns the correct data", () => {
     assertEquals(
-      base64Binary("AGIAYQBzAGUANgA0"),
-      new Uint8Array(
-        Array.prototype.map.call(
-          "\u{0}b\u{0}a\u{0}s\u{0}e\u{0}6\u{0}4",
-          ($) => $.charCodeAt(0),
-        ),
-      ).buffer,
+      new Uint8Array(base64Binary("")),
+      new Uint8Array([]),
+      "<empty>",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("AGIAYQBzAGUANgA0")),
+      Uint8Array.from(
+        "\u{0}b\u{0}a\u{0}s\u{0}e\u{0}6\u{0}4",
+        ($) => $.charCodeAt(0),
+      ),
       "AGIAYQBzAGUANgA0",
     );
     assertEquals(
-      base64Binary("R/Q="),
-      new Uint16Array([62535]).buffer,
+      new Uint16Array(base64Binary("R/Q=")),
+      new Uint16Array([62535]),
       "R/Q=",
     );
     assertEquals(
-      base64Binary("S0lCSQ=="),
-      new Uint8ClampedArray([75, 73, 66, 73]).buffer,
+      new Uint8ClampedArray(base64Binary("S0lCSQ==")),
+      new Uint8ClampedArray([75, 73, 66, 73]),
       "S0lCSQ==",
     );
     assertEquals(
-      base64Binary("YmFzZTY0"),
-      new Uint8Array([98, 97, 115, 101, 54, 52]).buffer,
+      new Uint8Array(base64Binary("YmFzZTY0")),
+      new Uint8Array([98, 97, 115, 101, 54, 52]),
       "YmFzZTY0",
     );
+    assertEquals(
+      new Uint8Array(base64Binary("FPucA9l+")),
+      new Uint8Array([0x14, 0xFB, 0x9C, 0x03, 0xD9, 0x7E]),
+      "FPucA9l+",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("FPucA9k=")),
+      new Uint8Array([0x14, 0xFB, 0x9C, 0x03, 0xD9]),
+      "FPucA9k=",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("FPucAw==")),
+      new Uint8Array([0x14, 0xFB, 0x9C, 0x03]),
+      "FPucAw==",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("KA==")),
+      new Uint8Array([0x28]),
+      "KA==",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("1g==")),
+      new Uint8Array([0xD6]),
+      "1g==",
+    );
+    assertEquals(
+      new Uint16Array(base64Binary("1vg")),
+      new Uint16Array([0xF8D6]),
+      "1vg",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("1vgA")),
+      new Uint8Array([0xD6, 0xF8, 0x00]),
+      "1vgA",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("1vgQ")),
+      new Uint8Array([0xD6, 0xF8, 0x10]),
+      "1vgQ",
+    );
+    assertEquals(
+      new Uint32Array(base64Binary("1vgRDA==")),
+      new Uint32Array([0x0C11F8D6]),
+      "1vgRDA==",
+    );
+    assertEquals(
+      new Uint8Array(base64Binary("1vgRDIA=")),
+      new Uint8Array([0xD6, 0xF8, 0x11, 0x0C, 0x80]),
+      "1vgRDIA=",
+    );
+    assertEquals(
+      new Uint16Array(base64Binary("1vgRDIUw")),
+      new Uint16Array([0xF8D6, 0x0C11, 0x3085]),
+      "1vgRDIUw",
+    );
   });
 
   it("[[Call]] throws when provided with an invalid character", () => {
@@ -78,39 +183,82 @@ describe("base64Binary", () => {
 
 describe("base64String", () => {
   it("[[Call]] returns the correct string", () => {
-    Object.entries(base64s).forEach(([key, value]) =>
-      assertStrictEquals(base64String(value), key)
-    );
+    for (const [source, { base64 }] of data) {
+      assertStrictEquals(base64String(source), base64);
+    }
   });
 });
 
 describe("filenameSafeBase64Binary", () => {
   it("[[Call]] returns the correct data", () => {
     assertEquals(
-      filenameSafeBase64Binary("AGIAYQBzAGUANgA0"),
-      new Uint8Array(
-        Array.prototype.map.call(
-          "\u{0}b\u{0}a\u{0}s\u{0}e\u{0}6\u{0}4",
-          ($) => $.charCodeAt(0),
-        ),
-      ).buffer,
+      new Uint8Array(filenameSafeBase64Binary("")),
+      new Uint8Array([]),
+      "<empty>",
+    );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("AGIAYQBzAGUANgA0")),
+      Uint8Array.from(
+        "\u{0}b\u{0}a\u{0}s\u{0}e\u{0}6\u{0}4",
+        ($) => $.charCodeAt(0),
+      ),
       "AGIAYQBzAGUANgA0",
     );
     assertEquals(
-      filenameSafeBase64Binary("R_Q="),
-      new Uint16Array([62535]).buffer,
+      new Uint16Array(filenameSafeBase64Binary("R_Q=")),
+      new Uint16Array([62535]),
       "R/Q=",
     );
     assertEquals(
-      filenameSafeBase64Binary("S0lCSQ=="),
-      new Uint8ClampedArray([75, 73, 66, 73]).buffer,
+      new Uint8ClampedArray(filenameSafeBase64Binary("S0lCSQ==")),
+      new Uint8ClampedArray([75, 73, 66, 73]),
       "S0lCSQ==",
     );
     assertEquals(
-      filenameSafeBase64Binary("YmFzZTY0"),
-      new Uint8Array([98, 97, 115, 101, 54, 52]).buffer,
+      new Uint8Array(filenameSafeBase64Binary("YmFzZTY0")),
+      new Uint8Array([98, 97, 115, 101, 54, 52]),
       "YmFzZTY0",
     );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("KA==")),
+      new Uint8Array([0x28]),
+      "KA==",
+    );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("1g==")),
+      new Uint8Array([0xD6]),
+      "1g==",
+    );
+    assertEquals(
+      new Uint16Array(filenameSafeBase64Binary("1vg")),
+      new Uint16Array([0xF8D6]),
+      "1vg",
+    );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("1vgA")),
+      new Uint8Array([0xD6, 0xF8, 0x00]),
+      "1vgA",
+    );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("1vgQ")),
+      new Uint8Array([0xD6, 0xF8, 0x10]),
+      "1vgQ",
+    );
+    assertEquals(
+      new Uint32Array(filenameSafeBase64Binary("1vgQDA==")),
+      new Uint32Array([0x0C10F8D6]),
+      "1vgQDA==",
+    );
+    assertEquals(
+      new Uint8Array(filenameSafeBase64Binary("1vgQDIA=")),
+      new Uint8Array([0xD6, 0xF8, 0x10, 0x0C, 0x80]),
+      "1vgQDIA=",
+    );
+    assertEquals(
+      new Uint16Array(filenameSafeBase64Binary("1vgQDIUw")),
+      new Uint16Array([0xF8D6, 0x0C10, 0x3085]),
+      "1vgQDIUw",
+    );
   });
 
   it("[[Call]] throws when provided with an invalid character", () => {
@@ -129,18 +277,20 @@ describe("filenameSafeBase64Binary", () => {
 
 describe("filenameSafeBase64String", () => {
   it("[[Call]] returns the correct string", () => {
-    Object.entries(base64s).forEach(([key, value]) =>
+    for (const [source, { base64 }] of data) {
       assertStrictEquals(
-        filenameSafeBase64String(value),
-        key.replace("+", "-").replace("/", "_"),
-      )
-    );
+        filenameSafeBase64String(source),
+        base64.replace("+", "-").replace("/", "_"),
+      );
+    }
   });
 });
 
 describe("isBase64", () => {
   it("[[Call]] returns true for base64 strings", () => {
-    Object.keys(base64s).forEach((key) => assert(isBase64(key)));
+    for (const { base64 } of data.values()) {
+      assert(isBase64(base64));
+    }
   });
 
   it("[[Call]] returns false for others", () => {
@@ -164,11 +314,13 @@ describe("isBase64", () => {
 
 describe("isFilenameSafeBase64", () => {
   it("[[Call]] returns true for filename‐safe base64 strings", () => {
-    Object.keys(base64s).forEach((key) =>
+    for (const { base64 } of data.values()) {
       assert(
-        isFilenameSafeBase64(key.replace("+", "-").replace("/", "_")),
-      )
-    );
+        isFilenameSafeBase64(
+          base64.replace("+", "-").replace("/", "_"),
+        ),
+      );
+    }
   });
 
   it("[[Call]] returns false for others", () => {
diff --git a/deno.json b/deno.json
index 548f1fe..6bdb9a3 100644
--- a/deno.json
+++ b/deno.json
@@ -1,4 +1,5 @@
 {
-  "fmt": { "options": { "lineWidth": 71 } },
-  "lint": { "rules": { "exclude": ["constructor-super"] } }
+  "fmt": { "lineWidth": 71 },
+  "lint": { "rules": { "exclude": ["constructor-super"] } },
+  "lock": false
 }
diff --git a/dev-deps.js b/dev-deps.js
index 96858a6..f2ed7c9 100644
--- a/dev-deps.js
+++ b/dev-deps.js
@@ -1,7 +1,7 @@
 // ♓🌟 Piscēs ∷ dev-deps.js
 // ====================================================================
 //
-// Copyright © 2022 Lady [@ Lady’s Computer].
+// Copyright © 2022–2023 Lady [@ Lady’s Computer].
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -12,13 +12,13 @@ export {
   assertEquals,
   assertStrictEquals,
   assertThrows,
-} from "https://deno.land/std@0.148.0/testing/asserts.ts";
+} from "https://deno.land/std@0.188.0/testing/asserts.ts";
 export {
   describe,
   it,
-} from "https://deno.land/std@0.148.0/testing/bdd.ts";
+} from "https://deno.land/std@0.188.0/testing/bdd.ts";
 export {
   assertSpyCall,
   assertSpyCalls,
   spy,
-} from "https://deno.land/std@0.148.0/testing/mock.ts";
+} from "https://deno.land/std@0.188.0/testing/mock.ts";