#![allow(clippy::needless_range_loop)]
use crate::allocator::{
ancestor_doubling_table, check_hierarchy_acyclic, clip, compute_pi_kq_for_kq,
};
use crate::fixed::{NonNegativeFixed, SignedFixed};
use crate::generated::consequence_mass::case_studies::{
LensSpec, PackedSemanticState, FACTOR_ACCESS_FREQUENCY, FACTOR_BUSINESS_VALUE,
FACTOR_DOWNSTREAM_CONSEQUENCE, FACTOR_RECOMPUTATION_COST, FACTOR_RETRIEVAL_DEMAND,
FACTOR_SCHEDULING_DEMAND, FACTOR_SEARCH_DEMAND, FACTOR_STANDING, FACTOR_VERIFICATION_COST, K,
MEASURE_CACHE, MEASURE_RETRIEVAL, MEASURE_SCHEDULING, MEASURE_SEARCH, N, Q,
};
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct AllocationBindings {
pub candidate_id: usize,
pub measure: usize,
pub lens_index: usize,
pub lens_q: i32,
pub inputs_digest: u64,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum AllocationRefusal {
CandidateIndexOutOfRange,
MeasureIndexOutOfRange,
LensIndexOutOfRange,
LensQMismatch,
InputsDigestMismatch,
ShareMismatch,
Cyclic,
}
impl core::fmt::Display for AllocationRefusal {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
core::fmt::Debug::fmt(self, f)
}
}
#[cfg(feature = "std")]
impl std::error::Error for AllocationRefusal {}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct AllocationReceipt {
bindings: AllocationBindings,
share: u32,
}
impl AllocationReceipt {
#[inline(always)]
pub fn bindings(&self) -> AllocationBindings {
self.bindings
}
#[inline(always)]
pub fn share_bits(&self) -> u32 {
self.share
}
#[inline(always)]
pub fn share(&self) -> NonNegativeFixed {
NonNegativeFixed::from_bits(self.share)
}
}
const MIX64_GAMMA: u64 = 0x9E37_79B9_7F4A_7C15;
const MIX64_FMUX_K1: u64 = 0xFF51_AFD7_ED55_8CCD;
const MIX64_FMUX_K2: u64 = 0xC4CE_B9FE_1A85_EC53;
#[inline(always)]
fn mix64(a: u64, b: u64) -> u64 {
let mut x = a ^ b.wrapping_mul(MIX64_GAMMA);
x ^= x >> 33;
x = x.wrapping_mul(MIX64_FMUX_K1);
x ^= x >> 33;
x = x.wrapping_mul(MIX64_FMUX_K2);
x ^= x >> 33;
x
}
fn inputs_digest(
states: &[PackedSemanticState; N],
parent: &[i32; N],
weights: &[[NonNegativeFixed; 2 * Q]; N],
) -> u64 {
const INPUTS_DIGEST_SEED: u64 = 0x1234_5678_9abc_def0;
let mut d = INPUTS_DIGEST_SEED;
for state in states.iter() {
for factor in state.factors.iter() {
d = mix64(d, factor.val as u64);
}
}
for &p in parent.iter() {
d = mix64(d, p as u32 as u64);
}
for row in weights.iter() {
for w in row.iter() {
d = mix64(d, w.val as u64);
}
}
d
}
fn derive_topology(parent: &[i32; N]) -> ([bool; N], [[bool; N]; N]) {
let mut is_leaf = [true; N];
for i in 0..N {
for j in 0..N {
if parent[j] == i as i32 {
is_leaf[i] = false;
}
}
}
let p = ancestor_doubling_table(parent);
let mut is_descendant = [[false; N]; N];
for i in 0..N {
for j in 0..N {
let mut matched = j == i;
for level in 0..8 {
matched |= p[level][j] == i as i32;
}
is_descendant[i][j] = matched;
}
}
let mut is_subtree_leaf = [[false; N]; N];
for i in 0..N {
for k in 0..N {
is_subtree_leaf[i][k] = is_leaf[k] && is_descendant[i][k];
}
}
(is_leaf, is_subtree_leaf)
}
fn derive_node_masses(
states: &[PackedSemanticState; N],
m_min: NonNegativeFixed,
m_max: NonNegativeFixed,
) -> [[NonNegativeFixed; N]; K] {
let mut node_masses = [[NonNegativeFixed::ZERO; N]; K];
for i in 0..N {
let state = &states[i];
let f_recomp = state.factors[FACTOR_RECOMPUTATION_COST];
let f_verify = state.factors[FACTOR_VERIFICATION_COST];
let f_stand = state.factors[FACTOR_STANDING];
let f_access = state.factors[FACTOR_ACCESS_FREQUENCY];
let f_search = state.factors[FACTOR_SEARCH_DEMAND];
let f_retrieve = state.factors[FACTOR_RETRIEVAL_DEMAND];
let f_sched = state.factors[FACTOR_SCHEDULING_DEMAND];
let f_bval = state.factors[FACTOR_BUSINESS_VALUE];
let f_conseq = state.factors[FACTOR_DOWNSTREAM_CONSEQUENCE];
let m_cache = (f_recomp * NonNegativeFixed::from_num(5) + f_verify) * f_access * f_stand;
let m_search = (f_bval + f_conseq) * f_search * f_stand;
let m_retrieval = f_bval * f_retrieve;
let m_sched = f_bval * f_sched;
node_masses[MEASURE_CACHE][i] = m_cache;
node_masses[MEASURE_RETRIEVAL][i] = m_retrieval;
node_masses[MEASURE_SCHEDULING][i] = m_sched;
node_masses[MEASURE_SEARCH][i] = m_search;
}
for k in 0..K {
for i in 0..N {
node_masses[k][i] = clip(node_masses[k][i], m_min, m_max);
}
}
node_masses
}
#[allow(clippy::too_many_arguments)]
fn recompute_share(
candidate_id: usize,
measure: usize,
lens_index: usize,
states: &[PackedSemanticState; N],
parent: &[i32; N],
weights: &[[NonNegativeFixed; 2 * Q]; N],
lenses: &[LensSpec; Q],
m_min: NonNegativeFixed,
m_max: NonNegativeFixed,
) -> NonNegativeFixed {
let (is_leaf, is_subtree_leaf) = derive_topology(parent);
let node_masses = derive_node_masses(states, m_min, m_max);
let q_val = SignedFixed::from_bits(lenses[lens_index].q.val);
let pi = compute_pi_kq_for_kq(
measure,
lens_index,
q_val,
parent,
&is_leaf,
&is_subtree_leaf,
&node_masses,
weights,
);
pi[candidate_id]
}
#[allow(clippy::too_many_arguments)]
pub fn seal_allocation_receipt(
candidate_id: usize,
measure: usize,
lens_index: usize,
states: &[PackedSemanticState; N],
parent: &[i32; N],
weights: &[[NonNegativeFixed; 2 * Q]; N],
lenses: &[LensSpec; Q],
m_min: NonNegativeFixed,
m_max: NonNegativeFixed,
) -> Result<AllocationReceipt, AllocationRefusal> {
if candidate_id >= N {
return Err(AllocationRefusal::CandidateIndexOutOfRange);
}
if measure >= K {
return Err(AllocationRefusal::MeasureIndexOutOfRange);
}
if lens_index >= Q {
return Err(AllocationRefusal::LensIndexOutOfRange);
}
if check_hierarchy_acyclic(parent).is_err() {
return Err(AllocationRefusal::Cyclic);
}
let share = recompute_share(
candidate_id,
measure,
lens_index,
states,
parent,
weights,
lenses,
m_min,
m_max,
);
Ok(AllocationReceipt {
bindings: AllocationBindings {
candidate_id,
measure,
lens_index,
lens_q: lenses[lens_index].q.val,
inputs_digest: inputs_digest(states, parent, weights),
},
share: share.val,
})
}
pub fn verify_allocation_receipt(
receipt: &AllocationReceipt,
states: &[PackedSemanticState; N],
parent: &[i32; N],
weights: &[[NonNegativeFixed; 2 * Q]; N],
lenses: &[LensSpec; Q],
m_min: NonNegativeFixed,
m_max: NonNegativeFixed,
) -> Result<(), AllocationRefusal> {
let b = receipt.bindings;
if b.candidate_id >= N {
return Err(AllocationRefusal::CandidateIndexOutOfRange);
}
if b.measure >= K {
return Err(AllocationRefusal::MeasureIndexOutOfRange);
}
if b.lens_index >= Q {
return Err(AllocationRefusal::LensIndexOutOfRange);
}
if lenses[b.lens_index].q.val != b.lens_q {
return Err(AllocationRefusal::LensQMismatch);
}
if check_hierarchy_acyclic(parent).is_err() {
return Err(AllocationRefusal::Cyclic);
}
if inputs_digest(states, parent, weights) != b.inputs_digest {
return Err(AllocationRefusal::InputsDigestMismatch);
}
let recomputed = recompute_share(
b.candidate_id,
b.measure,
b.lens_index,
states,
parent,
weights,
lenses,
m_min,
m_max,
);
if recomputed.val != receipt.share {
return Err(AllocationRefusal::ShareMismatch);
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generated::consequence_mass::case_studies::{
ETA, LAMBDA, LENS_REGISTRY, OBJECT_REGISTRY,
};
use crate::generated_profile::{ALLOCATOR_MASS_MAX_BITS, ALLOCATOR_MASS_MIN_BITS};
fn fresh_weights() -> [[NonNegativeFixed; 2 * Q]; N] {
[[NonNegativeFixed::ONE; 2 * Q]; N]
}
fn star_parent() -> [i32; N] {
let mut parent = [0i32; N];
parent[0] = -1;
parent
}
#[test]
fn genuine_receipt_verifies() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let receipt = seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
)
.expect("bounds are in range");
assert_eq!(
verify_allocation_receipt(&receipt, &states, &parent, &weights, &lenses, m_min, m_max),
Ok(())
);
let mut mutable_weights = weights;
let payoffs = [[NonNegativeFixed::ZERO; 2 * Q]; N];
let mu = [NonNegativeFixed::ZERO; N];
let costs = [NonNegativeFixed::ZERO; N];
let mut last_switch_t = 0u32;
let mut prev_mode = 0u32;
let result = crate::allocator::allocate(
&states,
&lenses,
&LAMBDA,
ETA,
&parent,
&mut mutable_weights,
&payoffs,
NonNegativeFixed::ZERO,
NonNegativeFixed::ZERO,
&mu,
&costs,
0,
&mut last_switch_t,
&mut prev_mode,
500,
crate::generated::stability_profile::CERTIFICATE_DIGEST,
None,
);
assert!(result.is_ok());
}
#[test]
fn refuses_when_share_was_tampered_with() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let mut receipt = seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
)
.expect("bounds are in range");
receipt.share ^= 1;
assert_eq!(
verify_allocation_receipt(&receipt, &states, &parent, &weights, &lenses, m_min, m_max),
Err(AllocationRefusal::ShareMismatch)
);
}
#[test]
fn refuses_when_inputs_were_tampered_with() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let receipt = seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
)
.expect("bounds are in range");
let mut tampered_weights = weights;
tampered_weights[0][0] = NonNegativeFixed::from_bits(tampered_weights[0][0].val + 1);
assert_eq!(
verify_allocation_receipt(
&receipt,
&states,
&parent,
&tampered_weights,
&lenses,
m_min,
m_max
),
Err(AllocationRefusal::InputsDigestMismatch)
);
}
#[test]
fn refuses_when_lens_q_was_tampered_with() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let mut receipt = seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
)
.expect("bounds are in range");
receipt.bindings.lens_q ^= 1;
assert_eq!(
verify_allocation_receipt(&receipt, &states, &parent, &weights, &lenses, m_min, m_max),
Err(AllocationRefusal::LensQMismatch)
);
}
#[test]
fn seal_refuses_cyclic_parent() {
let states = OBJECT_REGISTRY;
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let mut parent = star_parent();
parent[0] = 1;
parent[1] = 0;
assert_eq!(
seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
),
Err(AllocationRefusal::Cyclic)
);
}
#[test]
fn verify_refuses_cyclic_parent() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
let receipt = seal_allocation_receipt(
3,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
)
.expect("bounds are in range, acyclic parent");
let mut cyclic_parent = parent;
cyclic_parent[0] = 1;
cyclic_parent[1] = 0;
assert_eq!(
verify_allocation_receipt(
&receipt,
&states,
&cyclic_parent,
&weights,
&lenses,
m_min,
m_max
),
Err(AllocationRefusal::Cyclic)
);
}
#[test]
fn seal_refuses_out_of_range_candidate() {
let states = OBJECT_REGISTRY;
let parent = star_parent();
let weights = fresh_weights();
let lenses = LENS_REGISTRY;
let m_min = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MIN_BITS);
let m_max = NonNegativeFixed::from_bits(ALLOCATOR_MASS_MAX_BITS);
assert_eq!(
seal_allocation_receipt(
N,
MEASURE_CACHE,
1,
&states,
&parent,
&weights,
&lenses,
m_min,
m_max,
),
Err(AllocationRefusal::CandidateIndexOutOfRange)
);
}
}