diff options
Diffstat (limited to 'packages/idb-bridge/src/util/key-storage.ts')
-rw-r--r-- | packages/idb-bridge/src/util/key-storage.ts | 363 |
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; +} |