RIFT Auto-EVPN

/// indicates how many RRs we're computing in AUTO EVPN
pub const MAX_AUTO_EVPN_RRS: usize = 3;
/// indicates the fabric has no ID, used in computations to omit effects of fabric ID
pub const NO_FABRIC_ID: FabricIDType = 0;
/// invalid MACVRF number, MACVRFs start from 1
pub const NO_MACVRF: MACVRFNumberType = 0;
/// first MACVRF
pub const MIN_MACVRF : MACVRFNumberType  = 1;

/// unique v6 prefix for all nodes starts with this
pub fn auto_evpn_v6pref(fid: FabricIDType) -> String {
    format!("FD00:{:04X}:A1", fid)
}
/// how many bytes in a v6pref for different purposes
pub const AUTO_EVPN_V6PREFLEN: usize = 8 * 5;
/// unique v6 prefix for route reflector purposes starts like this
pub fn auto_evpn_v6rrpref(fid: FabricIDType) -> String {
    format!("FD00:{:04X}:A2", fid)
}
/// unique v6 prefix for type-5 purposes starts like this
pub fn auto_evpn_v6t5pref(fid: FabricIDType) -> String {
    format!("FD00:{:04X}:A3", fid)
}
/// unique v6 prefix for IRB prefix purposes
pub fn auto_evpn_v6irbpref(fid: FabricIDType) -> String {
    format!("FD00:{:04X}:A4", fid)
}
/// 2 bytes of prefix, then fabric ID, then another byte
pub const AUTO_EVPN_V6_FABPREFIXLEN: usize = 16 + 16 + 8;
/// unique v4 prefix for IRB purposes
pub const AUTO_EVPN_V4IRBPREF: &str = "10";

/// per RFC magic
const RT_TARGET_HIGH: CommunityType = 0;
const RT_TARGET_LOW: CommunityType = 0;

/// first available VLAN number
pub const FIRST_VLAN: UnsignedVLANIDType = 1;
// maximum vlan number one less than maximum to use as bitmask
pub const MAX_VLAN: UnsignedVLANIDType = 4095;
/// constant VLAN shift
pub const FIRST_VLAN_SHIFT: UnsignedVLANIDType = NATIVE_VLAN + 1;
/// NATIVE VLAN number
pub const NATIVE_VLAN: UnsignedVLANIDType = 1;

/// abstract description of VLAN properties for a derived VLAN
pub struct VLANDescription {
    pub vlan_id: UnsignedVLANIDType,
    pub name: String,
    /// can this VLAN be stretched across multiple fabrics
    pub stretchable: bool,
    pub native: bool,
}

/// maximum number of VLANs per MACVRF
pub const MAX_VLANS_PER_EVI: usize = 30;

/// maximum number of EVIs
pub const MAX_EVIS: MACVRFNumberType = 7;

pub type VLANStretchableType = bool;
pub type VLANNativeType = bool;

pub type UnsignedVNIType = u32;
pub type UnsignedFabricIDType = u16;

pub type UnsignedUnitType = u16;
pub type UnsignedVLANIDType = u16;

pub type UnsignedRTDistinguisherType = u64;

pub const EXTRATYPE5_RD_DISTINGUISHER: u32 = 0xffff_ffff;

/// high bits of type 5 VNI
const TYPE5VNIHIGH: UnsignedVNIType = 0x0080_0000;
/// bitmask for type 2 VNI
const TYPE2VNIMASK: UnsignedVNIType = 0x00ff_ffff ^ TYPE5VNIHIGH;

/// random seeds used in several algorithms to increase entropy
pub const RANDOMSEEDS: [u64; 4] = [
    27008318799u64,
    67438371571,
    37087353685,
    88675895388,
];

