trust_dns_proto/rr/

type_bit_map.rs

// Copyright 2015-2021 Benjamin Fry <benjaminfry@me.com>
//
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
// http://opensource.org/licenses/MIT>, at your option. This file may not be
// copied, modified, or distributed except according to those terms.

//! type bit map helper definitions

use crate::error::*;
use crate::rr::RecordType;
use crate::serialize::binary::*;
use std::collections::BTreeMap;

enum BitMapReadState {
    Window,
    Len {
        window: u8,
    },
    RecordType {
        window: u8,
        len: Restrict<u8>,
        left: Restrict<u8>,
    },
}

/// Encode the bit map
///
/// # Arguments
///
/// * `encoder` - the encoder to write to
/// * `type_bit_maps` - types to encode into the bitmap
pub(crate) fn encode_type_bit_maps(
    encoder: &mut BinEncoder<'_>,
    type_bit_maps: &[RecordType],
) -> ProtoResult<()> {
    let mut hash: BTreeMap<u8, Vec<u8>> = BTreeMap::new();
    let mut type_bit_maps = type_bit_maps.to_vec();
    type_bit_maps.sort();

    // collect the bitmaps
    for rr_type in type_bit_maps {
        let code: u16 = (rr_type).into();
        let window: u8 = (code >> 8) as u8;
        let low: u8 = (code & 0x00FF) as u8;

        let bit_map: &mut Vec<u8> = hash.entry(window).or_insert_with(Vec::new);
        // len + left is the block in the bitmap, divided by 8 for the bits, + the bit in the current_byte
        let index: u8 = low / 8;
        let bit: u8 = 0b1000_0000 >> (low % 8);

        // adding necessary space to the vector
        if bit_map.len() < (index as usize + 1) {
            bit_map.resize(index as usize + 1, 0_u8);
        }

        bit_map[index as usize] |= bit;
    }

    // output bitmaps
    for (window, bitmap) in hash {
        encoder.emit(window)?;
        // the hashset should never be larger that 255 based on above logic.
        encoder.emit(bitmap.len() as u8)?;
        for bits in bitmap {
            encoder.emit(bits)?;
        }
    }

    Ok(())
}

/// Decodes the array of RecordTypes covered by this NSEC record
///
/// # Arguments
///
/// * `decoder` - decoder to read from
/// * `bit_map_len` - the number bytes in the bit map
///
/// # Returns
///
/// The Array of covered types
pub(crate) fn decode_type_bit_maps(
    decoder: &mut BinDecoder<'_>,
    bit_map_len: Restrict<usize>,
) -> ProtoResult<Vec<RecordType>> {
    // 3.2.1.  Type Bit Maps Encoding
    //
    //  The encoding of the Type Bit Maps field is the same as that used by
    //  the NSEC RR, described in [RFC4034].  It is explained and clarified
    //  here for clarity.
    //
    //  The RR type space is split into 256 window blocks, each representing
    //  the low-order 8 bits of the 16-bit RR type space.  Each block that
    //  has at least one active RR type is encoded using a single octet
    //  window number (from 0 to 255), a single octet bitmap length (from 1
    //  to 32) indicating the number of octets used for the bitmap of the
    //  window block, and up to 32 octets (256 bits) of bitmap.
    //
    //  Blocks are present in the NSEC3 RR RDATA in increasing numerical
    //  order.
    //
    //     Type Bit Maps Field = ( Window Block # | Bitmap Length | Bitmap )+
    //
    //     where "|" denotes concatenation.
    //
    //  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.  For window block 1, bit 1
    //  corresponds to RR type 257, bit 2 to RR type 258.  If a bit is set to
    //  1, it indicates that an RRSet of that type is present for the
    //  original owner name of the NSEC3 RR.  If a bit is set to 0, it
    //  indicates that no RRSet of that type is present for the original
    //  owner name of the NSEC3 RR.
    //
    //  Since bit 0 in window block 0 refers to the non-existing RR type 0,
    //  it MUST be set to 0.  After verification, the validator MUST ignore
    //  the value of bit 0 in window block 0.
    //
    //  Bits representing Meta-TYPEs or QTYPEs as specified in Section 3.1 of
    //  [RFC2929] or within the range reserved for assignment only to QTYPEs
    //  and Meta-TYPEs MUST be set to 0, since they do not appear in zone
    //  data.  If encountered, they must be ignored upon reading.
    //
    //  Blocks with no types present MUST NOT be included.  Trailing zero
    //  octets in the bitmap MUST be omitted.  The length of the bitmap of
    //  each block is determined by the type code with the largest numerical
    //  value, within that block, among the set of RR types present at the
    //  original owner name of the NSEC3 RR.  Trailing octets not specified
    //  MUST be interpreted as zero octets.
    let mut record_types: Vec<RecordType> = Vec::new();
    let mut state: BitMapReadState = BitMapReadState::Window;

    // loop through all the bytes in the bitmap
    for _ in 0..bit_map_len.unverified(/*bounded over any length of u16*/) {
        let current_byte = decoder.read_u8()?;

        state = match state {
            BitMapReadState::Window => BitMapReadState::Len {
                window: current_byte.unverified(/*window is any valid u8,*/),
            },
            BitMapReadState::Len { window } => BitMapReadState::RecordType {
                window,
                len: current_byte,
                left: current_byte,
            },
            BitMapReadState::RecordType { window, len, left } => {
                // window is the Window Block # from above
                // len is the Bitmap Length
                // current_byte is the Bitmap
                let mut bit_map = current_byte.unverified(/*validated and restricted in usage in following usage*/);

                // for all the bits in the current_byte
                for i in 0..8 {
                    // if the current_bytes most significant bit is set
                    if bit_map & 0b1000_0000 == 0b1000_0000 {
                        // len - left is the block in the bitmap, times 8 for the bits, + the bit in the current_byte
                        let low_byte: u8 = len
                            .checked_sub(left.unverified(/*will fail as param in this call if invalid*/))
                            .checked_mul(8)
                            .checked_add(i)
                            .map_err(|_| "block len or left out of bounds in NSEC(3)")?
                            .unverified(/*any u8 is valid at this point*/);
                        let rr_type: u16 = (u16::from(window) << 8) | u16::from(low_byte);
                        record_types.push(RecordType::from(rr_type));
                    }
                    // shift left and look at the next bit
                    bit_map <<= 1;
                }

                // move to the next section of the bit_map
                let left = left
                    .checked_sub(1)
                    .map_err(|_| ProtoError::from("block left out of bounds in NSEC(3)"))?;
                if left.unverified(/*comparison is safe*/) == 0 {
                    // we've exhausted this Window, move to the next
                    BitMapReadState::Window
                } else {
                    // continue reading this Window
                    BitMapReadState::RecordType { window, len, left }
                }
            }
        };
    }

    Ok(record_types)
}

#[cfg(test)]
mod tests {
    #![allow(clippy::dbg_macro, clippy::print_stdout)]

    use super::*;

    #[test]
    fn test_encode_decode() {
        let types = vec![RecordType::A, RecordType::NS];

        let mut bytes = Vec::new();
        let mut encoder: BinEncoder<'_> = BinEncoder::new(&mut bytes);
        assert!(encode_type_bit_maps(&mut encoder, &types).is_ok());
        let bytes = encoder.into_bytes();

        let mut decoder: BinDecoder<'_> = BinDecoder::new(bytes);
        let restrict = Restrict::new(bytes.len());
        let read_bit_map = decode_type_bit_maps(&mut decoder, restrict).expect("Decoding error");
        assert_eq!(types, read_bit_map);
    }
}