path: root/server/internal/signature/library.go

package signature

import (
	"crypto/sha256"
	"encoding/binary"
	"encoding/hex"
	"sort"
)

// What a signature is.
const (
	// KindCue is a show's own furniture: its opening, its break stinger, its credits. It
	// belongs to one show and does not expire -- it is part of what the show is.
	KindCue = "cue"
	// KindCopy is one advertisement. It belongs to nobody, turns up in any show running the
	// same campaign, and stops being worth matching against once the campaign ends.
	KindCopy = "copy"
)

// CopyLifetimeSeconds is how long an advertisement is kept after it was last heard.
//
// Six months. Campaigns run for weeks and return, and a signature costs little to hold, so this
// errs towards remembering. A cue is never aged out at all; see [Library.Age].
const CopyLifetimeSeconds = int64(180 * 24 * 60 * 60)

// matchVotes is how much agreement on one offset counts as the same audio.
//
// Measured on the live corpus: real repeats scored 813-1564 votes and coincidences 27-94, so
// anything in between separates them. Set near the bottom of that gap rather than the middle,
// because a match is proposed here and confirmed by correlation before anything is published --
// missing a real advertisement is worse than proposing one that gets thrown out.
const matchVotes = 150

// Observation is one sighting of a stretch of audio worth remembering.
type Observation struct {
	Fingerprint Fingerprint
	// Kind is [KindCue] or [KindCopy].
	Kind string
	// FeedURL is the show a cue belongs to. Ignored for a copy.
	FeedURL    string
	DurationMs int64
	// Partners is how many episodes in this one batch carried the audio, as detection
	// measured it. Within-batch corroboration, which is not the same thing as independence.
	Partners int
	// Confirmed is set when the listener said so himself -- pressing "this is an ad", or
	// marking a break the detector found as right. The strongest evidence there is: detection
	// infers from repetition, and he heard it.
	Confirmed bool
	// Occasion is what makes two sightings independent. A whole batch of episodes mirrored in
	// one minute is one occasion, however many of them carried the audio -- they all ran
	// whatever campaign was running that minute, which is exactly why eight agreeing episodes
	// proved nothing about an intro.
	Occasion string
}

// Entry is a signature the library holds.
type Entry struct {
	ID         string `json:"id"`
	Kind       string `json:"kind"`
	FeedURL    string `json:"feedUrl,omitempty"`
	DurationMs int64  `json:"durationMs"`
	// Partners is the most episodes ever seen sharing this in a single batch.
	Partners int `json:"partners,omitempty"`
	// Confirmed is whether the listener ever said this is what it is. Never unset once set --
	// he does not un-hear it next week.
	Confirmed bool `json:"confirmed,omitempty"`

	Fingerprint Fingerprint `json:"fingerprint"`

	// Occasions are the distinct times this was seen, in order. Its length is the confidence.
	Occasions     []string `json:"occasions"`
	FirstSeenUnix int64    `json:"firstSeenUnix"`
	LastSeenUnix  int64    `json:"lastSeenUnix"`
}

// Confidence is how many separate occasions this signature has been seen on.
func (e *Entry) Confidence() int { return len(e.Occasions) }

// Trusted says whether this is worth matching against, and the rule differs by kind.
//
// A cue needs [minOccasions] separate occasions, no exceptions. That is the independence test
// the withheld intro and outro offsets have been waiting for: eight episodes mirrored in one
// minute all carry whatever campaign is running, so agreement across them says nothing about
// whether audio is the show's own. Only agreement across *weeks* does.
//
// An advertisement is different, and the difference is not a loophole. Detection publishes a
// break only because the audio recurred across several episodes, verified by correlating them
// against each other -- so a copy that arrived with partners is already a confirmed repeat, not
// a single unsupported sighting. Holding it back for a second week would mean the library could
// only ever propose advertising that detection had already found twice, which is precisely when
// it has nothing to add.
func (e *Entry) Trusted(minOccasions int) bool {
	// Nothing outranks the listener. Detection and the occasion count are both ways of
	// inferring what this audio is; he was there.
	if e.Confirmed {
		return true
	}
	if e.Confidence() >= minOccasions {
		return true
	}
	return e.Kind == KindCopy && e.Partners >= 2
}

func (e *Entry) seenOn(occasion string) bool {
	for _, o := range e.Occasions {
		if o == occasion {
			return true
		}
	}
	return false
}

// Library is every signature worth matching against.
type Library struct {
	entries []*Entry
	index   *Index
}

// NewLibrary returns an empty library.
func NewLibrary() *Library { return &Library{index: NewIndex()} }

// Len is how many signatures are held, trusted or not.
func (l *Library) Len() int { return len(l.entries) }

// Observe records a sighting, merging it into an existing signature when it is the same audio.
// It returns the entry and whether it was new.
func (l *Library) Observe(o Observation, atUnix int64) (*Entry, bool) {
	if len(o.Fingerprint.Hashes) == 0 {
		return nil, false
	}
	if existing := l.same(o); existing != nil {
		if !existing.seenOn(o.Occasion) {
			existing.Occasions = append(existing.Occasions, o.Occasion)
		}
		if atUnix > existing.LastSeenUnix {
			existing.LastSeenUnix = atUnix
		}
		if o.Partners > existing.Partners {
			existing.Partners = o.Partners
		}
		if o.Confirmed {
			existing.Confirmed = true
		}
		return existing, false
	}
	e := &Entry{
		ID:            fingerprintID(o.Fingerprint),
		Kind:          o.Kind,
		DurationMs:    o.DurationMs,
		Partners:      o.Partners,
		Confirmed:     o.Confirmed,
		Fingerprint:   o.Fingerprint,
		Occasions:     []string{o.Occasion},
		FirstSeenUnix: atUnix,
		LastSeenUnix:  atUnix,
	}
	if o.Kind == KindCue {
		e.FeedURL = o.FeedURL
	}
	l.entries = append(l.entries, e)
	l.reindex()
	return e, true
}

