36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 1/**
2 * Lossless codecs run in the browser, on int16 sample data.
3 *
4 * The baseline throughout is the uncompressed int16 stream: 2 bytes = 16 bits
5 * per sample. A ratio is (baseline bytes) / (compressed bytes).
6 */
7import { zlibSync } from 'fflate'
8import { init as zstdInit, compress as zstdCompress } from '@bokuweb/zstd-wasm'
9import { ansEncode, ansDecode, encodedSize } from './ans'
10import { fitLpc, lpcResidual, lpcRestore, modelSize } from './lpc'
11// Bundled as an asset so the page needs no network at run time. The path is
12// relative rather than a bare specifier because the package's `exports` map
13// has no entry for the wasm file, so `@bokuweb/zstd-wasm/dist/web/zstd.wasm`
14// cannot be resolved.
15import zstdWasmUrl from '../../node_modules/@bokuweb/zstd-wasm/dist/web/zstd.wasm?url'
18 * Compressed size in bytes, including any table the decoder needs. Codecs
19 * that code against an explicit probability model also report that model's
20 * ideal cost in bits, so the coder's own overhead — its tables, its
21 * coefficients, and its arithmetic loss — can be shown against it.
22 */
23export type CodecSize = number | { bytes: number; modelBits: number }
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 25export interface Codec {
26 name: string
27 /** Longer description, shown on hover. */
28 note: string
4ec0133Code against the prediction, not the integer residualJeremy Magland 29 size: (samples: Int16Array, bytes: Uint8Array) => CodecSize
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 30}
32/**
33 * First differences, in int16 with wraparound — exactly invertible, and the
34 * standard prefilter for signals whose neighbouring samples are related.
35 */
36function delta(samples: Int16Array): Int16Array {
37 const d = new Int16Array(samples.length)
38 d[0] = samples[0]
39 for (let i = 1; i < samples.length; i++) {
40 d[i] = ((samples[i] - samples[i - 1]) << 16) >> 16
41 }
42 return d
43}
45function undelta(d: Int16Array): Int16Array {
46 const s = new Int16Array(d.length)
47 s[0] = d[0]
48 for (let i = 1; i < d.length; i++) {
49 s[i] = ((s[i - 1] + d[i]) << 16) >> 16
50 }
51 return s
52}
54function asBytes(samples: Int16Array): Uint8Array {
55 return new Uint8Array(samples.buffer, samples.byteOffset, samples.byteLength)
56}
58/**
59 * Size of an ANS encoding of `coded`, after decoding it, running `inverse` to
60 * undo whatever prefilter produced it, and checking the result against the
61 * original samples — so a reported size always belongs to an encoding that
62 * actually round-trips. `extraBytes` covers anything else the decoder needs,
63 * such as predictor coefficients.
65 * ANS codes each symbol against the histogram of `coded`, so that histogram's
66 * order-0 entropy is exactly the model this coder is aiming at.
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 67 */
68function ansSize(
69 samples: Int16Array,
70 coded: Int16Array,
71 inverse: (coded: Int16Array) => Int16Array,
72 extraBytes = 0,
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 74 const encoded = ansEncode(coded)
75 const decoded = inverse(ansDecode(encoded))
76 if (decoded.length !== samples.length) throw new Error('ANS round-trip length mismatch')
77 for (let i = 0; i < samples.length; i++) {
78 if (decoded[i] !== samples[i]) throw new Error(`ANS round-trip mismatch at ${i}`)
79 }
81 bytes: encodedSize(encoded) + extraBytes,
82 modelBits: order0Entropy(coded) * coded.length,
83 }
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 84}
e411dffMake LPC order and compression block size controlsJeremy Magland 86/** Predictor orders the UI offers; 32 is the FLAC default and ours. */
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 87export const LPC_ORDERS = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
e411dffMake LPC order and compression block size controlsJeremy Magland 88export const DEFAULT_LPC_ORDER = 32
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 89
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 90interface LpcTransform {
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 91 residual: Int16Array
92 restore: (residual: Int16Array) => Int16Array
93 extraBytes: number
96/**
97 * The fit and the residual are wanted four times per measurement — once by
98 * each LPC codec and once by the entropy bound — and cost O(order · N) each,
99 * which is seconds at the top of the order range. Compute once per
100 * (samples, order); the entry dies with the sample block.
101 */
102const transformCache = new WeakMap<Int16Array, Map<number, LpcTransform>>()
104/** Fit the predictor and take the residual, with the coefficients' cost. */
105function lpcTransform(samples: Int16Array, order: number): LpcTransform {
106 let byOrder = transformCache.get(samples)
107 if (!byOrder) {
108 byOrder = new Map()
109 transformCache.set(samples, byOrder)
110 }
111 const cached = byOrder.get(order)
112 if (cached) return cached
e411dffMake LPC order and compression block size controlsJeremy Magland 114 const model = fitLpc(samples, order)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 115 if (!model) throw new Error('LPC fit failed')
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 116 const transform: LpcTransform = {
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 117 residual: lpcResidual(samples, model),
118 restore: residual => lpcRestore(residual, model),
119 extraBytes: modelSize(model),
120 }
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 121 byOrder.set(order, transform)
122 return transform
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 123}
125export const ZLIB: Codec = {
126 name: 'zlib -9',
127 note: 'DEFLATE at maximum level — the HDF5 gzip filter',
128 size: (_s, bytes) => zlibSync(bytes, { level: 9 }).length,
129}
131export const ZSTD: Codec = {
132 name: 'zstd -19',
133 note: 'Zstandard at level 19 — the Blosc/Zarr default family',
134 size: (_s, bytes) => zstdCompress(bytes, 19).length,
135}
137export const ANS: Codec = {
138 name: 'ANS',
139 note: 'rANS entropy coder over the sample histogram, ported from simple_ans; the size includes the symbol table',
140 size: samples => ansSize(samples, samples, x => x),
141}
143export const DELTA_ZLIB: Codec = {
144 name: 'delta + zlib -9',
145 note: 'First differences, then DEFLATE',
146 size: samples => zlibSync(asBytes(delta(samples)), { level: 9 }).length,
147}
149export const DELTA_ZSTD: Codec = {
150 name: 'delta + zstd -19',
151 note: 'First differences, then Zstandard 19',
152 size: samples => zstdCompress(asBytes(delta(samples)), 19).length,
153}
155export const DELTA_ANS: Codec = {
156 name: 'delta + ANS',
157 note: 'First differences, then the rANS entropy coder',
158 size: samples => ansSize(samples, delta(samples), undelta),
159}
e411dffMake LPC order and compression block size controlsJeremy Magland 161/** The three LPC codecs at a given predictor order. */
162export function lpcCodecs(order: number): Codec[] {
163 const note = `Order-${order} linear prediction with integer coefficients; the size includes the coefficients`
164 return [
165 {
166 name: `LPC(${order}) + zlib -9`,
167 note: `${note}, then DEFLATE`,
168 size: samples => {
169 const { residual, extraBytes } = lpcTransform(samples, order)
170 return zlibSync(asBytes(residual), { level: 9 }).length + extraBytes
171 },
172 },
173 {
174 name: `LPC(${order}) + zstd -19`,
175 note: `${note}, then Zstandard 19`,
176 size: samples => {
177 const { residual, extraBytes } = lpcTransform(samples, order)
178 return zstdCompress(asBytes(residual), 19).length + extraBytes
179 },
180 },
181 {
182 name: `LPC(${order}) + ANS`,
183 note: `${note}, then the rANS entropy coder`,
184 size: samples => {
185 const { residual, restore, extraBytes } = lpcTransform(samples, order)
186 return ansSize(samples, residual, restore, extraBytes)
187 },
188 },
189 ]
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 190}
192/** The general-purpose compressors, which know nothing about the data. */
193export const GENERAL_CODECS: Codec[] = [ZLIB, ZSTD]
196 * Order-0 (memoryless) entropy of an int16 stream, in bits per sample: what a
197 * perfect entropy coder for the sample histogram would spend, with nothing
4ec0133Code against the prediction, not the integer residualJeremy Magland 198 * charged for describing that histogram — the model an ANS coder aims at.
200export function order0Entropy(samples: Int16Array): number {
201 const counts = new Int32Array(65536)
202 for (let i = 0; i < samples.length; i++) counts[samples[i] + 32768]++
203 let bits = 0
204 for (const c of counts) {
205 if (c > 0) {
206 const p = c / samples.length
207 bits -= p * Math.log2(p)
208 }
209 }
210 return bits
211}
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 213let ready: Promise<void> | null = null
215// zstd-wasm publishes the *node* build's types while the bundler resolves the
216// browser build (its `exports` map has a "browser" condition). Only the browser
217// build's `init` takes a wasm URL, so the signature has to be restated here.
218const initWithUrl = zstdInit as unknown as (path?: string) => Promise<void>
220/** Load the zstd wasm module. Safe to call repeatedly. */
221export function initCodecs(): Promise<void> {
222 if (!ready) {
223 ready = initWithUrl(zstdWasmUrl).catch((err: unknown) => {
224 ready = null
225 throw err
226 })
227 }
228 return ready
229}
231export interface CodecResult {
232 codec: string
233 note: string
234 bytes: number
235 ratio: number
236 bitsPerSample: number
4ec0133Code against the prediction, not the integer residualJeremy Magland 237 /** Ideal cost of this coder's own probability model, when it has one — the
238 * yardstick its output is measured against. Absent for zlib and zstd. */
239 modelBitsPerSample?: number
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 240}
243 * Compress one int16 block with each of the given codecs. Takes the samples
244 * rather than raw bytes so every codec — and the entropy bounds — key the
245 * LPC cache off the same array.
246 */
247export function compressAll(samples: Int16Array, codecs: Codec[]): CodecResult[] {
248 const bytes = asBytes(samples)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 249 return codecs.map(codec => {
4ec0133Code against the prediction, not the integer residualJeremy Magland 250 const out = codec.size(samples, bytes)
251 const size = typeof out === 'number' ? out : out.bytes
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 252 return {
253 codec: codec.name,
254 note: codec.note,
256 ratio: bytes.byteLength / size,
257 bitsPerSample: (8 * size) / samples.length,
259 typeof out === 'number' ? undefined : out.modelBits / samples.length,
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 260 }
261 })
262}