par2_rs/create/
volume.rs

1use crate::error::{Par2Error, Result};
2
3const MAX_EXPLICIT_VOLUME_COUNT: u32 = 31;
4
5/// A recovery-volume allocation before packet bytes are written.
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct RecoveryVolumePlan {
8    /// First recovery exponent assigned to this volume.
9    pub first_exponent: u32,
10    /// Number of recovery packets assigned to this volume.
11    pub recovery_count: u32,
12    /// Deterministic output filename for this volume.
13    pub filename: String,
14}
15
16/// Divide recovery exponents into deterministic volume allocations.
17pub(crate) fn allocate_volumes(
18    first_exponent: u32,
19    recovery_count: u32,
20    requested_count: Option<u32>,
21    scheme: super::options::VolumeScheme,
22    stem: &str,
23    largest_source_file_size: u64,
24    block_size: u64,
25) -> Result<Vec<RecoveryVolumePlan>> {
26    if let Some(count) = requested_count {
27        if count == 0 {
28            return Err(Par2Error::InvalidCreationOptions {
29                reason: "explicit volume count must be positive".to_string(),
30            });
31        }
32        if count > MAX_EXPLICIT_VOLUME_COUNT {
33            return Err(Par2Error::InvalidCreationOptions {
34                reason: format!(
35                    "explicit volume count {count} exceeds maximum {MAX_EXPLICIT_VOLUME_COUNT}"
36                ),
37            });
38        }
39    }
40    if requested_count.is_some() && matches!(scheme, super::options::VolumeScheme::Limited) {
41        return Err(Par2Error::InvalidCreationOptions {
42            reason: "a volume count is not valid with limited volume sizing".to_string(),
43        });
44    }
45    if recovery_count == 0 {
46        if requested_count.is_some() {
47            return Err(Par2Error::InvalidCreationOptions {
48                reason: "a volume count is not valid when recovery count is zero".to_string(),
49            });
50        }
51        return Ok(Vec::new());
52    }
53
54    let allocations = match (requested_count, scheme) {
55        (Some(count), _) => uniform_allocations(first_exponent, recovery_count, count),
56        (None, super::options::VolumeScheme::Uniform) => {
57            let count = bit_length(recovery_count);
58            uniform_allocations(first_exponent, recovery_count, count)
59        }
60        (None, super::options::VolumeScheme::Variable) => {
61            let count = bit_length(recovery_count);
62            variable_allocations(first_exponent, recovery_count, count)
63        }
64        (None, super::options::VolumeScheme::Limited) => limited_allocations(
65            first_exponent,
66            recovery_count,
67            largest_source_file_size,
68            block_size,
69        )?,
70    };
71    let boundary_exponent = first_exponent.checked_add(recovery_count).ok_or_else(|| {
72        Par2Error::InvalidCreationOptions {
73            reason: "recovery exponent range overflows".to_string(),
74        }
75    })?;
76
77    if allocations.is_empty() || allocations.len() as u32 > recovery_count {
78        return Err(Par2Error::InvalidCreationOptions {
79            reason: "recovery volumes must have a positive count".to_string(),
80        });
81    }
82    let exponent = allocations
83        .last()
84        .and_then(|(first, count)| first.checked_add(*count))
85        .ok_or_else(|| Par2Error::InvalidCreationOptions {
86            reason: "recovery exponent range overflows".to_string(),
87        })?;
88    if exponent != boundary_exponent || allocations.iter().any(|(_, count)| *count == 0) {
89        return Err(Par2Error::InvalidCreationOptions {
90            reason: "recovery volume allocation does not cover the recovery range".to_string(),
91        });
92    }
93    let exponent_width = decimal_width(boundary_exponent);
94    let count_width = decimal_width(
95        allocations
96            .iter()
97            .map(|&(_, count)| count)
98            .chain(std::iter::once(0))
99            .max()
100            .unwrap_or(0),
101    );
102    let volumes = allocations
103        .into_iter()
104        .map(|(first_exponent, recovery_count)| RecoveryVolumePlan {
105            filename: format!(
106                "{stem}.vol{first_exponent:0exponent_width$}+{recovery_count:0count_width$}.par2"
107            ),
108            first_exponent,
109            recovery_count,
110        })
111        .collect();
112    Ok(volumes)
113}
114
115fn uniform_allocations(first_exponent: u32, total: u32, volume_count: u32) -> Vec<(u32, u32)> {
116    let base = total / volume_count;
117    let remainder = total % volume_count;
118    let mut exponent = first_exponent;
119    (0..volume_count)
120        .map(|index| {
121            let count = base + u32::from(index < remainder);
122            let allocation = (exponent, count);
123            exponent += count;
124            allocation
125        })
126        .collect()
127}
128
129fn variable_allocations(first_exponent: u32, total: u32, volume_count: u32) -> Vec<(u32, u32)> {
130    let mut low = 1u64;
131    let geometric_sum = if volume_count >= 64 {
132        u64::MAX
133    } else {
134        (1u64 << volume_count) - 1
135    };
136    while low.saturating_mul(geometric_sum) < total as u64 {
137        low = low.saturating_mul(2);
138    }
139
140    let mut remaining = total as u64;
141    let mut allocations = Vec::with_capacity(volume_count as usize);
142    let mut exponent = first_exponent;
143    for _ in 0..volume_count {
144        let count = remaining.min(low);
145        allocations.push((exponent, count as u32));
146        exponent += count as u32;
147        remaining -= count;
148        low = low.saturating_mul(2);
149    }
150    allocations
151}
152
153fn limited_allocations(
154    first_exponent: u32,
155    recovery_count: u32,
156    largest_source_file_size: u64,
157    block_size: u64,
158) -> Result<Vec<(u32, u32)>> {
159    if block_size == 0 || largest_source_file_size == 0 {
160        return Err(Par2Error::InvalidCreationOptions {
161            reason: "limited volume sizing requires a non-empty source and block size".to_string(),
162        });
163    }
164    let largest = u32::try_from(
165        largest_source_file_size
166            .checked_add(block_size - 1)
167            .ok_or_else(|| Par2Error::InvalidCreationOptions {
168                reason: "largest source block count overflows".to_string(),
169            })?
170            / block_size,
171    )
172    .map_err(|_| Par2Error::InvalidCreationOptions {
173        reason: "largest source block count exceeds the supported range".to_string(),
174    })?;
175    if largest == 0 {
176        return Err(Par2Error::InvalidCreationOptions {
177            reason: "limited volume sizing computed zero source blocks".to_string(),
178        });
179    }
180
181    let whole = recovery_count / largest;
182    let whole = whole.saturating_sub(1);
183    let extra = recovery_count - whole * largest;
184    let volume_count =
185        whole
186            .checked_add(bit_length(extra))
187            .ok_or_else(|| Par2Error::InvalidCreationOptions {
188                reason: "limited volume count overflows".to_string(),
189            })?;
190    let mut allocations = vec![(0u32, 0u32); volume_count as usize];
191    let mut filenumber = volume_count;
192    let mut blocks = recovery_count;
193    let mut exponent = first_exponent.checked_add(recovery_count).ok_or_else(|| {
194        Par2Error::InvalidCreationOptions {
195            reason: "recovery exponent range overflows".to_string(),
196        }
197    })?;
198
199    while blocks >= largest.saturating_mul(2) && filenumber > 0 {
200        filenumber -= 1;
201        exponent -= largest;
202        allocations[filenumber as usize] = (exponent, largest);
203        blocks -= largest;
204    }
205    if filenumber == 0 || blocks == 0 {
206        return Err(Par2Error::InvalidCreationOptions {
207            reason: "limited volume allocation cannot place all recovery blocks".to_string(),
208        });
209    }
210
211    exponent = first_exponent;
212    let mut count = 1u32;
213    for allocation in allocations.iter_mut().take(filenumber as usize) {
214        let number = count.min(blocks);
215        if number == 0 {
216            return Err(Par2Error::InvalidCreationOptions {
217                reason: "limited volume allocation produced an empty volume".to_string(),
218            });
219        }
220        *allocation = (exponent, number);
221        exponent += number;
222        blocks -= number;
223        count = count.saturating_mul(2);
224    }
225    if blocks != 0 {
226        return Err(Par2Error::InvalidCreationOptions {
227            reason: "limited volume allocation left recovery blocks unassigned".to_string(),
228        });
229    }
230    Ok(allocations)
231}
232
233fn bit_length(value: u32) -> u32 {
234    u32::BITS - value.leading_zeros()
235}
236
237fn decimal_width(value: u32) -> usize {
238    value.to_string().len().max(1)
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244    use crate::create::options::VolumeScheme;
245
246    #[test]
247    fn automatic_count_is_bit_length() {
248        let volumes = allocate_volumes(0, 5, None, VolumeScheme::Variable, "set", 20, 4).unwrap();
249        assert_eq!(volumes.len(), 3);
250        assert_eq!(
251            volumes
252                .iter()
253                .map(|volume| volume.recovery_count)
254                .sum::<u32>(),
255            5
256        );
257    }
258
259    #[test]
260    fn uniform_allocation_and_widths_are_stable() {
261        let volumes =
262            allocate_volumes(7, 10, Some(3), VolumeScheme::Uniform, "set", 20, 4).unwrap();
263        assert_eq!(
264            volumes
265                .iter()
266                .map(|volume| volume.recovery_count)
267                .collect::<Vec<_>>(),
268            vec![4, 3, 3]
269        );
270        assert_eq!(volumes[0].filename, "set.vol07+4.par2");
271        assert_eq!(volumes[2].first_exponent, 14);
272    }
273
274    #[test]
275    fn widths_include_the_zero_count_boundary_entry() {
276        let volumes =
277            allocate_volumes(0, 100, Some(3), VolumeScheme::Uniform, "set", 400, 4).unwrap();
278        assert_eq!(volumes[0].filename, "set.vol000+34.par2");
279        assert_eq!(volumes[2].filename, "set.vol067+33.par2");
280    }
281
282    #[test]
283    fn explicit_count_forces_uniform_allocation() {
284        let volumes =
285            allocate_volumes(0, 100, Some(10), VolumeScheme::Variable, "set", 400, 4).unwrap();
286        assert_eq!(
287            volumes
288                .iter()
289                .map(|volume| volume.recovery_count)
290                .collect::<Vec<_>>(),
291            vec![10; 10]
292        );
293        assert_eq!(volumes[0].filename, "set.vol000+10.par2");
294        assert_eq!(volumes[9].filename, "set.vol090+10.par2");
295    }
296
297    #[test]
298    fn explicit_count_above_public_limit_is_rejected() {
299        let error =
300            allocate_volumes(0, 100, Some(32), VolumeScheme::Uniform, "set", 400, 4).unwrap_err();
301        assert!(matches!(error, Par2Error::InvalidCreationOptions { .. }));
302    }
303
304    #[test]
305    fn limited_allocation_matches_largest_source_cap() {
306        for (recovery_count, expected) in [
307            (1, vec![1]),
308            (10, vec![1, 2, 4, 3]),
309            (20, vec![1, 2, 4, 3, 10]),
310            (35, vec![1, 2, 4, 8, 10, 10]),
311        ] {
312            let volumes =
313                allocate_volumes(0, recovery_count, None, VolumeScheme::Limited, "set", 40, 4)
314                    .unwrap();
315            assert_eq!(
316                volumes
317                    .iter()
318                    .map(|volume| volume.recovery_count)
319                    .collect::<Vec<_>>(),
320                expected
321            );
322            assert!(volumes.iter().all(|volume| volume.recovery_count <= 10));
323        }
324
325        let volumes = allocate_volumes(7, 20, None, VolumeScheme::Limited, "set", 40, 4).unwrap();
326        assert_eq!(volumes[0].filename, "set.vol07+01.par2");
327        assert_eq!(volumes.last().unwrap().filename, "set.vol17+10.par2");
328    }
329
330    #[test]
331    fn limited_allocation_rejects_explicit_count() {
332        let error =
333            allocate_volumes(0, 8, Some(2), VolumeScheme::Limited, "set", 40, 4).unwrap_err();
334        assert!(matches!(error, Par2Error::InvalidCreationOptions { .. }));
335    }
336}
par2_rs/create/volume.rs

par2_rs/create/
volume.rs