/// function sorts vector of (is_dci, systemID) first,
/// splits of the DCIs from the non-DCIs and sorts them
/// followed by a shuffle taking largest/smallest/2nd largest/2nd smallest.
/// Ultimately both are merged which prefers the DCIs while
/// still making sure that the election is stable with a system ID joining
/// as smallest/largest.
pub(crate) fn auto_evpn_sids2rrs(v: Vec<(bool, UnsignedSystemID)>)
    -> Vec<UnsignedSystemID> {
    let (dcis, nondcis): (Vec<(bool, UnsignedSystemID)>, Vec<(bool, UnsignedSystemID)>) =
        v.into_iter().partition(|(dci, _)| *dci);

    vec![dcis, nondcis]
        .into_iter()
        .flat_map(|mut v| {
            v.par_sort();
            if v.len() > 2 {
                let mut s = v.split_off(v.len() / 2);
                s.reverse();
                interleave(v.into_iter(), s.into_iter())
                    .collect::<Vec<_>>()
                    .into_iter()
            } else {
                v.into_iter()
            }
        })
        .map(|(_, sid)| sid)
        .collect()
}

pub(crate) fn auto_evpn_v62octets(a: Ipv6Addr) -> Vec<u8> {
    a.octets().iter().cloned().collect()
}

/// fabric prefixes derived instead of advertising default on the fabric to allow
/// for default route on ToF or leaves
pub fn auto_evpn_fid2fabric_prefixes(fid: FabricIDType) -> Result<Vec<IPPrefixType>, ServiceErrorType> {
    vec![
        (auto_evpn_fidsidv6loopback(fid, ILLEGAL_SYSTEM_I_D as _), AUTO_EVPN_V6PREFLEN),
        (auto_evpn_fidrrpref2rrloopback(fid, ILLEGAL_SYSTEM_I_D as _), AUTO_EVPN_V6PREFLEN),
    ]
        .into_iter()
        .map(|(p, _)|
            match p {
                Ok(_) => Ok(
                    IPPrefixType::Ipv6prefix(
                        IPv6PrefixType {
                            address: auto_evpn_v62octets(p?),
                            prefixlen: AUTO_EVPN_V6PREFLEN as _,
                        })),
                Err(e) => Err(e),
            }
        )
        .collect::<Result<Vec<_>, _>>()
}

/// local address with encoded fabric ID and system ID for collision free identifiers. Basis
/// for several different prefixes.
pub fn auto_evpn_v6prefixfidsid2loopback(v6pref: &str, fid: FabricIDType,
                                         sid: UnsignedSystemID) -> Result<Ipv6Addr, ServiceErrorType> {
    assert!(fid != UNDEFINED_FABRIC_ID);
    let a = format!("{}00::{}",
                    v6pref,
                    sid.to_ne_bytes()
                        .iter()
                        .chunks(2)
                        .into_iter()
                        .map(|chunk|
                            chunk.fold(0u16, |v, n| (v << 8) | *n as u16))
                        .map(|v| format!("{:04X}", v))
                        .collect::<Vec<_>>()
                        .into_iter()
                        .join(":")
    );

    Ipv6Addr::from_str(&a)
        .map_err(|_| ServiceErrorType::INTERNALRIFTERROR)
}

/// auto evpn V6 loopback for RRs
pub fn auto_evpn_fidrrpref2rrloopback(fid: FabricIDType,
                                      preference: u8) -> Result<Ipv6Addr, ServiceErrorType> {
    auto_evpn_v6prefixfidsid2loopback(&auto_evpn_v6rrpref(fid), fid, (1 + preference) as _)
}

/// auto evpn BGP router ID
pub fn auto_evpn_sidfid2bgpid(fid: FabricIDType, sid: UnsignedSystemID) -> u32 {
    assert!(fid != 0);
    let hs: u32 = ((sid & 0xffff_ffff_0000_0000) >> 32) as _;
    let mut ls: u32 = (sid & 0xffff_ffff) as _;
    ls = ls.rotate_right(7) ^ (fid as u32).rotate_right(13);
    max(1, hs ^ ls) // never a 0
}

/// route target bytes are type0/0 and then add EVI
pub fn auto_evpn_evi2rt(evi: MACVRFNumberType) -> CommunityType {
    let wideevi = (evi + 1) as CommunityType;

    (RT_TARGET_HIGH << (64 - 8)) | (RT_TARGET_LOW << 64 - 16) |
        ((wideevi) << 17) |
        ((wideevi))
}

