From 7cc88394458e9d03e3a6a6e58cdff9c8dd4ad7a3 Mon Sep 17 00:00:00 2001 From: Peter Stone Date: Mon, 5 Oct 2026 08:57:59 +0000 Subject: Find why Tier 3 never confirmed, and port detection to Go Peter's report: the phone runs hot, uses a lot of battery, playback takes a moment to start, and intelligent skipping has never done anything. **The hot phone and the dead detection were one bug.** The candidate search correlated 117 window positions against the whole of the other clip, re-transforming that unchanged clip every time -- 199 seconds per episode end, measured on a desktop, so minutes more on a phone. FingerprintWorker is a plain WorkManager worker, Android stops one at ten minutes, and nothing was persisted until a comparison returned. So it was killed mid-flight, saved nothing, and was re-enqueued to start over, forever. IntroOutroDetectorScaleTest is the tripwire whose absence allowed this: the unit tests ran on 300-sample clips while production ran on 1,920,000. Fixed coarse-to-fine, plus AudioCorrelation.prepareTarget so the target clip is transformed once per search rather than 117 times. 10.6x, and a test asserts the chosen reference window is byte-identical to what a full-resolution search picks. **Midroll detection could never have run at all.** decodeFull buffered a whole episode at its native rate -- 434MB for a 13-minute episode, no largeHeap -- to produce 6MB of 8kHz mono. It threw OutOfMemoryError into a swallowing runCatching and the episode was then marked checked forever. MonoResampler now streams the decode so the peak allocation is the output, and maxDecodableMs skips a longer episode before spending anything and without marking it checked. **Detection is moving to a server**, Peter's call, in Go to match podkit and doot. server/ holds the ported core, verified three ways because this is the second port of this maths and the first shipped a normalization bug: numpy's literals extracted mechanically from AudioCorrelationTest, the FFT against a direct DFT, and the whole correlation path against a brute-force Pearson. On four real Radiolab episodes it confirms the intro on 4 of 4, at 48.0s, 8.65s, 8.65s and 65.15s -- the varying pre-roll, observed in working code at last. skips.SelfCheck verifies located segments against *each other* rather than against the reference, which is a different claim: correlation is not transitive, so two segments can each clear 0.6 against a reference and be unrelated. It rejected the outro on its first real run (r=0.746), withholding offsets that would have ended three episodes early. Offsets are published only when they verify. Also: the episode screen gets a working scrubber with ad-break marks and a declared-versus-measured length readout, queue rows open the episode instead of doing nothing, PrepareTrace logs playback-start timing against episode length for the still-open pause question, and -PphoneOnly drops the emulator's CPython from a sideload build (114MB -> 99MB). Full history and numbers in docs/detection-findings.md. Co-Authored-By: Claude Opus 5 Claude-Session: https://claude.ai/code/session_018AwnALZL6bD4VBtATDVv3B --- .coverage-baseline | 2 +- CLAUDE.md | 80 ++++- app/build.gradle.kts | 15 +- .../terst/listen/fingerprint/AudioCorrelation.kt | 91 +++-- .../terst/listen/fingerprint/IntroOutroDetector.kt | 144 +++++++- .../listen/fingerprint/MediaCodecClipSource.kt | 145 ++++---- .../org/terst/listen/fingerprint/MidrollUpdater.kt | 44 ++- .../org/terst/listen/fingerprint/MonoResampler.kt | 134 +++++++ .../org/terst/listen/fingerprint/SkipSummary.kt | 39 ++ .../org/terst/listen/playback/PlaybackService.kt | 25 ++ .../java/org/terst/listen/playback/PrepareTrace.kt | 89 +++++ .../org/terst/listen/ui/EpisodeDetailActions.kt | 8 + .../main/java/org/terst/listen/ui/EpisodeScreen.kt | 205 ++++++++++- .../java/org/terst/listen/ui/ListenViewModel.kt | 12 + .../main/java/org/terst/listen/ui/MainActivity.kt | 9 +- .../main/java/org/terst/listen/ui/QueueScreen.kt | 49 ++- .../listen/fingerprint/AudioCorrelationTest.kt | 37 ++ .../fingerprint/IntroOutroDetectorScaleTest.kt | 171 +++++++++ .../listen/fingerprint/IntroOutroDetectorTest.kt | 2 +- .../terst/listen/fingerprint/MidrollUpdaterTest.kt | 67 +++- .../terst/listen/fingerprint/MonoResamplerTest.kt | 161 +++++++++ .../terst/listen/fingerprint/SkipSummaryTest.kt | 94 +++++ .../org/terst/listen/playback/PrepareTraceTest.kt | 142 ++++++++ docs/detection-findings.md | 223 ++++++++++++ server/cmd/listen-detect/main.go | 119 +++++++ server/go.mod | 3 + server/internal/decode/decode.go | 123 +++++++ server/internal/decode/decode_test.go | 164 +++++++++ server/internal/detect/correlate.go | 182 ++++++++++ server/internal/detect/correlate_test.go | 140 ++++++++ server/internal/detect/decimate.go | 22 ++ server/internal/detect/decimate_test.go | 35 ++ server/internal/detect/fft.go | 76 ++++ server/internal/detect/fft_test.go | 78 ++++ server/internal/detect/fixtures_test.go | 128 +++++++ server/internal/detect/recurring.go | 229 ++++++++++++ server/internal/detect/recurring_test.go | 164 +++++++++ server/internal/skips/selfcheck.go | 106 ++++++ server/internal/skips/selfcheck_test.go | 104 ++++++ server/internal/skips/skips.go | 251 +++++++++++++ server/internal/skips/skips_test.go | 394 +++++++++++++++++++++ tools/.keep | 0 42 files changed, 4141 insertions(+), 165 deletions(-) create mode 100644 app/src/main/java/org/terst/listen/fingerprint/MonoResampler.kt create mode 100644 app/src/main/java/org/terst/listen/playback/PrepareTrace.kt create mode 100644 app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorScaleTest.kt create mode 100644 app/src/test/java/org/terst/listen/fingerprint/MonoResamplerTest.kt create mode 100644 app/src/test/java/org/terst/listen/playback/PrepareTraceTest.kt create mode 100644 server/cmd/listen-detect/main.go create mode 100644 server/go.mod create mode 100644 server/internal/decode/decode.go create mode 100644 server/internal/decode/decode_test.go create mode 100644 server/internal/detect/correlate.go create mode 100644 server/internal/detect/correlate_test.go create mode 100644 server/internal/detect/decimate.go create mode 100644 server/internal/detect/decimate_test.go create mode 100644 server/internal/detect/fft.go create mode 100644 server/internal/detect/fft_test.go create mode 100644 server/internal/detect/fixtures_test.go create mode 100644 server/internal/detect/recurring.go create mode 100644 server/internal/detect/recurring_test.go create mode 100644 server/internal/skips/selfcheck.go create mode 100644 server/internal/skips/selfcheck_test.go create mode 100644 server/internal/skips/skips.go create mode 100644 server/internal/skips/skips_test.go create mode 100644 tools/.keep diff --git a/.coverage-baseline b/.coverage-baseline index 1f799fd..423c6ac 100644 --- a/.coverage-baseline +++ b/.coverage-baseline @@ -1 +1 @@ -93.03 +93.41 diff --git a/CLAUDE.md b/CLAUDE.md index 8121bfe..5a7d1ae 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -194,21 +194,77 @@ by default and correct; it is simply waiting for a publisher who marks breaks. - **Auto-downloads are not retried.** A rule's download that fails is left FAILED rather than requeued: retrying forever against a 404 would burn the battery, and the failed row is visible in the episode list. Retry is the manual Download button. -- **Tier 3 had never confirmed a real intro, outro or midroll, and root cause is now found and +- **Tier 3 had never confirmed anything, and there were two independent reasons, both now fixed.** Not the correlation algorithm -- a real production-algorithm simulation against real - Up First audio confirmed cleanly at the app's actual defaults before any of this. The real - cause: `RetentionPolicy`'s one-day grace period routinely reclaimed a show's pending episode's - file before the next download arrived to compare it against, for a fast, promptly-listened-to - show like Up First -- so the detector kept discarding its only candidate and restarting instead - of ever comparing two episodes. Confirmed live on the phone (a fresh download's - `FingerprintWorker` run replaced the stale pending episode instead of advancing toward a - comparison). Fixed by protecting a show's pending episode from reclaim, for both intro/outro - and midroll -- `RetentionSweeper` now takes a `pendingEpisodeIds` seam and - `RetentionWorker` supplies the union of both mechanisms' pending ids. **Not yet re-verified on - a device.** Full history in `docs/detection-findings.md`. Do not tune + Up First audio confirmed cleanly at the app's actual defaults before any of this. Do not tune `DEFAULT_REFERENCE_SECONDS`, `MIN_SCORE` or `CONFIRM_THRESHOLD` from the app -- they were never the problem, the app cannot show you what a change costs in false positives, and the threshold - is the whole safety mechanism. + is the whole safety mechanism. Full history, with numbers, in `docs/detection-findings.md`. + + **Reason one, retention (found 2026-09-29).** `RetentionPolicy`'s one-day grace period + routinely reclaimed a show's pending episode's file before the next download arrived to compare + it against, for a fast, promptly-listened-to show like Up First -- so the detector kept + discarding its only candidate and restarting. Confirmed live on the phone. Fixed by protecting + a show's pending episode from reclaim, for both mechanisms: `RetentionSweeper` takes a + `pendingEpisodeIds` seam and `RetentionWorker` supplies the union. + + **Reason two, cost (found 2026-10-03, and on the evidence the dominant one).** The candidate + search correlated 117 window positions against the whole of the other clip, re-transforming + that unchanged clip every time: **199 seconds per end, measured on a desktop**, so minutes more + on a phone. `FingerprintWorker` is a plain WorkManager worker, Android stops one at ~ten + minutes, and nothing is persisted until a comparison returns -- so it was killed mid-flight, + saved nothing, and was re-enqueued to start over. That is why Peter's phone ran hot *and* why + no show ever got past its first processed episode; one cause, both symptoms. Fixed by + coarse-to-fine search plus `AudioCorrelation.prepareTarget`: **10.6x faster, and + `IntroOutroDetectorScaleTest` asserts the chosen reference window is byte-identical to what a + full-resolution search picks**, so none of the speed came out of detection quality. + + **Neither fix is yet verified on a device.** + +- **`IntroOutroDetectorScaleTest` is a cost tripwire, not a benchmark -- do not delete it for + being slow.** The unit tests prove the state machine on 300-sample clips; production hands the + detector 1,920,000, and nothing measured that for two phases of work. It asserts a 60-second + budget at the real sizes with the real constants. If it starts failing, the search got + expensive again, and the consequence is a worker that burns ten minutes and persists nothing. + +- **Midroll detection could never have run on an episode of normal length**, found the same day + and independent of everything above. `decodeFull` buffered the whole episode at its native rate + (a 13-minute stereo episode: 145MB of PCM plus 289MB of mono frames live at once, no + `largeHeap`) to produce 6MB of 8kHz output. It threw `OutOfMemoryError`, `runCatching` + swallowed it, and `MidrollUpdater` then marked the episode **checked forever** -- so nothing + was ever scanned, nothing would be retried, and the readout said "None found" rather than + anything true. `MonoResampler` now consumes the decoder buffer by buffer and keeps only the + output, and `Tuning.maxDecodableMs` (20 minutes) skips a longer episode before spending + anything and without marking it checked. + + **Still outstanding:** episodes over that ceiling are not scanned at all. Lifting it means + decoding candidate ranges on demand rather than the whole body -- `MidrollUpdater.discover`, + `extractSegment` and `MidrollDetector.check` all currently want the entire native-resolution + array. Left deliberately undone rather than half-done. + +- **`PrepareTrace` logs one line per playback start**, tagged `ListenPlayback`, carrying the + episode's real length against the elapsed time to READY and to PLAYING: + `prepare ep=abc len=1774s src=local ready=812ms playing=903ms`. It exists for an open question + of Peter's -- a pause before playback that looks proportional to episode length -- which cannot + be answered from the code: nothing in the play path scales with length, so it is either Media3's + own preparation or CPU starvation, and those are indistinguishable from outside. The clock + starts in `onMediaItemTransition`, the only hook both play paths reach (a tap in the UI goes + through a MediaController and never calls the service's `play`). + + **Measured so far: ~440ms to READY for a 27-minute downloaded episode on the emulator**, with + nothing else loading the device -- so the cost is real and not purely CPU starvation. Whether + it scales with length is still open and needs two episodes of very different lengths; the log + line carries both numbers, so ordinary use on the phone answers it. + +- **Do not re-test the missing MP3 seek table.** These files carry no Xing, Info or VBRI header, + so Media3 has no seek table to read, and the obvious theory was that `Mp3Extractor` scans the + file to build one -- length-proportional, matching the report exactly. **Disproven by + measurement:** enabling `Mp3Extractor.FLAG_ENABLE_CONSTANT_BITRATE_SEEKING` moved the mean not + at all (404/531/386ms against 469/450/404ms). A first single sample of each had looked like a + 38% win and was cold-start noise -- the spread here is wider than any effect, so one sample + proves nothing. It would have been the wrong trade regardless: constant-bitrate seeking makes + seeks approximate on a VBR file, and the playback position is the crown jewel. Full numbers in + `docs/detection-findings.md`. - **Android Auto is verified in a real car**, as of 2026-09-28. It appears, and connects. The notification Peter saw on first connect was Android Auto's own new-media-app announcement, diff --git a/app/build.gradle.kts b/app/build.gradle.kts index bc8c4bd..36d6038 100644 --- a/app/build.gradle.kts +++ b/app/build.gradle.kts @@ -65,7 +65,20 @@ android { ndk { // CPython ships as native code, so every ABI included multiplies the APK size. // arm64 is the phone; x86_64 is the emulator. - abiFilters += listOf("arm64-v8a", "x86_64") + // + // `-PphoneOnly` drops the emulator's copy: measured at 114MB -> 99MB, so 15MB and + // not the halving it looks like it should be. The APK is dominated by 72MB of + // unminified debug dex, with Chaquopy's assets and one ABI's CPython adding ~25MB + // between them; shrinking it meaningfully means R8 on a debug build, not ABIs. + // + // Not the default: a build with no flag has to stay installable on the emulator too, + // or it stops being usable by whoever forgets. Pass it for a build only the phone + // will ever install. + abiFilters += if (project.hasProperty("phoneOnly")) { + listOf("arm64-v8a") + } else { + listOf("arm64-v8a", "x86_64") + } } } diff --git a/app/src/main/java/org/terst/listen/fingerprint/AudioCorrelation.kt b/app/src/main/java/org/terst/listen/fingerprint/AudioCorrelation.kt index 0b477a1..1576bc8 100644 --- a/app/src/main/java/org/terst/listen/fingerprint/AudioCorrelation.kt +++ b/app/src/main/java/org/terst/listen/fingerprint/AudioCorrelation.kt @@ -28,12 +28,69 @@ object AudioCorrelation { /** A score below this isn't a real match -- see [bestMatch]'s silence/no-signal handling. */ private const val MIN_QUERY_ENERGY = 1e-6 + /** + * A target with its expensive, query-independent half already computed. + * + * The transform of the target and its rolling sums depend only on the target and on how long + * a query will be -- not on the query's contents. A window search correlates many queries + * against one unchanged target ([IntroOutroDetector]'s candidate search does it 117 times), + * and recomputing this for each of them was most of why fingerprinting could not finish + * inside a WorkManager worker. + * + * Opaque on purpose: [prepareTarget] is the only way to build one, so the invariant that the + * transform matches [querySize] cannot be broken from outside. + */ + class PreparedTarget internal constructor( + internal val targetSize: Int, + internal val querySize: Int, + internal val transformRe: DoubleArray, + internal val transformIm: DoubleArray, + internal val localSum: DoubleArray, + internal val localSumSq: DoubleArray, + ) + + /** + * [target] with everything that does not depend on the query's contents computed once, for + * queries of exactly [querySize] samples. + * + * Returns a prepared target even when [querySize] does not fit, so the caller does not have + * to duplicate that check; [bestMatch] reports the same null it always did. + */ + fun prepareTarget(target: DoubleArray, querySize: Int): PreparedTarget { + if (querySize <= 0 || querySize > target.size) { + return PreparedTarget(target.size, querySize, DoubleArray(0), DoubleArray(0), DoubleArray(0), DoubleArray(0)) + } + val n = Fft.nextPowerOfTwo(target.size + querySize - 1) + val re = target.copyOf(n) + val im = DoubleArray(n) + Fft.transform(re, im, inverse = false) + return PreparedTarget( + targetSize = target.size, + querySize = querySize, + transformRe = re, + transformIm = im, + localSum = rollingSum(target, querySize), + localSumSq = rollingSum(DoubleArray(target.size) { target[it] * target[it] }, querySize), + ) + } + /** * The best-aligned position of [query] inside [target], or null if there is nowhere valid * to place it (the query is longer than the target) or the query itself carries no signal * to match against (silence has an undefined correlation with anything). */ - fun bestMatch(query: DoubleArray, target: DoubleArray): Match? { + fun bestMatch(query: DoubleArray, target: DoubleArray): Match? = + bestMatch(query, prepareTarget(target, query.size)) + + /** + * The same answer as [bestMatch], against a target prepared once by [prepareTarget]. + * + * Null for a query whose length is not the one the target was prepared for: the prepared + * transform is sized for that length and silently reusing it at another would not be a + * slower correct answer, it would be a wrong one. + */ + fun bestMatch(query: DoubleArray, target: PreparedTarget): Match? { + if (query.size != target.querySize) return null val scores = normalizedCrossCorrelation(query, target) ?: return null if (scores.isEmpty()) return null var bestIndex = 0 @@ -59,9 +116,9 @@ object AudioCorrelation { * (each window's own standard deviation times the query's) comes from a rolling sum and * sum-of-squares over `target`, needing no FFT. */ - private fun normalizedCrossCorrelation(query: DoubleArray, target: DoubleArray): DoubleArray? { + private fun normalizedCrossCorrelation(query: DoubleArray, target: PreparedTarget): DoubleArray? { val win = query.size - if (win == 0 || win > target.size) return null + if (win == 0 || win > target.targetSize) return null val queryMean = query.average() val centeredQuery = DoubleArray(win) { query[it] - queryMean } @@ -70,13 +127,10 @@ object AudioCorrelation { val dot = validConvolution(target, reversed(centeredQuery)) - val localSum = rollingSum(target, win) - val localSumSq = rollingSum(DoubleArray(target.size) { target[it] * target[it] }, win) - val scores = DoubleArray(dot.size) for (i in dot.indices) { - val mean = localSum[i] / win - val variance = max(localSumSq[i] / win - mean * mean, 0.0) + val mean = target.localSum[i] / win + val variance = max(target.localSumSq[i] / win - mean * mean, 0.0) val localNorm = sqrt(variance * win) val denom = localNorm * queryNorm scores[i] = if (denom < MIN_QUERY_ENERGY) 0.0 else dot[i] / denom @@ -100,31 +154,28 @@ object AudioCorrelation { } /** - * The "valid" slice of convolving [target] with [kernel]: length `target.size - kernel.size - * + 1`, computed via zero-padded FFT rather than the O(n*m) direct sum. + * The "valid" slice of convolving [target] with [kernel]: length `target.targetSize - + * kernel.size + 1`, computed via zero-padded FFT rather than the O(n*m) direct sum. + * + * Two transforms, not three: the target's was already done by [prepareTarget]. */ - private fun validConvolution(target: DoubleArray, kernel: DoubleArray): DoubleArray { - val fullLength = target.size + kernel.size - 1 - val n = Fft.nextPowerOfTwo(fullLength) + private fun validConvolution(target: PreparedTarget, kernel: DoubleArray): DoubleArray { + val n = target.transformRe.size - val targetRe = target.copyOf(n) - val targetIm = DoubleArray(n) val kernelRe = kernel.copyOf(n) val kernelIm = DoubleArray(n) - - Fft.transform(targetRe, targetIm, inverse = false) Fft.transform(kernelRe, kernelIm, inverse = false) val productRe = DoubleArray(n) val productIm = DoubleArray(n) for (i in 0 until n) { - productRe[i] = targetRe[i] * kernelRe[i] - targetIm[i] * kernelIm[i] - productIm[i] = targetRe[i] * kernelIm[i] + targetIm[i] * kernelRe[i] + productRe[i] = target.transformRe[i] * kernelRe[i] - target.transformIm[i] * kernelIm[i] + productIm[i] = target.transformRe[i] * kernelIm[i] + target.transformIm[i] * kernelRe[i] } Fft.transform(productRe, productIm, inverse = true) // The valid region starts once the kernel is fully overlapped with the target. - val validLength = target.size - kernel.size + 1 + val validLength = target.targetSize - kernel.size + 1 return DoubleArray(validLength) { productRe[it + kernel.size - 1] } } } diff --git a/app/src/main/java/org/terst/listen/fingerprint/IntroOutroDetector.kt b/app/src/main/java/org/terst/listen/fingerprint/IntroOutroDetector.kt index 9050466..ebbe4a6 100644 --- a/app/src/main/java/org/terst/listen/fingerprint/IntroOutroDetector.kt +++ b/app/src/main/java/org/terst/listen/fingerprint/IntroOutroDetector.kt @@ -60,22 +60,65 @@ object IntroOutroDetector { private const val MIN_SCORE = 0.6 private const val CANDIDATE_STEP_DIVISOR = 4 + /** Matches [MidrollUpdater]'s own coarse factor, which was validated against real shows. */ + private const val DEFAULT_COARSE_FACTOR = 8 + private const val DEFAULT_FINE_CANDIDATES = 3 + + /** + * Below this many samples a coarse window stops carrying enough signal to rank positions by, + * so the search runs at full resolution instead. Also what keeps the unit tests' 300-sample + * clips on the path they were written against. + */ + private const val MIN_COARSE_WINDOW_SAMPLES = 512 + + /** + * What the candidate search is allowed to cost. Mirrors [MidrollUpdater.Tuning], including + * the reason it exists: the search's resolution is a performance choice, and the only honest + * way to show that is to make it a value a test can set. + * + * Nothing here is a detection threshold. `MIN_SCORE`, `CONFIRM_THRESHOLD` and the reference + * length are deliberately *not* reachable from the app or from tuning -- see CLAUDE.md. + */ + data class Tuning( + /** + * How much to shrink both clips before searching for a candidate position. 1 searches at + * full resolution, which is what this did before and is kept reachable so the fast path + * can be compared against it. + */ + val coarseFactor: Int = DEFAULT_COARSE_FACTOR, + /** + * How many coarse hits get verified at full resolution. More than one because + * decimation can reorder near-equal peaks, and the real intro losing a coarse tie to a + * spurious one would otherwise be unrecoverable. + */ + val fineCandidates: Int = DEFAULT_FINE_CANDIDATES, + /** + * How many independently-fetched episodes must agree before a candidate is trusted. + * + * Here with the cost knobs rather than as its own argument because [MidrollUpdater.Tuning] + * already carries the same value the same way -- but unlike them it is a *safety* + * threshold, and the reason it is three is in this class's own documentation. It is + * reachable for tests, not for the app; see CLAUDE.md. + */ + val confirmThreshold: Int = CONFIRM_THRESHOLD, + ) + fun check( state: FingerprintState, episodeId: String, clip: DoubleArray, referenceLengthSamples: Int, - confirmThreshold: Int = CONFIRM_THRESHOLD, + tuning: Tuning = Tuning(), ): FingerprintUpdate { if (episodeId == state.lastConfirmedEpisodeId || episodeId == state.pendingEpisodeId) { - return toUpdate(state, confirmThreshold) + return toUpdate(state, tuning.confirmThreshold) } val reference = state.referenceClip if (reference == null) { - return checkAgainstPending(state, episodeId, clip, referenceLengthSamples) + return checkAgainstPending(state, episodeId, clip, referenceLengthSamples, tuning) } - return checkAgainstReference(state, episodeId, clip, reference, confirmThreshold) + return checkAgainstReference(state, episodeId, clip, reference, tuning.confirmThreshold) } private fun checkAgainstPending( @@ -83,6 +126,7 @@ object IntroOutroDetector { episodeId: String, clip: DoubleArray, referenceLengthSamples: Int, + tuning: Tuning, ): FingerprintUpdate { val pending = state.pendingClip if (pending == null) { @@ -91,7 +135,7 @@ object IntroOutroDetector { ) } - val candidate = findCandidate(pending, clip, referenceLengthSamples) + val candidate = findCandidate(pending, clip, referenceLengthSamples, tuning) if (candidate == null) { // No shared segment between the only two episodes seen so far -- this one becomes // the new basis, same as if nothing had ever been seen. @@ -139,32 +183,96 @@ object IntroOutroDetector { } /** - * Slides a [referenceLengthSamples]-long window across [a] a quarter-window at a time, - * keeping whichever position matches best somewhere in [b] -- or null if nothing matches - * strongly enough to trust. + * Finds a [referenceLengthSamples]-long segment of [a] that also occurs in [b], or null if + * nothing matches strongly enough to trust. + * + * Coarse-to-fine, the composition [MidrollUpdater] already uses and for the same reason: the + * *position* of a shared segment can be found on heavily decimated audio for a fraction of + * the cost, while whether it is really a match is still decided at full resolution. Searched + * flat at full resolution this took 199 seconds per end on a desktop -- measured, in + * [IntroOutroDetectorScaleTest] -- which is how fingerprinting came to burn a WorkManager + * worker's entire ten-minute allowance and persist nothing. * - * A step equal to the full window would almost always straddle a real embedded segment - * rather than land on it exactly (any embed position not a multiple of the window length - * gets split across two candidate windows, each only partially the real signal, which is - * often too weak to clear [MIN_SCORE]). A quarter-window step costs more candidate checks - * but actually lands on the real segment. + * The step within the search is a quarter-window, not a whole one. A step equal to the full + * window would almost always straddle a real embedded segment rather than land on it (any + * embed position not a multiple of the window length gets split across two candidate + * windows, each only partially the real signal, which is often too weak to clear + * [MIN_SCORE]). */ - private fun findCandidate(a: DoubleArray, b: DoubleArray, referenceLengthSamples: Int): DoubleArray? { + private fun findCandidate( + a: DoubleArray, + b: DoubleArray, + referenceLengthSamples: Int, + tuning: Tuning, + ): DoubleArray? { val win = referenceLengthSamples.coerceAtMost(a.size).coerceAtMost(b.size) if (win <= 0) return null + + val factor = coarseFactorFor(win, tuning.coarseFactor) + val positions = if (factor == 1) { + searchPositions(a, b, win, tuning.fineCandidates) + } else { + searchPositions(Decimate.byAveraging(a, factor), Decimate.byAveraging(b, factor), win / factor, tuning.fineCandidates) + .map { it * factor } + } + + return bestVerifiedWindow(a, b, win, positions) + } + + /** + * Decimation is skipped rather than allowed to shrink the search window into noise: a + * window of a handful of samples correlates with anything, and the clips the unit tests use + * are three hundred samples long in total. + */ + private fun coarseFactorFor(win: Int, requested: Int): Int { + val factor = requested.coerceAtLeast(1) + if (factor == 1) return 1 + return if (win / factor >= MIN_COARSE_WINDOW_SAMPLES) factor else 1 + } + + /** + * The best-scoring window start positions in [a], highest first -- in whatever resolution + * [a] and [b] are handed in at. + * + * No score threshold here on purpose. This pass only ranks positions; at a coarse resolution + * its absolute scores are not the ones detection is allowed to decide on, so rejecting here + * would be rejecting on a number the fine pass is about to compute properly. + */ + private fun searchPositions(a: DoubleArray, b: DoubleArray, win: Int, keep: Int): List { + if (win <= 0 || win > a.size || win > b.size) return emptyList() val step = (win / CANDIDATE_STEP_DIVISOR).coerceAtLeast(1) + val target = AudioCorrelation.prepareTarget(b, win) - var bestScore = MIN_SCORE - var bestWindow: DoubleArray? = null + val scored = mutableListOf>() var start = 0 while (start + win <= a.size) { + AudioCorrelation.bestMatch(a.copyOfRange(start, start + win), target) + ?.let { scored += start to it.score } + start += step + } + return scored.sortedByDescending { it.second }.take(keep.coerceAtLeast(1)).map { it.first } + } + + /** + * The first candidate position whose full-resolution score clears [MIN_SCORE], as a window of + * [a] -- which is the clip the reference is kept from, exactly as before. + * + * This is where detection actually happens: every number the coarse pass produced is + * discarded and the decision is made on native-resolution audio. + */ + private fun bestVerifiedWindow(a: DoubleArray, b: DoubleArray, win: Int, positions: List): DoubleArray? { + val target = AudioCorrelation.prepareTarget(b, win) + var bestScore = MIN_SCORE + var bestWindow: DoubleArray? = null + + for (position in positions) { + val start = position.coerceIn(0, a.size - win) val window = a.copyOfRange(start, start + win) - val match = AudioCorrelation.bestMatch(window, b) + val match = AudioCorrelation.bestMatch(window, target) if (match != null && match.score > bestScore) { bestScore = match.score bestWindow = window } - start += step } return bestWindow } diff --git a/app/src/main/java/org/terst/listen/fingerprint/MediaCodecClipSource.kt b/app/src/main/java/org/terst/listen/fingerprint/MediaCodecClipSource.kt index 4daed7d..7294ba9 100644 --- a/app/src/main/java/org/terst/listen/fingerprint/MediaCodecClipSource.kt +++ b/app/src/main/java/org/terst/listen/fingerprint/MediaCodecClipSource.kt @@ -38,9 +38,12 @@ class MediaCodecClipSource : AudioClipSource { /** * Unlike [decodeHead]/[decodeTail], there is no fixed window: a midroll ad can be anywhere, - * so the whole episode is decoded. [EpisodeEntity.durationMs] sizes the buffer up front for - * the same reason [decodeToPcm] does for a short clip -- a boxed, growable collection for - * what can be hours of samples would be real, avoidable garbage on a phone. + * so the whole episode is decoded. [EpisodeEntity.durationMs] bounds how far to read rather + * than sizing an allocation -- see [MonoResampler] for why that distinction is the whole + * reason this path used to fail. + * + * How long an episode this is *worth* attempting is [MidrollUpdater]'s call, not this + * class's: the result is still held whole in memory by whoever asked for it. */ override suspend fun decodeFull(episode: EpisodeEntity): DecodedClip? { val path = episode.localPath ?: return null @@ -65,10 +68,9 @@ class MediaCodecClipSource : AudioClipSource { val channels = format.getInteger(MediaFormat.KEY_CHANNEL_COUNT) extractor.seekTo(startMs * MICROS_PER_MS, MediaExtractor.SEEK_TO_CLOSEST_SYNC) - val raw = decodeToPcm(extractor, format, inputRate, channels, clipSeconds) - val mono = downmix(raw, channels) - val resampled = resample(mono, inputRate, TARGET_SAMPLE_RATE) - return DecodedClip(resampled, TARGET_SAMPLE_RATE, startMs) + val resampler = MonoResampler(inputRate, channels, TARGET_SAMPLE_RATE) + decodeInto(extractor, format, resampler, channels, clipSeconds.toLong() * inputRate * channels) + return DecodedClip(resampler.finish(), TARGET_SAMPLE_RATE, startMs) } finally { extractor.release() } @@ -82,35 +84,36 @@ class MediaCodecClipSource : AudioClipSource { error("No audio track in this file") } - /** Interleaved PCM16 samples for up to [clipSeconds] of decoded audio. */ - private fun decodeToPcm( + /** + * Pumps the decoder into [resampler] until [maxSamples] interleaved samples have been read + * or the track ends. + * + * Nothing here holds the decoded audio: each output buffer is copied into a small reused + * scratch array and handed straight on, so the bound is a stop condition rather than an + * allocation. That is the whole difference from the version this replaces, which asked for + * 145MB of native-rate PCM to produce 6MB of 8kHz mono and died doing it. + */ + private fun decodeInto( extractor: MediaExtractor, format: MediaFormat, - inputRate: Int, + resampler: MonoResampler, channels: Int, - clipSeconds: Int, - ): ShortArray { + maxSamples: Long, + ) { val mime = format.getString(MediaFormat.KEY_MIME) ?: error("No MIME on the audio track") val codec = MediaCodec.createDecoderByType(mime) try { codec.configure(format, null, null, 0) codec.start() - // Sized to the clip length up front rather than grown: a boxed collection for - // several million samples would be real, avoidable garbage on a phone. - val target = ShortArray((clipSeconds.toLong() * inputRate * channels).toInt()) - var written = 0 + val pump = OutputPump(codec, resampler, channels, maxSamples) var inputDone = false - var outputDone = false - val info = MediaCodec.BufferInfo() - - while (!outputDone && written < target.size) { + while (!pump.finished) { if (!inputDone) { inputDone = feedInput(extractor, codec) } - written = drainOutput(codec, info, target, written) { outputDone = true } + pump.drain() } - return if (written == target.size) target else target.copyOf(written) } finally { codec.stop() codec.release() @@ -133,59 +136,54 @@ class MediaCodecClipSource : AudioClipSource { } } - private fun drainOutput( - codec: MediaCodec, - info: MediaCodec.BufferInfo, - target: ShortArray, - writtenSoFar: Int, - onEndOfStream: () -> Unit, - ): Int { - val outputIndex = codec.dequeueOutputBuffer(info, TIMEOUT_US) - if (outputIndex < 0) return writtenSoFar - - var written = writtenSoFar - if (info.size > 0) { - val output = codec.getOutputBuffer(outputIndex) - if (output != null) { - output.position(info.offset) - output.limit(info.offset + info.size) - val shorts = output.order(ByteOrder.LITTLE_ENDIAN).asShortBuffer() - while (shorts.hasRemaining() && written < target.size) { - target[written] = shorts.get() - written++ - } - } - } - codec.releaseOutputBuffer(outputIndex, false) - if (info.flags and MediaCodec.BUFFER_FLAG_END_OF_STREAM != 0) onEndOfStream() - return written - } + /** + * One decoder's output side, with the running count it needs. + * + * A class rather than a function taking all of it: the loop needs a sample count, an + * end-of-stream flag and a reusable buffer carried between calls, and threading those + * through arguments produced a seven-parameter function that said less than this does. + */ + private class OutputPump( + private val codec: MediaCodec, + private val resampler: MonoResampler, + channels: Int, + private val maxSamples: Long, + ) { + private val info = MediaCodec.BufferInfo() - private fun downmix(interleaved: ShortArray, channels: Int): DoubleArray { - if (channels <= 1) return DoubleArray(interleaved.size) { interleaved[it].toDouble() } - val frames = interleaved.size / channels - return DoubleArray(frames) { frame -> - var sum = 0.0 - for (c in 0 until channels) sum += interleaved[frame * channels + c] - sum / channels + // A multiple of the channel count, so copying never splits a frame unless the decoder's + // own buffer already did -- which MonoResampler carries across anyway. + private val scratch = ShortArray(SCRATCH_FRAMES * channels) + + private var samplesRead = 0L + private var endOfStream = false + + /** Whether there is no more to read: the track ended, or enough has been taken. */ + val finished: Boolean get() = endOfStream || samplesRead >= maxSamples + + /** Hands one output buffer to the resampler, if one is ready. */ + fun drain() { + val outputIndex = codec.dequeueOutputBuffer(info, TIMEOUT_US) + if (outputIndex < 0) return + + if (info.size > 0) { + codec.getOutputBuffer(outputIndex)?.let { copyOut(it) } + } + codec.releaseOutputBuffer(outputIndex, false) + if (info.flags and MediaCodec.BUFFER_FLAG_END_OF_STREAM != 0) endOfStream = true } - } - /** - * Linear-interpolation resample, not a proper anti-aliasing filter: matching only needs - * coarse spectral shape, not audiophile fidelity, and every source feed converges on the - * same [TARGET_SAMPLE_RATE] regardless of what it was encoded at. - */ - private fun resample(mono: DoubleArray, inputRate: Int, targetRate: Int): DoubleArray { - if (inputRate == targetRate || mono.isEmpty()) return mono - val ratio = targetRate.toDouble() / inputRate - val outLength = (mono.size * ratio).toInt() - return DoubleArray(outLength) { i -> - val sourcePosition = i / ratio - val index = sourcePosition.toInt().coerceIn(0, mono.size - 1) - val next = (index + 1).coerceAtMost(mono.size - 1) - val fraction = sourcePosition - index - mono[index] * (1 - fraction) + mono[next] * fraction + private fun copyOut(output: java.nio.ByteBuffer) { + output.position(info.offset) + output.limit(info.offset + info.size) + val shorts = output.order(ByteOrder.LITTLE_ENDIAN).asShortBuffer() + while (shorts.hasRemaining() && samplesRead < maxSamples) { + val room = minOf(maxSamples - samplesRead, scratch.size.toLong()).toInt() + val count = minOf(shorts.remaining(), room) + shorts.get(scratch, 0, count) + resampler.accept(scratch, 0, count) + samplesRead += count + } } } @@ -200,6 +198,9 @@ class MediaCodecClipSource : AudioClipSource { const val FULL_DECODE_MARGIN_SECONDS = 30 const val TARGET_SAMPLE_RATE = 8_000 const val TIMEOUT_US = 10_000L + + /** Frames copied out of one decoder buffer at a time; see [decodeInto]. */ + const val SCRATCH_FRAMES = 4_096 const val MICROS_PER_MS = 1_000L const val MS_PER_SECOND = 1_000L } diff --git a/app/src/main/java/org/terst/listen/fingerprint/MidrollUpdater.kt b/app/src/main/java/org/terst/listen/fingerprint/MidrollUpdater.kt index e5e757c..95dcd3e 100644 --- a/app/src/main/java/org/terst/listen/fingerprint/MidrollUpdater.kt +++ b/app/src/main/java/org/terst/listen/fingerprint/MidrollUpdater.kt @@ -7,6 +7,7 @@ import org.terst.listen.data.EpisodeMidrollEntity import org.terst.listen.data.MidrollDao import org.terst.listen.data.ShowMidrollEntity import org.terst.listen.data.SubscriptionDao +import org.terst.listen.data.playbackDurationMs /** * Runs [MidrollDetector] for every downloaded episode a show has not yet been checked against, @@ -37,6 +38,22 @@ class MidrollUpdater( val discoverySamples: Int = DEFAULT_DISCOVERY_SAMPLES, val maxCandidates: Int = DEFAULT_MAX_CANDIDATES, val confirmThreshold: Int = DEFAULT_CONFIRM_THRESHOLD, + /** + * The longest episode a full-body scan will attempt. + * + * A scan holds the whole episode decoded in memory, so an episode's length is also an + * allocation: an hour of 8kHz mono is 28.8 million doubles, 230MB, on a phone with no + * largeHeap. Asking for that threw OutOfMemoryError inside [AudioClipSource.decodeFull], + * where `runCatching` swallowed it -- and the episode was then marked checked forever, so + * midroll detection could never find anything on any episode of normal length and said + * nothing about why. + * + * An over-budget episode is skipped *before* anything is spent, and deliberately left + * unchecked, so that lifting this limit (by decoding candidate ranges on demand instead + * of the whole body at once) picks those episodes up rather than finding them written + * off. + */ + val maxDecodableMs: Long = DEFAULT_MAX_DECODABLE_MS, val newId: () -> String = { UUID.randomUUID().toString() }, val now: () -> Long = System::currentTimeMillis, ) @@ -52,7 +69,12 @@ class MidrollUpdater( val show = subscriptions.getById(subscriptionId) ?: return var pendingEpisodeId = show.midrollPendingEpisodeId - for (episode in midrolls.getUncheckedDownloaded(subscriptionId)) { + // Over-budget episodes are dropped here rather than skipped inside the loop: nothing is + // spent on them and they stay unchecked, so lifting the limit picks them up again -- + // see Tuning.maxDecodableMs. + val scannable = midrolls.getUncheckedDownloaded(subscriptionId).filterNot(::exceedsDecodeBudget) + + for (episode in scannable) { val decoded = clips.decodeFull(episode) if (decoded == null) { midrolls.setMidrollCheckedAtMs(episode.id, now()) @@ -84,6 +106,18 @@ class MidrollUpdater( } } + /** + * Whether this episode is longer than a whole-body decode can hold. + * + * An unknown length is not over budget: it is the case [AudioClipSource.decodeFull] already + * declines for want of a size to allocate, and routing it through here would change what + * happens to it. + */ + private fun exceedsDecodeBudget(episode: EpisodeEntity): Boolean { + val durationMs = episode.playbackDurationMs ?: return false + return durationMs > tuning.maxDecodableMs + } + private suspend fun discoverAgainstPending( subscriptionId: String, pendingEpisodeId: String, @@ -249,6 +283,14 @@ class MidrollUpdater( const val DEFAULT_DISCOVERY_SAMPLES = 20_000 // 20s at the coarse (post-decimation) rate const val DEFAULT_MAX_CANDIDATES = 4 const val DEFAULT_CONFIRM_THRESHOLD = 3 + + /** + * Twenty minutes, which at 8kHz mono is 9.6 million doubles -- about 77MB, the most a + * background worker can reasonably hold on a phone with no largeHeap. Not a detection + * threshold: it is the ceiling of the current in-memory decode, and it rises when that + * decode learns to fetch candidate ranges on demand. + */ + const val DEFAULT_MAX_DECODABLE_MS = 20L * 60 * 1000 const val SEEDED_CONFIRM_COUNT = 2 const val COARSE_MIN_SCORE = 0.7 const val FINE_MIN_SCORE = 0.6 diff --git a/app/src/main/java/org/terst/listen/fingerprint/MonoResampler.kt b/app/src/main/java/org/terst/listen/fingerprint/MonoResampler.kt new file mode 100644 index 0000000..a98d2ab --- /dev/null +++ b/app/src/main/java/org/terst/listen/fingerprint/MonoResampler.kt @@ -0,0 +1,134 @@ +package org.terst.listen.fingerprint + +/** + * Turns a decoder's interleaved PCM16 output into mono at a fixed rate, a buffer at a time. + * + * The reason this is streaming rather than three passes over three arrays: a full-episode scan's + * decode used to buffer every interleaved sample at the source's native rate, then every mono + * frame, and only then resample. For a 13-minute stereo 44.1kHz episode that is 145MB and 289MB + * live at once to produce 6MB of output -- on a phone with no largeHeap. It threw + * OutOfMemoryError inside a `runCatching` that swallowed it, which is why midroll detection + * never ran on anything and never said why. Here the peak allocation is the output. + * + * Pure, so it is the part of [MediaCodecClipSource] that can actually be tested; what is left + * there is MediaCodec plumbing and nothing else. + * + * The interpolation is deliberately unchanged -- naive linear, no anti-aliasing filter. It was + * measured at 0.9991 correlation against a proper ffmpeg/swresample decode of the same audio + * (`docs/detection-findings.md`), so it was never the weak link, and a rewrite that both moved + * the allocation and changed the arithmetic would be untraceable if detection got worse. + */ +class MonoResampler( + private val inputRate: Int, + private val channels: Int, + private val targetRate: Int, +) { + + private val ratio = targetRate.toDouble() / inputRate + + private var out = DoubleArray(INITIAL_CAPACITY) + private var outCount = 0 + + /** Mono frames of the buffer being consumed, reused across calls to keep churn down. */ + private var frames = DoubleArray(0) + + private var framesAccepted = 0 + + /** + * The last mono frame accepted, kept because an output sample interpolates between two + * source frames and those two can straddle a decoder buffer boundary. One frame is all that + * is ever needed: output positions only move forward. + */ + private var previousFrame = 0.0 + + /** A frame split across two decoder buffers. Nothing guarantees they arrive frame-aligned. */ + private val splitFrame = ShortArray(channels.coerceAtLeast(1)) + private var splitCount = 0 + + /** Consumes [count] interleaved samples from [interleaved] starting at [offset]. */ + fun accept(interleaved: ShortArray, offset: Int, count: Int) { + if (count <= 0 || channels <= 0) return + + val accepted = toMonoFrames(interleaved, offset, count) + if (accepted == 0) return + + emitWhatIsReadable(start = framesAccepted, available = accepted) + framesAccepted += accepted + previousFrame = frames[accepted - 1] + } + + /** + * The resampled mono audio. + * + * Length is `(frames * ratio)` truncated, exactly as the batch implementation computed it, so + * that the two cannot disagree about where the audio ends. + */ + fun finish(): DoubleArray { + if (framesAccepted == 0) return DoubleArray(0) + + // Whatever is left reads past the final frame, which clamps to it -- so every remaining + // output is that frame, whatever its fractional position would have been. + val total = (framesAccepted * ratio).toInt() + while (outCount < total) append(previousFrame) + + return out.copyOf(outCount) + } + + /** + * Averages [count] interleaved samples down into [frames], completing any frame the previous + * buffer left split and keeping any this one does. Returns how many whole frames resulted. + */ + private fun toMonoFrames(source: ShortArray, offset: Int, count: Int): Int { + val total = splitCount + count + val whole = total / channels + if (frames.size < whole) frames = DoubleArray(whole) + + // The split frame's samples come first: together with this buffer they are one stream. + fun sampleAt(index: Int): Short = + if (index < splitCount) splitFrame[index] else source[offset + index - splitCount] + + var read = 0 + for (frame in 0 until whole) { + var sum = 0.0 + repeat(channels) { sum += sampleAt(read++) } + frames[frame] = sum / channels + } + + // Safe to overwrite while reading: with a whole frame produced, `read` is already past + // everything held in splitFrame; with none, this copies those samples onto themselves. + val leftover = total - whole * channels + for (i in 0 until leftover) splitFrame[i] = sampleAt(read + i) + splitCount = leftover + + return whole + } + + /** + * Emits every output sample whose two source frames are both readable now -- the newest + * buffer's frames, plus [previousFrame] sitting immediately before them. + */ + private fun emitWhatIsReadable(start: Int, available: Int) { + val lastReadable = start + available - 1 + while (true) { + val sourcePosition = outCount / ratio + val index = sourcePosition.toInt() + if (index + 1 > lastReadable) return + + // Output positions advance monotonically and everything readable from earlier + // buffers was already emitted, so `index` is never further back than previousFrame. + val before = if (index < start) previousFrame else frames[index - start] + val after = if (index + 1 < start) previousFrame else frames[index + 1 - start] + val fraction = sourcePosition - index + append(before * (1 - fraction) + after * fraction) + } + } + + private fun append(value: Double) { + if (outCount == out.size) out = out.copyOf(out.size * 2) + out[outCount++] = value + } + + private companion object { + const val INITIAL_CAPACITY = 8_192 + } +} diff --git a/app/src/main/java/org/terst/listen/fingerprint/SkipSummary.kt b/app/src/main/java/org/terst/listen/fingerprint/SkipSummary.kt index fedd3e4..63b3ec5 100644 --- a/app/src/main/java/org/terst/listen/fingerprint/SkipSummary.kt +++ b/app/src/main/java/org/terst/listen/fingerprint/SkipSummary.kt @@ -16,6 +16,18 @@ data class EpisodeSkips( val outro: String, val breaks: List, val insertedAds: String?, + /** What the feed says the episode is, null if it does not say. */ + val declaredLength: String? = null, + /** What the player measured the file to be, null until it has opened it. */ + val measuredLength: String? = null, + /** + * How much of the episode the detected breaks add up to, null when none are detected. + * + * The point of showing it next to [insertedAds]: the length gap says how much advertising is + * in the file without any audio analysis, so these two should roughly agree. Far short means + * the scan is missing breaks; far over means it is matching programme. + */ + val breaksTotal: String? = null, ) /** @@ -41,6 +53,28 @@ object SkipSummary { private const val SECONDS_PER_MINUTE = 60 private const val MINUTES_PER_HOUR = 60 + /** Where one detected break sits in an episode, as fractions of its length. */ + data class BreakMarker(val start: Float, val end: Float) + + /** + * The detected breaks as positions on a 0..1 timeline, for the episode screen's scrubber. + * + * Here rather than in the composable because a marker drawn in the wrong place looks + * plausible in a screenshot and is obvious in a test -- and because a break can run past a + * duration that was measured on a different fetch of the same episode, dynamic ad insertion + * being per request. Clamped rather than dropped: the break is real, the length is the + * doubtful number. + */ + fun breakMarkers(ranges: List, durationMs: Long?): List { + if (durationMs == null || durationMs <= 0) return emptyList() + return ranges.sortedBy { it.startMs }.map { + BreakMarker( + start = (it.startMs.toFloat() / durationMs).coerceIn(0f, 1f), + end = (it.endMs.toFloat() / durationMs).coerceIn(0f, 1f), + ) + } + } + /** One end of a show's episodes -- its intro or its outro. */ fun candidateState(state: ShowFingerprintEntity?, threshold: Int): String { // No reference clip means no candidate: either nothing has been processed, or a single @@ -98,6 +132,11 @@ object SkipSummary { val breaks = ranges(ranges) return EpisodeSkips( insertedAds = episode.insertedAdMs?.let { clock(it) }, + declaredLength = episode.durationMs?.let { clock(it) }, + measuredLength = episode.actualDurationMs?.let { clock(it) }, + breaksTotal = ranges.sumOf { (it.endMs - it.startMs).coerceAtLeast(0) } + .takeIf { ranges.isNotEmpty() } + ?.let { clock(it) }, intro = offset(episode.detectedIntroMs, show?.skipIntroMs ?: 0), outro = offset(episode.detectedOutroMs, show?.skipOutroMs ?: 0), breaks = when { diff --git a/app/src/main/java/org/terst/listen/playback/PlaybackService.kt b/app/src/main/java/org/terst/listen/playback/PlaybackService.kt index 39af65d..3a10e4e 100644 --- a/app/src/main/java/org/terst/listen/playback/PlaybackService.kt +++ b/app/src/main/java/org/terst/listen/playback/PlaybackService.kt @@ -38,6 +38,12 @@ class PlaybackService : MediaLibraryService() { private var advancer: PlaybackAdvancer? = null private val progress = PlaybackProgress() + /** + * Times each start against the episode's length, for the open question about the pause + * before playback -- see [PrepareTrace]. Cheap enough to leave in: one line per episode. + */ + private val prepareTrace = PrepareTrace() + /** What the ticker runs against, refreshed whenever the playing item changes. */ private var context = PlayingContext() @@ -110,7 +116,18 @@ class PlaybackService : MediaLibraryService() { * component that survives backgrounding is the one that has to own this. */ private val completionListener = object : Player.Listener { + override fun onIsPlayingChanged(isPlaying: Boolean) { + if (!isPlaying) return + prepareTrace.mark(PrepareTrace.Stage.PLAYING) + prepareTrace.summary()?.let { android.util.Log.i(TAG, it) } + } + override fun onPlaybackStateChanged(playbackState: Int) { + if (playbackState == Player.STATE_READY) { + prepareTrace.length(player?.duration?.takeIf { it > 0 }) + prepareTrace.mark(PrepareTrace.Stage.READY) + prepareTrace.summary()?.let { android.util.Log.i(TAG, it) } + } if (playbackState != Player.STATE_ENDED) return // Read before anything else runs: starting the next episode replaces the media item, // so the id is gone by the time this returns. @@ -119,6 +136,13 @@ class PlaybackService : MediaLibraryService() { } override fun onMediaItemTransition(mediaItem: MediaItem?, reason: Int) { + // Where the prepare clock starts. This is the one hook both play paths reach: the + // service's own queue advance, and a tap in the UI, which sets the item through a + // MediaController and never calls this service's play(). + mediaItem?.mediaId?.let { id -> + val uri = mediaItem.localConfiguration?.uri?.scheme + prepareTrace.start(id, durationMs = null, local = uri == null || uri == "file") + } // The cached show and chapters belong to whatever is playing; refresh them whenever // that changes, including when something else in the app starts an episode. loadContextFor(mediaItem?.mediaId) @@ -241,6 +265,7 @@ class PlaybackService : MediaLibraryService() { } private companion object { + const val TAG = "ListenPlayback" const val POSITION_TICK_MS = 2_000L const val SEEK_BACK_MS = 15_000L const val SEEK_FORWARD_MS = 25_000L diff --git a/app/src/main/java/org/terst/listen/playback/PrepareTrace.kt b/app/src/main/java/org/terst/listen/playback/PrepareTrace.kt new file mode 100644 index 0000000..f565754 --- /dev/null +++ b/app/src/main/java/org/terst/listen/playback/PrepareTrace.kt @@ -0,0 +1,89 @@ +package org.terst.listen.playback + +/** + * Times how long starting an episode takes, against how long the episode is. + * + * Exists for a specific open question: playback takes a noticeable moment to start, and the + * delay looks proportional to the episode's length. Nothing in this app's play path scales with + * length -- it reads a few rows and calls `setMediaItem`/`prepare` -- so the delay is either + * inside Media3's preparation or it is the CPU being busy with something else. From outside + * those look identical, and picking between them by argument is how the wrong thing gets fixed. + * + * One line per start, carrying both numbers, settles it from a log: + * + * ``` + * prepare ep=abc123 len=1774s src=local ready=812ms playing=903ms + * ``` + * + * Deliberately a value rather than logging directly, so the format is pinned by + * [PrepareTraceTest] -- a line that quietly stopped reporting the length would make the whole + * measurement worthless while still looking like it worked. + */ +class PrepareTrace(private val now: () -> Long = System::currentTimeMillis) { + + /** The points worth timing between asking for an episode and hearing it. */ + enum class Stage(internal val label: String) { + /** Media3 has the media open and buffered enough to play. */ + READY("ready"), + + /** Audio is actually coming out. */ + PLAYING("playing"), + } + + private var episodeId: String? = null + private var durationMs: Long? = null + private var local = true + private var startedAt = 0L + private val reached = linkedMapOf() + + /** Called as the media item is handed to the player. */ + fun start(episodeId: String, durationMs: Long?, local: Boolean) { + this.episodeId = episodeId + this.durationMs = durationMs + this.local = local + startedAt = now() + reached.clear() + } + + /** + * Supplies the episode's length once the player knows it. + * + * The clock has to start when the media item is set -- the only point both play paths pass + * through, since a tap in the UI reaches the player through a MediaController and never + * calls the service's own `play` -- and a MediaItem carries no duration. What the player + * reports once it has opened the file is the better number anyway: the real length of the + * file rather than the feed's claim, which on a show using dynamic ad insertion is minutes + * short. + * + * A null is ignored rather than stored: Media3 reports no duration until it has one, and + * letting that clear a known length would lose it. + */ + fun length(durationMs: Long?) { + if (episodeId == null || durationMs == null) return + this.durationMs = durationMs + } + + /** + * Records when [stage] was first reached. + * + * First, not last: Media3 reports READY again after a rebuffer, and letting that overwrite + * the original would replace the delay being measured with a small number. + */ + fun mark(stage: Stage) { + if (episodeId == null || stage in reached) return + reached[stage] = now() - startedAt + } + + /** The line to log, or null if no start has been recorded yet. */ + fun summary(): String? { + val id = episodeId ?: return null + val length = durationMs?.let { "${it / MS_PER_SECOND}s" } ?: "?" + val source = if (local) "local" else "stream" + val stages = reached.entries.joinToString("") { " ${it.key.label}=${it.value}ms" } + return "prepare ep=$id len=$length src=$source$stages" + } + + private companion object { + const val MS_PER_SECOND = 1_000L + } +} diff --git a/app/src/main/java/org/terst/listen/ui/EpisodeDetailActions.kt b/app/src/main/java/org/terst/listen/ui/EpisodeDetailActions.kt index 5ef0ff1..009c8c0 100644 --- a/app/src/main/java/org/terst/listen/ui/EpisodeDetailActions.kt +++ b/app/src/main/java/org/terst/listen/ui/EpisodeDetailActions.kt @@ -43,4 +43,12 @@ data class EpisodeDetailActions( val download: () -> Unit, val togglePlayed: () -> Unit, val markOlderPlayed: () -> Unit, + /** Play/pause when this episode is the one playing; starts it when it is not. */ + val togglePlayPause: () -> Unit = {}, + /** + * Where the scrubber was dragged to. Seeks the player when this episode is the one playing, + * and otherwise moves where Play will start from -- the screen decides which, because only + * it knows whether the drag is fighting a live position tick. + */ + val seekTo: (Long) -> Unit = {}, ) diff --git a/app/src/main/java/org/terst/listen/ui/EpisodeScreen.kt b/app/src/main/java/org/terst/listen/ui/EpisodeScreen.kt index de828e2..649d24f 100644 --- a/app/src/main/java/org/terst/listen/ui/EpisodeScreen.kt +++ b/app/src/main/java/org/terst/listen/ui/EpisodeScreen.kt @@ -1,12 +1,15 @@ package org.terst.listen.ui +import androidx.compose.foundation.Canvas import androidx.compose.foundation.background import androidx.compose.foundation.layout.Arrangement +import androidx.compose.foundation.layout.Box import androidx.compose.foundation.layout.Column import androidx.compose.foundation.layout.FlowRow import androidx.compose.foundation.layout.Row import androidx.compose.foundation.layout.fillMaxSize import androidx.compose.foundation.layout.fillMaxWidth +import androidx.compose.foundation.layout.height import androidx.compose.foundation.layout.padding import androidx.compose.foundation.layout.size import androidx.compose.foundation.rememberScrollState @@ -14,6 +17,8 @@ import androidx.compose.foundation.shape.RoundedCornerShape import androidx.compose.foundation.verticalScroll import androidx.compose.material.icons.Icons import androidx.compose.material.icons.automirrored.filled.ArrowBack +import androidx.compose.material.icons.filled.Pause +import androidx.compose.material.icons.filled.PlayArrow import androidx.compose.material3.Button import androidx.compose.material3.ExperimentalMaterial3Api import androidx.compose.material3.Icon @@ -21,26 +26,33 @@ import androidx.compose.material3.IconButton import androidx.compose.material3.MaterialTheme import androidx.compose.material3.OutlinedButton import androidx.compose.material3.Scaffold +import androidx.compose.material3.Slider import androidx.compose.material3.Text import androidx.compose.material3.TopAppBar import androidx.compose.runtime.Composable import androidx.compose.runtime.LaunchedEffect import androidx.compose.runtime.collectAsState import androidx.compose.runtime.getValue +import androidx.compose.runtime.mutableFloatStateOf import androidx.compose.runtime.mutableStateOf import androidx.compose.runtime.remember import androidx.compose.runtime.setValue +import androidx.compose.ui.Alignment import androidx.compose.ui.Modifier import androidx.compose.ui.draw.clip +import androidx.compose.ui.geometry.Offset +import androidx.compose.ui.geometry.Size import androidx.compose.ui.text.style.TextOverflow import androidx.compose.ui.unit.dp import coil3.compose.AsyncImage import org.terst.listen.data.EpisodeEntity import org.terst.listen.data.EpisodeMidrollEntity import org.terst.listen.data.SubscriptionEntity +import org.terst.listen.data.playbackDurationMs import org.terst.listen.feed.WatchLink import org.terst.listen.fingerprint.EpisodeSkips import org.terst.listen.fingerprint.SkipSummary +import org.terst.listen.playback.NowPlaying import org.terst.listen.playback.effectiveIntroMs import org.terst.listen.playback.effectiveOutroMs @@ -67,32 +79,29 @@ fun EpisodeScreen( } val rules by vm.rules.collectAsState() val shows by vm.subscriptions.collectAsState() + val nowPlaying by player.nowPlaying.collectAsState() val current = episode Scaffold( - topBar = { - TopAppBar( - title = { Text(current?.title ?: "Episode", maxLines = 1, overflow = TextOverflow.Ellipsis) }, - navigationIcon = { - IconButton(onClick = nav.back) { - Icon(Icons.AutoMirrored.Filled.ArrowBack, contentDescription = "Back") - } - }, - ) - }, + topBar = { EpisodeTopBar(current?.title, nav.back) }, bottomBar = { PlayerBar(player, nav.openPlayer, nav.openQueue) }, ) { padding -> if (current == null) { Text("Episode not found", Modifier.padding(padding).padding(24.dp)) return@Scaffold } + // Whether the transport controls drive the player or just move a stored position. An + // episode can be open on this screen while something else is playing, and a scrubber + // that silently drove the wrong episode would be worse than one that did nothing. + val isPlayingThis = nowPlaying.episodeId == current.id EpisodeDetail( episode = current, - ruleName = rules.firstOrNull { rule -> rule.id == current.appliedRuleId }?.name, - skips = SkipSummary.episode( - current, - shows.firstOrNull { it.id == current.subscriptionId }, - ranges, + detail = episodeDetailState( + episode = current, + show = shows.firstOrNull { it.id == current.subscriptionId }, + ruleName = rules.firstOrNull { rule -> rule.id == current.appliedRuleId }?.name, + ranges = ranges, + nowPlaying = nowPlaying, ), modifier = Modifier.padding(padding), actions = EpisodeDetailActions( @@ -104,6 +113,19 @@ fun EpisodeScreen( episode = current.copy(playedAtMs = if (current.playedAtMs == null) 1L else null) }, markOlderPlayed = { vm.markPlayedUpTo(current) }, + togglePlayPause = { + if (isPlayingThis) player.togglePlayPause() else player.play(current) + }, + seekTo = { positionMs -> + // Seeking the player only works for the item it has loaded; for any other + // episode the drag is a statement about where Play should begin. + if (isPlayingThis) { + player.seekTo(positionMs) + } else { + vm.setPosition(current.id, positionMs) + episode = current.copy(positionMs = positionMs) + } + }, ), ) } @@ -112,8 +134,7 @@ fun EpisodeScreen( @Composable private fun EpisodeDetail( episode: EpisodeEntity, - ruleName: String?, - skips: EpisodeSkips, + detail: EpisodeDetailState, modifier: Modifier, actions: EpisodeDetailActions, ) { @@ -136,6 +157,8 @@ private fun EpisodeDetail( } } + EpisodeScrubber(detail.playback, actions) + FlowRow( horizontalArrangement = Arrangement.spacedBy(8.dp), verticalArrangement = Arrangement.spacedBy(8.dp), @@ -155,9 +178,9 @@ private fun EpisodeDetail( Text("Mark this and older as played") } - RuleAttribution(episode, ruleName) + RuleAttribution(episode, detail.ruleName) - SkipReadout(skips) + SkipReadout(detail.skips) episode.description?.let { Text(stripHtml(it), style = MaterialTheme.typography.bodyMedium) @@ -165,6 +188,133 @@ private fun EpisodeDetail( } } +@OptIn(ExperimentalMaterial3Api::class) +@Composable +private fun EpisodeTopBar(title: String?, onBack: () -> Unit) { + TopAppBar( + title = { Text(title ?: "Episode", maxLines = 1, overflow = TextOverflow.Ellipsis) }, + navigationIcon = { + IconButton(onClick = onBack) { + Icon(Icons.AutoMirrored.Filled.ArrowBack, contentDescription = "Back") + } + }, + ) +} + +/** Everything the detail body renders but does not change. */ +data class EpisodeDetailState( + val ruleName: String?, + val skips: EpisodeSkips, + val playback: EpisodePlayback, +) + +/** + * Gathers what the detail body shows. + * + * Out of the composable because assembling it inline pushed `EpisodeScreen` past the length + * limit, and because the one decision in here is worth seeing plainly: a position and duration + * come from the player when this is the episode playing, and from the stored row when it is not. + */ +private fun episodeDetailState( + episode: EpisodeEntity, + show: SubscriptionEntity?, + ruleName: String?, + ranges: List, + nowPlaying: NowPlaying, +): EpisodeDetailState { + // Whether the transport controls drive the player or just describe a stored position. + val isPlayingThis = nowPlaying.episodeId == episode.id + val durationMs = if (isPlayingThis) nowPlaying.durationMs else episode.playbackDurationMs + return EpisodeDetailState( + ruleName = ruleName, + skips = SkipSummary.episode(episode, show, ranges), + playback = EpisodePlayback( + positionMs = if (isPlayingThis) nowPlaying.positionMs else episode.positionMs, + durationMs = durationMs, + isPlaying = isPlayingThis && nowPlaying.isPlaying, + breaks = SkipSummary.breakMarkers(ranges, durationMs), + ), + ) +} + +/** What the episode screen's transport controls act on. */ +data class EpisodePlayback( + val positionMs: Long, + val durationMs: Long?, + val isPlaying: Boolean, + /** Detected ad breaks as fractions of the episode -- see [SkipSummary.breakMarkers]. */ + val breaks: List, +) + +/** + * This episode's position, with the detected ad breaks marked on it. + * + * Separate from the player screen's scrubber on purpose: that one always drives whatever is + * playing, and this one has to work for an episode that is merely open -- where a drag sets + * where Play will begin rather than seeking anything. The drag rule is the same, though: a + * finger should not fight the live position tick, so the local value only tracks the drag and + * the seek fires once on release. + */ +@Composable +private fun EpisodeScrubber(playback: EpisodePlayback, actions: EpisodeDetailActions) { + val duration = playback.durationMs?.takeIf { it > 0 } ?: 0L + var dragValue by remember { mutableFloatStateOf(-1f) } + val shown = if (dragValue >= 0f) dragValue else playback.positionMs.toFloat() + + Row(verticalAlignment = Alignment.CenterVertically) { + IconButton(onClick = actions.togglePlayPause) { + Icon( + if (playback.isPlaying) Icons.Default.Pause else Icons.Default.PlayArrow, + contentDescription = if (playback.isPlaying) "Pause" else "Play", + ) + } + Column(Modifier.weight(1f)) { + Box { + // Behind the slider, so the track reads as the episode and the marks read as + // parts of it. Drawn at the track's own inset, or they would not line up with + // the thumb positions they are describing. + BreakMarks(playback.breaks, Modifier.align(Alignment.Center)) + Slider( + value = shown.coerceIn(0f, duration.toFloat().coerceAtLeast(0f)), + onValueChange = { dragValue = it }, + onValueChangeFinished = { + actions.seekTo(dragValue.toLong()) + dragValue = -1f + }, + valueRange = 0f..duration.toFloat().coerceAtLeast(1f), + enabled = duration > 0, + ) + } + Row(Modifier.fillMaxWidth(), horizontalArrangement = Arrangement.SpaceBetween) { + Text(formatClock(shown.toLong()), style = MaterialTheme.typography.bodySmall) + Text(formatClock(duration), style = MaterialTheme.typography.bodySmall) + } + } + } +} + +/** The detected ad breaks as bands across the track. */ +@Composable +private fun BreakMarks(breaks: List, modifier: Modifier) { + if (breaks.isEmpty()) return + val colour = MaterialTheme.colorScheme.tertiary + Canvas(modifier.fillMaxWidth().height(BREAK_MARK_HEIGHT)) { + // Inset by the thumb's radius at each end: the slider's track is laid out inside it, so + // marks drawn edge to edge would sit a thumb-width off the positions they describe. + val inset = THUMB_RADIUS_PX + val usable = (size.width - inset * 2).coerceAtLeast(0f) + breaks.forEach { mark -> + val left = inset + usable * mark.start + val right = inset + usable * mark.end + drawRect( + color = colour, + topLeft = Offset(left, 0f), + size = Size((right - left).coerceAtLeast(MIN_BREAK_MARK_PX), size.height), + ) + } + } +} + /** * What is actually being skipped in this episode, and where the numbers came from. * @@ -182,12 +332,20 @@ private fun SkipReadout(skips: EpisodeSkips) { Text("Skips", style = MaterialTheme.typography.titleSmall) // Free, and a check on the detector: whatever it finds should eventually add up to // about this much. + // The three numbers only mean anything together: the feed's length against the file's + // says how much advertising is in it, and what the detector found says how much of that + // it has actually accounted for. Short means breaks are being missed; over means + // programme is being matched. + skips.declaredLength?.let { declared -> + ReadoutRow("Length", skips.measuredLength?.let { "$declared declared, $it measured" } ?: declared) + } skips.insertedAds?.let { ReadoutRow("Ads inserted", "~$it") } ReadoutRow("Intro", skips.intro) ReadoutRow("Outro", skips.outro) skips.breaks.forEachIndexed { index, line -> ReadoutRow(if (index == 0) "Ad breaks" else "", line) } + skips.breaksTotal?.let { ReadoutRow("Breaks found", it) } } } @@ -223,3 +381,12 @@ private fun RuleAttribution(episode: EpisodeEntity, ruleName: String?) { val label = if (ruleName != null) "Handled by \"$ruleName\" — $reason" else "Handled by a rule — $reason" Text(label, style = MaterialTheme.typography.bodySmall) } + +/** Thin enough to read as an annotation on the track rather than a second control. */ +private val BREAK_MARK_HEIGHT = 4.dp + +/** Material's slider thumb radius, which the track is inset by at both ends. */ +private const val THUMB_RADIUS_PX = 20f + +/** A break shorter than this would otherwise draw as nothing at all. */ +private const val MIN_BREAK_MARK_PX = 2f diff --git a/app/src/main/java/org/terst/listen/ui/ListenViewModel.kt b/app/src/main/java/org/terst/listen/ui/ListenViewModel.kt index e278f78..d03c7a5 100644 --- a/app/src/main/java/org/terst/listen/ui/ListenViewModel.kt +++ b/app/src/main/java/org/terst/listen/ui/ListenViewModel.kt @@ -84,6 +84,18 @@ class ListenViewModel(app: Application) : AndroidViewModel(app) { /** The ad breaks detection has confirmed in one episode, for the episode screen's readout. */ suspend fun midrollRanges(episodeId: String) = graph.midrolls.getRanges(episodeId) + /** + * Moves where an episode will start from, for the episode screen's scrubber. + * + * Only for an episode that is *not* the one playing -- that one is dragged through the + * player, so the position comes back from Media3 rather than being written underneath it. + * Through [org.terst.listen.data.PlaybackStateDao] like every other position write, because + * this is the one piece of data in the app that cannot be reconstructed from anywhere. + */ + fun setPosition(episodeId: String, positionMs: Long) { + viewModelScope.launch { graph.playbackState.updatePosition(episodeId, positionMs.coerceAtLeast(0)) } + } + /** * A show's episodes as it displays them. * diff --git a/app/src/main/java/org/terst/listen/ui/MainActivity.kt b/app/src/main/java/org/terst/listen/ui/MainActivity.kt index fedc34d..a4cc048 100644 --- a/app/src/main/java/org/terst/listen/ui/MainActivity.kt +++ b/app/src/main/java/org/terst/listen/ui/MainActivity.kt @@ -117,9 +117,12 @@ private fun ListenApp( QueueScreen( vm = viewModel, player = player, - onOpenPlayer = { nav.navigate("player") }, - onOpenQueue = {}, - onBack = { nav.popBackStack() }, + nav = QueueNav( + openEpisode = { nav.navigate("episode/$it") }, + openPlayer = { nav.navigate("player") }, + openQueue = {}, + back = { nav.popBackStack() }, + ), ) } composable("subscription/{id}") { entry -> diff --git a/app/src/main/java/org/terst/listen/ui/QueueScreen.kt b/app/src/main/java/org/terst/listen/ui/QueueScreen.kt index 75fbaca..c53fd5b 100644 --- a/app/src/main/java/org/terst/listen/ui/QueueScreen.kt +++ b/app/src/main/java/org/terst/listen/ui/QueueScreen.kt @@ -1,6 +1,7 @@ package org.terst.listen.ui import androidx.compose.foundation.background +import androidx.compose.foundation.clickable import androidx.compose.foundation.layout.Column import androidx.compose.foundation.layout.Row import androidx.compose.foundation.layout.fillMaxSize @@ -45,9 +46,7 @@ import sh.calvin.reorderable.rememberReorderableLazyListState @OptIn(ExperimentalMaterial3Api::class) @Composable -fun QueueScreen(vm: ListenViewModel, player: PlayerViewModel, - onOpenPlayer: () -> Unit, - onOpenQueue: () -> Unit, onBack: () -> Unit) { +fun QueueScreen(vm: ListenViewModel, player: PlayerViewModel, nav: QueueNav) { val queue by vm.queue.collectAsState() val nowPlaying by player.nowPlaying.collectAsState() val subscriptions by vm.subscriptions.collectAsState() @@ -70,13 +69,13 @@ fun QueueScreen(vm: ListenViewModel, player: PlayerViewModel, TopAppBar( title = { Text("Up Next") }, navigationIcon = { - IconButton(onClick = onBack) { + IconButton(onClick = nav.back) { Icon(Icons.AutoMirrored.Filled.ArrowBack, contentDescription = "Back") } }, ) }, - bottomBar = { PlayerBar(player, onOpenPlayer, onOpenQueue) }, + bottomBar = { PlayerBar(player, nav.openPlayer, nav.openQueue) }, ) { padding -> LazyColumn(state = lazyListState, modifier = Modifier.padding(padding).fillMaxSize()) { items(localOrder, key = { it.id }) { episode -> @@ -84,9 +83,12 @@ fun QueueScreen(vm: ListenViewModel, player: PlayerViewModel, QueueRow( episode = episode, artworkUrl = Artwork.preferredUrl(episode.imageUrl, subscriptionImages[episode.subscriptionId]), - onPlay = { player.play(episode) }, - onRemove = { vm.removeFromQueue(episode.id) }, - onDragStopped = { vm.reorderQueue(localOrder.map { it.id }) }, + actions = QueueRowActions( + play = { player.play(episode) }, + remove = { vm.removeFromQueue(episode.id) }, + dragStopped = { vm.reorderQueue(localOrder.map { it.id }) }, + openDetails = { nav.openEpisode(episode.id) }, + ), ) } HorizontalDivider() @@ -99,16 +101,17 @@ fun QueueScreen(vm: ListenViewModel, player: PlayerViewModel, private fun ReorderableCollectionItemScope.QueueRow( episode: EpisodeEntity, artworkUrl: String?, - onPlay: () -> Unit, - onRemove: () -> Unit, - onDragStopped: () -> Unit, + actions: QueueRowActions, ) { + // The row opens the episode, the same as the show screen's rows do. It used to do nothing, + // so where a tap landed decided whether anything happened -- the drag handle, play and + // remove keep their own handlers and sit above this. Row( - Modifier.fillMaxWidth().padding(horizontal = 16.dp, vertical = 8.dp), + Modifier.fillMaxWidth().clickable(onClick = actions.openDetails).padding(horizontal = 16.dp, vertical = 8.dp), verticalAlignment = Alignment.CenterVertically, ) { IconButton( - modifier = Modifier.draggableHandle(onDragStopped = onDragStopped), + modifier = Modifier.draggableHandle(onDragStopped = actions.dragStopped), onClick = {}, ) { Icon(Icons.Default.DragHandle, contentDescription = "Reorder") @@ -125,11 +128,27 @@ private fun ReorderableCollectionItemScope.QueueRow( Text(episode.title, maxLines = 2, overflow = TextOverflow.Ellipsis) Text(episode.progressLabel(), style = MaterialTheme.typography.bodySmall) } - IconButton(onClick = onPlay) { + IconButton(onClick = actions.play) { Icon(Icons.Default.PlayArrow, contentDescription = "Play") } - IconButton(onClick = onRemove) { + IconButton(onClick = actions.remove) { Icon(Icons.Default.RemoveCircleOutline, contentDescription = "Remove from queue") } } } + +/** Where the queue screen navigates to, bundled like [LibraryNav] and [SubscriptionNav]. */ +data class QueueNav( + val openEpisode: (String) -> Unit, + val openPlayer: () -> Unit, + val openQueue: () -> Unit, + val back: () -> Unit, +) + +/** One queue row's actions, bundled for the same reason [EpisodeActions] is. */ +data class QueueRowActions( + val play: () -> Unit, + val remove: () -> Unit, + val dragStopped: () -> Unit, + val openDetails: () -> Unit, +) diff --git a/app/src/test/java/org/terst/listen/fingerprint/AudioCorrelationTest.kt b/app/src/test/java/org/terst/listen/fingerprint/AudioCorrelationTest.kt index 6274e99..0d078cd 100644 --- a/app/src/test/java/org/terst/listen/fingerprint/AudioCorrelationTest.kt +++ b/app/src/test/java/org/terst/listen/fingerprint/AudioCorrelationTest.kt @@ -157,4 +157,41 @@ class AudioCorrelationTest { fun `silence in the query has no meaningful correlation with anything`() { assertNull(AudioCorrelation.bestMatch(DoubleArray(40), targetWithMatch)) } + + /** + * The target's transform is the expensive half of a correlation, and inside a window search + * the target never changes -- see [IntroOutroDetector]'s candidate search, which correlates + * every window of one clip against the *same* other clip. Preparing it once has to give + * bit-for-bit what the one-shot call gives, or the search would quietly change its answers + * as a side effect of going faster. + */ + @Test + fun `a prepared target gives the same match as a one-shot call`() { + val oneShot = AudioCorrelation.bestMatch(sting, targetWithMatch)!! + val reused = AudioCorrelation.bestMatch(sting, AudioCorrelation.prepareTarget(targetWithMatch, sting.size))!! + + assertEquals(oneShot.position, reused.position) + assertEquals(oneShot.score, reused.score, 1e-12) + } + + /** The whole point: one preparation, many queries, each scoring as it would alone. */ + @Test + fun `a prepared target serves several queries, each scoring as it would alone`() { + val prepared = AudioCorrelation.prepareTarget(targetWithMatch, sting.size) + + for (start in listOf(0, 40, 120, 200)) { + val query = targetWithMatch.copyOfRange(start, start + sting.size) + val alone = AudioCorrelation.bestMatch(query, targetWithMatch)!! + val viaPrepared = AudioCorrelation.bestMatch(query, prepared)!! + assertEquals("position at $start", alone.position, viaPrepared.position) + assertEquals("score at $start", alone.score, viaPrepared.score, 1e-12) + } + } + + /** A prepared target is sized for one query length; anything else is a programming error. */ + @Test + fun `a prepared target rejects a query of the wrong length`() { + val prepared = AudioCorrelation.prepareTarget(targetWithMatch, sting.size) + assertNull(AudioCorrelation.bestMatch(DoubleArray(sting.size + 1), prepared)) + } } diff --git a/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorScaleTest.kt b/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorScaleTest.kt new file mode 100644 index 0000000..a8fcaa5 --- /dev/null +++ b/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorScaleTest.kt @@ -0,0 +1,171 @@ +package org.terst.listen.fingerprint + +import kotlin.math.sin +import kotlin.random.Random +import kotlin.system.measureTimeMillis +import org.junit.Assert.assertArrayEquals +import org.junit.Assert.assertEquals +import org.junit.Assert.assertTrue +import org.junit.Test + +/** + * The guard whose absence let the detector ship unusable. + * + * [IntroOutroDetectorTest] proves the state machine on 300-sample clips. Production hands it + * 1,920,000 -- a 240-second window at 8kHz, 6,400 times larger -- and nothing anywhere measured + * what that costs. It cost minutes per episode: the candidate search correlated every one of 117 + * window positions against the whole of the other clip, re-transforming that unchanged clip + * every time. `FingerprintWorker` is a plain WorkManager worker, so Android stopped it at ten + * minutes, before it had persisted anything, and WorkManager re-ran it -- which is why Peter's + * phone ran hot and why no show ever got past its first processed episode. + * + * So these tests assert cost, at the real sizes, with real constants. The budget is deliberately + * generous: this runs on whatever machine happens to build the app, and a phone is slower again. + * It is not a benchmark, it is a tripwire -- the failure it exists to catch is minutes, not + * milliseconds. + */ +class IntroOutroDetectorScaleTest { + + private companion object { + const val SAMPLE_RATE = 8_000 + /** [MediaCodecClipSource.CLIP_SECONDS], the window production actually decodes. */ + const val CLIP_SECONDS = 240 + const val CLIP_SAMPLES = SAMPLE_RATE * CLIP_SECONDS + + /** [FingerprintUpdater.DEFAULT_REFERENCE_SECONDS] at [FingerprintUpdater.DEFAULT_SAMPLE_RATE]. */ + const val REFERENCE_SAMPLES = 8 * SAMPLE_RATE + + /** + * One episode's worth of candidate search. Both ends of an episode run inside the same + * ten-minute worker, so a single end has to come in far enough under that to leave room + * for the other end, two or four MediaCodec decodes, and a slower CPU than this one. + */ + const val BUDGET_MS = 60_000L + } + + private fun noise(seed: Int, n: Int) = Random(seed).let { r -> DoubleArray(n) { r.nextDouble(-50.0, 50.0) } } + + /** A tonal sting, the shape a real show's intro music has at 8kHz. */ + private fun sting(seed: Int, n: Int): DoubleArray { + val r = Random(seed) + return DoubleArray(n) { sin(it * 0.03) * 400 + r.nextDouble(-20.0, 20.0) } + } + + private fun embed(base: DoubleArray, segment: DoubleArray, at: Int): DoubleArray { + val out = base.copyOf() + segment.forEachIndexed { i, v -> out[at + i] = v } + return out + } + + /** The show's recurring intro, long enough that a reference window lands wholly inside it. */ + private val theShowsSting = sting(seed = 100, n = REFERENCE_SAMPLES * 2) + + /** + * Two episodes, the sting at a different offset in each -- the dynamic-pre-roll case + * `docs/detection-findings.md` measured on real Up First audio, where the intro landed + * anywhere between 44 and 94 seconds in. + */ + private fun episodeClip(seed: Int, stingAtSeconds: Int, clipSeconds: Int = CLIP_SECONDS) = + embed(noise(seed, clipSeconds * SAMPLE_RATE), theShowsSting, stingAtSeconds * SAMPLE_RATE) + + @Test + fun `a production-sized candidate search finds the sting inside the worker's budget`() { + val first = episodeClip(seed = 1, stingAtSeconds = 44) + val second = episodeClip(seed = 2, stingAtSeconds = 94) + + val waiting = IntroOutroDetector.check(FingerprintState(), "ep1", first, REFERENCE_SAMPLES) + assertTrue("first episode has nothing to compare against", waiting is FingerprintUpdate.Waiting) + + lateinit var update: FingerprintUpdate + val elapsed = measureTimeMillis { + update = IntroOutroDetector.check(waiting.state, "ep2", second, REFERENCE_SAMPLES) + } + + assertTrue( + "expected a candidate from two episodes sharing an intro, got $update", + update is FingerprintUpdate.Tentative, + ) + assertTrue( + "candidate search took ${elapsed}ms against a ${BUDGET_MS}ms budget -- a worker " + + "that cannot finish inside WorkManager's ten minutes never persists anything", + elapsed < BUDGET_MS, + ) + } + + /** + * The confirming episode's path, which runs once a reference exists and is the one that + * actually writes a skip offset. Cheap by construction -- a single correlation -- and pinned + * here so it stays that way. + */ + @Test + fun `confirming against an existing reference stays cheap at production size`() { + val reference = theShowsSting.copyOf(REFERENCE_SAMPLES) + val state = FingerprintState( + referenceClip = reference, + confirmedCount = 2, + lastConfirmedEpisodeId = "ep2", + ) + + lateinit var update: FingerprintUpdate + val elapsed = measureTimeMillis { + update = IntroOutroDetector.check(state, "ep3", episodeClip(seed = 3, stingAtSeconds = 61), REFERENCE_SAMPLES) + } + + assertTrue("expected the third episode to confirm, got $update", update is FingerprintUpdate.Confirmed) + assertEquals(61 * SAMPLE_RATE, (update as FingerprintUpdate.Confirmed).positionInClip) + assertTrue("single confirmation took ${elapsed}ms", elapsed < BUDGET_MS) + } + + /** + * Full resolution has to stay reachable, because that is what the current behaviour is + * defined by: a coarse factor of 1 means "search exactly as before". Having the knob proves + * the speed-up is a resolution choice and not a different algorithm wearing its name. + * + * Deliberately on a shorter clip than the budget tests. At the full 240 seconds this takes + * 137 seconds -- the cost the coarse pass exists to avoid -- and paying it on every run of + * the suite to re-prove something a 40-second clip proves just as well is the kind of thing + * that gets a test deleted rather than kept. + */ + @Test + fun `a coarse factor of one still finds the sting`() { + val first = episodeClip(seed = 4, stingAtSeconds = 8, clipSeconds = 40) + val second = episodeClip(seed = 5, stingAtSeconds = 24, clipSeconds = 40) + val tuning = IntroOutroDetector.Tuning(coarseFactor = 1) + + val waiting = IntroOutroDetector.check(FingerprintState(), "ep1", first, REFERENCE_SAMPLES, tuning = tuning) + val update = IntroOutroDetector.check(waiting.state, "ep2", second, REFERENCE_SAMPLES, tuning = tuning) + + assertTrue("expected a candidate at full resolution, got $update", update is FingerprintUpdate.Tentative) + } + + /** + * The coarse pass has to agree with full resolution about *where* the sting is, not just + * that there is one. A faster search that found a different segment would still report + * Tentative and would still be wrong -- and nothing downstream could tell. + */ + @Test + fun `the coarse search picks the same segment full resolution does`() { + val first = episodeClip(seed = 6, stingAtSeconds = 8, clipSeconds = 40) + val second = episodeClip(seed = 7, stingAtSeconds = 24, clipSeconds = 40) + + fun referenceWith(tuning: IntroOutroDetector.Tuning): DoubleArray { + val waiting = IntroOutroDetector.check(FingerprintState(), "ep1", first, REFERENCE_SAMPLES, tuning = tuning) + return IntroOutroDetector.check(waiting.state, "ep2", second, REFERENCE_SAMPLES, tuning = tuning) + .state.referenceClip!! + } + + val atFullResolution = referenceWith(IntroOutroDetector.Tuning(coarseFactor = 1)) + val viaCoarsePass = referenceWith(IntroOutroDetector.Tuning()) + + // Both searches step across the clip on the same native grid -- full resolution by + // win/4, the coarse pass by (win/factor)/4 scaled back up by factor, which is the same + // 16,000 samples -- so the window they pick is comparable sample for sample. Identical + // contents means the same position, and the position is what a skip offset comes from. + assertArrayEquals( + "coarse and full-resolution searches disagree about which segment is the sting", + atFullResolution, + viaCoarsePass, + 0.0, + ) + } +} diff --git a/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorTest.kt b/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorTest.kt index 91f2800..a9dfdbc 100644 --- a/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorTest.kt +++ b/app/src/test/java/org/terst/listen/fingerprint/IntroOutroDetectorTest.kt @@ -166,7 +166,7 @@ class IntroOutroDetectorTest { * confirmation genuinely depends on the threshold rather than being hardcoded to 3. */ @Test fun `a raised threshold keeps a third agreeing episode merely tentative`() { - val threshold = 4 + val threshold = IntroOutroDetector.Tuning(confirmThreshold = 4) var state = FingerprintState() state = IntroOutroDetector.check( state, "ep1", embed(noise(1, 300), theShowsSting, 50), REFERENCE_LENGTH, threshold, diff --git a/app/src/test/java/org/terst/listen/fingerprint/MidrollUpdaterTest.kt b/app/src/test/java/org/terst/listen/fingerprint/MidrollUpdaterTest.kt index e8e4474..ae9478e 100644 --- a/app/src/test/java/org/terst/listen/fingerprint/MidrollUpdaterTest.kt +++ b/app/src/test/java/org/terst/listen/fingerprint/MidrollUpdaterTest.kt @@ -3,6 +3,7 @@ package org.terst.listen.fingerprint import kotlin.random.Random import kotlinx.coroutines.test.runTest import org.junit.Assert.assertEquals +import org.junit.Assert.assertNull import org.junit.Assert.assertTrue import org.junit.Before import org.junit.Test @@ -173,14 +174,76 @@ class MidrollUpdaterTest { assertEquals(fixedNow, episodes.rows.single().midrollCheckedAtMs) } + /** + * The decode a full-body scan needs is held entirely in memory, so an episode's length is + * also an allocation. An hour of 8kHz mono is 28.8 million doubles -- 230MB, on a phone with + * no largeHeap -- and before this the updater asked for it anyway: `decodeFull` threw + * OutOfMemoryError, `runCatching` swallowed it, and the episode was then marked checked + * forever, so no episode was ever scanned and nothing said why. + * + * Over budget now costs nothing and is left unchecked, so the slice-on-demand decode that + * lifts the limit picks these episodes up rather than finding them all written off. + */ + @Test + fun `an episode too long to hold in memory is never decoded`() = runTest { + show() + downloadedEpisode("marathon", downloadedAtMs = 1, durationMs = 3 * 60 * 60 * 1000L) + + updater.processShow("show1") + + assertEquals(emptyList(), clips.decodeRequests) + } + + @Test + fun `an episode too long to hold in memory is left for later, not marked checked`() = runTest { + show() + downloadedEpisode("marathon", downloadedAtMs = 1, durationMs = 3 * 60 * 60 * 1000L) + + updater.processShow("show1") + + assertNull( + "an over-budget episode marked checked can never be scanned again", + episodes.rows.single { it.id == "marathon" }.midrollCheckedAtMs, + ) + } + + /** An over-budget episode must not become the pending basis either, or it blocks the show. */ + @Test + fun `an episode too long to hold in memory does not become the pending basis`() = runTest { + show() + downloadedEpisode("marathon", downloadedAtMs = 1, durationMs = 3 * 60 * 60 * 1000L) + + updater.processShow("show1") + + assertNull(subscriptions.rows.single().midrollPendingEpisodeId) + } + + /** A normal-length episode is unaffected -- the budget is a ceiling, not a new gate. */ + @Test + fun `an episode inside the budget is decoded as before`() = runTest { + show() + clips.full["e1"] = embed(noise(1, 3000), ad, at = 500) + downloadedEpisode("e1", downloadedAtMs = 1, durationMs = 600_000) + + updater.processShow("show1") + + assertEquals(listOf("e1"), clips.decodeRequests) + assertEquals(fixedNow, episodes.rows.single { it.id == "e1" }.midrollCheckedAtMs) + } + private class FakeFullClipSource : AudioClipSource { val full = mutableMapOf() val sampleRate = 8_000 + /** Which episodes were actually asked for, so "never attempted" can be asserted. */ + val decodeRequests = mutableListOf() + override suspend fun decodeHead(episode: EpisodeEntity): DecodedClip? = null override suspend fun decodeTail(episode: EpisodeEntity): DecodedClip? = null - override suspend fun decodeFull(episode: EpisodeEntity): DecodedClip? = - full[episode.id]?.let { DecodedClip(it, sampleRate, startMs = 0) } + override suspend fun decodeFull(episode: EpisodeEntity): DecodedClip? { + decodeRequests += episode.id + return full[episode.id]?.let { DecodedClip(it, sampleRate, startMs = 0) } + } } } diff --git a/app/src/test/java/org/terst/listen/fingerprint/MonoResamplerTest.kt b/app/src/test/java/org/terst/listen/fingerprint/MonoResamplerTest.kt new file mode 100644 index 0000000..068585b --- /dev/null +++ b/app/src/test/java/org/terst/listen/fingerprint/MonoResamplerTest.kt @@ -0,0 +1,161 @@ +package org.terst.listen.fingerprint + +import kotlin.random.Random +import org.junit.Assert.assertArrayEquals +import org.junit.Assert.assertEquals +import org.junit.Test + +/** + * The decode a full-episode scan needs, made to cost its output rather than its input. + * + * [MediaCodecClipSource] used to buffer the whole episode at its native rate -- a `ShortArray` + * of every interleaved sample, then a `DoubleArray` of every mono frame -- and only then + * resample to 8kHz. For a 13-minute stereo 44.1kHz episode that is 145MB plus 289MB live at + * once, on a phone with no largeHeap, to produce 6MB of output. It threw OutOfMemoryError, + * `runCatching` swallowed it, and midroll detection silently never ran on anything. + * + * This consumes the decoder's output chunk by chunk and keeps only the 8kHz mono result, so the + * peak allocation is the result. Being pure, it is also the half of that adapter that can + * actually be tested -- the rest is MediaCodec plumbing. + * + * The resampling is deliberately the same naive linear interpolation as before: measured at + * 0.9991 correlation against a proper ffmpeg/swresample decode of the same audio + * (`docs/detection-findings.md`), so it was never the weak link and this is not the change to + * start improving it in. + */ +class MonoResamplerTest { + + /** + * The batch formula the streaming one has to agree with, lifted from the implementation it + * replaces. Present as an oracle so the chunking is what gets tested -- the formula itself + * is pinned separately, by hand, in [matches hand-computed linear interpolation]. + */ + private fun batch(interleaved: ShortArray, channels: Int, inputRate: Int, targetRate: Int): DoubleArray { + val frames = interleaved.size / channels + val mono = DoubleArray(frames) { frame -> + var sum = 0.0 + for (c in 0 until channels) sum += interleaved[frame * channels + c] + sum / channels + } + if (inputRate == targetRate || mono.isEmpty()) return mono + + val ratio = targetRate.toDouble() / inputRate + val outLength = (mono.size * ratio).toInt() + return DoubleArray(outLength) { i -> + val sourcePosition = i / ratio + val index = sourcePosition.toInt().coerceIn(0, mono.size - 1) + val next = (index + 1).coerceAtMost(mono.size - 1) + val fraction = sourcePosition - index + mono[index] * (1 - fraction) + mono[next] * fraction + } + } + + private fun streamed( + interleaved: ShortArray, + channels: Int, + inputRate: Int, + targetRate: Int, + chunkFrames: Int, + ): DoubleArray { + val resampler = MonoResampler(inputRate = inputRate, channels = channels, targetRate = targetRate) + var offset = 0 + while (offset < interleaved.size) { + val count = minOf(chunkFrames * channels, interleaved.size - offset) + resampler.accept(interleaved, offset, count) + offset += count + } + return resampler.finish() + } + + @Test + fun `matches hand-computed linear interpolation`() { + // Mono, 4Hz in, 2Hz out: ratio 0.5, so output i reads source position 2i exactly and + // every fraction is zero -- every other sample, with no interpolation to obscure it. + val resampler = MonoResampler(inputRate = 4, channels = 1, targetRate = 2) + resampler.accept(shortArrayOf(10, 20, 30, 40), 0, 4) + + assertArrayEquals(doubleArrayOf(10.0, 30.0), resampler.finish(), 1e-9) + } + + @Test + fun `interpolates between neighbouring samples on a fractional position`() { + // 4Hz in, 3Hz out: ratio 0.75, so output 1 sits at source position 1.333... + val resampler = MonoResampler(inputRate = 4, channels = 1, targetRate = 3) + resampler.accept(shortArrayOf(0, 300, 600, 900), 0, 4) + + val out = resampler.finish() + assertEquals(3, out.size) + assertEquals(0.0, out[0], 1e-9) + assertEquals(300 * (1 - 1.0 / 3) + 600 * (1.0 / 3), out[1], 1e-9) + assertEquals(600 * (1 - 2.0 / 3) + 900 * (2.0 / 3), out[2], 1e-9) + } + + @Test + fun `averages channels down to mono`() { + val resampler = MonoResampler(inputRate = 8, channels = 2, targetRate = 8) + resampler.accept(shortArrayOf(10, 20, 100, 200), 0, 4) + + assertArrayEquals(doubleArrayOf(15.0, 150.0), resampler.finish(), 1e-9) + } + + /** + * The actual risk in streaming this: an output sample interpolates between two source + * frames, and those two can straddle a chunk boundary. A decoder hands over whatever buffer + * sizes it likes, so every split has to give the same answer as no split at all. + */ + @Test + fun `chunking the input does not change the output`() { + val random = Random(42) + val interleaved = ShortArray(20_000) { random.nextInt(-3000, 3000).toShort() } + val expected = batch(interleaved, channels = 2, inputRate = 44_100, targetRate = 8_000) + + for (chunkFrames in listOf(1, 2, 3, 7, 64, 999, 10_000)) { + assertArrayEquals( + "a $chunkFrames-frame chunking disagreed with the unchunked result", + expected, + streamed(interleaved, 2, 44_100, 8_000, chunkFrames), + 1e-9, + ) + } + } + + @Test + fun `chunking does not change the output when no resampling is needed`() { + val random = Random(7) + val interleaved = ShortArray(5_000) { random.nextInt(-3000, 3000).toShort() } + val expected = batch(interleaved, channels = 1, inputRate = 8_000, targetRate = 8_000) + + for (chunkFrames in listOf(1, 5, 333, 5_000)) { + assertArrayEquals(expected, streamed(interleaved, 1, 8_000, 8_000, chunkFrames), 1e-9) + } + } + + @Test + fun `upsampling agrees with the batch formula too`() { + val random = Random(9) + val interleaved = ShortArray(3_000) { random.nextInt(-3000, 3000).toShort() } + val expected = batch(interleaved, channels = 2, inputRate = 8_000, targetRate = 16_000) + + for (chunkFrames in listOf(1, 11, 1_500)) { + assertArrayEquals(expected, streamed(interleaved, 2, 8_000, 16_000, chunkFrames), 1e-9) + } + } + + @Test + fun `nothing accepted produces nothing`() { + assertEquals(0, MonoResampler(inputRate = 44_100, channels = 2, targetRate = 8_000).finish().size) + } + + /** + * The whole point, stated as a number: the result is sized by the output rate, so what the + * decoder was handed at its native rate is never all live at once. + */ + @Test + fun `the result is sized by the target rate, not the input rate`() { + val resampler = MonoResampler(inputRate = 44_100, channels = 2, targetRate = 8_000) + val oneSecondStereo = ShortArray(44_100 * 2) + resampler.accept(oneSecondStereo, 0, oneSecondStereo.size) + + assertEquals(8_000, resampler.finish().size) + } +} diff --git a/app/src/test/java/org/terst/listen/fingerprint/SkipSummaryTest.kt b/app/src/test/java/org/terst/listen/fingerprint/SkipSummaryTest.kt index bd10ece..efb01ae 100644 --- a/app/src/test/java/org/terst/listen/fingerprint/SkipSummaryTest.kt +++ b/app/src/test/java/org/terst/listen/fingerprint/SkipSummaryTest.kt @@ -247,4 +247,98 @@ class SkipSummaryTest { assertEquals(null, skips.insertedAds) } + + /** + * The sanity check Peter asked for, in one place: what the feed claims, what the file turned + * out to be, and how much of the gap the detector has actually accounted for. + * + * The three numbers only mean anything together. `insertedAds` says there are seven and a + * half minutes of advertising in Grass Apes; `breaksTotal` saying thirty seconds means the + * midroll scan is missing breaks, and saying nine minutes means it is matching programme. + * Either way the readout has to show both or it cannot be checked at all. + */ + @Test + fun `reports the declared and measured lengths side by side`() { + val skips = SkipSummary.episode( + episodeRow(durationMs = 1_325_000, actualDurationMs = 1_774_000), + showRow(), + emptyList(), + ) + + assertEquals("22:05", skips.declaredLength) + assertEquals("29:34", skips.measuredLength) + } + + /** An episode the player has never opened has no measured length to report. */ + @Test + fun `an unplayed episode reports only the declared length`() { + val skips = SkipSummary.episode(episodeRow(durationMs = 1_325_000), showRow(), emptyList()) + + assertEquals("22:05", skips.declaredLength) + assertEquals(null, skips.measuredLength) + } + + @Test + fun `totals up the detected ad breaks so they can be checked against the inserted ads`() { + val skips = SkipSummary.episode( + episodeRow(durationMs = 1_325_000, actualDurationMs = 1_774_000, midrollCheckedAtMs = 1), + showRow(), + listOf( + EpisodeMidrollEntity("e1", "c1", startMs = 120_000, endMs = 180_000), + EpisodeMidrollEntity("e1", "c2", startMs = 600_000, endMs = 690_000), + ), + ) + + // A minute plus ninety seconds, against the 7:29 the length gap implies. + assertEquals("2:30", skips.breaksTotal) + } + + /** Nothing detected is not a total of zero -- there is no figure to compare yet. */ + @Test + fun `no detected breaks means no total`() { + val skips = SkipSummary.episode( + episodeRow(durationMs = 1_325_000, actualDurationMs = 1_774_000, midrollCheckedAtMs = 1), + showRow(), + emptyList(), + ) + + assertEquals(null, skips.breaksTotal) + } + + /** + * Where the detected breaks sit, as fractions of the episode, so the scrubber can mark them. + * Computed here rather than in the composable for the usual reason: an off-by-a-factor that + * draws a marker in the wrong place is invisible in a screenshot and obvious in a test. + */ + @Test + fun `places detected breaks on the timeline as fractions of the measured length`() { + val markers = SkipSummary.breakMarkers( + listOf(EpisodeMidrollEntity("e1", "c1", startMs = 300_000, endMs = 600_000)), + durationMs = 1_200_000, + ) + + assertEquals(1, markers.size) + assertEquals(0.25f, markers.single().start, 1e-6f) + assertEquals(0.5f, markers.single().end, 1e-6f) + } + + @Test + fun `a break running past the end of the episode is clamped to it`() { + val markers = SkipSummary.breakMarkers( + listOf(EpisodeMidrollEntity("e1", "c1", startMs = 1_100_000, endMs = 9_000_000)), + durationMs = 1_200_000, + ) + + assertEquals(1.0f, markers.single().end, 1e-6f) + } + + @Test + fun `an unknown length places no markers`() { + val markers = SkipSummary.breakMarkers( + listOf(EpisodeMidrollEntity("e1", "c1", startMs = 1, endMs = 2)), + durationMs = null, + ) + + assertEquals(emptyList(), markers) + } } diff --git a/app/src/test/java/org/terst/listen/playback/PrepareTraceTest.kt b/app/src/test/java/org/terst/listen/playback/PrepareTraceTest.kt new file mode 100644 index 0000000..b5b1d75 --- /dev/null +++ b/app/src/test/java/org/terst/listen/playback/PrepareTraceTest.kt @@ -0,0 +1,142 @@ +package org.terst.listen.playback + +import org.junit.Assert.assertEquals +import org.junit.Assert.assertNull +import org.junit.Test + +/** + * The measurement Peter's third report needs: "a longish pause when starting playback, + * proportional to episode length". + * + * Nothing in the app's own play path scales with an episode's length -- it is database reads and + * then `setMediaItem`/`prepare` -- so the candidates are Media3's own preparation and the CPU + * being saturated by something else. Those are indistinguishable from the outside, and guessing + * between them is how a fix gets shipped for the wrong one. + * + * So this emits one line per start carrying the length *and* the elapsed stages, which answers + * "is it proportional?" directly from a log rather than from an argument. The line is built here + * rather than in the service because a format that silently dropped the length would make the + * whole exercise pointless, and that is worth a test. + */ +class PrepareTraceTest { + + private var clock = 0L + private fun trace() = PrepareTrace { clock } + + @Test + fun `reports each stage as elapsed milliseconds since the start`() { + val trace = trace() + clock = 1_000 + trace.start(episodeId = "ep1", durationMs = 1_774_000, local = true) + clock = 1_812 + trace.mark(PrepareTrace.Stage.READY) + clock = 1_903 + trace.mark(PrepareTrace.Stage.PLAYING) + + assertEquals( + "prepare ep=ep1 len=1774s src=local ready=812ms playing=903ms", + trace.summary(), + ) + } + + /** A streamed episode is a different question from a downloaded one, so the line says which. */ + @Test + fun `distinguishes a streamed episode from a downloaded one`() { + val trace = trace() + clock = 500 + trace.start(episodeId = "ep2", durationMs = 60_000, local = false) + clock = 2_500 + trace.mark(PrepareTrace.Stage.READY) + + assertEquals("prepare ep=ep2 len=60s src=stream ready=2000ms", trace.summary()) + } + + /** An unknown length still traces: that it was unknown is itself worth seeing. */ + @Test + fun `reports an unknown length as unknown`() { + val trace = trace() + trace.start(episodeId = "ep3", durationMs = null, local = true) + clock = 40 + trace.mark(PrepareTrace.Stage.READY) + + assertEquals("prepare ep=ep3 len=? src=local ready=40ms", trace.summary()) + } + + @Test + fun `nothing to report before a start`() { + assertNull(trace().summary()) + } + + /** + * Media3 reports READY more than once for one item -- a rebuffer is another READY. Only the + * first is the preparation being measured; later ones would overwrite it with a small + * number and hide exactly the delay being chased. + */ + @Test + fun `keeps the first time a stage was reached, not the last`() { + val trace = trace() + trace.start(episodeId = "ep4", durationMs = 1_000, local = true) + clock = 900 + trace.mark(PrepareTrace.Stage.READY) + clock = 5_000 + trace.mark(PrepareTrace.Stage.READY) + + assertEquals("prepare ep=ep4 len=1s src=local ready=900ms", trace.summary()) + } + + /** A new start is a new measurement; the previous episode's stages must not bleed into it. */ + @Test + fun `starting again clears the previous episode's stages`() { + val trace = trace() + trace.start(episodeId = "ep5", durationMs = 1_000, local = true) + clock = 700 + trace.mark(PrepareTrace.Stage.READY) + + clock = 1_000 + trace.start(episodeId = "ep6", durationMs = 2_000, local = true) + + assertEquals("prepare ep=ep6 len=2s src=local", trace.summary()) + } + + /** + * The clock has to start when the media item is set, which is the only hook both play paths + * go through -- the service's own queue advance and a tap in the UI, which reaches the + * player through a MediaController and never calls the service's `play`. A MediaItem carries + * no duration, so the length arrives later, from the player, once it has opened the file. + * + * That length is also the better of the two available: it is what the file really is, not + * what the feed claimed, and on a show using dynamic ad insertion those differ by minutes. + */ + @Test + fun `a length supplied after the start still appears in the line`() { + val trace = trace() + clock = 1_000 + trace.start(episodeId = "ep7", durationMs = null, local = true) + clock = 1_500 + trace.length(1_774_000) + trace.mark(PrepareTrace.Stage.READY) + + assertEquals("prepare ep=ep7 len=1774s src=local ready=500ms", trace.summary()) + } + + /** A length learned for a previous episode must not be reported for the next one. */ + @Test + fun `a length does not survive into the next episode`() { + val trace = trace() + trace.start(episodeId = "ep8", durationMs = null, local = true) + trace.length(600_000) + trace.start(episodeId = "ep9", durationMs = null, local = true) + + assertEquals("prepare ep=ep9 len=? src=local", trace.summary()) + } + + /** Media3 reports no duration until it has one; that must not overwrite a real length. */ + @Test + fun `an unset length is ignored rather than clearing a known one`() { + val trace = trace() + trace.start(episodeId = "ep10", durationMs = 60_000, local = true) + trace.length(null) + + assertEquals("prepare ep=ep10 len=60s src=local", trace.summary()) + } +} diff --git a/docs/detection-findings.md b/docs/detection-findings.md index 6c7385d..1bb7880 100644 --- a/docs/detection-findings.md +++ b/docs/detection-findings.md @@ -272,3 +272,226 @@ instead of restarting again. YouTube extraction and resolution **cannot be exercised from tungsten** — every watch URL gets a 302 to a bot-check page. Anything touching YouTube has to be verified on the phone. Podcast feeds, Room migrations, playback and the fingerprint pipeline are all fine on the emulator. + +--- + +## Fifth pass, 2026-10-03: the cost nobody had measured + +**Peter's report:** the phone runs hot and uses a lot of battery, and intelligent skipping has +never done anything to any episode. + +Everything above is still true and the retention fix still stands. It was not the whole story, +and on the evidence below it was not the dominant blocker either. + +### The candidate search cost 199 seconds per end, measured + +`IntroOutroDetector.findCandidate` bootstrapped a show by sliding an 8-second window across a +240-second clip in quarter-window steps -- **117 positions** -- and running a *full-length* FFT +cross-correlation against the whole of the other clip at every one of them, re-transforming that +unchanged clip each time. 702 transforms of 2^21 points per episode. + +Measured, not estimated, by `IntroOutroDetectorScaleTest` at the real sizes and real constants: + +| path | before | after | +| --- | --- | --- | +| candidate search, one end | **199.1 s** | 17.8 s | +| ditto, full resolution with the target transform hoisted | 136.6 s | -- | +| confirming against an existing reference | 1.7 s | 1.7 s | + +That is on a desktop. A phone has a fraction of this machine's memory bandwidth. + +### Why that meant nothing was ever persisted + +`FingerprintWorker` is a plain WorkManager worker, so **Android stops it at about ten minutes**. +Both ends of an episode run inside one worker, and `FingerprintUpdater` writes nothing until a +comparison returns -- so the worker was killed mid-correlation, saved nothing, and WorkManager +re-enqueued it to start the same work again with backoff. + +The expensive path is specifically the *bootstrap*, the one that runs until a show has a +reference clip. Escaping it requires one run to finish. None ever did. This is a complete +explanation of both of Peter's reports at once: hours of full-CPU work, and a +`show_fingerprints` row frozen at the first episode ever processed. + +It also fits the second pass's observation better than the retention theory does. That pass found +Up First's row frozen even though a second episode "was downloaded, played and decoded +successfully (by a different worker)", and concluded the comparison "never ran at all". On this +evidence the comparison *did* run, for ten minutes, and died before its `upsert`. Both mechanisms +produce a frozen row; only one of them also produces a hot phone. + +**One data point still does not fit:** Cruising the Waves reached `confirmedCount=2` that day, so +something completed once. Worth checking whether its episodes are short enough to have come in +under the limit. + +### The fix + +Coarse-to-fine, the composition `MidrollUpdater` already used and this document already +defended: decimate both clips by 8, rank candidate positions on the decimated copies, then +re-slice the best three at native resolution and let a full-resolution correlation decide. +Plus `AudioCorrelation.prepareTarget`, so the target clip is transformed once per search rather +than 117 times. + +**10.6x faster, and provably the same answer.** `the coarse search picks the same segment full +resolution does` asserts the chosen reference window is identical sample for sample -- both +searches step the same native grid, so the positions are directly comparable. No detection +threshold was touched. + +### Midroll detection could never have run at all + +Separately and independently: `MediaCodecClipSource.decodeFull` buffered every interleaved sample +at the file's native rate, then every mono frame, and only then resampled to 8kHz. + +| episode | native PCM buffer | mono buffer | both live at once | +| --- | --- | --- | --- | +| 10m | 106 MB | 212 MB | 318 MB | +| 13m (Up First) | 145 MB | 289 MB | 434 MB | +| 30m | 308 MB | 616 MB | 924 MB | +| 60m | 611 MB | 1,221 MB | 1,832 MB | + +There is no `largeHeap` in the manifest. It threw `OutOfMemoryError`, the `runCatching` in +`decode` swallowed it, `decodeFull` returned null, and `MidrollUpdater` then marked the episode +**checked forever**. So no episode of any normal length was ever scanned, none would be retried, +and the readout said "None found" rather than anything true. + +Two changes: `MonoResampler` consumes the decoder buffer by buffer and keeps only the 8kHz +output, so the peak allocation is the result rather than the input; and `MidrollUpdater.Tuning` +now has a `maxDecodableMs` (20 minutes) that skips a longer episode **before** spending anything +and **without** marking it checked. + +**Still outstanding:** an episode over that ceiling is not scanned. Lifting it properly means +decoding candidate ranges on demand (`decodeRange`) instead of holding the whole body, which is +a real change to `MidrollUpdater.discover`/`extractSegment` and to `MidrollDetector.check` -- +all three currently want the entire native-resolution array. Left deliberately undone rather +than half-done. + +--- + +## The playback-start pause: one hypothesis disproven, instrumentation shipped + +Peter's third report: "there's a longish pause when starting playback, proportional to episode +length." Recorded here with the others because the next session should not re-check what has +already been eliminated. + +**Nothing in the app's own play path scales with episode length.** Traced end to end: tap -> +`PlayerViewModel.play` -> `PlaybackAdvancer.start` (a few indexed row reads) -> +`PlayerConnection.play` -> `setMediaItem`/`prepare`. No file scan, no hashing, no probe. + +**`PrepareTrace` now measures it**, tagged `ListenPlayback`, one line per start: + +``` +prepare ep=9c9750ef len=1642s src=local ready=666ms playing=667ms +``` + +**Measured on the emulator, a 27-minute downloaded Radiolab episode: ~400-500ms to READY**, with +no other load on the device. So there is a real cost here and it is not only CPU starvation from +the fingerprint worker. + +### Disproven: the missing MP3 seek table + +The downloaded file has **no Xing, Info or VBRI header** (checked directly: ID3 tag of 166 bytes, +audio from byte 176, none of the three markers present). Without one, Media3 has no seek table to +read, and the obvious suspicion was that `Mp3Extractor` was reading through the file to build one +-- which would be length-proportional, exactly matching the report. + +Tested by enabling `Mp3Extractor.FLAG_ENABLE_CONSTANT_BITRATE_SEEKING` on a +`DefaultExtractorsFactory` and measuring the same episode: + +| configuration | ready (ms) | mean | +| --- | --- | --- | +| shipped default | 404, 531, 386 | ~440 | +| constant-bitrate seeking on | 469, 450, 404 | ~441 | + +**No difference.** The distributions overlap entirely. A first pair of samples had looked like +666ms against 411ms, which is a 38% improvement and was cold-start noise -- the lesson being that +one sample of each proves nothing here, because the spread is wider than any effect. + +The flag was reverted. It would also have been the wrong trade even if it had worked: constant- +bitrate seeking makes seeks approximate on a genuinely VBR file, and playback position is the one +piece of data in this app that cannot be reconstructed. + +### What is still open + +Whether the ~440ms scales with episode length. It cannot be settled on the emulator, which has +one episode on it. The instrumented build is on the phone, so **two plays of episodes with very +different lengths will answer it from the log** -- compare `len=` against `ready=`. If it is flat, +the pause is a fixed preparation cost and the "proportional" impression was the fingerprint +worker saturating the CPU, which is now fixed. If it scales, the cause is inside Media3's +preparation and the next place to look is what `ProgressiveMediaPeriod` reads before reporting +READY. + +--- + +## 2026-10-05: detection ported to Go and verified on real audio + +Peter's call: detection moves to a server, in Go, matching podkit and doot. The port is in +`server/`, and this section is what it actually proves -- which is not the same as what it is. + +### Verified + +**Against numpy, not against itself.** `AudioCorrelationTest`'s numpy-derived fixtures were +extracted mechanically (not retyped) into `server/internal/detect/fixtures_test.go`, with the +same pinned literals: self-match 1.0, embedded sting r=0.9998959789695058 at position 120, +unrelated target r=0.3672490793439344. The Go FFT is separately checked against a direct DFT +computed from the definition, and the whole FFT correlation path against a brute-force Pearson +correlation. That is three independent anchors, because this is the second port of this maths +and the first one shipped a normalization bug. + +**On real audio, end to end.** Four Radiolab episodes, fetched from the live feed: + +``` +intro: confirmed on 4 of 4 episodes; self-check passed on 6 pairs, worst r=0.9286 + ep1 21:07 skip intro to 0:56.000 + ep2 22:05 skip intro to 0:16.652 + ep3 31:02 skip intro to 0:16.652 + ep4 1:03:27 skip intro to 1:13.152 +detection took 2m9s +``` + +The intro sits at a different offset in each episode -- 48.0s, 8.65s, 8.65s, 65.15s -- which is +the varying pre-roll this document has described since the first pass, now observed directly in +production code. Cross-checking the located segments against each other at exact sample +positions gives 0.93 to 0.998 on all six pairs: it is genuinely the same recording in all four. + +### What the self-check caught, immediately + +`skips.SelfCheck` correlates the *located segments against one another*, rather than each +against the reference they were found with. Those are different claims. Correlation is not +transitive: two segments can each clear 0.6 against a reference while scoring near zero against +each other, and offsets derived from such a set would cut different audio out of different +episodes. + +On the very first real run it rejected the outro: + +``` +outro: confirmed on 3 of 4 episodes; SELF-CHECK FAILED: ep1 vs ep2 at r=0.7460 -- offsets withheld +``` + +Before the check existed, that same run published outro offsets of 0:12, 0:11 and 0:11 -- which +would have ended three episodes early at a point two of them do not share. **The confirmation +threshold passed a false positive and the self-check stopped it.** Offsets are now only +published when the segments verify against each other, and `listen-detect` exits non-zero when +they do not. + +Outro detection on this show is therefore still unproven. It fails closed, which is the +important part, but why a 0.746 pair cleared a 0.6 threshold is the next thing to look at. + +### A false alarm worth not repeating + +The first hand check of the real run showed r=0.03 between two located segments and looked like +a serious bug. It was an artifact of reading offsets the CLI had rounded to whole seconds: the +true position was 8.65s, so the extracted window was 0.65s out, while two episodes that happened +to share the same rounded offset lined up perfectly and scored 0.997. The CLI now prints +milliseconds, and `SelfCheck` tolerates half a second of position error for the same reason. + +### Not verified, and not built + +- **No server.** What exists is the detection core and a CLI. The feed poller, the episode + mirror, the 8-episode retention, the HTTP API and the phone changes are all still to come. +- **Dynamic ad insertion did not reproduce from this host.** All four episodes served *exactly* + their declared length -- Grass Apes at 22:05, against the 29:34 and 27:39 measured earlier + from the phone. So either insertion is conditioned on the client (user agent, geography, + headers) or it is not always on. This matters in both directions: it is the entire reason the + server has to serve the audio it detected against, and if the server reliably gets the clean + file then mirroring strips the advertising rather than merely locating it. Four samples from + one host with curl is not enough to conclude either way, and it should be measured properly + before the design leans on it. +- **Midroll detection is not ported.** Only intro/outro. diff --git a/server/cmd/listen-detect/main.go b/server/cmd/listen-detect/main.go new file mode 100644 index 0000000..49394fd --- /dev/null +++ b/server/cmd/listen-detect/main.go @@ -0,0 +1,119 @@ +// Command listen-detect reports the recurring intro and outro across a show's episode files. +// +// The detection core of the server, usable on its own so a result can be checked against real +// audio rather than only against synthetic fixtures. Point it at several episodes of one show: +// +// listen-detect episode1.mp3 episode2.mp3 episode3.mp3 episode4.mp3 +package main + +import ( + "context" + "flag" + "fmt" + "os" + "path/filepath" + "time" + + "github.com/terst/listen/server/internal/decode" + "github.com/terst/listen/server/internal/skips" +) + +func main() { + clipSeconds := flag.Int("clip-seconds", skips.DefaultClipSeconds, "window searched at each end of an episode") + referenceSeconds := flag.Int("reference-seconds", skips.DefaultReferenceSeconds, "length of the segment looked for") + threshold := flag.Int("confirm", skips.DefaultConfirmThreshold, "episodes that must agree (lowering this defeats the safety mechanism)") + coarse := flag.Int("coarse", 0, "decimation for the candidate search; 0 uses the default, 1 searches at full resolution") + flag.Parse() + + files := flag.Args() + if len(files) == 0 { + fmt.Fprintln(os.Stderr, "usage: listen-detect [flags] ...") + flag.PrintDefaults() + os.Exit(2) + } + + cfg := skips.DefaultConfig() + cfg.ClipSeconds = *clipSeconds + cfg.ReferenceSeconds = *referenceSeconds + cfg.ConfirmThreshold = *threshold + if *coarse > 0 { + cfg.Tuning.CoarseFactor = *coarse + } + + episodes := make([]skips.Episode, 0, len(files)) + for _, f := range files { + episodes = append(episodes, skips.Episode{ID: filepath.Base(f), Path: f}) + } + + decoder := decode.Decoder{} + ctx := context.Background() + + fmt.Printf("%d episodes, %ds windows, %ds reference, confirm on %d, coarse factor %d\n\n", + len(episodes), cfg.ClipSeconds, cfg.ReferenceSeconds, cfg.ConfirmThreshold, cfg.Tuning.CoarseFactor) + + for _, ep := range episodes { + ms, err := decoder.DurationMs(ctx, ep.Path) + if err != nil { + fmt.Fprintf(os.Stderr, "%s: %v\n", ep.ID, err) + os.Exit(1) + } + fmt.Printf(" %-44s %s\n", ep.ID, clock(ms)) + } + + started := time.Now() + result, err := skips.Detect(ctx, decoder, episodes, cfg) + if err != nil { + fmt.Fprintln(os.Stderr, err) + os.Exit(1) + } + elapsed := time.Since(started) + + fmt.Printf("\nintro: confirmed on %d of %d episodes%s\n", + result.IntroConfirmedOn, len(episodes), verdict(result.IntroCheck)) + fmt.Printf("outro: confirmed on %d of %d episodes%s\n", + result.OutroConfirmedOn, len(episodes), verdict(result.OutroCheck)) + fmt.Printf("detection took %s\n\n", elapsed.Round(time.Millisecond)) + + fmt.Printf(" %-44s %-14s %s\n", "episode", "skip intro to", "end early by") + for _, o := range result.Offsets { + fmt.Printf(" %-44s %-14s %s\n", o.EpisodeID, optional(o.IntroMs), optional(o.OutroMs)) + } + + // Non-zero when a confirmation could not verify itself, so this is usable as a check and + // not only as a report. + if !result.IntroCheck.OK || !result.OutroCheck.OK { + fmt.Fprintln(os.Stderr, "\nat least one confirmation failed its self-check; no offsets published for it") + os.Exit(1) + } +} + +// verdict describes whether the located segments agreed with each other -- a different and +// stricter question than the detection threshold, and the one that says the answer is real. +func verdict(r skips.CheckReport) string { + if r.Pairs == 0 { + return "" + } + if r.OK { + return fmt.Sprintf("; self-check passed on %d pairs, worst r=%.4f", r.Pairs, r.WorstScore) + } + return fmt.Sprintf("; SELF-CHECK FAILED: %s vs %s at r=%.4f -- offsets withheld", + r.WorstA, r.WorstB, r.WorstScore) +} + +func optional(ms *int64) string { + if ms == nil { + return "-" + } + return clock(*ms) +} + +// clock renders a duration to the millisecond. Not to the nearest second: an offset read back +// at second precision is out by up to half a second, which is enough to make the same audio +// look like different audio, and that cost real time the first time this was checked by hand. +func clock(ms int64) string { + total := ms / 1000 + if h := total / 3600; h > 0 { + return fmt.Sprintf("%d:%02d:%02d.%03d", h, total/60%60, total%60, ms%1000) + } + return fmt.Sprintf("%d:%02d.%03d", total/60, total%60, ms%1000) +} diff --git a/server/go.mod b/server/go.mod new file mode 100644 index 0000000..63508e0 --- /dev/null +++ b/server/go.mod @@ -0,0 +1,3 @@ +module github.com/terst/listen/server + +go 1.22 diff --git a/server/internal/decode/decode.go b/server/internal/decode/decode.go new file mode 100644 index 0000000..12ec204 --- /dev/null +++ b/server/internal/decode/decode.go @@ -0,0 +1,123 @@ +// Package decode turns an audio file into the mono PCM the detector works on. +package decode + +import ( + "bytes" + "context" + "encoding/binary" + "fmt" + "math" + "os/exec" + "strconv" + "strings" + "time" +) + +// TargetSampleRate is what every clip is decoded to, whatever the file was encoded at. +// +// 8kHz is plenty of signal for a spoken or musical sting, and a fixed rate means the detector +// never has to care what an episode's own encoding was. +const TargetSampleRate = 8000 + +// Clip is decoded mono audio and where it starts in the file it came from. +type Clip struct { + Samples []float64 + SampleRate int + StartMs int64 +} + +// Decoder decodes audio by shelling out to ffmpeg, the same way podkit shells out to yt-dlp. +// +// ffmpeg rather than a Go decoder: it handles every container and codec a podcast CDN might +// serve, including the ones that turn up once. Replacing the phone's MediaCodec with it is the +// only platform-specific part of moving detection to a server -- and unlike MediaCodec it has +// no per-process Java heap to run out of, which is what made whole-episode decoding impossible +// on the phone. +type Decoder struct { + // FFmpegDir is the directory holding ffmpeg and ffprobe. Empty means look them up on PATH. + FFmpegDir string + // Timeout bounds a single decode. Zero means DefaultTimeout. + Timeout time.Duration +} + +// DefaultTimeout is generous on purpose: decoding a three-hour episode is legitimate work, and +// the server has no equivalent of the ten-minute ceiling that killed this on the phone. +const DefaultTimeout = 10 * time.Minute + +// Range decodes durationMs of audio starting at startMs. A durationMs of zero decodes to the +// end of the file. +// +// Decoding a range rather than always the whole file is what lets a caller verify one candidate +// segment at full resolution without holding an entire episode in memory. +func (d Decoder) Range(ctx context.Context, path string, startMs, durationMs int64) (*Clip, error) { + args := []string{"-nostdin", "-hide_banner", "-loglevel", "error"} + if startMs > 0 { + args = append(args, "-ss", millisToTimestamp(startMs)) + } + args = append(args, "-i", path) + if durationMs > 0 { + args = append(args, "-t", millisToTimestamp(durationMs)) + } + // f64le straight out, so nothing downstream has to reinterpret or rescale it. + args = append(args, "-vn", "-ac", "1", "-ar", strconv.Itoa(TargetSampleRate), "-f", "f64le", "-") + + timeout := d.Timeout + if timeout == 0 { + timeout = DefaultTimeout + } + ctx, cancel := context.WithTimeout(ctx, timeout) + defer cancel() + + cmd := exec.CommandContext(ctx, d.tool("ffmpeg"), args...) + var out, errOut bytes.Buffer + cmd.Stdout = &out + cmd.Stderr = &errOut + if err := cmd.Run(); err != nil { + return nil, fmt.Errorf("decode %s: %w: %s", path, err, strings.TrimSpace(errOut.String())) + } + + samples, err := readFloat64LE(out.Bytes()) + if err != nil { + return nil, fmt.Errorf("decode %s: %w", path, err) + } + return &Clip{Samples: samples, SampleRate: TargetSampleRate, StartMs: startMs}, nil +} + +// DurationMs reports a file's real length, which is routinely not what its feed claims -- +// Radiolab declares one episode at 22:05 and serves 27 to 30 minutes of it. +func (d Decoder) DurationMs(ctx context.Context, path string) (int64, error) { + cmd := exec.CommandContext(ctx, d.tool("ffprobe"), + "-v", "error", "-show_entries", "format=duration", + "-of", "default=noprint_wrappers=1:nokey=1", path) + out, err := cmd.Output() + if err != nil { + return 0, fmt.Errorf("probe %s: %w", path, err) + } + seconds, err := strconv.ParseFloat(strings.TrimSpace(string(out)), 64) + if err != nil { + return 0, fmt.Errorf("probe %s: unparseable duration %q: %w", path, out, err) + } + return int64(math.Round(seconds * 1000)), nil +} + +func (d Decoder) tool(name string) string { + if d.FFmpegDir == "" { + return name + } + return strings.TrimSuffix(d.FFmpegDir, "/") + "/" + name +} + +func readFloat64LE(raw []byte) ([]float64, error) { + if len(raw)%8 != 0 { + return nil, fmt.Errorf("got %d bytes, not a whole number of float64 samples", len(raw)) + } + out := make([]float64, len(raw)/8) + for i := range out { + out[i] = math.Float64frombits(binary.LittleEndian.Uint64(raw[i*8:])) + } + return out, nil +} + +func millisToTimestamp(ms int64) string { + return fmt.Sprintf("%d.%03d", ms/1000, ms%1000) +} diff --git a/server/internal/decode/decode_test.go b/server/internal/decode/decode_test.go new file mode 100644 index 0000000..fea4e85 --- /dev/null +++ b/server/internal/decode/decode_test.go @@ -0,0 +1,164 @@ +package decode + +import ( + "context" + "fmt" + "math" + "os" + "os/exec" + "path/filepath" + "testing" +) + +// These run against real ffmpeg on generated audio of known content, so the decode is checked +// against something independently true rather than against itself. A wrong sample format or a +// byte-order mistake would otherwise read as plausible noise and sail through. + +func requireFFmpeg(t *testing.T) { + t.Helper() + if _, err := exec.LookPath("ffmpeg"); err != nil { + t.Skip("ffmpeg not on PATH") + } +} + +// writeTone generates a pure sine of the given frequency and length, using ffmpeg itself. +func writeTone(t *testing.T, hz, seconds int) string { + t.Helper() + path := filepath.Join(t.TempDir(), "tone.wav") + cmd := exec.Command("ffmpeg", "-nostdin", "-hide_banner", "-loglevel", "error", + "-f", "lavfi", "-i", fmt.Sprintf("sine=frequency=%d:duration=%d", hz, seconds), + "-ac", "1", "-ar", "44100", path) + if out, err := cmd.CombinedOutput(); err != nil { + t.Fatalf("generating fixture: %v: %s", err, out) + } + return path +} + +func TestDecodesToTheTargetRateAndLength(t *testing.T) { + requireFFmpeg(t) + path := writeTone(t, 440, 2) + + clip, err := Decoder{}.Range(context.Background(), path, 0, 0) + if err != nil { + t.Fatal(err) + } + if clip.SampleRate != TargetSampleRate { + t.Errorf("sample rate %d, want %d", clip.SampleRate, TargetSampleRate) + } + // Two seconds at 8kHz, allowing a frame of slack at the boundary. + if len(clip.Samples) < 2*TargetSampleRate-256 || len(clip.Samples) > 2*TargetSampleRate+256 { + t.Errorf("got %d samples, want about %d", len(clip.Samples), 2*TargetSampleRate) + } +} + +// A 440Hz sine decoded down to 8kHz must still be a 440Hz sine at full scale. +func TestDecodedAudioIsTheToneThatWentIn(t *testing.T) { + requireFFmpeg(t) + path := writeTone(t, 440, 2) + + clip, err := Decoder{}.Range(context.Background(), path, 0, 0) + if err != nil { + t.Fatal(err) + } + + // A 440Hz sine crosses zero 880 times a second. + crossings := 0 + window := clip.Samples[TargetSampleRate/2 : TargetSampleRate/2+TargetSampleRate] + for i := 1; i < len(window); i++ { + if (window[i-1] < 0) != (window[i] < 0) { + crossings++ + } + } + if crossings < 860 || crossings > 900 { + t.Errorf("%d zero crossings per second, want about 880 for a 440Hz tone", crossings) + } + + // Amplitude, checked by a property of the signal rather than an absolute level: a pure + // sine has an RMS of peak/sqrt(2) whatever its loudness. That catches the failure mode + // worth catching -- reading the bytes as the wrong format or byte order, which produces + // values that are individually plausible but have no sinusoidal structure -- without + // depending on how loud ffmpeg's sine filter happens to be. (It is -18 dBFS, not full + // scale, which is what this assertion originally got wrong.) + peak, sumSquares := 0.0, 0.0 + for _, v := range clip.Samples { + if math.IsNaN(v) || math.IsInf(v, 0) { + t.Fatalf("decoded a non-finite sample: %v", v) + } + peak = math.Max(peak, math.Abs(v)) + sumSquares += v * v + } + if peak <= 0 || peak > 1.0 { + t.Errorf("peak amplitude %v, want within (0, 1] for normalised float PCM", peak) + } + rms := math.Sqrt(sumSquares / float64(len(clip.Samples))) + if ratio := rms / peak; ratio < 0.65 || ratio > 0.74 { + t.Errorf("rms/peak = %.3f, want about %.3f (1/sqrt2) for a pure sine", ratio, 1/math.Sqrt2) + } +} + +func TestRangeStartsWhereAsked(t *testing.T) { + requireFFmpeg(t) + path := writeTone(t, 440, 4) + + clip, err := Decoder{}.Range(context.Background(), path, 2000, 1000) + if err != nil { + t.Fatal(err) + } + if clip.StartMs != 2000 { + t.Errorf("StartMs %d, want 2000", clip.StartMs) + } + if len(clip.Samples) < TargetSampleRate-256 || len(clip.Samples) > TargetSampleRate+256 { + t.Errorf("got %d samples, want about %d for one second", len(clip.Samples), TargetSampleRate) + } +} + +// Ranges have to be positioned correctly, not merely the right length: a 220Hz second followed +// by a 880Hz second, asked for one second in, must come back as the 880Hz half. +func TestRangeReturnsTheAudioAtThatOffsetNotJustTheRightAmount(t *testing.T) { + requireFFmpeg(t) + dir := t.TempDir() + path := filepath.Join(dir, "two.wav") + cmd := exec.Command("ffmpeg", "-nostdin", "-hide_banner", "-loglevel", "error", + "-f", "lavfi", "-i", "sine=frequency=220:duration=1", + "-f", "lavfi", "-i", "sine=frequency=880:duration=1", + "-filter_complex", "[0:a][1:a]concat=n=2:v=0:a=1", + "-ac", "1", "-ar", "44100", path) + if out, err := cmd.CombinedOutput(); err != nil { + t.Fatalf("generating fixture: %v: %s", err, out) + } + + clip, err := Decoder{}.Range(context.Background(), path, 1100, 700) + if err != nil { + t.Fatal(err) + } + crossings := 0 + for i := 1; i < len(clip.Samples); i++ { + if (clip.Samples[i-1] < 0) != (clip.Samples[i] < 0) { + crossings++ + } + } + perSecond := float64(crossings) * float64(TargetSampleRate) / float64(len(clip.Samples)) + if perSecond < 1700 || perSecond > 1860 { + t.Errorf("%.0f zero crossings per second, want about 1760 (880Hz) -- wrong offset decoded", perSecond) + } +} + +func TestReportsTheRealDuration(t *testing.T) { + requireFFmpeg(t) + path := writeTone(t, 440, 3) + + ms, err := Decoder{}.DurationMs(context.Background(), path) + if err != nil { + t.Fatal(err) + } + if ms < 2900 || ms > 3100 { + t.Errorf("duration %dms, want about 3000", ms) + } +} + +func TestAMissingFileIsAnError(t *testing.T) { + requireFFmpeg(t) + if _, err := (Decoder{}).Range(context.Background(), filepath.Join(os.TempDir(), "nope.mp3"), 0, 0); err == nil { + t.Error("expected an error for a missing file") + } +} diff --git a/server/internal/detect/correlate.go b/server/internal/detect/correlate.go new file mode 100644 index 0000000..5d9c9dd --- /dev/null +++ b/server/internal/detect/correlate.go @@ -0,0 +1,182 @@ +package detect + +import "math" + +// minQueryEnergy is the floor below which a signal carries nothing to correlate against. +// Silence has an undefined correlation with anything. +const minQueryEnergy = 1e-6 + +// Match is where a query best aligns inside a target, and how strongly. +type Match struct { + Position int + Score float64 +} + +// PreparedTarget holds the half of a correlation that does not depend on the query's contents: +// the target's transform and its rolling sums. A window search correlates many queries against +// one unchanged target, and recomputing this for each of them is most of what made the +// on-device search unaffordable. +// +// Valid only for queries of exactly QuerySize samples. The transform is zero-padded to a length +// chosen for that size, so reusing it at another length would not be a slower correct answer, +// it would be a wrong one. +type PreparedTarget struct { + TargetSize int + QuerySize int + + transformRe []float64 + transformIm []float64 + localSum []float64 + localSumSq []float64 +} + +// PrepareTarget precomputes what BestMatchPrepared needs for queries of querySize samples. +// +// A querySize that cannot fit yields a prepared target that reports no match, so callers do not +// have to duplicate the bounds check. +func PrepareTarget(target []float64, querySize int) *PreparedTarget { + if querySize <= 0 || querySize > len(target) { + return &PreparedTarget{TargetSize: len(target), QuerySize: querySize} + } + n := NextPowerOfTwo(len(target) + querySize - 1) + re := make([]float64, n) + copy(re, target) + im := make([]float64, n) + Transform(re, im, false) + + squares := make([]float64, len(target)) + for i, v := range target { + squares[i] = v * v + } + + return &PreparedTarget{ + TargetSize: len(target), + QuerySize: querySize, + transformRe: re, + transformIm: im, + localSum: rollingSum(target, querySize), + localSumSq: rollingSum(squares, querySize), + } +} + +// BestMatch reports where query best aligns inside target. +// +// Nil when there is nowhere valid to place the query (it is longer than the target) or the query +// carries no signal to match against. +func BestMatch(query, target []float64) *Match { + return BestMatchPrepared(query, PrepareTarget(target, len(query))) +} + +// BestMatchPrepared is BestMatch against a target prepared once by PrepareTarget. +func BestMatchPrepared(query []float64, target *PreparedTarget) *Match { + scores := NormalizedCrossCorrelation(query, target) + if len(scores) == 0 { + return nil + } + best := 0 + for i := 1; i < len(scores); i++ { + if scores[i] > scores[best] { + best = i + } + } + return &Match{Position: best, Score: scores[best]} +} + +// NormalizedCrossCorrelation returns a Pearson correlation coefficient at every valid alignment +// of query inside the prepared target: scores[i] correlates query against +// target[i : i+len(query)]. +// +// The normalization is the part that matters as much as the FFT: each window is correlated +// against its own local mean and variance, not the whole recording's. Centering the target once +// up front instead produces plausible but bogus scores -- a 0.98 for a correlation that plain +// arithmetic puts at -0.02 -- and that is the bug the pinned numpy fixtures exist to catch. +// +// Derivation: let q be query mean-centered. For a window at offset i, the covariance numerator +// sum((target[i+k] - localMean) * q[k]) equals sum(target[i+k] * q[k]) with target left raw, +// because sum(q) is zero. That sum as a function of i is the "valid" part of convolving target +// with the reverse of q, which is what makes the FFT applicable. The denominator comes from +// rolling sums and needs no transform. +// +// Nil (empty) under the same conditions as BestMatch. +func NormalizedCrossCorrelation(query []float64, target *PreparedTarget) []float64 { + win := len(query) + if win == 0 || win > target.TargetSize || win != target.QuerySize { + return nil + } + + mean := 0.0 + for _, v := range query { + mean += v + } + mean /= float64(win) + + centered := make([]float64, win) + norm := 0.0 + for i, v := range query { + centered[i] = v - mean + norm += centered[i] * centered[i] + } + norm = math.Sqrt(norm) + if norm < minQueryEnergy { + return nil + } + + // Reversed, because correlation is convolution with a reversed kernel. + kernel := make([]float64, win) + for i := range centered { + kernel[i] = centered[win-1-i] + } + + dot := validConvolution(target, kernel) + scores := make([]float64, len(dot)) + for i := range dot { + localMean := target.localSum[i] / float64(win) + variance := target.localSumSq[i]/float64(win) - localMean*localMean + if variance < 0 { + variance = 0 + } + denom := math.Sqrt(variance*float64(win)) * norm + if denom < minQueryEnergy { + scores[i] = 0 + } else { + scores[i] = dot[i] / denom + } + } + return scores +} + +// validConvolution returns the fully-overlapped slice of convolving the prepared target with +// kernel. Two transforms, not three: the target's was done by PrepareTarget. +func validConvolution(target *PreparedTarget, kernel []float64) []float64 { + n := len(target.transformRe) + kRe := make([]float64, n) + copy(kRe, kernel) + kIm := make([]float64, n) + Transform(kRe, kIm, false) + + for i := 0; i < n; i++ { + re := target.transformRe[i]*kRe[i] - target.transformIm[i]*kIm[i] + im := target.transformRe[i]*kIm[i] + target.transformIm[i]*kRe[i] + kRe[i], kIm[i] = re, im + } + Transform(kRe, kIm, true) + + out := make([]float64, target.TargetSize-len(kernel)+1) + for i := range out { + out[i] = kRe[i+len(kernel)-1] + } + return out +} + +// rollingSum returns the sum of each win-long window of a, one per valid starting offset. +func rollingSum(a []float64, win int) []float64 { + prefix := make([]float64, len(a)+1) + for i, v := range a { + prefix[i+1] = prefix[i] + v + } + out := make([]float64, len(a)-win+1) + for i := range out { + out[i] = prefix[i+win] - prefix[i] + } + return out +} diff --git a/server/internal/detect/correlate_test.go b/server/internal/detect/correlate_test.go new file mode 100644 index 0000000..af06b55 --- /dev/null +++ b/server/internal/detect/correlate_test.go @@ -0,0 +1,140 @@ +package detect + +import ( + "math" + "math/rand" + "testing" +) + +// The scores below are numpy's, pinned as literals. They are the same values +// AudioCorrelationTest asserts in Kotlin, so Go and Kotlin are each checked against real +// signal-processing math rather than against one another. + +func TestSelfMatchScoresOneAtTheOnlyValidPosition(t *testing.T) { + m := BestMatch(sting, sting) + if m == nil { + t.Fatal("expected a match") + } + if m.Position != 0 { + t.Errorf("position = %d, want 0", m.Position) + } + if math.Abs(m.Score-1.0) > 1e-6 { + t.Errorf("score = %v, want 1.0", m.Score) + } +} + +func TestFindsEmbeddedStingAtNumpysPositionAndScore(t *testing.T) { + m := BestMatch(sting, targetWithMatch) + if m == nil { + t.Fatal("expected a match") + } + if m.Position != 120 { + t.Errorf("position = %d, want 120", m.Position) + } + if math.Abs(m.Score-0.9998959789695058) > 1e-6 { + t.Errorf("score = %v, want 0.9998959789695058", m.Score) + } +} + +// The case that catches a global-mean normalization bug: an unrelated target must score far +// below the match, not plausibly near it. +func TestUnrelatedTargetScoresNumpysLowValue(t *testing.T) { + m := BestMatch(sting, targetNoMatch) + if m == nil { + t.Fatal("expected a best-effort match even with no real signal") + } + if math.Abs(m.Score-0.3672490793439344) > 1e-6 { + t.Errorf("score = %v, want 0.3672490793439344", m.Score) + } +} + +func TestQueryLongerThanTargetHasNowhereToMatch(t *testing.T) { + if m := BestMatch(targetWithMatch, sting); m != nil { + t.Errorf("expected nil, got %+v", m) + } +} + +func TestSilentQueryHasNoMeaningfulCorrelation(t *testing.T) { + if m := BestMatch(make([]float64, 40), targetWithMatch); m != nil { + t.Errorf("expected nil for a silent query, got %+v", m) + } +} + +// The optimisation that made the Kotlin search affordable: the target's transform does not +// depend on the query, so a window search prepares it once. It must give identical answers. +func TestPreparedTargetMatchesOneShot(t *testing.T) { + prepared := PrepareTarget(targetWithMatch, len(sting)) + one := BestMatch(sting, targetWithMatch) + reused := BestMatchPrepared(sting, prepared) + if one == nil || reused == nil { + t.Fatal("expected both to match") + } + if one.Position != reused.Position || math.Abs(one.Score-reused.Score) > 1e-12 { + t.Errorf("prepared (%d,%v) != one-shot (%d,%v)", reused.Position, reused.Score, one.Position, one.Score) + } +} + +func TestPreparedTargetRejectsWrongQueryLength(t *testing.T) { + prepared := PrepareTarget(targetWithMatch, len(sting)) + if m := BestMatchPrepared(make([]float64, len(sting)+1), prepared); m != nil { + t.Errorf("expected nil for a mismatched query length, got %+v", m) + } +} + +// A brute-force normalized correlation computed straight from the Pearson definition. The FFT +// path is an optimisation of exactly this, so where they disagree the FFT path is wrong. +func directNormalizedScores(query, target []float64) []float64 { + win := len(query) + qMean := 0.0 + for _, v := range query { + qMean += v + } + qMean /= float64(win) + qNorm := 0.0 + for _, v := range query { + qNorm += (v - qMean) * (v - qMean) + } + qNorm = math.Sqrt(qNorm) + + out := make([]float64, len(target)-win+1) + for i := range out { + wMean := 0.0 + for k := 0; k < win; k++ { + wMean += target[i+k] + } + wMean /= float64(win) + cov, wNorm := 0.0, 0.0 + for k := 0; k < win; k++ { + d := target[i+k] - wMean + cov += d * (query[k] - qMean) + wNorm += d * d + } + wNorm = math.Sqrt(wNorm) + if wNorm*qNorm < 1e-6 { + out[i] = 0 + } else { + out[i] = cov / (wNorm * qNorm) + } + } + return out +} + +func TestFFTPathAgreesWithDirectPearsonCorrelation(t *testing.T) { + rng := rand.New(rand.NewSource(3)) + target := make([]float64, 900) + for i := range target { + target[i] = rng.NormFloat64() * 50 + } + query := append([]float64(nil), target[300:340]...) + + want := directNormalizedScores(query, target) + got := NormalizedCrossCorrelation(query, PrepareTarget(target, len(query))) + if len(got) != len(want) { + t.Fatalf("length %d, want %d", len(got), len(want)) + } + for i := range want { + if math.Abs(got[i]-want[i]) > 1e-9 { + t.Fatalf("offset %d: fft gave %v, direct gave %v", i, got[i], want[i]) + } + } +} diff --git a/server/internal/detect/decimate.go b/server/internal/detect/decimate.go new file mode 100644 index 0000000..fbcae98 --- /dev/null +++ b/server/internal/detect/decimate.go @@ -0,0 +1,22 @@ +package detect + +// Decimate downsamples by averaging fixed-size blocks rather than dropping samples. +// +// Only a cheap pre-filter ahead of a coarse alignment search: averaging keeps the signal's +// overall shape, which is all a coarse search needs, where keeping every Nth sample would +// alias. Correctness of the real match still comes from re-checking at full resolution. +func Decimate(samples []float64, factor int) []float64 { + if factor <= 1 { + return samples + } + out := make([]float64, len(samples)/factor) + for i := range out { + sum := 0.0 + base := i * factor + for j := 0; j < factor; j++ { + sum += samples[base+j] + } + out[i] = sum / float64(factor) + } + return out +} diff --git a/server/internal/detect/decimate_test.go b/server/internal/detect/decimate_test.go new file mode 100644 index 0000000..dca3984 --- /dev/null +++ b/server/internal/detect/decimate_test.go @@ -0,0 +1,35 @@ +package detect + +import ( + "math" + "testing" +) + +func TestDecimateAveragesBlocksRatherThanDroppingSamples(t *testing.T) { + got := Decimate([]float64{1, 3, 5, 7, 9, 11}, 2) + want := []float64{2, 6, 10} + if len(got) != len(want) { + t.Fatalf("length %d, want %d", len(got), len(want)) + } + for i := range want { + if math.Abs(got[i]-want[i]) > 1e-9 { + t.Errorf("index %d: got %v, want %v", i, got[i], want[i]) + } + } +} + +func TestDecimateByOneIsIdentity(t *testing.T) { + in := []float64{1, 2, 3} + got := Decimate(in, 1) + for i := range in { + if got[i] != in[i] { + t.Errorf("index %d changed", i) + } + } +} + +func TestDecimateDropsAnIncompleteTrailingBlock(t *testing.T) { + if got := Decimate([]float64{1, 2, 3, 4, 5}, 2); len(got) != 2 { + t.Errorf("length %d, want 2", len(got)) + } +} diff --git a/server/internal/detect/fft.go b/server/internal/detect/fft.go new file mode 100644 index 0000000..7c79e96 --- /dev/null +++ b/server/internal/detect/fft.go @@ -0,0 +1,76 @@ +package detect + +import "math" + +// NextPowerOfTwo returns the smallest power of two at or above n. +func NextPowerOfTwo(n int) int { + p := 1 + for p < n { + p <<= 1 + } + return p +} + +// Transform computes an in-place radix-2 Cooley-Tukey FFT (or its inverse) of a complex signal +// given as parallel real and imaginary slices. len(re) must be a power of two. +// +// Twiddle factors are computed once per (stage, k) and reused across every block at that +// stage, rather than once per butterfly. The Kotlin version recomputes them per butterfly -- +// (n/2)*log2(n) sin+cos calls against this version's n-1 -- which measured as not mattering +// there, because the JVM compiles those to hardware intrinsics and memory traffic dominates +// anyway. Done properly here because there is no reason not to. +func Transform(re, im []float64, inverse bool) { + n := len(re) + if n <= 1 { + return + } + if n&(n-1) != 0 { + panic("detect: FFT length must be a power of two") + } + bitReverse(re, im) + + sign := -1.0 + if inverse { + sign = 1.0 + } + for size := 2; size <= n; size <<= 1 { + half := size / 2 + step := sign * 2 * math.Pi / float64(size) + for k := 0; k < half; k++ { + wRe := math.Cos(step * float64(k)) + wIm := math.Sin(step * float64(k)) + for start := 0; start < n; start += size { + i, j := start+k, start+k+half + oddRe := re[j]*wRe - im[j]*wIm + oddIm := re[j]*wIm + im[j]*wRe + evenRe, evenIm := re[i], im[i] + re[i], im[i] = evenRe+oddRe, evenIm+oddIm + re[j], im[j] = evenRe-oddRe, evenIm-oddIm + } + } + } + + if inverse { + for i := range re { + re[i] /= float64(n) + im[i] /= float64(n) + } + } +} + +func bitReverse(re, im []float64) { + n := len(re) + j := 0 + for i := 0; i < n; i++ { + if i < j { + re[i], re[j] = re[j], re[i] + im[i], im[j] = im[j], im[i] + } + bit := n >> 1 + for bit != 0 && j&bit != 0 { + j ^= bit + bit >>= 1 + } + j ^= bit + } +} diff --git a/server/internal/detect/fft_test.go b/server/internal/detect/fft_test.go new file mode 100644 index 0000000..4487ddf --- /dev/null +++ b/server/internal/detect/fft_test.go @@ -0,0 +1,78 @@ +package detect + +import ( + "math" + "math/rand" + "testing" +) + +// The FFT is the one piece with no ground truth to borrow, so it is checked against the +// properties that actually matter: that it inverts itself, and that it agrees with a direct +// DFT computed from the definition. A transform that is self-consistent but wrong would sail +// past the first check and fail the second. + +func TestInverseUndoesForward(t *testing.T) { + n := 1024 + rng := rand.New(rand.NewSource(1)) + re := make([]float64, n) + im := make([]float64, n) + for i := range re { + re[i] = rng.NormFloat64() + } + wantRe := append([]float64(nil), re...) + + Transform(re, im, false) + Transform(re, im, true) + + for i := range re { + if math.Abs(re[i]-wantRe[i]) > 1e-9 { + t.Fatalf("sample %d: round trip gave %v, want %v", i, re[i], wantRe[i]) + } + if math.Abs(im[i]) > 1e-9 { + t.Fatalf("sample %d: round trip left imaginary residue %v", i, im[i]) + } + } +} + +// A direct DFT from the textbook definition, deliberately the slow way. +func naiveDFT(re, im []float64) ([]float64, []float64) { + n := len(re) + outRe := make([]float64, n) + outIm := make([]float64, n) + for k := 0; k < n; k++ { + for j := 0; j < n; j++ { + angle := -2 * math.Pi * float64(k) * float64(j) / float64(n) + c, s := math.Cos(angle), math.Sin(angle) + outRe[k] += re[j]*c - im[j]*s + outIm[k] += re[j]*s + im[j]*c + } + } + return outRe, outIm +} + +func TestForwardAgreesWithDirectDFT(t *testing.T) { + n := 64 + rng := rand.New(rand.NewSource(2)) + re := make([]float64, n) + im := make([]float64, n) + for i := range re { + re[i] = rng.NormFloat64() + } + wantRe, wantIm := naiveDFT(re, im) + + Transform(re, im, false) + + for k := 0; k < n; k++ { + if math.Abs(re[k]-wantRe[k]) > 1e-9 || math.Abs(im[k]-wantIm[k]) > 1e-9 { + t.Fatalf("bin %d: got (%v,%v), want (%v,%v)", k, re[k], im[k], wantRe[k], wantIm[k]) + } + } +} + +func TestNextPowerOfTwo(t *testing.T) { + for _, c := range []struct{ in, want int }{{1, 1}, {2, 2}, {3, 4}, {1000, 1024}, {1024, 1024}, {1025, 2048}} { + if got := NextPowerOfTwo(c.in); got != c.want { + t.Errorf("NextPowerOfTwo(%d) = %d, want %d", c.in, got, c.want) + } + } +} diff --git a/server/internal/detect/fixtures_test.go b/server/internal/detect/fixtures_test.go new file mode 100644 index 0000000..c70d6f5 --- /dev/null +++ b/server/internal/detect/fixtures_test.go @@ -0,0 +1,128 @@ +package detect + +// Ground-truth fixtures, extracted mechanically from the Kotlin +// AudioCorrelationTest by tools/extract_fixtures.py -- NOT retyped. +// +// They originate in numpy/scipy: the desktop prototype these were computed with is the same +// tool the whole detection design was validated against, and the expected scores below are +// pinned as literals so this Go port is checked against real signal-processing math rather +// than against itself. The Kotlin port's first version got the normalization wrong -- it +// centered the target on its global mean instead of each window's own local mean -- and +// reported a plausible 0.98 for a correlation that was really -0.02. These fixtures are what +// caught it, so they come along to every reimplementation. + +var sting = []float64{ + 32.486907, 220.126458, 400.928498, 474.895065, 484.816274, 285.530555, + 154.554067, -134.88197, -325.180547, -472.495529, -467.112278, -452.694747, + -238.80993, -7.681087, 255.036975, 389.494108, 492.905873, 449.950953, + 332.405604, 131.314136, -141.670216, -308.666855, -449.476307, -486.30455, + -393.474814, -246.036143, -2.457805, 213.646197, 406.134171, 506.961546, + 453.674906, 323.626259, 105.914378, -136.561945, -344.986252, -467.761413, + -518.700644, -406.803619, -199.165542, 14.840883, +} + +var targetWithMatch = []float64{ + -20.837892, -2.813341, -106.809805, 82.01354, -89.671779, -42.087368, + 25.144071, -62.264404, -52.897611, -45.450381, 27.572702, 114.610401, + 2.07697, -55.896272, 26.952916, -29.807985, -0.956525, 58.750061, + -37.393547, 0.451263, -43.905395, -7.821709, 12.828523, -49.438952, + -16.941098, -11.809202, -31.882751, -59.380614, -71.060861, -7.67476, + -13.452848, 111.568339, -121.738379, 5.636325, 18.522227, 67.981693, + 25.09286, -42.210685, 0.000488, 27.117629, -15.67541, 38.550587, + -93.404533, 86.559233, 73.383901, -16.783867, 30.567039, 2.39853, + -41.456764, 4.385511, 50.018294, -19.054626, -18.783471, -3.723538, + 21.674817, 63.918962, -31.733965, 25.419812, 10.8058, -92.930619, + -20.965824, -6.616445, -1.978512, 16.300172, -102.016152, 2.312776, + -33.883779, -71.971951, 26.214822, 36.763979, -32.662513, 42.122814, + -19.075824, 3.32445, -54.936947, 79.224353, -132.972473, -4.572631, + 34.75598, -101.673327, -9.473463, -3.860933, 41.23515, 62.410646, + -20.194613, -69.225933, 68.361771, 60.894282, -23.100267, 17.544425, + 19.093312, 28.313772, 10.210399, 70.334812, -86.897975, 52.041198, + 19.023599, -10.856763, 58.676575, -117.18016, 58.076075, 19.303902, + -56.656664, 21.654628, -15.204322, 129.264743, 91.766636, 22.034494, + -35.962692, -29.17073, -16.252481, -28.011725, -45.112303, -29.548614, + -13.808975, -25.844195, -34.929497, -46.444596, 127.521912, -73.658662, + 41.43005, 222.309007, 401.410985, 465.577601, 483.429333, 283.75676, + 154.14036, -138.016974, -325.399638, -474.881619, -473.681602, -448.271635, + -234.40334, 0.866778, 255.287143, 387.470721, 490.179073, 442.218566, + 337.317441, 125.808798, -147.595448, -309.695104, -442.045565, -485.120969, + -398.59374, -249.601109, 0.66842, 212.843631, 402.28999, 505.811393, + 457.400188, 333.506812, 99.693761, -139.69403, -349.005082, -479.856829, + -523.319604, -411.922998, -193.545653, 14.181312, -62.771361, 46.908184, + -23.417313, -62.736015, 6.241182, 37.825107, 12.071981, 24.871282, + 205.434631, 41.056044, 76.588016, -99.292289, 18.252676, 38.704102, + -18.223955, -43.798974, 19.826008, -15.730872, -29.687779, 57.475028, + 66.778308, 15.131467, -22.711393, 25.718536, 41.472922, 31.531098, + -72.668217, -16.900889, 17.956667, 31.111021, 48.039097, 37.918517, + -56.715924, -35.371044, -61.071458, 90.223832, 9.02049, 27.658214, + 51.651453, -16.450122, -57.550147, -21.326124, -7.40736, 75.071846, + 43.47991, -54.354529, 33.211071, 36.744233, -53.068287, -5.425841, + -92.520199, 16.524403, -15.784661, -67.500105, -34.90855, 11.99756, + -27.647472, 14.976341, 27.633185, -42.022151, -15.613533, 107.233904, + 6.055279, -42.341438, 3.023122, -66.929444, 56.637304, 18.515242, + 54.29032, 45.10897, 19.514822, 48.775471, 9.578682, -33.110451, + -51.175749, -22.408741, -125.272907, 91.299723, -85.703371, -3.831978, + -65.878363, -101.27968, -4.112269, -15.233329, -7.986207, 27.447328, + -30.918774, 18.939723, 25.662572, -16.742206, -14.175976, 26.921213, + 2.862547, 7.954424, -118.720134, 2.925997, 18.827296, -6.773988, + 16.79542, 95.218795, 4.268222, 33.266714, -42.499775, -42.61709, + -23.999256, -50.982455, -0.380057, -46.691533, -8.749842, -71.857172, + -82.610015, -33.783089, -53.353356, -32.646557, -30.604738, -17.563123, + 52.273899, 68.450801, 36.267663, -17.973723, 74.847589, -76.555555, + -101.168197, 13.398629, -0.110322, -6.964594, 1.628273, -82.028011, + -57.834959, 61.701734, 51.409245, -36.093986, 96.657848, -53.539816, + -28.56908, 14.621603, -59.749995, -24.396527, -8.653558, -19.76732, +} + +var targetNoMatch = []float64{ + 2.528085, 24.997567, -49.795447, 34.679925, -20.915076, -79.228862, + -32.385338, 29.928759, 16.612502, -57.373832, 30.933484, -4.399346, + 21.25362, 16.612657, -57.840813, 17.549858, -30.344364, 77.348966, + 36.16708, 2.306778, -49.149583, 2.721637, 7.994647, -60.447408, + 111.168011, 19.714761, 84.617886, -55.640608, 81.787377, -68.04828, + -32.561292, 27.122565, 2.400312, -117.903682, -55.279202, 41.891818, + 104.393543, 45.742048, -13.810168, 39.825595, -57.189929, 25.495989, + -67.373015, -0.468005, -6.535232, 40.104331, -15.148198, 60.100129, + -9.837264, 41.826435, 39.330114, -92.043793, 1.877374, 1.796403, + -38.936996, 8.970536, -72.776716, 27.809261, 25.488943, 15.022277, + 123.829208, 17.61717, 3.37355, -36.613235, 14.857061, -48.08884, + 63.590931, -32.382227, 7.923477, 99.504151, 58.209378, 12.133008, + 68.996005, -2.727935, 39.761697, 0.954498, -45.271907, 21.513567, + 46.732503, -17.305094, -54.856094, -26.409803, -118.988764, -30.384185, + -53.764505, 101.120253, -28.243765, -77.146453, 43.542089, -8.760526, + 2.43015, 9.43231, 10.465674, -18.722246, 47.73493, 26.162383, + -24.790926, -8.57323, -47.21843, 14.043234, 36.912356, 32.537662, + 30.737031, -6.32843, 78.943712, -10.359084, 1.503354, -16.808992, + 4.063189, -12.026209, 101.608966, 21.292336, -84.148244, -21.694319, + -70.811377, 43.99495, 68.729662, -22.552145, 30.676631, -10.507828, + 20.402908, 86.619925, -17.472398, -61.656841, 35.913719, 25.827982, + 33.690075, 51.322748, -34.057421, -98.300736, 52.045318, -20.432516, + -60.370023, -58.414514, 56.418667, 9.041666, 15.145102, 42.519344, + -33.845047, -56.25573, -42.647564, -55.228731, -14.55479, -44.548787, + 1.931761, -24.042457, -3.998974, 32.489517, 70.063845, 77.796896, + 5.746109, 10.618514, -25.419011, 50.2991, 76.589543, -29.68009, + 38.205283, -16.478327, -8.55575, 9.214238, -20.058841, 44.755219, + -74.792618, -34.769845, -5.970572, -52.241185, 18.031899, -75.745215, + 2.758879, -72.013244, -7.262337, 25.403665, 110.178201, 53.881717, + 80.86206, 3.39861, 105.786792, -12.062934, -12.609875, -64.104141, + 11.112587, 52.68002, -31.692907, -18.530109, -23.177249, -16.572628, + -29.519169, -67.501986, 69.048406, -98.587654, -46.35411, 17.187073, + 50.578087, -10.430041, -14.162315, 2.473827, -13.065602, 43.837124, + -24.143934, -49.270923, -23.633141, 4.813397, 61.46067, 79.993876, + -19.970714, -73.209178, -69.193314, 106.266108, -20.143489, 22.895311, + 95.864243, -34.005812, -9.7287, -29.029759, -54.7958, 39.987777, + 53.284988, -93.686922, 49.085533, -11.798356, 9.181316, 9.89345, + -65.326934, -15.543546, -49.545661, 95.762579, 109.292408, 4.20167, + -58.947801, 57.802803, -9.500092, 87.272225, 98.435969, 83.645321, + -19.762973, -49.903739, -33.1525, -4.817262, -46.190367, 59.668426, + 32.873208, -1.698264, -20.019649, 32.465724, 68.920978, -96.489767, + 11.69368, -15.023265, -37.211485, -17.0628, 6.725856, 93.478276, + 2.852858, -21.488338, -61.359507, 38.699963, -37.593538, -5.687254, + 35.65434, 2.61853, -19.311432, -8.635993, 44.917451, -0.981811, + 12.13366, 21.142423, -16.726968, 16.396956, -13.840458, 56.692166, + 25.090513, -86.516897, -10.367697, 55.458729, -10.643295, -21.125871, + 49.684189, -54.131309, 3.251745, 29.508159, 42.596381, -51.667508, + -62.310604, 74.72785, -38.921091, -4.494221, 121.5612, -23.262437, + -110.103229, 139.34018, 50.628967, 17.939541, 138.856734, -3.763288, + 72.296643, 0.622999, -13.782231, 31.625723, 44.219391, 64.118368, +} diff --git a/server/internal/detect/recurring.go b/server/internal/detect/recurring.go new file mode 100644 index 0000000..c517b2c --- /dev/null +++ b/server/internal/detect/recurring.go @@ -0,0 +1,229 @@ +package detect + +// Clip is a decoded window of one episode's audio, and where that window sits in the episode. +type Clip struct { + EpisodeID string + Samples []float64 + SampleRate int + StartMs int64 +} + +// Occurrence is where a recurring segment was found in one episode's clip. +type Occurrence struct { + EpisodeID string + Position int // samples into the clip + Score float64 +} + +// Recurring is a segment found in enough episodes to be trusted, and where it sits in each. +type Recurring struct { + Reference []float64 + Occurrences []Occurrence +} + +// Tuning is what the search is allowed to cost, plus the score a match must clear. +// +// MinScore and the confirmation threshold are safety mechanisms, not performance knobs: the +// threshold is the only thing standing between "the show's intro" and "an ad that happened to +// be inserted into two episodes fetched minutes apart". Reachable for tests, not for operators. +type Tuning struct { + // CoarseFactor shrinks both clips before ranking candidate positions. 1 searches at full + // resolution, which is kept reachable so the fast path can be compared against it. + CoarseFactor int + // FineCandidates is how many ranked positions get verified at full resolution. Several, + // for two reasons: decimation can reorder near-equal peaks, and one strongly-recurring + // segment that is not the one wanted must not be able to crowd the shortlist. + FineCandidates int + // MinScore is the correlation a match must exceed to count as the same audio. + MinScore float64 +} + +// DefaultTuning is the production configuration, matching the values validated on real shows. +func DefaultTuning() Tuning { + return Tuning{CoarseFactor: 8, FineCandidates: 5, MinScore: 0.6} +} + +// minCoarseWindow is the point below which a decimated window stops carrying enough signal to +// rank positions by, so the search runs at full resolution instead. +const minCoarseWindow = 512 + +// candidateStepDivisor makes the search step a quarter of the window. +// +// A step of a whole window would almost always straddle a real embedded segment rather than +// land on it: any embed position that is not a multiple of the window length gets split across +// two candidate windows, each only partly the real signal, and often too weak to clear +// MinScore. +const candidateStepDivisor = 4 + +// DetectRecurring finds a referenceLen-sample segment present in at least confirmThreshold of +// the clips, and reports where it sits in each clip that has it. Nil when nothing recurs widely +// enough to trust. +// +// This is the whole reason for doing detection on a server. On the phone only one episode's clip +// could be held at a time, so the same question had to be answered by a rolling state machine +// that carried a "pending" clip between runs, re-decoded it, accumulated a confirmation count +// over weeks, and lost everything whenever retention reclaimed the pending episode's file. +// Holding every clip at once replaces all of that with a single pass: the threshold is evaluated +// rather than accumulated. +// +// Costs one coarse window search plus FineCandidates*len(clips) full-resolution correlations -- +// not a correlation per window per clip, which would be hundreds of times more work for the +// same answer. +func DetectRecurring(clips []Clip, referenceLen, confirmThreshold int, t Tuning) *Recurring { + if len(clips) < confirmThreshold || confirmThreshold < 1 || referenceLen <= 0 { + return nil + } + + pivot := clips[0] + win := referenceLen + for _, c := range clips { + if len(c.Samples) < win { + return nil + } + } + + // Rank candidate positions in the pivot by how well they match the next clip. Cheap, and + // only a shortlist -- which of them is real is decided below, against every clip. + ranked := rankPositions(pivot.Samples, clips[1].Samples, win, t) + + var best *Recurring + for _, position := range ranked { + start := clampStart(position, len(pivot.Samples), win) + reference := pivot.Samples[start : start+win] + + occurrences := locateInAll(reference, clips, t.MinScore) + if len(occurrences) < confirmThreshold { + continue + } + // Most support wins, not first found. A rotating ad shared by two episodes must lose to + // an intro shared by all of them -- picking the first candidate over MinScore is how a + // skip feature starts cutting advertising it happens to have seen twice and calling it + // the theme tune. + if best == nil || len(occurrences) > len(best.Occurrences) { + best = &Recurring{ + Reference: append([]float64(nil), reference...), + Occurrences: occurrences, + } + } + } + return best +} + +// rankPositions returns candidate window starts in a, best-matching first, in a's own +// resolution. No score threshold is applied: at a coarse resolution these scores are not the +// ones detection is allowed to decide on, so rejecting here would reject on a number the +// full-resolution pass is about to compute properly. +func rankPositions(a, b []float64, win int, t Tuning) []int { + factor := coarseFactor(win, t.CoarseFactor) + searchA, searchB, searchWin := a, b, win + if factor > 1 { + searchA, searchB, searchWin = Decimate(a, factor), Decimate(b, factor), win/factor + } + if searchWin <= 0 || searchWin > len(searchA) || searchWin > len(searchB) { + return nil + } + + step := searchWin / candidateStepDivisor + if step < 1 { + step = 1 + } + target := PrepareTarget(searchB, searchWin) + + type scored struct { + position int + score float64 + } + var all []scored + for start := 0; start+searchWin <= len(searchA); start += step { + if m := BestMatchPrepared(searchA[start:start+searchWin], target); m != nil { + all = append(all, scored{position: start * factor, score: m.Score}) + } + } + + // Highest-scoring first, but one entry per distinct region of a. + // + // Without the spacing rule the shortlist fills with overlapping slices of whichever + // segment scores best, and any other recurring segment never gets looked at. That is not + // hypothetical: a rotating ad present in two episodes produced three near-identical + // candidates covering itself, so the intro shared by all four was never evaluated and the + // detector confirmed the ad. Candidates have to describe different audio, not the same + // audio three times. + keep := t.FineCandidates + if keep < 1 { + keep = 1 + } + out := make([]int, 0, keep) + used := make([]bool, len(all)) + for len(out) < keep { + bestIdx := -1 + for i, s := range all { + if used[i] { + continue + } + if bestIdx < 0 || s.score > all[bestIdx].score { + bestIdx = i + } + } + if bestIdx < 0 { + break + } + used[bestIdx] = true + + position := all[bestIdx].position + if !separated(out, position, win) { + continue + } + out = append(out, position) + } + return out +} + +// separated reports whether position describes a different stretch of audio than everything +// already shortlisted. +func separated(chosen []int, position, spacing int) bool { + for _, c := range chosen { + d := c - position + if d < 0 { + d = -d + } + if d < spacing { + return false + } + } + return true +} + +// locateInAll finds reference in every clip at full resolution, keeping those that clear +// minScore. This is where detection actually happens: every number the coarse pass produced is +// discarded and the decision is made on native-resolution audio. +func locateInAll(reference []float64, clips []Clip, minScore float64) []Occurrence { + var found []Occurrence + for _, c := range clips { + m := BestMatch(reference, c.Samples) + if m == nil || m.Score < minScore { + continue + } + found = append(found, Occurrence{EpisodeID: c.EpisodeID, Position: m.Position, Score: m.Score}) + } + return found +} + +func coarseFactor(win, requested int) int { + if requested < 2 { + return 1 + } + if win/requested < minCoarseWindow { + return 1 + } + return requested +} + +func clampStart(position, length, win int) int { + if position < 0 { + return 0 + } + if position > length-win { + return length - win + } + return position +} diff --git a/server/internal/detect/recurring_test.go b/server/internal/detect/recurring_test.go new file mode 100644 index 0000000..a17a983 --- /dev/null +++ b/server/internal/detect/recurring_test.go @@ -0,0 +1,164 @@ +package detect + +import ( + "math" + "math/rand" + "testing" +) + +// Synthetic clips in the shape the real thing has: mostly unrelated content, with the show's +// recurring sting embedded at a different offset in each, because the pre-roll in front of it +// varies per fetch. Measured on real Up First audio the intro landed anywhere from 44s to 94s +// into the head window. + +func noise(seed int64, n int) []float64 { + rng := rand.New(rand.NewSource(seed)) + out := make([]float64, n) + for i := range out { + out[i] = rng.Float64()*100 - 50 + } + return out +} + +func tone(seed int64, n int) []float64 { + rng := rand.New(rand.NewSource(seed)) + out := make([]float64, n) + for i := range out { + out[i] = math.Sin(float64(i)*0.03)*400 + rng.Float64()*40 - 20 + } + return out +} + +func embed(base, segment []float64, at int) []float64 { + out := append([]float64(nil), base...) + copy(out[at:], segment) + return out +} + +func clip(id string, samples []float64) Clip { + return Clip{EpisodeID: id, Samples: samples, SampleRate: 8000} +} + +func TestConfirmsAStingSharedByEnoughEpisodes(t *testing.T) { + sting := tone(100, 4000) + clips := []Clip{ + clip("e1", embed(noise(1, 40000), sting, 3000)), + clip("e2", embed(noise(2, 40000), sting, 11000)), + clip("e3", embed(noise(3, 40000), sting, 7000)), + clip("e4", embed(noise(4, 40000), sting, 20000)), + } + + got := DetectRecurring(clips, 2000, 3, DefaultTuning()) + if got == nil { + t.Fatal("expected a confirmed recurring segment") + } + if len(got.Occurrences) < 3 { + t.Fatalf("confirmed on %d episodes, want at least 3", len(got.Occurrences)) + } + // Every occurrence must land inside the window the sting really occupies. + starts := map[string]int{"e1": 3000, "e2": 11000, "e3": 7000, "e4": 20000} + for _, occ := range got.Occurrences { + lo, hi := starts[occ.EpisodeID], starts[occ.EpisodeID]+len(sting) + if occ.Position < lo-500 || occ.Position > hi+500 { + t.Errorf("%s: found at %d, sting is at %d..%d", occ.EpisodeID, occ.Position, lo, hi) + } + } +} + +func TestReportsNothingWhenNoSegmentRecurs(t *testing.T) { + clips := []Clip{ + clip("e1", noise(11, 40000)), + clip("e2", noise(12, 40000)), + clip("e3", noise(13, 40000)), + clip("e4", noise(14, 40000)), + } + + if got := DetectRecurring(clips, 2000, 3, DefaultTuning()); got != nil { + t.Errorf("expected nil, found a segment on %d episodes", len(got.Occurrences)) + } +} + +// Too few agreeing episodes must not confirm. This is the whole safety mechanism: two episodes +// fetched close together can share a dynamically-inserted ad, which is not the show's intro. +func TestDoesNotConfirmBelowTheThreshold(t *testing.T) { + ad := tone(200, 4000) + clips := []Clip{ + clip("e1", embed(noise(21, 40000), ad, 3000)), + clip("e2", embed(noise(22, 40000), ad, 9000)), + clip("e3", noise(23, 40000)), + clip("e4", noise(24, 40000)), + } + + if got := DetectRecurring(clips, 2000, 3, DefaultTuning()); got != nil { + t.Errorf("two agreeing episodes confirmed a segment; want nil, got %d occurrences", len(got.Occurrences)) + } +} + +// The Darknet Diaries trap, as a test. A rotating ad is shared by a couple of episodes while +// the show's real intro is shared by all of them. Picking whichever segment is found first +// would latch onto the ad; the detector has to prefer the one with the most support. +func TestPrefersTheSegmentSharedByMostEpisodes(t *testing.T) { + // Deliberately different *kinds* of signal, not just different seeds. tone() is dominated + // by its sine term, so tone(300) and tone(400) correlate at 0.998 -- using both would ask + // the detector to tell apart two things that are the same audio. + intro := tone(300, 4000) + rotatingAd := noise(400, 4000) + clips := []Clip{ + clip("e1", embed(embed(noise(31, 60000), rotatingAd, 1000), intro, 30000)), + clip("e2", embed(embed(noise(32, 60000), rotatingAd, 5000), intro, 42000)), + clip("e3", embed(noise(33, 60000), intro, 20000)), + clip("e4", embed(noise(34, 60000), intro, 50000)), + } + + got := DetectRecurring(clips, 2000, 3, DefaultTuning()) + if got == nil { + t.Fatal("expected the intro to be confirmed") + } + if len(got.Occurrences) != 4 { + t.Errorf("confirmed on %d episodes, want all 4 (the intro, not the 2-episode ad)", len(got.Occurrences)) + } + // The ad sits in the first 10,000 samples of e1 and e2; the intro is far later in both. + for _, occ := range got.Occurrences { + if occ.EpisodeID == "e1" && occ.Position < 20000 { + t.Errorf("e1: locked onto the rotating ad at %d instead of the intro", occ.Position) + } + } +} + +func TestNeedsAtLeastThresholdClipsToSayAnything(t *testing.T) { + sting := tone(500, 4000) + clips := []Clip{ + clip("e1", embed(noise(41, 40000), sting, 3000)), + clip("e2", embed(noise(42, 40000), sting, 9000)), + } + + if got := DetectRecurring(clips, 2000, 3, DefaultTuning()); got != nil { + t.Error("two clips cannot satisfy a threshold of three") + } +} + +// Decimation is a cost shortcut, so it must not change which segment is chosen. +func TestCoarseSearchAgreesWithFullResolution(t *testing.T) { + sting := tone(600, 4000) + clips := []Clip{ + clip("e1", embed(noise(51, 40000), sting, 3000)), + clip("e2", embed(noise(52, 40000), sting, 11000)), + clip("e3", embed(noise(53, 40000), sting, 7000)), + } + + full := DefaultTuning() + full.CoarseFactor = 1 + coarse := DefaultTuning() + + atFull := DetectRecurring(clips, 2000, 3, full) + viaCoarse := DetectRecurring(clips, 2000, 3, coarse) + if atFull == nil || viaCoarse == nil { + t.Fatal("expected both searches to confirm") + } + for i := range atFull.Occurrences { + a, c := atFull.Occurrences[i], viaCoarse.Occurrences[i] + if a.EpisodeID != c.EpisodeID || a.Position != c.Position { + t.Errorf("%s: full resolution found %d, coarse found %d", a.EpisodeID, a.Position, c.Position) + } + } +} diff --git a/server/internal/skips/selfcheck.go b/server/internal/skips/selfcheck.go new file mode 100644 index 0000000..6714b70 --- /dev/null +++ b/server/internal/skips/selfcheck.go @@ -0,0 +1,106 @@ +package skips + +import ( + "github.com/terst/listen/server/internal/detect" +) + +// CheckReport is the outcome of verifying a confirmation against itself. +type CheckReport struct { + OK bool + Pairs int + // WorstA, WorstB and WorstScore identify the least convincing pair, which is what a + // failure needs to say to be actionable. + WorstA string + WorstB string + WorstScore float64 +} + +// slopSamples is how far a reported position may be out before the check calls it a mismatch. +// +// Half a second. A genuine position can differ from a reported one by rounding -- reading an +// offset that was displayed to the nearest second is the first thing that produced a false +// mismatch here -- while a segment that is actually different audio is wrong by far more than +// this. Without the tolerance the check cries wolf; with much more of it, a real error hides. +const slopSamples = 4000 + +// SelfCheck verifies a confirmation by correlating the located segments against each other +// rather than against the reference they were found with. +// +// This asks a different question from the detection threshold, which is why it catches things +// the threshold cannot. "Each of these scored above 0.6 against one reference" does not imply +// "these are all the same audio": correlation is not transitive, and two segments can each +// clear a threshold against a reference while being unrelated to one another. Publishing skip +// offsets derived from such a set would cut different audio out of different episodes, which +// is precisely the failure a skip feature must never have. +// +// Cheap enough to run every time: a handful of correlations over eight-second clips. +func SelfCheck(found *detect.Recurring, clips []detect.Clip, minScore float64) CheckReport { + if found == nil || len(found.Occurrences) < 2 { + return CheckReport{OK: true} + } + + byID := make(map[string][]float64, len(clips)) + for _, c := range clips { + byID[c.EpisodeID] = c.Samples + } + + segments := make(map[string][]float64, len(found.Occurrences)) + for _, o := range found.Occurrences { + samples, ok := byID[o.EpisodeID] + if !ok { + continue + } + // Widened by the tolerance at both ends, so a position that is slightly out still has + // the whole segment inside the window being compared. + from := o.Position - slopSamples + if from < 0 { + from = 0 + } + to := o.Position + len(found.Reference) + slopSamples + if to > len(samples) { + to = len(samples) + } + if to-from > 0 { + segments[o.EpisodeID] = samples[from:to] + } + } + + report := CheckReport{OK: true, WorstScore: 1} + ids := make([]string, 0, len(segments)) + for _, o := range found.Occurrences { + if _, ok := segments[o.EpisodeID]; ok { + ids = append(ids, o.EpisodeID) + } + } + + for i := 0; i < len(ids); i++ { + for j := i + 1; j < len(ids); j++ { + // The query is the reference-length core of one segment; the target is the other + // segment with its tolerance either side, so the search absorbs the slop. + query := core(segments[ids[i]], len(found.Reference)) + target := segments[ids[j]] + score := 0.0 + if m := detect.BestMatch(query, target); m != nil { + score = m.Score + } + report.Pairs++ + if score < report.WorstScore { + report.WorstScore, report.WorstA, report.WorstB = score, ids[i], ids[j] + } + if score < minScore { + report.OK = false + } + } + } + return report +} + +// core takes the middle referenceLen samples of a widened segment, so the query is the segment +// itself rather than the segment plus the tolerance around it. +func core(segment []float64, referenceLen int) []float64 { + if len(segment) <= referenceLen { + return segment + } + start := (len(segment) - referenceLen) / 2 + return segment[start : start+referenceLen] +} diff --git a/server/internal/skips/selfcheck_test.go b/server/internal/skips/selfcheck_test.go new file mode 100644 index 0000000..8766003 --- /dev/null +++ b/server/internal/skips/selfcheck_test.go @@ -0,0 +1,104 @@ +package skips + +import ( + "testing" + + "github.com/terst/listen/server/internal/detect" +) + +// Why a self-check exists at all. +// +// A confirmation says "this segment scored above the threshold in N episodes". That is not quite +// the same claim as "these N episodes all contain the same audio": correlation is not +// transitive, and two segments can each score 0.65 against a reference while scoring near zero +// against each other. Verifying the located segments against one another closes that gap, and +// it is cheap -- a handful of correlations over eight-second clips. +// +// This was not hypothetical caution. Checking the first real run by hand produced an apparent +// mismatch (r = 0.03 between two located segments) which turned out to be an artifact of +// reading offsets that had been rounded to whole seconds. The lesson kept is that the answer +// needs checking by something other than the component that produced it. + +func TestSelfCheckPassesWhenEveryLocatedSegmentIsTheSameAudio(t *testing.T) { + sting := tone(1, 4*testRate) + clips := []detect.Clip{ + {EpisodeID: "e1", Samples: embed(noise(1, 40*testRate), sting, 5*testRate), SampleRate: testRate}, + {EpisodeID: "e2", Samples: embed(noise(2, 40*testRate), sting, 12*testRate), SampleRate: testRate}, + {EpisodeID: "e3", Samples: embed(noise(3, 40*testRate), sting, 20*testRate), SampleRate: testRate}, + } + found := &detect.Recurring{ + Reference: sting, + Occurrences: []detect.Occurrence{ + {EpisodeID: "e1", Position: 5 * testRate, Score: 1}, + {EpisodeID: "e2", Position: 12 * testRate, Score: 1}, + {EpisodeID: "e3", Position: 20 * testRate, Score: 1}, + }, + } + + report := SelfCheck(found, clips, 0.8) + if !report.OK { + t.Errorf("expected agreement, got worst pair %s vs %s at r=%.4f", + report.WorstA, report.WorstB, report.WorstScore) + } + if report.Pairs != 3 { + t.Errorf("checked %d pairs, want 3", report.Pairs) + } +} + +// The case the check exists for: an occurrence pointing at audio that is not the segment. +func TestSelfCheckFailsWhenALocatedSegmentIsDifferentAudio(t *testing.T) { + sting := tone(2, 4*testRate) + clips := []detect.Clip{ + {EpisodeID: "e1", Samples: embed(noise(11, 40*testRate), sting, 5*testRate), SampleRate: testRate}, + {EpisodeID: "e2", Samples: embed(noise(12, 40*testRate), sting, 12*testRate), SampleRate: testRate}, + // e3's reported position points at plain noise, not the sting. + {EpisodeID: "e3", Samples: noise(13, 40*testRate), SampleRate: testRate}, + } + found := &detect.Recurring{ + Reference: sting, + Occurrences: []detect.Occurrence{ + {EpisodeID: "e1", Position: 5 * testRate, Score: 1}, + {EpisodeID: "e2", Position: 12 * testRate, Score: 1}, + {EpisodeID: "e3", Position: 20 * testRate, Score: 1}, + }, + } + + report := SelfCheck(found, clips, 0.8) + if report.OK { + t.Error("expected the check to fail on a segment that is different audio") + } + if report.WorstA != "e3" && report.WorstB != "e3" { + t.Errorf("worst pair was %s vs %s, expected it to involve e3", report.WorstA, report.WorstB) + } +} + +// A rounding difference in a reported position must not read as a mismatch: the check allows +// slop, because that is the artifact that produced the original false alarm. +func TestSelfCheckToleratesASmallPositionError(t *testing.T) { + sting := tone(3, 4*testRate) + clips := []detect.Clip{ + {EpisodeID: "e1", Samples: embed(noise(21, 40*testRate), sting, 5*testRate), SampleRate: testRate}, + {EpisodeID: "e2", Samples: embed(noise(22, 40*testRate), sting, 12*testRate), SampleRate: testRate}, + {EpisodeID: "e3", Samples: embed(noise(23, 40*testRate), sting, 20*testRate), SampleRate: testRate}, + } + found := &detect.Recurring{ + Reference: sting, + Occurrences: []detect.Occurrence{ + {EpisodeID: "e1", Position: 5 * testRate, Score: 1}, + // Half a second late, as reading a rounded offset back would be. + {EpisodeID: "e2", Position: 12*testRate + testRate/2, Score: 1}, + {EpisodeID: "e3", Position: 20 * testRate, Score: 1}, + }, + } + + if report := SelfCheck(found, clips, 0.8); !report.OK { + t.Errorf("a half-second position error failed the check at r=%.4f (%s vs %s)", + report.WorstScore, report.WorstA, report.WorstB) + } +} + +func TestSelfCheckOfNothingIsVacuouslyFine(t *testing.T) { + if report := SelfCheck(nil, nil, 0.8); !report.OK || report.Pairs != 0 { + t.Errorf("checking nothing should pass with no pairs, got %+v", report) + } +} diff --git a/server/internal/skips/skips.go b/server/internal/skips/skips.go new file mode 100644 index 0000000..a7ae808 --- /dev/null +++ b/server/internal/skips/skips.go @@ -0,0 +1,251 @@ +// Package skips turns a show's recent episode files into per-episode skip offsets. +package skips + +import ( + "context" + "fmt" + + "github.com/terst/listen/server/internal/decode" + "github.com/terst/listen/server/internal/detect" +) + +// Config is what a detection run searches and what it will trust. +type Config struct { + // ClipSeconds is the window searched at each end of an episode. + // + // Long enough to contain a pre-roll plus the show's intro behind it, because the pre-roll + // varies per fetch: measured on four real Up First episodes the intro landed anywhere from + // 44 to 94 seconds in, so a window that only just fits an intro would sometimes miss it. + ClipSeconds int + // ReferenceSeconds is the length of segment looked for -- long enough to be a sting, short + // enough not to swallow the programme behind it. + ReferenceSeconds int + // ConfirmThreshold is how many independently-fetched episodes must agree before an offset + // is trusted. See DefaultConfirmThreshold: this is the safety mechanism, not a knob. + ConfirmThreshold int + // Tuning is what the search within those windows is allowed to cost. + Tuning detect.Tuning + // SelfCheckMinScore is how closely the located segments must agree with *each other* + // before offsets are published. See SelfCheck for why that is a different question from + // the detection threshold, and a necessary one. + SelfCheckMinScore float64 +} + +// DefaultClipSeconds and friends are the production values, validated against real shows. +const ( + DefaultClipSeconds = 240 + DefaultReferenceSeconds = 8 + + // DefaultConfirmThreshold is three, and lowering it defeats the feature. + // + // Two episodes fetched close together can agree on a segment that turns out to be a + // dynamically-inserted ad rather than the show's intro -- found prototyping against real + // Darknet Diaries episodes, where a years-old archived episode shared the same "matching" + // segment while two other recent ones shared nothing. A third genuinely independent + // episode is very unlikely to be assigned the same rotating ad. + DefaultConfirmThreshold = 3 + + // DefaultSelfCheckMinScore is how well two located segments must agree to be accepted as + // the same audio. Higher than the detection threshold on purpose: clearing 0.6 against a + // reference is a weaker claim than being the same recording as another episode's segment, + // and real matches between separately-encoded episodes measure above 0.9. + DefaultSelfCheckMinScore = 0.8 +) + +// DefaultConfig is the production configuration. +func DefaultConfig() Config { + return Config{ + ClipSeconds: DefaultClipSeconds, + ReferenceSeconds: DefaultReferenceSeconds, + ConfirmThreshold: DefaultConfirmThreshold, + Tuning: detect.DefaultTuning(), + SelfCheckMinScore: DefaultSelfCheckMinScore, + } +} + +// Decoder is the audio decoding this package needs, behind an interface so the orchestration is +// testable without ffmpeg or real audio. +type Decoder interface { + // Range decodes durationMs of mono audio from startMs. durationMs of 0 means to the end. + Range(ctx context.Context, path string, startMs, durationMs int64) (*decode.Clip, error) + // DurationMs is the file's real length, which is routinely not what its feed claims. + DurationMs(ctx context.Context, path string) (int64, error) +} + +// Episode is one episode's audio on disk. +type Episode struct { + ID string + Path string +} + +// Offsets is what playback needs for one episode: how much to skip at each end. +// +// Both are measured in that episode's own timeline, because that is the only frame of reference +// that survives dynamic ad insertion -- the same episode fetched twice has its intro at +// different offsets in the two files. +type Offsets struct { + EpisodeID string + // IntroMs is where the recurring intro ends, or nil if none was confirmed. + IntroMs *int64 + // OutroMs is how long before the end the recurring outro starts, or nil. + OutroMs *int64 +} + +// Result is a show's detection outcome. +type Result struct { + Offsets []Offsets + // IntroConfirmedOn and OutroConfirmedOn are how many episodes agreed, for reporting. + IntroConfirmedOn int + OutroConfirmedOn int + // IntroCheck and OutroCheck record whether the located segments agreed with each other. + // Offsets are only published when they did. + IntroCheck CheckReport + OutroCheck CheckReport +} + +// Detect finds a show's recurring intro and outro across episodes and reports per-episode +// offsets. +// +// Every episode is examined in one pass, which is the whole reason this runs on a server: on the +// phone only one episode's clip fitted in memory at a time, so the same question needed a +// rolling state machine that accumulated agreement over weeks and lost its progress whenever +// retention reclaimed the file it was holding. +func Detect(ctx context.Context, d Decoder, episodes []Episode, cfg Config) (*Result, error) { + if cfg.ConfirmThreshold < 1 || len(episodes) < cfg.ConfirmThreshold { + return &Result{Offsets: emptyOffsets(episodes)}, nil + } + + durations := make(map[string]int64, len(episodes)) + for _, ep := range episodes { + ms, err := d.DurationMs(ctx, ep.Path) + if err != nil { + return nil, fmt.Errorf("episode %s: %w", ep.ID, err) + } + durations[ep.ID] = ms + } + + heads, err := decodeWindows(ctx, d, episodes, durations, cfg.ClipSeconds, false) + if err != nil { + return nil, err + } + tails, err := decodeWindows(ctx, d, episodes, durations, cfg.ClipSeconds, true) + if err != nil { + return nil, err + } + + referenceLen := cfg.ReferenceSeconds * sampleRateOf(heads) + intro := detect.DetectRecurring(heads, referenceLen, cfg.ConfirmThreshold, cfg.Tuning) + outro := detect.DetectRecurring(tails, referenceLen, cfg.ConfirmThreshold, cfg.Tuning) + + result := &Result{Offsets: emptyOffsets(episodes)} + byID := map[string]int{} + for i, o := range result.Offsets { + byID[o.EpisodeID] = i + } + + if intro != nil { + result.IntroConfirmedOn = len(intro.Occurrences) + result.IntroCheck = SelfCheck(intro, heads, cfg.SelfCheckMinScore) + } + if intro != nil && result.IntroCheck.OK { + for _, occ := range intro.Occurrences { + clip := clipFor(heads, occ.EpisodeID) + if clip == nil { + continue + } + // Where the intro *ends*: playback starts there, so the sting is skipped and + // nothing after it is. + endMs := clip.StartMs + samplesToMs(occ.Position+len(intro.Reference), clip.SampleRate) + ms := endMs + result.Offsets[byID[occ.EpisodeID]].IntroMs = &ms + } + } + + if outro != nil { + result.OutroConfirmedOn = len(outro.Occurrences) + result.OutroCheck = SelfCheck(outro, tails, cfg.SelfCheckMinScore) + } + if outro != nil && result.OutroCheck.OK { + for _, occ := range outro.Occurrences { + clip := clipFor(tails, occ.EpisodeID) + if clip == nil { + continue + } + // An outro offset is measured back from the end of the episode, which is how + // playback uses it: the episode finishes when the playhead reaches that point. + startMs := clip.StartMs + samplesToMs(occ.Position, clip.SampleRate) + fromEnd := durations[occ.EpisodeID] - startMs + if fromEnd < 0 { + fromEnd = 0 + } + ms := fromEnd + result.Offsets[byID[occ.EpisodeID]].OutroMs = &ms + } + } + + return result, nil +} + +// decodeWindows decodes the head or tail window of every episode. +func decodeWindows( + ctx context.Context, + d Decoder, + episodes []Episode, + durations map[string]int64, + clipSeconds int, + tail bool, +) ([]detect.Clip, error) { + windowMs := int64(clipSeconds) * 1000 + clips := make([]detect.Clip, 0, len(episodes)) + for _, ep := range episodes { + start := int64(0) + if tail { + start = durations[ep.ID] - windowMs + if start < 0 { + start = 0 + } + } + clip, err := d.Range(ctx, ep.Path, start, windowMs) + if err != nil { + return nil, fmt.Errorf("episode %s: %w", ep.ID, err) + } + clips = append(clips, detect.Clip{ + EpisodeID: ep.ID, + Samples: clip.Samples, + SampleRate: clip.SampleRate, + StartMs: clip.StartMs, + }) + } + return clips, nil +} + +func emptyOffsets(episodes []Episode) []Offsets { + out := make([]Offsets, len(episodes)) + for i, ep := range episodes { + out[i] = Offsets{EpisodeID: ep.ID} + } + return out +} + +func clipFor(clips []detect.Clip, episodeID string) *detect.Clip { + for i := range clips { + if clips[i].EpisodeID == episodeID { + return &clips[i] + } + } + return nil +} + +func sampleRateOf(clips []detect.Clip) int { + if len(clips) == 0 { + return 0 + } + return clips[0].SampleRate +} + +func samplesToMs(samples, sampleRate int) int64 { + if sampleRate == 0 { + return 0 + } + return int64(samples) * 1000 / int64(sampleRate) +} diff --git a/server/internal/skips/skips_test.go b/server/internal/skips/skips_test.go new file mode 100644 index 0000000..bfddcd3 --- /dev/null +++ b/server/internal/skips/skips_test.go @@ -0,0 +1,394 @@ +package skips + +import ( + "context" + "errors" + "math" + "math/rand" + "testing" + + "github.com/terst/listen/server/internal/decode" +) + +// A decoder serving audio this test constructed, so the arithmetic between "where a correlation +// peaked" and "what playback should skip" is checked in isolation. That conversion is where an +// off-by-a-window hides: a skip offset that is eight seconds wrong cuts speech, and nothing +// downstream can tell. + +const testRate = 1000 + +type stubDecoder struct { + durations map[string]int64 + // audio is the whole episode, indexed by path; Range slices it. + audio map[string][]float64 + err error + calls []call +} + +type call struct { + path string + startMs, lengthMs int64 +} + +func (s *stubDecoder) DurationMs(_ context.Context, path string) (int64, error) { + if s.err != nil { + return 0, s.err + } + return s.durations[path], nil +} + +func (s *stubDecoder) Range(_ context.Context, path string, startMs, durationMs int64) (*decode.Clip, error) { + if s.err != nil { + return nil, s.err + } + s.calls = append(s.calls, call{path: path, startMs: startMs, lengthMs: durationMs}) + whole := s.audio[path] + from := int(startMs) * testRate / 1000 + to := from + int(durationMs)*testRate/1000 + if from > len(whole) { + from = len(whole) + } + if to > len(whole) { + to = len(whole) + } + return &decode.Clip{Samples: whole[from:to], SampleRate: testRate, StartMs: startMs}, nil +} + +func noise(seed int64, n int) []float64 { + rng := rand.New(rand.NewSource(seed)) + out := make([]float64, n) + for i := range out { + out[i] = rng.Float64()*100 - 50 + } + return out +} + +func tone(seed int64, n int) []float64 { + rng := rand.New(rand.NewSource(seed)) + out := make([]float64, n) + for i := range out { + out[i] = math.Sin(float64(i)*0.05)*400 + rng.Float64()*40 - 20 + } + return out +} + +// jitter returns a near-identical copy of a segment, as a separate encode of the same audio +// would be. Embedding the bit-identical array instead makes every correlation exactly 1.0, +// which no real pair of episodes ever reaches and which hides anything threshold-sensitive. +func jitter(segment []float64, seed int64) []float64 { + rng := rand.New(rand.NewSource(seed)) + out := make([]float64, len(segment)) + for i, v := range segment { + out[i] = v + rng.Float64()*8 - 4 + } + return out +} + +func embed(base, segment []float64, at int) []float64 { + out := append([]float64(nil), base...) + copy(out[at:], segment) + return out +} + +// A deliberately small configuration. The production window is 240 seconds, which at full +// resolution is a 2^18-point correlation per candidate position -- the suite took 140 seconds +// measuring the FFT rather than the behaviour under test. Sizes here are the smallest that +// still exercise the real arithmetic, and the production values are checked separately by +// TestDefaultConfigUsesTheValidatedValues. +func testConfig() Config { + cfg := DefaultConfig() + cfg.ClipSeconds = 40 + cfg.ReferenceSeconds = 4 + cfg.Tuning.CoarseFactor = 1 + return cfg +} + +func TestFewerEpisodesThanTheThresholdDetectsNothing(t *testing.T) { + d := &stubDecoder{durations: map[string]int64{"a": 60000, "b": 60000}, audio: map[string][]float64{}} + got, err := Detect(context.Background(), d, []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}}, testConfig()) + if err != nil { + t.Fatal(err) + } + if len(got.Offsets) != 2 { + t.Fatalf("got %d offsets, want 2", len(got.Offsets)) + } + for _, o := range got.Offsets { + if o.IntroMs != nil || o.OutroMs != nil { + t.Errorf("%s: detected something from two episodes", o.EpisodeID) + } + } + if len(d.calls) != 0 { + t.Errorf("decoded %d windows for a show that cannot confirm", len(d.calls)) + } +} + +// The reported intro offset must be where the sting ENDS, in the episode's own timeline -- +// that is the point playback starts from, so reporting the start would play the whole sting. +func TestIntroOffsetIsWhereTheStingEnds(t *testing.T) { + sting := tone(1, 4*testRate) + episodeLen := 40 * testRate + // The sting at a different offset in each, as a varying pre-roll produces. + audio := map[string][]float64{ + "a": embed(noise(11, episodeLen), sting, 8*testRate), + "b": embed(noise(12, episodeLen), sting, 20*testRate), + "c": embed(noise(13, episodeLen), sting, 30*testRate), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 40000, "b": 40000, "c": 40000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + got, err := Detect(context.Background(), d, eps, testConfig()) + if err != nil { + t.Fatal(err) + } + if got.IntroConfirmedOn != 3 { + t.Fatalf("confirmed on %d episodes, want 3", got.IntroConfirmedOn) + } + + // Sting starts at 8s/20s/30s and runs 4s, so playback should resume at 12s/24s/34s. + want := map[string]int64{"e1": 12000, "e2": 24000, "e3": 34000} + for _, o := range got.Offsets { + if o.IntroMs == nil { + t.Errorf("%s: no intro offset", o.EpisodeID) + continue + } + if diff := *o.IntroMs - want[o.EpisodeID]; diff < -1500 || diff > 1500 { + t.Errorf("%s: intro ends at %dms, want about %dms", o.EpisodeID, *o.IntroMs, want[o.EpisodeID]) + } + } +} + +// An outro offset is measured backwards from the end of the episode, because that is how +// playback consumes it: the episode is finished once the playhead reaches that distance from +// the end. Reporting an absolute position would end episodes at the wrong moment. +func TestOutroOffsetIsMeasuredBackFromTheEnd(t *testing.T) { + credits := tone(2, 4*testRate) + episodeLen := 80 * testRate + // Credits 30s before the end of each episode, which are all 300s long. + audio := map[string][]float64{ + "a": embed(noise(21, episodeLen), credits, episodeLen-20*testRate), + "b": embed(noise(22, episodeLen), credits, episodeLen-20*testRate), + "c": embed(noise(23, episodeLen), credits, episodeLen-20*testRate), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 80000, "b": 80000, "c": 80000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + got, err := Detect(context.Background(), d, eps, testConfig()) + if err != nil { + t.Fatal(err) + } + if got.OutroConfirmedOn != 3 { + t.Fatalf("outro confirmed on %d episodes, want 3", got.OutroConfirmedOn) + } + for _, o := range got.Offsets { + if o.OutroMs == nil { + t.Errorf("%s: no outro offset", o.EpisodeID) + continue + } + if diff := *o.OutroMs - 20000; diff < -1500 || diff > 1500 { + t.Errorf("%s: outro offset %dms from the end, want about 20000", o.EpisodeID, *o.OutroMs) + } + } +} + +// The tail window has to be taken from the end of the file, not the start. +func TestTailWindowIsReadFromTheEndOfTheEpisode(t *testing.T) { + episodeLen := 120 * testRate + audio := map[string][]float64{ + "a": noise(31, episodeLen), "b": noise(32, episodeLen), "c": noise(33, episodeLen), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 120000, "b": 120000, "c": 120000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + if _, err := Detect(context.Background(), d, eps, testConfig()); err != nil { + t.Fatal(err) + } + + var heads, tails int + for _, c := range d.calls { + switch c.startMs { + case 0: + heads++ + case 120000 - int64(testConfig().ClipSeconds)*1000: + tails++ + default: + t.Errorf("unexpected window start %dms", c.startMs) + } + } + if heads != 3 || tails != 3 { + t.Errorf("got %d head and %d tail windows, want 3 and 3", heads, tails) + } +} + +// An episode shorter than the window must be read from zero rather than a negative offset. +func TestAShortEpisodeIsReadFromTheStart(t *testing.T) { + short := int64(20000) + audio := map[string][]float64{ + "a": noise(41, 20*testRate), "b": noise(42, 20*testRate), "c": noise(43, 20*testRate), + } + d := &stubDecoder{ + durations: map[string]int64{"a": short, "b": short, "c": short}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + if _, err := Detect(context.Background(), d, eps, testConfig()); err != nil { + t.Fatal(err) + } + for _, c := range d.calls { + if c.startMs < 0 { + t.Errorf("decoded from a negative offset %dms", c.startMs) + } + } +} + +func TestNothingRecurringLeavesEveryOffsetUnset(t *testing.T) { + episodeLen := 40 * testRate + audio := map[string][]float64{ + "a": noise(51, episodeLen), "b": noise(52, episodeLen), "c": noise(53, episodeLen), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 40000, "b": 40000, "c": 40000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + got, err := Detect(context.Background(), d, eps, testConfig()) + if err != nil { + t.Fatal(err) + } + if got.IntroConfirmedOn != 0 || got.OutroConfirmedOn != 0 { + t.Errorf("confirmed intro on %d and outro on %d from unrelated noise", + got.IntroConfirmedOn, got.OutroConfirmedOn) + } + for _, o := range got.Offsets { + if o.IntroMs != nil || o.OutroMs != nil { + t.Errorf("%s: offset set with nothing recurring", o.EpisodeID) + } + } +} + +// A decode failure must name the episode. A show that silently detects nothing because one file +// was unreadable is the failure mode this whole feature has already had twice. +func TestADecodeFailureNamesTheEpisode(t *testing.T) { + d := &stubDecoder{ + durations: map[string]int64{}, + audio: map[string][]float64{}, + err: errors.New("no such file"), + } + eps := []Episode{{ID: "ep-abc", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + _, err := Detect(context.Background(), d, eps, testConfig()) + if err == nil { + t.Fatal("expected an error") + } + if !errors.Is(err, d.err) { + t.Errorf("error does not wrap the cause: %v", err) + } + if got := err.Error(); got == "" || !contains(got, "ep-abc") { + t.Errorf("error %q does not name the episode", got) + } +} + +func contains(haystack, needle string) bool { + for i := 0; i+len(needle) <= len(haystack); i++ { + if haystack[i:i+len(needle)] == needle { + return true + } + } + return false +} + +// The tests above run at reduced sizes, so what production actually uses is pinned here rather +// than going unchecked. These are the values validated against real shows; the confirmation +// threshold in particular is the whole safety mechanism. +func TestDefaultConfigUsesTheValidatedValues(t *testing.T) { + cfg := DefaultConfig() + if cfg.ClipSeconds != 240 { + t.Errorf("ClipSeconds = %d, want 240", cfg.ClipSeconds) + } + if cfg.ReferenceSeconds != 8 { + t.Errorf("ReferenceSeconds = %d, want 8", cfg.ReferenceSeconds) + } + if cfg.ConfirmThreshold != 3 { + t.Errorf("ConfirmThreshold = %d, want 3", cfg.ConfirmThreshold) + } + if cfg.Tuning.MinScore != 0.6 { + t.Errorf("MinScore = %v, want 0.6", cfg.Tuning.MinScore) + } + if cfg.Tuning.CoarseFactor != 8 { + t.Errorf("CoarseFactor = %d, want 8", cfg.Tuning.CoarseFactor) + } +} + +// The wiring that makes the self-check matter: a confirmation that cannot verify itself must +// not produce skip offsets. Forced here by demanding near-perfect agreement, which a genuine +// match between two separately-encoded episodes does not reach -- so this exercises the +// suppression path without having to contrive audio that fools the detector. +func TestOffsetsAreSuppressedWhenTheSelfCheckFails(t *testing.T) { + sting := tone(1, 4*testRate) + episodeLen := 40 * testRate + audio := map[string][]float64{ + "a": embed(noise(61, episodeLen), jitter(sting, 601), 8*testRate), + "b": embed(noise(62, episodeLen), jitter(sting, 602), 20*testRate), + "c": embed(noise(63, episodeLen), jitter(sting, 603), 30*testRate), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 40000, "b": 40000, "c": 40000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + cfg := testConfig() + cfg.SelfCheckMinScore = 0.99999 + + got, err := Detect(context.Background(), d, eps, cfg) + if err != nil { + t.Fatal(err) + } + if got.IntroCheck.OK { + t.Fatalf("expected the self-check to fail at 0.99999, worst pair r=%.4f", got.IntroCheck.WorstScore) + } + for _, o := range got.Offsets { + if o.IntroMs != nil { + t.Errorf("%s: published an intro offset of %dms despite a failed self-check", + o.EpisodeID, *o.IntroMs) + } + } +} + +// And the ordinary case: a real confirmation verifies, and says so. +func TestAGenuineConfirmationPassesItsSelfCheck(t *testing.T) { + sting := tone(1, 4*testRate) + episodeLen := 40 * testRate + audio := map[string][]float64{ + "a": embed(noise(71, episodeLen), jitter(sting, 701), 8*testRate), + "b": embed(noise(72, episodeLen), jitter(sting, 702), 20*testRate), + "c": embed(noise(73, episodeLen), jitter(sting, 703), 30*testRate), + } + d := &stubDecoder{ + durations: map[string]int64{"a": 40000, "b": 40000, "c": 40000}, + audio: audio, + } + eps := []Episode{{ID: "e1", Path: "a"}, {ID: "e2", Path: "b"}, {ID: "e3", Path: "c"}} + + got, err := Detect(context.Background(), d, eps, testConfig()) + if err != nil { + t.Fatal(err) + } + if !got.IntroCheck.OK { + t.Errorf("self-check failed on a genuine confirmation: worst %s vs %s at r=%.4f", + got.IntroCheck.WorstA, got.IntroCheck.WorstB, got.IntroCheck.WorstScore) + } + if got.IntroCheck.Pairs != 3 { + t.Errorf("checked %d pairs, want 3", got.IntroCheck.Pairs) + } +} diff --git a/tools/.keep b/tools/.keep new file mode 100644 index 0000000..e69de29 -- cgit v1.2.3