mdns_sd/

dns_parser.rs

//! DNS parsing utility.
//!
//! [DnsIncoming] is the logic representation of an incoming DNS packet.
//! [DnsOutgoing] is the logic representation of an outgoing DNS message of one or more packets.
//! [DnsOutPacket] is the encoded one packet for [DnsOutgoing].

#[cfg(feature = "logging")]
use crate::log::{debug, trace};

use crate::current_time_millis;
use crate::error::{e_fmt, Error, Result};
use crate::service_info::{is_unicast_link_local, DnsRegistry, MyIntf, ServiceInfo};

use if_addrs::Interface;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

use std::{
    any::Any,
    cmp,
    collections::HashMap,
    convert::TryInto,
    fmt,
    hash::Hash,
    net::{IpAddr, Ipv4Addr, Ipv6Addr},
    str,
};

/// Represents a network interface identifier defined by the OS.
#[derive(Clone, Debug, Eq, Hash, PartialEq, Default)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
pub struct InterfaceId {
    /// Interface name, e.g. "en0", "wlan0", etc.
    pub name: String,

    /// Interface index assigned by the OS, e.g. 1, 2, etc.
    pub index: u32,
}

impl InterfaceId {
    /// Returns all IP addresses associated with this interface by querying the OS.
    pub fn get_addrs(&self) -> Vec<IpAddr> {
        if_addrs::get_if_addrs()
            .unwrap_or_default()
            .into_iter()
            .filter(|iface| iface.index == Some(self.index))
            .map(|iface| iface.ip())
            .collect()
    }
}

impl fmt::Display for InterfaceId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}('{}')", self.index, self.name)
    }
}

impl From<&Interface> for InterfaceId {
    fn from(interface: &Interface) -> Self {
        InterfaceId {
            name: interface.name.clone(),
            index: interface.index.unwrap_or_default(),
        }
    }
}

/// An IPv4 address with interface identifiers indicating which interfaces discovered it.
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
pub struct ScopedIpV4 {
    addr: Ipv4Addr,
    /// The interfaces this address was discovered on.
    interface_ids: Vec<InterfaceId>,
}

impl ScopedIpV4 {
    /// Creates a new `ScopedIpV4` with a single interface identifier.
    pub fn new(addr: Ipv4Addr, interface_id: InterfaceId) -> Self {
        Self {
            addr,
            interface_ids: vec![interface_id],
        }
    }

    /// Returns the IPv4 address.
    pub const fn addr(&self) -> &Ipv4Addr {
        &self.addr
    }

    /// Returns the interfaces this address was discovered on.
    pub fn interface_ids(&self) -> &[InterfaceId] {
        &self.interface_ids
    }

    /// Adds an interface identifier if not already present.
    pub(crate) fn add_interface_id(&mut self, id: InterfaceId) {
        if !self.interface_ids.contains(&id) {
            self.interface_ids.push(id);
        }
    }
}

/// An IPv6 address with scope_id (interface identifier).
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
pub struct ScopedIpV6 {
    addr: Ipv6Addr,
    scope_id: InterfaceId,
}

impl ScopedIpV6 {
    /// Returns the IPv6 address.
    pub const fn addr(&self) -> &Ipv6Addr {
        &self.addr
    }

    /// Returns the scope_id for this IPv6 address.
    pub const fn scope_id(&self) -> &InterfaceId {
        &self.scope_id
    }
}

/// An IP address, either IPv4 or IPv6, that supports scope_id for IPv6.
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
#[non_exhaustive]
pub enum ScopedIp {
    V4(ScopedIpV4),
    V6(ScopedIpV6),
}

impl ScopedIp {
    pub const fn to_ip_addr(&self) -> IpAddr {
        match self {
            ScopedIp::V4(v4) => IpAddr::V4(v4.addr),
            ScopedIp::V6(v6) => IpAddr::V6(v6.addr),
        }
    }

    pub const fn is_ipv4(&self) -> bool {
        matches!(self, ScopedIp::V4(_))
    }

    pub const fn is_ipv6(&self) -> bool {
        matches!(self, ScopedIp::V6(_))
    }

    pub const fn is_loopback(&self) -> bool {
        match self {
            ScopedIp::V4(v4) => v4.addr.is_loopback(),
            ScopedIp::V6(v6) => v6.addr.is_loopback(),
        }
    }
}

impl From<IpAddr> for ScopedIp {
    fn from(ip: IpAddr) -> Self {
        match ip {
            IpAddr::V4(v4) => ScopedIp::V4(ScopedIpV4 {
                addr: v4,
                interface_ids: vec![],
            }),
            IpAddr::V6(v6) => ScopedIp::V6(ScopedIpV6 {
                addr: v6,
                scope_id: InterfaceId::default(),
            }),
        }
    }
}

impl From<&Interface> for ScopedIp {
    fn from(interface: &Interface) -> Self {
        match interface.ip() {
            IpAddr::V4(v4) => ScopedIp::V4(ScopedIpV4 {
                addr: v4,
                interface_ids: vec![InterfaceId::from(interface)],
            }),
            IpAddr::V6(v6) => ScopedIp::V6(ScopedIpV6 {
                addr: v6,
                scope_id: InterfaceId::from(interface),
            }),
        }
    }
}

impl fmt::Display for ScopedIp {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ScopedIp::V4(v4) => write!(f, "{}", v4.addr),
            ScopedIp::V6(v6) => {
                if v6.scope_id.index != 0 && is_unicast_link_local(&v6.addr) {
                    #[cfg(windows)]
                    {
                        write!(f, "{}%{}", v6.addr, v6.scope_id.index)
                    }
                    #[cfg(not(windows))]
                    {
                        write!(f, "{}%{}", v6.addr, v6.scope_id.name)
                    }
                } else {
                    write!(f, "{}", v6.addr)
                }
            }
        }
    }
}

/// DNS resource record types, stored as `u16`. Can do `as u16` when needed.
///
/// See [RFC 1035 section 3.2.2](https://datatracker.ietf.org/doc/html/rfc1035#section-3.2.2)
#[derive(Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
#[non_exhaustive]
#[repr(u16)]
pub enum RRType {
    /// DNS record type for IPv4 address
    A = 1,

    /// DNS record type for Canonical Name
    CNAME = 5,

    /// DNS record type for Pointer
    PTR = 12,

    /// DNS record type for Host Info
    HINFO = 13,

    /// DNS record type for Text (properties)
    TXT = 16,

    /// DNS record type for IPv6 address
    AAAA = 28,

    /// DNS record type for Service
    SRV = 33,

    /// DNS record type for Negative Responses
    NSEC = 47,

    /// DNS record type for any records (wildcard)
    ANY = 255,
}

impl RRType {
    /// Converts `u16` into `RRType` if possible.
    pub const fn from_u16(value: u16) -> Option<Self> {
        match value {
            1 => Some(RRType::A),
            5 => Some(RRType::CNAME),
            12 => Some(RRType::PTR),
            13 => Some(RRType::HINFO),
            16 => Some(RRType::TXT),
            28 => Some(RRType::AAAA),
            33 => Some(RRType::SRV),
            47 => Some(RRType::NSEC),
            255 => Some(RRType::ANY),
            _ => None,
        }
    }
}

impl fmt::Display for RRType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            RRType::A => write!(f, "TYPE_A"),
            RRType::CNAME => write!(f, "TYPE_CNAME"),
            RRType::PTR => write!(f, "TYPE_PTR"),
            RRType::HINFO => write!(f, "TYPE_HINFO"),
            RRType::TXT => write!(f, "TYPE_TXT"),
            RRType::AAAA => write!(f, "TYPE_AAAA"),
            RRType::SRV => write!(f, "TYPE_SRV"),
            RRType::NSEC => write!(f, "TYPE_NSEC"),
            RRType::ANY => write!(f, "TYPE_ANY"),
        }
    }
}

/// The class value for the Internet.
pub const CLASS_IN: u16 = 1;
pub const CLASS_MASK: u16 = 0x7FFF;

/// Cache-flush bit: the most significant bit of the rrclass field of the resource record.  
pub const CLASS_CACHE_FLUSH: u16 = 0x8000;

/// Max size of UDP datagram payload.
///
/// It is calculated as: 9000 bytes - IP header 20 bytes - UDP header 8 bytes.
/// Reference: [RFC6762 section 17](https://datatracker.ietf.org/doc/html/rfc6762#section-17)
pub const MAX_MSG_ABSOLUTE: usize = 8972;

const MSG_HEADER_LEN: usize = 12;

/// Max size of a single DNS label, in bytes.
///
/// Reference: [RFC1035 section 2.3.4](https://datatracker.ietf.org/doc/html/rfc1035#section-2.3.4)
const MAX_LABEL_BYTES: usize = 63;

/// Why a question or a record could not be written into a packet.
///
/// In either case nothing is left behind in the packet: the caller rolls back
/// whatever was written and skips the item.
#[derive(Debug, PartialEq, Eq)]
pub enum WriteError {
    /// A label in a name is longer than [`MAX_LABEL_BYTES`].
    NameTooLong,

    /// The packet would exceed [`MAX_MSG_ABSOLUTE`] with this record.
    PacketFull,
}

/// `crate::error::Result` shadows the std alias here, hence the full path.
type WriteResult = core::result::Result<(), WriteError>;

// Definitions for DNS message header "flags" field
//
// The "flags" field is 16-bit long, in this format:
// (RFC 1035 section 4.1.1)
//
//   0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
// |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
//
pub const FLAGS_QR_MASK: u16 = 0x8000; // mask for query/response bit

/// Flag bit to indicate a query
pub const FLAGS_QR_QUERY: u16 = 0x0000;

/// Flag bit to indicate a response
pub const FLAGS_QR_RESPONSE: u16 = 0x8000;

/// Flag bit for Authoritative Answer
pub const FLAGS_AA: u16 = 0x0400;

/// mask for TC(Truncated) bit
///
/// 2024-08-10: currently this flag is only supported on the querier side,
///             not supported on the responder side. I.e. the responder only
///             handles the first packet and ignore this bit. Since the
///             additional packets have 0 questions, the processing of them
///             is no-op.
///             In practice, this means the responder supports Known-Answer
///             only with single packet, not multi-packet. The querier supports
///             both single packet and multi-packet.
pub const FLAGS_TC: u16 = 0x0200;