/// type-5 VNI for an EVI
pub fn auto_evpn_fidevi2type5vni(fid: FabricIDType, evi: MACVRFNumberType) -> UnsignedVNIType {
    TYPE5VNIHIGH | auto_evpn_fidevivid2vni(fid, evi, 0, false)
}

/// type-2 VNI for a specific VLAN
pub fn auto_evpn_fidevivid2vni(fid: FabricIDType, evi: MACVRFNumberType, vlanid: VLANIDType, stretchable: bool) -> UnsignedVNIType {
    let rfid = if stretchable {
        NO_FABRIC_ID as _
    } else {
        fid as UnsignedVNIType
    };

    let revi = evi as UnsignedVNIType;
    let rvlan = vlanid as UnsignedVNIType;
// mask out high bits, VNI is only 24 bits
    TYPE2VNIMASK &
        (
            rfid.rotate_left(16) ^
                revi.rotate_left(12) ^
                rvlan
        )
}

/// maximum VLANs per EVI supported by auto evpn when deriving
pub fn auto_evpn_vlan_description_table<'a>(vlans: usize)
                                            -> Result<&'a [(UnsignedVLANIDType, VLANStretchableType, VLANNativeType)], ServiceErrorType> {
    // up to 15 vlans can be activated
    const VLANSARRAY: [(UnsignedVLANIDType, bool, bool); MAX_VLANS_PER_EVI] = [
        (NATIVE_VLAN, true, true, ),
        (FIRST_VLAN_SHIFT, true, false, ),
        (FIRST_VLAN_SHIFT + 1, true, false, ),
        (FIRST_VLAN_SHIFT + 2, true, false, ),
        (FIRST_VLAN_SHIFT + 3, true, false, ),
        (FIRST_VLAN_SHIFT + 4, true, false, ),
        (FIRST_VLAN_SHIFT + 5, true, false, ),
        (FIRST_VLAN_SHIFT + 6, true, false, ),
        (FIRST_VLAN_SHIFT + 7, true, false, ),
        (FIRST_VLAN_SHIFT + 8, false, false, ),
        (FIRST_VLAN_SHIFT + 9, false, false, ),
        (FIRST_VLAN_SHIFT +10, false, false, ),
        (FIRST_VLAN_SHIFT +11, false, false, ),
        (FIRST_VLAN_SHIFT +12, false, false, ),
        (FIRST_VLAN_SHIFT +13, false, false, ),
        (FIRST_VLAN_SHIFT +14, false, false, ),
        (FIRST_VLAN_SHIFT +15, false, false, ),
        (FIRST_VLAN_SHIFT +16, false, false, ),
        (FIRST_VLAN_SHIFT +17, false, false, ),
        (FIRST_VLAN_SHIFT +18, false, false, ),
        (FIRST_VLAN_SHIFT +19, false, false, ),
        (FIRST_VLAN_SHIFT +20, false, false, ),
        (FIRST_VLAN_SHIFT +21, false, false, ),
        (FIRST_VLAN_SHIFT +22, false, false, ),
        (FIRST_VLAN_SHIFT +23, false, false, ),
        (FIRST_VLAN_SHIFT +24, false, false, ),
        (FIRST_VLAN_SHIFT +25, false, false, ),
        (FIRST_VLAN_SHIFT +26, false, false, ),
        (FIRST_VLAN_SHIFT +27, false, false, ),
        (FIRST_VLAN_SHIFT +28, false, false, ),
    ];

    if vlans > VLANSARRAY.len() {
        return Err(ServiceErrorType::INVALIDPARAMETERVALUE)
    }

    Ok(&VLANSARRAY[..vlans])
}

const fn num_bits<T>() -> usize { std::mem::size_of::<T>() * 8 }

fn log2(x: u32) -> u32 {
    assert!(x > 0);
    num_bits::<u32>() as u32 - x.leading_zeros() - 1
}

