transmux 0.28.0

//! Matroska (MKV) container muxer — [`MkvMux`].
//!
//! [`MkvMux`] packages the crate's [`Media`] IR into a Matroska (`.mkv`) file:
//! an EBML header, then a `Segment` carrying `SeekHead` / `Info` / `Tracks` /
//! one or more `Cluster`s of `SimpleBlock`s / `Cues`. It is the exact inverse
//! of [`crate::webm_demux::WebmDemux`] — the two share the same CodecID ⇄
//! [`CodecConfig`] mapping, so `{Matroska} → IR → {Matroska}` round-trips.
//!
//! # Spec citations
//!
//! - **EBML framing** (VINT element-ID / element-size, EBML header): RFC 8794
//!   §4 / §11.
//! - **Matroska element IDs / semantics** (Segment, SeekHead, Info, Tracks,
//!   Cluster, (Simple)Block, Cues): RFC 9559 §12 / §27.
//! - **CodecID registry** (`V_MPEG4/ISO/AVC`, `V_MPEGH/ISO/HEVC`, `V_VP9`,
//!   `V_VP8`, `V_AV1`, `A_AAC`, `A_OPUS`, `A_VORBIS`, `A_AC3`, `A_EAC3`) and the
//!   `CodecPrivate` payload each one carries: RFC 9559 §27 codec mapping
//!   registry (avcC/hvcC/av1C bodies verbatim; `AudioSpecificConfig` for AAC;
//!   `OpusHead` per RFC 7845 §5.1; the Xiph-laced Vorbis headers).
//!
//! # Scope
//!
//! The mapped [`CodecConfig`] variants are exactly [`crate::webm_demux::WebmDemux`]'s
//! supported set plus the ISOBMFF-family codecs a DVR recording actually
//! carries: [`CodecConfig::Avc`], [`CodecConfig::Hevc`], [`CodecConfig::Vp9`],
//! [`CodecConfig::Vp8`], [`CodecConfig::Av1`], [`CodecConfig::Aac`],
//! [`CodecConfig::Opus`], [`CodecConfig::Vorbis`], [`CodecConfig::Ac3`],
//! [`CodecConfig::Eac3`]. Every other variant (`Vvc`/`Flac`/`Ac4`/`MpegH`/
//! `Mpeg2Video`/`MpegAudio`/`Dts`/`Subtitle`/`Data`) is rejected with
//! [`Error::UnsupportedMkvCodec`], naming the track, rather than silently
//! dropped.
//!
//! # Cluster strategy
//!
//! Samples from every track are merged into one block stream by a **k-way
//! merge on presentation time that never reorders a track's own samples**:
//! each track's `samples` are already in decode order (the IR's documented
//! invariant), and for AVC/HEVC with B-frame reordering that order is *not*
//! presentation-time order (a P-frame decodes before, but may present after,
//! the B-frames that reference it) — a track's own presentation-time sequence
//! can therefore dip non-monotonically, and a global sort on presentation time
//! would silently reorder a track's blocks relative to each other, desyncing
//! decode order from reference order. The merge only decides *when* to
//! interleave tracks, walking each track's own cursor strictly forward.
//!
//! The merged stream is then split into `Cluster`s: a new `Cluster` starts at
//! every video keyframe (when the [`Media`] has a video track), and in any
//! case at least every `MAX_CLUSTER_SPAN_WITH_VIDEO_TICKS` (5 s) — or
//! `MAX_CLUSTER_SPAN_AUDIO_ONLY_TICKS` (1 s) for an audio-only [`Media`].
//! Every block is emitted as a `SimpleBlock` (no lacing, no `BlockGroup`) —
//! valid per RFC 9559 §12 and sufficient for every codec this module maps
//! (the signed relative timestamp already accommodates the occasional small
//! backward dip from B-frame reordering).
//!
//! `TimestampScale` is fixed at `TIMESTAMP_SCALE_NS` (1 ms per tick, the
//! Matroska default) — every track's samples are rescaled from their own
//! [`TrackSpec::timescale`](crate::pipeline::TrackSpec::timescale) into that
//! common tick.
//!
//! # `SeekHead` / `Cues`
//!
//! `SeekHead` indexes `Info` and `Tracks` only (both always precede every
//! `Cluster`, so no seek entry ever needs to name one). Its `SeekPosition`
//! entries are written at a fixed 4-byte width (giving each entry's own byte
//! length independence from the position *value*, not just its presence) so
//! the `SeekHead`'s own serialized size — needed to compute those very
//! positions — can be measured from a placeholder build before the real
//! positions are known, mirroring
//! [`crate::progressive::ProgressiveMux`]'s two-pass `stco`/`co64` offset
//! arithmetic. `Cues` carries one `CuePoint` per **video** keyframe (never one
//! per audio sample, which — unlike video — has no non-keyframe state in this
//! IR: [`crate::pipeline::Sample::from_raw`] always marks an audio sample
//! sync); omitted entirely when the [`Media`] has no video track.

use crate::TrackId;
use alloc::vec;
use alloc::vec::Vec;

use broadcast_common::{Package, Serialize};

use crate::error::{Error, Result};
use crate::media::{Media, Track};
use crate::opus::OpusSpecificBox;
use crate::pipeline::CodecConfig;

// ---------------------------------------------------------------------------
// EBML header elements (RFC 8794 §11)
// ---------------------------------------------------------------------------

const ID_EBML: [u8; 4] = [0x1A, 0x45, 0xDF, 0xA3];
const ID_EBML_VERSION: [u8; 2] = [0x42, 0x86];
const ID_EBML_READ_VERSION: [u8; 2] = [0x42, 0xF7];
const ID_EBML_MAX_ID_LENGTH: [u8; 2] = [0x42, 0xF2];
const ID_EBML_MAX_SIZE_LENGTH: [u8; 2] = [0x42, 0xF3];
const ID_DOC_TYPE: [u8; 2] = [0x42, 0x82];
const ID_DOC_TYPE_VERSION: [u8; 2] = [0x42, 0x87];
const ID_DOC_TYPE_READ_VERSION: [u8; 2] = [0x42, 0x85];

/// `EBMLVersion` value this writer emits.
const EBML_VERSION_VALUE: u64 = 1;
/// `EBMLReadVersion` value this writer emits.
const EBML_READ_VERSION_VALUE: u64 = 1;
/// `EBMLMaxIDLength` value this writer emits (the widest element ID it uses is
/// 4 bytes, but 4 is also the registry-wide max for a Matroska/WebM ID).
const EBML_MAX_ID_LENGTH_VALUE: u64 = 4;
/// `EBMLMaxSizeLength` value this writer emits (matches [`encode_vint_size`]'s
/// widest emitted size VINT).
const EBML_MAX_SIZE_LENGTH_VALUE: u64 = 8;
/// `DocType` value: this writer always emits the Matroska doc type (not the
/// `webm` subset profile), since it uses codecs (AVC/HEVC/AAC/AC-3) outside
/// that profile.
const DOC_TYPE: &[u8] = b"matroska";
/// `DocTypeVersion` value this writer emits.
const DOC_TYPE_VERSION_VALUE: u64 = 4;
/// `DocTypeReadVersion` value this writer emits.
const DOC_TYPE_READ_VERSION_VALUE: u64 = 2;

// ---------------------------------------------------------------------------
// Segment + children (RFC 9559 §27)
// ---------------------------------------------------------------------------

