pub(super) fn direct_retained_graph_bytes(
num_procs: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
intra_len: usize,
inter_len: usize,
gen_len: usize,
) -> Result<usize, String> {
let slots_per_proc = blocks_per_proc.checked_mul(facts_per_proc).ok_or_else(|| {
format!(
"weir direct resident IFDS CSR budget overflowed blocks*facts: {blocks_per_proc}*{facts_per_proc}. Fix: shard the IFDS problem before direct resident prepare."
)
})?;
let total_nodes_u32 = num_procs.checked_mul(slots_per_proc).ok_or_else(|| {
format!(
"weir direct resident IFDS CSR budget overflowed procs*blocks*facts: {num_procs}*{blocks_per_proc}*{facts_per_proc}. Fix: shard the IFDS problem before direct resident prepare."
)
})?;
let total_nodes = crate::dispatch_decode::u32_to_usize(
total_nodes_u32,
"weir direct resident IFDS CSR budget total node count",
)?;
let intra_count = u32::try_from(intra_len).map_err(|error| {
format!(
"weir direct resident IFDS CSR budget received too many intra edges for u32 indexing: {error}. Fix: shard the IFDS graph before direct resident prepare."
)
})?;
let inter_count = u32::try_from(inter_len).map_err(|error| {
format!(
"weir direct resident IFDS CSR budget received too many inter edges for u32 indexing: {error}. Fix: shard the IFDS graph before direct resident prepare."
)
})?;
let gen_count = u32::try_from(gen_len).map_err(|error| {
format!(
"weir direct resident IFDS CSR budget received too many GEN entries for u32 indexing: {error}. Fix: shard the IFDS graph before direct resident prepare."
)
})?;
let max_col_count = intra_count
.checked_mul(facts_per_proc)
.and_then(|value| value.checked_add(intra_count.checked_mul(gen_count)?))
.and_then(|value| value.checked_add(inter_count.checked_mul(facts_per_proc)?))
.ok_or_else(|| {
"weir direct resident IFDS CSR budget maximum column count overflows u32. Fix: shard the IFDS graph before direct resident prepare.".to_string()
})?;
let max_col_count = crate::dispatch_decode::u32_to_usize(
max_col_count,
"weir direct resident IFDS CSR budget maximum column count",
)?;
let word = std::mem::size_of::<u32>();
total_nodes
.checked_mul(word)
.and_then(|pg_nodes| {
total_nodes
.checked_add(1)
.and_then(|row_words| row_words.checked_mul(word))
.and_then(|row_ptr| pg_nodes.checked_add(row_ptr))
})
.and_then(|bytes| {
max_col_count
.max(1)
.checked_mul(word)
.and_then(|col_idx| bytes.checked_add(col_idx))
})
.and_then(|bytes| {
max_col_count
.max(1)
.checked_mul(word)
.and_then(|edge_mask| bytes.checked_add(edge_mask))
})
.and_then(|bytes| {
total_nodes
.checked_mul(word)
.and_then(|node_tags| bytes.checked_add(node_tags))
})
.ok_or_else(|| {
"weir direct resident IFDS CSR budget retained byte count overflowed usize. Fix: shard the IFDS graph before direct resident prepare.".to_string()
})
}
pub(crate) fn graph_hash(
intra_edges: &[(u32, u32, u32)],
inter_edges: &[(u32, u32, u32, u32)],
flow_gen: &[(u32, u32, u32)],
flow_kill: &[(u32, u32, u32)],
) -> u64 {
const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
let mut hash = FNV_OFFSET;
hash = mix_unordered_triples(hash, 0x4946_4453_494e_5452, intra_edges);
hash = mix_unordered_quads(hash, 0x4946_4453_494e_5445, inter_edges);
hash = mix_unordered_triples(hash, 0x4946_4453_5f47_454e, flow_gen);
hash = mix_unordered_triples(hash, 0x4946_4453_4b49_4c4c, flow_kill);
hash
}
fn mix_unordered_triples(hash: u64, family: u64, edges: &[(u32, u32, u32)]) -> u64 {
let mut bag = BagHash::new(family, edge_count_for_hash(edges.len()));
for &(a, b, c) in edges {
bag.push(mix_u32_words(family, &[a, b, c]));
}
bag.finish(hash)
}
fn mix_unordered_quads(hash: u64, family: u64, edges: &[(u32, u32, u32, u32)]) -> u64 {
let mut bag = BagHash::new(family, edge_count_for_hash(edges.len()));
for &(a, b, c, d) in edges {
bag.push(mix_u32_words(family, &[a, b, c, d]));
}
bag.finish(hash)
}
struct BagHash {
family: u64,
len: u64,
sum: u64,
xor: u64,
sum_square: u64,
rotate_xor: u64,
}
impl BagHash {
fn new(family: u64, len: u64) -> Self {
Self {
family,
len,
sum: 0,
xor: 0,
sum_square: 0,
rotate_xor: 0,
}
}
fn push(&mut self, edge_hash: u64) {
self.sum = self.sum.wrapping_add(edge_hash);
self.xor ^= edge_hash;
self.sum_square = self
.sum_square
.wrapping_add(edge_hash.wrapping_mul(edge_hash | 1));
self.rotate_xor ^= edge_hash.rotate_left(bag_hash_rotation(edge_hash));
}
fn finish(self, hash: u64) -> u64 {
mix_u64(
mix_u64(
mix_u64(
mix_u64(mix_u64(mix_u64(hash, self.family), self.len), self.sum),
self.xor,
),
self.sum_square,
),
self.rotate_xor,
)
}
}
fn bag_hash_rotation(edge_hash: u64) -> u32 {
(edge_hash & 63) as u32
}
fn edge_count_for_hash(edge_count: usize) -> u64 {
if usize::BITS > u64::BITS && edge_count > u64::MAX as usize {
return u64::MAX;
}
edge_count as u64
}
fn mix_u32_words(mut hash: u64, words: &[u32]) -> u64 {
for &word in words {
hash = mix_u64(hash, u64::from(word));
}
hash
}
pub(super) fn mix_u64(mut hash: u64, word: u64) -> u64 {
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
for byte in word.to_le_bytes() {
hash ^= u64::from(byte);
hash = hash.wrapping_mul(FNV_PRIME);
}
hash
}