moq-video 0.0.24

//! Native V4L2 webcam capture (Linux), replacing nokhwa.
//!
//! Streams MMAP buffers through the [`v4l`] crate and converts each frame to CPU
//! [`I420`] for the encoder. Two source formats cover essentially all UVC
//! webcams: YUYV (raw 4:2:2, resampled directly) and MJPEG (decoded to RGB with
//! the pure-Rust [`zune_jpeg`], then converted). This is the CPU path feeding
//! NVENC / VAAPI / openh264; there's no GPU surface here.

use std::collections::{BTreeMap, BTreeSet};

use v4l::buffer::Type as BufType;
use v4l::capability::Flags;
use v4l::frameinterval::FrameIntervalEnum;
use v4l::framesize::FrameSizeEnum;
use v4l::io::mmap::Stream as MmapStream;
use v4l::io::traits::CaptureStream;
use v4l::video::Capture;
use v4l::video::capture::Parameters;
use v4l::{Device, Format, FourCC};
use zune_jpeg::zune_core::bytestream::ZCursor;

use super::channel::FrameChannel;
use super::pump::{self, Geometry};
use super::{Config, Mode, Rate, Stream};
use crate::frame::{I420, Surface};
use crate::{Error, Size};

/// List V4L2 capture nodes using paths that [`open_device`] accepts.
pub(super) fn cameras() -> Result<Vec<super::Camera>, Error> {
	let mut nodes = v4l::context::enum_devices();
	nodes.sort_by_key(v4l::context::Node::index);

	let cameras = nodes
		.into_iter()
		.filter_map(|node| {
			let path = node.path().to_string_lossy().into_owned();
			let device = match Device::with_path(node.path()) {
				Ok(device) => device,
				Err(err) => {
					tracing::debug!(device = %path, error = %err, "could not inspect V4L2 node");
					return None;
				}
			};
			let capabilities = match device.query_caps() {
				Ok(capabilities) => capabilities,
				Err(err) => {
					tracing::debug!(device = %path, error = %err, "could not query V4L2 node");
					return None;
				}
			};
			if !capabilities.capabilities.contains(Flags::VIDEO_CAPTURE)
				|| !capabilities.capabilities.contains(Flags::STREAMING)
			{
				return None;
			}

			let name = node.name().filter(|name| !name.is_empty()).unwrap_or(capabilities.card);
			Some(super::Camera { id: path, name })
		})
		.collect();
	Ok(cameras)
}

/// List the modes a V4L2 camera reports, for the formats this backend converts.
///
/// `VIDIOC_ENUM_FRAMESIZES` and `VIDIOC_ENUM_FRAMEINTERVALS` describe a device
/// without configuring it, which is what makes this answerable before the camera
/// opens. `VIDIOC_S_FMT` cannot: it asks and applies in one step, which is why
/// [`negotiate`] has to probe.
///
/// Only YUYV and MJPEG are enumerated, so what comes back is what [`open`] could
/// negotiate rather than everything the driver advertises. Sizes reported for
/// both formats are merged, and their rates with them: the encoder sees I420
/// either way, so which format carried a mode is not something a caller can act
/// on.
pub(super) fn modes(selector: Option<&str>) -> Result<Vec<Mode>, Error> {
	let (device, _) = open_device(selector)?;
	let mut sizes: BTreeMap<(u32, u32), BTreeSet<Rate>> = BTreeMap::new();

	for candidate in Source::ALL {
		let fourcc = candidate.fourcc();
		let enumerated = frame_sizes(&device, fourcc)?;
		for size in enumerated {
			for (width, height) in reported_sizes(size) {
				sizes.entry((width, height)).or_default().extend(framerates(
					&device,
					fourcc,
					Size::new(width, height),
				)?);
			}
		}
	}

	let mut modes: Vec<Mode> = sizes
		.into_iter()
		.map(|((width, height), framerates)| Mode {
			width,
			height,
			// Highest first, so the rate a caller most often wants is the one it
			// reads without scanning.
			framerates: framerates.into_iter().rev().collect(),
		})
		.collect();
	modes.sort_by_key(|mode| std::cmp::Reverse(u64::from(mode.width) * u64::from(mode.height)));
	Ok(modes)
}