/// A convenience type alias for DNS record trait objects.
pub type DnsRecordBox = Box<dyn DnsRecordExt>;

impl Clone for DnsRecordBox {
    fn clone(&self) -> Self {
        self.clone_box()
    }
}

const U16_SIZE: usize = 2;

/// Returns `RRType` for a given IP address.
#[inline]
pub const fn ip_address_rr_type(address: &IpAddr) -> RRType {
    match address {
        IpAddr::V4(_) => RRType::A,
        IpAddr::V6(_) => RRType::AAAA,
    }
}

#[derive(Eq, PartialEq, Debug, Clone)]
pub struct DnsEntry {
    pub(crate) name: String, // always lower case.
    pub(crate) ty: RRType,
    class: u16,
    cache_flush: bool,
}

impl DnsEntry {
    const fn new(name: String, ty: RRType, class: u16) -> Self {
        Self {
            name,
            ty,
            class: class & CLASS_MASK,
            cache_flush: (class & CLASS_CACHE_FLUSH) != 0,
        }
    }
}

/// Common methods for all DNS entries:  questions and resource records.
pub trait DnsEntryExt: fmt::Debug {
    fn entry_name(&self) -> &str;

    fn entry_type(&self) -> RRType;
}

/// A DNS question entry
#[derive(Debug)]
pub struct DnsQuestion {
    pub(crate) entry: DnsEntry,
}

impl DnsEntryExt for DnsQuestion {
    fn entry_name(&self) -> &str {
        &self.entry.name
    }

    fn entry_type(&self) -> RRType {
        self.entry.ty
    }
}

/// A DNS Resource Record - like a DNS entry, but has a TTL.
/// RFC: https://www.rfc-editor.org/rfc/rfc1035#section-3.2.1
///      https://www.rfc-editor.org/rfc/rfc1035#section-4.1.3
#[derive(Debug, Clone)]
pub struct DnsRecord {
    pub(crate) entry: DnsEntry,
    ttl: u32,     // in seconds, 0 means this record should not be cached
    created: u64, // UNIX time in millis
    expires: u64, // expires at this UNIX time in millis

    /// Support re-query an instance before its PTR record expires.
    /// See https://datatracker.ietf.org/doc/html/rfc6762#section-5.2
    refresh: u64, // UNIX time in millis

    /// If conflict resolution decides to change the name, this is the new one.
    new_name: Option<String>,
}

impl DnsRecord {
    fn new(name: &str, ty: RRType, class: u16, ttl: u32) -> Self {
        let created = current_time_millis();

        // From RFC 6762 section 5.2:
        // "... The querier should plan to issue a query at 80% of the record
        // lifetime, and then if no answer is received, at 85%, 90%, and 95%."
        let refresh = get_expiration_time(created, ttl, 80);

        let expires = get_expiration_time(created, ttl, 100);

        Self {
            entry: DnsEntry::new(name.to_string(), ty, class),
            ttl,
            created,
            expires,
            refresh,
            new_name: None,
        }
    }

    pub const fn get_ttl(&self) -> u32 {
        self.ttl
    }

    pub const fn get_expire_time(&self) -> u64 {
        self.expires
    }

    pub const fn get_refresh_time(&self) -> u64 {
        self.refresh
    }

    pub const fn is_expired(&self, now: u64) -> bool {
        now >= self.expires
    }

    /// Returns whether record expires in 1 second.
    ///
    /// This is useful because mDNS sets TTL to 1 (not 0) for expiring records.
    pub const fn expires_soon(&self, now: u64) -> bool {
        now + 1000 >= self.expires
    }

    pub const fn refresh_due(&self, now: u64) -> bool {
        now >= self.refresh
    }

    /// Returns whether `now` (in millis) has passed half of TTL.
    pub fn halflife_passed(&self, now: u64) -> bool {
        let halflife = get_expiration_time(self.created, self.ttl, 50);
        now > halflife
    }

    pub fn is_unique(&self) -> bool {
        self.entry.cache_flush
    }

    /// Updates the refresh time to be the same as the expire time so that
    /// this record will not refresh again and will just expire.
    pub fn refresh_no_more(&mut self) {
        self.refresh = get_expiration_time(self.created, self.ttl, 100);
    }

    /// Returns if this record is due for refresh. If yes, `refresh` time is updated.
    pub fn refresh_maybe(&mut self, now: u64) -> bool {
        if self.is_expired(now) || !self.refresh_due(now) {
            return false;
        }

        trace!(
            "{} qtype {} is due to refresh",
            &self.entry.name,
            self.entry.ty
        );

        // From RFC 6762 section 5.2:
        // "... The querier should plan to issue a query at 80% of the record
        // lifetime, and then if no answer is received, at 85%, 90%, and 95%."
        //
        // If the answer is received in time, 'refresh' will be reset outside
        // this function, back to 80% of the new TTL.
        if self.refresh == get_expiration_time(self.created, self.ttl, 80) {
            self.refresh = get_expiration_time(self.created, self.ttl, 85);
        } else if self.refresh == get_expiration_time(self.created, self.ttl, 85) {
            self.refresh = get_expiration_time(self.created, self.ttl, 90);
        } else if self.refresh == get_expiration_time(self.created, self.ttl, 90) {
            self.refresh = get_expiration_time(self.created, self.ttl, 95);
        } else {
            self.refresh_no_more();
        }

        true
    }

    /// Returns the remaining TTL in seconds
    fn get_remaining_ttl(&self, now: u64) -> u32 {
        let remaining_millis = get_expiration_time(self.created, self.ttl, 100) - now;
        cmp::max(0, remaining_millis / 1000) as u32
    }

    /// Return the absolute time for this record being created
    pub const fn get_created(&self) -> u64 {
        self.created
    }

    /// Set the absolute expiration time in millis
    fn set_expire(&mut self, expire_at: u64) {
        self.expires = expire_at;
    }

    fn reset_ttl(&mut self, other: &Self) {
        self.ttl = other.ttl;
        self.created = other.created;
        self.expires = get_expiration_time(self.created, self.ttl, 100);
        self.refresh = if self.ttl > 1 {
            get_expiration_time(self.created, self.ttl, 80)
        } else {
            // If TTL is 1, it means this record is expiring,
            // then we set refresh to the same time as expires.
            self.expires
        };
    }

    /// Modify TTL to reflect the remaining life time from `now`.
    pub fn update_ttl(&mut self, now: u64) {
        if now > self.created {
            let elapsed = now - self.created;
            self.ttl -= (elapsed / 1000) as u32;
        }
    }

    pub fn set_new_name(&mut self, new_name: String) {
        if new_name == self.entry.name {
            self.new_name = None;
        } else {
            self.new_name = Some(new_name);
        }
    }

    pub fn get_new_name(&self) -> Option<&str> {
        self.new_name.as_deref()
    }

    /// Return the new name if exists, otherwise the regular name in DnsEntry.
    pub(crate) fn get_name(&self) -> &str {
        self.new_name.as_deref().unwrap_or(&self.entry.name)
    }

    pub fn get_original_name(&self) -> &str {
        &self.entry.name
    }
}

impl PartialEq for DnsRecord {
    fn eq(&self, other: &Self) -> bool {
        self.entry == other.entry
    }
}

/// Common methods for DNS resource records.
pub trait DnsRecordExt: fmt::Debug {
    fn get_record(&self) -> &DnsRecord;
    fn get_record_mut(&mut self) -> &mut DnsRecord;
    /// Writes the rdata of this record into `packet`.
    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult;
    fn any(&self) -> &dyn Any;

    /// Returns whether `other` record is considered the same except TTL.
    fn matches(&self, other: &dyn DnsRecordExt) -> bool;

    /// Returns whether `other` record has the same rdata.
    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool;

    /// Returns the result based on a byte-level comparison of `rdata`.
    /// If `other` is not valid, returns `Greater`.
    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering;

    /// Returns the result based on "lexicographically later" defined below.
    fn compare(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        /*
        RFC 6762: https://datatracker.ietf.org/doc/html/rfc6762#section-8.2

        ... The determination of "lexicographically later" is performed by first
        comparing the record class (excluding the cache-flush bit described
        in Section 10.2), then the record type, then raw comparison of the
        binary content of the rdata without regard for meaning or structure.
        If the record classes differ, then the numerically greater class is
        considered "lexicographically later".  Otherwise, if the record types
        differ, then the numerically greater type is considered
        "lexicographically later".  If the rrtype and rrclass both match,
        then the rdata is compared. ...
        */
        match self.get_class().cmp(&other.get_class()) {
            cmp::Ordering::Equal => match self.get_type().cmp(&other.get_type()) {
                cmp::Ordering::Equal => self.compare_rdata(other),
                not_equal => not_equal,
            },
            not_equal => not_equal,
        }
    }

    /// Returns a human-readable string of rdata.
    fn rdata_print(&self) -> String;

    /// Returns the class only, excluding class_flush / unique bit.
    fn get_class(&self) -> u16 {
        self.get_record().entry.class
    }

    fn get_cache_flush(&self) -> bool {
        self.get_record().entry.cache_flush
    }

    /// Return the new name if exists, otherwise the regular name in DnsEntry.
    fn get_name(&self) -> &str {
        self.get_record().get_name()
    }

    fn get_type(&self) -> RRType {
        self.get_record().entry.ty
    }

    /// Resets TTL using `other` record.
    /// `self.refresh` and `self.expires` are also reset.
    fn reset_ttl(&mut self, other: &dyn DnsRecordExt) {
        self.get_record_mut().reset_ttl(other.get_record());
    }

    fn get_created(&self) -> u64 {
        self.get_record().get_created()
    }

    fn get_expire(&self) -> u64 {
        self.get_record().get_expire_time()
    }

    fn set_expire(&mut self, expire_at: u64) {
        self.get_record_mut().set_expire(expire_at);
    }

    /// Set expire as `expire_at` if it is sooner than the current `expire`.
    fn set_expire_sooner(&mut self, expire_at: u64) {
        if expire_at < self.get_expire() {
            self.get_record_mut().set_expire(expire_at);
        }
    }

    /// Returns true if the record expires in 1 second from `now`.
    fn expires_soon(&self, now: u64) -> bool {
        self.get_record().expires_soon(now)
    }

