mod arq_set;
mod peer_view;
mod strat;
#[cfg(feature = "test_utils")]
pub mod ascii;
pub use arq_set::*;
pub use peer_view::*;
pub use strat::*;
use kitsune_p2p_dht_arc::{DhtArc, DhtArcRange};
use crate::{op::Loc, spacetime::*};
pub fn pow2(p: u8) -> u32 {
debug_assert!(p < 32);
2u32.pow((p as u32).min(31))
}
pub fn pow2f(p: u8) -> f64 {
debug_assert!(p < 32);
2f64.powf(p as f64)
}
pub(crate) const U32_LEN: u64 = u32::MAX as u64 + 1;
pub trait ArqStart: Sized + Copy + std::fmt::Debug {
fn to_loc(&self, topo: &Topology, power: u8) -> Loc;
fn to_offset(&self, topo: &Topology, power: u8) -> SpaceOffset;
fn requantize_up(&self, factor: u32) -> Option<Self>;
fn requantize_down(&self, factor: u32) -> Self;
}
impl ArqStart for Loc {
fn to_loc(&self, _topo: &Topology, _power: u8) -> Loc {
*self
}
fn to_offset(&self, topo: &Topology, power: u8) -> SpaceOffset {
SpaceOffset::from_absolute_rounded(*self, topo, power)
}
fn requantize_up(&self, _factor: u32) -> Option<Self> {
Some(*self)
}
fn requantize_down(&self, _factor: u32) -> Self {
*self
}
}
impl ArqStart for SpaceOffset {
fn to_loc(&self, topo: &Topology, power: u8) -> Loc {
self.to_absolute(topo, power)
}
fn to_offset(&self, _topo: &Topology, _power: u8) -> SpaceOffset {
*self
}
fn requantize_up(&self, factor: u32) -> Option<Self> {
((**self) % factor == 0).then(|| *self / factor)
}
fn requantize_down(&self, factor: u32) -> Self {
*self * factor
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Arq<S: ArqStart = Loc> {
pub start: S,
pub power: u8,
pub count: SpaceOffset,
}
pub type ArqLocated = Arq<Loc>;
pub type ArqBounds = Arq<SpaceOffset>;
impl<S: ArqStart> Arq<S> {
pub fn new(power: u8, start: S, count: SpaceOffset) -> Self {
Self {
power,
start,
count,
}
}
#[inline]
fn quantum_chunk_width(&self) -> u32 {
pow2(self.power)
}
#[inline]
pub(crate) fn absolute_chunk_width(&self, topo: &Topology) -> u32 {
let len = self
.quantum_chunk_width()
.saturating_mul(topo.space.quantum)
.min(u32::MAX / 2);
debug_assert!(
len <= u32::MAX / 4 + 2,
"chunk width is much larger than expected: {}",
len
);
len
}
pub fn absolute_length(&self, topo: &Topology) -> u64 {
let len = (self.absolute_chunk_width(topo) as u64 * (*self.count as u64)).min(U32_LEN);
debug_assert_eq!(
len,
self.to_dht_arc_range(topo).length(),
"lengths don't match {:?}",
self
);
len
}
pub fn to_dht_arc_range(&self, topo: &Topology) -> DhtArcRange {
if is_full(topo, self.power, *self.count) {
DhtArcRange::Full
} else if *self.count == 0 {
DhtArcRange::Empty
} else {
let (a, b) = self.to_edge_locs(topo);
DhtArcRange::from_bounds(a, b)
}
}
pub fn to_edge_locs(&self, topo: &Topology) -> (Loc, Loc) {
let start = self.start.to_offset(topo, self.power);
let left = start.to_loc(topo, self.power);
let right = (start + self.count).to_loc(topo, self.power) - Loc::from(1);
(left, right)
}
pub fn power(&self) -> u8 {
self.power
}
pub fn count(&self) -> u32 {
self.count.into()
}
pub fn coverage(&self, topo: &Topology) -> f64 {
self.absolute_length(topo) as f64 / 2f64.powf(32.0)
}
pub fn requantize(&self, new_power: u8) -> Option<Self> {
let old_power = self.power;
let old_count = self.count;
if old_power < new_power {
let factor = 2u32.pow((new_power - old_power) as u32);
self.start.requantize_up(factor).and_then(|start| {
let new_count = old_count / factor;
if old_count == new_count * factor {
Some((start, new_power, new_count))
} else {
None
}
})
} else {
let factor = 2u32.pow((old_power - new_power) as u32);
let new_count = old_count * factor;
Some((self.start.requantize_down(factor), new_power, new_count))
}
.map(|(start, power, count)| Self {
start,
power,
count,
})
}
pub fn is_full(&self, topo: &Topology) -> bool {
is_full(topo, self.power(), self.count())
}
pub fn is_empty(&self) -> bool {
self.count() == 0
}
}
impl Arq<Loc> {
pub fn new_full(topo: &Topology, start: Loc, power: u8) -> Self {
let count = pow2(32u8.saturating_sub(power + topo.space.quantum_power));
assert!(is_full(topo, power, count));
Self {
start,
power,
count: count.into(),
}
}
pub fn downshift(&self) -> Self {
Self {
start: self.start,
power: self.power - 1,
count: self.count * 2,
}
}
pub fn upshift(&self, force: bool) -> Option<Self> {
let count = if force && *self.count % 2 == 1 {
self.count + SpaceOffset(1)
} else {
self.count
};
(*count % 2 == 0).then(|| Self {
start: self.start,
power: self.power + 1,
count: count / 2,
})
}
pub fn to_bounds(&self, topo: &Topology) -> ArqBounds {
ArqBounds {
start: SpaceOffset::from(self.start.as_u32() / self.absolute_chunk_width(topo)),
power: self.power,
count: self.count,
}
}
pub fn start_loc(&self) -> Loc {
self.start
}
pub fn count_mut(&mut self) -> &mut u32 {
&mut self.count
}
pub fn to_dht_arc(&self, topo: &Topology) -> DhtArc {
let len = self.absolute_length(topo);
DhtArc::from_start_and_len(self.start, len)
}
pub fn from_dht_arc_approximate(topo: &Topology, strat: &ArqStrat, dht_arc: &DhtArc) -> Self {
approximate_arq(topo, strat, dht_arc.start_loc(), dht_arc.length())
}
pub fn equivalent(topo: &Topology, a: &Self, b: &Self) -> bool {
let qa = a.absolute_chunk_width(topo);
let qb = b.absolute_chunk_width(topo);
a.start == b.start && (a.count.wrapping_mul(qa) == b.count.wrapping_mul(qb))
}
}
impl From<&ArqBounds> for ArqBounds {
fn from(a: &ArqBounds) -> Self {
*a
}
}
impl ArqBounds {
pub fn equivalent(topo: &Topology, a: &Self, b: &Self) -> bool {
let qa = a.absolute_chunk_width(topo);
let qb = b.absolute_chunk_width(topo);
*a.count == 0 && *b.count == 0
|| (a.start.wrapping_mul(qa) == b.start.wrapping_mul(qb)
&& a.count.wrapping_mul(qa) == b.count.wrapping_mul(qb))
}
pub fn from_interval_rounded(
topo: &Topology,
power: u8,
interval: DhtArcRange,
) -> (Self, bool) {
Self::from_interval_inner(&topo.space, power, interval, true).unwrap()
}
pub fn from_interval(topo: &Topology, power: u8, interval: DhtArcRange) -> Option<Self> {
Self::from_interval_inner(&topo.space, power, interval, false).map(|(a, _)| a)
}
#[cfg(any(test, feature = "test_utils"))]
pub fn to_arq<F: FnOnce(Loc) -> Loc>(&self, topo: &Topology, f: F) -> Arq {
Arq {
start: f(self.start.to_loc(topo, self.power)),
power: self.power,
count: self.count,
}
}
pub fn empty(topo: &Topology, power: u8) -> Self {
Self::from_interval(topo, power, DhtArcRange::Empty).unwrap()
}
fn from_interval_inner(
dim: &Dimension,
power: u8,
interval: DhtArcRange,
always_round: bool,
) -> Option<(Self, bool)> {
match interval {
DhtArcRange::Empty => Some((
Self {
start: 0.into(),
power,
count: 0.into(),
},
false,
)),
DhtArcRange::Full => {
assert!(power > 0);
let full_count = 2u32.pow(32 - power as u32 - dim.quantum_power as u32);
Some((
Self {
start: 0.into(),
power,
count: full_count.into(),
},
false,
))
}
DhtArcRange::Bounded(lo, hi) => {
let lo = lo.as_u32();
let hi = hi.as_u32();
let q = dim.quantum;
let s = 2u32.pow(power as u32) * q;
let offset = lo / s;
let len = if lo <= hi {
hi - lo + 1
} else {
(2u64.pow(32) - (lo as u64) + (hi as u64) + 1) as u32
};
let count = len / s;
let rem = len % s;
let diff = rem.min(s - rem);
let lossless = lo == offset * s && (diff <= 1);
if always_round || lossless {
Some((
Self {
start: offset.into(),
power,
count: count.into(),
},
!lossless,
))
} else {
tracing::warn!("{} =?= {} == {} * {}", lo, offset * s, offset, s);
tracing::warn!("{} =?= {} == {} * {}", len, count * s, count, s);
None
}
}
}
}
pub fn segments(&self) -> impl Iterator<Item = SpaceSegment> + '_ {
(0..*self.count).map(|c| SpaceSegment::new(self.power, c.wrapping_add(*self.start)))
}
pub fn offset(&self) -> SpaceOffset {
self.start
}
}
pub fn is_full(topo: &Topology, power: u8, count: u32) -> bool {
let max = 32u8.saturating_sub(topo.space.quantum_power);
if power == 0 {
false
} else if power >= 32 {
true
} else {
count >= pow2(max.saturating_sub(power))
}
}
pub fn power_and_count_from_length(dim: &Dimension, len: u64, max_chunks: u32) -> (u8, u32) {
assert!(len <= U32_LEN);
let mut power = 0;
let mut count = (len / dim.quantum as u64) as f64;
let max = max_chunks as f64;
while count.round() > max {
power += 1;
count /= 2.0;
}
let count = count.round() as u32;
(power, count)
}
pub fn power_and_count_from_length_exact(
dim: &Dimension,
len: u64,
min_chunks: u32,
) -> Option<(u8, u32)> {
assert!(len <= U32_LEN);
let z = len.trailing_zeros();
if z < dim.quantum_power.into() {
return None;
}
let mut power = z as u8 - dim.quantum_power;
let mut count = len >> z;
while (count as u32) < min_chunks {
count *= 2;
power -= 1;
}
Some((power, count as u32))
}
pub fn approximate_arq(topo: &Topology, strat: &ArqStrat, start: Loc, len: u64) -> Arq {
if len == 0 {
Arq::new(topo.min_space_power(), start, 0.into())
} else {
let (power, count) = power_and_count_from_length(&topo.space, len, strat.max_chunks());
let min = strat.min_chunks() as f64;
let max = strat.max_chunks() as f64;
debug_assert!(
power == 0 || count >= min as u32,
"count < min: {} < {}",
count,
min
);
debug_assert!(
power == 0 || count <= max as u32,
"count > max: {} > {}",
count,
max
);
debug_assert!(count == 0 || count - 1 <= u32::MAX / topo.space.quantum);
debug_assert!(
power <= topo.max_space_power(strat),
"power too large: {}",
power
);
Arq::new(power, start, count.into())
}
}
#[cfg(test)]
mod tests {
use super::*;
use test_case::test_case;
#[test]
fn test_is_full() {
{
let topo = Topology::unit_zero();
assert!(!is_full(&topo, 31, 1));
assert!(is_full(&topo, 31, 2));
assert!(is_full(&topo, 31, 3));
assert!(!is_full(&topo, 30, 3));
assert!(is_full(&topo, 30, 4));
assert!(is_full(&topo, 29, 8));
assert!(is_full(&topo, 1, 2u32.pow(31)));
assert!(!is_full(&topo, 1, 2u32.pow(31) - 1));
assert!(is_full(&topo, 2, 2u32.pow(30)));
assert!(!is_full(&topo, 2, 2u32.pow(30) - 1));
}
{
let topo = Topology::standard_epoch_full();
assert!(!is_full(&topo, 31 - 12, 1));
assert!(is_full(&topo, 31 - 12, 2));
assert!(is_full(&topo, 31, 2));
assert!(!is_full(&topo, 1, 2));
}
}
#[test]
fn test_full_intervals() {
let topo = Topology::unit_zero();
let full1 = Arq::new_full(&topo, 0u32.into(), 29);
let full2 = Arq::new_full(&topo, 2u32.pow(31).into(), 25);
assert!(matches!(full1.to_dht_arc_range(&topo), DhtArcRange::Full));
assert!(matches!(full2.to_dht_arc_range(&topo), DhtArcRange::Full));
}
#[test]
fn arq_requantize() {
let c = Arq {
start: Loc::from(42u32),
power: 20,
count: SpaceOffset(10),
};
let rq = |c: &Arq, p| (*c).requantize(p);
assert_eq!(rq(&c, 18).map(|c| *c.count), Some(40));
assert_eq!(rq(&c, 19).map(|c| *c.count), Some(20));
assert_eq!(rq(&c, 20).map(|c| *c.count), Some(10));
assert_eq!(rq(&c, 21).map(|c| *c.count), Some(5));
assert_eq!(rq(&c, 22).map(|c| *c.count), None);
assert_eq!(rq(&c, 23).map(|c| *c.count), None);
assert_eq!(rq(&c, 24).map(|c| *c.count), None);
let c = Arq {
start: Loc::from(42u32),
power: 20,
count: SpaceOffset(256),
};
assert_eq!(rq(&c, 12).map(|c| *c.count), Some(256 * 256));
assert_eq!(rq(&c, 28).map(|c| *c.count), Some(1));
assert_eq!(rq(&c, 29).map(|c| *c.count), None);
}
#[test]
fn test_to_bounds() {
let topo = Topology::unit_zero();
let pow: u8 = 4;
{
let a = Arq::new(pow, (2u32.pow(pow.into()) - 1).into(), 16.into());
let b = a.to_bounds(&topo);
assert_eq!(b.offset(), SpaceOffset(0));
assert_eq!(b.count(), 16);
}
{
let a = Arq::new(pow, 4u32.into(), 18.into());
let b = a.to_bounds(&topo);
assert_eq!(b.count(), 18);
}
}
#[test]
fn from_interval_regression() {
let topo = Topology::unit_zero();
let i = DhtArcRange::Bounded(4294967040u32.into(), 511.into());
assert!(ArqBounds::from_interval(&topo, 8, i).is_some());
}
#[test_case(2u64.pow(30), (14, 16))]
#[test_case(2u64.pow(31), (15, 16))]
#[test_case(2u64.pow(32), (16, 16))]
#[test_case(128 * 2u64.pow(24), (15, 16))]
#[test_case((128 + 16) * 2u64.pow(24), (16, 9))]
fn test_power_and_count_from_length(len: u64, expected: (u8, u32)) {
let topo = Topology::standard_epoch_full();
let (p, c) = power_and_count_from_length(&topo.space, len, 16);
assert_eq!((p, c), expected);
assert_eq!(
2u64.pow(p as u32 + topo.space.quantum_power as u32) * c as u64,
len
);
}
#[test_case(2u64.pow(30), (15, 8))]
#[test_case(2u64.pow(31), (16, 8))]
#[test_case(2u64.pow(32), (17, 8))]
#[test_case((128 + 16 + 8) * 2u64.pow(24), (15, 19))]
#[test_case((128 + 16 + 8 + 4 + 2) * 2u64.pow(24), (13, 79))]
fn test_power_and_count_from_length_exact(len: u64, expected: (u8, u32)) {
let topo = Topology::standard_epoch_full();
let (p, c) = power_and_count_from_length_exact(&topo.space, len, 8).unwrap();
assert_eq!((p, c), expected);
assert_eq!(
2u64.pow(p as u32 + topo.space.quantum_power as u32) * c as u64,
len
);
}
proptest::proptest! {
#[test]
fn test_to_edge_locs(power in 0u8..16, count in 8u32..16, loc: u32) {
let topo = Topology::standard_epoch_full();
let a = Arq::new(power, Loc::from(loc), SpaceOffset(count));
let (left, right) = a.to_edge_locs(&topo);
let p = pow2(power);
assert_eq!(left.as_u32() % p, 0);
assert_eq!(right.as_u32().wrapping_add(1) % p, 0);
assert_eq!(a.absolute_length(&topo), (right - left).as_u32() as u64 + 1);
}
#[test]
fn test_preserve_ordering_for_bounds(mut centers: Vec<u32>, count in 0u32..8, power in 0u8..16) {
let topo = Topology::standard_epoch_full();
centers.sort();
let arqs: Vec<_> = centers.into_iter().map(|c| Arq::new(power, c.into(), count.into())).collect();
let mut bounds: Vec<_> = arqs.into_iter().map(|a| a.to_bounds(&topo)).enumerate().collect();
bounds.sort_by_key(|(_, b)| b.to_edge_locs(&topo).0);
let mut prev = 0;
let mut split = None;
for (i, (ix, _)) in bounds.iter().enumerate() {
if prev > *ix {
split = Some(i);
break;
}
prev = *ix;
}
let (b1, b2) = bounds.split_at(split.unwrap_or(0));
let ix1: Vec<_> = b1.iter().map(|(i, _)| i).collect();
let ix2: Vec<_> = b2.iter().map(|(i, _)| i).collect();
let mut ix1s = ix1.clone();
let mut ix2s = ix2.clone();
ix1s.sort();
ix2s.sort();
assert_eq!(ix1, ix1s);
assert_eq!(ix2, ix2s);
}
#[test]
fn dht_arc_roundtrip_unit_topo(center: u32, pow in 4..29u8, count in 0..8u32) {
let topo = Topology::unit_zero();
let length = count as u64 * 2u64.pow(pow as u32) / 2 * 2;
let strat = ArqStrat::default();
let arq = approximate_arq(&topo, &strat, center.into(), length);
let dht_arc = arq.to_dht_arc(&topo);
assert_eq!(arq.absolute_length(&topo), dht_arc.length());
let arq2 = Arq::from_dht_arc_approximate(&topo, &strat, &dht_arc);
assert_eq!(arq, arq2);
}
#[test]
fn dht_arc_roundtrip_standard_topo(center: u32, pow in 0..16u8, count in 0..8u32) {
let topo = Topology::standard_epoch_full();
let length = count as u64 * 2u64.pow(pow as u32) / 2 * 2;
let strat = ArqStrat::default();
let arq = approximate_arq(&topo, &strat, center.into(), length);
let dht_arc = arq.to_dht_arc(&topo);
assert_eq!(arq.absolute_length(&topo), dht_arc.length());
let arq2 = Arq::from_dht_arc_approximate(&topo, &strat, &dht_arc);
assert!(Arq::<Loc>::equivalent(&topo, &arq, &arq2));
}
#[test]
fn arc_interval_roundtrip(center: u32, pow in 0..16u8, count in 0..8u32) {
let topo = Topology::standard_epoch_full();
let length = count as u64 * 2u64.pow(pow as u32) / 2 * 2;
let strat = ArqStrat::default();
let arq = approximate_arq(&topo, &strat, center.into(), length).to_bounds(&topo);
let interval = arq.to_dht_arc_range(&topo);
let arq2 = ArqBounds::from_interval(&topo, arq.power(), interval).unwrap();
assert!(ArqBounds::equivalent(&topo, &arq, &arq2));
}
}
}