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'
17/**
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 }
25export interface Codec {
26 name: string
27 /** Longer description, shown on hover. */
28 note: string
29 size: (samples: Int16Array, bytes: Uint8Array) => CodecSize
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.
64 *
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.
67 */
68function ansSize(
69 samples: Int16Array,
70 coded: Int16Array,
71 inverse: (coded: Int16Array) => Int16Array,
72 extraBytes = 0,
73): CodecSize {
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 }
80 return {
81 bytes: encodedSize(encoded) + extraBytes,
82 modelBits: order0Entropy(coded) * coded.length,
83 }
84}
86/** Predictor orders the UI offers; 32 is the FLAC default and ours. */
87export const LPC_ORDERS = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
88export const DEFAULT_LPC_ORDER = 32
90interface LpcTransform {
91 residual: Int16Array
92 restore: (residual: Int16Array) => Int16Array
93 extraBytes: number
94}
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
114 const model = fitLpc(samples, order)
115 if (!model) throw new Error('LPC fit failed')
116 const transform: LpcTransform = {
117 residual: lpcResidual(samples, model),
118 restore: residual => lpcRestore(residual, model),
119 extraBytes: modelSize(model),
120 }
121 byOrder.set(order, transform)
122 return transform
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}
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 ]
190}
192/** The general-purpose compressors, which know nothing about the data. */
193export const GENERAL_CODECS: Codec[] = [ZLIB, ZSTD]
195/**
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
198 * charged for describing that histogram — the model an ANS coder aims at.
199 */
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}
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
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
240}
242/**
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)
249 return codecs.map(codec => {
250 const out = codec.size(samples, bytes)
251 const size = typeof out === 'number' ? out : out.bytes
252 return {
253 codec: codec.name,
254 note: codec.note,
255 bytes: size,
256 ratio: bytes.byteLength / size,
257 bitsPerSample: (8 * size) / samples.length,
258 modelBitsPerSample:
259 typeof out === 'number' ? undefined : out.modelBits / samples.length,
260 }
261 })
262}