/// The sizes worth reporting from one `VIDIOC_ENUM_FRAMESIZES` entry.
///
/// A discrete entry is one size. A stepwise or continuous entry describes a
/// whole rectangle of them, which on a driver with a one-pixel step is millions,
/// so only its smallest and largest I420-compatible sizes are reported.
fn reported_sizes(size: FrameSizeEnum) -> Vec<(u32, u32)> {
	let sizes = match size {
		FrameSizeEnum::Discrete(discrete) => vec![(discrete.width, discrete.height)],
		FrameSizeEnum::Stepwise(stepwise) => {
			let Some((min_width, max_width)) = bounds(stepwise.min_width, stepwise.max_width, stepwise.step_width)
			else {
				return Vec::new();
			};
			let Some((min_height, max_height)) = bounds(stepwise.min_height, stepwise.max_height, stepwise.step_height)
			else {
				return Vec::new();
			};
			let smallest = (min_width, min_height);
			let largest = (max_width, max_height);
			if smallest == largest {
				vec![smallest]
			} else {
				vec![smallest, largest]
			}
		}
	};
	sizes
		.into_iter()
		.filter(|&(width, height)| Size::new(width, height).validate("camera resolution").is_ok())
		.collect()
}

/// First and last nonzero even values on the driver's step grid.
fn bounds(min: u32, max: u32, step: u32) -> Option<(u32, u32)> {
	if min == max {
		return (min != 0 && min.is_multiple_of(2)).then_some((min, min));
	}
	if min > max || step == 0 {
		return None;
	}
	let mut first = if min == 0 { step } else { min };
	let mut last = min + (max - min) / step * step;
	if !first.is_multiple_of(2) {
		if step.is_multiple_of(2) {
			return None;
		}
		first = first.checked_add(step)?;
	}
	if !last.is_multiple_of(2) {
		last = last.checked_sub(step)?;
	}
	(first <= last).then_some((first, last))
}

// Read one entry at a time: v4l's collection helpers treat every error after
// the first entry as end-of-list, hiding device failures and malformed replies.
fn frame_sizes(device: &Device, fourcc: FourCC) -> Result<Vec<FrameSizeEnum>, Error> {
	let mut sizes = Vec::new();
	for index in 0..=u32::MAX {
		// All fields are integers or integer unions; reserved fields must be zero.
		let mut entry: v4l::v4l_sys::v4l2_frmsizeenum = unsafe { std::mem::zeroed() };
		entry.index = index;
		entry.pixel_format = fourcc.into();
		// The request matches the initialized argument's type and size.
		let result = unsafe {
			v4l::v4l2::ioctl(
				device.handle().fd(),
				v4l::v4l2::vidioc::VIDIOC_ENUM_FRAMESIZES,
				&mut entry as *mut _ as *mut std::ffi::c_void,
			)
		};
		if enumeration(result)?.is_none() {
			return Ok(sizes);
		}
		sizes.push(FrameSizeEnum::try_from(entry).map_err(|e| Error::Codec(anyhow::anyhow!(e)))?);
	}
	Err(Error::Codec(anyhow::anyhow!("V4L2 frame size index overflow")))
}

fn enumeration<T>(result: std::io::Result<T>) -> Result<Option<T>, Error> {
	match result {
		Ok(value) => Ok(Some(value)),
		Err(error) if error.raw_os_error() == Some(libc::EINVAL) => Ok(None),
		Err(error) => Err(Error::SourceUnavailable(format!("V4L2 enumeration: {error}"))),
	}
}

