sva_samples/collapse/
plan.rs

1// Concern: which row of the collapse table a form takes, and what that row costs | Non-concern: running the row (collapse.rs) | IO: (&SpectralSum, rate, Horizon) -> Plan, flops
2
3use sva_formula::closed_form::{Part, map_children};
4use sva_formula::spectral_sum::atom::SpectralAtom;
5use sva_formula::{Body, ClosedForm, Lane, Line, SpectralSum, Var, normalize_closed_form};
6
7use super::truncate::Audible;
8use super::{Horizon, atoms, lines, point, truncate};
9use crate::error::CollapseError;
10use crate::label::Rule;
11use crate::profile::Profile;
12
13/// Both routes place a line exactly, so cost decides; the direct one hands a lone line back
14/// unchanged.
15pub fn direct_is_cheaper(lines: usize, n: usize, len: usize) -> bool {
16    (lines as f64) * (len as f64) <= (n as f64) * (n as f64).log2()
17}
18
19pub struct LinePlan {
20    pub placed: Vec<Vec<Line>>,
21    pub summed: Vec<Vec<Line>>,
22    pub dropped: Vec<Vec<Line>>,
23    pub bins: usize,
24    pub tail_db: Option<f64>,
25}
26
27/// FORMAT 9.2's window route.
28pub struct Group {
29    pub factor: SpectralAtom,
30    pub placed: Vec<Line>,
31    pub summed: Vec<Line>,
32}
33
34pub enum LanePlan {
35    Grouped { groups: Vec<Group>, bins: usize },
36    Sweep { atoms: usize, samples: usize },
37}
38
39pub struct Sampled {
40    pub sum: Box<SpectralSum>,
41    pub rule: Rule,
42    pub lanes: Vec<LanePlan>,
43}
44
45/// The row of FORMAT 9.1 that runs, decided once for the collapse and the count alike.
46pub enum Plan {
47    Spectrum(Box<SpectralSum>),
48    Lines(Box<LinePlan>),
49    Sampled(Box<Sampled>),
50    /// Row 4 over the written closed form: every node the truncation leaves, at every instant.
51    Point {
52        written: Box<ClosedForm>,
53        nodes: usize,
54        width: usize,
55    },
56    /// A sum whose addends name different rows, each taking its own.
57    Added(Vec<Plan>),
58}
59
60/// The rows in FORMAT 9.1's order; the first guard that holds decides.
61pub fn of(
62    sum: &SpectralSum,
63    rate: u32,
64    horizon: Horizon,
65    profile: &Profile,
66    len: usize,
67) -> Result<Plan, CollapseError> {
68    let ceiling = profile.ceiling(rate);
69    if sum.var == Var::F {
70        return Ok(Plan::Spectrum(Box::new(sum.clone())));
71    }
72    if let Some(found) = line_plan(sum, rate, horizon, profile, len, ceiling)? {
73        return Ok(Plan::Lines(Box::new(found)));
74    }
75    let truncated = truncate::spectral_sum(sum, Audible::of(profile, rate))?;
76    let rule = match () {
77        () if atoms::band_limited(&truncated, ceiling, profile) => Rule::BandLimited,
78        () if atoms::windowed(&truncated) => Rule::CroppedPair,
79        () => Rule::PointSampled,
80    };
81    let lanes = truncated
82        .lanes
83        .iter()
84        .map(|lane| lane_plan(lane, rate, horizon, len))
85        .collect();
86    Ok(Plan::Sampled(Box::new(Sampled {
87        sum: Box::new(truncated),
88        rule,
89        lanes,
90    })))
91}
92
93/// The row a closed form with no spectral sum takes: one per addend where they differ, else 4.
94pub fn of_written(
95    form: &ClosedForm,
96    rate: u32,
97    horizon: Horizon,
98    profile: &Profile,
99    len: usize,
100) -> Result<Plan, CollapseError> {
101    let Some(addends) = addends(form) else {
102        return point_plan(form, rate, profile);
103    };
104    let mut parts = Vec::with_capacity(addends.len());
105    for addend in &addends {
106        match of_term(addend, rate, horizon, profile, len)? {
107            Plan::Added(inner) => parts.extend(inner),
108            part => parts.push(part),
109        }
110    }
111    // Addends that all name row 4 are one row 4 over the whole sum, measured once.
112    match parts.iter().all(|part| matches!(part, Plan::Point { .. })) {
113        true => point_plan(form, rate, profile),
114        false => Ok(Plan::Added(parts)),
115    }
116}
117
118/// A row the addend alone cannot take refuses nothing; the written row still stands for it.
119/// A nesting past the bound is the one exception, refused wherever it is written.
120fn of_term(
121    form: &ClosedForm,
122    rate: u32,
123    horizon: Horizon,
124    profile: &Profile,
125    len: usize,
126) -> Result<Plan, CollapseError> {
127    let Ok(sum) = normalize_closed_form(form) else {
128        return of_written(form, rate, horizon, profile, len);
129    };
130    match of(&sum, rate, horizon, profile, len) {
131        Err(nested @ CollapseError::NestedSeries { .. }) => Err(nested),
132        Err(_) => of_written(form, rate, horizon, profile, len),
133        held => held,
134    }
135}
136
137pub(super) fn addends(form: &ClosedForm) -> Option<Vec<ClosedForm>> {
138    if let Body::Add(parts) = &form.body {
139        return Some(
140            parts
141                .iter()
142                .map(|part| ClosedForm {
143                    var: form.var,
144                    body: (*part.body).clone(),
145                    origin: part.origin,
146                })
147                .collect(),
148        );
149    }
150    let under = linear_over(&form.body)?;
151    let held = addends(&ClosedForm {
152        body: under,
153        ..form.clone()
154    })?;
155    Some(
156        held.into_iter()
157            .map(|addend| ClosedForm {
158                body: map_children(&form.body, |_| {
159                    Part::new(addend.origin, addend.body.clone())
160                }),
161                ..addend
162            })
163            .collect(),
164    )
165}
166
167/// Each of these is linear, so over a sum it is the sum of itself over every addend.
168fn linear_over(f: &Body) -> Option<Body> {
169    match f {
170        Body::Crop { of, .. }
171        | Body::Shift { of, .. }
172        | Body::Deriv { of, .. }
173        | Body::Channel(of, _) => Some((*of.body).clone()),
174        _ => None,
175    }
176}
177
178fn point_plan(form: &ClosedForm, rate: u32, profile: &Profile) -> Result<Plan, CollapseError> {
179    let written = ClosedForm {
180        body: truncate::written(&form.body, Audible::of(profile, rate))?,
181        ..form.clone()
182    };
183    let width = point::width_of(&written.body, &point::NoRefs).max(1);
184    Ok(Plan::Point {
185        nodes: point_nodes(&written.body),
186        written: Box::new(written),
187        width,
188    })
189}
190
191/// What one instant's evaluation walks over every component: a join walks that component's branch.
192pub fn point_nodes(f: &Body) -> usize {
193    let width = point::width_of(f, &point::NoRefs).max(1);
194    (0..width).map(|c| nodes_at(f, c)).sum()
195}
196
197fn nodes_at(f: &Body, component: usize) -> usize {
198    let branch = |part: &Part, c: usize| nodes_at(&part.body, c);
199    match f {
200        Body::Join(parts) => {
201            let widths: Vec<usize> = parts
202                .iter()
203                .map(|p| point::width_of(&p.body, &point::NoRefs))
204                .collect();
205            match point::lane_of(&widths, component) {
206                Some((at, inner)) => 1 + branch(&parts[at], inner),
207                None => 1,
208            }
209        }
210        Body::Channel(of, k) => 1 + branch(of, usize::from(*k)),
211        other => {
212            1 + sva_formula::closed_form::children(other)
213                .iter()
214                .map(|part| branch(part, component))
215                .sum::<usize>()
216        }
217    }
218}
219
220/// Rows one and two: every atom a line, none of them windowed.
221fn line_plan(
222    sum: &SpectralSum,
223    rate: u32,
224    horizon: Horizon,
225    profile: &Profile,
226    len: usize,
227    ceiling: f64,
228) -> Result<Option<LinePlan>, CollapseError> {
229    let Some(found) = kept_lines(sum, profile, ceiling)? else {
230        return Ok(None);
231    };
232    let bins = lines::grid(&found.kept, &found.grids, rate, horizon.span(), len);
233    let split: Vec<(Vec<Line>, Vec<Line>)> = found
234        .kept
235        .iter()
236        .map(|k| match direct_is_cheaper(k.len(), bins, len) {
237            true => (Vec::new(), k.clone()),
238            false => lines::split(k, bins, rate),
239        })
240        .collect();
241    Ok(Some(LinePlan {
242        placed: split.iter().map(|(on, _)| on.clone()).collect(),
243        summed: split.into_iter().map(|(_, off)| off).collect(),
244        dropped: found.dropped,
245        bins,
246        tail_db: found.tail,
247    }))
248}
249
250/// Each lane's lines under the ceiling and over it, before any horizon places them.
251pub(super) struct Kept {
252    pub(super) kept: Vec<Vec<Line>>,
253    dropped: Vec<Vec<Line>>,
254    grids: Vec<f64>,
255    tail: Option<f64>,
256}
257
258pub(super) fn kept_lines(
259    sum: &SpectralSum,
260    profile: &Profile,
261    ceiling: f64,
262) -> Result<Option<Kept>, CollapseError> {
263    let mut per_lane = Vec::with_capacity(sum.lanes.len());
264    let mut grids: Vec<f64> = Vec::new();
265    let mut tail: Option<f64> = None;
266    for lane in &sum.lanes {
267        match lines::of_lane(lane, ceiling, profile.floor(ceiling), profile.half_lsb()) {
268            Some(found) => {
269                if let Some(left) = found.tail_db {
270                    tail = Some(tail.map_or(left, |held: f64| held.max(left)));
271                }
272                grids.extend(found.grids);
273                per_lane.push(found.lines);
274            }
275            None => return Ok(None),
276        }
277    }
278
279    let (mut kept, mut dropped): (Vec<Vec<Line>>, Vec<Vec<Line>>) = (Vec::new(), Vec::new());
280    for found in &per_lane {
281        let (here, gone): (Vec<Line>, Vec<Line>) = found.iter().partition(|l| l.hz.abs() < ceiling);
282        kept.push(here);
283        dropped.push(gone);
284    }
285    // A form with no line at all is silence, not a band every line sat above.
286    if kept.iter().all(Vec::is_empty) && !dropped.iter().all(Vec::is_empty) {
287        let lowest = dropped
288            .iter()
289            .flatten()
290            .map(|l| l.hz.abs())
291            .fold(f64::INFINITY, f64::min);
292        return Err(CollapseError::EmptyBand { ceiling, lowest });
293    }
294    Ok(Some(Kept {
295        kept,
296        dropped,
297        grids,
298        tail,
299    }))
300}
301
302fn lane_plan(lane: &Lane, rate: u32, horizon: Horizon, len: usize) -> LanePlan {
303    let bins = lines::bins(horizon.span(), rate);
304    let sweep = LanePlan::Sweep {
305        atoms: lane.atoms.len(),
306        samples: super::span::nonzero(lane, horizon, rate, len)
307            .iter()
308            .map(|(from, to)| to - from)
309            .sum(),
310    };
311    let Some(found) = lines::grouped(lane) else {
312        return sweep;
313    };
314    let groups: Vec<Group> = found
315        .into_iter()
316        .map(|(factor, held)| {
317            let (placed, summed) = match direct_is_cheaper(held.len(), bins, len) {
318                true => (Vec::new(), held),
319                false => lines::split(&held, bins, rate),
320            };
321            Group {
322                factor,
323                placed,
324                summed,
325            }
326        })
327        .collect();
328    let grouped = LanePlan::Grouped { groups, bins };
329    match grouped.flops(len) <= sweep.flops(len) {
330        true => grouped,
331        false => sweep,
332    }
333}
334
335/// `n*log2(n)` butterflies; a length that is no power of two is Bluestein's three
336/// transforms over the next one past `2n-1`.
337pub fn transform_flops(n: usize) -> u128 {
338    let stages = |m: usize| m as u128 * (m.max(2).trailing_zeros() as u128);
339    match n.is_power_of_two() {
340        true => stages(n),
341        false => 3 * stages((2 * n - 1).next_power_of_two()),
342    }
343}
344
345impl LinePlan {
346    pub fn flops(&self, len: usize) -> u128 {
347        let transforms: u128 = self
348            .placed
349            .iter()
350            .filter(|p| !p.is_empty())
351            .map(|_| transform_flops(self.bins))
352            .sum();
353        let direct: u128 = self
354            .summed
355            .iter()
356            .map(|s| s.len() as u128 * len as u128)
357            .sum();
358        transforms + direct
359    }
360
361    pub fn rule(&self) -> Rule {
362        match (lines::distinct(&self.placed), lines::distinct(&self.summed)) {
363            (_, 0) => Rule::LineSpectrumExact,
364            (0, _) => Rule::LineSpectrumSummed,
365            _ => Rule::LineSpectrumMixed,
366        }
367    }
368}
369
370impl LanePlan {
371    pub fn flops(&self, len: usize) -> u128 {
372        match self {
373            LanePlan::Grouped { groups, bins } => groups
374                .iter()
375                .map(|g| {
376                    let placed = match g.placed.is_empty() {
377                        true => 0,
378                        false => transform_flops(*bins),
379                    };
380                    placed + (g.summed.len() as u128 + 1) * len as u128
381                })
382                .sum(),
383            LanePlan::Sweep { atoms, samples } => *atoms as u128 * *samples as u128,
384        }
385    }
386
387    fn swept_flops(&self, len: u128) -> u128 {
388        let terms: u128 = match self {
389            LanePlan::Grouped { groups, .. } => groups
390                .iter()
391                .map(|g| (g.placed.len() + g.summed.len() + 1) as u128)
392                .sum(),
393            LanePlan::Sweep { atoms, .. } => *atoms as u128,
394        };
395        terms * len
396    }
397}
398
399impl Plan {
400    pub fn flops(&self, len: usize) -> u128 {
401        match self {
402            Plan::Spectrum(_) => transform_flops(len),
403            Plan::Lines(found) => found.flops(len),
404            Plan::Sampled(held) => held.lanes.iter().map(|lane| lane.flops(len)).sum(),
405            Plan::Point { nodes, .. } => *nodes as u128 * len as u128,
406            Plan::Added(parts) => parts.iter().map(|part| part.flops(len)).sum(),
407        }
408    }
409
410    pub fn alias_flops(&self, len: usize) -> u128 {
411        self.alias_flops_at(len, super::ALIAS_OVERSAMPLE)
412    }
413
414    /// The multiple a reading names need not be the label's `ALIAS_OVERSAMPLE`. Every component
415    /// is scored, so every component's reference is paid for.
416    pub fn alias_flops_at(&self, len: usize, oversample: usize) -> u128 {
417        let reference = (len * oversample) as u128;
418        match self {
419            Plan::Point { nodes, .. } => *nodes as u128 * reference,
420            Plan::Sampled(held) if held.rule == Rule::PointSampled => held
421                .lanes
422                .iter()
423                .map(|lane| lane.swept_flops(reference))
424                .sum(),
425            Plan::Added(parts) => parts
426                .iter()
427                .map(|part| part.alias_flops_at(len, oversample))
428                .sum(),
429            Plan::Spectrum(_) | Plan::Lines(_) | Plan::Sampled(_) => 0,
430        }
431    }
432
433    pub fn rule(&self) -> Rule {
434        match self {
435            Plan::Spectrum(_) => Rule::InverseSpectrum,
436            Plan::Lines(found) => found.rule(),
437            Plan::Sampled(held) => held.rule,
438            Plan::Point { .. } => Rule::PointSampled,
439            Plan::Added(_) => Rule::Added,
440        }
441    }
442}
sva_samples/collapse/plan.rs

sva_samples/collapse/
plan.rs