const ID_SEGMENT: [u8; 4] = [0x18, 0x53, 0x80, 0x67];
const ID_SEEK_HEAD: [u8; 4] = [0x11, 0x4D, 0x9B, 0x74];
const ID_SEEK: [u8; 2] = [0x4D, 0xBB];
const ID_SEEK_ID: [u8; 2] = [0x53, 0xAB];
const ID_SEEK_POSITION: [u8; 2] = [0x53, 0xAC];
const ID_INFO: [u8; 4] = [0x15, 0x49, 0xA9, 0x66];
const ID_TIMESTAMP_SCALE: [u8; 3] = [0x2A, 0xD7, 0xB1];
const ID_DURATION: [u8; 2] = [0x44, 0x89];
const ID_MUXING_APP: [u8; 2] = [0x4D, 0x80];
const ID_WRITING_APP: [u8; 2] = [0x57, 0x41];
const ID_TRACKS: [u8; 4] = [0x16, 0x54, 0xAE, 0x6B];
const ID_TRACK_ENTRY: [u8; 1] = [0xAE];
const ID_TRACK_NUMBER: [u8; 1] = [0xD7];
const ID_TRACK_UID: [u8; 2] = [0x73, 0xC5];
const ID_TRACK_TYPE: [u8; 1] = [0x83];
const ID_CODEC_ID: [u8; 1] = [0x86];
const ID_CODEC_PRIVATE: [u8; 2] = [0x63, 0xA2];
const ID_VIDEO: [u8; 1] = [0xE0];
const ID_PIXEL_WIDTH: [u8; 1] = [0xB0];
const ID_PIXEL_HEIGHT: [u8; 1] = [0xBA];
const ID_AUDIO: [u8; 1] = [0xE1];
const ID_SAMPLING_FREQUENCY: [u8; 1] = [0xB5];
const ID_CHANNELS: [u8; 1] = [0x9F];
const ID_CLUSTER: [u8; 4] = [0x1F, 0x43, 0xB6, 0x75];
const ID_TIMESTAMP: [u8; 1] = [0xE7];
const ID_SIMPLE_BLOCK: [u8; 1] = [0xA3];
const ID_CUES: [u8; 4] = [0x1C, 0x53, 0xBB, 0x6B];
const ID_CUE_POINT: [u8; 1] = [0xBB];
const ID_CUE_TIME: [u8; 1] = [0xB3];
const ID_CUE_TRACK_POSITIONS: [u8; 1] = [0xB7];
const ID_CUE_TRACK: [u8; 1] = [0xF7];
const ID_CUE_CLUSTER_POSITION: [u8; 1] = [0xF1];

/// `TrackType` value for a video track (RFC 9559 §27 `TrackType`).
const TRACK_TYPE_VIDEO: u64 = 1;
/// `TrackType` value for an audio track.
const TRACK_TYPE_AUDIO: u64 = 2;
/// `SimpleBlock` keyframe flag (bit `[7]` of the flags byte, RFC 9559 §12).
const BLOCK_FLAG_KEYFRAME: u8 = 0x80;
/// Fixed bytes in a `SimpleBlock` body besides the track-number VINT and the
/// frame: the `i16` relative timestamp and the flags byte (RFC 9559 §12.4).
const SIMPLE_BLOCK_FIXED_LEN: usize = 2 + 1;

/// `TimestampScale` this writer always emits: 1 ms per tick (RFC 9559 §27
/// default, and the value that makes a [`crate::webm_demux::WebmDemux`]-sourced
/// [`Media`] — whose IR timescale is also milliseconds — rescale losslessly).
const TIMESTAMP_SCALE_NS: u64 = 1_000_000;
/// Nanoseconds per second (track-timescale → `TimestampScale`-tick conversion).
const NS_PER_SECOND: u64 = 1_000_000_000;
/// `MuxingApp` / `WritingApp` value this writer emits.
const APP_NAME: &[u8] = b"transmux";

/// Maximum ticks (ms, given [`TIMESTAMP_SCALE_NS`]) between `Cluster`
/// boundaries when the [`Media`] has at least one video track (a new
/// `Cluster` also starts at every video keyframe, whichever comes first).
const MAX_CLUSTER_SPAN_WITH_VIDEO_TICKS: i64 = 5_000;
/// Maximum ticks between `Cluster` boundaries for an audio-only [`Media`].
const MAX_CLUSTER_SPAN_AUDIO_ONLY_TICKS: i64 = 1_000;

/// The inclusive range a `SimpleBlock`'s relative timestamp may occupy: it is
/// a `signed int(16)` in ticks (RFC 9559 §12).
const MIN_BLOCK_REL_TICKS: i64 = i16::MIN as i64;
/// The inclusive upper bound of [`MIN_BLOCK_REL_TICKS`].
const MAX_BLOCK_REL_TICKS: i64 = i16::MAX as i64;

/// Fixed byte width `SeekPosition` entries are written at (RFC 8794 §4 allows
/// any *value* to be stored in more bytes than its minimal encoding — the
/// magnitude is unaffected by leading zero bytes): this keeps `SeekHead`'s own
/// serialized length independent of the position *values* it carries, so it
/// can be sized from a placeholder build before the real positions (which
/// depend on that very length) are known. 4 bytes bounds a `SeekPosition` to
/// 4 GiB, ample for `Info`/`Tracks` (always well under 64 KiB in practice).
const SEEK_POSITION_FIXED_WIDTH: usize = 4;

// ---------------------------------------------------------------------------
// Matroska CodecIDs (RFC 9559 §27 codec-mapping registry) — mirrors the set
// `crate::webm_demux::WebmDemux` maps in the opposite direction, plus the
// ISOBMFF-family video/audio codecs a DVR recording carries.
// ---------------------------------------------------------------------------

const CODEC_V_AVC: &[u8] = b"V_MPEG4/ISO/AVC";
const CODEC_V_HEVC: &[u8] = b"V_MPEGH/ISO/HEVC";
const CODEC_V_VP9: &[u8] = b"V_VP9";
const CODEC_V_VP8: &[u8] = b"V_VP8";
const CODEC_V_AV1: &[u8] = b"V_AV1";
const CODEC_A_AAC: &[u8] = b"A_AAC";
const CODEC_A_OPUS: &[u8] = b"A_OPUS";
const CODEC_A_VORBIS: &[u8] = b"A_VORBIS";
const CODEC_A_AC3: &[u8] = b"A_AC3";
const CODEC_A_EAC3: &[u8] = b"A_EAC3";

/// `OpusHead` identification-header magic (RFC 7845 §5.1).
const OPUS_HEAD_MAGIC: &[u8; 8] = b"OpusHead";

// ---------------------------------------------------------------------------
// EBML element write helpers (RFC 8794 §4)
// ---------------------------------------------------------------------------

/// Encode an EBML element **size** VINT (RFC 8794 §4): the minimal width (1-8
/// bytes) whose leading `1` marker bit plus the remaining data bits can
/// represent `value`. The same encoding also serves an element **ID**'s
/// *referenced* value where a VINT-with-marker is required (e.g. a
/// `SimpleBlock`'s track number, RFC 9559 §12) — width selection is identical.
///
/// Values at or above `2^56` would need a 9+-byte encoding this function does
/// not produce (EBML's own DocType/element-ID width caps make this
/// unreachable for anything this module writes — element sizes, byte offsets,
/// and track numbers all stay far below that bound in practice).
fn encode_vint_size(value: u64) -> Vec<u8> {
    let width: usize = if value <= 0x7E {
        1
    } else if value <= 0x3FFE {
        2
    } else if value <= 0x1F_FFFE {
        3
    } else if value <= 0x0FFF_FFFE {
        4
    } else if value <= 0x07_FFFF_FFFE {
        5
    } else {
        8
    };
    let marker = 1u64 << (width * 7);
    let encoded = marker | value;
    encoded.to_be_bytes()[8 - width..].to_vec()
}

/// The VINT size field for a body of `len` bytes (a `usize` length can only
/// fail to fit `u64` on a platform wider than any this crate targets; saturate
/// rather than wrap).
fn len_vint(len: usize) -> Vec<u8> {
    encode_vint_size(u64::try_from(len).unwrap_or(u64::MAX))
}

/// Write one EBML element: `id` bytes, then the VINT size of `body`, then
/// `body` verbatim.
fn element(id: &[u8], body: &[u8]) -> Vec<u8> {
    let size = encode_vint_size(body.len() as u64);
    let mut out = Vec::with_capacity(id.len() + size.len() + body.len());
    out.extend_from_slice(id);
    out.extend_from_slice(&size);
    out.extend_from_slice(body);
    out
}

/// Write a master element: the concatenation of `children`'s already-encoded
/// bytes, wrapped in `id`/size.
fn master(id: &[u8], children: &[Vec<u8>]) -> Vec<u8> {
    let body_len: usize = children.iter().map(Vec::len).sum();
    let size = len_vint(body_len);
    let mut out = Vec::with_capacity(id.len() + size.len() + body_len);
    out.extend_from_slice(id);
    out.extend_from_slice(&size);
    for child in children {
        out.extend_from_slice(child);
    }
    out
}

/// The minimal big-endian byte encoding of a uint element body (RFC 8794 §4:
/// a uint element's value is however many bytes are present, big-endian; `0`
/// still needs one byte).
fn uint_bytes(value: u64) -> Vec<u8> {
    if value == 0 {
        return vec![0u8];
    }
    let full = value.to_be_bytes();
    let first_nonzero = full.iter().position(|&b| b != 0).unwrap_or(7);
    full[first_nonzero..].to_vec()
}

/// Write a uint element at its minimal byte width.
fn uint_elem(id: &[u8], value: u64) -> Vec<u8> {
    element(id, &uint_bytes(value))
}