/// Exact discrete rates; continuous and stepwise intervals have no finite list.
fn framerates(device: &Device, fourcc: FourCC, size: Size) -> Result<Vec<Rate>, Error> {
	let mut rates = Vec::new();
	for index in 0..=u32::MAX {
		// All fields are integers or integer unions; reserved fields must be zero.
		let mut entry: v4l::v4l_sys::v4l2_frmivalenum = unsafe { std::mem::zeroed() };
		entry.index = index;
		entry.pixel_format = fourcc.into();
		entry.width = size.width;
		entry.height = size.height;
		// The request matches the initialized argument's type and size.
		let result = unsafe {
			v4l::v4l2::ioctl(
				device.handle().fd(),
				v4l::v4l2::vidioc::VIDIOC_ENUM_FRAMEINTERVALS,
				&mut entry as *mut _ as *mut std::ffi::c_void,
			)
		};
		if enumeration(result)?.is_none() {
			return Ok(rates);
		}
		let interval = FrameIntervalEnum::try_from(entry).map_err(|e| Error::Codec(anyhow::anyhow!(e)))?;
		if let FrameIntervalEnum::Discrete(interval) = interval {
			rates.push(rate(interval)?);
		}
	}
	Err(Error::Codec(anyhow::anyhow!("V4L2 frame interval index overflow")))
}

fn rate(interval: v4l::Fraction) -> Result<Rate, Error> {
	let frames = std::num::NonZeroU32::new(interval.denominator);
	let seconds = std::num::NonZeroU32::new(interval.numerator);
	match (frames, seconds) {
		(Some(frames), Some(seconds)) => Ok(Rate { frames, seconds }),
		_ => Err(Error::Codec(anyhow::anyhow!(
			"V4L2 reported a zero frame interval component"
		))),
	}
}

/// Open a V4L2 camera and stream its frames over a pump thread.
pub(super) async fn open(config: &Config, device: Option<&str>) -> Result<Stream, Error> {
	let config = config.clone();
	// The camera opens on the pump thread, so the selector has to be owned.
	let device = device.map(str::to_string);
	let chan = FrameChannel::new();
	let (geo, guard) = pump::spawn(
		chan.clone(),
		move || {
			let camera = Camera::open(&config, device.as_deref())?;
			let geometry = Geometry {
				width: camera.width,
				height: camera.height,
				framerate: camera.framerate,
				label: camera.name.clone(),
			};
			Ok((camera, geometry))
		},
		Camera::read,
	)
	.await?;

	Ok(Stream::new(
		chan,
		geo.width,
		geo.height,
		geo.framerate,
		geo.label,
		None,
		Box::new(guard),
	))
}

/// Fallback geometry when the caller doesn't pin a resolution; the driver picks
/// the nearest mode it supports.
const DEFAULT_WIDTH: u32 = 1280;
const DEFAULT_HEIGHT: u32 = 720;

/// Driver buffers to keep in flight; a small ring lets capture overlap encode.
const BUFFER_COUNT: u32 = 4;

/// The negotiated source format, chosen once at open.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Source {
	/// Raw 4:2:2; resampled to I420 with no color-space conversion.
	Yuyv,
	/// Motion-JPEG; decoded per frame.
	Mjpeg,
}

impl Source {
	/// Every format we can convert, cheapest first. The order only breaks ties
	/// between modes that fit the requested size and rate equally well.
	const ALL: [Self; 2] = [Self::Yuyv, Self::Mjpeg];

	fn fourcc(self) -> FourCC {
		FourCC::new(match self {
			Self::Yuyv => b"YUYV",
			Self::Mjpeg => b"MJPG",
		})
	}

	fn from_fourcc(fourcc: FourCC) -> Option<Self> {
		Self::ALL.into_iter().find(|source| source.fourcc() == fourcc)
	}

	fn cost(self) -> u8 {
		match self {
			Self::Yuyv => 0,
			Self::Mjpeg => 1,
		}
	}
}

pub(crate) struct Camera {
	stream: MmapStream<'static>,
	source: Source,
	width: u32,
	height: u32,
	/// Bytes per row of the YUYV buffer (`bytesperline`); unused for MJPEG.
	stride: u32,
	framerate: Option<u32>,
	name: String,
}