/// delivers the vlan description that can be used to generate vlans for a
/// specific fabric ID and a MACVRF number
pub fn auto_evpn_fidevivlansvlans2desc(fid: UnsignedFabricIDType, macvrf: MACVRFNumberType,
                                       vlans: usize) -> Vec<VLANDescription> {
    assert!(NO_MACVRF != macvrf);

    // abstract description of derived VLANs
    let vlan_table = auto_evpn_vlan_description_table(vlans)
        .expect("vlan table in AUTO EVPN incorrect");

    let vlanshift = log2(vlan_table
        .iter()
        .map(|(vl, _, _)| *vl as usize)
        .max()
        .expect("vlan table in AUTO EVPN incorrect")
        .checked_next_power_of_two()
        .expect("vlan table in AUTO EVPN incorrect")
        as u32);

    vlan_table
        .iter()
        .map(move |(vid, stretch, native_)| {
            let stretchedfid = if !stretch {
                fid
            } else {
                NO_FABRIC_ID as _
            };

            let reducedmacvrf = macvrf - MIN_MACVRF;

            // we shift fid & evi same amount to extinguish them possibly
            let fidandevishift = vlanshift + 1;
            let mut vlan_id = *vid ^ stretchedfid
                .rotate_left(fidandevishift) as UnsignedVLANIDType;
            // leave space for VLANs in the encoding
            vlan_id ^= reducedmacvrf.rotate_left(fidandevishift) as UnsignedVLANIDType;

            vlan_id %= MAX_VLAN;
            vlan_id = max(1, vlan_id);

            VLANDescription {
                vlan_id: vlan_id as _,
                name: format!("V{}", vlan_id),
                stretchable: *stretch,
                native: *native_,
            }
        })
        .collect()
}

/// IRB interface number.
/// fid/evi combination shifted up to not interfere with the VLAN-ID
/// and then add the VLAN-ID
pub fn auto_evpn_fidevivid2irb(_fid: FabricIDType, _evi: MACVRFNumberType, vid: VLANIDType) -> UnsignedUnitType {

    assert!(NO_MACVRF != _evi);

    // VLAN collision function is collision free to the point we can just ignore EVI
    // and assign IRB interface number to be same as VLAN which simplifies deployment
    let mut v: UnsignedUnitType = 0;

    v = v.wrapping_add(vid as UnsignedVLANIDType);
    max(1, v % (UnsignedUnitType::MAX - 1))
}

/// route distinguisher derivation
pub fn auto_evpn_sidfid2rd(sid: UnsignedSystemID, fid: UnsignedFabricIDType, extra: u32) -> UnsignedRTDistinguisherType {
    // generate type 0 route distinguisher, first 2 bytes 0 and then 6 bytes
    assert!(fid != NO_FABRIC_ID as _);
    // shift the 2 bytes we loose
    let convsid = sid as UnsignedRTDistinguisherType;
    let hs = ((sid & 0xffff_0000_0000_0000) >> 32) as UnsignedRTDistinguisherType;
    let mut ls: UnsignedRTDistinguisherType = convsid & 0x0000_ffff_ffff_ffff;
    ls ^= hs;
    ls ^= (fid as UnsignedRTDistinguisherType).rotate_left(16);
    ls ^= extra as UnsignedRTDistinguisherType;
    ls
}

/// v4 subnet derivation
pub fn auto_evpn_v4prefixfidevividsid2v4subnet(v4pref: &str, fid: FabricIDType,
                                               evi: MACVRFNumberType, vid: VLANIDType,
                                               sid: UnsignedSystemID) -> Result<IPv4PrefixType, ServiceErrorType> {

    assert!(NO_MACVRF != evi);

    // fid can be 0 for stretched v4subnets
    let mut sub = evi.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[0] & 0xff) as u8, |r, e| r.rotate_left(1) ^ e.rotate_right(1));
    sub ^= fid.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[1] & 0xff) as u8, |r, e| r.rotate_left(2) ^ e.rotate_right(1));
    sub ^= vid.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[2] & 0xff) as u8, |r, e| r.rotate_left(3) ^ e.rotate_right(1));

    let subnet = sub % 254; // make sure we don't show multicast subnet

    let _host = sid.to_ne_bytes().iter()
        .fold(0u16, |r, e| r.rotate_left(3) ^ e.rotate_right(3) as u16);

    let a = format!("{}.{}.{}.{}",
                    v4pref,
                    subnet,
                    0,
                    1,
    );

    Ok(
        IPv4PrefixType {
            address: Ipv4Addr::from_str(&a)
                .map_err(|_| {
                    ServiceErrorType::INTERNALRIFTERROR
                })?
                .octets()
                .iter()
                .fold(0u32, |v, nv| v << 8 | (*nv as u32)) as IPv4Address
            ,
            prefixlen: 16,
        }
    )
}

