server/lib/src/digest.rs
//! Content digests ON THE ENGINE (W12, stinky-01 section 3.1).
//!
//! Every digest holger computed for ITSELF — the blake3 content address a
//! promotion seals under — ran `blake3::hash(whole)` on the request thread:
//! one core, MEASURED at 2.04 GB/s on t14s, fifteen cores idle. blake3 is a
//! tree hash, so it can be forked over subtrees and the subtrees merged into
//! the same digest the serial call produces; this module does that fork on
//! `znippy_zoomies::gatling_forkjoin` (ROOT LAW #0: gatling, never rayon —
//! `blake3`'s own `update_rayon` is exactly what this module exists to not
//! call).
//!
//! sha256 is NOT here, on purpose: it is a sequential Merkle–Damgård
//! construction and cannot be forked without changing the digest, and cargo,
//! OCI and pip name it on the wire. Where holger must match a client's sha256
//! it hashes WHILE the bytes stream (`exposed::http::StreamedDigests`,
//! `raw::write_relpath_from`, the OCI upload session), so the pass costs no
//! second traversal; where holger chooses its own digest, it is blake3, and it
//! comes here.
use blake3::hazmat::{
left_subtree_len, merge_subtrees_non_root, merge_subtrees_root, ChainingValue, HasherExt as _,
Mode,
};
use znippy_zoomies::gatling_forkjoin::gatling_for_each;
/// One leaf per worker unit: 1 MiB = 1024 blake3 chunks, a power-of-two
/// multiple of `CHUNK_LEN`, so every leaf boundary is a subtree boundary
/// whatever the input's length.
const LEAF_BYTES: usize = 1 << 20;
/// Below this the fork costs more than it saves (thread wake-up against a
/// few MiB of SIMD hashing); the serial reference is used unchanged.
pub const PARALLEL_FLOOR_BYTES: usize = 8 * LEAF_BYTES;
/// The blake3 digest of `data`, forked over the engine when it is large enough
/// to pay. Bit-identical to `blake3::hash(data)` at every length.
pub fn blake3_hash(data: &[u8]) -> blake3::Hash {
blake3_hash_with_floor(data, PARALLEL_FLOOR_BYTES)
}
/// Lowercase-hex of [`blake3_hash`] — the content address promote seals under.
pub fn blake3_hex(data: &[u8]) -> String {
blake3_hash(data).to_hex().to_string()
}
/// [`blake3_hash`] with the serial/forked cut-over chosen by the caller (tests
/// drive the forked path over small inputs with it).
pub fn blake3_hash_with_floor(data: &[u8], floor: usize) -> blake3::Hash {
if data.len() < floor.max(LEAF_BYTES + 1) {
return blake3::hash(data);
}
let leaves = data.len().div_ceil(LEAF_BYTES);
// One fan-out over every core: each unit hashes its own leaf into a
// chaining value at its own input offset. The output lands in index order,
// preallocated by the engine — no channel, no barrier, no collector.
let cvs: Vec<ChainingValue> = gatling_for_each(leaves, 0, |i| {
let start = i * LEAF_BYTES;
let end = (start + LEAF_BYTES).min(data.len());
let mut h = blake3::Hasher::new();
h.set_input_offset(start as u64);
h.update(&data[start..end]);
h.finalize_non_root()
});
// The tree combine is O(leaves) and trivial next to the leaves.
let split = left_leaves(data.len() as u64);
let left = combine(&cvs[..split], (split * LEAF_BYTES) as u64);
let right = combine(
&cvs[split..],
data.len() as u64 - (split * LEAF_BYTES) as u64,
);
merge_subtrees_root(&left, &right, Mode::Hash)
}
/// How many whole leaves the left subtree of an input of `len` bytes holds.
/// `left_subtree_len` is the largest power-of-two multiple of `CHUNK_LEN`
/// strictly below `len`; for `len > LEAF_BYTES` that is a multiple of
/// `LEAF_BYTES`, so the split always lands on a leaf boundary.
fn left_leaves(len: u64) -> usize {
(left_subtree_len(len) / LEAF_BYTES as u64) as usize
}
fn combine(cvs: &[ChainingValue], len: u64) -> ChainingValue {
if cvs.len() == 1 {
return cvs[0];
}
let split = left_leaves(len);
let left = combine(&cvs[..split], (split * LEAF_BYTES) as u64);
let right = combine(&cvs[split..], len - (split * LEAF_BYTES) as u64);
merge_subtrees_non_root(&left, &right, Mode::Hash)
}
#[cfg(test)]
mod tests {
use super::*;
fn pattern(len: usize) -> Vec<u8> {
let mut v = vec![0u8; len];
let mut x = 0x9E37_79B9_7F4A_7C15u64;
for b in v.iter_mut() {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
*b = (x & 0xFF) as u8;
}
v
}
/// The forked digest is the reference digest at every length that
/// exercises a different tree shape: below a leaf, exactly a leaf, a leaf
/// and one byte, two leaves, a non-power-of-two number of leaves, a
/// partial last leaf, and the real cut-over.
#[test]
fn blake3_on_gatling_matches_the_reference_at_every_tree_shape() {
let l = LEAF_BYTES;
for len in [
0,
1,
1023,
1024,
l - 1,
l,
l + 1,
2 * l,
2 * l + 1,
3 * l + 5,
4 * l,
5 * l - 1,
7 * l + 1024,
PARALLEL_FLOOR_BYTES,
PARALLEL_FLOOR_BYTES + 7,
17 * l + 1,
] {
let data = pattern(len);
let forked = blake3_hash_with_floor(&data, 0);
assert_eq!(forked, blake3::hash(&data), "length {len}");
assert_eq!(
blake3_hash(&data),
blake3::hash(&data),
"length {len} (default floor)"
);
}
}
/// The hex form promote seals under is the same string `blake3::hash(..).to_hex()`
/// produced before this module existed.
#[test]
fn the_hex_is_the_same_string_promote_always_sealed_under() {
let data = pattern(PARALLEL_FLOOR_BYTES + 3);
assert_eq!(blake3_hex(&data), blake3::hash(&data).to_hex().to_string());
assert_eq!(blake3_hex(b""), blake3::hash(b"").to_hex().to_string());
}
}