#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PieceSelectionStrategy {
Sequential,
RarestFirst,
Random,
LongestSequence,
Priority,
Geometric,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PiecePriorityMode {
SequentialHead,
SequentialTail,
RarestFirst,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PiecePickStrategy {
Sequential,
RarestFirst,
Random,
LongestSequence,
Priority,
Geometric,
}
#[derive(Debug, Clone)]
pub struct PieceInfo {
pub index: u32,
pub frequency: u32,
pub is_completed: bool,
pub completed: bool,
pub in_progress: bool,
pub priority: u8,
}
pub const DEFAULT_ENDGAME_THRESHOLD: usize = 20;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ScanOrder {
Forward,
Backward,
Rarest,
Random,
LongestRun,
Priority,
Geometric,
}
pub struct PiecePicker {
num_pieces: u32,
strategy: PieceSelectionStrategy,
priority_mode: PiecePriorityMode,
frequencies: Vec<u32>,
completed: Vec<bool>,
in_progress: Vec<bool>,
priorities: Vec<u8>,
endgame_candidates: Vec<usize>,
completed_count: usize,
head_cursor: usize,
tail_cursor: usize,
endgame_threshold: usize,
rng_state: u64,
}
impl PiecePicker {
pub fn new(num_pieces: u32) -> Self {
let n = num_pieces as usize;
Self {
num_pieces,
strategy: PieceSelectionStrategy::RarestFirst,
priority_mode: PiecePriorityMode::RarestFirst,
frequencies: vec![0; n],
completed: vec![false; n],
in_progress: vec![false; n],
priorities: vec![0; n],
endgame_candidates: Vec::new(),
completed_count: 0,
head_cursor: 0,
tail_cursor: n,
endgame_threshold: DEFAULT_ENDGAME_THRESHOLD,
rng_state: Self::seed(),
}
}
fn seed() -> u64 {
use std::hash::{BuildHasher, Hasher};
let s = std::collections::hash_map::RandomState::new()
.build_hasher()
.finish();
s | 1
}
fn next_rand(&mut self) -> u64 {
let mut x = self.rng_state;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.rng_state = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
pub fn set_strategy(&mut self, strategy: PieceSelectionStrategy) {
self.strategy = strategy;
}
pub fn set_priority_mode(&mut self, mode: PiecePriorityMode) {
self.priority_mode = mode;
}
pub fn set_endgame_threshold(&mut self, threshold: usize) {
self.endgame_threshold = threshold;
self.refresh_endgame_candidates();
}
pub fn set_priority(&mut self, index: u32, priority: u8) {
let i = index as usize;
if i < self.num_pieces as usize {
self.priorities[i] = priority;
}
}
fn scan_order(&self) -> ScanOrder {
match self.priority_mode {
PiecePriorityMode::SequentialHead => ScanOrder::Forward,
PiecePriorityMode::SequentialTail => ScanOrder::Backward,
PiecePriorityMode::RarestFirst => match self.strategy {
PieceSelectionStrategy::Sequential => ScanOrder::Forward,
PieceSelectionStrategy::RarestFirst => ScanOrder::Rarest,
PieceSelectionStrategy::Random => ScanOrder::Random,
PieceSelectionStrategy::LongestSequence => ScanOrder::LongestRun,
PieceSelectionStrategy::Priority => ScanOrder::Priority,
PieceSelectionStrategy::Geometric => ScanOrder::Geometric,
},
}
}
#[inline]
fn is_available(&self, i: usize) -> bool {
!self.completed[i] && !self.in_progress[i]
}
#[inline]
fn peer_has(bitfield: Option<&[u8]>, i: usize) -> bool {
match bitfield {
None => true,
Some(bf) => {
let byte = i / 8;
let bit = 7 - (i % 8);
byte < bf.len() && (bf[byte] & (1 << bit)) != 0
}
}
}
fn advance_head(&mut self) {
let n = self.num_pieces as usize;
while self.head_cursor < n {
let i = self.head_cursor;
if self.is_available(i) {
break;
}
self.head_cursor = i + 1;
}
}
fn advance_tail(&mut self) {
while self.tail_cursor > 0 {
let i = self.tail_cursor - 1;
if self.is_available(i) {
break;
}
self.tail_cursor = i;
}
}
fn reopen(&mut self, i: usize) {
if i < self.head_cursor {
self.head_cursor = i;
}
if i + 1 > self.tail_cursor {
self.tail_cursor = i + 1;
}
}
fn pick_internal(
&mut self,
bitfield: Option<&[u8]>,
nbits: usize,
allow_in_progress: bool,
) -> Option<u32> {
let n = (self.num_pieces as usize).min(nbits);
if n == 0 {
return None;
}
let order = self.scan_order();
if !allow_in_progress {
match order {
ScanOrder::Forward => {
self.advance_head();
for i in self.head_cursor..n {
if self.is_available(i) && Self::peer_has(bitfield, i) {
return Some(i as u32);
}
}
return None;
}
ScanOrder::Backward => {
self.advance_tail();
let mut i = self.tail_cursor.min(n);
while i > 0 {
i -= 1;
if self.is_available(i) && Self::peer_has(bitfield, i) {
return Some(i as u32);
}
}
return None;
}
_ => {}
}
}
let usable = |p: &Self, i: usize| -> bool {
!p.completed[i]
&& (allow_in_progress || !p.in_progress[i])
&& Self::peer_has(bitfield, i)
};
match order {
ScanOrder::Forward => (0..n).find(|&i| usable(self, i)).map(|i| i as u32),
ScanOrder::Backward => (0..n).rev().find(|&i| usable(self, i)).map(|i| i as u32),
ScanOrder::Rarest => {
let mut best: Option<(u32, usize)> = None;
for i in 0..n {
if usable(self, i) {
let f = self.frequencies[i];
if best.is_none_or(|(bf, _)| f < bf) {
best = Some((f, i));
}
}
}
best.map(|(_, i)| i as u32)
}
ScanOrder::Priority => {
let mut best: Option<(u8, usize)> = None;
for i in 0..n {
if usable(self, i) {
let p = self.priorities[i];
if best.is_none_or(|(bp, _)| p > bp) {
best = Some((p, i));
}
}
}
best.map(|(_, i)| i as u32)
}
ScanOrder::LongestRun => {
let (mut best_start, mut best_len) = (None, 0usize);
let (mut cur_start, mut cur_len) = (None, 0usize);
for i in 0..n {
if usable(self, i) {
if cur_start.is_none() {
cur_start = Some(i);
cur_len = 0;
}
cur_len += 1;
if cur_len > best_len {
best_len = cur_len;
best_start = cur_start;
}
} else {
cur_start = None;
cur_len = 0;
}
}
best_start.map(|i| i as u32)
}
ScanOrder::Random => {
let mut chosen: Option<usize> = None;
let mut seen: u64 = 0;
for i in 0..n {
if usable(self, i) {
seen += 1;
if self.next_rand().is_multiple_of(seen) {
chosen = Some(i);
}
}
}
chosen.map(|i| i as u32)
}
ScanOrder::Geometric => {
let candidates = (0..n).filter(|&i| usable(self, i)).count();
if candidates == 0 {
return None;
}
let r = self.next_rand();
let k = (r.trailing_zeros() as usize).min(candidates - 1);
(0..n).filter(|&i| usable(self, i)).nth(k).map(|i| i as u32)
}
}
}
pub fn select(&mut self, bitfield: &[u8], nbits: usize) -> Option<u32> {
self.pick_internal(Some(bitfield), nbits, false)
}
pub fn pick_next(&mut self) -> Option<u32> {
let allow_in_progress = self.endgame_active();
let n = self.num_pieces as usize;
self.pick_internal(None, n, allow_in_progress)
}
pub fn endgame_active(&self) -> bool {
let remaining = self.remaining_count();
remaining > 0 && remaining <= self.endgame_threshold
}
fn refresh_endgame_candidates(&mut self) {
self.endgame_candidates.clear();
if !self.endgame_active() {
return;
}
for i in 0..self.num_pieces as usize {
if !self.completed[i] {
self.endgame_candidates.push(i);
}
}
}
pub fn endgame_candidates(&self) -> &[usize] {
&self.endgame_candidates
}
pub fn set_frequencies_from_peers(&mut self, freqs: &[usize]) {
let len = freqs.len().min(self.frequencies.len());
for (dst, src) in self.frequencies.iter_mut().zip(freqs.iter()).take(len) {
*dst = *src as u32;
}
}
pub fn pieces_iter(&self) -> impl Iterator<Item = PieceInfo> + '_ {
let n = self.num_pieces as usize;
(0..n).map(move |i| PieceInfo {
index: i as u32,
frequency: self.frequencies[i],
is_completed: self.completed[i],
completed: self.completed[i],
in_progress: self.in_progress[i],
priority: self.priorities[i],
})
}
pub fn get_piece_info(&self, index: u32) -> Option<PieceInfo> {
let i = index as usize;
if i >= self.num_pieces as usize {
return None;
}
Some(PieceInfo {
index,
frequency: self.frequencies[i],
is_completed: self.completed[i],
completed: self.completed[i],
in_progress: self.in_progress[i],
priority: self.priorities[i],
})
}
pub fn priority_mode(&self) -> PiecePriorityMode {
self.priority_mode
}
pub fn remaining_count(&self) -> usize {
self.num_pieces as usize - self.completed_count
}
pub fn mark_completed(&mut self, index: u32) {
let i = index as usize;
debug_assert!(
i < self.num_pieces as usize,
"mark_completed: index out of range"
);
if i >= self.num_pieces as usize {
return;
}
if !self.completed[i] {
self.completed[i] = true;
self.completed_count += 1;
}
self.in_progress[i] = false;
self.refresh_endgame_candidates();
}
pub fn mark_in_progress(&mut self, index: u32, in_progress: bool) {
let i = index as usize;
debug_assert!(
i < self.num_pieces as usize,
"mark_in_progress: index out of range"
);
if i >= self.num_pieces as usize {
return;
}
self.in_progress[i] = in_progress;
if !in_progress {
self.reopen(i);
}
}
pub fn is_in_progress(&self, index: u32) -> bool {
let i = index as usize;
i < self.num_pieces as usize && self.in_progress[i]
}
pub fn is_completed(&self, index: u32) -> bool {
let i = index as usize;
i < self.num_pieces as usize && self.completed[i]
}
pub fn export_bitfield(&self) -> Vec<u8> {
let n = self.num_pieces as usize;
let bf_len = n.div_ceil(8);
let mut bitfield = vec![0u8; bf_len];
for (i, &done) in self.completed.iter().enumerate() {
if done {
let byte_idx = i / 8;
let bit_idx = 7 - (i % 8);
bitfield[byte_idx] |= 1 << bit_idx;
}
}
bitfield
}
pub fn is_complete(&self) -> bool {
self.completed_count == self.num_pieces as usize
}
}
#[derive(Debug, Clone)]
pub struct PiecePickerConfig {
pub strategy: PiecePickStrategy,
pub request_queue_size: usize,
pub end_game_threshold: f64,
}
impl Default for PiecePickerConfig {
fn default() -> Self {
Self {
strategy: PiecePickStrategy::RarestFirst,
request_queue_size: 16,
end_game_threshold: 0.95,
}
}
}
#[derive(Debug, Clone)]
pub struct PickedPiece {
pub index: usize,
pub priority: u8,
pub is_end_game: bool,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_piece_selection_strategy_variants() {
assert_ne!(
PieceSelectionStrategy::Sequential,
PieceSelectionStrategy::RarestFirst
);
assert_ne!(
PieceSelectionStrategy::Random,
PieceSelectionStrategy::Geometric
);
}
#[test]
fn test_piece_priority_mode_variants() {
assert_ne!(
PiecePriorityMode::SequentialHead,
PiecePriorityMode::SequentialTail
);
assert_ne!(
PiecePriorityMode::SequentialTail,
PiecePriorityMode::RarestFirst
);
}
#[test]
fn test_piece_picker_new() {
let picker = PiecePicker::new(100);
assert!(picker.endgame_candidates().is_empty());
assert_eq!(picker.remaining_count(), 100);
assert!(!picker.is_complete());
}
#[test]
fn test_piece_picker_new_u32() {
let picker = PiecePicker::new(50u32);
assert_eq!(picker.remaining_count(), 50);
}
#[test]
fn test_piece_picker_set_strategy() {
let mut picker = PiecePicker::new(100);
picker.set_strategy(PieceSelectionStrategy::Sequential);
let _ = picker.select(&[0xFF; 13], 100);
}
#[test]
fn test_piece_picker_set_priority_mode() {
let mut picker = PiecePicker::new(100);
picker.set_priority_mode(PiecePriorityMode::SequentialHead);
assert_eq!(picker.priority_mode(), PiecePriorityMode::SequentialHead);
}
#[test]
fn test_piece_pick_strategy_variants() {
assert_ne!(
PiecePickStrategy::Sequential,
PiecePickStrategy::RarestFirst
);
assert_ne!(PiecePickStrategy::Random, PiecePickStrategy::Geometric);
}
#[test]
fn test_piece_picker_config_default() {
let config = PiecePickerConfig::default();
assert_eq!(config.strategy, PiecePickStrategy::RarestFirst);
assert_eq!(config.request_queue_size, 16);
assert!(config.end_game_threshold > 0.9);
}
#[test]
fn test_picked_piece() {
let picked = PickedPiece {
index: 42,
priority: 5,
is_end_game: false,
};
assert_eq!(picked.index, 42);
assert_eq!(picked.priority, 5);
assert!(!picked.is_end_game);
}
#[test]
fn test_mark_completed_and_is_complete() {
let mut picker = PiecePicker::new(3u32);
assert!(!picker.is_complete());
assert_eq!(picker.remaining_count(), 3);
picker.mark_completed(0);
assert!(!picker.is_complete());
assert_eq!(picker.remaining_count(), 2);
picker.mark_completed(1);
picker.mark_completed(2);
assert!(picker.is_complete());
assert_eq!(picker.remaining_count(), 0);
}
#[test]
fn test_export_bitfield() {
let mut picker = PiecePicker::new(8u32);
picker.mark_completed(0);
picker.mark_completed(7);
let bf = picker.export_bitfield();
assert_eq!(bf.len(), 1);
assert_eq!(bf[0], 0x81);
}
#[test]
fn test_get_piece_info() {
let mut picker = PiecePicker::new(10u32);
picker.mark_completed(3);
picker.set_frequencies_from_peers(&[0, 2, 0, 0, 5, 0, 0, 0, 0, 0]);
let info = picker.get_piece_info(3).unwrap();
assert!(info.is_completed);
assert_eq!(info.index, 3);
assert_eq!(info.frequency, 0);
let info4 = picker.get_piece_info(4).unwrap();
assert!(!info4.is_completed);
assert_eq!(info4.frequency, 5);
assert!(picker.get_piece_info(100).is_none());
}
#[test]
fn test_pieces_iter() {
let picker = PiecePicker::new(5u32);
let indices: Vec<u32> = picker.pieces_iter().map(|p| p.index).collect();
assert_eq!(indices, vec![0, 1, 2, 3, 4]);
}
#[test]
fn test_pieces_iter_empty() {
let picker = PiecePicker::new(0u32);
let indices: Vec<u32> = picker.pieces_iter().map(|p| p.index).collect();
assert!(indices.is_empty());
}
#[test]
fn test_export_bitfield_partial() {
let mut picker = PiecePicker::new(16u32);
picker.mark_completed(0);
picker.mark_completed(3);
picker.mark_completed(7);
let bf = picker.export_bitfield();
assert_eq!(bf.len(), 2);
assert_eq!(bf[0], 0x91);
assert_eq!(bf[1], 0x00);
}
#[test]
fn test_is_complete_zero_pieces() {
let picker = PiecePicker::new(0u32);
assert!(picker.is_complete());
assert_eq!(picker.remaining_count(), 0);
}
#[test]
fn test_set_frequencies_from_peers() {
let mut picker = PiecePicker::new(4u32);
let freqs: Vec<usize> = vec![3, 1, 5, 2];
picker.set_frequencies_from_peers(&freqs);
let info = picker.get_piece_info(2).unwrap();
assert_eq!(info.frequency, 5);
}
#[test]
fn test_sequential_pick_advances_in_order() {
let mut picker = PiecePicker::new(5u32);
picker.set_strategy(PieceSelectionStrategy::Sequential);
for expected in 0..5u32 {
assert_eq!(picker.pick_next(), Some(expected));
picker.mark_completed(expected);
}
assert_eq!(picker.pick_next(), None);
assert!(picker.is_complete());
}
#[test]
fn test_sequential_skips_in_progress() {
let mut picker = PiecePicker::new(4u32);
picker.set_strategy(PieceSelectionStrategy::Sequential);
picker.set_endgame_threshold(0);
picker.mark_in_progress(0, true);
assert_eq!(picker.pick_next(), Some(1));
picker.mark_in_progress(0, false);
assert_eq!(picker.pick_next(), Some(0));
}
#[test]
fn test_tail_mode_picks_from_the_end() {
let mut picker = PiecePicker::new(6u32);
picker.set_priority_mode(PiecePriorityMode::SequentialTail);
assert_eq!(picker.pick_next(), Some(5));
picker.mark_completed(5);
assert_eq!(picker.pick_next(), Some(4));
}
#[test]
fn test_head_mode_picks_from_the_start() {
let mut picker = PiecePicker::new(6u32);
picker.set_priority_mode(PiecePriorityMode::SequentialHead);
assert_eq!(picker.pick_next(), Some(0));
picker.mark_completed(0);
assert_eq!(picker.pick_next(), Some(1));
}
#[test]
fn test_rarest_first_prefers_lowest_frequency() {
let mut picker = PiecePicker::new(4u32);
picker.set_strategy(PieceSelectionStrategy::RarestFirst);
picker.set_frequencies_from_peers(&[9, 4, 1, 7]);
assert_eq!(picker.pick_next(), Some(2));
picker.mark_completed(2);
assert_eq!(picker.pick_next(), Some(1));
}
#[test]
fn test_priority_strategy_prefers_highest_priority() {
let mut picker = PiecePicker::new(4u32);
picker.set_strategy(PieceSelectionStrategy::Priority);
picker.set_priority(3, 9);
picker.set_priority(1, 5);
assert_eq!(picker.pick_next(), Some(3));
picker.mark_completed(3);
assert_eq!(picker.pick_next(), Some(1));
}
#[test]
fn test_longest_sequence_picks_run_start() {
let mut picker = PiecePicker::new(8u32);
picker.set_strategy(PieceSelectionStrategy::LongestSequence);
picker.mark_completed(1);
picker.mark_completed(2);
assert_eq!(picker.pick_next(), Some(3));
}
#[test]
fn test_random_strategy_returns_available_piece() {
let mut picker = PiecePicker::new(16u32);
picker.set_strategy(PieceSelectionStrategy::Random);
for i in 0..15u32 {
picker.mark_completed(i);
}
assert_eq!(picker.pick_next(), Some(15));
}
#[test]
fn test_geometric_strategy_returns_available_piece() {
let mut picker = PiecePicker::new(32u32);
picker.set_strategy(PieceSelectionStrategy::Geometric);
for _ in 0..50 {
let picked = picker.pick_next().expect("piece must be available");
assert!(picked < 32);
assert!(!picker.is_completed(picked));
}
}
#[test]
fn test_select_respects_peer_bitfield() {
let mut picker = PiecePicker::new(8u32);
picker.set_strategy(PieceSelectionStrategy::Sequential);
let bf = [0b0000_0100u8];
assert_eq!(picker.select(&bf, 8), Some(5));
picker.mark_completed(5);
assert_eq!(picker.select(&bf, 8), None);
}
#[test]
fn test_select_with_zero_nbits_returns_none() {
let mut picker = PiecePicker::new(8u32);
assert_eq!(picker.select(&[0xFF], 0), None);
}
#[test]
fn test_select_ignores_bits_beyond_bitfield_length() {
let mut picker = PiecePicker::new(16u32);
picker.set_strategy(PieceSelectionStrategy::Sequential);
let bf = [0x00u8];
assert_eq!(picker.select(&bf, 16), None);
}
#[test]
fn test_endgame_allows_duplicate_requests() {
let mut picker = PiecePicker::new(4u32);
picker.set_strategy(PieceSelectionStrategy::Sequential);
picker.set_endgame_threshold(4);
picker.mark_in_progress(0, true);
picker.mark_in_progress(1, true);
picker.mark_in_progress(2, true);
picker.mark_in_progress(3, true);
assert!(picker.endgame_active());
assert_eq!(picker.pick_next(), Some(0));
}
#[test]
fn test_endgame_candidates_populated_near_completion() {
let mut picker = PiecePicker::new(4u32);
picker.set_endgame_threshold(2);
picker.mark_completed(0);
assert!(picker.endgame_candidates().is_empty(), "remaining=3 > 2");
picker.mark_completed(1);
assert_eq!(picker.endgame_candidates(), &[2, 3]);
picker.mark_completed(2);
picker.mark_completed(3);
assert!(picker.endgame_candidates().is_empty(), "download finished");
}
#[test]
fn test_mark_completed_is_idempotent() {
let mut picker = PiecePicker::new(3u32);
picker.mark_completed(1);
picker.mark_completed(1);
picker.mark_completed(1);
assert_eq!(picker.remaining_count(), 2);
assert!(!picker.is_complete());
}
#[test]
fn test_pick_next_on_empty_torrent() {
let mut picker = PiecePicker::new(0u32);
assert_eq!(picker.pick_next(), None);
assert!(!picker.endgame_active());
}
#[test]
fn test_mark_in_progress_flag_roundtrip() {
let mut picker = PiecePicker::new(2u32);
assert!(!picker.is_in_progress(0));
picker.mark_in_progress(0, true);
assert!(picker.is_in_progress(0));
assert!(picker.get_piece_info(0).unwrap().in_progress);
picker.mark_in_progress(0, false);
assert!(!picker.is_in_progress(0));
}
#[test]
fn test_mark_completed_clears_in_progress() {
let mut picker = PiecePicker::new(2u32);
picker.mark_in_progress(1, true);
picker.mark_completed(1);
assert!(!picker.is_in_progress(1));
assert!(picker.is_completed(1));
}
}