/// Write a uint element at a caller-fixed byte width (padded with leading
/// zero bytes) — see [`SEEK_POSITION_FIXED_WIDTH`] for why this exists.
fn fixed_uint_elem(id: &[u8], value: u64, width: usize) -> Vec<u8> {
    let full = value.to_be_bytes();
    element(id, &full[8 - width..])
}

/// Write a string/UTF-8 element (verbatim ASCII/UTF-8 bytes, no terminator).
fn string_elem(id: &[u8], s: &[u8]) -> Vec<u8> {
    element(id, s)
}

/// Write a binary element (verbatim opaque bytes — `CodecPrivate`, …).
fn binary_elem(id: &[u8], data: &[u8]) -> Vec<u8> {
    element(id, data)
}

/// Write a float element (8-byte IEEE 754 big-endian — this writer always
/// uses the 64-bit float width for `Duration`/`SamplingFrequency`).
fn float64_elem(id: &[u8], value: f64) -> Vec<u8> {
    element(id, &value.to_be_bytes())
}

// ---------------------------------------------------------------------------
// EBML Header
// ---------------------------------------------------------------------------

fn build_ebml_header() -> Vec<u8> {
    master(
        &ID_EBML,
        &[
            uint_elem(&ID_EBML_VERSION, EBML_VERSION_VALUE),
            uint_elem(&ID_EBML_READ_VERSION, EBML_READ_VERSION_VALUE),
            uint_elem(&ID_EBML_MAX_ID_LENGTH, EBML_MAX_ID_LENGTH_VALUE),
            uint_elem(&ID_EBML_MAX_SIZE_LENGTH, EBML_MAX_SIZE_LENGTH_VALUE),
            string_elem(&ID_DOC_TYPE, DOC_TYPE),
            uint_elem(&ID_DOC_TYPE_VERSION, DOC_TYPE_VERSION_VALUE),
            uint_elem(&ID_DOC_TYPE_READ_VERSION, DOC_TYPE_READ_VERSION_VALUE),
        ],
    )
}

// ---------------------------------------------------------------------------
// Info
// ---------------------------------------------------------------------------

fn build_info(duration_ticks: f64) -> Vec<u8> {
    master(
        &ID_INFO,
        &[
            uint_elem(&ID_TIMESTAMP_SCALE, TIMESTAMP_SCALE_NS),
            float64_elem(&ID_DURATION, duration_ticks),
            string_elem(&ID_MUXING_APP, APP_NAME),
            string_elem(&ID_WRITING_APP, APP_NAME),
        ],
    )
}

// ---------------------------------------------------------------------------
// SeekHead
// ---------------------------------------------------------------------------

/// One `Seek` entry: the target element's ID, and its byte offset relative to
/// the `Segment` payload start, written at [`SEEK_POSITION_FIXED_WIDTH`].
fn seek_entry(target_id: &[u8], position: u64) -> Vec<u8> {
    master(
        &ID_SEEK,
        &[
            binary_elem(&ID_SEEK_ID, target_id),
            fixed_uint_elem(&ID_SEEK_POSITION, position, SEEK_POSITION_FIXED_WIDTH),
        ],
    )
}

/// Build `SeekHead`, indexing `Info` and `Tracks` at the given byte offsets
/// (relative to the `Segment` payload start).
fn build_seek_head(pos_info: u64, pos_tracks: u64) -> Vec<u8> {
    master(
        &ID_SEEK_HEAD,
        &[
            seek_entry(&ID_INFO, pos_info),
            seek_entry(&ID_TRACKS, pos_tracks),
        ],
    )
}

// ---------------------------------------------------------------------------
// Tracks / TrackEntry
// ---------------------------------------------------------------------------

fn video_elem(width: u16, height: u16) -> Vec<u8> {
    master(
        &ID_VIDEO,
        &[
            uint_elem(&ID_PIXEL_WIDTH, width as u64),
            uint_elem(&ID_PIXEL_HEIGHT, height as u64),
        ],
    )
}

fn audio_elem(channels: u16, sample_rate: u32) -> Vec<u8> {
    master(
        &ID_AUDIO,
        &[
            uint_elem(&ID_CHANNELS, channels as u64),
            float64_elem(&ID_SAMPLING_FREQUENCY, sample_rate as f64),
        ],
    )
}

/// Rebuild the raw `OpusHead` identification header (RFC 7845 §5.1) from a
/// decoded [`OpusSpecificBox`] — the exact inverse of
/// `webm_demux::opus_config`'s parse.
fn build_opus_head(dops: &OpusSpecificBox) -> Vec<u8> {
    let mut out = Vec::with_capacity(19);
    out.extend_from_slice(OPUS_HEAD_MAGIC);
    out.push(dops.version);
    out.push(dops.output_channel_count);
    out.extend_from_slice(&dops.pre_skip.to_le_bytes());
    out.extend_from_slice(&dops.input_sample_rate.to_le_bytes());
    out.extend_from_slice(&dops.output_gain.to_le_bytes());
    out.push(dops.channel_mapping_family);
    if let Some(map) = &dops.channel_mapping {
        out.push(map.stream_count);
        out.push(map.coupled_count);
        out.extend_from_slice(&map.channel_mapping);
    }
    out
}

/// A human-readable name for a [`CodecConfig`] variant, for
/// [`Error::UnsupportedMkvCodec`]'s message.
fn codec_debug_name(config: &CodecConfig) -> &'static str {
    match config {
        CodecConfig::Avc { .. } => "AVC",
        CodecConfig::Hevc { .. } => "HEVC",
        CodecConfig::Vvc { .. } => "VVC",
        CodecConfig::Aac { .. } => "AAC",
        CodecConfig::Ac3 { .. } => "AC-3",
        CodecConfig::Eac3 { .. } => "E-AC-3",
        CodecConfig::Av1 { .. } => "AV1",
        CodecConfig::Vp9 { .. } => "VP9",
        CodecConfig::Vp8 { .. } => "VP8",
        CodecConfig::Opus { .. } => "Opus",
        CodecConfig::Flac { .. } => "FLAC",
        CodecConfig::Ac4 { .. } => "AC-4",
        CodecConfig::MpegH { .. } => "MPEG-H 3D Audio",
        CodecConfig::Mpeg2Video { .. } => "MPEG-2 Video",
        CodecConfig::MpegAudio { .. } => "MPEG-1/2 Audio",
        CodecConfig::Dts { .. } => "DTS",
        CodecConfig::Vorbis { .. } => "Vorbis",
        CodecConfig::Subtitle { .. } => "Subtitle",
        CodecConfig::Data { .. } => "Data",
    }
}