    /// Given `now`, if the record is due to refresh, this method updates the refresh time
    /// and returns the new refresh time. Otherwise, returns None.
    fn updated_refresh_time(&mut self, now: u64) -> Option<u64> {
        if self.get_record_mut().refresh_maybe(now) {
            Some(self.get_record().get_refresh_time())
        } else {
            None
        }
    }

    /// Returns true if another record has matched content,
    /// and if its TTL is at least half of this record's.
    fn suppressed_by_answer(&self, other: &dyn DnsRecordExt) -> bool {
        self.matches(other) && (other.get_record().ttl > self.get_record().ttl / 2)
    }

    /// Required by RFC 6762 Section 7.1: Known-Answer Suppression.
    fn suppressed_by(&self, msg: &DnsIncoming) -> bool {
        for answer in msg.answers.iter() {
            if self.suppressed_by_answer(answer.as_ref()) {
                return true;
            }
        }
        false
    }

    fn clone_box(&self) -> DnsRecordBox;

    fn boxed(self) -> DnsRecordBox;
}

/// Resource Record for IPv4 address or IPv6 address.
#[derive(Debug, Clone)]
pub(crate) struct DnsAddress {
    pub(crate) record: DnsRecord,
    address: IpAddr,
    pub(crate) interface_id: InterfaceId,
}

impl DnsAddress {
    pub fn new(
        name: &str,
        ty: RRType,
        class: u16,
        ttl: u32,
        address: IpAddr,
        interface_id: InterfaceId,
    ) -> Self {
        let record = DnsRecord::new(name, ty, class, ttl);
        Self {
            record,
            address,
            interface_id,
        }
    }

    pub fn address(&self) -> ScopedIp {
        match self.address {
            IpAddr::V4(v4) => ScopedIp::V4(ScopedIpV4 {
                addr: v4,
                interface_ids: vec![self.interface_id.clone()],
            }),
            IpAddr::V6(v6) => ScopedIp::V6(ScopedIpV6 {
                addr: v6,
                scope_id: self.interface_id.clone(),
            }),
        }
    }
}

impl DnsRecordExt for DnsAddress {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        match self.address {
            IpAddr::V4(addr) => packet.write_bytes(addr.octets().as_ref()),
            IpAddr::V6(addr) => packet.write_bytes(addr.octets().as_ref()),
        };
        Ok(())
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_a) = other.any().downcast_ref::<Self>() {
            return self.address == other_a.address
                && self.record.entry == other_a.record.entry
                && self.interface_id == other_a.interface_id;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_a) = other.any().downcast_ref::<Self>() {
            return self.address == other_a.address;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        if let Some(other_a) = other.any().downcast_ref::<Self>() {
            self.address.cmp(&other_a.address)
        } else {
            cmp::Ordering::Greater
        }
    }

    fn rdata_print(&self) -> String {
        format!("{}", self.address)
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

/// Resource Record for a DNS pointer
#[derive(Debug, Clone)]
pub struct DnsPointer {
    record: DnsRecord,
    alias: String, // the full name of Service Instance
}

impl DnsPointer {
    pub fn new(name: &str, ty: RRType, class: u16, ttl: u32, alias: String) -> Self {
        let record = DnsRecord::new(name, ty, class, ttl);
        Self { record, alias }
    }

    pub fn alias(&self) -> &str {
        &self.alias
    }
}

impl DnsRecordExt for DnsPointer {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        packet.write_name(&self.alias)
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_ptr) = other.any().downcast_ref::<Self>() {
            return self.alias == other_ptr.alias && self.record.entry == other_ptr.record.entry;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_ptr) = other.any().downcast_ref::<Self>() {
            return self.alias == other_ptr.alias;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        if let Some(other_ptr) = other.any().downcast_ref::<Self>() {
            self.alias.cmp(&other_ptr.alias)
        } else {
            cmp::Ordering::Greater
        }
    }

    fn rdata_print(&self) -> String {
        self.alias.clone()
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

/// Resource Record for a DNS service.
#[derive(Debug, Clone)]
pub struct DnsSrv {
    pub(crate) record: DnsRecord,
    pub(crate) priority: u16, // lower number means higher priority. Should be 0 in common cases.
    pub(crate) weight: u16,   // Should be 0 in common cases
    host: String,
    port: u16,
}

impl DnsSrv {
    pub fn new(
        name: &str,
        class: u16,
        ttl: u32,
        priority: u16,
        weight: u16,
        port: u16,
        host: String,
    ) -> Self {
        let record = DnsRecord::new(name, RRType::SRV, class, ttl);
        Self {
            record,
            priority,
            weight,
            host,
            port,
        }
    }

    pub fn host(&self) -> &str {
        &self.host
    }

    pub fn port(&self) -> u16 {
        self.port
    }

    pub fn set_host(&mut self, host: String) {
        self.host = host;
    }
}

impl DnsRecordExt for DnsSrv {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        packet.write_short(self.priority);
        packet.write_short(self.weight);
        packet.write_short(self.port);
        packet.write_name(&self.host)
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_svc) = other.any().downcast_ref::<Self>() {
            return self.host == other_svc.host
                && self.port == other_svc.port
                && self.weight == other_svc.weight
                && self.priority == other_svc.priority
                && self.record.entry == other_svc.record.entry;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_srv) = other.any().downcast_ref::<Self>() {
            return self.host == other_srv.host
                && self.port == other_srv.port
                && self.weight == other_srv.weight
                && self.priority == other_srv.priority;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        let Some(other_srv) = other.any().downcast_ref::<Self>() else {
            return cmp::Ordering::Greater;
        };

        // 1. compare `priority`
        match self
            .priority
            .to_be_bytes()
            .cmp(&other_srv.priority.to_be_bytes())
        {
            cmp::Ordering::Equal => {
                // 2. compare `weight`
                match self
                    .weight
                    .to_be_bytes()
                    .cmp(&other_srv.weight.to_be_bytes())
                {
                    cmp::Ordering::Equal => {
                        // 3. compare `port`.
                        match self.port.to_be_bytes().cmp(&other_srv.port.to_be_bytes()) {
                            cmp::Ordering::Equal => self.host.cmp(&other_srv.host),
                            not_equal => not_equal,
                        }
                    }
                    not_equal => not_equal,
                }
            }
            not_equal => not_equal,
        }
    }

    fn rdata_print(&self) -> String {
        format!(
            "priority: {}, weight: {}, port: {}, host: {}",
            self.priority, self.weight, self.port, self.host
        )
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

/// Resource Record for a DNS TXT record.
///
/// From [RFC 6763 section 6]:
///
/// The format of each constituent string within the DNS TXT record is a
/// single length byte, followed by 0-255 bytes of text data.
///
/// DNS-SD uses DNS TXT records to store arbitrary key/value pairs
///    conveying additional information about the named service.  Each
///    key/value pair is encoded as its own constituent string within the
///    DNS TXT record, in the form "key=value" (without the quotation
///    marks).  Everything up to the first '=' character is the key (Section
///    6.4).  Everything after the first '=' character to the end of the
///    string (including subsequent '=' characters, if any) is the value
#[derive(Clone)]
pub struct DnsTxt {
    pub(crate) record: DnsRecord,
    text: Vec<u8>,
}

impl DnsTxt {
    pub fn new(name: &str, class: u16, ttl: u32, text: Vec<u8>) -> Self {
        let record = DnsRecord::new(name, RRType::TXT, class, ttl);
        Self { record, text }
    }

    pub fn text(&self) -> &[u8] {
        &self.text
    }
}

impl DnsRecordExt for DnsTxt {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        packet.write_bytes(&self.text);
        Ok(())
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_txt) = other.any().downcast_ref::<Self>() {
            return self.text == other_txt.text && self.record.entry == other_txt.record.entry;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_txt) = other.any().downcast_ref::<Self>() {
            return self.text == other_txt.text;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        if let Some(other_txt) = other.any().downcast_ref::<Self>() {
            self.text.cmp(&other_txt.text)
        } else {
            cmp::Ordering::Greater
        }
    }

    fn rdata_print(&self) -> String {
        format!("{:?}", decode_txt(&self.text))
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

impl fmt::Debug for DnsTxt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let properties = decode_txt(&self.text);
        write!(
            f,
            "DnsTxt {{ record: {:?}, text: {:?} }}",
            self.record, properties
        )
    }
}

// Convert from DNS TXT record content to key/value pairs
fn decode_txt(txt: &[u8]) -> Vec<TxtProperty> {
    let mut properties = Vec::new();
    let mut offset = 0;
    while offset < txt.len() {
        let length = txt[offset] as usize;
        if length == 0 {
            break; // reached the end
        }
        offset += 1; // move over the length byte

        let offset_end = offset + length;
        if offset_end > txt.len() {
            trace!("ERROR: DNS TXT: size given for property is out of range. (offset={}, length={}, offset_end={}, record length={})", offset, length, offset_end, txt.len());
            break; // Skipping the rest of the record content, as the size for this property would already be out of range.
        }
        let kv_bytes = &txt[offset..offset_end];

        // split key and val using the first `=`
        let (k, v) = kv_bytes.iter().position(|&x| x == b'=').map_or_else(
            || (kv_bytes.to_vec(), None),
            |idx| (kv_bytes[..idx].to_vec(), Some(kv_bytes[idx + 1..].to_vec())),
        );

        // Make sure the key can be stored in UTF-8.
        match String::from_utf8(k) {
            Ok(k_string) => {
                properties.push(TxtProperty {
                    key: k_string,
                    val: v,
                });
            }
            Err(e) => trace!("ERROR: convert to String from key: {}", e),
        }

        offset += length;
    }

    properties
}

/// Represents a property in a TXT record.
#[derive(Clone, PartialEq, Eq)]
pub struct TxtProperty {
    /// The name of the property. The original cases are kept.
    key: String,

    /// RFC 6763 says values are bytes, not necessarily UTF-8.
    /// It is also possible that there is no value, in which case
    /// the key is a boolean key.
    val: Option<Vec<u8>>,
}

impl TxtProperty {
    /// Returns the value of a property as str.
    pub fn val_str(&self) -> &str {
        self.val
            .as_ref()
            .map_or("", |v| std::str::from_utf8(&v[..]).unwrap_or_default())
    }
}

/// Supports constructing from a tuple.
impl<K, V> From<&(K, V)> for TxtProperty
where
    K: ToString,
    V: ToString,
{
    fn from(prop: &(K, V)) -> Self {
        Self {
            key: prop.0.to_string(),
            val: Some(prop.1.to_string().into_bytes()),
        }
    }
}

impl<K, V> From<(K, V)> for TxtProperty
where
    K: ToString,
    V: AsRef<[u8]>,
{
    fn from(prop: (K, V)) -> Self {
        Self {
            key: prop.0.to_string(),
            val: Some(prop.1.as_ref().into()),
        }
    }
}

/// Support a property that has no value.
impl From<&str> for TxtProperty {
    fn from(key: &str) -> Self {
        Self {
            key: key.to_string(),
            val: None,
        }
    }
}

impl fmt::Display for TxtProperty {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}={}", self.key, self.val_str())
    }
}

