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'
17export interface Codec {
18 name: string
19 /** Longer description, shown on hover. */
20 note: string
21 /** Compressed size in bytes, including any table the decoder needs. */
22 size: (samples: Int16Array, bytes: Uint8Array) => number
23}
25/**
26 * First differences, in int16 with wraparound — exactly invertible, and the
27 * standard prefilter for signals whose neighbouring samples are related.
28 */
29function delta(samples: Int16Array): Int16Array {
30 const d = new Int16Array(samples.length)
31 d[0] = samples[0]
32 for (let i = 1; i < samples.length; i++) {
33 d[i] = ((samples[i] - samples[i - 1]) << 16) >> 16
34 }
35 return d
36}
38function undelta(d: Int16Array): Int16Array {
39 const s = new Int16Array(d.length)
40 s[0] = d[0]
41 for (let i = 1; i < d.length; i++) {
42 s[i] = ((s[i - 1] + d[i]) << 16) >> 16
43 }
44 return s
45}
47function asBytes(samples: Int16Array): Uint8Array {
48 return new Uint8Array(samples.buffer, samples.byteOffset, samples.byteLength)
49}
51/**
52 * Size of an ANS encoding of `coded`, after decoding it, running `inverse` to
53 * undo whatever prefilter produced it, and checking the result against the
54 * original samples — so a reported size always belongs to an encoding that
55 * actually round-trips. `extraBytes` covers anything else the decoder needs,
56 * such as predictor coefficients.
57 */
58function ansSize(
59 samples: Int16Array,
60 coded: Int16Array,
61 inverse: (coded: Int16Array) => Int16Array,
62 extraBytes = 0,
63): number {
64 const encoded = ansEncode(coded)
65 const decoded = inverse(ansDecode(encoded))
66 if (decoded.length !== samples.length) throw new Error('ANS round-trip length mismatch')
67 for (let i = 0; i < samples.length; i++) {
68 if (decoded[i] !== samples[i]) throw new Error(`ANS round-trip mismatch at ${i}`)
69 }
70 return encodedSize(encoded) + extraBytes
71}
e411dffMake LPC order and compression block size controlsJeremy Magland 73/** Predictor orders the UI offers; 32 is the FLAC default and ours. */
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 74export const LPC_ORDERS = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
e411dffMake LPC order and compression block size controlsJeremy Magland 75export const DEFAULT_LPC_ORDER = 32
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 76
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 77interface LpcTransform {
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 78 residual: Int16Array
79 restore: (residual: Int16Array) => Int16Array
80 extraBytes: number
83/**
84 * The fit and the residual are wanted four times per measurement — once by
85 * each LPC codec and once by the entropy bound — and cost O(order · N) each,
86 * which is seconds at the top of the order range. Compute once per
87 * (samples, order); the entry dies with the sample block.
88 */
89const transformCache = new WeakMap<Int16Array, Map<number, LpcTransform>>()
91/** Fit the predictor and take the residual, with the coefficients' cost. */
92function lpcTransform(samples: Int16Array, order: number): LpcTransform {
93 let byOrder = transformCache.get(samples)
94 if (!byOrder) {
95 byOrder = new Map()
96 transformCache.set(samples, byOrder)
97 }
98 const cached = byOrder.get(order)
99 if (cached) return cached
e411dffMake LPC order and compression block size controlsJeremy Magland 101 const model = fitLpc(samples, order)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 102 if (!model) throw new Error('LPC fit failed')
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 103 const transform: LpcTransform = {
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 104 residual: lpcResidual(samples, model),
105 restore: residual => lpcRestore(residual, model),
106 extraBytes: modelSize(model),
107 }
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 108 byOrder.set(order, transform)
109 return transform
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 110}
112export const ZLIB: Codec = {
113 name: 'zlib -9',
114 note: 'DEFLATE at maximum level — the HDF5 gzip filter',
115 size: (_s, bytes) => zlibSync(bytes, { level: 9 }).length,
116}
118export const ZSTD: Codec = {
119 name: 'zstd -19',
120 note: 'Zstandard at level 19 — the Blosc/Zarr default family',
121 size: (_s, bytes) => zstdCompress(bytes, 19).length,
122}
124export const ANS: Codec = {
125 name: 'ANS',
126 note: 'rANS entropy coder over the sample histogram, ported from simple_ans; the size includes the symbol table',
127 size: samples => ansSize(samples, samples, x => x),
128}
130export const DELTA_ZLIB: Codec = {
131 name: 'delta + zlib -9',
132 note: 'First differences, then DEFLATE',
133 size: samples => zlibSync(asBytes(delta(samples)), { level: 9 }).length,
134}
136export const DELTA_ZSTD: Codec = {
137 name: 'delta + zstd -19',
138 note: 'First differences, then Zstandard 19',
139 size: samples => zstdCompress(asBytes(delta(samples)), 19).length,
140}
142export const DELTA_ANS: Codec = {
143 name: 'delta + ANS',
144 note: 'First differences, then the rANS entropy coder',
145 size: samples => ansSize(samples, delta(samples), undelta),
146}
e411dffMake LPC order and compression block size controlsJeremy Magland 148/** The three LPC codecs at a given predictor order. */
149export function lpcCodecs(order: number): Codec[] {
150 const note = `Order-${order} linear prediction with integer coefficients; the size includes the coefficients`
151 return [
152 {
153 name: `LPC(${order}) + zlib -9`,
154 note: `${note}, then DEFLATE`,
155 size: samples => {
156 const { residual, extraBytes } = lpcTransform(samples, order)
157 return zlibSync(asBytes(residual), { level: 9 }).length + extraBytes
158 },
159 },
160 {
161 name: `LPC(${order}) + zstd -19`,
162 note: `${note}, then Zstandard 19`,
163 size: samples => {
164 const { residual, extraBytes } = lpcTransform(samples, order)
165 return zstdCompress(asBytes(residual), 19).length + extraBytes
166 },
167 },
168 {
169 name: `LPC(${order}) + ANS`,
170 note: `${note}, then the rANS entropy coder`,
171 size: samples => {
172 const { residual, restore, extraBytes } = lpcTransform(samples, order)
173 return ansSize(samples, residual, restore, extraBytes)
174 },
175 },
176 ]
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 177}
179/** The general-purpose compressors, which know nothing about the data. */
180export const GENERAL_CODECS: Codec[] = [ZLIB, ZSTD]
183 * Order-0 (memoryless) entropy of an int16 stream, in bits per sample: what a
184 * perfect entropy coder for the sample histogram would spend, with nothing
185 * charged for describing that histogram. The ANS bars sit above this by the
186 * symbol table plus the coder's own arithmetic loss.
187 */
188export function order0Entropy(samples: Int16Array): number {
189 const counts = new Int32Array(65536)
190 for (let i = 0; i < samples.length; i++) counts[samples[i] + 32768]++
191 let bits = 0
192 for (const c of counts) {
193 if (c > 0) {
194 const p = c / samples.length
195 bits -= p * Math.log2(p)
196 }
197 }
198 return bits
199}
201export interface BoundResult {
202 /** The prefilter group this bounds, matching the codec groups. */
203 group: string
204 note: string
205 bitsPerSample: number
206 ratio: number
207 bytes: number
208}
210/** The order-0 bound for each prefilter: raw samples, delta, LPC residual. */
e411dffMake LPC order and compression block size controlsJeremy Magland 211export function entropyBounds(samples: Int16Array, lpcOrder: number): BoundResult[] {
355ddbbAdd per-group entropy limit bars to the compression chartJeremy Magland 212 const streams: { group: string; what: string; data: Int16Array }[] = [
213 { group: 'no prefilter', what: 'the samples themselves', data: samples },
214 { group: 'delta', what: 'the first differences', data: delta(samples) },
216 group: 'LPC',
217 what: `the order-${lpcOrder} prediction residual`,
218 data: lpcTransform(samples, lpcOrder).residual,
219 },
221 return streams.map(({ group, what, data }) => {
222 const bitsPerSample = order0Entropy(data)
223 return {
224 group,
225 note: `order-0 entropy of ${what} — the limit for a per-sample entropy coder, with no symbol table or coefficients charged`,
226 bitsPerSample,
227 ratio: 16 / bitsPerSample,
228 bytes: Math.ceil((bitsPerSample * samples.length) / 8),
229 }
230 })
231}
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 233let ready: Promise<void> | null = null
235// zstd-wasm publishes the *node* build's types while the bundler resolves the
236// browser build (its `exports` map has a "browser" condition). Only the browser
237// build's `init` takes a wasm URL, so the signature has to be restated here.
238const initWithUrl = zstdInit as unknown as (path?: string) => Promise<void>
240/** Load the zstd wasm module. Safe to call repeatedly. */
241export function initCodecs(): Promise<void> {
242 if (!ready) {
243 ready = initWithUrl(zstdWasmUrl).catch((err: unknown) => {
244 ready = null
245 throw err
246 })
247 }
248 return ready
249}
251export interface CodecResult {
252 codec: string
253 note: string
254 bytes: number
255 ratio: number
256 bitsPerSample: number
257}
260 * Compress one int16 block with each of the given codecs. Takes the samples
261 * rather than raw bytes so every codec — and the entropy bounds — key the
262 * LPC cache off the same array.
263 */
264export function compressAll(samples: Int16Array, codecs: Codec[]): CodecResult[] {
265 const bytes = asBytes(samples)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 266 return codecs.map(codec => {
1d751ddOffer LPC orders to 2048, caching the transform across codecsJeremy Magland 267 const size = codec.size(samples, bytes)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 268 return {
269 codec: codec.name,
270 note: codec.note,
272 ratio: bytes.byteLength / size,
273 bitsPerSample: (8 * size) / samples.length,
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 274 }
275 })
276}