function compress(dataset, config, { zip } = {}) { const { bytesPerRow, meta } = prepare(dataset, config); createMasks(meta, bytesPerRow); const buffer = new ArrayBuffer(bytesPerRow * dataset.length); const view = new DataView(buffer, 0, bytesPerRow * dataset.length); for (let i = 0; i < dataset.length; i++) { setRow(view, dataset[i], i); } return new Promise((resolve) => { const blob = new Blob([buffer]); const result = zip ? compressBlob(blob).then(blobToDataURL) : blobToDataURL(blob); result.then((dataURL) => resolve({ numberOfRows: dataset.length, bytesPerRow, zipped: zip, meta, //config, // optional //compress, // optional decompress: `(${decompress.toString()})`, documentation: "https://observablehq.com/@notanaccent/bit-bunching-compression", dataURL }) ); }); function setRow(view, dataRow, index) { let binaryRow = ""; for (let j = 0; j < meta.length; j++) { binaryRow += encodeValue(dataRow[meta[j].field], index, meta[j]); } while (binaryRow.length < bytesPerRow * 8) { binaryRow += "0"; } for (let i = 0; i < bytesPerRow; i++) { view.setUint8( index * bytesPerRow + i, parseInt(binaryRow.slice(i * 8, i * 8 + 8), 2) ); } } function encodeValue(dataPoint, index, fieldMeta) { const integerValue = packValue(dataPoint, index, fieldMeta) || 0; let binaryValue = Math.round(integerValue) .toString(2) .slice(0, fieldMeta.length); while (binaryValue.length < fieldMeta.length) { binaryValue = "0" + binaryValue; } return binaryValue; } function packValue(dataPoint, index, fieldMeta) { switch (fieldMeta.type) { case "index": return (index - fieldMeta.datum) / fieldMeta.gain; case "integer": return +dataPoint - fieldMeta.datum; case "float": return (+dataPoint - fieldMeta.datum) / fieldMeta.precision; case "enum": return fieldMeta.lut.indexOf(dataPoint); default: return undefined; } } function prepare(dataset, config = []) { // TODO autodetect best config const meta = []; let offset = 0; for (let c of config) { let slot = { field: c.field, type: c.type, length: 0 }; if (typeof c.postProcess === "function") { slot.postProcessString = `(${c.postProcess.toString()})`; } if (c.type === "enum") { slot.lut = Array.from(unique(dataset.map((d) => d[c.field]))); slot.length = Math.ceil(Math.log(slot.lut.length) / Math.log(2)); } else { const d0 = +dataset[0][c.field]; const min = dataset.reduce((a, d) => Math.min(a, +d[c.field]), d0); const max = dataset.reduce((a, d) => Math.max(a, +d[c.field]), d0); const range = max - min; slot.datum = min; switch (c.type) { case "integer": slot.length = Math.ceil(Math.log(range) / Math.log(2)); break; case "float": // TODO absolute deviation polynomial regression slot.precision = c.precision || range / 2 ** 16; slot.length = Math.ceil( Math.log(range / slot.precision) / Math.log(2) ); break; case "index": const gain2 = c.gain || range / (dataset.length - 1); slot.gain = gain2; slot.length = 0; break; default: throw ( "Bad type <" + c.type + "> for field <" + c.field + "> during preperation for data encoding." ); } } slot.offset = offset; offset += slot.length; meta.push(slot); } const bytesPerRow = Math.ceil(offset / 8); return { bytesPerRow, meta }; } function createMasks(meta, bytesPerRow) { for (let i = 0; i < meta.length; i++) { let fieldMeta = meta[i]; fieldMeta.mask = []; const { field, offset, length } = { ...fieldMeta }; const start = Math.floor(offset / 8), end = Math.ceil((offset + length) / 8), rem = (8 - ((offset + length) % 8)) % 8; fieldMeta.endBit = offset + length; for (let b = 0; b < bytesPerRow; b++) { let mask = b < start || b >= end ? 0x00 : b === start && b === end - 1 ? ((0xff >> offset % 8) >> rem) << rem : b === start ? 0xff >> offset % 8 : b === end - 1 ? (0xff >> rem) << rem : 0xff; fieldMeta.mask.push(mask); } } } function unique(arr) { // could also use d3.union const dict = {}; for (let i = 0; i < arr.length; i++) { dict[arr[i]] = true; } return Object.keys(dict); } function blobToDataURL(blob) { return new Promise((resolve) => { const reader = new FileReader(); reader.onload = (e) => resolve(e.target.result); reader.readAsDataURL(blob); }); } function compressBlob(blob) { const format = zip === "deflate" ? "deflate" : "gzip"; return new Response( blob.stream().pipeThrough(new window.CompressionStream(format)) ).blob(); } }