tightbeam-rs 0.9.0

//! Jitter calculation utilities
//!
//! Provides traits and implementations for calculating jitter from observed durations.
//! Used by both timing verification and restart policies.

use crate::utils::math::integer_sqrt;
use crate::TightBeamError;

/// Bounds of the decorrelated-jitter window for a base value.
///
/// Returns `(min, range)` where the window spans `min..=min + range` with
/// `min = base / 3`. Shared by the restart backoff strategy
/// (`transport::policy::DecorrelatedJitter`) and
/// [`DecorrelatedJitterCalculator`] so the algorithm is defined once.
pub const fn decorrelated_bounds(base: u64) -> (u64, u64) {
	let min = base / 3;
	(min, base.saturating_sub(min))
}

/// Trait for calculating jitter from a collection of observed durations.
///
/// Jitter represents the variation in execution times. Different calculation
/// methods provide different statistical measures of this variation.
pub trait JitterCalculator: Send + Sync + core::fmt::Debug {
	/// Calculate jitter from observed durations.
	///
	/// # Arguments
	/// * `durations` - Slice of observed durations in nanoseconds
	///
	/// # Returns
	/// * `Ok(u64)` - Calculated jitter in nanoseconds
	/// * `Err(TightBeamError)` - If calculation fails (e.g., insufficient data)
	///
	/// # Errors
	/// Returns an error if:
	/// * `durations` is empty
	/// * `durations` has fewer than 2 elements (for methods requiring multiple samples)
	fn calculate(&self, durations: &[u64]) -> Result<u64, TightBeamError>;
}

/// Min-Max jitter calculator (default).
///
/// Calculates jitter as the difference between maximum and minimum observed durations.
/// This is the simplest and most commonly used jitter metric.
#[derive(Default, Debug, Clone, Copy)]
pub struct MinMaxJitter;

impl JitterCalculator for MinMaxJitter {
	fn calculate(&self, durations: &[u64]) -> Result<u64, TightBeamError> {
		if durations.is_empty() {
			return Err(TightBeamError::InvalidMetadata);
		}

		if durations.len() < 2 {
			return Ok(0);
		}

		let min = durations.iter().min().copied().unwrap_or(0);
		let max = durations.iter().max().copied().unwrap_or(0);
		Ok(max.saturating_sub(min))
	}
}

/// Variance-based jitter calculator.
///
/// Calculates jitter as the variance of observed durations.
/// Variance measures the spread of data points around the mean.
#[derive(Default, Debug, Clone, Copy)]
pub struct VarianceJitter;

impl JitterCalculator for VarianceJitter {
	fn calculate(&self, durations: &[u64]) -> Result<u64, TightBeamError> {
		if durations.is_empty() {
			return Err(TightBeamError::InvalidMetadata);
		}

		if durations.len() < 2 {
			return Ok(0);
		}

		// Calculate mean
		let sum: u64 = durations.iter().sum();
		let count = durations.len() as u64;
		let mean = sum / count;

		// Calculate variance: sum of squared differences from mean
		let variance_sum: u128 = durations
			.iter()
			.map(|&d| {
				let diff = d.abs_diff(mean);
				(diff as u128).saturating_pow(2)
			})
			.sum();

		// Return variance (average of squared differences)
		let variance = (variance_sum / count as u128) as u64;
		Ok(variance)
	}
}

/// Standard deviation-based jitter calculator.
///
/// Calculates jitter as the standard deviation of observed durations.
/// Standard deviation is the square root of variance, providing a measure
/// in the same units as the original data.
#[derive(Default, Debug, Clone, Copy)]
pub struct StdDevJitter;