impl Camera {
	fn open(config: &Config, selector: Option<&str>) -> Result<Self, Error> {
		let (device, name) = open_device(selector)?;
		let width = config.width.unwrap_or(DEFAULT_WIDTH);
		let height = config.height.unwrap_or(DEFAULT_HEIGHT);

		let (format, source, rate) = negotiate(
			&device,
			&name,
			Request {
				size: Size::new(width, height),
				framerate: config.framerate,
			},
		)?;

		let (width, height, stride) = (format.width, format.height, format.stride);
		Size::new(width, height).validate("camera resolution")?;

		let framerate = rate.map(|rate| rate.rounded());

		// The stream owns a clone of the device's `Arc<Handle>`, so the fd stays
		// open after `device` drops here; the mmap'd buffers live with the stream.
		let stream = MmapStream::with_buffers(&device, BufType::VideoCapture, BUFFER_COUNT)
			.map_err(|e| Error::Codec(anyhow::anyhow!("V4L2 stream init: {e}")))?;

		tracing::info!(device = %name, width, height, "opened V4L2 capture");
		Ok(Self {
			stream,
			source,
			width,
			height,
			stride,
			framerate,
			name,
		})
	}

	/// Pull the next frame. Blocks one frame interval; the pump thread calls this
	/// in a loop and checks its stop flag between calls.
	fn read(&mut self) -> Result<pump::Read, Error> {
		let (buf, meta) = CaptureStream::next(&mut self.stream)
			.map_err(|error| Error::SourceUnavailable(format!("V4L2 camera {}: {error}", self.name)))?;

		let i420 = match self.source {
			Source::Yuyv => I420::from_yuyv(buf, self.stride, self.width, self.height)?,
			Source::Mjpeg => {
				// Only `bytesused` of the buffer holds the JPEG; the rest is stale.
				let jpeg = buf.get(..meta.bytesused as usize).unwrap_or(buf);
				// zune-jpeg 0.5 reads through a seekable cursor, not a bare slice.
				let mut decoder = zune_jpeg::JpegDecoder::new(ZCursor::new(jpeg));
				let rgb = decoder
					.decode()
					.map_err(|e| Error::Codec(anyhow::anyhow!("MJPEG decode: {e:?}")))?;
				let (w, h) = decoder
					.dimensions()
					.ok_or_else(|| Error::Codec(anyhow::anyhow!("MJPEG frame had no dimensions")))?;
				// The stream reports the negotiated size and the encoder is built
				// from it, so a frame that decodes to another one can't be published
				// as this stream's.
				if w as u32 != self.width || h as u32 != self.height {
					return Err(Error::Codec(anyhow::anyhow!(
						"MJPEG frame is {w}x{h}, not the negotiated {}x{}",
						self.width,
						self.height
					)));
				}
				I420::from_rgb(&rgb, self.width, self.height)?
			}
		};
		Ok(pump::Read::Frame(Surface::I420(i420)))
	}
}

/// Open `device`: a bare integer selects `/dev/videoN` by index, anything
/// else is a device path. `None` opens index 0.
fn open_device(device: Option<&str>) -> Result<(Device, String), Error> {
	match device {
		None => {
			let device = Device::new(0).map_err(|error| open_error("/dev/video0", error))?;
			Ok((device, "/dev/video0".to_string()))
		}
		Some(spec) => match spec.parse::<usize>() {
			Ok(index) => {
				let name = format!("/dev/video{index}");
				let device = Device::new(index).map_err(|error| open_error(&name, error))?;
				Ok((device, format!("/dev/video{index}")))
			}
			Err(_) => {
				let device = Device::with_path(spec).map_err(|error| open_error(spec, error))?;
				Ok((device, spec.to_string()))
			}
		},
	}
}

fn open_error(device: &str, error: std::io::Error) -> Error {
	match error.kind() {
		std::io::ErrorKind::PermissionDenied => Error::PermissionDenied(format!("{device}: {error}")),
		_ => Error::SourceUnavailable(format!("{device}: {error}")),
	}
}

struct Request {
	size: Size,
	framerate: Option<u32>,
}