/// Mimic the default debug output for a struct, with a twist:
/// - If self.var is UTF-8, will output it as a string in double quotes.
/// - If self.var is not UTF-8, will output its bytes as in hex.
impl fmt::Debug for TxtProperty {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let val_string = self.val.as_ref().map_or_else(
            || "None".to_string(),
            |v| {
                std::str::from_utf8(&v[..]).map_or_else(
                    |_| format!("Some({})", u8_slice_to_hex(&v[..])),
                    |s| format!("Some(\"{s}\")"),
                )
            },
        );

        write!(
            f,
            "TxtProperty {{key: \"{}\", val: {}}}",
            &self.key, &val_string,
        )
    }
}

const HEX_TABLE: [char; 16] = [
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f',
];

/// Create a hex string from `slice`, with a "0x" prefix.
///
/// For example, [1u8, 2u8] -> "0x0102"
fn u8_slice_to_hex(slice: &[u8]) -> String {
    let mut hex = String::with_capacity(slice.len() * 2 + 2);
    hex.push_str("0x");
    for b in slice {
        hex.push(HEX_TABLE[(b >> 4) as usize]);
        hex.push(HEX_TABLE[(b & 0x0F) as usize]);
    }
    hex
}

/// A DNS host information record
#[derive(Debug, Clone)]
struct DnsHostInfo {
    record: DnsRecord,
    cpu: String,
    os: String,
}

impl DnsHostInfo {
    fn new(name: &str, ty: RRType, class: u16, ttl: u32, cpu: String, os: String) -> Self {
        let record = DnsRecord::new(name, ty, class, ttl);
        Self { record, cpu, os }
    }
}

impl DnsRecordExt for DnsHostInfo {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        debug!("Writing HInfo: cpu {} os {}", &self.cpu, &self.os);
        packet.write_bytes(self.cpu.as_bytes());
        packet.write_bytes(self.os.as_bytes());
        Ok(())
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_hinfo) = other.any().downcast_ref::<Self>() {
            return self.cpu == other_hinfo.cpu
                && self.os == other_hinfo.os
                && self.record.entry == other_hinfo.record.entry;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_hinfo) = other.any().downcast_ref::<Self>() {
            return self.cpu == other_hinfo.cpu && self.os == other_hinfo.os;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        if let Some(other_hinfo) = other.any().downcast_ref::<Self>() {
            match self.cpu.cmp(&other_hinfo.cpu) {
                cmp::Ordering::Equal => self.os.cmp(&other_hinfo.os),
                ordering => ordering,
            }
        } else {
            cmp::Ordering::Greater
        }
    }

    fn rdata_print(&self) -> String {
        format!("cpu: {}, os: {}", self.cpu, self.os)
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

/// Resource Record for negative responses
///
/// [RFC4034 section 4.1](https://datatracker.ietf.org/doc/html/rfc4034#section-4.1)
/// and
/// [RFC6762 section 6.1](https://datatracker.ietf.org/doc/html/rfc6762#section-6.1)
#[derive(Debug, Clone)]
pub struct DnsNSec {
    record: DnsRecord,
    next_domain: String,
    type_bitmap: Vec<u8>,
}

impl DnsNSec {
    pub fn new(
        name: &str,
        class: u16,
        ttl: u32,
        next_domain: String,
        type_bitmap: Vec<u8>,
    ) -> Self {
        let record = DnsRecord::new(name, RRType::NSEC, class, ttl);
        Self {
            record,
            next_domain,
            type_bitmap,
        }
    }

    /// Returns the types marked by `type_bitmap`
    pub fn _types(&self) -> Vec<u16> {
        // From RFC 4034: 4.1.2 The Type Bit Maps Field
        // https://datatracker.ietf.org/doc/html/rfc4034#section-4.1.2
        //
        // Each bitmap encodes the low-order 8 bits of RR types within the
        // window block, in network bit order.  The first bit is bit 0.  For
        // window block 0, bit 1 corresponds to RR type 1 (A), bit 2 corresponds
        // to RR type 2 (NS), and so forth.

        let mut bit_num = 0;
        let mut results = Vec::new();

        for byte in self.type_bitmap.iter() {
            let mut bit_mask: u8 = 0x80; // for bit 0 in network bit order

            // check every bit in this byte, one by one.
            for _ in 0..8 {
                if (byte & bit_mask) != 0 {
                    results.push(bit_num);
                }
                bit_num += 1;
                bit_mask >>= 1; // mask for the next bit
            }
        }
        results
    }
}

impl DnsRecordExt for DnsNSec {
    fn get_record(&self) -> &DnsRecord {
        &self.record
    }

    fn get_record_mut(&mut self) -> &mut DnsRecord {
        &mut self.record
    }

    fn write(&self, packet: &mut DnsOutPacket) -> WriteResult {
        packet.write_bytes(self.next_domain.as_bytes());
        packet.write_bytes(&self.type_bitmap);
        Ok(())
    }

    fn any(&self) -> &dyn Any {
        self
    }

    fn matches(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_record) = other.any().downcast_ref::<Self>() {
            return self.next_domain == other_record.next_domain
                && self.type_bitmap == other_record.type_bitmap
                && self.record.entry == other_record.record.entry;
        }
        false
    }

    fn rrdata_match(&self, other: &dyn DnsRecordExt) -> bool {
        if let Some(other_record) = other.any().downcast_ref::<Self>() {
            return self.next_domain == other_record.next_domain
                && self.type_bitmap == other_record.type_bitmap;
        }
        false
    }

    fn compare_rdata(&self, other: &dyn DnsRecordExt) -> cmp::Ordering {
        if let Some(other_nsec) = other.any().downcast_ref::<Self>() {
            match self.next_domain.cmp(&other_nsec.next_domain) {
                cmp::Ordering::Equal => self.type_bitmap.cmp(&other_nsec.type_bitmap),
                ordering => ordering,
            }
        } else {
            cmp::Ordering::Greater
        }
    }

    fn rdata_print(&self) -> String {
        format!(
            "next_domain: {}, type_bitmap len: {}",
            self.next_domain,
            self.type_bitmap.len()
        )
    }

    fn clone_box(&self) -> DnsRecordBox {
        Box::new(self.clone())
    }

    fn boxed(self) -> DnsRecordBox {
        Box::new(self)
    }
}

#[derive(PartialEq)]
enum PacketState {
    Init = 0,
    Finished = 1,
}

/// A single packet for outgoing DNS message.
pub struct DnsOutPacket {
    /// All bytes in `data` is the actual packet on the wire.
    data: Vec<u8>,

    /// An internal state, not defined by DNS.
    state: PacketState,

    /// k: name, v: offset
    names: HashMap<String, u16>,
}

impl DnsOutPacket {
    fn new() -> Self {
        Self {
            data: vec![0; MSG_HEADER_LEN],
            state: PacketState::Init,
            names: HashMap::new(),
        }
    }

    pub fn size(&self) -> usize {
        self.data.len()
    }

    pub fn as_bytes(&self) -> &[u8] {
        &self.data
    }

    fn write_question(&mut self, question: &DnsQuestion) -> WriteResult {
        self.write_name(&question.entry.name)?;
        self.write_short(question.entry.ty as u16);
        self.write_short(question.entry.class);
        Ok(())
    }

    /// Discards everything written since `start_size`, including the name
    /// compression offsets that point into the discarded bytes.
    fn rollback(&mut self, start_size: usize) {
        self.data.truncate(start_size);
        self.names
            .retain(|_, offset| (*offset as usize) < start_size);
    }

    /// Writes a record (answer, authoritative answer, additional).
    ///
    /// In error cases nothing is written to the packet.
    fn write_record(&mut self, record_ext: &dyn DnsRecordExt, now: u64) -> WriteResult {
        let start_size = self.size();

        let record = record_ext.get_record();
        self.write_name(record.get_name())?;
        self.write_short(record.entry.ty as u16);
        if record.entry.cache_flush {
            // check "multicast"
            self.write_short(record.entry.class | CLASS_CACHE_FLUSH);
        } else {
            self.write_short(record.entry.class);
        }

        if now == 0 {
            self.write_u32(record.ttl);
        } else {
            self.write_u32(record.get_remaining_ttl(now));
        }

        // Placeholder for record size
        self.write_short(0);
        let record_offset = self.size();

        if let Err(e) = record_ext.write(self) {
            self.rollback(start_size);
            return Err(e);
        }

        self.insert_short(record_offset - 2, (self.size() - record_offset) as u16);

        if self.size() > MAX_MSG_ABSOLUTE {
            self.rollback(start_size);
            self.state = PacketState::Finished;
            return Err(WriteError::PacketFull);
        }

        Ok(())
    }

    pub(crate) fn insert_short(&mut self, index: usize, value: u16) {
        self.data[index..index + 2].copy_from_slice(&value.to_be_bytes());
    }

    /// Parses a DNS name that may contain escaped characters according to RFC 6763 Section 4.3.
    /// Returns a vector of labels where each label is the unescaped content.
    ///
    /// Escape sequences:
    /// - \\. becomes . (literal dot)
    /// - \\\\ becomes \\ (literal backslash)
    fn parse_escaped_name(name: &str) -> Vec<String> {
        let mut labels = Vec::new();
        let mut current_label = String::new();
        let mut chars = name.chars().peekable();

        while let Some(ch) = chars.next() {
            match ch {
                '\\' => {
                    // Backslash escape sequence
                    if let Some(&next_ch) = chars.peek() {
                        match next_ch {
                            '.' | '\\' => {
                                // \\. or \\\\ - consume the backslash and add the escaped char
                                chars.next();
                                current_label.push(next_ch);
                            }
                            _ => {
                                // Not a recognized escape - treat backslash literally
                                current_label.push(ch);
                            }
                        }
                    } else {
                        // Trailing backslash - add it literally
                        current_label.push(ch);
                    }
                }
                '.' => {
                    // Unescaped dot - label separator
                    if !current_label.is_empty() {
                        labels.push(current_label.clone());
                        current_label.clear();
                    }
                }
                _ => {
                    current_label.push(ch);
                }
            }
        }

        // Add the last label if not empty
        if !current_label.is_empty() {
            labels.push(current_label);
        }

        labels
    }

