fire_scope/
overlap.rs

1use ipnet::{IpNet, Ipv4Net, Ipv6Net};
2use std::cmp::{max, min};
3use std::collections::BTreeSet;
4use std::net::{Ipv4Addr, Ipv6Addr};
5
6/// 国別IPs, AS別IPs それぞれから得られたBTreeSet<IpNet>を受け取り、
7/// 部分的に重複している範囲（サブネット）をすべてBTreeSet<IpNet>で返す。
8pub fn find_overlaps(country_ips: &BTreeSet<IpNet>, as_ips: &BTreeSet<IpNet>) -> BTreeSet<IpNet> {
9    let mut result = BTreeSet::new();
10
11    for cnet in country_ips {
12        for anet in as_ips {
13            let overlap_cidrs = ipnet_overlap(cnet, anet);
14            result.extend(overlap_cidrs);
15        }
16    }
17    result
18}
19
20/// 2つのIpNetの重複範囲をCIDRのリストで返す。
21/// 部分的にでも被っていればOK
22fn ipnet_overlap(a: &IpNet, b: &IpNet) -> Vec<IpNet> {
23    match (a, b) {
24        (IpNet::V4(a4), IpNet::V4(b4)) => ipv4_overlap(a4, b4),
25        (IpNet::V6(a6), IpNet::V6(b6)) => ipv6_overlap(a6, b6),
26        // IPv4 と IPv6 は重複しない
27        _ => Vec::new(),
28    }
29}
30
31/// IPv4同士の重複範囲を求めてCIDR列として返す
32fn ipv4_overlap(a: &Ipv4Net, b: &Ipv4Net) -> Vec<IpNet> {
33    let a_start = u32::from(a.network());
34    let a_end = u32::from(a.broadcast());
35    let b_start = u32::from(b.network());
36    let b_end = u32::from(b.broadcast());
37
38    let overlap_start = max(a_start, b_start);
39    let overlap_end = min(a_end, b_end);
40    if overlap_start > overlap_end {
41        return Vec::new();
42    }
43
44    ipv4_summarize_range(overlap_start, overlap_end)
45}
46
47/// IPv4用
48/// 開始～終了アドレスを最適なCIDRに分割
49fn ipv4_summarize_range(start: u32, end: u32) -> Vec<IpNet> {
50    let mut cidrs = Vec::new();
51    let mut current = start;
52
53    while current <= end {
54        let max_size = largest_ipv4_block_in_overlap(current, end);
55        if let Ok(net) = Ipv4Net::new(Ipv4Addr::from(current), max_size) {
56            cidrs.push(IpNet::V4(net));
57            let block_size = 1u32 << (32 - max_size);
58            current = current.saturating_add(block_size);
59        } else {
60            break;
61        }
62    }
63
64    cidrs
65}
66
67/// IPv4用
68/// 重複計算用の最大ブロックサイズ判定
69fn largest_ipv4_block_in_overlap(current: u32, end: u32) -> u8 {
70    let tz = current.trailing_zeros();
71    // Rust 1.67+ で使える標準ライブラリの ilog2() を利用
72    let span = (end - current + 1).ilog2();
73    let max_block = tz.min(span);
74    (32 - max_block) as u8
75}
76
77/// IPv6同士の重複範囲を求めてCIDR列として返す
78fn ipv6_overlap(a: &Ipv6Net, b: &Ipv6Net) -> Vec<IpNet> {
79    let a_start = ipv6_to_u128(a.network());
80    let a_end = ipv6_to_u128(a.broadcast());
81    let b_start = ipv6_to_u128(b.network());
82    let b_end = ipv6_to_u128(b.broadcast());
83
84    let overlap_start = max(a_start, b_start);
85    let overlap_end = min(a_end, b_end);
86    if overlap_start > overlap_end {
87        return Vec::new();
88    }
89
90    ipv6_summarize_range(overlap_start, overlap_end)
91}
92
93/// IPv6用
94/// 開始～終了アドレスを最適なCIDRに分割
95fn ipv6_summarize_range(start: u128, end: u128) -> Vec<IpNet> {
96    let mut cidrs = Vec::new();
97    let mut current = start;
98
99    while current <= end {
100        let max_size = largest_ipv6_block_in_overlap(current, end);
101        if let Ok(net) = Ipv6Net::new(Ipv6Addr::from(current), max_size) {
102            cidrs.push(IpNet::V6(net));
103            let block_size = 1u128 << (128 - max_size);
104            current = current.saturating_add(block_size);
105        } else {
106            break;
107        }
108    }
109
110    cidrs
111}
112
113/// IPv6用
114/// 重複計算用の最大ブロックサイズ判定
115fn largest_ipv6_block_in_overlap(current: u128, end: u128) -> u8 {
116    let tz = current.trailing_zeros() as u128;
117    // u128 用はまだ標準で ilog2() がないため、自前トレイトを使用
118    let span = (end - current + 1).ilog2_128();
119    let max_block = tz.min(span);
120    (128 - max_block) as u8
121}
122
123/// ヘルパー関数
124/// Ipv6Addrをu128に変換
125fn ipv6_to_u128(addr: Ipv6Addr) -> u128 {
126    u128::from_be_bytes(addr.octets())
127}
128
129/// u128用のilog2相当
130trait ILog2U128 {
131    fn ilog2_128(self) -> u128;
132}
133
134impl ILog2U128 for u128 {
135    fn ilog2_128(self) -> u128 {
136        if self == 0 {
137            0
138        } else {
139            127 - self.leading_zeros() as u128
140        }
141    }
142}
fire_scope/overlap.rs

fire_scope/
overlap.rs
