path: root/packages/idb-bridge/src/util/key-storage.ts

/*
 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;
}