    // Write name to packet
    //
    // [RFC1035]
    // 4.1.4. Message compression
    //
    // In order to reduce the size of messages, the domain system utilizes a
    // compression scheme which eliminates the repetition of domain names in a
    // message.  In this scheme, an entire domain name or a list of labels at
    // the end of a domain name is replaced with a pointer to a prior occurrence
    // of the same name.
    // The pointer takes the form of a two octet sequence:
    //     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //     | 1  1|                OFFSET                   |
    //     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    // The first two bits are ones.  This allows a pointer to be distinguished
    // from a label, since the label must begin with two zero bits because
    // labels are restricted to 63 octets or less.  (The 10 and 01 combinations
    // are reserved for future use.)  The OFFSET field specifies an offset from
    // the start of the message (i.e., the first octet of the ID field in the
    // domain header).  A zero offset specifies the first byte of the ID field,
    // etc.
    //
    // This function also handles RFC 6763 Section 4.3 escaping where dots and backslashes
    // in instance names are escaped (e.g., "My\\.Service" represents a single label "My.Service").
    // The actual name sent over the wire is the unescaped version.
    fn write_name(&mut self, name: &str) -> WriteResult {
        // Remove trailing dot if present
        let name_to_parse = name.strip_suffix('.').unwrap_or(name);

        // Parse the name considering escape sequences
        let labels = Self::parse_escaped_name(name_to_parse);

        if labels.is_empty() {
            self.write_byte(0);
            return Ok(());
        }

        // Validate before writing anything.
        if labels.iter().any(|label| label.len() > MAX_LABEL_BYTES) {
            return Err(WriteError::NameTooLong);
        }

        // Write each label
        for (i, label) in labels.iter().enumerate() {
            // Build the remaining name for compression (with dots as separators)
            let remaining: String = labels[i..].join(".");

            // Check if we can use compression for the remaining part
            const POINTER_MASK: u16 = 0xC000;
            if let Some(&offset) = self.names.get(&remaining) {
                let pointer = offset | POINTER_MASK;
                self.write_short(pointer);
                return Ok(());
            }

            // Store this position for potential future compression
            self.names.insert(remaining, self.size() as u16);

            // Write the label
            self.write_utf8(label)?;
        }

        // Write terminating zero byte
        self.write_byte(0);
        Ok(())
    }

    fn write_byte(&mut self, v: u8) {
        self.data.push(v);
    }

    fn write_bytes(&mut self, s: &[u8]) {
        self.data.extend(s);
    }

    /// Writes a single label. Nothing is written if the label is too long to
    /// be encoded.
    fn write_utf8(&mut self, s: &str) -> WriteResult {
        if s.len() > MAX_LABEL_BYTES {
            return Err(WriteError::NameTooLong);
        }
        self.write_byte(s.len() as u8);
        self.write_bytes(s.as_bytes());
        Ok(())
    }

    fn write_u32(&mut self, v: u32) {
        self.data.extend(&v.to_be_bytes());
    }

    fn write_short(&mut self, v: u16) {
        self.data.extend(&v.to_be_bytes());
    }

    /// Writes the header fields and finish the packet.
    /// This function should be only called when finishing a packet.
    ///
    /// The header format is based on RFC 1035 section 4.1.1:
    /// https://datatracker.ietf.org/doc/html/rfc1035#section-4.1.1
    //
    //                                  1  1  1  1  1  1
    //    0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |                      ID                       |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |                    QDCOUNT                    |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |                    ANCOUNT                    |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |                    NSCOUNT                    |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //    |                    ARCOUNT                    |
    //    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    //
    fn write_header(
        &mut self,
        id: u16,
        flags: u16,
        q_count: u16,
        a_count: u16,
        auth_count: u16,
        addi_count: u16,
    ) {
        self.insert_short(0, id);
        self.insert_short(2, flags);
        self.insert_short(4, q_count);
        self.insert_short(6, a_count);
        self.insert_short(8, auth_count);
        self.insert_short(10, addi_count);

        self.state = PacketState::Finished;
    }
}

/// Representation of one outgoing DNS message that could be sent in one or more packet(s).
#[derive(Debug)]
pub struct DnsOutgoing {
    flags: u16,
    id: u16,
    multicast: bool,
    questions: Vec<DnsQuestion>,
    answers: Vec<(DnsRecordBox, u64)>,
    authorities: Vec<DnsRecordBox>,
    additionals: Vec<DnsRecordBox>,
    known_answer_count: i64, // for internal maintenance only
}

impl DnsOutgoing {
    pub fn new(flags: u16) -> Self {
        Self {
            flags,
            id: 0,
            multicast: true,
            questions: Vec::new(),
            answers: Vec::new(),
            authorities: Vec::new(),
            additionals: Vec::new(),
            known_answer_count: 0,
        }
    }

    pub fn questions(&self) -> &[DnsQuestion] {
        &self.questions
    }

    /// For testing purposes only.
    pub(crate) fn _answers(&self) -> &[(DnsRecordBox, u64)] {
        &self.answers
    }

    pub fn answers_count(&self) -> usize {
        self.answers.len()
    }

    pub fn authorities(&self) -> &[DnsRecordBox] {
        &self.authorities
    }

    pub fn additionals(&self) -> &[DnsRecordBox] {
        &self.additionals
    }

    pub fn known_answer_count(&self) -> i64 {
        self.known_answer_count
    }

    pub fn set_id(&mut self, id: u16) {
        self.id = id;
    }

    pub const fn is_query(&self) -> bool {
        (self.flags & FLAGS_QR_MASK) == FLAGS_QR_QUERY
    }

    const fn is_response(&self) -> bool {
        (self.flags & FLAGS_QR_MASK) == FLAGS_QR_RESPONSE
    }

    // Adds an additional answer

    // From: RFC 6763, DNS-Based Service Discovery, February 2013

    // 12.  DNS Additional Record Generation

    //    DNS has an efficiency feature whereby a DNS server may place
    //    additional records in the additional section of the DNS message.
    //    These additional records are records that the client did not
    //    explicitly request, but the server has reasonable grounds to expect
    //    that the client might request them shortly, so including them can
    //    save the client from having to issue additional queries.

    //    This section recommends which additional records SHOULD be generated
    //    to improve network efficiency, for both Unicast and Multicast DNS-SD
    //    responses.

    // 12.1.  PTR Records

    //    When including a DNS-SD Service Instance Enumeration or Selective
    //    Instance Enumeration (subtype) PTR record in a response packet, the
    //    server/responder SHOULD include the following additional records:

    //    o  The SRV record(s) named in the PTR rdata.
    //    o  The TXT record(s) named in the PTR rdata.
    //    o  All address records (type "A" and "AAAA") named in the SRV rdata.

    // 12.2.  SRV Records

    //    When including an SRV record in a response packet, the
    //    server/responder SHOULD include the following additional records:

    //    o  All address records (type "A" and "AAAA") named in the SRV rdata.
    pub fn add_additional_answer(&mut self, answer: impl DnsRecordExt + 'static) {
        trace!("add_additional_answer: {:?}", &answer);
        self.additionals.push(answer.boxed());
    }

    /// A workaround as Rust doesn't allow us to pass DnsRecordBox in as `impl DnsRecordExt`
    pub fn add_answer_box(&mut self, answer_box: DnsRecordBox) {
        self.answers.push((answer_box, 0));
    }

    pub fn add_authority(&mut self, record: DnsRecordBox) {
        self.authorities.push(record);
    }

    /// Retains only the answers for which `keep` returns true.
    pub(crate) fn retain_answers<F>(&mut self, mut keep: F)
    where
        F: FnMut(&DnsRecordBox) -> bool,
    {
        self.answers.retain(|(record, _)| keep(record));
    }

    /// Retains only the additional records for which `keep` returns true.
    pub(crate) fn retain_additionals<F>(&mut self, mut keep: F)
    where
        F: FnMut(&DnsRecordBox) -> bool,
    {
        self.additionals.retain(|record| keep(record));
    }

    /// Returns true if `answer` is added to the outgoing msg.
    /// Returns false if `answer` was not added as it expired or suppressed by the incoming `msg`.
    pub fn add_answer(
        &mut self,
        msg: &DnsIncoming,
        answer: impl DnsRecordExt + Send + 'static,
    ) -> bool {
        trace!("Check for add_answer");
        if answer.suppressed_by(msg) {
            trace!("my answer is suppressed by incoming msg");
            self.known_answer_count += 1;
            return false;
        }

        self.add_answer_at_time(answer, 0)
    }

    /// Returns true if `answer` is added to the outgoing msg.
    /// Returns false if the answer is expired `now` hence not added.
    /// If `now` is 0, do not check if the answer expires.
    pub fn add_answer_at_time(
        &mut self,
        answer: impl DnsRecordExt + Send + 'static,
        now: u64,
    ) -> bool {
        if now == 0 || !answer.get_record().is_expired(now) {
            trace!("add_answer push: {:?}", &answer);
            self.answers.push((answer.boxed(), now));
            return true;
        }
        false
    }

