rtable/
prefix.rs

1//
2// Routing Table
3//   Copyright (C) 2019,2020 Toshiaki Takada
4//
5// IP Prefix - abstract IPv? address and prefix length.
6//
7
8use std::net::Ipv4Addr;
9use std::net::Ipv6Addr;
10use std::str::FromStr;
11use std::hash::Hash;
12use std::error::Error;
13use std::fmt;
14    
15const IPV4_BIT_LENGTH: u8 = 32;
16const IPV6_BIT_LENGTH: u8 = 128;
17
18///
19/// Trait Addressable to extend IpAddr.
20///
21pub trait Addressable
22where Self: Clone,
23      Self: FromStr,
24      Self: ToString,
25      Self: Hash,
26      Self: Eq,
27      Self: fmt::Debug,
28{
29    /// Return address bit length.
30    fn bit_len() -> u8;
31
32    /// Return address byte length.
33    fn byte_len() -> u8 {
34        Self::bit_len() / 8
35    }
36
37    /// Construct address with all 0s.
38    fn empty_new() -> Self;
39
40    /// Construct address from slice.
41    fn from_slice(s: &[u8]) -> Self;
42
43    /// Return reference of slice to address.
44    fn octets_ref(&self) -> &[u8];
45}
46
47/// Trait implementation for Ipv4Addr.
48impl Addressable for Ipv4Addr {
49
50    /// Return address bit length.
51    fn bit_len() -> u8 {
52        IPV4_BIT_LENGTH
53    }
54
55    /// Construct address with all 0s.
56    fn empty_new() -> Self {
57        Ipv4Addr::UNSPECIFIED
58    }
59
60    /// Construct address from slice.
61    fn from_slice(s: &[u8]) -> Self {
62        let t: [u8; 4] = [s[0], s[1], s[2], s[3]];
63
64        Ipv4Addr::from(t)
65    }
66
67    /// Return reference of slice to address.
68    fn octets_ref(&self) -> &[u8] {
69        let p = (self as *const Ipv4Addr) as *const u8;
70        unsafe {
71            std::slice::from_raw_parts(p, std::mem::size_of::<Ipv4Addr>())
72        }
73    }
74}
75
76/// Trait implementation for Ipv6Addr.
77impl Addressable for Ipv6Addr {
78
79    /// Return address bit length.
80    fn bit_len() -> u8 {
81        IPV6_BIT_LENGTH
82    }
83
84    /// Construct address with all 0s.
85    fn empty_new() -> Self {
86        Ipv6Addr::UNSPECIFIED
87    }
88
89    /// Construct address from slice.
90    fn from_slice(s: &[u8]) -> Self {
91        let t: [u8; 16] = [s[0], s[1], s[2], s[3], s[4], s[5], s[6], s[7],
92                           s[8], s[9], s[10], s[11], s[12], s[13], s[14], s[15]];
93
94        Ipv6Addr::from(t)
95    }
96
97    /// Return reference of slice to address.
98    fn octets_ref(&self) -> &[u8] {
99        let p = (self as *const Ipv6Addr) as *const u8;
100        unsafe {
101            std::slice::from_raw_parts(p, std::mem::size_of::<Ipv4Addr>())
102        }
103    }
104}
105
106///
107/// Trait Prefixable.
108///
109pub trait Prefixable {
110
111    /// Construct a prefix from given prefix.
112    fn from_prefix(p: &Self) -> Self;
113
114    /// Construct a prefix from common parts of two prefixes.
115    fn from_common(prefix1: &Self, prefix2: &Self) -> Self;
116
117    /// Return prefix length.
118    fn len(&self) -> u8;
119
120    /// Return 0 or 1 at certain position of bit in the prefix.
121    fn bit_at(&self, index: u8) -> u8 {
122        let offset = index / 8;
123        let shift = 7 - (index % 8);
124        let octets = self.octets();
125
126        (octets[offset as usize] >> shift) & 0x1
127    }
128
129    /// Return reference of slice to address.
130    fn octets(&self) -> &[u8];
131
132    /// Return mutable reference of slice to address.
133    fn octets_mut(&mut self) -> &mut [u8];
134
135    /// Return true if given prefix is included in this prefix.
136    fn contains(&self, prefix: &Self) -> bool {
137        if self.len() > prefix.len() {
138            return false
139        }
140
141        let np = self.octets();
142        let pp = prefix.octets();
143
144        let mut offset: usize = self.len() as usize / 8;
145        let shift: usize = self.len() as usize % 8;
146
147        if shift > 0 {
148            if (MASKBITS[shift] & (np[offset] ^ pp[offset])) > 0 {
149                return false
150            }
151        }
152
153        while offset > 0 {
154            offset -= 1;
155            if np[offset] != pp[offset] {
156                return false
157            }
158        }
159
160        return true
161    }
162}
163
164///
165/// Bitmask utilities.
166///
167const PLEN2MASK: [[u8; 4]; 32] = [
168    [0x00, 0x00, 0x00, 0x00],
169    [0x80, 0x00, 0x00, 0x00],
170    [0xc0, 0x00, 0x00, 0x00],
171    [0xe0, 0x00, 0x00, 0x00],
172    [0xf0, 0x00, 0x00, 0x00],
173    [0xf8, 0x00, 0x00, 0x00],
174    [0xfc, 0x00, 0x00, 0x00],
175    [0xfe, 0x00, 0x00, 0x00],
176
177    [0xff, 0x00, 0x00, 0x00],
178    [0xff, 0x80, 0x00, 0x00],
179    [0xff, 0xc0, 0x00, 0x00],
180    [0xff, 0xe0, 0x00, 0x00],
181    [0xff, 0xf0, 0x00, 0x00],
182    [0xff, 0xf8, 0x00, 0x00],
183    [0xff, 0xfc, 0x00, 0x00],
184    [0xff, 0xfe, 0x00, 0x00],
185
186    [0xff, 0xff, 0x00, 0x00],
187    [0xff, 0xff, 0x80, 0x00],
188    [0xff, 0xff, 0xc0, 0x00],
189    [0xff, 0xff, 0xe0, 0x00],
190    [0xff, 0xff, 0xf0, 0x00],
191    [0xff, 0xff, 0xf8, 0x00],
192    [0xff, 0xff, 0xfc, 0x00],
193    [0xff, 0xff, 0xfe, 0x00],
194
195    [0xff, 0xff, 0xff, 0x00],
196    [0xff, 0xff, 0xff, 0x80],
197    [0xff, 0xff, 0xff, 0xc0],
198    [0xff, 0xff, 0xff, 0xe0],
199    [0xff, 0xff, 0xff, 0xf0],
200    [0xff, 0xff, 0xff, 0xf8],
201    [0xff, 0xff, 0xff, 0xfc],
202    [0xff, 0xff, 0xff, 0xfe],
203];
204
205const PLEN2MASK6: [u16; 16] = [
206    0x0000,
207    0x8000,
208    0xc000,
209    0xe000,
210    0xf000,
211    0xf800,
212    0xfc00,
213    0xfe00,
214
215    0xff00,
216    0xff80,
217    0xffc0,
218    0xffe0,
219    0xfff0,
220    0xfff8,
221    0xfffc,
222    0xfffe,
223];
224
225const MASKBITS: [u8; 9] = [
226    0x00, 0x80, 0xc0, 0xe0,
227    0xf0, 0xf8, 0xfc, 0xfe, 0xff
228];
229
230/// Get 4 u8 values from slices and return u32 in network byte order.
231fn slice_get_u32(s: &[u8], i: usize) -> u32 {
232    ((s[i] as u32) << 24) | ((s[i + 1] as u32) << 16) | ((s[i + 2] as u32) << 8) | s[i + 3] as u32
233}
234
235/// Copy u32 value to slice.
236fn slice_copy_u32(s: &mut [u8], v: u32, i: usize) {
237    s[i + 0] = ((v >> 24) & 0xFF) as u8;
238    s[i + 1] = ((v >> 16) & 0xFF) as u8;
239    s[i + 2] = ((v >> 8) & 0xFF) as u8;
240    s[i + 3] = (v & 0xFF) as u8;
241}
242
243///
244/// IP Prefix.
245///
246#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
247pub struct Prefix<T: Addressable> {
248
249    // IP Address.
250    address: T,
251
252    // Prefix Length.
253    len: u8,
254}
255
256
257impl<T: Addressable> Prefixable for Prefix<T> {
258
259    /// Construct a prefix from given prefix.
260    fn from_prefix(p: &Self) -> Self {
261        Self {
262            address: p.address.clone(),
263            len: p.len
264        }
265    }
266
267    /// Construct a prefix from common parts of two prefixes, assuming p1 is shorter than p2.
268    fn from_common(prefix1: &Self, prefix2: &Self) -> Self {
269        let p1 = prefix1.octets();
270        let p2 = prefix2.octets();
271        let mut i = 0u8;
272        let mut j = 0u8;
273        let mut pcommon = Self { address: T::empty_new(), len: 0 };
274        let px = pcommon.octets_mut();
275        let bytes = T::bit_len() / 8;
276
277        while i < bytes {
278            let l1: u32 = slice_get_u32(p1, i as usize);
279            let l2: u32 = slice_get_u32(p2, i as usize);
280            let cp: u32 = l1 ^ l2;
281            if cp == 0 {
282                slice_copy_u32(px, l1, i as usize);
283            }
284            else {
285                j = cp.leading_zeros() as u8;
286                let (mask, _) = match j {
287                    0 => (0, false),
288                    _ => 0xFFFFFFFFu32.overflowing_shl((32 - j) as u32),
289                };
290                let v = l1 & (mask as u32);
291
292                slice_copy_u32(px, v, i as usize);
293                break;
294            }
295
296            i += 4;
297        }
298
299        pcommon.len = if prefix2.len() > i * 8 + j {
300            i * 8 + j
301        } else {
302            prefix2.len()
303        };
304
305        pcommon
306    }
307
308    /// Return prefix length.
309    fn len(&self) -> u8 {
310        self.len
311    }
312
313    /// Return reference of slice to address.
314    fn octets(&self) -> &[u8] {
315        let p = (&self.address as *const T) as *const u8;
316        unsafe {
317            std::slice::from_raw_parts(p, std::mem::size_of::<T>())
318        }
319    }
320
321    /// Return mutable reference of slice to address.
322    fn octets_mut(&mut self) -> &mut [u8] {
323        let p = (&mut self.address as *mut T) as *mut u8;
324        unsafe {
325            std::slice::from_raw_parts_mut(p, std::mem::size_of::<T>())
326        }
327    }
328}
329
330///
331/// Abstract IPv4 and IPv6 both.
332///
333impl<T: Addressable> Prefix<T>
334{
335
336    /// Construct empty prefix.
337    pub fn new() -> Self {
338        Self {
339            address: T::empty_new(),
340            len: 0,
341        }
342    }
343
344    /// Construct a prefix from an address and prefix length.
345    pub fn from(address: T, len: u8) -> Self {
346        Self {
347            address: address,
348            len: len,
349        }
350    }
351
352    /// Construct a prefix from address and prefix length.
353    pub fn from_slice(slice: &[u8], prefix_len: u8) -> Self{
354        Self {
355            address: T::from_slice(slice),
356            len: prefix_len,
357        }
358    }
359
360    /// Construct prefix from string slice.
361    pub fn from_str(s: &str) -> Result<Prefix<T>, PrefixParseError> {
362        let (pos, prefix_len) = match s.find('/') {
363            // Address with prefix length.
364            Some(pos) => {
365                match s[pos + 1..].parse::<u8>() {
366                    Ok(prefix_len) if prefix_len <= T::bit_len() => (pos, prefix_len),
367                    _ => return Err(PrefixParseError(())),
368                }
369            },
370            // Consider host address.
371            None => (s.len(), T::bit_len()),
372        };
373                    
374        let address_str = &s[..pos];
375        match T::from_str(address_str) {
376            Ok(address) =>
377                Ok(Prefix::<T> {
378                    address: address,
379                    len: prefix_len,
380                }),
381            Err(_) => Err(PrefixParseError(())),
382        }
383    }
384
385    /// Return address part of prefix.
386    pub fn address(&self) -> &T {
387        &self.address
388    }
389}
390
391/// Impl IPv4 Prefix.
392impl Prefix<Ipv4Addr> {
393    /// Apply network mask to address part.
394    pub fn apply_mask(&mut self) {
395        if self.len < Ipv4Addr::bit_len() {
396            let octets = self.address().octets();
397            let mask = &PLEN2MASK[self.len as usize];
398            self.address = Ipv4Addr::new(octets[0] & mask[0],
399                                         octets[1] & mask[1],
400                                         octets[2] & mask[2],
401                                         octets[3] & mask[3]);
402        }
403    }
404}
405
406/// Impl IPv6 Prefix.
407impl Prefix<Ipv6Addr> {
408    /// Apply network mask to address part.
409    pub fn apply_mask(&mut self) {
410        fn mask4segment(s: u8, len: u8) -> u16 {
411            if len >= s * 16 {
412                let offset = len - s * 16;
413                if offset >= 16 {
414                    0xffff
415                }
416                else {
417                    PLEN2MASK6[offset as usize]
418                }
419            }
420            else {
421                0
422            }
423        }
424
425        if self.len < Ipv6Addr::bit_len() {
426            let segments = self.address().segments();
427            self.address = Ipv6Addr::new(segments[0] & mask4segment(0, self.len),
428                                         segments[1] & mask4segment(1, self.len),
429                                         segments[2] & mask4segment(2, self.len),
430                                         segments[3] & mask4segment(3, self.len),
431                                         segments[4] & mask4segment(4, self.len),
432                                         segments[5] & mask4segment(5, self.len),
433                                         segments[6] & mask4segment(6, self.len),
434                                         segments[7] & mask4segment(7, self.len));
435        }
436    }
437}
438
439impl<T: Addressable> fmt::Display for Prefix<T>
440{
441    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
442        write!(fmt, "{}/{}", self.address.to_string(), self.len)
443    }
444}
445
446/// Utility functions.
447pub fn prefix_ipv4_from(addr_str: &str, mask_str: &str) -> Result<Prefix<Ipv4Addr>, PrefixParseError> {
448    match Ipv4Addr::from_str(addr_str) {
449        Err(_) => Err(PrefixParseError(())),
450        Ok(addr) => {
451            match Ipv4Addr::from_str(mask_str) {
452                Err(_) => Err(PrefixParseError(())),
453                Ok(mask) => {
454                    let mask = u32::from(mask);
455                    Ok(Prefix::<Ipv4Addr>::from(addr, (32 - mask.trailing_zeros()) as u8))
456                },
457            }
458        }
459    }
460}
461
462///
463/// Prefix Parse Error.
464///
465#[derive(Debug, Clone, PartialEq, Eq)]
466pub struct PrefixParseError(());
467
468impl fmt::Display for PrefixParseError {
469    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
470        fmt.write_str(self.description())
471    }
472}
473
474impl Error for PrefixParseError {
475    fn description(&self) -> &str {
476        "invalid IP prefix syntax"
477    }
478}
479
480///
481/// Unit tests for Prefix.
482///
483#[cfg(test)]
484mod tests {
485    use std::collections::BTreeMap;
486    use super::*;
487
488    #[test]
489    pub fn test_octets() {
490        let p = Prefix::<Ipv4Addr>::from_str("1.2.3.4/24").unwrap();
491        let o = p.octets();
492        assert_eq!(o, &[1, 2, 3, 4]);
493
494        let p = Prefix::<Ipv6Addr>::from_str("2001:1:2::7:8/48").unwrap();
495        let o = p.octets();
496        assert_eq!(o, &[0x20, 1, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8]);
497    }
498
499    #[test]
500    pub fn test_prefix_ipv4() {
501        let p = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
502        assert_eq!(p.address().octets(), [10, 10, 10, 0]);
503        assert_eq!(p.to_string(), "10.10.10.0/24");
504
505        let p = Prefix::<Ipv4Addr>::from_str("1.2.3.4").unwrap();
506        assert_eq!(p.address().octets(), [1, 2, 3, 4]);
507        assert_eq!(p.to_string(), "1.2.3.4/32");
508
509        let mut p = Prefix::<Ipv4Addr>::from_str("1.2.3.4/24").unwrap();
510        assert_eq!(p.address().octets(), [1, 2, 3, 4]);
511        assert_eq!(p.to_string(), "1.2.3.4/24");
512        p.apply_mask();
513        assert_eq!(p.address().octets(), [1, 2, 3, 0]);
514        assert_eq!(p.to_string(), "1.2.3.0/24");
515
516        let mut p = Prefix::<Ipv4Addr>::from_str("172.16.0.1/16").unwrap();
517        assert_eq!(p.address().octets(), [172, 16, 0, 1]);
518        assert_eq!(p.to_string(), "172.16.0.1/16");
519        p.apply_mask();
520        assert_eq!(p.address().octets(), [172, 16, 0, 0]);
521        assert_eq!(p.to_string(), "172.16.0.0/16");
522
523        let p = Prefix::<Ipv4Addr>::from_slice(&[172, 16, 0, 1], 24);
524        assert_eq!(p.to_string(), "172.16.0.1/24");
525
526        match Prefix::<Ipv4Addr>::from_str("10.10.10.10/33") {
527            Ok(_) => assert!(false, "Should return error"),
528            Err(_err) => { }
529        }
530    }
531
532    #[test]
533    pub fn test_prefix_ipv4_common() {
534        let p1 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
535        let p2 = Prefix::<Ipv4Addr>::from_str("10.10.11.0/24").unwrap();
536        let pc = Prefix::<Ipv4Addr>::from_common(&p1, &p2);
537        assert_eq!(pc.to_string(), "10.10.10.0/23");
538
539        let p1 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
540        let p2 = Prefix::<Ipv4Addr>::from_str("10.10.0.0/16").unwrap();
541        let pc = Prefix::<Ipv4Addr>::from_common(&p1, &p2);
542        assert_eq!(pc.to_string(), "10.10.0.0/16");
543
544        let p1 = Prefix::<Ipv4Addr>::from_str("192.168.0.0/24").unwrap();
545        let p2 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
546        let pc = Prefix::<Ipv4Addr>::from_common(&p1, &p2);
547        assert_eq!(pc.to_string(), "0.0.0.0/0");
548
549        let p1 = Prefix::<Ipv4Addr>::from_str("192.168.0.0/24").unwrap();
550        let p2 = Prefix::<Ipv4Addr>::from_str("128.10.10.0/24").unwrap();
551        let pc = Prefix::<Ipv4Addr>::from_common(&p1, &p2);
552        assert_eq!(pc.to_string(), "128.0.0.0/1");
553    }
554
555    #[test]
556    pub fn test_prefix_ipv4_sort() {
557        let mut map = BTreeMap::new();
558
559        let p1 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
560        let p2 = Prefix::<Ipv4Addr>::from_str("10.10.11.0/24").unwrap();
561        let p3 = Prefix::<Ipv4Addr>::from_common(&p1, &p2);
562        //assert_eq!(pc.to_string(), "10.10.10.0/23");
563
564        let p4 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
565        let p5 = Prefix::<Ipv4Addr>::from_str("10.10.0.0/16").unwrap();
566        let p6 = Prefix::<Ipv4Addr>::from_common(&p4, &p5);
567        //assert_eq!(pc.to_string(), "10.10.0.0/16");
568
569        let p7 = Prefix::<Ipv4Addr>::from_str("192.168.0.0/24").unwrap();
570        let p8 = Prefix::<Ipv4Addr>::from_str("10.10.10.0/24").unwrap();
571        let p9 = Prefix::<Ipv4Addr>::from_common(&p7, &p8);
572        //assert_eq!(pc.to_string(), "0.0.0.0/0");
573
574        let p10 = Prefix::<Ipv4Addr>::from_str("192.168.0.0/24").unwrap();
575        let p11 = Prefix::<Ipv4Addr>::from_str("128.10.10.0/24").unwrap();
576        let p12 = Prefix::<Ipv4Addr>::from_common(&p10, &p11);
577        //assert_eq!(pc.to_string(), "128.0.0.0/1");
578
579        map.insert(p1, 1);
580        map.insert(p2, 2);
581        map.insert(p3, 3);
582
583        map.insert(p5, 5);
584
585        map.insert(p7, 7);
586
587        map.insert(p9, 9);
588
589        map.insert(p11, 11);
590        map.insert(p12, 12);
591
592        let v: Vec<_> = map.iter().map(|(k, v)| v).collect();
593        assert_eq!(v, vec![&9, &5, &3, &1, &2, &12, &11, &7]);
594    }
595
596    #[test]
597    pub fn test_prefix_ipv6() {
598        let p = Prefix::<Ipv6Addr>::from_str("::/0").unwrap();
599        assert_eq!(p.address().segments(), [0, 0, 0, 0, 0, 0, 0, 0]);
600        assert_eq!(p.to_string(), "::/0");
601
602        let p = Prefix::<Ipv6Addr>::from_str("2001:1234::/48").unwrap();
603        assert_eq!(p.address().segments(), [0x2001, 0x1234, 0, 0, 0, 0, 0, 0]);
604        assert_eq!(p.to_string(), "2001:1234::/48");
605
606        let mut p = Prefix::<Ipv6Addr>::from_str("2001:1234::567/48").unwrap();
607        assert_eq!(p.address().segments(), [0x2001, 0x1234, 0, 0, 0, 0, 0, 0x567]);
608        assert_eq!(p.to_string(), "2001:1234::567/48");
609        p.apply_mask();
610        assert_eq!(p.address().segments(), [0x2001, 0x1234, 0, 0, 0, 0, 0, 0]);
611        assert_eq!(p.to_string(), "2001:1234::/48");
612
613        let mut p = Prefix::<Ipv6Addr>::from_str("2001:1234::ffff/124").unwrap();
614        p.apply_mask();
615        assert_eq!(p.address().segments(), [0x2001, 0x1234, 0, 0, 0, 0, 0, 0xfff0]);
616        assert_eq!(p.to_string(), "2001:1234::fff0/124");
617
618        let mut p = Prefix::<Ipv6Addr>::from_str("2001:1234::ffff/120").unwrap();
619        p.apply_mask();
620        assert_eq!(p.address().segments(), [0x2001, 0x1234, 0, 0, 0, 0, 0, 0xff00]);
621        assert_eq!(p.to_string(), "2001:1234::ff00/120");
622
623        let p = Prefix::<Ipv6Addr>::from_slice(&[0x20, 0x01, 0x12, 0x34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 48);
624        assert_eq!(p.to_string(), "2001:1234::/48");
625
626        match Prefix::<Ipv6Addr>::from_str("2001:1234::/130") {
627            Ok(_) => assert!(false, "Should return error"),
628            Err(_err) => { }
629        }
630    }
631}
rtable/prefix.rs

rtable/
prefix.rs