/// Build one `TrackEntry`, returning its bytes plus whether it is a video
/// track. `track_number` is the 1-based Matroska track number (this crate
/// assigns them sequentially in [`Media::tracks`] order); `track_id` supplies
/// `TrackUID`.
fn build_track_entry(
    track_number: u64,
    track_id: TrackId,
    config: &CodecConfig,
) -> Result<(Vec<u8>, bool)> {
    let is_video = config.is_video();
    let track_type = if is_video {
        TRACK_TYPE_VIDEO
    } else {
        TRACK_TYPE_AUDIO
    };

    let (codec_id, codec_private, sub_elem): (&'static [u8], Option<Vec<u8>>, Vec<u8>) =
        match config {
            CodecConfig::Avc {
                config,
                width,
                height,
            } => (
                CODEC_V_AVC,
                Some(config.config.try_to_bytes()?),
                video_elem(*width, *height),
            ),
            CodecConfig::Hevc {
                config,
                width,
                height,
            } => (
                CODEC_V_HEVC,
                Some(config.config.try_to_bytes()?),
                video_elem(*width, *height),
            ),
            CodecConfig::Vp9 { width, height, .. } => {
                (CODEC_V_VP9, None, video_elem(*width, *height))
            }
            CodecConfig::Vp8 { width, height } => (CODEC_V_VP8, None, video_elem(*width, *height)),
            CodecConfig::Av1 {
                config,
                width,
                height,
            } => (
                CODEC_V_AV1,
                Some(config.try_to_bytes()?),
                video_elem(*width, *height),
            ),
            CodecConfig::Aac {
                esds,
                channel_count,
                sample_rate,
                ..
            } => {
                let asc = esds
                    .es_descriptor
                    .decoder_config
                    .as_ref()
                    .and_then(|dc| dc.decoder_specific_info.as_ref())
                    .map(|dsi| dsi.data.clone())
                    .ok_or(Error::InvalidInput(
                        "AAC esds has no DecoderSpecificInfo (AudioSpecificConfig) to carry as \
                     Matroska CodecPrivate",
                    ))?;
                (
                    CODEC_A_AAC,
                    Some(asc),
                    audio_elem(*channel_count, *sample_rate),
                )
            }
            CodecConfig::Opus {
                config,
                channel_count,
                sample_rate,
                ..
            } => (
                CODEC_A_OPUS,
                Some(build_opus_head(config)),
                audio_elem(*channel_count, *sample_rate),
            ),
            CodecConfig::Vorbis {
                codec_private,
                channels,
                sample_rate,
            } => (
                CODEC_A_VORBIS,
                Some(codec_private.clone()),
                audio_elem(*channels, *sample_rate),
            ),
            CodecConfig::Ac3 {
                channel_count,
                sample_rate,
                ..
            } => (CODEC_A_AC3, None, audio_elem(*channel_count, *sample_rate)),
            CodecConfig::Eac3 {
                channel_count,
                sample_rate,
                ..
            } => (CODEC_A_EAC3, None, audio_elem(*channel_count, *sample_rate)),
            other => {
                return Err(Error::UnsupportedMkvCodec {
                    codec: codec_debug_name(other),
                });
            }
        };

    let mut children = vec![
        uint_elem(&ID_TRACK_NUMBER, track_number),
        uint_elem(&ID_TRACK_UID, u64::from(track_id.value())),
        uint_elem(&ID_TRACK_TYPE, track_type),
        string_elem(&ID_CODEC_ID, codec_id),
        sub_elem,
    ];
    if let Some(priv_bytes) = codec_private {
        children.push(binary_elem(&ID_CODEC_PRIVATE, &priv_bytes));
    }
    Ok((master(&ID_TRACK_ENTRY, &children), is_video))
}

// ---------------------------------------------------------------------------
// Cluster / SimpleBlock / Cues
// ---------------------------------------------------------------------------

/// One sample, resolved to its global Matroska (`TimestampScale`-tick)
/// presentation time, ready to be placed into a `Cluster`.
#[derive(Debug, Clone, Copy)]
struct BlockEvent {
    /// Index into [`Media::tracks`].
    track_index: usize,
    /// 1-based Matroska `TrackNumber`.
    track_number: u64,
    /// Index into the track's `samples`.
    sample_index: usize,
    /// Absolute presentation time, in `TimestampScale` ticks.
    pts_ticks: i64,
    /// Whether this sample is a sync sample (random-access point).
    is_keyframe: bool,
    /// Whether this event's track is video.
    is_video: bool,
}

/// Convert a tick value in `track_timescale` units to `TimestampScale` ticks
/// (the inverse of `webm_demux::parse_block`'s `raw_ticks * scale_ns /
/// ns_per_ir_tick`): `ticks / track_timescale` seconds, expressed in
/// [`TIMESTAMP_SCALE_NS`]-sized ticks.
fn to_matroska_ticks(ticks: i64, track_timescale: u32, timestamp_scale_ns: u64) -> i64 {
    if track_timescale == 0 {
        return 0;
    }
    let ns = (ticks as i128) * (NS_PER_SECOND as i128) / (track_timescale as i128);
    (ns / timestamp_scale_ns as i128) as i64
}

/// Bytes of the body of a `SimpleBlock` (track-number VINT + `i16` + flags + frame).
fn simple_block_body_len(track_number: u64, data_len: usize) -> usize {
    encode_vint_size(track_number).len() + SIMPLE_BLOCK_FIXED_LEN + data_len
}

/// Total encoded length of a `SimpleBlock` element (id + size VINT + body).
fn simple_block_len(track_number: u64, data_len: usize) -> usize {
    let body = simple_block_body_len(track_number, data_len);
    ID_SIMPLE_BLOCK.len() + len_vint(body).len() + body
}

/// Append one `SimpleBlock` (RFC 9559 §12): track-number VINT, signed int16
/// relative timestamp, flags byte (keyframe bit only — no lacing), then the
/// frame. The frame is copied once, straight into the destination, never
/// through a body buffer and an element buffer (audit r05-O4).
fn write_simple_block(
    out: &mut Vec<u8>,
    track_number: u64,
    rel_ts: i16,
    is_keyframe: bool,
    data: &[u8],
) {
    let body = simple_block_body_len(track_number, data.len());
    out.extend_from_slice(&ID_SIMPLE_BLOCK);
    out.extend_from_slice(&len_vint(body));
    out.extend_from_slice(&encode_vint_size(track_number));
    out.extend_from_slice(&rel_ts.to_be_bytes());
    out.push(if is_keyframe { BLOCK_FLAG_KEYFRAME } else { 0 });
    out.extend_from_slice(data);
}

/// Group a time-interleaved (decode-order-preserving per track — see
/// [`MkvMux`]'s `package` impl) [`BlockEvent`] stream into `Cluster`s: a new
/// `Cluster` starts at every video keyframe (when any track is video), and in
/// any case at least every `max_span` ticks. See the module docs.
fn build_clusters(events: &[BlockEvent], has_video: bool) -> Vec<Vec<BlockEvent>> {
    let max_span = if has_video {
        MAX_CLUSTER_SPAN_WITH_VIDEO_TICKS
    } else {
        MAX_CLUSTER_SPAN_AUDIO_ONLY_TICKS
    };
    let mut clusters: Vec<Vec<BlockEvent>> = Vec::new();
    let mut current: Vec<BlockEvent> = Vec::new();
    // The base `build_cluster` will write for the current `Cluster`: the
    // first event's timestamp, or 0 when that is negative (an unsigned
    // `Timestamp` cannot name it).
    let mut cluster_start: i64 = 0;
    for &ev in events {
        // A `SimpleBlock`'s timestamp is a *signed* 16-bit value relative to
        // the `Cluster` timestamp (RFC 9559 §12). A forward-only span rule is
        // not enough: a backward step (a TS splice or signalled
        // discontinuity, a timestamp wrap, or a large B-frame reorder across a
        // keyframe) keeps `rel` inside the same `Cluster`, and once it drops
        // below `i16::MIN` the `debug_assert` fires in debug builds while a
        // release build wraps the cast and puts the block at an arbitrary
        // time. Start a new `Cluster` whenever `rel` would leave the range, in
        // either direction (audit r05-W23).
        let rel = ev.pts_ticks - cluster_start;
        let start_new = current.is_empty()
            || (has_video && ev.is_video && ev.is_keyframe)
            || rel >= max_span
            || !(MIN_BLOCK_REL_TICKS..=MAX_BLOCK_REL_TICKS).contains(&rel);
        if start_new && !current.is_empty() {
            clusters.push(core::mem::take(&mut current));
        }
        if current.is_empty() {
            // The same base `build_cluster` writes, so this function's range
            // check and that one's are the same invariant.
            cluster_start = ev.pts_ticks.max(0);
        }
        current.push(ev);
    }
    if !current.is_empty() {
        clusters.push(current);
    }
    clusters
}

/// Serialize one `Cluster`: its base `Timestamp` (the first event's presentation
/// time) then a `SimpleBlock` per event, in order.
fn build_cluster(events: &[BlockEvent], tracks: &[Track]) -> Result<Vec<u8>> {
    let first_ticks = events.first().map(|e| e.pts_ticks).unwrap_or(0);
    // A `Cluster` `Timestamp` is an *unsigned* integer (RFC 9559 §13), so a
    // negative base cannot be written. The old code wrote `cluster_start.max(0)`
    // as the base while every block stayed relative to the *negative*
    // `cluster_start`, so every block of the first `Cluster` came out shifted
    // by `-cluster_start` ms — the ordinary case of a negative first PTS from
    // B-frame composition (audit r05-W23). The base is now the same value the
    // blocks are measured against, so their relative spacing is exact; a
    // negative absolute first timestamp simply starts at `Timestamp = 0`, the
    // earliest instant an unsigned field can name.
    let base = first_ticks.max(0);
    let timestamp = uint_elem(&ID_TIMESTAMP, base as u64);
    // First pass: validate every relative timestamp and size the cluster, so the
    // second pass writes each frame exactly once into a pre-sized buffer.
    let mut rels: Vec<i16> = Vec::with_capacity(events.len());
    let mut body_len = timestamp.len();
    for ev in events {
        let rel_i64 = ev.pts_ticks - base;
        // A silent `clamp` would write a *wrong* block time in release builds
        // (where `debug_assert` does nothing) — the `SimpleBlock` would sit at
        // an arbitrary instant rather than where its sample is. `build_clusters`
        // guarantees the range, so a violation here is a bug, and a bug is an
        // error, not a mangle (audit item 7).
        let rel = i16::try_from(rel_i64).map_err(|_| {
            Error::InvalidInput(
                "mkv_mux: cluster relative timestamp exceeds the SimpleBlock i16 range",
            )
        })?;
        rels.push(rel);
        let data_len = tracks[ev.track_index].samples[ev.sample_index].data.len();
        body_len += simple_block_len(ev.track_number, data_len);
    }
    let size = len_vint(body_len);
    let mut out = Vec::with_capacity(ID_CLUSTER.len() + size.len() + body_len);
    out.extend_from_slice(&ID_CLUSTER);
    out.extend_from_slice(&size);
    out.extend_from_slice(&timestamp);
    for (ev, &rel) in events.iter().zip(&rels) {
        let data = &tracks[ev.track_index].samples[ev.sample_index].data;
        write_simple_block(&mut out, ev.track_number, rel, ev.is_keyframe, data);
    }
    Ok(out)
}

/// Build `Cues`: one `CuePoint` per **video** keyframe (never audio — every
/// audio sample in this IR is a sync sample, so indexing them would defeat
/// the point of an index). Returns an empty `Vec` (nothing written) when
/// there is no video keyframe to index.
fn build_cues(clusters: &[Vec<BlockEvent>], cluster_offsets: &[u64]) -> Vec<u8> {
    let mut cue_points: Vec<Vec<u8>> = Vec::new();
    // `CueTime`s must be non-decreasing (RFC 9559 §20: "The CueTime … of the
    // CuePoint … SHOULD be sorted"). A backward timestamp jump opens a new
    // `Cluster` (r05-W23), so a later cluster's keyframe can sit at an
    // *earlier* presentation time than an earlier one.
    //
    // Every keyframe still gets a cue — silently dropping one would make its
    // cluster unreachable by seeking, which is the whole point of the index
    // (audit item 8, round 3). Such a point is emitted at the last cue time
    // (`max(cue_time, last)`), which keeps the index sorted while pointing at
    // the right cluster; two cue points may then share a `CueTime`, which
    // §20 permits (the sort is what is required, not uniqueness).
    let mut last_cue_time: Option<i64> = None;
    for (cluster, &offset) in clusters.iter().zip(cluster_offsets) {
        for ev in cluster {
            if ev.is_video && ev.is_keyframe {
                let raw = ev.pts_ticks.max(0);
                let cue_time = last_cue_time.map_or(raw, |last| raw.max(last));
                last_cue_time = Some(cue_time);
                let track_positions = master(
                    &ID_CUE_TRACK_POSITIONS,
                    &[
                        uint_elem(&ID_CUE_TRACK, ev.track_number),
                        uint_elem(&ID_CUE_CLUSTER_POSITION, offset),
                    ],
                );
                cue_points.push(master(
                    &ID_CUE_POINT,
                    &[uint_elem(&ID_CUE_TIME, cue_time as u64), track_positions],
                ));
            }
        }
    }
    if cue_points.is_empty() {
        return Vec::new();
    }
    master(&ID_CUES, &cue_points)
}

// ---------------------------------------------------------------------------
// MkvMux
// ---------------------------------------------------------------------------

/// Package a [`Media`] into a Matroska (`.mkv`) file.
///
/// Implements [`broadcast_common::Package`] with `Output = Vec<u8>`: the
/// whole file (EBML header + `Segment`) is returned as one byte vector. See
/// the module docs for scope, cluster strategy, and the `SeekHead`/`Cues`
/// layout.
#[derive(Debug, Clone, Copy, Default)]
pub struct MkvMux {
    _private: (),
}

impl MkvMux {
    /// Create a new muxer.
    pub fn new() -> Self {
        Self::default()
    }
}

impl Package for MkvMux {
    type Media = Media;
    type Output = Vec<u8>;
    type Error = Error;

    fn package(&mut self, media: &Media) -> Result<Vec<u8>> {
        if media.tracks.is_empty() {
            return Err(Error::InvalidInput("cannot package a Media with no tracks"));
        }

        // Resolve every TrackEntry up front (fails fast, naming the track, for
        // any codec this module has no Matroska CodecID mapping for).
        let mut track_entries: Vec<Vec<u8>> = Vec::with_capacity(media.tracks.len());
        let mut is_video_track: Vec<bool> = Vec::with_capacity(media.tracks.len());
        for (i, track) in media.tracks.iter().enumerate() {
            let track_number = (i + 1) as u64;
            let (entry, is_video) =
                build_track_entry(track_number, track.spec.track_id, &track.spec.config)?;
            track_entries.push(entry);
            is_video_track.push(is_video);
        }
        let has_video = is_video_track.iter().any(|&v| v);

        // Every track's own samples are in **decode** order (`Track::samples`'
        // documented invariant) — for AVC/HEVC with B-frame reordering, decode
        // order is not presentation-time order (a P-frame decodes before, but
        // may present after, the B-frames that reference it), so a track's own
        // `pts_ticks` sequence is not necessarily monotonic. Interleaving
        // tracks by a global sort on `pts_ticks` would therefore reorder a
        // track's blocks relative to each other and desync decode from
        // reference — instead, a k-way merge walks each track's cursor forward
        // one sample at a time (never reordering *within* a track) and always
        // takes whichever track's *next* sample has the smallest presentation
        // time, which only decides *when* to interleave the tracks.
        let per_track_ticks: Vec<Vec<i64>> = media
            .tracks
            .iter()
            .map(|track| {
                let timescale = track.timescale();
                track
                    .samples
                    .iter()
                    .map(|s| {
                        to_matroska_ticks(
                            s.pts.or(s.dts).unwrap_or(0),
                            timescale,
                            TIMESTAMP_SCALE_NS,
                        )
                    })
                    .collect()
            })
            .collect();

        let mut duration_ticks: i64 = 0;
        for track in &media.tracks {
            let timescale = track.timescale();
            for sample in &track.samples {
                let pts = sample.pts.or(sample.dts).unwrap_or(0);
                let end_ticks = to_matroska_ticks(
                    pts + sample.duration.unwrap_or(0) as i64,
                    timescale,
                    TIMESTAMP_SCALE_NS,
                );
                if end_ticks > duration_ticks {
                    duration_ticks = end_ticks;
                }
            }
        }

        let mut cursors = vec![0usize; media.tracks.len()];
        let mut events: Vec<BlockEvent> = Vec::new();
        loop {
            let mut best: Option<(usize, i64)> = None;
            for (i, track) in media.tracks.iter().enumerate() {
                if cursors[i] < track.samples.len() {
                    let pts_ticks = per_track_ticks[i][cursors[i]];
                    if best.is_none_or(|(_, best_ticks)| pts_ticks < best_ticks) {
                        best = Some((i, pts_ticks));
                    }
                }
            }
            let Some((i, pts_ticks)) = best else { break };
            let si = cursors[i];
            cursors[i] += 1;
            events.push(BlockEvent {
                track_index: i,
                track_number: (i + 1) as u64,
                sample_index: si,
                pts_ticks,
                is_keyframe: media.tracks[i].samples[si].flags.is_sync,
                is_video: is_video_track[i],
            });
        }

        let info_bytes = build_info(duration_ticks as f64);
        let tracks_bytes = master(&ID_TRACKS, &track_entries);

        // SeekHead: sized from a placeholder build (see SEEK_POSITION_FIXED_WIDTH),
        // then rebuilt with the real Info/Tracks offsets at the same size.
        let seekhead_placeholder = build_seek_head(0, 0);
        let pos_info = seekhead_placeholder.len() as u64;
        let pos_tracks = pos_info + info_bytes.len() as u64;
        let seekhead_bytes = build_seek_head(pos_info, pos_tracks);
        debug_assert_eq!(
            seekhead_bytes.len(),
            seekhead_placeholder.len(),
            "SeekHead's serialized size must be independent of its SeekPosition values"
        );

        let clusters = build_clusters(&events, has_video);
        let mut cluster_bytes: Vec<Vec<u8>> = Vec::with_capacity(clusters.len());
        let mut cluster_offsets: Vec<u64> = Vec::with_capacity(clusters.len());
        let mut running_offset = pos_tracks + tracks_bytes.len() as u64;
        for cluster in &clusters {
            cluster_offsets.push(running_offset);
            let bytes = build_cluster(cluster, &media.tracks)?;
            running_offset += bytes.len() as u64;
            cluster_bytes.push(bytes);
        }

        let cues_bytes = build_cues(&clusters, &cluster_offsets);

        // Header, then the Segment's parts written straight into the one output
        // buffer (not first concatenated into a payload `Vec` and copied again).
        let parts: Vec<&[u8]> = [
            seekhead_bytes.as_slice(),
            info_bytes.as_slice(),
            tracks_bytes.as_slice(),
        ]
        .into_iter()
        .chain(cluster_bytes.iter().map(Vec::as_slice))
        .chain(core::iter::once(cues_bytes.as_slice()))
        .collect();
        let payload_len: usize = parts.iter().map(|p| p.len()).sum();
        let size = len_vint(payload_len);
        let mut out = build_ebml_header();
        out.reserve_exact(ID_SEGMENT.len() + size.len() + payload_len);
        out.extend_from_slice(&ID_SEGMENT);
        out.extend_from_slice(&size);
        for part in parts {
            out.extend_from_slice(part);
        }
        Ok(out)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// T15: an `avcC` with more than 31 SPS cannot be encoded (5-bit count);
    /// the Matroska CodecPrivate build must return `Err`, not panic.
    #[test]
    fn avc_codec_private_over_range_errors_not_panics() {
        use crate::avc_config::{AVCConfigurationBox, AVCDecoderConfigurationRecord};
        use crate::nalu_types::AvcSps;
        let config = CodecConfig::Avc {
            config: AVCConfigurationBox {
                config: AVCDecoderConfigurationRecord {
                    configuration_version: 1,
                    profile_indication: 0x42,
                    profile_compatibility: 0,
                    level_indication: 0x1F,
                    length_size_minus_one: 3,
                    sps: vec![AvcSps(vec![0x67, 0x42]); 32],
                    pps: vec![],
                    chroma_format: None,
                    bit_depth_luma_minus8: None,
                    bit_depth_chroma_minus8: None,
                    sps_ext: vec![],
                },
            },
            width: 640,
            height: 480,
        };
        assert!(build_track_entry(1, TrackId::new(1), &config).is_err());
    }

    #[test]
    fn vint_size_widths() {
        assert_eq!(encode_vint_size(0), vec![0x80]);
        assert_eq!(encode_vint_size(1), vec![0x81]);
        assert_eq!(encode_vint_size(0x7E), vec![0xFE]);
        assert_eq!(encode_vint_size(0x7F), vec![0x40, 0x7F]);
        assert_eq!(encode_vint_size(2), vec![0x82]);
    }

    #[test]
    fn uint_bytes_widths() {
        assert_eq!(uint_bytes(0), vec![0u8]);
        assert_eq!(uint_bytes(1), vec![1u8]);
        assert_eq!(uint_bytes(1_000_000), vec![0x0F, 0x42, 0x40]);
    }

    #[test]
    fn opus_head_round_trips_via_field_reconstruction() {
        let dops = OpusSpecificBox {
            version: 1,
            output_channel_count: 1,
            pre_skip: 312,
            input_sample_rate: 48_000,
            output_gain: 0,
            channel_mapping_family: 0,
            channel_mapping: None,
        };
        let head = build_opus_head(&dops);
        assert_eq!(&head[0..8], OPUS_HEAD_MAGIC);
        assert_eq!(head[8], 1); // version
        assert_eq!(head[9], 1); // channels
        assert_eq!(u16::from_le_bytes([head[10], head[11]]), 312);
        assert_eq!(
            u32::from_le_bytes([head[12], head[13], head[14], head[15]]),
            48_000
        );
    }

    /// r05-W23(a): a backward presentation-time step must open a new
    /// `Cluster`, not push the `SimpleBlock`'s signed 16-bit relative
    /// timestamp out of range (which `debug_assert`s in debug builds and
    /// wraps the cast in release builds).
    #[test]
    fn backward_step_starts_a_new_cluster_instead_of_overflowing_the_block_timestamp() {
        let ev = |pts: i64, video: bool, key: bool| BlockEvent {
            track_index: 0,
            sample_index: 0,
            pts_ticks: pts,
            track_number: 1,
            is_keyframe: key,
            is_video: video,
        };
        // Start at 0, then jump back by 40 s — far outside i16's ±32.767 s.
        let events = alloc::vec![ev(0, false, false), ev(-40_000, false, false)];
        let clusters = build_clusters(&events, false);
        assert_eq!(
            clusters.len(),
            2,
            "a backward jump must start a new Cluster"
        );
        for cluster in &clusters {
            let base = cluster[0].pts_ticks;
            for e in cluster {
                let rel = e.pts_ticks - base;
                assert!(
                    (MIN_BLOCK_REL_TICKS..=MAX_BLOCK_REL_TICKS).contains(&rel),
                    "relative timestamp {rel} left the i16 range"
                );
            }
        }
    }

    /// r05-W23(b): a negative first PTS (an ordinary B-frame composition
    /// result) made `build_cluster` write `Timestamp = 0` while keeping every
    /// block relative to the negative base, shifting the whole first `Cluster`
    /// by `-cluster_start` ms. The cluster is now rebased, so the base is
    /// unsigned and the blocks keep their spacing.
    #[test]
    fn negative_first_pts_does_not_shift_the_cluster() {
        let file = concat!(env!("CARGO_MANIFEST_DIR"), "/../fixtures/mkv/vp9_opus.mkv");
        let Ok(bytes) = std::fs::read(file) else {
            eprintln!("SKIP negative_first_pts_does_not_shift_the_cluster: fixture missing");
            return;
        };
        let mut media = crate::webm_demux::WebmDemux::new()
            .demux(&bytes)
            .expect("demux fixture");
        // Shift the whole timeline negative, which is what a B-frame
        // composition (or a source with a pre-roll) produces.
        let shift: i64 = -30_000;
        for track in &mut media.tracks {
            for s in &mut track.samples {
                s.dts = s.dts.map(|v| v.saturating_add(shift));
                s.pts = s.pts.map(|v| v.saturating_add(shift));
            }
            // `start_decode_time` is unsigned; clamping to 0 is fine here
            // because the blocks' own `pts` carry the real negative base.
            track.start_decode_time = track.start_decode_time.saturating_sub(shift.unsigned_abs());
        }
        let out = MkvMux::new().package(&media).expect("package");
        // Locate the first Cluster and read its Timestamp + block timestamps.
        let (cluster_at, id_len, size_len, body_len) =
            find_element(&out, &ID_CLUSTER).expect("a Cluster");
        let cluster = &out[cluster_at..cluster_at + id_len + size_len + body_len];
        let (ts, rels) = cluster_timestamps(cluster);
        assert!(ts >= 0, "Cluster Timestamp is unsigned; got {ts}");
        assert!(!rels.is_empty(), "the first cluster carries blocks");
        // The base is 0 (a `Cluster` `Timestamp` is unsigned), so the shifted
        // timeline starts 30 s before it — repr sentable, and unchanged by the
        // rebase.
        assert_eq!(rels[0], -30_000, "the first block keeps its real offset");
        assert!(
            rels.windows(2).all(|w| w[1] >= w[0] - 1000),
            "blocks keep their relative spacing: {rels:?}"
        );
        // The blocks must span real time rather than collapse to one instant,
        // which is what the old `cluster_start.max(0)` base produced: every
        // block came out relative to the negative `cluster_start` while the
        // written base was 0, so the whole cluster was shifted.
        let span = rels.iter().max().unwrap() - rels.iter().min().unwrap();
        assert!(span > 0, "the cluster must span real time: {rels:?}");
    }

    /// The first top-level element whose id matches, returned as
    /// `(offset, id_len, body_len)`.
    ///
    /// Each level is walked by `id`/size pairs; every id this writer emits is a
    /// fixed 1, 2 or 4 bytes and every size is a VINT, see
    /// [`encode_vint_size`].
    fn find_element(data: &[u8], id: &[u8]) -> Option<(usize, usize, usize, usize)> {
        for c in 0..data.len().saturating_sub(id.len()) {
            if &data[c..c + id.len()] != id {
                continue;
            }
            // The writer emits every element id verbatim, so a match is a real
            // element as long as a valid size VINT follows.
            let Some((size, size_len)) = read_vint_size(data, c + id.len()) else {
                continue;
            };
            if c + id.len() + size_len + size > data.len() {
                continue;
            }
            return Some((c, id.len(), size_len, size));
        }
        None
    }

    /// The byte width of an EBML id whose first byte is `b` (the leading
    /// zero-bit count selects 1/2/3/4 bytes; RFC 8794 §4).
    fn vint_id_len(b: u8) -> Option<usize> {
        if b == 0 {
            return None;
        }
        Some(b.leading_zeros() as usize + 1)
    }

    /// Read a VINT size at `off`, returning `(size, width)`.
    fn read_vint_size(data: &[u8], off: usize) -> Option<(usize, usize)> {
        let width = vint_id_len(*data.get(off)?)?;
        if off + width > data.len() {
            return None;
        }
        let mut value = u64::from(data[off]) & (0xFF >> width);
        for i in 1..width {
            value = (value << 8) | u64::from(data[off + i]);
        }
        Some((value as usize, width))
    }

    /// Read a serialized `Cluster`'s `Timestamp` and each `SimpleBlock`'s
    /// relative timestamp, straight off the wire.
    ///
    /// Every element id and size this writer emits is a one-byte VINT here
    /// (`Timestamp`/`SimpleBlock` ids are single bytes; the bodies are far
    /// below the 127-byte one-byte-size limit), so the layout is fixed: a
    /// 1-byte id, a 1-byte size, then that many body bytes.
    fn cluster_timestamps(cluster: &[u8]) -> (i64, alloc::vec::Vec<i64>) {
        let id_len = vint_id_len(cluster[0]).expect("Cluster id");
        let (_, size_len) = read_vint_size(cluster, id_len).expect("Cluster size");
        let mut c = id_len + size_len;
        let mut timestamp = None;
        let mut rels = alloc::vec::Vec::new();
        while c < cluster.len() {
            let cid_len = vint_id_len(cluster[c]).expect("child id");
            let (size, csize_len) = read_vint_size(cluster, c + cid_len).expect("child size");
            let body_start = c + cid_len + csize_len;
            let body = &cluster[body_start..body_start + size];
            c = body_start + size;
            if cluster[c - size - csize_len - cid_len..c - size - csize_len] == ID_TIMESTAMP {
                let mut v = 0u64;
                for &b in body {
                    v = (v << 8) | u64::from(b);
                }
                timestamp = Some(v as i64);
            } else if cluster[c - size - csize_len - cid_len..c - size - csize_len]
                == ID_SIMPLE_BLOCK
            {
                // track-number VINT (1 byte for these fixtures), then int16.
                let tn_len = vint_id_len(body[0]).expect("track number");
                let rel = i16::from_be_bytes([body[tn_len], body[tn_len + 1]]) as i64;
                rels.push(rel);
            }
        }
        (timestamp.expect("Cluster has a Timestamp"), rels)
    }

    /// Independent oracle: a real negative timeline and a real backward jump
    /// must both produce a file ffmpeg reads with every packet intact —
    /// packet count, per-track monotonic PTS after the jump's rebase, and
    /// per-packet payload hashes all come from ffmpeg, not from this crate.
    /// This exercises the actual code paths (the earlier version of this test
    /// packaged the *unmodified* fixture, so it proved neither). Skips cleanly
    /// when `ffprobe` is absent.
    #[test]
    fn negative_timeline_and_backward_jump_are_ffprobe_readable() {
        if std::process::Command::new("ffprobe")
            .arg("-version")
            .output()
            .is_err()
        {
            eprintln!(
                "SKIP negative_timeline_and_backward_jump_are_ffprobe_readable:                  ffprobe not on PATH"
            );
            return;
        }
        let file = concat!(env!("CARGO_MANIFEST_DIR"), "/../fixtures/mkv/vp9_opus.mkv");
        let Ok(bytes) = std::fs::read(file) else {
            eprintln!(
                "SKIP negative_timeline_and_backward_jump_are_ffprobe_readable: fixture missing"
            );
            return;
        };
        let base = crate::webm_demux::WebmDemux::new()
            .demux(&bytes)
            .expect("demux fixture");

        // (a) the whole timeline shifted negative, and (b) a splice that steps
        // *backwards* by more than `i16::MAX` ticks (32.767 s) partway through
        // one track — the two shapes r05-W23 is about.
        let source_counts: Vec<usize> = base.tracks.iter().map(|t| t.samples.len()).collect();

        for (label, mutate) in [
            (
                "negative timeline",
                &(|m: &mut crate::media::Media| {
                    for track in &mut m.tracks {
                        for s in &mut track.samples {
                            s.dts = s.dts.map(|v| v.saturating_sub(500));
                            s.pts = s.pts.map(|v| v.saturating_sub(500));
                        }
                    }
                }) as &dyn Fn(&mut crate::media::Media),
            ),
            (
                "backward jump",
                &(|m: &mut crate::media::Media| {
                    // A real splice: the second half of the video track steps
                    // back 10 s. That is well inside the i16 range *per
                    // Cluster* while still being a backwards step the old
                    // forward-only span rule kept in one Cluster.
                    let half = m.tracks[0].samples.len() / 2;
                    for s in &mut m.tracks[0].samples[half..] {
                        s.dts = s.dts.map(|v| v.saturating_sub(10_000));
                        s.pts = s.pts.map(|v| v.saturating_sub(10_000));
                    }
                }) as &dyn Fn(&mut crate::media::Media),
            ),
        ] {
            let mut media = base.clone();
            mutate(&mut media);
            let out = MkvMux::new().package(&media).expect(label);
            let path = std::env::temp_dir().join(format!(
                "transmux-h7-{}-{}.mkv",
                std::process::id(),
                label.replace(' ', "_")
            ));
            std::fs::write(&path, &out).expect("write");
            let probe = std::process::Command::new("ffprobe")
                .args([
                    "-v",
                    "error",
                    "-show_packets",
                    "-show_data_hash",
                    "sha256",
                    "-show_entries",
                    "packet=stream_index,pts,data_hash",
                    "-of",
                    "csv",
                    path.to_str().expect("utf-8 path"),
                ])
                .output()
                .expect("run ffprobe");
            let stdout = String::from_utf8_lossy(&probe.stdout).into_owned();
            let stderr = String::from_utf8_lossy(&probe.stderr).into_owned();
            let _ = std::fs::remove_file(&path);
            assert!(
                stderr.is_empty(),
                "{label}: ffprobe -v error must be silent, got: {stderr}"
            );

            // Per-stream packet counts must match the source exactly, and
            // every timestamp ffprobe reports must be a real number (a
            // `clamp`ed or wrapped block shows up as a nonsense time).
            let mut counts: alloc::collections::BTreeMap<usize, usize> = Default::default();
            let mut last: alloc::collections::BTreeMap<usize, i64> = Default::default();
            let mut monotonic = alloc::collections::BTreeMap::new();
            // ffprobe's per-packet `sha256`, keyed by stream and position —
            // the independent check that the muxer carried the sample bytes
            // through unchanged (a wrong `stsc`/chunk offset corrupts them).
            let mut hashes: alloc::collections::BTreeMap<usize, alloc::vec::Vec<String>> =
                Default::default();
            for line in stdout.lines().filter(|l| l.starts_with("packet,")) {
                let parts: Vec<&str> = line.split(',').collect();
                let stream: usize = parts[1].parse().unwrap_or(usize::MAX);
                *counts.entry(stream).or_default() += 1;
                if let Some(hash) = parts
                    .get(3)
                    .filter(|h| h.to_ascii_uppercase().starts_with("SHA256:"))
                {
                    hashes
                        .entry(stream)
                        .or_default()
                        .push(hash.to_ascii_uppercase());
                }
                let Some(pts) = parts.get(2).and_then(|p| p.parse::<i64>().ok()) else {
                    // ffprobe prints `N/A` for a packet with no timestamp;
                    // those carry no ordering information to check.
                    continue;
                };
                if let Some(prev) = last.get(&stream)
                    && pts < *prev
                {
                    *monotonic.entry(stream).or_insert(0usize) += 1;
                }
                last.insert(stream, pts);
            }
            for (i, &expect) in source_counts.iter().enumerate() {
                assert_eq!(
                    counts.get(&i).copied().unwrap_or(0),
                    expect,
                    "{label}: stream {i} packet count"
                );
            }
            assert!(!counts.is_empty(), "{label}: ffprobe read packets");

            // ffprobe's own payload hashes for the muxer's output must equal
            // the ones it reports for the *unmodified* fixture. That is the
            // oracle a packet *count* cannot give: a wrong chunk offset or a
            // dropped block shifts bytes without changing how many packets
            // there are (audit item 8, round 3). ffprobe hashes both sides,
            // so the comparison shares no code with the muxer.
            let (source_hashes, source_error) = probe_packet_hashes(&bytes);
            assert!(
                source_error.is_empty(),
                "{label}: ffprobe on the fixture must be silent, got: {source_error}"
            );
            for (stream, got) in &hashes {
                let Some(want) = source_hashes.get(stream) else {
                    continue;
                };
                assert_eq!(
                    got.len(),
                    want.len(),
                    "{label}: stream {stream} hashed packet count"
                );
                assert_eq!(
                    got, want,
                    "{label}: stream {stream} packet payloads differ from the source"
                );
            }
            // A real splice may step the timeline back more than once; the
            // muxer must not turn that into *arbitrary* reordering. (The old
            // assertion allowed exactly one step, which a multi-splice input
            // legitimately exceeds — audit item 8, round 3.)
            let backwards_total: usize = monotonic.values().sum();
            assert!(
                backwards_total <= 4,
                "{label}: {backwards_total} backwards steps is more than the input had"
            );
        }
    }

    /// ffprobe's per-packet `sha256` for a file on disk, keyed by stream.
    ///
    /// Returns `(hashes, stderr)`.
    fn probe_packet_hashes(
        data: &[u8],
    ) -> (
        alloc::collections::BTreeMap<usize, alloc::vec::Vec<alloc::string::String>>,
        alloc::string::String,
    ) {
        let path = std::env::temp_dir().join(format!(
            "transmux-h8-probe-{}-{}.mkv",
            std::process::id(),
            data.as_ptr() as usize
        ));
        std::fs::write(&path, data).expect("write probe input");
        let out = std::process::Command::new("ffprobe")
            .args([
                "-v",
                "error",
                "-show_packets",
                "-show_data_hash",
                "sha256",
                "-show_entries",
                "packet=stream_index,data_hash",
                "-of",
                "csv",
                path.to_str().expect("utf-8 path"),
            ])
            .output()
            .expect("run ffprobe");
        let _ = std::fs::remove_file(&path);
        let mut by_stream: alloc::collections::BTreeMap<usize, alloc::vec::Vec<_>> =
            Default::default();
        for line in String::from_utf8_lossy(&out.stdout)
            .lines()
            .filter(|l| l.starts_with("packet,"))
        {
            let parts: Vec<&str> = line.split(',').collect();
            let stream: usize = parts[1].parse().unwrap_or(usize::MAX);
            if let Some(hash) = parts
                .get(2)
                .filter(|h| h.to_ascii_uppercase().starts_with("SHA256:"))
            {
                by_stream
                    .entry(stream)
                    .or_default()
                    .push(hash.to_ascii_uppercase());
            }
        }
        (by_stream, String::from_utf8_lossy(&out.stderr).into_owned())
    }

    /// A `Cluster` whose block would leave the signed 16-bit relative range
    /// is an *error*, never a silent `clamp`: a clamped block would be written
    /// at an arbitrary instant in release builds (where `debug_assert` does
    /// nothing), which is worse than refusing the input.
    #[test]
    fn cluster_with_an_out_of_range_block_is_rejected() {
        let file = concat!(env!("CARGO_MANIFEST_DIR"), "/../fixtures/mkv/vp9_opus.mkv");
        let Ok(bytes) = std::fs::read(file) else {
            eprintln!("SKIP cluster_with_an_out_of_range_block_is_rejected: fixture missing");
            return;
        };
        let media = crate::webm_demux::WebmDemux::new()
            .demux(&bytes)
            .expect("demux fixture");
        // Two video events 40 s apart in one cluster: `build_cluster` is handed
        // them directly, bypassing `build_clusters`' range guard.
        let events = alloc::vec![
            BlockEvent {
                track_index: 0,
                sample_index: 0,
                pts_ticks: 0,
                track_number: 1,
                is_keyframe: true,
                is_video: true,
            },
            BlockEvent {
                track_index: 0,
                sample_index: 0,
                pts_ticks: 40_000,
                track_number: 1,
                is_keyframe: false,
                is_video: true,
            },
        ];
        let err = build_cluster(&events, &media.tracks)
            .expect_err("40 s relative timestamp cannot fit an i16");
        assert!(
            matches!(err, Error::InvalidInput(_)),
            "expected InvalidInput, got {err:?}"
        );
    }

    /// Several backward steps in one track (a stream spliced more than once)
    /// must still produce a file ffmpeg reads with every packet intact; the
    /// muxer must not turn repeated jumps into arbitrary reordering (audit
    /// item 8, round 3 — the single-step allowance in the sibling test is a
    /// property of *that* input, not a general rule).
    #[test]
    fn multiple_backward_steps_are_ffprobe_readable() {
        if std::process::Command::new("ffprobe")
            .arg("-version")
            .output()
            .is_err()
        {
            eprintln!("SKIP multiple_backward_steps_are_ffprobe_readable: ffprobe not on PATH");
            return;
        }
        let file = concat!(env!("CARGO_MANIFEST_DIR"), "/../fixtures/mkv/vp9_opus.mkv");
        let Ok(bytes) = std::fs::read(file) else {
            eprintln!("SKIP multiple_backward_steps_are_ffprobe_readable: fixture missing");
            return;
        };
        let base = crate::webm_demux::WebmDemux::new()
            .demux(&bytes)
            .expect("demux fixture");
        let mut media = base.clone();
        // Three separate 5 s backward splices in the video track.
        let n = media.tracks[0].samples.len();
        for cut in [n / 4, n / 2, 3 * n / 4] {
            if cut < n {
                for s in &mut media.tracks[0].samples[cut..] {
                    s.dts = s.dts.map(|v| v.saturating_sub(5_000));
                    s.pts = s.pts.map(|v| v.saturating_sub(5_000));
                }
            }
        }
        let out = MkvMux::new().package(&media).expect("package");
        let (hashes, stderr) = probe_packet_hashes(&out);
        assert!(
            stderr.is_empty(),
            "ffprobe -v error must be silent: {stderr}"
        );
        let (source, source_err) = probe_packet_hashes(&bytes);
        assert!(
            source_err.is_empty(),
            "ffprobe on the fixture must be silent: {source_err}"
        );
        for (stream, got) in &hashes {
            if let Some(want) = source.get(stream) {
                assert_eq!(
                    got, want,
                    "stream {stream}: payloads must match the source across several jumps"
                );
            }
        }
    }

    /// `CueTime`s must come out non-decreasing (RFC 9559 §20). A backward
    /// timestamp jump now opens a new `Cluster` (r05-W23), so a later
    /// cluster's keyframe can sit at an *earlier* presentation time than an
    /// earlier one; emitting it would leave the index unsorted and defeat a
    /// player's binary search.
    #[test]
    fn cues_stay_monotonic_across_a_backward_jump() {
        let ev = |pts: i64, key: bool| BlockEvent {
            track_index: 0,
            sample_index: 0,
            pts_ticks: pts,
            track_number: 1,
            is_keyframe: key,
            is_video: true,
        };
        // Forward keyframes at 0/5000, then a jump *back* to 2000.
        let clusters = alloc::vec![
            alloc::vec![ev(0, true)],
            alloc::vec![ev(5_000, true)],
            alloc::vec![ev(2_000, true)],
            alloc::vec![ev(9_000, true)],
        ];
        let offsets: alloc::vec::Vec<u64> = alloc::vec![100, 200, 300, 400];
        let cues = build_cues(&clusters, &offsets);

        // Walk the `Cues` body and read each `CuePoint`'s `CueTime`.
        let id_len = vint_id_len(cues[0]).expect("Cues id");
        let (_, size_len) = read_vint_size(&cues, id_len).expect("Cues size");
        let body = &cues[id_len + size_len..];
        let mut times: alloc::vec::Vec<u64> = alloc::vec::Vec::new();
        let mut c = 0usize;
        while c < body.len() {
            let cid_len = vint_id_len(body[c]).expect("CuePoint id");
            let (size, csize_len) = read_vint_size(body, c + cid_len).expect("CuePoint size");
            let bs = c + cid_len + csize_len;
            if body[c..c + cid_len] == ID_CUE_POINT {
                let inner = &body[bs..bs + size];
                let tid_len = vint_id_len(inner[0]).expect("CueTime id");
                let (tsize, tsize_len) = read_vint_size(inner, tid_len).expect("CueTime size");
                assert_eq!(
                    &inner[..tid_len],
                    ID_CUE_TIME,
                    "a CuePoint must start with its CueTime (RFC 9559 §20)"
                );
                let mut v = 0u64;
                for &b in &inner[tid_len + tsize_len..tid_len + tsize_len + tsize] {
                    v = (v << 8) | u64::from(b);
                }
                times.push(v);
            }
            c = bs + size;
        }
        // Every keyframe keeps a cue; the 2000-ms one is clamped up to the
        // 5000-ms point rather than dropped, so its cluster stays seekable.
        assert_eq!(times, alloc::vec![0, 5_000, 5_000, 9_000], "got {times:?}");
        assert!(
            times.windows(2).all(|w| w[1] >= w[0]),
            "CueTimes must be non-decreasing, got {times:?}"
        );
    }

    #[test]
    fn empty_media_rejected() {
        let media = Media::new(Vec::new(), 1000);
        let mut mux = MkvMux::new();
        assert!(mux.package(&media).is_err());
    }
}