/// Negotiate the format we can convert to I420 that lands closest to `want`.
///
/// V4L2's non-mutating `VIDIOC_TRY_FMT` is optional, so use the required
/// `VIDIOC_S_FMT`. It asks and applies in one step, substituting the driver's
/// nearest supported mode for anything it doesn't have. Each format we handle
/// is applied in turn and scored against the requested geometry and frame rate, then the
/// winner is applied again to leave the device on it.
///
/// Taking the first reply instead would pin most laptop webcams to VGA: USB
/// bandwidth doesn't fit uncompressed 4:2:2 above that, so they offer YUYV only
/// at small sizes and reach HD through MJPEG alone. Asking such a camera for
/// YUYV at 1080p gets 640x480 back, which is a valid YUYV mode and nowhere near
/// what the caller asked for.
fn negotiate(device: &Device, name: &str, want: Request) -> Result<(Format, Source, Option<Rate>), Error> {
	let framerate = want.framerate;
	negotiate_with(name, want, |format| {
		let format = set_format(device, format)?;
		if let Some(fps) = framerate {
			match Capture::set_params(device, &Parameters::with_fps(fps)) {
				Ok(_) => {}
				Err(error) if matches!(error.raw_os_error(), Some(libc::EINVAL | libc::ENOTTY)) => {}
				Err(error) => return Err(open_error(name, error)),
			}
		}
		let rate = match Capture::params(device) {
			Ok(params) if params.interval.numerator != 0 && params.interval.denominator != 0 => {
				Some(rate(params.interval)?)
			}
			Ok(_) => None,
			Err(error) if matches!(error.raw_os_error(), Some(libc::EINVAL | libc::ENOTTY)) => None,
			Err(error) => return Err(open_error(name, error)),
		};
		Ok((format, rate))
	})
}

fn negotiate_with(
	name: &str,
	want: Request,
	mut apply: impl FnMut(Format) -> Result<(Format, Option<Rate>), Error>,
) -> Result<(Format, Source, Option<Rate>), Error> {
	let mut replies = Vec::with_capacity(Source::ALL.len());
	let mut offered = Vec::new();
	let mut probe_error = None;
	for candidate in Source::ALL {
		let (got, rate) = match apply(Format::new(want.size.width, want.size.height, candidate.fourcc())) {
			Ok(got) => got,
			Err(error) => {
				probe_error = Some(error);
				continue;
			}
		};
		let description = format!("{}x{} {}", got.width, got.height, got.fourcc);
		if !offered.contains(&description) {
			offered.push(description);
		}
		if let Some(source) = Source::from_fourcc(got.fourcc) {
			replies.push((got, source, rate));
		}
	}

	let Some((best, source, _)) = closest(replies, want) else {
		if offered.is_empty() {
			let Some(error) = probe_error else {
				return Err(Error::Codec(anyhow::anyhow!("camera {name} has no formats to probe")));
			};
			return Err(error);
		}
		let offered = offered.join(", ");
		let wanted = Source::ALL.map(|source| source.fourcc().to_string()).join(", ");
		return Err(Error::Codec(anyhow::anyhow!(
			"camera {name} has no encodable {wanted} mode (the driver returned {offered})"
		)));
	};

	// A successful probe may have left the device on another candidate.
	let (applied, rate) = apply(Format::new(best.width, best.height, best.fourcc))?;
	if applied.fourcc != best.fourcc || applied.width != best.width || applied.height != best.height {
		return Err(Error::Codec(anyhow::anyhow!(
			"camera {name} would not re-apply the {}x{} {} mode it just negotiated",
			best.width,
			best.height,
			best.fourcc
		)));
	}
	Ok((applied, source, rate))
}

/// Prefer geometry, then the accepted rate nearest the request, then conversion cost.
fn closest(
	replies: impl IntoIterator<Item = (Format, Source, Option<Rate>)>,
	want: Request,
) -> Option<(Format, Source, Option<Rate>)> {
	replies
		.into_iter()
		.filter(|(format, _, _)| {
			Size::new(format.width, format.height)
				.validate("camera resolution")
				.is_ok()
		})
		.min_by(|(left, left_source, left_rate), (right, right_source, right_rate)| {
			distance(*left, want.size)
				.cmp(&distance(*right, want.size))
				.then_with(|| rate_distance(*left_rate, *right_rate, want.framerate))
				.then_with(|| left_source.cost().cmp(&right_source.cost()))
		})
}

