Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/kademlia/id.rs

3.9 KiB, 25 runs

created by r1870400018:11188, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! 256-bit node identifiers with XOR distance.
2//!
3//! The Kademlia id space is the full 256-bit range. Every routing decision is
4//! expressed as a XOR distance between two [`NodeId`]s. The distance's position
5//! in its binary expansion -- specifically the index of the most-significant
6//! set bit -- selects which k-map in the routing table is responsible for a
7//! given peer.
8//!
9//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
10//! Anthropic Claude
11
12use oxedyne_fe2o3_core::prelude::*;
13
14use std::{
15 fmt,
16 ops::BitXor,
17};
18
19
20pub const ID_LEN: usize = 32; // 256 bits
21pub const ID_BITS: usize = ID_LEN * 8;
22
23
24/// A 256-bit node identifier.
25///
26/// The byte ordering is big-endian in the logical sense: index `0` holds the
27/// most-significant byte. `Ord` and `PartialOrd` follow the natural byte-wise
28/// ordering and are only useful for deterministic iteration, not for XOR
29/// distance comparison -- use [`NodeId::distance`] and its returned
30/// [`Distance`] for that.
31#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
32pub struct NodeId(pub [u8; ID_LEN]);
33
34impl NodeId {
35 pub const fn from_bytes(bytes: [u8; ID_LEN]) -> Self {
36 Self(bytes)
37 }
38
39 /// The slice must be exactly [`ID_LEN`] bytes.
40 pub fn from_slice(bytes: &[u8]) -> Outcome<Self> {
41 if bytes.len() != ID_LEN {
42 return Err(err!(
43 "NodeId requires exactly {} bytes, got {}.", ID_LEN, bytes.len();
44 Invalid, Input, Size));
45 }
46 let mut arr = [0u8; ID_LEN];
47 arr.copy_from_slice(bytes);
48 Ok(Self(arr))
49 }
50
51 pub fn as_bytes(&self) -> &[u8; ID_LEN] {
52 &self.0
53 }
54
55 /// The XOR distance between two identifiers.
56 pub fn distance(&self, other: &Self) -> Distance {
57 let mut out = [0u8; ID_LEN];
58 for i in 0..ID_LEN {
59 out[i] = self.0[i] ^ other.0[i];
60 }
61 Distance(out)
62 }
63
64 /// The index of the k-map holding peers at this XOR distance.
65 ///
66 /// The index is the bit-position of the distance's most-significant set
67 /// bit, counted from the least-significant bit (so index `0` is the
68 /// closest non-self bucket and index `255` is the furthest). If the two
69 /// identifiers are equal the distance is zero and this returns `None` --
70 /// a node should never appear in its own routing table.
71 pub fn bucket_index(&self, other: &Self) -> Option<usize> {
72 self.distance(other).bucket_index()
73 }
74}
75
76impl BitXor for NodeId {
77 type Output = Distance;
78
79 fn bitxor(self, rhs: Self) -> Self::Output {
80 self.distance(&rhs)
81 }
82}
83
84impl fmt::Display for NodeId {
85 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
86 for b in &self.0 {
87 ok!(write!(f, "{:02x}", b));
88 }
89 Ok(())
90 }
91}
92
93
94/// A 256-bit XOR distance between two [`NodeId`]s.
95///
96/// Comparison is byte-wise big-endian, which is equivalent to numeric
97/// comparison of the corresponding 256-bit unsigned integer. Smaller values
98/// are "closer" in the Kademlia sense.
99#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
100pub struct Distance(pub [u8; ID_LEN]);
101
102impl Distance {
103 pub const ZERO: Self = Self([0u8; ID_LEN]); // two equal identifiers
104
105 pub fn is_zero(&self) -> bool {
106 self.0.iter().all(|b| *b == 0)
107 }
108
109 /// The index of the most-significant set bit, counted from the
110 /// least-significant bit.
111 ///
112 /// Returns `None` if the distance is zero. For any non-zero distance the
113 /// result is in `0..ID_BITS`.
114 pub fn bucket_index(&self) -> Option<usize> {
115 for (i, b) in self.0.iter().enumerate() {
116 if *b != 0 {
117 // Byte `i` is the most-significant non-zero byte. Within the
118 // byte, the most-significant set bit sits at bit-position
119 // (7 - leading_zeros). The overall bit-index from the LSB is
120 // then (ID_BITS - 1 - 8*i - leading_zeros_within_byte).
121 let byte_lz = b.leading_zeros() as usize;
122 return Some(ID_BITS - 1 - (i * 8 + byte_lz));
123 }
124 }
125 None
126 }
127}
128
129impl fmt::Display for Distance {
130 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131 for b in &self.0 {
132 ok!(write!(f, "{:02x}", b));
133 }
134 Ok(())
135 }
136}