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
7/// 国別IPs, AS別IPsそれぞれから得られたBTreeSet<IpNet>を受け取り、
8/// 部分的に重複している範囲（サブネット）をすべてBTreeSet<IpNet>で返す。
9/// 改良版: まず集約→IPv4/IPv6分割→2ポインタ方式で重複計算
10pub fn find_overlaps(country_ips: &BTreeSet<IpNet>, as_ips: &BTreeSet<IpNet>) -> BTreeSet<IpNet> {
11    // まず両者をaggregateしてサブネット個数を削減
12    let country_agg = IpNet::aggregate(&country_ips.iter().copied().collect::<Vec<_>>());
13    let as_agg = IpNet::aggregate(&as_ips.iter().copied().collect::<Vec<_>>());
14
15    // IPv4/IPv6をそれぞれ分割
16    let (mut c_v4, mut c_v6) = split_ipv4_ipv6(&country_agg);
17    let (mut a_v4, mut a_v6) = split_ipv4_ipv6(&as_agg);
18
19    // 開始アドレス順にソート
20    c_v4.sort_by_key(|(start, _end)| *start);
21    c_v6.sort_by_key(|(start, _end)| *start);
22    a_v4.sort_by_key(|(start, _end)| *start);
23    a_v6.sort_by_key(|(start, _end)| *start);
24
25    // それぞれ2ポインタでオーバーラップを求める
26    let overlap_v4 = overlap_ranges_v4(&c_v4, &a_v4);
27    let overlap_v6 = overlap_ranges_v6(&c_v6, &a_v6);
28
29    // 合体してBTreeSetに
30    overlap_v4
31        .into_iter()
32        .chain(overlap_v6.into_iter())
33        .collect()
34}
35
36/// IpNetベクタを IPv4, IPv6 それぞれ (start, end)形式に変換して返す
37fn split_ipv4_ipv6(nets: &[IpNet]) -> (Vec<(u32, u32)>, Vec<(u128, u128)>) {
38    let mut v4_ranges = Vec::new();
39    let mut v6_ranges = Vec::new();
40
41    for net in nets {
42        match net {
43            IpNet::V4(v4net) => {
44                let start = u32::from(v4net.network());
45                let end = u32::from(v4net.broadcast());
46                v4_ranges.push((start, end));
47            }
48            IpNet::V6(v6net) => {
49                let start = ipv6_to_u128(v6net.network());
50                let end = ipv6_to_u128(v6net.broadcast());
51                v6_ranges.push((start, end));
52            }
53        }
54    }
55    (v4_ranges, v6_ranges)
56}
57
58/// 2つのソート済みIPv4範囲リストを 2ポインタで走査して重複区間をCIDR単位で返す
59fn overlap_ranges_v4(country: &[(u32, u32)], aslist: &[(u32, u32)]) -> Vec<IpNet> {
60    let mut result = Vec::new();
61    let mut i = 0;
62    let mut j = 0;
63
64    while i < country.len() && j < aslist.len() {
65        let (c_start, c_end) = country[i];
66        let (a_start, a_end) = aslist[j];
67
68        // 重複範囲の開始/終了
69        let overlap_start = max(c_start, a_start);
70        let overlap_end = min(c_end, a_end);
71
72        if overlap_start <= overlap_end {
73            // CIDR単位に分割
74            let cidrs = ipv4_summarize_range(overlap_start, overlap_end);
75            result.extend(cidrs);
76        }
77
78        // どちらかが先に終わるかでポインタを進める
79        if c_end < a_end {
80            i += 1;
81        } else {
82            j += 1;
83        }
84    }
85
86    result
87}
88
89/// 2つのソート済みIPv6範囲リストを2ポインタで走査して重複区間をCIDR単位で返す
90fn overlap_ranges_v6(country: &[(u128, u128)], aslist: &[(u128, u128)]) -> Vec<IpNet> {
91    let mut result = Vec::new();
92    let mut i = 0;
93    let mut j = 0;
94
95    while i < country.len() && j < aslist.len() {
96        let (c_start, c_end) = country[i];
97        let (a_start, a_end) = aslist[j];
98
99        let overlap_start = max(c_start, a_start);
100        let overlap_end = min(c_end, a_end);
101
102        if overlap_start <= overlap_end {
103            // CIDR単位に分割
104            let cidrs = ipv6_summarize_range(overlap_start, overlap_end);
105            result.extend(cidrs);
106        }
107
108        if c_end < a_end {
109            i += 1;
110        } else {
111            j += 1;
112        }
113    }
114
115    result
116}
117
118/// 開始～終了アドレスを最適なIPv6 CIDRに分割
119/// 従来のipv6_overlap内部ロジックを外部化
120fn ipv6_summarize_range(start: u128, end: u128) -> Vec<IpNet> {
121    let mut cidrs = Vec::new();
122    let mut current = start;
123
124    while current <= end {
125        let max_size = largest_ipv6_block_in_overlap(current, end);
126        if let Ok(net) = Ipv6Net::new(Ipv6Addr::from(current), max_size) {
127            cidrs.push(IpNet::V6(net));
128            let block_size = 1u128 << (128 - max_size);
129            current = current.saturating_add(block_size);
130        } else {
131            break;
132        }
133    }
134
135    cidrs
136}
137
138/// IPv6アドレスをu128に
139fn ipv6_to_u128(addr: Ipv6Addr) -> u128 {
140    u128::from_be_bytes(addr.octets())
141}
142
143/// IPv6の範囲を切り分けるためのブロックサイズを決定
144fn largest_ipv6_block_in_overlap(current: u128, end: u128) -> u8 {
145    let tz = current.trailing_zeros() as u128;
146    let span = (end - current + 1).ilog2_128();
147    let max_block = tz.min(span);
148    (128 - max_block) as u8
149}
150
151/// u128用のilog2相当
152trait ILog2U128 {
153    fn ilog2_128(self) -> u128;
154}
155impl ILog2U128 for u128 {
156    fn ilog2_128(self) -> u128 {
157        if self == 0 {
158            0
159        } else {
160            127 - self.leading_zeros() as u128
161        }
162    }
163}
fire_scope/overlap.rs

fire_scope/
overlap.rs