/// generic v6 bytes derivation used for different purposes
pub fn auto_evpn_v6hash(fid: FabricIDType, evi: MACVRFNumberType, vid: VLANIDType, sid: UnsignedSystemID)
                        -> [u8; 8] {

    let mut sub = evi.to_ne_bytes().iter()
        .fold(RANDOMSEEDS[3], |r, e| r.rotate_left(6) ^ e.rotate_right(4) as u64);
    sub ^= fid.to_ne_bytes().iter()
        .fold(RANDOMSEEDS[0], |r, e| r.rotate_left(6) ^ e.rotate_right(4) as u64);
    sub ^= vid as u64;
    sub ^= sid;

    sub.to_ne_bytes()
}

/// v6 subnet derivation
pub fn auto_evpn_fidevividsid2v6subnet(fid: FabricIDType, evi: MACVRFNumberType,
                                       vid: VLANIDType,
                                       sid: UnsignedSystemID) -> Result<IPv6PrefixType, ServiceErrorType> {

    assert!(NO_MACVRF != evi);

    let sb = auto_evpn_v6hash(fid, evi, vid, sid);

    let a = format!("{}:{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}::1",
                    auto_evpn_v6irbpref(fid),
                    sb[3] ^ sb[0],
                    sb[4] ^ sb[1],
                    sb[6],
                    sb[7],
                    sb[5],
                    sb[2],
    );

    Ok(IPv6PrefixType {
        address: Ipv6Addr::from_str(
            &a)
            .map_err(|_| {
                ServiceErrorType::INTERNALRIFTERROR
            })?
            .octets()
            .to_vec(),
        prefixlen: 64,
    })
}

/// MAC address derivation for IRB
pub fn auto_evpn_fidevividsid2mac(fid: FabricIDType, evi: MACVRFNumberType,
                                  vid: VLANIDType, sid: UnsignedSystemID) -> Vec<u8> {

    let sb = auto_evpn_v6hash(fid, evi, vid, sid);

    vec![0x02,
         sb[3] ^ sb[0],
         sb[4] ^ sb[1],
         sb[6],
         sb[7],
         sb[5] ^ sb[2],
    ]
}

/// v4 loopback address derivation for every node in auto-evpn, returns address and
/// subnet mask length
pub fn auto_evpn_fidsid2v4loopback(fid: FabricIDType, sid: UnsignedSystemID) -> (IPv4Address, u8) {
    let mut derived = sid.to_ne_bytes().iter()
        .fold(0 as IPv4Address, |p, e| (p << 4) ^ (*e as IPv4Address));
    derived ^= fid as IPv4Address;
    // use the byte we loose for entropy
    derived ^= derived >> 24;
    // and sanitize for loopback range, we nuke 9 bits out
    derived &= 0x007f_ffff;

    let m = ((127 as IPv4Address) << 24) | derived;
    (m as _, 9)
}

/// V6 loopback derivation for every node in auto-evpn
pub fn auto_evpn_fidsidv6loopback(fid: FabricIDType,
                                  sid: UnsignedSystemID) -> Result<Ipv6Addr, ServiceErrorType> {
    auto_evpn_v6prefixfidsid2loopback(&auto_evpn_v6pref(fid), fid, sid)
}

#[allow(non_snake_case)]
pub fn auto_evpn_fid2private_AS(fid: FabricIDType) -> u32 {
    assert!(fid != NO_FABRIC_ID);
    // range 4200000000-4294967294
    const DIFF: u32 = 4_294_967_294 - 4_200_000_000;
    64496 + ((fid as u32) << 3) % DIFF
}

pub fn auto_evpn_fid2clusterid(fid: FabricIDType) -> u32 {
    auto_evpn_fid2private_AS(fid)
}