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. */
74export const LPC_ORDERS = [1, 2, 4, 8, 16, 32, 64, 128]
75export const DEFAULT_LPC_ORDER = 32
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 76
77/** Fit the predictor and take the residual, with the coefficients' cost. */
79 samples: Int16Array,
80 order: number,
81): {
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 82 residual: Int16Array
83 restore: (residual: Int16Array) => Int16Array
84 extraBytes: number
85} {
e411dffMake LPC order and compression block size controlsJeremy Magland 86 const model = fitLpc(samples, order)
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 87 if (!model) throw new Error('LPC fit failed')
88 return {
89 residual: lpcResidual(samples, model),
90 restore: residual => lpcRestore(residual, model),
91 extraBytes: modelSize(model),
92 }
93}
95export const ZLIB: Codec = {
96 name: 'zlib -9',
97 note: 'DEFLATE at maximum level — the HDF5 gzip filter',
98 size: (_s, bytes) => zlibSync(bytes, { level: 9 }).length,
99}
101export const ZSTD: Codec = {
102 name: 'zstd -19',
103 note: 'Zstandard at level 19 — the Blosc/Zarr default family',
104 size: (_s, bytes) => zstdCompress(bytes, 19).length,
105}
107export const ANS: Codec = {
108 name: 'ANS',
109 note: 'rANS entropy coder over the sample histogram, ported from simple_ans; the size includes the symbol table',
110 size: samples => ansSize(samples, samples, x => x),
111}
113export const DELTA_ZLIB: Codec = {
114 name: 'delta + zlib -9',
115 note: 'First differences, then DEFLATE',
116 size: samples => zlibSync(asBytes(delta(samples)), { level: 9 }).length,
117}
119export const DELTA_ZSTD: Codec = {
120 name: 'delta + zstd -19',
121 note: 'First differences, then Zstandard 19',
122 size: samples => zstdCompress(asBytes(delta(samples)), 19).length,
123}
125export const DELTA_ANS: Codec = {
126 name: 'delta + ANS',
127 note: 'First differences, then the rANS entropy coder',
128 size: samples => ansSize(samples, delta(samples), undelta),
129}
e411dffMake LPC order and compression block size controlsJeremy Magland 131/** The three LPC codecs at a given predictor order. */
132export function lpcCodecs(order: number): Codec[] {
133 const note = `Order-${order} linear prediction with integer coefficients; the size includes the coefficients`
134 return [
135 {
136 name: `LPC(${order}) + zlib -9`,
137 note: `${note}, then DEFLATE`,
138 size: samples => {
139 const { residual, extraBytes } = lpcTransform(samples, order)
140 return zlibSync(asBytes(residual), { level: 9 }).length + extraBytes
141 },
142 },
143 {
144 name: `LPC(${order}) + zstd -19`,
145 note: `${note}, then Zstandard 19`,
146 size: samples => {
147 const { residual, extraBytes } = lpcTransform(samples, order)
148 return zstdCompress(asBytes(residual), 19).length + extraBytes
149 },
150 },
151 {
152 name: `LPC(${order}) + ANS`,
153 note: `${note}, then the rANS entropy coder`,
154 size: samples => {
155 const { residual, restore, extraBytes } = lpcTransform(samples, order)
156 return ansSize(samples, residual, restore, extraBytes)
157 },
158 },
159 ]
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 160}
162/** The general-purpose compressors, which know nothing about the data. */
163export const GENERAL_CODECS: Codec[] = [ZLIB, ZSTD]
166 * Order-0 (memoryless) entropy of an int16 stream, in bits per sample: what a
167 * perfect entropy coder for the sample histogram would spend, with nothing
168 * charged for describing that histogram. The ANS bars sit above this by the
169 * symbol table plus the coder's own arithmetic loss.
170 */
171export function order0Entropy(samples: Int16Array): number {
172 const counts = new Int32Array(65536)
173 for (let i = 0; i < samples.length; i++) counts[samples[i] + 32768]++
174 let bits = 0
175 for (const c of counts) {
176 if (c > 0) {
177 const p = c / samples.length
178 bits -= p * Math.log2(p)
179 }
180 }
181 return bits
182}
184export interface BoundResult {
185 /** The prefilter group this bounds, matching the codec groups. */
186 group: string
187 note: string
188 bitsPerSample: number
189 ratio: number
190 bytes: number
191}
193/** The order-0 bound for each prefilter: raw samples, delta, LPC residual. */
e411dffMake LPC order and compression block size controlsJeremy Magland 194export function entropyBounds(samples: Int16Array, lpcOrder: number): BoundResult[] {
355ddbbAdd per-group entropy limit bars to the compression chartJeremy Magland 195 const streams: { group: string; what: string; data: Int16Array }[] = [
196 { group: 'no prefilter', what: 'the samples themselves', data: samples },
197 { group: 'delta', what: 'the first differences', data: delta(samples) },
199 group: 'LPC',
200 what: `the order-${lpcOrder} prediction residual`,
201 data: lpcTransform(samples, lpcOrder).residual,
202 },
204 return streams.map(({ group, what, data }) => {
205 const bitsPerSample = order0Entropy(data)
206 return {
207 group,
208 note: `order-0 entropy of ${what} — the limit for a per-sample entropy coder, with no symbol table or coefficients charged`,
209 bitsPerSample,
210 ratio: 16 / bitsPerSample,
211 bytes: Math.ceil((bitsPerSample * samples.length) / 8),
212 }
213 })
214}
36e8ceaInteractive explorer for compressibility of quantized filtered Gaussian time seriesJeremy Magland 216let ready: Promise<void> | null = null
218// zstd-wasm publishes the *node* build's types while the bundler resolves the
219// browser build (its `exports` map has a "browser" condition). Only the browser
220// build's `init` takes a wasm URL, so the signature has to be restated here.
221const initWithUrl = zstdInit as unknown as (path?: string) => Promise<void>
223/** Load the zstd wasm module. Safe to call repeatedly. */
224export function initCodecs(): Promise<void> {
225 if (!ready) {
226 ready = initWithUrl(zstdWasmUrl).catch((err: unknown) => {
227 ready = null
228 throw err
229 })
230 }
231 return ready
232}
234export interface CodecResult {
235 codec: string
236 note: string
237 bytes: number
238 ratio: number
239 bitsPerSample: number
240}
242/** Compress one int16 buffer with each of the given codecs. */
243export function compressAll(buffer: Uint8Array, codecs: Codec[]): CodecResult[] {
244 // The session's buffer may sit at an odd offset; align before viewing as int16.
245 const aligned = buffer.byteOffset % 2 === 0 ? buffer : new Uint8Array(buffer)
246 const samples = new Int16Array(aligned.buffer, aligned.byteOffset, aligned.byteLength / 2)
247 return codecs.map(codec => {
248 const bytes = codec.size(samples, aligned)
249 return {
250 codec: codec.name,
251 note: codec.note,
252 bytes,
253 ratio: aligned.byteLength / bytes,
254 bitsPerSample: (8 * bytes) / samples.length,
255 }
256 })
257}