    /// Adds a PTR answer for `service` along with recommended additional records
    /// (SRV, TXT, and address records) per [RFC 6763 Section 12.1].
    ///
    /// Resolves any name conflicts via `dns_registry` and selects addresses
    /// matching the given interface. Does nothing if no addresses are available
    /// on `intf` or if the PTR answer is suppressed by known-answer entries in `msg`.
    ///
    /// [RFC 6763 Section 12.1]: https://tools.ietf.org/html/rfc6763#section-12.1
    pub(crate) fn add_answer_with_additionals(
        &mut self,
        msg: &DnsIncoming,
        service: &ServiceInfo,
        intf: &MyIntf,
        dns_registry: &DnsRegistry,
        is_ipv4: bool,
    ) {
        let intf_addrs = if is_ipv4 {
            service.get_addrs_on_my_intf_v4(intf)
        } else {
            service.get_addrs_on_my_intf_v6(intf)
        };
        if intf_addrs.is_empty() {
            trace!("No addrs on LAN of intf {:?}", intf);
            return;
        }

        // check if we changed our name due to conflicts.
        let service_fullname = dns_registry.resolve_name(service.get_fullname());
        let hostname = dns_registry.resolve_name(service.get_hostname());

        let ptr_added = self.add_answer(
            msg,
            DnsPointer::new(
                service.get_type(),
                RRType::PTR,
                CLASS_IN,
                service.get_other_ttl(),
                service_fullname.to_string(),
            ),
        );

        if !ptr_added {
            trace!("answer was not added for msg {:?}", msg);
            return;
        }

        if let Some(sub) = service.get_subtype() {
            trace!("Adding subdomain {}", sub);
            self.add_additional_answer(DnsPointer::new(
                sub,
                RRType::PTR,
                CLASS_IN,
                service.get_other_ttl(),
                service_fullname.to_string(),
            ));
        }

        // Add recommended additional answers according to
        // https://tools.ietf.org/html/rfc6763#section-12.1.
        self.add_additional_answer(DnsSrv::new(
            service_fullname,
            CLASS_IN | CLASS_CACHE_FLUSH,
            service.get_host_ttl(),
            service.get_priority(),
            service.get_weight(),
            service.get_port(),
            hostname.to_string(),
        ));

        self.add_additional_answer(DnsTxt::new(
            service_fullname,
            CLASS_IN | CLASS_CACHE_FLUSH,
            service.get_other_ttl(),
            service.generate_txt(),
        ));

        for address in intf_addrs {
            self.add_additional_answer(DnsAddress::new(
                hostname,
                ip_address_rr_type(&address),
                CLASS_IN | CLASS_CACHE_FLUSH,
                service.get_host_ttl(),
                address,
                intf.into(),
            ));
        }
    }

    pub fn add_question(&mut self, name: &str, qtype: RRType) {
        let q = DnsQuestion {
            entry: DnsEntry::new(name.to_string(), qtype, CLASS_IN),
        };
        self.questions.push(q);
    }

    /// Clear the cache-flush (unique) bit on every answer and additional
    /// record. Required for RFC 6762 §6.7 (Legacy Unicast Responses) and
    /// §10.2 — a legacy resolver doesn't know about the cache-flush bit
    /// and may misinterpret responses where it is set.
    pub fn clear_cache_flush_bits(&mut self) {
        for (rec, _) in &mut self.answers {
            rec.get_record_mut().entry.cache_flush = false;
        }
        for rec in &mut self.additionals {
            rec.get_record_mut().entry.cache_flush = false;
        }
        for rec in &mut self.authorities {
            rec.get_record_mut().entry.cache_flush = false;
        }
    }

    /// Returns a list of actual DNS packet data to be sent on the wire.
    pub fn to_data_on_wire(&self) -> Vec<Vec<u8>> {
        let packet_list = self.to_packets();
        packet_list.into_iter().map(|p| p.data).collect()
    }

    /// Encode self into one or more packets.
    pub fn to_packets(&self) -> Vec<DnsOutPacket> {
        let mut packet_list = Vec::new();
        let mut packet = DnsOutPacket::new();

        let mut question_count = 0;
        let mut answer_count = 0;
        let mut auth_count = 0;
        let mut addi_count = 0;
        let id = if self.multicast { 0 } else { self.id };

        for question in self.questions.iter() {
            question_count += u16::from(packet.write_question(question).is_ok());
        }

        for (answer, time) in self.answers.iter() {
            answer_count += u16::from(packet.write_record(answer.as_ref(), *time).is_ok());
        }

        for auth in self.authorities.iter() {
            auth_count += u16::from(packet.write_record(auth.as_ref(), 0).is_ok());
        }

        for addi in self.additionals.iter() {
            match packet.write_record(addi.as_ref(), 0) {
                Ok(()) => {
                    addi_count += 1;
                    continue;
                }
                // The record itself is unusable: skip it and keep the packet.
                Err(WriteError::NameTooLong) => continue,
                Err(WriteError::PacketFull) => {}
            }

            // No more processing for response packets.
            if self.is_response() {
                break;
            }

            // For query, the current packet exceeds its max size due to known answers,
            // need to truncate.

            // finish the current packet first.
            packet.write_header(
                id,
                self.flags | FLAGS_TC,
                question_count,
                answer_count,
                auth_count,
                addi_count,
            );

            packet_list.push(packet);

            // create a new packet and reset counts.
            packet = DnsOutPacket::new();
            addi_count = u16::from(packet.write_record(addi.as_ref(), 0).is_ok());

            question_count = 0;
            answer_count = 0;
            auth_count = 0;
        }

        packet.write_header(
            id,
            self.flags,
            question_count,
            answer_count,
            auth_count,
            addi_count,
        );

        packet_list.push(packet);
        packet_list
    }
}

/// An incoming DNS message. It could be a query or a response.
#[derive(Debug)]
pub struct DnsIncoming {
    offset: usize,
    data: Vec<u8>,
    questions: Vec<DnsQuestion>,
    answers: Vec<DnsRecordBox>,
    authorities: Vec<DnsRecordBox>,
    additional: Vec<DnsRecordBox>,
    id: u16,
    flags: u16,
    num_questions: u16,
    num_answers: u16,
    num_authorities: u16,
    num_additionals: u16,
    interface_id: InterfaceId,
}

impl DnsIncoming {
    pub fn new(data: Vec<u8>, interface_id: InterfaceId) -> Result<Self> {
        let mut incoming = Self {
            offset: 0,
            data,
            questions: Vec::new(),
            answers: Vec::new(),
            authorities: Vec::new(),
            additional: Vec::new(),
            id: 0,
            flags: 0,
            num_questions: 0,
            num_answers: 0,
            num_authorities: 0,
            num_additionals: 0,
            interface_id,
        };

        /*
        RFC 1035 section 4.1: https://datatracker.ietf.org/doc/html/rfc1035#section-4.1
        ...
        All communications inside of the domain protocol are carried in a single
        format called a message.  The top level format of message is divided
        into 5 sections (some of which are empty in certain cases) shown below:

            +---------------------+
            |        Header       |
            +---------------------+
            |       Question      | the question for the name server
            +---------------------+
            |        Answer       | RRs answering the question
            +---------------------+
            |      Authority      | RRs pointing toward an authority
            +---------------------+
            |      Additional     | RRs holding additional information
            +---------------------+
         */
        incoming.read_header()?;
        incoming.read_questions()?;
        incoming.read_answers()?;
        incoming.read_authorities()?;
        incoming.read_additional()?;

        Ok(incoming)
    }

    pub fn id(&self) -> u16 {
        self.id
    }

    pub fn questions(&self) -> &[DnsQuestion] {
        &self.questions
    }

    pub fn answers(&self) -> &[DnsRecordBox] {
        &self.answers
    }

    pub fn authorities(&self) -> &[DnsRecordBox] {
        &self.authorities
    }

    pub fn additionals(&self) -> &[DnsRecordBox] {
        &self.additional
    }

    pub fn answers_mut(&mut self) -> &mut Vec<DnsRecordBox> {
        &mut self.answers
    }

    pub fn authorities_mut(&mut self) -> &mut Vec<DnsRecordBox> {
        &mut self.authorities
    }

    pub fn additionals_mut(&mut self) -> &mut Vec<DnsRecordBox> {
        &mut self.additional
    }

    pub fn all_records(self) -> impl Iterator<Item = DnsRecordBox> {
        self.answers
            .into_iter()
            .chain(self.authorities)
            .chain(self.additional)
    }

    pub fn num_additionals(&self) -> u16 {
        self.num_additionals
    }

    pub fn num_authorities(&self) -> u16 {
        self.num_authorities
    }

    pub fn num_questions(&self) -> u16 {
        self.num_questions
    }

    pub const fn is_query(&self) -> bool {
        (self.flags & FLAGS_QR_MASK) == FLAGS_QR_QUERY
    }

    pub const fn is_response(&self) -> bool {
        (self.flags & FLAGS_QR_MASK) == FLAGS_QR_RESPONSE
    }

    fn read_header(&mut self) -> Result<()> {
        if self.data.len() < MSG_HEADER_LEN {
            return Err(e_fmt!(
                "DNS incoming: header is too short: {} bytes",
                self.data.len()
            ));
        }

        let data = &self.data[0..];
        self.id = u16_from_be_slice(&data[..2]);
        self.flags = u16_from_be_slice(&data[2..4]);
        self.num_questions = u16_from_be_slice(&data[4..6]);
        self.num_answers = u16_from_be_slice(&data[6..8]);
        self.num_authorities = u16_from_be_slice(&data[8..10]);
        self.num_additionals = u16_from_be_slice(&data[10..12]);

        self.offset = MSG_HEADER_LEN;

        trace!(
            "read_header: id {}, {} questions {} answers {} authorities {} additionals",
            self.id,
            self.num_questions,
            self.num_answers,
            self.num_authorities,
            self.num_additionals
        );
        Ok(())
    }

    fn read_questions(&mut self) -> Result<()> {
        trace!("read_questions: {}", &self.num_questions);
        for i in 0..self.num_questions {
            let name = self.read_name()?;

            let data = &self.data[self.offset..];
            if data.len() < 4 {
                return Err(Error::Msg(format!(
                    "DNS incoming: question idx {} too short: {}",
                    i,
                    data.len()
                )));
            }
            let ty = u16_from_be_slice(&data[..2]);
            let class = u16_from_be_slice(&data[2..4]);
            self.offset += 4;

            let Some(rr_type) = RRType::from_u16(ty) else {
                return Err(Error::Msg(format!(
                    "DNS incoming: question idx {i} qtype unknown: {ty}",
                )));
            };

            self.questions.push(DnsQuestion {
                entry: DnsEntry::new(name, rr_type, class),
            });
        }
        Ok(())
    }

    fn read_answers(&mut self) -> Result<()> {
        self.answers = self.read_rr_records(self.num_answers)?;
        Ok(())
    }

    fn read_authorities(&mut self) -> Result<()> {
        self.authorities = self.read_rr_records(self.num_authorities)?;
        Ok(())
    }

    fn read_additional(&mut self) -> Result<()> {
        self.additional = self.read_rr_records(self.num_additionals)?;
        Ok(())
    }

