1use std::fmt::Write as _;
16use std::path::{Path, PathBuf};
17
18use ffcine_core::{Error, Result};
19use ffcine_timeline::{
20 Clip, ExternalReference, Gap, HasMetadata, Item, MediaReference, RationalTime, TimeRange,
21 Timeline, Track, track_kind,
22};
23
24use crate::decode::{self, Request};
25use crate::dsp::{Biquad, ncc, parabolic};
26use crate::place::{self, media_path};
27use crate::schema::{self, Bus, Clean, Level, SyncInfo};
28
29pub const RATE: u32 = 8000;
31const HOP: usize = 40;
33
34#[derive(Debug, Clone)]
35pub struct SyncOptions {
36 pub min_confidence: f64,
38 pub window: f64,
40 pub max_windows: usize,
41 pub search: f64,
43}
44
45impl Default for SyncOptions {
46 fn default() -> Self {
47 Self {
48 min_confidence: 0.15,
49 window: 4.0,
50 max_windows: 24,
51 search: 0.1,
52 }
53 }
54}
55
56#[derive(Debug, Clone)]
58pub struct Prepared {
59 pub signal: Vec<f32>,
61 pub envelope: Vec<f32>,
63}
64
65impl Prepared {
66 pub fn new(mut signal: Vec<f32>) -> Self {
68 let hp = Biquad::highpass(f64::from(RATE), 150.0, std::f64::consts::FRAC_1_SQRT_2);
69 hp.run(&mut signal);
70 hp.run(&mut signal);
71 let mut envelope: Vec<f32> = signal
72 .chunks(HOP)
73 .map(|c| {
74 let ms = c.iter().map(|s| s * s).sum::<f32>() / c.len() as f32;
75 (ms + 1e-9).ln() * 0.5
76 })
77 .collect();
78 let n = envelope.len().max(1) as f32;
79 let mean = envelope.iter().sum::<f32>() / n;
80 let sd = (envelope.iter().map(|e| (e - mean).powi(2)).sum::<f32>() / n)
81 .sqrt()
82 .max(1e-6);
83 for e in &mut envelope {
84 *e = (*e - mean) / sd;
85 }
86 Self { signal, envelope }
87 }
88
89 pub fn load(path: &Path) -> Result<Self> {
90 let a = decode::load(
91 path,
92 &Request {
93 rate: RATE,
94 channels: 1,
95 ..Request::default()
96 },
97 )?;
98 Ok(Self::new(a.to_mono()))
99 }
100
101 fn seconds(&self) -> f64 {
102 self.signal.len() as f64 / f64::from(RATE)
103 }
104}
105
106#[derive(Debug, Clone, PartialEq)]
108pub struct Match {
109 pub recording: usize,
111 pub offset: f64,
113 pub drift_ppm: f64,
114 pub drift_measured: bool,
116 pub coarse: f64,
118 pub margin: f64,
120 pub fine: f64,
122 pub windows: usize,
123 pub inliers: usize,
124 pub residual_ms: f64,
126 pub confidence: f64,
128}
129
130pub fn align(clip: &Prepared, recordings: &[Prepared], opts: &SyncOptions) -> Option<Match> {
132 let na = clip.envelope.len();
133 if na < 20 {
134 return None;
135 }
136 let min_overlap = (na / 2).max(200.min(na));
137 let mut best: Option<(usize, f64, f64, f64)> = None; for (ri, rec) in recordings.iter().enumerate() {
139 let c = ncc(&clip.envelope, &rec.envelope, min_overlap);
140 let Some((k, &peak)) = c.iter().enumerate().max_by(|a, b| a.1.total_cmp(b.1)) else {
141 continue;
142 };
143 if peak <= 0.0 {
144 continue;
145 }
146 let guard = 200; let second = c
148 .iter()
149 .enumerate()
150 .filter(|(i, _)| i.abs_diff(k) > guard)
151 .map(|(_, v)| *v)
152 .fold(0.0f64, f64::max);
153 let margin = (1.0 - second.max(0.0) / peak).clamp(0.0, 1.0);
154 let lag = (k as f64 + parabolic(&c, k) - (na as f64 - 1.0)) * HOP as f64 / f64::from(RATE);
155 if best.is_none_or(|b| peak * margin > b.2 * b.3) {
156 best = Some((ri, lag, peak, margin));
157 }
158 }
159 let mut found =
160 best.map(|(ri, lag, peak, margin)| refine(clip, recordings, ri, lag, peak, margin, opts));
161 if found.as_ref().is_none_or(|m| m.confidence < 0.3) {
163 let wave = recordings
164 .iter()
165 .enumerate()
166 .filter_map(|(ri, r)| coarse_waveform(clip, r).map(|(lag, p, m)| (ri, lag, p, m)))
167 .max_by(|a, b| (a.2 * a.3).total_cmp(&(b.2 * b.3)));
168 if let Some((ri, lag, peak, margin)) = wave {
169 let m = refine(clip, recordings, ri, lag, peak, margin, opts);
170 if found.as_ref().is_none_or(|f| m.confidence > f.confidence) {
171 found = Some(m);
172 }
173 }
174 }
175 found
176}
177
178fn refine(
180 clip: &Prepared,
181 recordings: &[Prepared],
182 ri: usize,
183 lag: f64,
184 coarse: f64,
185 margin: f64,
186 opts: &SyncOptions,
187) -> Match {
188 let fine = fine_windows(clip, &recordings[ri], lag, opts);
189 let (offset, drift, measured, fine_mean, inliers, residual) = fit(&fine, lag);
190 let windows = fine.len().max(1);
191 let confidence = fine_mean * margin * inliers as f64 / windows as f64;
192 Match {
193 recording: ri,
194 offset,
195 drift_ppm: drift * 1e6,
196 drift_measured: measured,
197 coarse,
198 margin,
199 fine: fine_mean,
200 windows: fine.len(),
201 inliers,
202 residual_ms: residual * 1e3,
203 confidence,
204 }
205}
206
207fn coarse_waveform(clip: &Prepared, rec: &Prepared) -> Option<(f64, f64, f64)> {
210 let r = RATE as usize;
211 let w = (8 * r).min(clip.signal.len());
212 if w < r / 2 || rec.signal.len() < w {
213 return None;
214 }
215 let energy = |s: usize| clip.signal[s..s + w].iter().map(|x| x * x).sum::<f32>();
217 let ws = (0..=clip.signal.len() - w)
218 .step_by(r)
219 .max_by(|a, b| energy(*a).total_cmp(&energy(*b)))?;
220 let a = &clip.signal[ws..ws + w];
221 let block = (1usize << 20).max(4 * w);
222 let mut buckets = vec![(f64::MIN, 0.0f64); rec.signal.len() / r + 1];
223 let mut start = 0;
224 while start + w <= rec.signal.len() {
225 let end = (start + block).min(rec.signal.len());
226 let seg = &rec.signal[start..end];
227 let c = ncc(a, seg, w);
228 let full = &c[w - 1..=w - 1 + (seg.len() - w)];
229 for (k, &v) in full.iter().enumerate() {
230 let b = &mut buckets[(start + k) / r];
231 if v > b.0 {
232 *b = (v, (start + k) as f64 + parabolic(full, k));
233 }
234 }
235 if end == rec.signal.len() {
236 break;
237 }
238 start = end - w + 1;
239 }
240 let (bi, &(peak, pos)) = buckets
241 .iter()
242 .enumerate()
243 .max_by(|x, y| x.1.0.total_cmp(&y.1.0))?;
244 if peak <= 0.0 {
245 return None;
246 }
247 let second = buckets
248 .iter()
249 .enumerate()
250 .filter(|(i, _)| i.abs_diff(bi) > 1)
251 .map(|(_, b)| b.0)
252 .fold(0.0f64, f64::max);
253 let margin = (1.0 - second.max(0.0) / peak).clamp(0.0, 1.0);
254 Some(((pos - ws as f64) / f64::from(RATE), peak, margin))
255}
256
257fn fine_windows(
259 clip: &Prepared,
260 rec: &Prepared,
261 lag: f64,
262 opts: &SyncOptions,
263) -> Vec<(f64, f64, f64)> {
264 let r = f64::from(RATE);
265 let len = clip.signal.len();
266 let w = ((opts.window * r) as usize).min(len);
267 if w < RATE as usize / 2 {
268 return Vec::new();
269 }
270 let n = (len / w).clamp(1, opts.max_windows);
271 let rms = |x: &[f32]| (x.iter().map(|s| s * s).sum::<f32>() / x.len().max(1) as f32).sqrt();
272 let floor = rms(&clip.signal) * 0.05;
273 let m = (opts.search * r) as isize;
274 let mut out = Vec::new();
275 for i in 0..n {
276 let s = if n == 1 { 0 } else { i * (len - w) / (n - 1) };
277 let a = &clip.signal[s..s + w];
278 if rms(a) <= floor {
279 continue;
280 }
281 let p = s as isize + (lag * r).round() as isize;
282 let lo = (p - m).max(0);
283 let hi = (p + w as isize + m).min(rec.signal.len() as isize);
284 if hi - lo < w as isize {
285 continue;
286 }
287 let seg = &rec.signal[lo as usize..hi as usize];
288 let c = ncc(a, seg, w);
289 let full = &c[w - 1..=w - 1 + (seg.len() - w)];
291 let Some((k, &v)) = full.iter().enumerate().max_by(|x, y| x.1.total_cmp(y.1)) else {
292 continue;
293 };
294 let pos = lo as f64 + k as f64 + parabolic(full, k);
295 let t = (s as f64 + w as f64 / 2.0) / r;
296 out.push((t, (pos - s as f64) / r, v));
297 }
298 out
299}
300
301fn fit(points: &[(f64, f64, f64)], coarse: f64) -> (f64, f64, bool, f64, usize, f64) {
304 let mut pts: Vec<(f64, f64, f64)> = points.iter().copied().filter(|p| p.2 > 0.1).collect();
305 if pts.is_empty() {
306 return (coarse, 0.0, false, 0.0, 0, 0.0);
307 }
308 let mut offs: Vec<f64> = pts.iter().map(|p| p.1).collect();
310 offs.sort_by(f64::total_cmp);
311 let med = offs[offs.len() / 2];
312 pts.retain(|p| (p.1 - med).abs() < 0.005);
313 for _ in 0..3 {
314 let line = line_fit(&pts, med);
315 let before = pts.len();
316 pts.retain(|p| (p.1 - (line.0 + line.1 * p.0)).abs() < 0.001);
317 if pts.len() == before || pts.len() < 2 {
318 break;
319 }
320 }
321 if pts.is_empty() {
322 return (med, 0.0, false, 0.0, 0, 0.0);
323 }
324 let line = line_fit(&pts, med);
325 let n = pts.len() as f64;
326 let score = pts.iter().map(|p| p.2).sum::<f64>() / n;
327 let res = (pts
328 .iter()
329 .map(|p| (p.1 - (line.0 + line.1 * p.0)).powi(2))
330 .sum::<f64>()
331 / n)
332 .sqrt();
333 (line.0, line.1, line.2, score.min(1.0), pts.len(), res)
334}
335
336fn line_fit(pts: &[(f64, f64, f64)], fallback: f64) -> (f64, f64, bool) {
337 let sw: f64 = pts.iter().map(|p| p.2).sum();
338 if sw <= 0.0 {
339 return (fallback, 0.0, false);
340 }
341 let mt = pts.iter().map(|p| p.2 * p.0).sum::<f64>() / sw;
342 let mo = pts.iter().map(|p| p.2 * p.1).sum::<f64>() / sw;
343 let (tmin, tmax) = pts
344 .iter()
345 .fold((f64::MAX, f64::MIN), |(a, b), p| (a.min(p.0), b.max(p.0)));
346 if pts.len() < 3 || tmax - tmin < 20.0 {
347 return (mo, 0.0, false);
348 }
349 let stt: f64 = pts.iter().map(|p| p.2 * (p.0 - mt).powi(2)).sum();
350 let sto: f64 = pts.iter().map(|p| p.2 * (p.0 - mt) * (p.1 - mo)).sum();
351 let b = sto / stt;
352 (mo - b * mt, b, true)
353}
354
355#[derive(Debug, Clone)]
357pub struct ClipSync {
358 pub video: PathBuf,
359 pub seconds: f64,
360 pub found: Option<Match>,
361}
362
363pub fn sync_files(
366 videos: &[PathBuf],
367 recordings: &[PathBuf],
368 opts: &SyncOptions,
369) -> Result<Vec<ClipSync>> {
370 let recs = recordings
371 .iter()
372 .map(|p| Prepared::load(p))
373 .collect::<Result<Vec<_>>>()?;
374 let mut out = Vec::new();
375 for v in videos {
376 let clip = Prepared::load(v)?;
377 out.push(ClipSync {
378 video: v.clone(),
379 seconds: clip.seconds(),
380 found: align(&clip, &recs, opts),
381 });
382 }
383 borrow_drift(&mut out);
384 Ok(out)
385}
386
387fn borrow_drift(clips: &mut [ClipSync]) {
388 let recs: Vec<usize> = clips
389 .iter()
390 .filter_map(|c| c.found.as_ref().map(|m| m.recording))
391 .collect();
392 for r in recs {
393 let mut d: Vec<f64> = clips
394 .iter()
395 .filter_map(|c| c.found.as_ref())
396 .filter(|m| m.recording == r && m.drift_measured)
397 .map(|m| m.drift_ppm)
398 .collect();
399 if d.is_empty() {
400 continue;
401 }
402 d.sort_by(f64::total_cmp);
403 let med = d[d.len() / 2];
404 for m in clips.iter_mut().filter_map(|c| c.found.as_mut()) {
405 if m.recording == r && !m.drift_measured {
406 m.drift_ppm = med;
407 }
408 }
409 }
410}
411
412#[derive(Debug, Clone, Default)]
414pub struct WriteOptions {
415 pub lead: f64,
417 pub tail: f64,
419 pub min_confidence: f64,
420 pub track: Option<String>,
422 pub clean: Option<Clean>,
424}
425
426pub fn write_timeline(
430 timeline: Option<Timeline>,
431 syncs: &[ClipSync],
432 recordings: &[PathBuf],
433 opts: &WriteOptions,
434) -> Result<Timeline> {
435 let mut tl = match timeline {
436 Some(t) => t,
437 None => video_timeline(syncs),
438 };
439 let rates: Vec<f64> = recordings.iter().map(|p| native_rate(p)).collect();
440 let video = tl
441 .track_list()
442 .find(|t| t.kind == track_kind::VIDEO)
443 .ok_or_else(|| Error::Invalid {
444 what: "timeline",
445 value: "no video track".into(),
446 })?
447 .clone();
448 let (placed, _) = place::layout(&video);
449 let name = opts.track.clone().unwrap_or_else(|| "H2".into());
450 let split = opts.lead > 0.0 || opts.tail > 0.0;
451 let mut tracks = vec![audio_track(&name)];
452 if split {
453 tracks[0].name = format!("{name} A");
454 tracks.push(audio_track(&format!("{name} B")));
455 }
456 let mut cursor = vec![0.0f64; tracks.len()];
457 let mut n = 0usize;
458 for p in &placed {
459 let Some(path) = media_path(p.clip, None) else {
460 continue;
461 };
462 let Some(s) = syncs.iter().find(|s| same_file(&s.video, &path)) else {
463 continue;
464 };
465 let Some(m) = s
466 .found
467 .as_ref()
468 .filter(|m| m.confidence >= opts.min_confidence)
469 else {
470 continue;
471 };
472 let rate = rates[m.recording];
473 let k = 1.0 + m.drift_ppm * 1e-6;
474 let ti = n % tracks.len();
475 n += 1;
476 let mut start = p.start - opts.lead;
477 let mut src = m.offset + (p.source_start - opts.lead) * k;
478 let mut dur = p.duration + opts.lead + opts.tail;
479 let cut = (cursor[ti] - start).max(-src / k).max(0.0);
481 start += cut;
482 src += cut * k;
483 dur -= cut;
484 if dur <= 0.0 {
485 continue;
486 }
487 if start > cursor[ti] + 1e-9 {
488 tracks[ti]
489 .children
490 .push(Item::Gap(Gap::new(RationalTime::from_seconds(
491 start - cursor[ti],
492 rate,
493 ))));
494 }
495 let wav = &recordings[m.recording];
496 let mut clip = Clip::new(
497 format!("{} {}", stem(wav), p.clip.name),
498 MediaReference::External(ExternalReference::from_path(wav, None)),
499 Some(TimeRange::new(
500 RationalTime::from_seconds(src, rate),
501 RationalTime::from_seconds(dur, rate),
502 )),
503 );
504 let id = p.clip.ffcine_id().unwrap_or(&p.clip.name).to_owned();
505 clip.set_ffcine_id(format!("{id}.audio"));
506 clip.ffcine_set(
507 "sync",
508 &SyncInfo {
509 schema: format!("{}/1", schema::SYNC),
510 video: id,
511 offset: m.offset,
512 drift_ppm: m.drift_ppm,
513 confidence: m.confidence,
514 },
515 )?;
516 if let Some(c) = &opts.clean {
517 clip.effects
518 .push(schema::make_effect("clean", schema::CLEAN, c)?);
519 }
520 clip.effects.push(schema::make_effect(
521 "level",
522 schema::LEVEL,
523 &Level::default(),
524 )?);
525 tracks[ti].children.push(Item::Clip(clip));
526 cursor[ti] = start + dur;
527 }
528 tl.tracks
529 .children
530 .extend(tracks.into_iter().map(Item::Track));
531 Ok(tl)
532}
533
534fn audio_track(name: &str) -> Track {
535 let mut t = Track::new(name, track_kind::AUDIO);
536 t.ffcine_mut()
537 .insert("bus".into(), Bus::Dialogue.name().into());
538 t
539}
540
541fn video_timeline(syncs: &[ClipSync]) -> Timeline {
543 let mut track = Track::new("V1", track_kind::VIDEO);
544 for s in syncs {
545 let rate = decode::video_rate(&s.video).unwrap_or(48000.0);
546 let range = TimeRange::new(
547 RationalTime::new(0.0, rate),
548 RationalTime::from_seconds(s.seconds, rate),
549 );
550 let mut clip = Clip::new(
551 stem(&s.video),
552 MediaReference::External(ExternalReference::from_path(&s.video, Some(range.clone()))),
553 Some(range),
554 );
555 clip.set_ffcine_id(stem(&s.video));
556 track.children.push(Item::Clip(clip));
557 }
558 let mut tl = Timeline::new("sync");
559 tl.tracks.children.push(Item::Track(track));
560 tl
561}
562
563fn stem(p: &Path) -> String {
564 p.file_stem()
565 .map_or_else(String::new, |s| s.to_string_lossy().into_owned())
566}
567
568fn same_file(a: &Path, b: &Path) -> bool {
569 match (a.canonicalize(), b.canonicalize()) {
570 (Ok(x), Ok(y)) => x == y,
571 _ => a.file_name() == b.file_name(),
572 }
573}
574
575fn native_rate(p: &Path) -> f64 {
577 hound::WavReader::open(p).map_or(48000.0, |r| f64::from(r.spec().sample_rate))
578}
579
580pub fn report(syncs: &[ClipSync], recordings: &[PathBuf]) -> String {
582 let mut s = String::from(
583 "clip\trecording\toffset_s\tdrift_ppm\tconfidence\tfine\tmargin\twindows\tresidual_ms\n",
584 );
585 for c in syncs {
586 let name = c
587 .video
588 .file_name()
589 .map_or_else(String::new, |n| n.to_string_lossy().into_owned());
590 match &c.found {
591 Some(m) => {
592 let rec = recordings[m.recording]
593 .file_name()
594 .map_or_else(String::new, |n| n.to_string_lossy().into_owned());
595 let _ = writeln!(
596 s,
597 "{name}\t{rec}\t{:.6}\t{:.1}{}\t{:.2}\t{:.2}\t{:.2}\t{}/{}\t{:.3}",
598 m.offset,
599 m.drift_ppm,
600 if m.drift_measured { "" } else { "*" },
601 m.confidence,
602 m.fine,
603 m.margin,
604 m.inliers,
605 m.windows,
606 m.residual_ms
607 );
608 }
609 None => {
610 let _ = writeln!(s, "{name}\t-\t-\t-\t0\t-\t-\t-\t-");
611 }
612 }
613 }
614 s
615}
616
617#[cfg(test)]
618mod tests {
619 use super::*;
620 use crate::dsp::warp;
621
622 fn noise(seed: u64, n: usize) -> Vec<f32> {
624 let mut x = seed.max(1);
625 (0..n)
626 .map(|_| {
627 x ^= x << 13;
628 x ^= x >> 7;
629 x ^= x << 17;
630 (x >> 40) as f32 / (1u64 << 23) as f32 - 1.0
631 })
632 .collect()
633 }
634
635 fn scene(seed: u64, seconds: f64) -> Vec<f32> {
637 let n = (seconds * f64::from(RATE)) as usize;
638 let mut x = noise(seed, n);
639 let gates = noise(seed ^ 0xabc, n / 2000 + 1);
640 for (i, s) in x.iter_mut().enumerate() {
641 let g = gates[i / 2000].max(0.0);
642 *s *= g;
643 }
644 x
645 }
646
647 #[test]
648 fn finds_offset_and_drift() {
649 let rec = scene(7, 300.0);
650 let k = 1.0 + 40e-6;
653 let start = 100.0375 * f64::from(RATE);
654 let mut cam = warp(&rec, start, k, (60.0 * f64::from(RATE)) as usize);
655 let n2 = noise(99, cam.len());
656 for (c, n) in cam.iter_mut().zip(n2) {
657 *c = *c * 0.3 + n * 0.02;
658 }
659 let other = Prepared::new(scene(11, 200.0));
660 let m = align(
661 &Prepared::new(cam),
662 &[other, Prepared::new(rec)],
663 &SyncOptions::default(),
664 )
665 .expect("match");
666 assert_eq!(m.recording, 1);
667 assert!((m.offset - 100.0375).abs() < 2e-4, "offset {}", m.offset);
668 assert!(m.drift_measured);
669 assert!((m.drift_ppm - 40.0).abs() < 8.0, "drift {}", m.drift_ppm);
670 assert!(m.confidence > 0.5, "{m:?}");
671 }
672
673 #[test]
674 fn clip_before_recording_start() {
675 let rec = scene(3, 120.0);
676 let mut cam = scene(5, 2.0);
678 cam.extend_from_slice(&rec[..(10.0 * f64::from(RATE)) as usize]);
679 let m = align(
680 &Prepared::new(cam),
681 &[Prepared::new(rec)],
682 &SyncOptions::default(),
683 )
684 .expect("match");
685 assert!((m.offset + 2.0).abs() < 2e-4, "offset {}", m.offset);
686 }
687
688 #[test]
689 fn unrelated_audio_has_low_confidence() {
690 let rec = scene(3, 120.0);
691 let cam = scene(42, 15.0);
692 let m = align(
693 &Prepared::new(cam),
694 &[Prepared::new(rec)],
695 &SyncOptions::default(),
696 );
697 assert!(m.as_ref().is_none_or(|m| m.confidence < 0.15), "{m:?}");
698 }
699}