// same finds the held signature that is this audio, if any. By matching rather than by id,
// because the same advertisement re-encoded by a different CDN is not byte-identical and would
// otherwise accumulate as a new signature every week.
func (l *Library) same(o Observation) *Entry {
	for _, hit := range l.index.Search(o.Fingerprint) {
		if hit.Votes < matchVotes {
			continue
		}
		if e := l.byID(hit.ID); e != nil && e.Kind == o.Kind {
			return e
		}
	}
	return nil
}

func (l *Library) byID(id string) *Entry {
	for _, e := range l.entries {
		if e.ID == id {
			return e
		}
	}
	return nil
}

// Confident returns the signatures seen on at least minSightings separate occasions.
func (l *Library) Confident(minSightings int) []*Entry {
	var out []*Entry
	for _, e := range l.entries {
		if e.Confidence() >= minSightings {
			out = append(out, e)
		}
	}
	return out
}

// Trusted returns the signatures worth matching against; see [Entry.Trusted].
func (l *Library) Trusted(minOccasions int) []*Entry {
	var out []*Entry
	for _, e := range l.entries {
		if e.Trusted(minOccasions) {
			out = append(out, e)
		}
	}
	return out
}

// Age forgets advertisements nobody has heard in a long time, and returns how many went.
//
// Cues are never aged out: a show's break stinger is not a campaign, and a show that goes quiet
// for a year comes back using the same one. They go when the show does; see [Library.Forget].
func (l *Library) Age(nowUnix int64) int {
	kept := l.entries[:0]
	dropped := 0
	for _, e := range l.entries {
		if e.Kind == KindCopy && nowUnix-e.LastSeenUnix > CopyLifetimeSeconds {
			dropped++
			continue
		}
		kept = append(kept, e)
	}
	l.entries = kept
	if dropped > 0 {
		l.reindex()
	}
	return dropped
}

// Disown drops every signature matching this audio, and returns how many went.
//
// For audio the listener says is the programme. It is the worst failure this system has: a
// signature built from programme would cut the programme, in every episode carrying it, until
// somebody noticed. So his "no" removes it outright rather than lowering a score.
func (l *Library) Disown(fp Fingerprint) int {
	if len(fp.Hashes) == 0 {
		return 0
	}
	doomed := map[string]bool{}
	for _, hit := range l.index.Search(fp) {
		if hit.Votes >= matchVotes {
			doomed[hit.ID] = true
		}
	}
	if len(doomed) == 0 {
		return 0
	}
	kept := l.entries[:0]
	for _, e := range l.entries {
		if !doomed[e.ID] {
			kept = append(kept, e)
		}
	}
	l.entries = kept
	l.reindex()
	return len(doomed)
}

// Forget drops the cues belonging to a show, for when it is unsubscribed. Copies are untouched:
// an advertisement heard in that show is not the show's.
func (l *Library) Forget(feedURL string) int {
	kept := l.entries[:0]
	dropped := 0
	for _, e := range l.entries {
		if e.Kind == KindCue && e.FeedURL == feedURL {
			dropped++
			continue
		}
		kept = append(kept, e)
	}
	l.entries = kept
	if dropped > 0 {
		l.reindex()
	}
	return dropped
}

// Match is where a held signature turns up in an episode.
type Match struct {
	Entry   *Entry
	StartMs int64
	EndMs   int64
	Votes   int
}

// Match reports which trusted signatures appear in the given audio, and where.
//
// A proposal, not a verdict. The offset is accurate to about a frame and the extent is assumed
// to be the signature's own length, both of which want confirming by correlation before anything
// is cut from what somebody is listening to.
func (l *Library) Match(fp Fingerprint, minSightings int) []Match {
	trusted := map[string]*Entry{}
	for _, e := range l.Trusted(minSightings) {
		trusted[e.ID] = e
	}
	if len(trusted) == 0 {
		return nil
	}
	// The query here is the episode and the index holds the signatures, so a hit's offset is
	// where the episode sits inside the signature -- negated, where the signature sits in the
	// episode.
	var out []Match
	for _, hit := range l.index.Search(fp) {
		e, ok := trusted[hit.ID]
		if !ok || hit.Votes < matchVotes {
			continue
		}
		start := -hit.OffsetMs
		if start < 0 {
			start = 0
		}
		out = append(out, Match{Entry: e, StartMs: start, EndMs: start + e.DurationMs, Votes: hit.Votes})
	}
	sort.Slice(out, func(i, j int) bool { return out[i].StartMs < out[j].StartMs })
	return out
}

func (l *Library) reindex() {
	l.index = NewIndex()
	for _, e := range l.entries {
		l.index.Add(e.ID, e.Fingerprint)
	}
}

// fingerprintID names a signature by its own contents, so the same audio observed twice gets the
// same name without anything having to remember it.
func fingerprintID(fp Fingerprint) string {
	h := sha256.New()
	buf := make([]byte, 4)
	for _, v := range fp.Hashes {
		binary.LittleEndian.PutUint32(buf, v)
		h.Write(buf)
	}
	return hex.EncodeToString(h.Sum(nil))[:16]
}