    /// Decodes a sequence of RR records (in answers, authorities and additionals).
    fn read_rr_records(&mut self, count: u16) -> Result<Vec<DnsRecordBox>> {
        trace!("read_rr_records: {}", count);
        let mut rr_records = Vec::new();

        // RFC 1035: https://datatracker.ietf.org/doc/html/rfc1035#section-3.2.1
        //
        // All RRs have the same top level format shown below:
        //                               1  1  1  1  1  1
        // 0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        // |                                               |
        // /                                               /
        // /                      NAME                     /
        // |                                               |
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        // |                      TYPE                     |
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        // |                     CLASS                     |
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        // |                      TTL                      |
        // |                                               |
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        // |                   RDLENGTH                    |
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
        // /                     RDATA                     /
        // /                                               /
        // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

        // Muse have at least TYPE, CLASS, TTL, RDLENGTH fields: 10 bytes.
        const RR_HEADER_REMAIN: usize = 10;

        for _ in 0..count {
            let name = self.read_name()?;
            let slice = &self.data[self.offset..];

            if slice.len() < RR_HEADER_REMAIN {
                return Err(Error::Msg(format!(
                    "read_others: RR '{}' is too short after name: {} bytes",
                    &name,
                    slice.len()
                )));
            }

            let ty = u16_from_be_slice(&slice[..2]);
            let class = u16_from_be_slice(&slice[2..4]);
            let mut ttl = u32_from_be_slice(&slice[4..8]);
            if ttl == 0 && self.is_response() {
                // RFC 6762 section 10.1:
                // "...Queriers receiving a Multicast DNS response with a TTL of zero SHOULD
                // NOT immediately delete the record from the cache, but instead record
                // a TTL of 1 and then delete the record one second later."
                // See https://datatracker.ietf.org/doc/html/rfc6762#section-10.1

                ttl = 1;
            }
            let rdata_len = u16_from_be_slice(&slice[8..10]) as usize;
            self.offset += RR_HEADER_REMAIN;
            let next_offset = self.offset + rdata_len;

            // Sanity check for RDATA length.
            if next_offset > self.data.len() {
                return Err(Error::Msg(format!(
                    "RR {name} RDATA length {rdata_len} is invalid: remain data len: {}",
                    self.data.len() - self.offset
                )));
            }

            // decode RDATA based on the record type.
            let rec: Option<DnsRecordBox> = match RRType::from_u16(ty) {
                None => None,

                Some(rr_type) => match rr_type {
                    RRType::CNAME | RRType::PTR => {
                        Some(DnsPointer::new(&name, rr_type, class, ttl, self.read_name()?).boxed())
                    }
                    RRType::TXT => {
                        Some(DnsTxt::new(&name, class, ttl, self.read_vec(rdata_len)?).boxed())
                    }
                    RRType::SRV => Some(
                        DnsSrv::new(
                            &name,
                            class,
                            ttl,
                            self.read_u16()?,
                            self.read_u16()?,
                            self.read_u16()?,
                            self.read_name()?,
                        )
                        .boxed(),
                    ),
                    RRType::HINFO => Some(
                        DnsHostInfo::new(
                            &name,
                            rr_type,
                            class,
                            ttl,
                            self.read_char_string()?,
                            self.read_char_string()?,
                        )
                        .boxed(),
                    ),
                    RRType::A => Some(
                        DnsAddress::new(
                            &name,
                            rr_type,
                            class,
                            ttl,
                            self.read_ipv4()?.into(),
                            self.interface_id.clone(),
                        )
                        .boxed(),
                    ),
                    RRType::AAAA => Some(
                        DnsAddress::new(
                            &name,
                            rr_type,
                            class,
                            ttl,
                            self.read_ipv6()?.into(),
                            self.interface_id.clone(),
                        )
                        .boxed(),
                    ),
                    RRType::NSEC => Some(
                        DnsNSec::new(
                            &name,
                            class,
                            ttl,
                            self.read_name()?,
                            self.read_type_bitmap()?,
                        )
                        .boxed(),
                    ),
                    _ => None,
                },
            };

            if let Some(record) = rec {
                trace!("read_rr_records: {:?}", &record);
                rr_records.push(record);
            } else {
                trace!("Unsupported DNS record type: {} name: {}", ty, &name);
                self.offset += rdata_len;
            }

            // sanity check.
            if self.offset != next_offset {
                return Err(Error::Msg(format!(
                    "read_rr_records: decode offset error for RData type {} offset: {} expected offset: {}",
                    ty, self.offset, next_offset,
                )));
            }
        }

        Ok(rr_records)
    }

    fn read_char_string(&mut self) -> Result<String> {
        let length = self.data[self.offset];
        self.offset += 1;
        self.read_string(length as usize)
    }

    fn read_u16(&mut self) -> Result<u16> {
        let slice = &self.data[self.offset..];
        if slice.len() < U16_SIZE {
            return Err(Error::Msg(format!(
                "read_u16: slice len is only {}",
                slice.len()
            )));
        }
        let num = u16_from_be_slice(&slice[..U16_SIZE]);
        self.offset += U16_SIZE;
        Ok(num)
    }

    /// Reads the "Type Bit Map" block for a DNS NSEC record.
    fn read_type_bitmap(&mut self) -> Result<Vec<u8>> {
        // From RFC 6762: 6.1.  Negative Responses
        // https://datatracker.ietf.org/doc/html/rfc6762#section-6.1
        //   o The Type Bit Map block number is 0.
        //   o The Type Bit Map block length byte is a value in the range 1-32.
        //   o The Type Bit Map data is 1-32 bytes, as indicated by length
        //     byte.

        // Sanity check: at least 2 bytes to read.
        if self.data.len() < self.offset + 2 {
            return Err(Error::Msg(format!(
                "DnsIncoming is too short: {} at NSEC Type Bit Map offset {}",
                self.data.len(),
                self.offset
            )));
        }

        let block_num = self.data[self.offset];
        self.offset += 1;
        if block_num != 0 {
            return Err(Error::Msg(format!(
                "NSEC block number is not 0: {block_num}"
            )));
        }

        let block_len = self.data[self.offset] as usize;
        if !(1..=32).contains(&block_len) {
            return Err(Error::Msg(format!(
                "NSEC block length must be in the range 1-32: {block_len}"
            )));
        }
        self.offset += 1;

        let end = self.offset + block_len;
        if end > self.data.len() {
            return Err(Error::Msg(format!(
                "NSEC block overflow: {} over RData len {}",
                end,
                self.data.len()
            )));
        }
        let bitmap = self.data[self.offset..end].to_vec();
        self.offset += block_len;

        Ok(bitmap)
    }

    fn read_vec(&mut self, length: usize) -> Result<Vec<u8>> {
        if self.data.len() < self.offset + length {
            return Err(e_fmt!(
                "DNS Incoming: not enough data to read a chunk of data"
            ));
        }

        let v = self.data[self.offset..self.offset + length].to_vec();
        self.offset += length;
        Ok(v)
    }

    fn read_ipv4(&mut self) -> Result<Ipv4Addr> {
        if self.data.len() < self.offset + 4 {
            return Err(e_fmt!("DNS Incoming: not enough data to read an IPV4"));
        }

        let bytes: [u8; 4] = self.data[self.offset..self.offset + 4]
            .try_into()
            .map_err(|_| e_fmt!("DNS incoming: Not enough bytes for reading an IPV4"))?;
        self.offset += bytes.len();
        Ok(Ipv4Addr::from(bytes))
    }

    fn read_ipv6(&mut self) -> Result<Ipv6Addr> {
        if self.data.len() < self.offset + 16 {
            return Err(e_fmt!("DNS Incoming: not enough data to read an IPV6"));
        }

        let bytes: [u8; 16] = self.data[self.offset..self.offset + 16]
            .try_into()
            .map_err(|_| e_fmt!("DNS incoming: Not enough bytes for reading an IPV6"))?;
        self.offset += bytes.len();
        Ok(Ipv6Addr::from(bytes))
    }

    fn read_string(&mut self, length: usize) -> Result<String> {
        if self.data.len() < self.offset + length {
            return Err(e_fmt!("DNS Incoming: not enough data to read a string"));
        }

        let s = str::from_utf8(&self.data[self.offset..self.offset + length])
            .map_err(|e| Error::Msg(e.to_string()))?;
        self.offset += length;
        Ok(s.to_string())
    }

    /// Reads a domain name at the current location of `self.data`.
    ///
    /// See https://datatracker.ietf.org/doc/html/rfc1035#section-3.1 for
    /// domain name encoding.
    fn read_name(&mut self) -> Result<String> {
        let data = &self.data[..];
        let start_offset = self.offset;
        let mut offset = start_offset;
        let mut name = "".to_string();
        let mut at_end = false;

        // From RFC1035:
        // "...Domain names in messages are expressed in terms of a sequence of labels.
        // Each label is represented as a one octet length field followed by that
        // number of octets."
        //
        // "...The compression scheme allows a domain name in a message to be
        // represented as either:
        // - a sequence of labels ending in a zero octet
        // - a pointer
        // - a sequence of labels ending with a pointer"
        loop {
            if offset >= data.len() {
                return Err(Error::Msg(format!(
                    "read_name: offset: {} data len {}. DnsIncoming: {:?}",
                    offset,
                    data.len(),
                    self
                )));
            }
            let length = data[offset];

            // From RFC1035:
            // "...Since every domain name ends with the null label of
            // the root, a domain name is terminated by a length byte of zero."
            if length == 0 {
                if !at_end {
                    self.offset = offset + 1;
                }
                break; // The end of the name
            }

            // Check the first 2 bits for possible "Message compression".
            match length & 0xC0 {
                0x00 => {
                    // regular utf8 string with length
                    offset += 1;
                    let ending = offset + length as usize;

                    // Never read beyond the whole data length.
                    if ending > data.len() {
                        return Err(Error::Msg(format!(
                            "read_name: ending {} exceeds data length {}",
                            ending,
                            data.len()
                        )));
                    }

                    name += str::from_utf8(&data[offset..ending])
                        .map_err(|e| Error::Msg(format!("read_name: from_utf8: {e}")))?;
                    name += ".";
                    offset += length as usize;
                }
                0xC0 => {
                    // Message compression.
                    // See https://datatracker.ietf.org/doc/html/rfc1035#section-4.1.4
                    let slice = &data[offset..];
                    if slice.len() < U16_SIZE {
                        return Err(Error::Msg(format!(
                            "read_name: u16 slice len is only {}",
                            slice.len()
                        )));
                    }
                    let pointer = (u16_from_be_slice(slice) ^ 0xC000) as usize;
                    if pointer >= start_offset {
                        // Error: could trigger an infinite loop.
                        return Err(Error::Msg(format!(
                            "Invalid name compression: pointer {} must be less than the start offset {}",
                            &pointer, &start_offset
                        )));
                    }

                    // A pointer marks the end of a domain name.
                    if !at_end {
                        self.offset = offset + U16_SIZE;
                        at_end = true;
                    }
                    offset = pointer;
                }
                _ => {
                    return Err(Error::Msg(format!(
                        "Bad name with invalid length: 0x{:x} offset {}, data (so far): {:x?}",
                        length,
                        offset,
                        &data[..offset]
                    )));
                }
            };
        }

        Ok(name)
    }
}