fn rate_distance(left: Option<Rate>, right: Option<Rate>, want: Option<u32>) -> std::cmp::Ordering {
	let Some(want) = want else {
		return std::cmp::Ordering::Equal;
	};
	match (left, right) {
		(Some(left), Some(right)) => {
			let delta =
				|rate: Rate| u64::from(rate.frames.get()).abs_diff(u64::from(want) * u64::from(rate.seconds.get()));
			(u128::from(delta(left)) * u128::from(right.seconds.get()))
				.cmp(&(u128::from(delta(right)) * u128::from(left.seconds.get())))
		}
		(Some(_), None) => std::cmp::Ordering::Less,
		(None, Some(_)) => std::cmp::Ordering::Greater,
		(None, None) => std::cmp::Ordering::Equal,
	}
}

/// How far a negotiated mode lands from the requested geometry, summed over both
/// dimensions. Zero is an exact match.
fn distance(format: Format, want: Size) -> u64 {
	u64::from(format.width.abs_diff(want.width)) + u64::from(format.height.abs_diff(want.height))
}

fn set_format(device: &Device, format: Format) -> Result<Format, Error> {
	Capture::set_format(device, &format).map_err(|e| Error::Codec(anyhow::anyhow!("V4L2 set format: {e}")))
}

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

	use v4l::framesize::{Discrete, Stepwise};

	fn request(width: u32, height: u32) -> Request {
		Request {
			size: Size::new(width, height),
			framerate: None,
		}
	}

	fn reply(width: u32, height: u32, source: Source) -> (Format, Source, Option<Rate>) {
		(Format::new(width, height, source.fourcc()), source, None)
	}

	fn stepwise(min: (u32, u32), max: (u32, u32), step: u32) -> FrameSizeEnum {
		FrameSizeEnum::Stepwise(Stepwise {
			min_width: min.0,
			max_width: max.0,
			step_width: step,
			min_height: min.1,
			max_height: max.1,
			step_height: step,
		})
	}

	/// A discrete entry is the one mode it names.
	#[test]
	fn a_discrete_frame_size_is_reported_as_itself() {
		let size = FrameSizeEnum::Discrete(Discrete {
			width: 1280,
			height: 720,
		});
		assert_eq!(reported_sizes(size), vec![(1280, 720)]);
	}

	#[test]
	fn unencodable_frame_sizes_are_not_reported() {
		for (width, height) in [(0, 480), (640, 0), (641, 480), (640, 481)] {
			assert!(reported_sizes(FrameSizeEnum::Discrete(Discrete { width, height })).is_empty());
		}
	}

	#[test]
	fn rates_preserve_fractional_and_sub_one_fps_intervals() {
		let ntsc = rate(v4l::Fraction::new(1001, 30000)).unwrap();
		assert_eq!(ntsc.frames().get(), 30000);
		assert_eq!(ntsc.rounded(), 30);
		assert_eq!(ntsc.interval(), std::time::Duration::from_secs(1001));
		let slow = rate(v4l::Fraction::new(2, 1)).unwrap();
		assert_eq!(slow.frames().get(), 1);
		assert_eq!(slow.rounded(), 1);
		assert_eq!(rate(v4l::Fraction::new(1, u32::MAX)).unwrap().rounded(), u32::MAX);
		assert_eq!(slow.interval(), std::time::Duration::from_secs(2));
		assert!(slow < ntsc);
		assert!(rate(v4l::Fraction::new(0, 30)).is_err());
		assert!(rate(v4l::Fraction::new(1, 0)).is_err());
	}

	#[test]
	fn equivalent_rates_deduplicate_and_sort_numerically() {
		let rates: BTreeSet<_> = [(1001, 30000), (1, 30), (2, 60), (2, 1)]
			.into_iter()
			.map(|(n, d)| rate(v4l::Fraction::new(n, d)).unwrap())
			.collect();
		assert_eq!(rates.len(), 3);
		assert_eq!(*rates.last().unwrap(), rate(v4l::Fraction::new(1, 30)).unwrap());
		assert_eq!(*rates.first().unwrap(), rate(v4l::Fraction::new(2, 1)).unwrap());
	}

	#[test]
	fn enumeration_only_stops_on_einval() {
		assert_eq!(enumeration(Ok(42)).unwrap(), Some(42));
		assert!(
			enumeration::<()>(Err(std::io::Error::from_raw_os_error(libc::EINVAL)))
				.unwrap()
				.is_none()
		);
		for code in [libc::EIO, libc::ENODEV, libc::EACCES] {
			assert!(enumeration::<()>(Err(std::io::Error::from_raw_os_error(code))).is_err());
		}
	}

	#[test]
	fn negotiation_selects_and_reapplies_the_format_accepting_the_requested_rate() {
		let mut formats = Vec::new();
		let want = Request {
			size: Size::new(1280, 720),
			framerate: Some(60),
		};
		let (_, source, accepted) = negotiate_with("camera", want, |format| {
			formats.push(format.fourcc);
			let fps = if format.fourcc == Source::Yuyv.fourcc() { 30 } else { 60 };
			Ok((format, Some(rate(v4l::Fraction::new(1, fps)).unwrap())))
		})
		.unwrap();
		assert_eq!(source, Source::Mjpeg);
		assert_eq!(accepted.unwrap().rounded(), 60);
		assert_eq!(
			formats,
			[Source::Yuyv.fourcc(), Source::Mjpeg.fourcc(), Source::Mjpeg.fourcc()]
		);
	}

	#[test]
	fn rate_scoring_preserves_fractional_precision_and_handles_unknown_rates() {
		let ntsc = Some(rate(v4l::Fraction::new(1001, 60000)).unwrap());
		let thirty = Some(rate(v4l::Fraction::new(1, 30)).unwrap());
		assert!(rate_distance(ntsc, thirty, Some(60)).is_lt());
		assert!(rate_distance(thirty, ntsc, Some(30)).is_lt());
		assert!(rate_distance(ntsc, None, Some(60)).is_lt());
		assert!(rate_distance(ntsc, thirty, None).is_eq());
		let tiny = Some(rate(v4l::Fraction::new(u32::MAX, 1)).unwrap());
		let huge = Some(rate(v4l::Fraction::new(1, u32::MAX)).unwrap());
		assert!(rate_distance(tiny, huge, Some(u32::MAX)).is_gt());
	}

	/// A one-pixel step over a 4K range is 8 million modes, and reporting them
	/// would say nothing the two corners do not.
	#[test]
	fn a_stepwise_frame_size_is_reported_as_its_corners() {
		let size = stepwise((32, 32), (3840, 2160), 1);
		assert_eq!(reported_sizes(size), vec![(32, 32), (3840, 2160)]);
	}

	/// A range whose corners coincide is one mode, not the same one twice.
	#[test]
	fn a_stepwise_frame_size_of_one_mode_is_reported_once() {
		let size = stepwise((640, 480), (640, 480), 1);
		assert_eq!(reported_sizes(size), vec![(640, 480)]);
	}

	#[test]
	fn stepwise_sizes_keep_even_interior_endpoints() {
		assert_eq!(
			reported_sizes(stepwise((1, 1), (1919, 1079), 1)),
			vec![(2, 2), (1918, 1078)]
		);
		assert_eq!(reported_sizes(stepwise((1, 1), (20, 20), 3)), vec![(4, 4), (16, 16)]);
		assert_eq!(reported_sizes(stepwise((0, 0), (3, 3), 1)), vec![(2, 2)]);
		assert!(reported_sizes(stepwise((1, 1), (19, 19), 2)).is_empty());
	}

	#[test]
	fn stepwise_bounds_match_the_enumerated_grid() {
		for min in 0..8 {
			for max in min..16 {
				for step in 1..8 {
					let values: Vec<_> = (min..=max)
						.step_by(step as usize)
						.filter(|value| *value != 0 && value % 2 == 0)
						.collect();
					let expected = values.first().zip(values.last()).map(|(&first, &last)| (first, last));
					assert_eq!(bounds(min, max, step), expected, "{min}..={max}, step {step}");
				}
			}
		}
		assert_eq!(bounds(u32::MAX - 4, u32::MAX, 3), Some((u32::MAX - 1, u32::MAX - 1)));
		assert_eq!(bounds(0, u32::MAX, u32::MAX), None);
		assert_eq!(bounds(2, 2, 0), Some((2, 2)));
		assert_eq!(bounds(2, 4, 0), None);
		assert_eq!(bounds(4, 2, 1), None);
	}

	/// The case that motivates scoring at all, taken from a real UVC webcam:
	/// YUYV tops out at VGA while MJPEG reaches 720p, so a 720p request has to
	/// land on MJPEG even though YUYV is probed first and answers successfully.
	#[test]
	fn prefers_the_nearer_mode_over_the_cheaper_one() {
		let replies = [reply(640, 480, Source::Yuyv), reply(1280, 720, Source::Mjpeg)];
		let (format, source, _) = closest(replies, request(1280, 720)).expect("a reply is usable");
		assert_eq!(source, Source::Mjpeg);
		assert_eq!((format.width, format.height), (1280, 720));
	}

	/// When both formats reach the requested size, the cheaper one wins regardless
	/// of probe order: YUYV resamples, MJPEG costs a full JPEG decode per frame.
	#[test]
	fn breaks_ties_toward_the_cheaper_format() {
		let replies = [reply(640, 480, Source::Mjpeg), reply(640, 480, Source::Yuyv)];
		let (_, source, _) = closest(replies, request(640, 480)).expect("a reply is usable");
		assert_eq!(source, Source::Yuyv);
	}

	/// An exact odd mode cannot feed I420, so a nearby even mode has to win rather
	/// than letting `Camera::open` reject the selected result.
	#[test]
	fn ignores_a_nearer_mode_the_pipeline_cannot_encode() {
		let replies = [reply(1279, 719, Source::Mjpeg), reply(1280, 720, Source::Yuyv)];
		let (format, source, _) = closest(replies, request(1279, 719)).expect("an even reply is usable");
		assert_eq!(source, Source::Yuyv);
		assert_eq!((format.width, format.height), (1280, 720));
	}

	/// A YUYV-only driver may reject MJPEG instead of substituting its supported
	/// mode, which must not discard the valid reply from the first probe.
	#[test]
	fn keeps_a_valid_mode_when_another_probe_fails() {
		let mut calls = 0;
		let (format, source, _) = negotiate_with("camera", request(640, 480), |requested| {
			calls += 1;
			match calls {
				1 => Ok((Format::new(640, 480, Source::Yuyv.fourcc()), None)),
				2 => Err(Error::Codec(anyhow::anyhow!("MJPEG is unsupported"))),
				3 => Ok((requested, None)),
				_ => panic!("unexpected format probe"),
			}
		})
		.expect("the YUYV reply is usable");

		assert_eq!(calls, 3);
		assert_eq!(source, Source::Yuyv);
		assert_eq!((format.width, format.height), (640, 480));
	}

	/// When every candidate is rejected, preserve the last real driver error.
	#[test]
	fn returns_an_error_when_every_probe_fails() {
		let mut calls = 0;
		let error = negotiate_with("camera", request(640, 480), |_| {
			calls += 1;
			Err(Error::Codec(anyhow::anyhow!("probe {calls} failed")))
		})
		.expect_err("no format probe succeeded");

		assert_eq!(calls, Source::ALL.len());
		assert_eq!(error.to_string(), "probe 2 failed");
	}

	/// Zero and odd dimensions cannot feed I420, so they leave nothing to score.
	#[test]
	fn no_usable_reply_is_none() {
		let replies = [reply(0, 720, Source::Yuyv), reply(1279, 719, Source::Mjpeg)];
		assert!(closest(replies, request(1280, 720)).is_none());
	}

	/// Distance is symmetric in the two dimensions and zero only on an exact hit,
	/// so a mode that overshoots is no better than one that undershoots by as much.
	#[test]
	fn distance_is_zero_only_on_an_exact_match() {
		let want = Size::new(1280, 720);
		assert_eq!(distance(Format::new(1280, 720, Source::Yuyv.fourcc()), want), 0);
		assert_eq!(distance(Format::new(1280, 600, Source::Yuyv.fourcc()), want), 120);
		assert_eq!(distance(Format::new(1280, 840, Source::Yuyv.fourcc()), want), 120);
	}

	/// Every format we advertise round-trips through its fourcc, which is what
	/// lets `negotiate` recognize the driver's substitution.
	#[test]
	fn fourcc_round_trips() {
		for source in Source::ALL {
			assert_eq!(Source::from_fourcc(source.fourcc()), Some(source));
		}
		assert_eq!(Source::from_fourcc(FourCC::new(b"GREY")), None);
	}
}