Skip to main content

silence_split/
plan.rs

1//! Cut planning: where to split the audio.
2
3use alloc::vec::Vec;
4use core::num::NonZeroUsize;
5use core::time::Duration;
6
7use crate::analyze::Analysis;
8use crate::candidates::{Candidate, Context, Grid};
9use crate::dp;
10use crate::errors::ConfigError;
11use crate::segment::SegmentConfig;
12
13/// Where to cut inside a silence that is longer than its padding.
14#[derive(Clone, Copy, Debug, PartialEq)]
15#[non_exhaustive]
16pub enum Placement {
17    /// At the lowest smoothed level.
18    Quietest,
19    /// In the middle.
20    Center,
21    /// At this fraction of the way through, from `0.0` (start) to `1.0` (end).
22    Ratio(f32),
23}
24
25/// What happens to the silence at a cut.
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27#[non_exhaustive]
28pub enum Gap {
29    /// Nothing is dropped; the pieces joined in order are the original audio.
30    Keep,
31    /// The middle of a silence chosen for a cut is dropped, keeping the padding on both sides.
32    /// Leading and trailing silence beyond the padding is dropped too.
33    Drop,
34}
35
36/// Cost weights of the planner.
37///
38/// A cut at `x` costs `cut + level · norm(x) + pause · (1 − min(1, q(x) / pause_ref))`, where
39/// `norm` is the level smoothed over 150 ms and scaled between the noise floor and the reference
40/// (at least 20 dB apart), and `q` is the
41/// length of the quiet stretch around `x`. A piece of length `ℓ` costs
42/// `target · ((ℓ − target_len) / target_len)² + short · (min − ℓ) / min` when `ℓ < min`.
43/// [`adjust`] adds `|x − p| / window` for the distance from the requested point.
44///
45/// The defaults are starting values that have not been tuned on a corpus.
46#[derive(Clone, Debug, PartialEq)]
47#[non_exhaustive]
48pub struct Weights {
49    /// Fixed cost of every cut. Keeps free cuts in digital silence from multiplying.
50    pub cut: f64,
51    /// Weight of the level at the cut.
52    pub level: f64,
53    /// Weight of cutting outside a long pause.
54    pub pause: f64,
55    /// Pause length that earns the full pause credit.
56    pub pause_ref: Duration,
57    /// Weight of the squared relative distance from the target length. Zero cuts only to stay
58    /// within the maximum.
59    pub target: f64,
60    /// Weight of pieces shorter than the minimum.
61    pub short: f64,
62}
63
64impl Default for Weights {
65    fn default() -> Self {
66        Self {
67            cut: 0.1,
68            level: 1.0,
69            pause: 1.0,
70            pause_ref: Duration::from_millis(500),
71            target: 1.0,
72            short: 4.0,
73        }
74    }
75}
76
77/// Piece length limits and cut preferences for [`plan`].
78#[derive(Clone, Debug, PartialEq)]
79#[non_exhaustive]
80pub struct PlanConfig {
81    pub(crate) min: Duration,
82    pub(crate) target: Duration,
83    pub(crate) max: Duration,
84    pub(crate) count: Option<NonZeroUsize>,
85    pub(crate) gap: Gap,
86    pub(crate) placement: Placement,
87    pub(crate) weights: Weights,
88}
89
90impl PlanConfig {
91    /// Pieces never longer than `max`, preferably `target` long and not shorter than `min`.
92    ///
93    /// `max` is a hard limit that includes padding. `min` is soft: a shorter piece is penalized
94    /// ([`Weights::short`]) and flagged [`Piece::too_short`]. Silence is kept ([`Gap::Keep`]) and cuts inside
95    /// silence go to the quietest point ([`Placement::Quietest`]).
96    ///
97    /// # Errors
98    ///
99    /// [`ConfigError::InvalidLengths`] unless `min <= target <= max` and `target` is non-zero.
100    pub fn new(min: Duration, target: Duration, max: Duration) -> Result<Self, ConfigError> {
101        if target.is_zero() || min > target || target > max {
102            return Err(ConfigError::InvalidLengths);
103        }
104        Ok(Self {
105            min,
106            target,
107            max,
108            count: None,
109            gap: Gap::Keep,
110            placement: Placement::Quietest,
111            weights: Weights::default(),
112        })
113    }
114
115    /// Asks for exactly `count` pieces, each targeting an equal share of the audio. `min` and
116    /// `max` still apply; fewer pieces are returned only when there are not enough cut positions.
117    #[must_use]
118    pub fn count(mut self, count: NonZeroUsize) -> Self {
119        self.count = Some(count);
120        self
121    }
122
123    /// Sets what happens to the silence at a cut.
124    #[must_use]
125    pub fn gap(mut self, gap: Gap) -> Self {
126        self.gap = gap;
127        self
128    }
129
130    /// Sets where a cut goes inside a long silence when silence is kept.
131    ///
132    /// # Errors
133    ///
134    /// [`ConfigError::InvalidRatio`] if a [`Placement::Ratio`] is outside `0.0..=1.0`.
135    pub fn placement(mut self, placement: Placement) -> Result<Self, ConfigError> {
136        if let Placement::Ratio(r) = placement {
137            if !(0.0..=1.0).contains(&r) {
138                return Err(ConfigError::InvalidRatio);
139            }
140        }
141        self.placement = placement;
142        Ok(self)
143    }
144
145    /// Sets the cost weights.
146    ///
147    /// # Errors
148    ///
149    /// [`ConfigError::InvalidWeights`] if a weight is negative or not finite, the per-cut cost is
150    /// zero, or `pause_ref` is zero.
151    pub fn weights(mut self, weights: Weights) -> Result<Self, ConfigError> {
152        let w = &weights;
153        let valid = [w.level, w.pause, w.target, w.short]
154            .iter()
155            .all(|v| v.is_finite() && *v >= 0.0)
156            && w.cut.is_finite()
157            && w.cut > 0.0
158            && !w.pause_ref.is_zero();
159        if !valid {
160            return Err(ConfigError::InvalidWeights);
161        }
162        self.weights = weights;
163        Ok(self)
164    }
165}
166
167/// A boundary between two consecutive pieces.
168///
169/// The earlier piece ends at `end` and the later one starts at `start`. With [`Gap::Keep`] they
170/// are equal; with [`Gap::Drop`] the samples `[end, start)` are dropped.
171#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
172#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
173#[non_exhaustive]
174pub struct Cut {
175    /// End of the earlier piece.
176    pub end: u64,
177    /// Start of the later piece.
178    pub start: u64,
179    /// What the cut is in.
180    pub reason: CutReason,
181}
182
183/// What a cut falls in.
184#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
185#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
186#[non_exhaustive]
187pub enum CutReason {
188    /// A silence span.
189    Silence,
190    /// Not silence, but within the quietest quarter of the level range.
191    Quiet,
192    /// Anywhere else: the length limits left no quiet choice.
193    Forced,
194}
195
196/// A piece of the original audio, `[start, end)` in samples.
197#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
198#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
199#[non_exhaustive]
200pub struct Piece {
201    /// First sample.
202    pub start: u64,
203    /// One past the last sample.
204    pub end: u64,
205    /// Shorter than the minimum length.
206    pub too_short: bool,
207    /// Longer than the maximum length. Only when the limits cannot be met on the analysis frame
208    /// grid, such as a maximum shorter than a frame or a count too small for the maximum.
209    pub too_long: bool,
210}
211
212/// Pieces in order and the cuts between them: `cuts[i]` separates `pieces[i]` and
213/// `pieces[i + 1]`.
214///
215/// Samples before the first piece and after the last are dropped leading and trailing silence
216/// ([`Gap::Drop`] only).
217#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
218#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
219#[non_exhaustive]
220pub struct Plan {
221    /// The pieces.
222    pub pieces: Vec<Piece>,
223    /// The cuts between pieces.
224    pub cuts: Vec<Cut>,
225}
226
227/// Chooses cuts over the whole audio that keep every piece within `max`, minimizing the total
228/// cost of all cuts and piece lengths (see [`Weights`]).
229///
230/// Candidates are the silence spans and the quietest point of every block of
231/// `min(1 s, max((max − min) / 2, max / 8))` outside them. Additional frame boundaries are inserted
232/// when needed to satisfy the maximum or the piece count, including within padding. Padding that
233/// would leave less than two blocks of the maximum is shortened to fit. Silence wins over quiet
234/// sound through the cut cost. Cuts fall on analysis frame boundaries. The result is deterministic.
235///
236/// With [`PlanConfig::count`], feasibility includes the removable silence ranges. Only when no
237/// frame-grid plan can meet both limits is the maximum relaxed to the smallest attainable longest
238/// piece; pieces exceeding the requested maximum are flagged [`Piece::too_long`].
239#[must_use]
240pub fn plan(analysis: &Analysis, segment: &SegmentConfig, config: &PlanConfig) -> Plan {
241    let max = analysis.samples_floor(config.max);
242    // Blocks follow max − min, but not below max / 8: a tight soft minimum must not shrink the
243    // grid to every frame.
244    let block_time = (config.max.saturating_sub(config.min) / 2)
245        .max(config.max / 8)
246        .min(Duration::from_secs(1));
247    let block = analysis.frames_floor(block_time).max(1);
248    let block_samples = analysis.position(block.min(analysis.frames()));
249    // A piece must hold the padding plus a block to reach the next grid candidate.
250    let padding_cap = analysis.frames_floor(config.max).saturating_sub(2 * block);
251    let ctx = Context::new(analysis, segment, &config.weights, padding_cap);
252    let Some((first, last)) = ctx.ends(config.gap) else {
253        return Plan::default();
254    };
255    let span = analysis.position(last) - analysis.position(first);
256    // The nearest grid candidates outside a silence may be a block or two from it, so a silence
257    // longer than the maximum less two blocks gets grid candidates of its own.
258    let grid = Grid {
259        block,
260        edge_limit: Some(max.saturating_sub(2 * block_samples)),
261    };
262    let mut nodes = ctx.candidates(config.gap, config.placement, &grid, first, last);
263    let target = match config.count {
264        Some(n) => span as f64 / n.get() as f64,
265        None => {
266            ctx.complete_max(&mut nodes, max);
267            analysis.samples_in(config.target)
268        }
269    };
270    let solve = |nodes: &[Candidate], reach: u64| -> Plan {
271        let lengths = dp::Lengths {
272            min: analysis.samples_in(config.min),
273            target,
274            max: reach,
275            weights: &config.weights,
276        };
277        let left: Vec<u64> = nodes.iter().map(|c| analysis.position(c.left)).collect();
278        let right: Vec<u64> = nodes.iter().map(|c| analysis.position(c.right)).collect();
279        let cost: Vec<f64> = nodes.iter().map(|c| c.cost).collect();
280        let path = match config.count {
281            Some(n) => dp::solve_count(&left, &right, &cost, &lengths, n.get()),
282            None => dp::solve(&left, &right, &cost, &lengths),
283        };
284        ctx.to_plan(nodes, &path, lengths.min, max)
285    };
286    let result = solve(&nodes, max);
287    if let Some(n) = config.count {
288        if result.pieces.len() < n.get() || result.pieces.iter().any(|p| p.too_long) {
289            let reach = ctx.complete_count(&mut nodes, max, n.get());
290            return solve(&nodes, reach);
291        }
292    }
293    result
294}
295
296/// Moves each requested cut point to the best candidate within `window` of it, keeping the order
297/// of the points and all audio ([`Gap::Keep`]).
298///
299/// Each point is adjusted on its own; the pieces' lengths are not constrained. Candidates are the
300/// silence spans, points inside silence clear of its padding, and the quietest point of every
301/// block of `min(1 s, window)`. Each point takes the candidate with the lowest cut cost (default
302/// [`Weights`], [`Placement::Quietest`]) plus `|x − p| / window`, among those before the midpoints
303/// to its neighbouring points. A point with no candidate in its window stays at the nearest frame
304/// boundary as a [`CutReason::Forced`] cut. Points are sorted first; points at or beyond either
305/// end of the audio are ignored.
306#[must_use]
307pub fn adjust(
308    analysis: &Analysis,
309    segment: &SegmentConfig,
310    points: &[u64],
311    window: Duration,
312) -> Plan {
313    let weights = Weights::default();
314    let ctx = Context::new(analysis, segment, &weights, usize::MAX);
315    let n = analysis.frames();
316    if n == 0 {
317        return Plan::default();
318    }
319    let grid = Grid {
320        block: analysis
321            .frames_floor(window.min(Duration::from_secs(1)))
322            .max(1),
323        edge_limit: Some(0),
324    };
325    let candidates = ctx.candidates(Gap::Keep, Placement::Quietest, &grid, 0, n);
326    let inner = &candidates[1..candidates.len() - 1];
327    let positions: Vec<u64> = inner.iter().map(|c| analysis.position(c.left)).collect();
328    let len = analysis.sample_count();
329    let mut points: Vec<u64> = points
330        .iter()
331        .copied()
332        .filter(|p| *p > 0 && *p < len)
333        .collect();
334    points.sort_unstable();
335    points.dedup();
336
337    let reach = analysis.samples_in(window);
338    let mut chosen: Vec<Candidate> = Vec::with_capacity(points.len() + 2);
339    chosen.push(Candidate::node(0));
340    for (k, &p) in points.iter().enumerate() {
341        let lo = k.checked_sub(1).map_or(0, |i| points[i].midpoint(p));
342        let hi = points.get(k + 1).map_or(len, |next| p.midpoint(*next));
343        let from = positions.partition_point(|x| (*x as f64) < p as f64 - reach || *x < lo);
344        let to = positions.partition_point(|x| *x < hi && *x as f64 <= p as f64 + reach);
345        let best = (from..to.max(from))
346            .map(|i| {
347                let distance = positions[i].abs_diff(p) as f64;
348                let pull = if reach > 0.0 { distance / reach } else { 0.0 };
349                (inner[i].cost + pull, &inner[i])
350            })
351            .fold(None, |best: Option<(f64, &Candidate)>, (v, c)| match best {
352                Some((b, _)) if b <= v => best,
353                _ => Some((v, c)),
354            });
355        let pick = match best {
356            Some((_, c)) => c.clone(),
357            None => ctx.forced_at(p),
358        };
359        let after_previous = chosen.last().is_some_and(|c| c.left < pick.left);
360        if pick.left < n && after_previous {
361            chosen.push(pick);
362        }
363    }
364    chosen.push(Candidate::node(n));
365    let path: Vec<usize> = (0..chosen.len()).collect();
366    ctx.to_plan(&chosen, &path, 0.0, u64::MAX)
367}