const fn u16_from_be_slice(bytes: &[u8]) -> u16 {
    let u8_array: [u8; 2] = [bytes[0], bytes[1]];
    u16::from_be_bytes(u8_array)
}

const fn u32_from_be_slice(s: &[u8]) -> u32 {
    let u8_array: [u8; 4] = [s[0], s[1], s[2], s[3]];
    u32::from_be_bytes(u8_array)
}

/// Returns the UNIX time in millis at which this record will have expired
/// by a certain percentage.
const fn get_expiration_time(created: u64, ttl: u32, percent: u32) -> u64 {
    // 'created' is in millis, 'ttl' is in seconds, hence:
    // ttl * 1000 * (percent / 100) => ttl * percent * 10
    created + (ttl as u64 * percent as u64 * 10)
}

#[cfg(test)]
mod tests {
    use super::{
        DnsAddress, DnsHostInfo, DnsIncoming, DnsOutgoing, DnsPointer, DnsTxt, RRType,
        CLASS_CACHE_FLUSH, CLASS_IN, MSG_HEADER_LEN,
    };
    use crate::InterfaceId;
    use std::collections::HashMap;
    use std::net::{IpAddr, Ipv4Addr};

    #[test]
    fn test_dns_outgoing_serialization_empty() {
        let out = DnsOutgoing::new(0);
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(packets[0].as_bytes(), &[0; 12]);
        let expected_names = HashMap::new();
        assert_eq!(&packets[0].names, &expected_names);
    }

    #[test]
    fn test_dns_outgoing_serialization_question() {
        let mut out = DnsOutgoing::new(0);
        out.add_question("123.test", RRType::A);
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, // Header
                // Payload
                3, 49, 50, 51, 4, 116, 101, 115, 116, 0, 0, 1, 0, 1,
            ]
        );
        let mut expected_names = HashMap::new();
        expected_names.insert("123.test".to_string(), 12);
        expected_names.insert("test".to_string(), 16);
        assert_eq!(&packets[0].names, &expected_names);
    }

    #[test]
    fn test_dns_outgoing_serialization_question_with_authority() {
        let mut out = DnsOutgoing::new(0);
        out.add_question("123.test", RRType::ANY);
        out.add_authority(Box::new(DnsTxt::new(
            "124.test",
            CLASS_IN,
            0x00112233,
            b"help".to_vec(),
        )));
        out.add_authority(Box::new(DnsHostInfo::new(
            "124.test",
            RRType::CNAME,
            CLASS_IN,
            0x00112233,
            "arm".to_string(),
            "linux".to_string(),
        )));
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, // Header
                // Payload
                3, 49, 50, 51, 4, 116, 101, 115, 116, 0, 0, 255, 0, 1, 3, 49, 50, 52, 192, 16, 0,
                16, 0, 1, 0, 17, 34, 51, 0, 4, 104, 101, 108, 112, 192, 26, 0, 5, 0, 1, 0, 17, 34,
                51, 0, 8, 97, 114, 109, 108, 105, 110, 117, 120,
            ]
        );
        let mut expected_names = HashMap::new();
        expected_names.insert("123.test".to_string(), 12);
        expected_names.insert("test".to_string(), 16);
        expected_names.insert("124.test".to_string(), 26);
        assert_eq!(&packets[0].names, &expected_names);
    }

    #[test]
    fn test_dns_outgoing_serialization_additional_answer() {
        let mut out = DnsOutgoing::new(0);
        out.add_additional_answer(DnsAddress::new(
            "test.local",
            RRType::A,
            CLASS_IN | CLASS_CACHE_FLUSH,
            0xdead_beef,
            IpAddr::V4(Ipv4Addr::new(127, 0, 0, 1)),
            InterfaceId::default(),
        ));
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, // Header
                // Payload
                4, 116, 101, 115, 116, 5, 108, 111, 99, 97, 108, 0, 0, 1, 128, 1, 222, 173, 190,
                239, 0, 4, 127, 0, 0, 1,
            ]
        );
        let mut expected_names = HashMap::new();
        expected_names.insert("test.local".to_string(), 12);
        expected_names.insert("local".to_string(), 17);
        assert_eq!(&packets[0].names, &expected_names);
    }

    #[test]
    fn test_dns_outgoing_serialization_answer_at_time() {
        let mut out = DnsOutgoing::new(0);
        out.add_answer_at_time(
            DnsPointer::new(
                "test",
                RRType::PTR,
                CLASS_IN,
                0xaaaa5555,
                "test-service".to_string(),
            ),
            0,
        );
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, // Header
                // Payload
                4, 116, 101, 115, 116, 0, 0, 12, 0, 1, 170, 170, 85, 85, 0, 14, 12, 116, 101, 115,
                116, 45, 115, 101, 114, 118, 105, 99, 101, 0,
            ]
        );

        let mut out = DnsOutgoing::new(0);
        out.add_answer_at_time(
            DnsPointer::new(
                "test",
                RRType::CNAME,
                CLASS_IN,
                0xaaaa5555,
                "test-service.local".to_string(),
            ),
            0,
        );
        out.add_answer_at_time(
            DnsPointer::new(
                "test",
                RRType::AAAA,
                CLASS_IN,
                0xffffffff,
                "test-service.local".to_string(),
            ),
            0,
        );
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, // Header
                // Payload
                4, 116, 101, 115, 116, 0, 0, 5, 0, 1, 170, 170, 85, 85, 0, 20, 12, 116, 101, 115,
                116, 45, 115, 101, 114, 118, 105, 99, 101, 5, 108, 111, 99, 97, 108, 0, 192, 12, 0,
                28, 0, 1, 255, 255, 255, 255, 0, 2, 192, 28,
            ]
        );
        let mut expected_names = HashMap::new();
        expected_names.insert("test".to_string(), 12);
        expected_names.insert("test-service.local".to_string(), 28);
        expected_names.insert("local".to_string(), 41);
        assert_eq!(&packets[0].names, &expected_names);
    }

    /// A question whose name has a label longer than 63 bytes cannot be
    /// encoded. It must be skipped, not panic. (Note the question count in the
    /// header must reflect the questions actually written.)
    #[test]
    fn test_dns_outgoing_question_label_too_long() {
        let long_label = "a".repeat(64);
        let mut out = DnsOutgoing::new(0);
        out.add_question(&format!("{long_label}.local"), RRType::PTR);
        out.add_question("123.test", RRType::A);

        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(
            packets[0].as_bytes(),
            &[
                0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, // Header: 1 question
                // Payload: only "123.test" made it in.
                3, 49, 50, 51, 4, 116, 101, 115, 116, 0, 0, 1, 0, 1,
            ]
        );

        // The rolled back name must not leave a stale compression offset behind.
        let mut expected_names = HashMap::new();
        expected_names.insert("123.test".to_string(), 12);
        expected_names.insert("test".to_string(), 16);
        assert_eq!(&packets[0].names, &expected_names);
    }

    /// A record whose rdata carries an unencodable name (here a PTR alias) is
    /// dropped as a whole, leaving the rest of the packet intact.
    #[test]
    fn test_dns_outgoing_record_label_too_long() {
        let long_label = "a".repeat(64);
        let mut out = DnsOutgoing::new(0);
        out.add_answer_at_time(
            DnsPointer::new(
                "_test._tcp.local.",
                RRType::PTR,
                CLASS_IN,
                0,
                format!("{long_label}._test._tcp.local."),
            ),
            0,
        );
        out.add_answer_at_time(
            DnsPointer::new(
                "_test._tcp.local.",
                RRType::PTR,
                CLASS_IN,
                0,
                "ok._test._tcp.local.".to_string(),
            ),
            0,
        );

        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);

        // Header answer count is 1: the first answer was dropped.
        assert_eq!(&packets[0].as_bytes()[6..8], &[0, 1]);

        // Re-parsing must succeed and yield only the good answer.
        let incoming = DnsIncoming::new(
            packets[0].as_bytes().to_vec(),
            InterfaceId {
                name: "test".to_string(),
                index: 1,
            },
        )
        .unwrap();
        assert_eq!(incoming.answers().len(), 1);
    }

    /// A name learned from the network can hold a label that ends with a
    /// backslash, which escapes the following label separator. Unescaping such
    /// a name on the way out merges two 63-byte labels into a 127-byte one.
    /// This used to panic the daemon thread. See issue #483.
    #[test]
    fn test_incoming_name_with_merged_labels_does_not_panic() {
        // A query with one question: "aa..a\" + "bb..b", 63 bytes each.
        let mut data: Vec<u8> = vec![0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0];
        data.push(63);
        data.extend(vec![b'a'; 62]);
        data.push(b'\\');
        data.push(63);
        data.extend(vec![b'b'; 63]);
        data.push(0);
        data.extend([0, 12, 0, 1]); // PTR, IN

        let incoming = DnsIncoming::new(
            data,
            InterfaceId {
                name: "test".to_string(),
                index: 1,
            },
        )
        .unwrap();
        let name = incoming.questions()[0].entry.name.clone();

        // The two labels merged: the trailing backslash escaped the separator.
        assert!(name.starts_with("aaa"));
        assert!(name.contains("\\.bbb"));

        // Re-emitting it must drop the question rather than panic.
        let mut out = DnsOutgoing::new(0);
        out.add_question(&name, RRType::PTR);
        let packets = out.to_packets();
        assert_eq!(packets.len(), 1);
        assert_eq!(packets[0].as_bytes(), &[0; MSG_HEADER_LEN]);
    }
}