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 --- 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 +++++++++++++++++++++++++++++++ 15 files changed, 2196 insertions(+) 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 (limited to 'server/internal') 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) + } +} -- cgit v1.2.3