eth_state_diff/
participation.rs

1//! Delta encoding for validator participation flags.
2//!
3//! This module provides a compact sparse encoding for participation flag
4//! vectors used in Ethereum consensus state.
5//!
6//! Rather than storing the entire target vector, only modified indices and
7//! their replacement values are encoded. Modified indices are represented as
8//! delta-varint encoded gaps, allowing sparse updates to compress efficiently.
9//!
10//! Deltas produced by [`diff_participation`] can be applied in-place using
11//! [`apply_participation`].
12
13use crate::{
14    balances::{read_varint, write_varint},
15    types::{ArchivedParticipationDiff, ParticipationDiff},
16};
17
18/// Computes a compact participation delta.
19///
20/// The returned delta contains sufficient information to reconstruct `target`
21/// from `base`.
22pub fn diff_participation(base: &[u8], target: &[u8]) -> ParticipationDiff {
23    let target_len = target.len();
24
25    if target.iter().all(|&v| v == 0) {
26        return ParticipationDiff::AllZeros(target_len);
27    }
28
29    let common_len = base.len().min(target_len);
30    let mut sparse_indices = Vec::with_capacity(50_000);
31    let mut new_values = Vec::with_capacity(50_000);
32
33    let mut last_idx = 0u64;
34
35    for i in 0..common_len {
36        if base[i] != target[i] {
37            // Calculate and write the gap from the last changed index
38            let gap = (i - last_idx as usize) as u64;
39            write_varint(gap, &mut sparse_indices);
40
41            new_values.push(target[i]);
42            last_idx = i as u64;
43        }
44    }
45
46    let extension = if target_len > base.len() {
47        target[base.len()..].to_vec()
48    } else {
49        Vec::new()
50    };
51
52    ParticipationDiff::Sparse {
53        sparse_indices,
54        new_values,
55        extension,
56    }
57}
58
59/// Applies a participation delta in-place.
60///
61/// After successful execution, `base` is identical to the target participation
62/// vector used to produce `delta`.
63///
64/// This function performs a single linear pass over the encoded delta.
65/// Additional storage is allocated only when the reconstructed vector grows
66/// beyond its current length.
67///
68/// # Complexity
69///
70/// O(m)
71///
72/// where `m` is the number of encoded modifications plus any appended values.
73pub fn apply_participation(base: &mut Vec<u8>, delta: &ArchivedParticipationDiff) {
74    match delta {
75        ArchivedParticipationDiff::AllZeros(len) => {
76            base.clear();
77            base.resize(len.to_native() as usize, 0);
78        }
79        ArchivedParticipationDiff::Sparse {
80            sparse_indices,
81            new_values,
82            extension,
83        } => {
84            let indices_raw = sparse_indices.as_slice();
85            let values_iter = new_values.iter();
86
87            let mut cursor = 0usize;
88            let mut current_idx = 0usize;
89
90            for val in values_iter {
91                // Decode the gap
92                let gap = read_varint(indices_raw, &mut cursor) as usize;
93                current_idx += gap;
94
95                if current_idx >= base.len() {
96                    base.resize(current_idx + 1, 0);
97                }
98
99                base[current_idx] = *val;
100            }
101
102            base.extend(extension.iter().copied());
103        }
104    }
105}
eth_state_diff/participation.rs

eth_state_diff/
participation.rs
