bd46f233de
staged-measurement §9: objects, distinct contents, referenced and stored bytes, recomputed from the objects. A content hash given two lengths has no accounting. wai_video_package::dedup_stats calls it; a well-formed map seals the same bytes, and a map with one hash at two lengths now fails verify. Co-Authored-By: Claude Opus 5.5 <[email protected]>
73 lines
2.8 KiB
Rust
73 lines
2.8 KiB
Rust
//! Deduplication totals over a set of objects (`extensions/staged-measurement.md` §9).
|
|
//!
|
|
//! Every figure is recomputed from the objects themselves, never declared: how many
|
|
//! objects a set references, how many distinct contents they have, the bytes the set
|
|
//! references, and the bytes a store keeps when it holds one copy of each content.
|
|
//! The same function serves a staged title's objects and a package's segments.
|
|
|
|
use std::collections::BTreeMap;
|
|
|
|
/// The four totals of staged-measurement §9.1.
|
|
#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
|
|
pub struct DedupTotals {
|
|
/// Objects referenced, a repeated content counted each time.
|
|
pub objects: u64,
|
|
/// Distinct content hashes.
|
|
pub unique: u64,
|
|
/// The bytes of every object referenced, a repeated content counted each time.
|
|
pub referenced_bytes: u64,
|
|
/// The bytes of one object per distinct content hash.
|
|
pub stored_bytes: u64,
|
|
}
|
|
|
|
/// The totals over `items`, each a content hash and the object's bytes.
|
|
///
|
|
/// One content hash names one content, so it has one length. A hash that comes with
|
|
/// two lengths is a set that cannot be accounted: the first such hash is returned
|
|
/// with the length seen first and the conflicting one, and no totals are given.
|
|
/// A byte sum past `u64` is not a set of real objects either; it saturates, which
|
|
/// no set that fits in memory reaches.
|
|
pub fn totals_checked<I: IntoIterator<Item = ([u8; 32], u64)>>(items: I) -> Result<DedupTotals, ([u8; 32], u64, u64)> {
|
|
let mut seen: BTreeMap<[u8; 32], u64> = BTreeMap::new();
|
|
let mut t = DedupTotals::default();
|
|
for (hash, len) in items {
|
|
t.objects += 1;
|
|
t.referenced_bytes = t.referenced_bytes.saturating_add(len);
|
|
match seen.get(&hash) {
|
|
Some(&first) if first != len => return Err((hash, first, len)),
|
|
Some(_) => {}
|
|
None => {
|
|
seen.insert(hash, len);
|
|
t.unique += 1;
|
|
t.stored_bytes = t.stored_bytes.saturating_add(len);
|
|
}
|
|
}
|
|
}
|
|
Ok(t)
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
fn h(b: u8) -> [u8; 32] {
|
|
[b; 32]
|
|
}
|
|
|
|
#[test]
|
|
fn totals_of_a_set_with_a_repeat() {
|
|
let t = totals_checked([(h(1), 100), (h(2), 40), (h(1), 100), (h(3), 7)]).unwrap();
|
|
assert_eq!(t, DedupTotals { objects: 4, unique: 3, referenced_bytes: 247, stored_bytes: 147 });
|
|
}
|
|
|
|
#[test]
|
|
fn empty_set_is_all_zero() {
|
|
assert_eq!(totals_checked(std::iter::empty()).unwrap(), DedupTotals::default());
|
|
}
|
|
|
|
#[test]
|
|
fn one_hash_with_two_lengths_is_refused() {
|
|
// The first hash seen twice with a different length is named, with both lengths.
|
|
assert_eq!(totals_checked([(h(1), 10), (h(2), 5), (h(1), 11), (h(2), 6)]), Err((h(1), 10, 11)));
|
|
}
|
|
}
|