1 files changed, 363 insertions, 0 deletions
diff --git a/packages/idb-bridge/src/util/key-storage.ts b/packages/idb-bridge/src/util/key-storage.ts
new file mode 100644
index 000000000..b71548dd3
--- /dev/null
+++ b/packages/idb-bridge/src/util/key-storage.ts
@@ -0,0 +1,363 @@
+/*
+ This file is part of GNU Taler
+ (C) 2023 Taler Systems S.A.
+
+ GNU Taler is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ */
+
+/*
+Encoding rules (inspired by Firefox, but slightly simplified):
+
+Numbers:   0x10 n n n n n n n n
+Dates:     0x20 n n n n n n n n
+Strings:   0x30 s s s s ... 0
+Binaries:  0x40 s s s s ... 0
+Arrays:    0x50 i i i ... 0
+
+Numbers/dates are encoded as 64-bit IEEE 754 floats with the sign bit
+flipped, in order to make them sortable.
+*/
+
+/**
+ * Imports.
+ */
+import { IDBValidKey } from "../idbtypes.js";
+
+const tagNum = 0xa0;
+const tagDate = 0xb0;
+const tagString = 0xc0;
+const tagBinary = 0xc0;
+const tagArray = 0xe0;
+
+const oneByteOffset = 0x01;
+const twoByteOffset = 0x7f;
+const oneByteMax = 0x7e;
+const twoByteMax = 0x3fff + twoByteOffset;
+const twoByteMask = 0b1000_0000;
+const threeByteMask = 0b1100_0000;
+
+export function countEncSize(c: number): number {
+  if (c > twoByteMax) {
+    return 3;
+  }
+  if (c > oneByteMax) {
+    return 2;
+  }
+  return 1;
+}
+
+export function writeEnc(dv: DataView, offset: number, c: number): number {
+  if (c > twoByteMax) {
+    dv.setUint8(offset + 2, (c & 0xff) << 6);
+    dv.setUint8(offset + 1, (c >>> 2) & 0xff);
+    dv.setUint8(offset, threeByteMask | (c >>> 10));
+    return 3;
+  } else if (c > oneByteMax) {
+    c -= twoByteOffset;
+    dv.setUint8(offset + 1, c & 0xff);
+    dv.setUint8(offset, (c >>> 8) | twoByteMask);
+    return 2;
+  } else {
+    c += oneByteOffset;
+    dv.setUint8(offset, c);
+    return 1;
+  }
+}
+
+export function internalSerializeString(
+  dv: DataView,
+  offset: number,
+  key: string,
+): number {
+  dv.setUint8(offset, tagString);
+  let n = 1;
+  for (let i = 0; i < key.length; i++) {
+    let c = key.charCodeAt(i);
+    n += writeEnc(dv, offset + n, c);
+  }
+  // Null terminator
+  dv.setUint8(offset + n, 0);
+  n++;
+  return n;
+}
+
+export function countSerializeKey(key: IDBValidKey): number {
+  if (typeof key === "number") {
+    return 9;
+  }
+  if (key instanceof Date) {
+    return 9;
+  }
+  if (key instanceof ArrayBuffer) {
+    let len = 2;
+    const uv = new Uint8Array(key);
+    for (let i = 0; i < uv.length; i++) {
+      len += countEncSize(uv[i]);
+    }
+    return len;
+  }
+  if (ArrayBuffer.isView(key)) {
+    let len = 2;
+    const uv = new Uint8Array(key.buffer, key.byteOffset, key.byteLength);
+    for (let i = 0; i < uv.length; i++) {
+      len += countEncSize(uv[i]);
+    }
+    return len;
+  }
+  if (typeof key === "string") {
+    let len = 2;
+    for (let i = 0; i < key.length; i++) {
+      len += countEncSize(key.charCodeAt(i));
+    }
+    return len;
+  }
+  if (Array.isArray(key)) {
+    let len = 2;
+    for (let i = 0; i < key.length; i++) {
+      len += countSerializeKey(key[i]);
+    }
+    return len;
+  }
+  throw Error("unsupported type for key");
+}
+
+function internalSerializeNumeric(
+  dv: DataView,
+  offset: number,
+  tag: number,
+  val: number,
+): number {
+  dv.setUint8(offset, tagNum);
+  dv.setFloat64(offset + 1, val);
+  // Flip sign bit
+  let b = dv.getUint8(offset + 1);
+  b ^= 0x80;
+  dv.setUint8(offset + 1, b);
+  return 9;
+}
+
+function internalSerializeArray(
+  dv: DataView,
+  offset: number,
+  key: any[],
+): number {
+  dv.setUint8(offset, tagArray);
+  let n = 1;
+  for (let i = 0; i < key.length; i++) {
+    n += internalSerializeKey(key[i], dv, offset + n);
+  }
+  dv.setUint8(offset + n, 0);
+  n++;
+  return n;
+}
+
+function internalSerializeBinary(
+  dv: DataView,
+  offset: number,
+  key: Uint8Array,
+): number {
+  dv.setUint8(offset, tagBinary);
+  let n = 1;
+  for (let i = 0; i < key.length; i++) {
+    n += internalSerializeKey(key[i], dv, offset + n);
+  }
+  dv.setUint8(offset + n, 0);
+  n++;
+  return n;
+}
+
+function internalSerializeKey(
+  key: IDBValidKey,
+  dv: DataView,
+  offset: number,
+): number {
+  if (typeof key === "number") {
+    return internalSerializeNumeric(dv, offset, tagNum, key);
+  }
+  if (key instanceof Date) {
+    return internalSerializeNumeric(dv, offset, tagDate, key.getDate());
+  }
+  if (typeof key === "string") {
+    return internalSerializeString(dv, offset, key);
+  }
+  if (Array.isArray(key)) {
+    return internalSerializeArray(dv, offset, key);
+  }
+  if (key instanceof ArrayBuffer) {
+    return internalSerializeBinary(dv, offset, new Uint8Array(key));
+  }
+  if (ArrayBuffer.isView(key)) {
+    const uv = new Uint8Array(key.buffer, key.byteOffset, key.byteLength);
+    return internalSerializeBinary(dv, offset, uv);
+  }
+  throw Error("unsupported type for key");
+}
+
+export function serializeKey(key: IDBValidKey): Uint8Array {
+  const len = countSerializeKey(key);
+  let buf = new Uint8Array(len);
+  const outLen = internalSerializeKey(key, new DataView(buf.buffer), 0);
+  if (len != outLen) {
+    throw Error("internal invariant failed");
+  }
+  let numTrailingZeroes = 0;
+  for (let i = buf.length - 1; i >= 0 && buf[i] == 0; i--, numTrailingZeroes++);
+  if (numTrailingZeroes > 0) {
+    buf = buf.slice(0, buf.length - numTrailingZeroes);
+  }
+  return buf;
+}
+
+function internalReadString(dv: DataView, offset: number): [number, string] {
+  const chars: string[] = [];
+  while (offset < dv.byteLength) {
+    const v = dv.getUint8(offset);
+    if (v == 0) {
+      // Got end-of-string.
+      offset += 1;
+      break;
+    }
+    let c: number;
+    if ((v & threeByteMask) === threeByteMask) {
+      const b1 = v;
+      const b2 = dv.getUint8(offset + 1);
+      const b3 = dv.getUint8(offset + 2);
+      c = (b1 << 10) | (b2 << 2) | (b3 >> 6);
+      offset += 3;
+    } else if ((v & twoByteMask) === twoByteMask) {
+      const b1 = v & ~twoByteMask;
+      const b2 = dv.getUint8(offset + 1);
+      c = ((b1 << 8) | b2) + twoByteOffset;
+      offset += 2;
+    } else {
+      c = v - oneByteOffset;
+      offset += 1;
+    }
+    chars.push(String.fromCharCode(c));
+  }
+  return [offset, chars.join("")];
+}
+
+function internalReadBytes(dv: DataView, offset: number): [number, Uint8Array] {
+  let count = 0;
+  while (offset + count < dv.byteLength) {
+    const v = dv.getUint8(offset + count);
+    if (v === 0) {
+      break;
+    }
+    count++;
+  }
+  let writePos = 0;
+  const bytes = new Uint8Array(count);
+  while (offset < dv.byteLength) {
+    const v = dv.getUint8(offset);
+    if (v == 0) {
+      offset += 1;
+      break;
+    }
+    let c: number;
+    if ((v & threeByteMask) === threeByteMask) {
+      const b1 = v;
+      const b2 = dv.getUint8(offset + 1);
+      const b3 = dv.getUint8(offset + 2);
+      c = (b1 << 10) | (b2 << 2) | (b3 >> 6);
+      offset += 3;
+    } else if ((v & twoByteMask) === twoByteMask) {
+      const b1 = v & ~twoByteMask;
+      const b2 = dv.getUint8(offset + 1);
+      c = ((b1 << 8) | b2) + twoByteOffset;
+      offset += 2;
+    } else {
+      c = v - oneByteOffset;
+      offset += 1;
+    }
+    bytes[writePos] = c;
+    writePos++;
+  }
+  return [offset, bytes];
+}
+
+/**
+ * Same as DataView.getFloat64, but logically pad input
+ * with zeroes on the right if read offset would be out
+ * of bounds.
+ * 
+ * This allows reading from buffers where zeros have been
+ * truncated.
+ */
+function getFloat64Trunc(dv: DataView, offset: number): number {
+  if (offset + 7 >= dv.byteLength) {
+    const buf = new Uint8Array(8);
+    for (let i = offset; i < dv.byteLength; i++) {
+      buf[i - offset] = dv.getUint8(i);
+    }
+    const dv2 = new DataView(buf.buffer);
+    return dv2.getFloat64(0);
+  } else {
+    return dv.getFloat64(offset);
+  }
+}
+
+function internalDeserializeKey(
+  dv: DataView,
+  offset: number,
+): [number, IDBValidKey] {
+  let tag = dv.getUint8(offset);
+  switch (tag) {
+    case tagNum: {
+      const num = -getFloat64Trunc(dv, offset + 1);
+      const newOffset = Math.min(offset + 9, dv.byteLength);
+      return [newOffset, num];
+    }
+    case tagDate: {
+      const num = -getFloat64Trunc(dv, offset + 1);
+      const newOffset = Math.min(offset + 9, dv.byteLength);
+      return [newOffset, new Date(num)];
+    }
+    case tagString: {
+      return internalReadString(dv, offset + 1);
+    }
+    case tagBinary: {
+      return internalReadBytes(dv, offset + 1);
+    }
+    case tagArray: {
+      const arr: any[] = [];
+      offset += 1;
+      while (offset < dv.byteLength) {
+        const innerTag = dv.getUint8(offset);
+        if (innerTag === 0) {
+          offset++;
+          break;
+        }
+        const [innerOff, innerVal] = internalDeserializeKey(dv, offset);
+        arr.push(innerVal);
+        offset = innerOff;
+      }
+      return [offset, arr];
+    }
+    default:
+      throw Error("invalid key (unrecognized tag)");
+  }
+}
+
+export function deserializeKey(encodedKey: Uint8Array): IDBValidKey {
+  const dv = new DataView(
+    encodedKey.buffer,
+    encodedKey.byteOffset,
+    encodedKey.byteLength,
+  );
+  let [off, res] = internalDeserializeKey(dv, 0);
+  if (off != encodedKey.byteLength) {
+    throw Error("internal invariant failed");
+  }
+  return res;
+}