alpha2_audio/
waveform.rs

1//! Multi-resolution waveform summaries for timeline display.
2//!
3//! [`WaveformSummary`] computes per-bucket min, max and RMS at a base bucket size and at
4//! coarser levels, each four times the last, from planar samples streamed in any block size.
5//!
6//! Coarser buckets fold four finer ones exactly, with sums of squares in `f64` (exact for squared
7//! `f32`), so results are independent of block boundaries and bit-identical natively and in
8//! wasm. Extremes order -0 below +0 because `f32::min` and `max` pick either zero differently on
9//! aarch64 and `x86_64`. Non-finite samples count as silence, as in a mix.
10
11/// The extremes and RMS of one run of samples of one channel.
12#[derive(Copy, Clone, Debug, Default, PartialEq)]
13pub struct WaveformBucket {
14    /// Smallest sample.
15    pub min: f32,
16    /// Largest sample.
17    pub max: f32,
18    /// Root mean square of the samples.
19    pub rms: f32,
20}
21
22/// One zoom level of a [`Waveform`].
23#[derive(Clone, Debug, PartialEq)]
24pub struct WaveformLevel {
25    /// Samples per bucket at this level. The last bucket may cover fewer.
26    pub bucket_samples: usize,
27    /// Buckets per channel, in time order.
28    pub channels: Vec<Vec<WaveformBucket>>,
29}
30
31/// A finished waveform summary: its levels, finest first.
32#[derive(Clone, Debug, PartialEq)]
33pub struct Waveform {
34    /// Samples summarized per channel.
35    pub frames: u64,
36    /// Levels from the base bucket size up, each four times coarser.
37    pub levels: Vec<WaveformLevel>,
38}
39
40/// Why a waveform summary cannot be configured or fed.
41#[derive(Copy, Clone, Debug, Eq, PartialEq)]
42#[non_exhaustive]
43pub enum WaveformError {
44    /// No channels, a zero bucket, or no levels.
45    InvalidShape,
46    /// A block's channel count or plane lengths do not match.
47    MismatchedBlock,
48}
49
50impl std::fmt::Display for WaveformError {
51    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52        formatter.write_str(match self {
53            Self::InvalidShape => "a waveform needs channels, a positive bucket, and a level",
54            Self::MismatchedBlock => "the block's channels do not match the waveform's",
55        })
56    }
57}
58
59impl std::error::Error for WaveformError {}
60
61/// Buckets folded into one bucket of the next level.
62const FOLD: usize = 4;
63/// Most zoom levels; a 1-sample base reaches 4^15 samples, over six hours at 48 kHz.
64pub const MAX_WAVEFORM_LEVELS: usize = 16;
65
66/// A bucket still being filled: exact extremes and the sum of squares.
67#[derive(Copy, Clone, Debug)]
68struct Accumulator {
69    min: f32,
70    max: f32,
71    sum_squares: f64,
72    samples: u64,
73    parts: usize,
74}
75
76impl Accumulator {
77    const EMPTY: Self = Self {
78        min: f32::INFINITY,
79        max: f32::NEG_INFINITY,
80        sum_squares: 0.0,
81        samples: 0,
82        parts: 0,
83    };
84
85    fn is_empty(&self) -> bool {
86        self.samples == 0
87    }
88
89    /// Adds one sample; non-finite samples count as silence.
90    fn add_sample(&mut self, sample: f32) {
91        let sample = if sample.is_finite() { sample } else { 0.0 };
92        self.min = lower(self.min, sample);
93        self.max = higher(self.max, sample);
94        let square = f64::from(sample);
95        self.sum_squares += square * square;
96        self.samples += 1;
97    }
98
99    fn add_part(&mut self, part: &Self) {
100        self.min = lower(self.min, part.min);
101        self.max = higher(self.max, part.max);
102        self.sum_squares += part.sum_squares;
103        self.samples += part.samples;
104        self.parts += 1;
105    }
106
107    #[allow(clippy::cast_possible_truncation, clippy::cast_precision_loss)]
108    fn bucket(&self) -> WaveformBucket {
109        WaveformBucket {
110            min: self.min,
111            max: self.max,
112            rms: (self.sum_squares / self.samples as f64).sqrt() as f32,
113        }
114    }
115}
116
117/// The smaller of `current` and `sample`, -0 below +0.
118fn lower(current: f32, sample: f32) -> f32 {
119    if sample.total_cmp(&current).is_lt() {
120        sample
121    } else {
122        current
123    }
124}
125
126/// The larger of `current` and `sample`, +0 above -0.
127fn higher(current: f32, sample: f32) -> f32 {
128    if sample.total_cmp(&current).is_gt() {
129        sample
130    } else {
131        current
132    }
133}
134
135/// Builds a [`Waveform`] from planar samples streamed in blocks.
136#[derive(Clone, Debug)]
137pub struct WaveformSummary {
138    base_bucket: usize,
139    levels: Vec<WaveformLevel>,
140    /// The open bucket of each level, per channel: `open[level][channel]`.
141    open: Vec<Vec<Accumulator>>,
142    frames: u64,
143}
144
145impl WaveformSummary {
146    /// A summary of `channels` channels with `base_bucket` samples per finest bucket and
147    /// `levels` levels.
148    ///
149    /// # Errors
150    /// Returns [`WaveformError::InvalidShape`] for zero channels, a zero bucket, or a level count
151    /// outside `1..=MAX_WAVEFORM_LEVELS`.
152    pub fn new(channels: usize, base_bucket: usize, levels: usize) -> Result<Self, WaveformError> {
153        if channels == 0 || base_bucket == 0 || !(1..=MAX_WAVEFORM_LEVELS).contains(&levels) {
154            return Err(WaveformError::InvalidShape);
155        }
156        let mut bucket_samples = base_bucket;
157        let mut summary_levels = Vec::with_capacity(levels);
158        for _ in 0..levels {
159            summary_levels.push(WaveformLevel {
160                bucket_samples,
161                channels: vec![Vec::new(); channels],
162            });
163            bucket_samples = bucket_samples.saturating_mul(FOLD);
164        }
165        Ok(Self {
166            base_bucket,
167            levels: summary_levels,
168            open: vec![vec![Accumulator::EMPTY; channels]; levels],
169            frames: 0,
170        })
171    }
172
173    /// Adds one block of equal-length planes.
174    ///
175    /// # Errors
176    /// Returns [`WaveformError::MismatchedBlock`] for another channel count or ragged planes.
177    pub fn push(&mut self, planes: &[&[f32]]) -> Result<(), WaveformError> {
178        let channels = self.levels[0].channels.len();
179        let Some(frames) = planes.first().map(|plane| plane.len()) else {
180            return Err(WaveformError::MismatchedBlock);
181        };
182        if planes.len() != channels || planes.iter().any(|plane| plane.len() != frames) {
183            return Err(WaveformError::MismatchedBlock);
184        }
185        for index in 0..frames {
186            for (channel, plane) in planes.iter().enumerate() {
187                self.open[0][channel].add_sample(plane[index]);
188            }
189            if self.open[0][0].samples == self.base_bucket as u64 {
190                self.close(0);
191            }
192        }
193        self.frames += frames as u64;
194        Ok(())
195    }
196
197    /// Closes `level`'s open bucket on every channel and folds it upward, cascading when full.
198    fn close(&mut self, level: usize) {
199        let channels = self.open[level].len();
200        for channel in 0..channels {
201            let finished = self.open[level][channel];
202            self.levels[level].channels[channel].push(finished.bucket());
203            if let Some(next) = self.open.get_mut(level + 1) {
204                next[channel].add_part(&finished);
205            }
206            self.open[level][channel] = Accumulator::EMPTY;
207        }
208        if level + 1 < self.open.len() && self.open[level + 1][0].parts == FOLD {
209            self.close(level + 1);
210        }
211    }
212
213    /// Closes the partial buckets and returns the summary.
214    #[must_use]
215    pub fn finish(mut self) -> Waveform {
216        for level in 0..self.open.len() {
217            if !self.open[level][0].is_empty() {
218                self.close(level);
219            }
220        }
221        Waveform {
222            frames: self.frames,
223            levels: self.levels,
224        }
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use super::{WaveformBucket, WaveformError, WaveformSummary};
231
232    /// The extremes of each level-0 bucket of one channel, as bits.
233    fn extreme_bits(samples: &[f32], bucket: usize) -> Vec<(u32, u32)> {
234        let mut summary = WaveformSummary::new(1, bucket, 1).expect("shape");
235        summary.push(&[samples]).expect("block");
236        summary.finish().levels[0].channels[0]
237            .iter()
238            .map(|bucket| (bucket.min.to_bits(), bucket.max.to_bits()))
239            .collect()
240    }
241
242    #[test]
243    fn a_signed_zero_extreme_is_the_same_on_every_target() {
244        // -0 is always the minimum and +0 the maximum, whatever the arrival order.
245        let (positive, negative) = (0.0_f32.to_bits(), (-0.0_f32).to_bits());
246        let samples = [
247            0.0, -0.0, 0.0, -0.0, // +0 first
248            -0.0, 0.0, -0.0, 0.0, // -0 first
249            -0.25, 0.0, -0.0, -0.0, // a negative extreme, a zero maximum
250            0.25, -0.0, 0.0, 0.0, // a zero minimum, a positive extreme
251            -0.0, -0.0, -0.0, -0.0, // one zero alone
252        ];
253        assert_eq!(
254            extreme_bits(&samples, 4),
255            [
256                (negative, positive),
257                (negative, positive),
258                ((-0.25_f32).to_bits(), positive),
259                (negative, 0.25_f32.to_bits()),
260                (negative, negative),
261            ]
262        );
263        let mut summary = WaveformSummary::new(1, 2, 2).expect("shape");
264        summary.push(&[&samples[..8]]).expect("block");
265        let coarse = summary.finish().levels[1].channels[0][0];
266        assert_eq!(
267            (coarse.min.to_bits(), coarse.max.to_bits()),
268            (negative, positive)
269        );
270    }
271
272    fn sine(frames: usize, period: usize, amplitude: f32) -> Vec<f32> {
273        (0..frames)
274            .map(|index| {
275                #[allow(clippy::cast_precision_loss)]
276                let phase = index as f32 / period as f32 * core::f32::consts::TAU;
277                amplitude * libm::sinf(phase)
278            })
279            .collect()
280    }
281
282    #[test]
283    fn a_sine_has_its_peak_and_its_rms() {
284        // 64 samples per period, whole periods per bucket.
285        let signal = sine(4_096, 64, 0.5);
286        let mut summary = WaveformSummary::new(1, 256, 1).expect("shape");
287        summary.push(&[&signal]).expect("block");
288        let waveform = summary.finish();
289        assert_eq!(waveform.frames, 4_096);
290        let buckets = &waveform.levels[0].channels[0];
291        assert_eq!(buckets.len(), 16);
292        for bucket in buckets {
293            assert!((bucket.max - 0.5).abs() < 1e-6, "{bucket:?}");
294            assert!((bucket.min + 0.5).abs() < 1e-6, "{bucket:?}");
295            assert!(
296                (bucket.rms - 0.5 / 2.0_f32.sqrt()).abs() < 1e-5,
297                "{bucket:?}"
298            );
299        }
300    }
301
302    #[test]
303    fn coarser_levels_are_the_fold_of_finer_ones_and_match_direct_summaries() {
304        let left = sine(10_000, 37, 0.8);
305        let right = sine(10_000, 91, 0.3)
306            .into_iter()
307            .enumerate()
308            .map(|(index, sample)| if index % 7 == 0 { -sample } else { sample })
309            .collect::<Vec<_>>();
310        let mut folded = WaveformSummary::new(2, 16, 3).expect("shape");
311        folded.push(&[&left, &right]).expect("block");
312        let folded = folded.finish();
313        for (level, bucket_samples) in [(1, 64), (2, 256)] {
314            let mut direct = WaveformSummary::new(2, bucket_samples, 1).expect("shape");
315            direct.push(&[&left, &right]).expect("block");
316            let direct = direct.finish();
317            assert_eq!(folded.levels[level].bucket_samples, bucket_samples);
318            for channel in 0..2 {
319                let ours = &folded.levels[level].channels[channel];
320                let theirs = &direct.levels[0].channels[channel];
321                assert_eq!(ours.len(), theirs.len(), "level {level}");
322                for (a, b) in ours.iter().zip(theirs) {
323                    assert_eq!(a.min.to_bits(), b.min.to_bits());
324                    assert_eq!(a.max.to_bits(), b.max.to_bits());
325                    // A different summation order moves the f32 RMS by at most one ulp.
326                    assert!((a.rms - b.rms).abs() <= f32::EPSILON * b.rms, "{a:?} {b:?}");
327                }
328            }
329        }
330        // 10 000 samples in buckets of 16: 625 full buckets; 157 and 40 above.
331        assert_eq!(folded.levels[0].channels[0].len(), 625);
332        assert_eq!(folded.levels[1].channels[0].len(), 157);
333        assert_eq!(folded.levels[2].channels[0].len(), 40);
334    }
335
336    #[test]
337    fn block_boundaries_do_not_change_the_result() {
338        let signal = sine(5_000, 23, 0.9);
339        let whole = {
340            let mut summary = WaveformSummary::new(1, 30, 4).expect("shape");
341            summary.push(&[&signal]).expect("block");
342            summary.finish()
343        };
344        for block in [1, 7, 29, 128, 4_999] {
345            let mut summary = WaveformSummary::new(1, 30, 4).expect("shape");
346            for chunk in signal.chunks(block) {
347                summary.push(&[chunk]).expect("block");
348            }
349            assert_eq!(summary.finish(), whole, "block {block}");
350        }
351    }
352
353    #[test]
354    fn a_partial_last_bucket_covers_only_its_samples() {
355        let mut summary = WaveformSummary::new(1, 4, 2).expect("shape");
356        summary
357            .push(&[&[0.5, -0.5, 0.5, -0.5, 1.0, 1.0]])
358            .expect("block");
359        let waveform = summary.finish();
360        assert_eq!(
361            waveform.levels[0].channels[0],
362            vec![
363                WaveformBucket {
364                    min: -0.5,
365                    max: 0.5,
366                    rms: 0.5
367                },
368                WaveformBucket {
369                    min: 1.0,
370                    max: 1.0,
371                    rms: 1.0
372                },
373            ]
374        );
375        let top = waveform.levels[1].channels[0][0];
376        assert_eq!((top.min, top.max), (-0.5, 1.0));
377        // sqrt((4 * 0.25 + 2 * 1) / 6) = sqrt(0.5)
378        assert!((top.rms - 0.5_f32.sqrt()).abs() < 1e-7);
379    }
380
381    #[test]
382    fn a_non_finite_sample_counts_as_silence_at_every_level() {
383        // Non-finite samples count as silence rather than poisoning every bucket above.
384        let samples = [
385            0.1,
386            f32::NAN,
387            0.2,
388            0.3,
389            f32::NAN,
390            f32::NAN,
391            f32::NAN,
392            f32::NAN,
393            0.1,
394            f32::INFINITY,
395            f32::NEG_INFINITY,
396            0.1,
397        ];
398        let mut summary = WaveformSummary::new(1, 4, 2).expect("shape");
399        summary.push(&[&samples]).expect("block");
400        let waveform = summary.finish();
401        let silenced = samples.map(|sample| if sample.is_finite() { sample } else { 0.0 });
402        let mut reference = WaveformSummary::new(1, 4, 2).expect("shape");
403        reference.push(&[&silenced]).expect("block");
404        assert_eq!(waveform, reference.finish());
405        for level in &waveform.levels {
406            for bucket in &level.channels[0] {
407                assert!(
408                    bucket.min.is_finite() && bucket.max.is_finite() && bucket.rms.is_finite(),
409                    "{bucket:?}"
410                );
411            }
412        }
413        // A bucket of nothing but NaN is a silent bucket, not the empty sentinel.
414        assert_eq!(
415            waveform.levels[0].channels[0][1],
416            WaveformBucket {
417                min: 0.0,
418                max: 0.0,
419                rms: 0.0
420            }
421        );
422    }
423
424    #[test]
425    fn shapes_and_blocks_are_checked() {
426        assert_eq!(
427            WaveformSummary::new(0, 1, 1).map(|_| ()),
428            Err(WaveformError::InvalidShape)
429        );
430        assert_eq!(
431            WaveformSummary::new(1, 0, 1).map(|_| ()),
432            Err(WaveformError::InvalidShape)
433        );
434        assert_eq!(
435            WaveformSummary::new(1, 1, 17).map(|_| ()),
436            Err(WaveformError::InvalidShape)
437        );
438        let mut summary = WaveformSummary::new(2, 8, 1).expect("shape");
439        assert_eq!(
440            summary.push(&[&[0.0; 3], &[0.0; 2]]),
441            Err(WaveformError::MismatchedBlock)
442        );
443        assert_eq!(
444            summary.push(&[&[0.0; 3]]),
445            Err(WaveformError::MismatchedBlock)
446        );
447    }
448}
alpha2_audio/waveform.rs

alpha2_audio/
waveform.rs