impl JitterCalculator for StdDevJitter {
	fn calculate(&self, durations: &[u64]) -> Result<u64, TightBeamError> {
		if durations.is_empty() {
			return Err(TightBeamError::InvalidMetadata);
		}

		if durations.len() < 2 {
			return Ok(0);
		}

		// Calculate mean
		let sum: u64 = durations.iter().sum();
		let count = durations.len() as u64;
		let mean = sum / count;

		// Calculate variance: sum of squared differences from mean
		let variance_sum: u128 = durations
			.iter()
			.map(|&d| {
				let diff = d.abs_diff(mean);
				(diff as u128).saturating_pow(2)
			})
			.sum();

		// Calculate variance (average of squared differences)
		let variance = variance_sum / count as u128;

		// Calculate standard deviation: square root of variance
		// Use integer square root approximation
		let std_dev = integer_sqrt(variance);
		Ok(std_dev as u64)
	}
}

/// Decorrelated jitter calculator.
///
/// Calculates jitter using the decorrelated jitter algorithm.
/// Uses max duration as base and returns the width of the
/// [`decorrelated_bounds`] window (max/3 to max) as the jitter value.
#[derive(Default, Debug, Clone, Copy)]
pub struct DecorrelatedJitterCalculator;

impl JitterCalculator for DecorrelatedJitterCalculator {
	fn calculate(&self, durations: &[u64]) -> Result<u64, TightBeamError> {
		if durations.is_empty() {
			return Err(TightBeamError::InvalidMetadata);
		}

		if durations.len() < 2 {
			return Ok(0);
		}

		let max_duration = durations.iter().max().copied().unwrap_or(0);
		if max_duration == 0 {
			return Ok(0);
		}

		let (_, range) = decorrelated_bounds(max_duration);
		Ok(range)
	}
}

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

	#[test]
	fn test_min_max_jitter() -> Result<(), Box<dyn core::error::Error>> {
		let calculator = MinMaxJitter;
		assert!(matches!(calculator.calculate(&[]), Err(TightBeamError::InvalidMetadata)));
		assert_eq!(calculator.calculate(&[100])?, 0);
		assert_eq!(calculator.calculate(&[100, 200])?, 100);
		assert_eq!(calculator.calculate(&[50, 100, 150, 200])?, 150);

		Ok(())
	}

	#[test]
	fn test_variance_jitter() -> Result<(), Box<dyn core::error::Error>> {
		let calculator = VarianceJitter;
		assert!(matches!(calculator.calculate(&[]), Err(TightBeamError::InvalidMetadata)));
		assert_eq!(calculator.calculate(&[100])?, 0);

		// Test with known values: [100, 200]
		// Mean = 150, variance = ((100-150)² + (200-150)²) / 2 = (2500 + 2500) / 2 = 2500
		let result = calculator.calculate(&[100, 200])?;
		assert_eq!(result, 2500);

		Ok(())
	}

	#[test]
	fn test_std_dev_jitter() -> Result<(), Box<dyn core::error::Error>> {
		let calculator = StdDevJitter;
		assert!(matches!(calculator.calculate(&[]), Err(TightBeamError::InvalidMetadata)));
		assert_eq!(calculator.calculate(&[100])?, 0);

		// Test with known values: [100, 200]
		// Variance = 2500, std_dev = sqrt(2500) = 50
		let result = calculator.calculate(&[100, 200])?;
		assert_eq!(result, 50);

		Ok(())
	}

	#[test]
	fn test_decorrelated_jitter() -> Result<(), Box<dyn core::error::Error>> {
		let calculator = DecorrelatedJitterCalculator;
		assert!(matches!(calculator.calculate(&[]), Err(TightBeamError::InvalidMetadata)));
		assert_eq!(calculator.calculate(&[100])?, 0);

		// Test with max = 300: range = 300 - (300/3) = 300 - 100 = 200
		assert_eq!(calculator.calculate(&[100, 200, 300])?, 200);

		// Test with max = 150: range = 150 - (150/3) = 150 - 50 = 100
		assert_eq!(calculator.calculate(&[50, 100, 150])?, 100);

		Ok(())
	}
}