fire_scope/
overlap.rs

1use crate::ipv4_utils::ipv4_summarize_range;
2use ipnet::{IpNet, Ipv6Net};
3use std::cmp::{max, min};
4use std::collections::BTreeSet;
5use std::net::Ipv6Addr;
6
7pub fn find_overlaps(country_ips: &BTreeSet<IpNet>, as_ips: &BTreeSet<IpNet>) -> BTreeSet<IpNet> {
8    // aggregateでプレフィックス数を削減
9    let country_agg = IpNet::aggregate(&country_ips.iter().copied().collect::<Vec<_>>());
10    let as_agg = IpNet::aggregate(&as_ips.iter().copied().collect::<Vec<_>>());
11
12    // IPv4 / IPv6を分割
13    let (mut c_v4, mut c_v6) = split_ipv4_ipv6(&country_agg);
14    let (mut a_v4, mut a_v6) = split_ipv4_ipv6(&as_agg);
15
16    c_v4.sort_by_key(|(s, _)| *s);
17    a_v4.sort_by_key(|(s, _)| *s);
18    c_v6.sort_by_key(|(s, _)| *s);
19    a_v6.sort_by_key(|(s, _)| *s);
20
21    let o_v4 = overlap_ranges_v4(&c_v4, &a_v4);
22    let o_v6 = overlap_ranges_v6(&c_v6, &a_v6);
23
24    o_v4.into_iter().chain(o_v6).collect()
25}
26
27fn split_ipv4_ipv6(nets: &[IpNet]) -> (Vec<(u64, u64)>, Vec<(u128, u128)>) {
28    let mut v4 = Vec::new();
29    let mut v6 = Vec::new();
30
31    for net in nets {
32        match net {
33            IpNet::V4(n) => {
34                v4.push((
35                    u32::from(n.network()) as u64,
36                    u32::from(n.broadcast()) as u64,
37                ));
38            }
39            IpNet::V6(n) => {
40                v6.push((ipv6_to_u128(n.network()), ipv6_to_u128(n.broadcast())));
41            }
42        }
43    }
44    (v4, v6)
45}
46
47fn overlap_ranges_v4(country: &[(u64, u64)], aslist: &[(u64, u64)]) -> Vec<IpNet> {
48    let mut res = Vec::new();
49    let (mut i, mut j) = (0, 0);
50
51    while i < country.len() && j < aslist.len() {
52        let (c_s, c_e) = country[i];
53        let (a_s, a_e) = aslist[j];
54
55        let s = max(c_s, a_s);
56        let e = min(c_e, a_e);
57
58        if s <= e {
59            res.extend(ipv4_summarize_range(s, e));
60        }
61        if c_e < a_e {
62            i += 1;
63        } else {
64            j += 1;
65        }
66    }
67    res
68}
69
70fn overlap_ranges_v6(country: &[(u128, u128)], aslist: &[(u128, u128)]) -> Vec<IpNet> {
71    let mut res = Vec::new();
72    let (mut i, mut j) = (0, 0);
73
74    while i < country.len() && j < aslist.len() {
75        let (c_s, c_e) = country[i];
76        let (a_s, a_e) = aslist[j];
77
78        let s = max(c_s, a_s);
79        let e = min(c_e, a_e);
80
81        if s <= e {
82            res.extend(ipv6_summarize_range(s, e));
83        }
84        if c_e < a_e {
85            i += 1;
86        } else {
87            j += 1;
88        }
89    }
90    res
91}
92
93fn ipv6_summarize_range(start: u128, end: u128) -> Vec<IpNet> {
94    let mut cidrs = Vec::new();
95    let mut cur = start;
96
97    while cur <= end {
98        let max = largest_ipv6_block_in_overlap(cur, end);
99        if let Ok(net) = Ipv6Net::new(Ipv6Addr::from(cur), max) {
100            cidrs.push(IpNet::V6(net));
101            let step = 1u128 << (128 - max);
102            cur = cur.saturating_add(step);
103        } else {
104            break;
105        }
106    }
107
108    cidrs
109}
110
111fn ipv6_to_u128(addr: Ipv6Addr) -> u128 {
112    u128::from_be_bytes(addr.octets())
113}
114
115fn largest_ipv6_block_in_overlap(current: u128, end: u128) -> u8 {
116    let tz: u32 = current.trailing_zeros();
117    let span: u32 = ((end - current + 1).ilog2_128()) as u32;
118    let max: u32 = tz.min(span);
119    (128 - max) as u8
120}
121
122trait ILog2U128 {
123    fn ilog2_128(self) -> u32;
124}
125impl ILog2U128 for u128 {
126    fn ilog2_128(self) -> u32 {
127        if self == 0 {
128            0
129        } else {
130            127 - self.leading_zeros()
131        }
132    }
133}
fire_scope/overlap.rs

fire_scope/
overlap.rs
