rasn 0.29.0

//! Decoding Packed Encoding Rules data into Rust structures.

use alloc::{string::ToString, vec::Vec};

use super::{
    FOURTY_EIGHT_K, LARGE_UNSIGNED_CONSTRAINT, SIXTEEN_K, SIXTY_FOUR_K, SMALL_UNSIGNED_CONSTRAINT,
    THIRTY_TWO_K,
};
use crate::{
    Decode,
    de::Error as _,
    types::{
        self, Constraints, Enumerated, IntegerType, SetOf, Tag,
        constraints::{self, Extensible},
        fields::{Field, Fields},
        strings::{CharacterAlphabet, StaticPermittedAlphabet},
    },
};

pub use crate::error::DecodeError;
use crate::error::DecodeErrorKind;
type Result<T, E = DecodeError> = core::result::Result<T, E>;

type InputSlice<'input> = crate::bits::BitReader<'input>;

/// Splits off the first `count` bits of `input`, advancing it past them.
#[inline]
fn take<'input>(
    input: &mut InputSlice<'input>,
    count: usize,
    codec: crate::Codec,
) -> Result<InputSlice<'input>> {
    input
        .split(count)
        .map_err(|missing| DecodeError::incomplete(nom::Needed::new(missing), codec))
}

/// The bits of an open type: a single fragment is read in place, while a
/// value of 16K octets or more arrives in fragments that are gathered.
enum OpenType<'input> {
    Empty,
    Borrowed(InputSlice<'input>),
    Gathered(types::BitString),
}

impl OpenType<'_> {
    fn bits(&self) -> &types::BitStr {
        match self {
            Self::Empty => types::BitStr::empty(),
            Self::Borrowed(reader) => reader.bits(),
            Self::Gathered(bits) => bits,
        }
    }

    fn reader(&self) -> InputSlice<'_> {
        match self {
            Self::Empty => InputSlice::new(types::BitStr::empty()),
            Self::Borrowed(reader) => *reader,
            Self::Gathered(bits) => InputSlice::new(bits),
        }
    }

    /// The octets, borrowed when they lie on octet boundaries.
    fn octets(&self) -> alloc::borrow::Cow<'_, [u8]> {
        self.reader().octets()
    }
}

/// Options for configuring the [`Decoder`].
#[derive(Clone, Copy, Debug)]
pub struct DecoderOptions {
    #[allow(unused)]
    aligned: bool,
    // limit decoding to prevent stack overflow from deep or circular references
    remaining_depth: usize,
}

impl DecoderOptions {
    /// Returns the default decoding rules options for Aligned Packed Encoding Rules.
    #[must_use]
    pub fn aligned() -> Self {
        Self {
            aligned: true,
            remaining_depth: 128,
        }
    }

    /// Returns the default decoding rules options for unaligned Packed Encoding Rules.
    #[must_use]
    pub fn unaligned() -> Self {
        Self {
            aligned: false,
            remaining_depth: 128,
        }
    }

    #[must_use]
    fn current_codec(self) -> crate::Codec {
        if self.aligned {
            crate::Codec::Aper
        } else {
            crate::Codec::Uper
        }
    }
}

/// Decodes Packed Encoding Rules (PER) data into Rust data structures.
pub struct Decoder<'input, const RFC: usize = 0, const EFC: usize = 0> {
    input: InputSlice<'input>,
    options: DecoderOptions,
    /// Presence bitmap for optional/default root fields. The cursor advances as each
    /// field is consumed; `None` entries mark slots past the filled count.
    fields: (usize, [Option<(Field, bool)>; RFC]),
    extension_fields: Option<Fields<EFC>>,
    /// Presence bitmap for extension fields. `None` outer = not extensible;
    /// `Some(None)` = extensible but header not yet parsed;
    /// `Some(Some((cursor, data)))` = header parsed.
    #[allow(clippy::type_complexity)]
    extensions_present: Option<Option<(usize, [Option<(Field, bool)>; EFC])>>,
}

impl<'input, const RFC: usize, const EFC: usize> Decoder<'input, RFC, EFC> {
    /// Returns the currently selected codec.
    #[must_use]
    pub fn codec(&self) -> crate::Codec {
        self.options.current_codec()
    }

    /// Creates a new Decoder from the given input and options.
    #[must_use]
    pub fn new(input: &'input crate::types::BitStr, options: DecoderOptions) -> Self {
        Self::from_reader(InputSlice::new(input), options)
    }

    /// Creates a decoder over `octets`.
    pub(crate) fn from_octets(octets: &'input [u8], options: DecoderOptions) -> Self {
        Self::from_reader(InputSlice::from_octets(octets), options)
    }

    /// Creates a decoder that continues from `input`.
    fn from_reader(input: InputSlice<'input>, options: DecoderOptions) -> Self {
        Self {
            input,
            options,
            fields: (0, [None; RFC]),
            extension_fields: None,
            extensions_present: None,
        }
    }

    /// Returns the remaining input, if any.
    #[must_use]
    pub fn input(&self) -> &'input crate::types::BitStr {
        self.input.bits()
    }

    #[track_caller]
    fn require_field(&mut self, tag: Tag) -> Result<bool> {
        let cursor = self.fields.0;
        match self.fields.1.get(cursor).copied().flatten() {
            Some((field, bit)) if field.tag_tree.smallest_tag() == tag => {
                self.fields.0 += 1;
                Ok(bit)
            }
            _ => Err(DecodeError::missing_tag_class_or_value_in_sequence_or_set(
                tag.class,
                tag.value,
                self.codec(),
            )),
        }
    }

    fn parse_extensible_bit(&mut self, constraints: &Constraints) -> Result<bool> {
        constraints
            .extensible()
            .then(|| self.parse_one_bit())
            .transpose()
            .map(core::option::Option::unwrap_or_default)
    }

    fn extension_is_present(&mut self) -> Result<Option<(Field, bool)>> {
        let codec = self.codec();
        let inner = self
            .extensions_present
            .as_mut()
            .ok_or_else(|| DecodeError::type_not_extensible(codec))?
            .as_mut()
            .ok_or_else(|| DecodeError::type_not_extensible(codec))?;
        let cursor = inner.0;
        let result = inner.1.get(cursor).copied().flatten();
        if result.is_some() {
            inner.0 += 1;
        }
        Ok(result)
    }

    fn parse_padding(&self, input: InputSlice<'input>) -> Result<InputSlice<'input>> {
        if self.options.aligned {
            self.force_parse_padding(input)
        } else {
            Ok(input)
        }
    }

    fn force_parse_padding(&self, input: InputSlice<'input>) -> Result<InputSlice<'input>> {
        if input.len().is_multiple_of(8) {
            Ok(input)
        } else {
            let mut input = input;
            let padding = input.len() % 8;
            take(&mut input, padding, self.codec())?;
            Ok(input)
        }
    }

    fn parse_optional_and_default_field_bitmap<const RC: usize>(
        &mut self,
        fields: &Fields<RC>,
    ) -> Result<&'input types::BitStr> {
        let codec = self.codec();
        let bitset = take(
            &mut self.input,
            fields.number_of_optional_and_default_fields(),
            codec,
        )?;
        Ok(bitset.bits())
    }

    fn decode_extensible_string(
        &mut self,
        constraints: &Constraints,
        is_large_string: bool,
        mut decode_fn: impl FnMut(InputSlice<'input>, usize) -> Result<InputSlice<'input>>,
    ) -> Result<()> {
        let extensible_is_present = self.parse_extensible_bit(constraints)?;
        let size = constraints.size().filter(|_| !extensible_is_present);
        let mut total_length = 0usize;
        let input =
            self.decode_string_length(self.input, size, is_large_string, &mut |input, length| {
                total_length += length;
                decode_fn(input, length)
            })?;
        self.input = input;
        self.check_size(size, total_length)
    }

    fn decode_extensible_container(
        &mut self,
        constraints: &Constraints,
        mut decode_fn: impl FnMut(InputSlice<'input>, usize) -> Result<InputSlice<'input>>,
    ) -> Result<()> {
        let extensible_is_present = self.parse_extensible_bit(constraints)?;
        let size = constraints.size().filter(|_| !extensible_is_present);
        let mut total_length = 0usize;
        let input = self.decode_length(self.input, size, &mut |input, length| {
            total_length += length;
            decode_fn(input, length)
        })?;
        self.input = input;
        self.check_size(size, total_length)
    }

    /// The bits of a length-prefixed open type, borrowed from the input.
    /// Only a value of 16K octets or more, which arrives in fragments, has to
    /// be gathered into a copy.
    fn decode_open_type(&mut self) -> Result<OpenType<'input>> {
        let mut open = OpenType::Empty;
        let codec = self.codec();

        let input = self.decode_length(self.input, <_>::default(), &mut |mut input, length| {
            let data = take(&mut input, length * 8, codec)?;
            open = match core::mem::replace(&mut open, OpenType::Empty) {
                OpenType::Empty => OpenType::Borrowed(data),
                previous => {
                    let mut gathered = types::BitString::new();
                    crate::bits::extend_bitstring(&mut gathered, previous.bits());
                    crate::bits::extend_bitstring(&mut gathered, data.bits());
                    OpenType::Gathered(gathered)
                }
            };
            Ok(input)
        })?;

        self.input = input;
        Ok(open)
    }

    fn decode_unknown_length(
        &mut self,
        mut input: InputSlice<'input>,
        decode_fn: &mut impl FnMut(InputSlice<'input>, usize) -> Result<InputSlice<'input>>,
    ) -> Result<InputSlice<'input>> {
        // ITU-T X.691 (02/2021) §11.9.3.8: a 16K..64K fragment is always followed by
        // another length determinant, either a further fragment or the final (possibly
        // zero) length. Iterate rather than recurse so that a long chain of fragments
        // cannot exhaust the stack.
        loop {
            input = self.parse_padding(input)?;
            let codec = self.codec();

            if !take(&mut input, 1, codec)?.first_bit() {
                let length = take(&mut input, 7, codec)?.first_bits(7) as usize;
                return (decode_fn)(input, length);
            }

            if !take(&mut input, 1, codec)?.first_bit() {
                let length = take(&mut input, 14, codec)?.first_bits(14) as usize;
                return (decode_fn)(input, length);
            }

            let length: usize = match take(&mut input, 6, codec)?.first_bits(6) {
                1 => SIXTEEN_K.into(),
                2 => THIRTY_TWO_K.into(),
                3 => FOURTY_EIGHT_K.into(),
                4 => SIXTY_FOUR_K as usize,
                _ => {
                    return Err(DecodeError::parser_fail(
                        "Invalid length fragment".into(),
                        self.codec(),
                    ));
                }
            };

            input = (decode_fn)(input, length)?;
        }
    }

    fn decode_string_length(
        &mut self,
        mut input: InputSlice<'input>,
        constraints: Option<&Extensible<constraints::Size>>,
        is_large_string: bool,
        decode_fn: &mut impl FnMut(InputSlice<'input>, usize) -> Result<InputSlice<'input>>,
    ) -> Result<InputSlice<'input>> {
        let Some(constraints) = constraints else {
            return self.decode_unknown_length(input, decode_fn);
        };

        let size_constraint = constraints.constraint;
        if let Some(range) = size_constraint
            .range()
            .filter(|range| *range <= SIXTY_FOUR_K as usize)
        {
            if range == 0 {
                Ok(input)
            } else if range == 1 {
                if self.options.aligned {
                    input = self.parse_padding(input)?;
                }
                (decode_fn)(input, size_constraint.minimum())
            } else {
                let range = if self.options.aligned && range > 256 {
                    input = self.parse_padding(input)?;
                    let range = crate::num::log2(range as i128);
                    crate::bits::range_from_len(if range.is_power_of_two() {
                        range
                    } else {
                        range.next_power_of_two()
                    })
                } else {
                    range as i128
                };

                let bits = crate::num::log2(range) as usize;
                let length = take(&mut input, bits, self.codec())?;
                if is_large_string {
                    input = self.parse_padding(input)?;
                }
                (length.first_bits(bits) as usize)
                    .checked_add(size_constraint.minimum())
                    .ok_or_else(|| DecodeError::exceeds_max_length(usize::MAX.into(), self.codec()))
                    .and_then(|sum| (decode_fn)(input, sum))
            }
        } else {
            self.decode_unknown_length(input, decode_fn)
        }
    }

    fn decode_length(
        &mut self,
        mut input: InputSlice<'input>,
        constraints: Option<&Extensible<constraints::Size>>,
        decode_fn: &mut impl FnMut(InputSlice<'input>, usize) -> Result<InputSlice<'input>>,
    ) -> Result<InputSlice<'input>> {
        let Some(constraints) = constraints else {
            return self.decode_unknown_length(input, decode_fn);
        };

        let size_constraint = constraints.constraint;
        if let Some(range) = size_constraint
            .range()
            .filter(|range| *range <= SIXTY_FOUR_K as usize)
        {
            if range == 0 {
                Ok(input)
            } else if range == 1 {
                (decode_fn)(input, size_constraint.minimum())
            } else {
                let range = if self.options.aligned && range > 256 {
                    input = self.parse_padding(input)?;
                    let range = crate::num::log2(range as i128);
                    crate::bits::range_from_len(if range.is_power_of_two() {
                        range
                    } else {
                        range.next_power_of_two()
                    })
                } else {
                    range as i128
                };

                let bits = crate::num::log2(range) as usize;
                let length = take(&mut input, bits, self.codec())?;
                input = self.parse_padding(input)?;
                (length.first_bits(bits) as usize)
                    .checked_add(size_constraint.minimum())
                    .ok_or_else(|| DecodeError::exceeds_max_length(usize::MAX.into(), self.codec()))
                    .and_then(|sum| (decode_fn)(input, sum))
            }
        } else {
            self.decode_unknown_length(input, decode_fn)
        }
    }

    fn parse_one_bit(&mut self) -> Result<bool> {
        let codec = self.codec();
        Ok(take(&mut self.input, 1, codec)?.first_bit())
    }

    fn parse_normally_small_integer<I: IntegerType>(&mut self) -> Result<I> {
        let is_large = self.parse_one_bit()?;
        if is_large {
            self.parse_integer::<I>(&LARGE_UNSIGNED_CONSTRAINT)
        } else {
            self.parse_integer::<I>(&SMALL_UNSIGNED_CONSTRAINT)
        }
    }
    fn parse_normally_small_length(&mut self) -> Result<usize> {
        let is_large = self.parse_one_bit()?;
        if !is_large {
            self.parse_integer::<usize>(&SMALL_UNSIGNED_CONSTRAINT)
        } else {
            let mut length_out = 0usize;
            let input = self.decode_unknown_length(self.input, &mut |input, length| {
                length_out = length;
                Ok(input)
            })?;
            self.input = input;
            Ok(length_out)
        }
    }

    fn parse_non_negative_binary_integer<I: types::IntegerType>(
        &mut self,
        range: i128,
    ) -> Result<I> {
        self.parse_non_negative_binary_integer_bits(crate::num::log2(range) as usize)
    }

    fn parse_non_negative_binary_integer_bits<I: types::IntegerType>(
        &mut self,
        bits: usize,
    ) -> Result<I> {
        let codec = self.codec();
        let data = take(&mut self.input, bits, codec)?;
        if bits == 0 {
            return Ok(I::ZERO);
        }
        let value = data.first_u128(bits);
        match i128::try_from(value) {
            Ok(value) => I::try_from(value)
                .map_err(|_| DecodeError::integer_overflow(I::WIDTH, self.codec())),
            Err(_) => I::try_from_unsigned_bytes(&value.to_be_bytes(), self.codec()),
        }
    }

    fn parse_integer<I: types::IntegerType>(&mut self, constraints: &Constraints) -> Result<I> {
        self.parse_integer_with_extension_bit(constraints)
            .map(|(value, _)| value)
    }

    fn parse_integer_with_extension_bit<I: types::IntegerType>(
        &mut self,
        constraints: &Constraints,
    ) -> Result<(I, bool)> {
        let extension_is_present = self.parse_extensible_bit(constraints)?;
        let value_constraint = constraints.value();

        let Some(value_constraint) = value_constraint.filter(|_| !extension_is_present) else {
            let open = self.decode_open_type()?;
            let octets = open.octets();
            return I::try_from_bytes(&octets, self.codec())
                .map(|value| (value, extension_is_present));
        };

        const K64: i128 = SIXTY_FOUR_K as i128;
        const OVER_K64: i128 = K64 + 1;

        // Doing .map_error here causes 5% performance regression for unknown reason
        // It would make code cleaner though
        let minimum: I = match value_constraint.constraint.minimum().try_into() {
            Ok(value) => value,
            Err(_) => return Err(DecodeError::integer_overflow(I::WIDTH, self.codec())),
        };

        let number = if let Some(range) = value_constraint.constraint.range() {
            match (self.options.aligned, range) {
                (_, 0) => return Ok((minimum, extension_is_present)),
                (true, 256) => {
                    self.input = self.parse_padding(self.input)?;
                    self.parse_non_negative_binary_integer::<I::UnsignedPair>(range)?
                }
                (true, 257..=K64) => {
                    self.input = self.parse_padding(self.input)?;
                    self.parse_non_negative_binary_integer::<I::UnsignedPair>(K64)?
                }
                (true, OVER_K64..) => {
                    let range_len_in_bytes =
                        num_integer::div_ceil(crate::num::log2(range), 8) as i128;
                    let length: u32 = self.parse_non_negative_binary_integer(range_len_in_bytes)?;
                    self.input = self.parse_padding(self.input)?;
                    let range = length
                        .checked_add(1)
                        .ok_or_else(|| {
                            DecodeError::exceeds_max_length(u32::MAX.into(), self.codec())
                        })?
                        .checked_mul(8)
                        .ok_or_else(|| {
                            DecodeError::exceeds_max_length(u32::MAX.into(), self.codec())
                        })?;
                    self.parse_non_negative_binary_integer::<I::UnsignedPair>(
                        crate::bits::range_from_len(range),
                    )?
                }
                (_, _) => {
                    let bits = if I::WIDTH <= 16 && range == (1i128 << I::WIDTH) {
                        I::WIDTH as usize
                    } else {
                        crate::num::log2(range) as usize
                    };
                    self.parse_non_negative_binary_integer_bits::<I::UnsignedPair>(bits)?
                }
            }
        } else {
            let open = self.decode_open_type()?;
            let octets = open.octets();
            let number = value_constraint.constraint.as_start().map_or_else(
                || I::try_from_signed_bytes(&octets, self.codec()),
                |_| I::try_from_unsigned_bytes(&octets, self.codec()),
            )?;

            return minimum
                .checked_add(&number)
                .map(|value| (value, extension_is_present))
                .ok_or_else(|| DecodeError::integer_overflow(I::WIDTH, self.codec()));
        };

        Ok((minimum.wrapping_unsigned_add(number), extension_is_present))
    }

    fn parse_extension_header(&mut self) -> Result<bool> {
        match self.extensions_present {
            Some(Some(_)) => return Ok(true),
            Some(None) => (),
            None => return Ok(false),
        }

        // The length bitfield has a lower bound of `1..`
        let extensions_length = self.parse_normally_small_length()? + 1;
        let codec = self.codec();
        let bitfield = take(&mut self.input, extensions_length, codec)?;

        let mut data = [None; EFC];
        for (i, (field, bit)) in self
            .extension_fields
            .as_ref()
            .unwrap()
            .iter()
            .zip(bitfield.bits().iter().map(|b| *b))
            .enumerate()
        {
            data[i] = Some((field, bit));
        }

        for entry in &data {
            if let Some((field, is_present)) = entry
                && field.is_not_optional_or_default()
                && !is_present
            {
                return Err(DecodeError::required_extension_not_present(
                    field.tag,
                    self.codec(),
                ));
            }
        }

        self.extensions_present = Some(Some((0, data)));

        Ok(true)
    }

    fn check_recursion_depth(&self) -> Result<()> {
        if self.options.remaining_depth == 0 {
            return Err(DecodeError::from_kind(
                DecodeErrorKind::ExceedsMaxParseDepth,
                self.codec(),
            ));
        }
        Ok(())
    }

    /// Checks a decoded length against an already extension-bit-filtered size
    /// constraint, so that we don't accept lengths we would refuse to encode.
    ///
    /// PER encodes a constrained length in `log2(range)` bits, so whenever the
    /// range isn't a power of two the surplus code points would otherwise be
    /// accepted silently.
    ///
    /// `size` is `None` when the type is unconstrained, or when the extension
    /// bit signalled a length outside of the root constraint; in both cases no
    /// check applies. Mirrors the `Error::check_length` call the encoder makes
    /// in `encode_string_length`.
    fn check_size(
        &self,
        size: Option<&Extensible<constraints::Size>>,
        length: usize,
    ) -> Result<()> {
        let Some(size) = size else {
            return Ok(());
        };
        size.constraint.contains_or_else(&length, || {
            DecodeError::size_constraint_not_satisfied(
                Some(length),
                size.constraint.to_string(),
                self.codec(),
            )
        })
    }

    #[allow(clippy::too_many_lines)]
    fn parse_fixed_width_string<ALPHABET: StaticPermittedAlphabet>(
        &mut self,
        constraints: &Constraints,
    ) -> Result<ALPHABET> {
        use crate::types::constraints::Bounded;

        let mut bit_string = types::BitString::default();
        let char_width = constraints
            .permitted_alphabet()
            .map_or(ALPHABET::character_width() as usize, |alphabet| {
                crate::num::log2(alphabet.constraint.len() as i128) as usize
            });

        let char_width = if self.options.aligned && !char_width.is_power_of_two() {
            char_width.next_power_of_two()
        } else {
            char_width
        };

        let is_large_string = if let Some(size) = constraints.size() {
            match *size.constraint {
                Bounded::Range {
                    start: Some(_),
                    end: Some(_),
                } if size
                    .constraint
                    .range()
                    .unwrap()
                    .checked_mul(char_width)
                    .ok_or_else(|| {
                        DecodeError::exceeds_max_length(usize::MAX.into(), self.codec())
                    })?
                    > 16 =>
                {
                    true
                }
                Bounded::Single(max)
                    if max.checked_mul(char_width).ok_or_else(|| {
                        DecodeError::exceeds_max_length(usize::MAX.into(), self.codec())
                    })? > 16 =>
                {
                    self.input = self.parse_padding(self.input)?;
                    true
                }
                Bounded::Range {
                    start: None,
                    end: Some(max),
                } if max.checked_mul(char_width).ok_or_else(|| {
                    DecodeError::exceeds_max_length(usize::MAX.into(), self.codec())
                })? > 16 =>
                {
                    self.input = self.parse_padding(self.input)?;
                    true
                }
                _ => false,
            }
        } else {
            false
        };

        // ITU-T X.691 (02/2021) §30.5: each character is a fixed-width value or
        // alphabet index. Gather the character bits, then read them back one
        // code at a time.
        let alphabet = CharacterAlphabet::new::<ALPHABET>(
            constraints
                .permitted_alphabet()
                .map(|alphabet| alphabet.constraint.as_inner()),
            self.options.aligned,
        );
        let width = alphabet.width();
        let mut total_length = 0;
        let codec = self.codec();
        self.decode_extensible_string(constraints, is_large_string, |mut input, length| {
            total_length += length;
            let part = take(&mut input, length * width, codec)?;
            crate::bits::extend_bitstring(&mut bit_string, part.bits());
            Ok(input)
        })?;

        let bytes = bit_string.as_raw_slice();
        let mut string = ALPHABET::default();
        if width > 0 {
            // The characters' bits have all been read, so this is bounded by
            // the input.
            string.reserve(total_length);
        }
        let mut position = 0;
        for _ in 0..total_length {
            let code = crate::bits::read_bits(bytes, position, width);
            position += width;
            let ch = alphabet
                .decode(code)
                .map_err(|e| DecodeError::permitted_alphabet_error(e, codec))?;
            string.push_char(ch);
        }
        Ok(string)
    }
}
impl<'input, const RFC: usize, const EFC: usize> crate::Decoder for Decoder<'input, RFC, EFC> {
    type Ok = ();
    type Error = DecodeError;
    type AnyDecoder<const R: usize, const E: usize> = Decoder<'input, R, E>;

    fn codec(&self) -> crate::Codec {
        Self::codec(self)
    }
    fn decode_any(&mut self, _tag: Tag) -> Result<types::Any> {
        let mut octet_string = Vec::new();
        let codec = self.codec();

        self.decode_extensible_container(&Constraints::default(), |mut input, length| {
            let part = take(&mut input, length * 8, codec)?;
            crate::bits::extend_vec_from_bitslice(&mut octet_string, part.bits());
            Ok(input)
        })?;

        Ok(types::Any::new(octet_string))
    }

    fn decode_bool(&mut self, _: Tag) -> Result<bool> {
        self.parse_one_bit()
    }

    fn decode_enumerated<E: Enumerated>(&mut self, _: Tag) -> Result<E> {
        let extensible = E::EXTENDED_VARIANTS
            .is_some()
            .then(|| self.parse_one_bit())
            .transpose()?
            .unwrap_or_default();

        if extensible {
            let index: usize = self.parse_normally_small_integer()?;
            E::from_extended_enumeration_index(index)
                .ok_or_else(|| DecodeError::enumeration_index_not_found(index, true, self.codec()))
        } else {
            let index = self.parse_non_negative_binary_integer::<usize>(E::variance() as i128)?;
            E::from_enumeration_index(index)
                .ok_or_else(|| DecodeError::enumeration_index_not_found(index, false, self.codec()))
        }
    }

    fn decode_integer<I: types::IntegerType>(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<I> {
        let (result, extension_is_present) =
            self.parse_integer_with_extension_bit::<I>(constraints)?;

        if let Some(value) = constraints.value()
            && !extension_is_present
            && !value.constraint.in_bound(&result)
        {
            return Err(DecodeError::value_constraint_not_satisfied(
                result.to_bigint().unwrap_or_default(),
                value.constraint.value,
                self.codec(),
            ));
        }

        Ok(result)
    }

    fn decode_real<R: types::RealType>(
        &mut self,
        _: Tag,
        _: &Constraints,
    ) -> Result<R, Self::Error> {
        Err(DecodeError::real_not_supported(self.codec()))
    }

    fn decode_octet_string<'b, T: From<&'b [u8]> + From<Vec<u8>>>(
        &'b mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<T> {
        // The octets are borrowed from the input whenever a single fragment
        // is octet-aligned; only misaligned or fragmented values are copied,
        // into one allocation sized by what has already been read.
        enum Octets<'a> {
            None,
            Borrowed(&'a [u8]),
            Owned(Vec<u8>),
        }
        let mut octets = Octets::None;
        let codec = self.codec();

        // Aligned PER (X.691 §17): fixed-size OCTET STRING with SIZE > 2 is
        // octet-aligned. The encoder calls pad_to_alignment before the length
        // determinant, so we must consume that padding here too.
        if let Some(size) = constraints.size()
            && size.constraint.range() == Some(1)
            && size.constraint.as_start() > Some(&2)
            && self.options.aligned
        {
            self.input = self.parse_padding(self.input)?;
        }

        self.decode_extensible_container(constraints, |mut input, length| {
            let part = take(&mut input, length * 8, codec)?;

            octets = match core::mem::replace(&mut octets, Octets::None) {
                Octets::None => match part.aligned_octets() {
                    Some(borrowed) => Octets::Borrowed(borrowed),
                    None => {
                        let mut owned = Vec::with_capacity(length);
                        crate::bits::extend_vec_from_bitslice(&mut owned, part.bits());
                        Octets::Owned(owned)
                    }
                },
                Octets::Borrowed(previous) => {
                    let mut owned = Vec::with_capacity(previous.len() + length);
                    owned.extend_from_slice(previous);
                    crate::bits::extend_vec_from_bitslice(&mut owned, part.bits());
                    Octets::Owned(owned)
                }
                Octets::Owned(mut owned) => {
                    owned.reserve(length);
                    crate::bits::extend_vec_from_bitslice(&mut owned, part.bits());
                    Octets::Owned(owned)
                }
            };
            Ok(input)
        })?;

        Ok(match octets {
            Octets::None => T::from(Vec::new()),
            Octets::Borrowed(borrowed) => T::from(borrowed),
            Octets::Owned(owned) => T::from(owned),
        })
    }

    fn decode_null(&mut self, _: Tag) -> Result<()> {
        Ok(())
    }

    fn decode_object_identifier(&mut self, _: Tag) -> Result<crate::types::ObjectIdentifier> {
        let open = self.decode_open_type()?;
        let octets = open.octets();
        let decoder = crate::ber::de::Decoder::new(&octets, crate::ber::de::DecoderOptions::ber());
        decoder.decode_object_identifier_from_bytes(&octets)
    }

    fn decode_bit_string(&mut self, _: Tag, constraints: &Constraints) -> Result<types::BitString> {
        let mut bit_string = types::BitString::default();
        let codec = self.codec();

        self.decode_extensible_container(constraints, |mut input, length| {
            let part = take(&mut input, length, codec)?;
            crate::bits::extend_bitstring(&mut bit_string, part.bits());
            Ok(input)
        })?;
        Ok(bit_string)
    }

    fn decode_visible_string(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<types::VisibleString> {
        self.parse_fixed_width_string(constraints)
    }

    fn decode_ia5_string(&mut self, _: Tag, constraints: &Constraints) -> Result<types::Ia5String> {
        self.parse_fixed_width_string(constraints)
    }

    fn decode_printable_string(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<types::PrintableString> {
        self.parse_fixed_width_string(constraints)
    }

    fn decode_numeric_string(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<types::NumericString> {
        self.parse_fixed_width_string(constraints)
    }

    fn decode_teletex_string(
        &mut self,
        _: Tag,
        _constraints: &Constraints,
    ) -> Result<types::TeletexString> {
        todo!()
    }

    fn decode_bmp_string(
        &mut self,
        _: Tag,
        _constraints: &Constraints,
    ) -> Result<types::BmpString> {
        todo!()
    }

    fn decode_utf8_string(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> Result<types::Utf8String> {
        self.decode_octet_string(tag, constraints)
            .and_then(|bytes| {
                alloc::string::String::from_utf8(bytes).map_err(|e| {
                    DecodeError::string_conversion_failed(
                        Tag::UTF8_STRING,
                        e.to_string(),
                        self.codec(),
                    )
                })
            })
    }

    fn decode_general_string(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> Result<types::GeneralString> {
        <types::GeneralString>::try_from(self.decode_octet_string::<Vec<u8>>(tag, constraints)?)
            .map_err(|e| {
                DecodeError::string_conversion_failed(
                    Tag::GENERAL_STRING,
                    e.to_string(),
                    self.codec(),
                )
            })
    }

    fn decode_graphic_string(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> Result<types::GraphicString> {
        <types::GraphicString>::try_from(self.decode_octet_string::<Vec<u8>>(tag, constraints)?)
            .map_err(|e| {
                DecodeError::string_conversion_failed(
                    Tag::GRAPHIC_STRING,
                    e.to_string(),
                    self.codec(),
                )
            })
    }

    // ITU-T X.680 defines GeneralizedTime and UTCTime as IMPLICIT VisibleString
    // holding the canonical time string, so PER decodes them as one.

    fn decode_generalized_time(&mut self, tag: Tag) -> Result<types::GeneralizedTime> {
        let string = self.decode_visible_string(tag, &Constraints::default())?;
        let string = alloc::string::String::from_utf8(string.into_vec()).map_err(|e| {
            DecodeError::string_conversion_failed(
                Tag::GENERALIZED_TIME,
                e.to_string(),
                self.codec(),
            )
        })?;
        crate::ber::de::Decoder::parse_canonical_generalized_time_string(string)
    }

    fn decode_utc_time(&mut self, tag: Tag) -> Result<types::UtcTime> {
        let string = self.decode_visible_string(tag, &Constraints::default())?;
        let string = core::str::from_utf8(string.as_iso646_bytes()).map_err(|e| {
            DecodeError::string_conversion_failed(Tag::UTC_TIME, e.to_string(), self.codec())
        })?;
        crate::ber::de::Decoder::parse_canonical_utc_time_string(string)
    }

    fn decode_date(&mut self, _: Tag) -> core::result::Result<types::Date, Self::Error> {
        // ITU-T X.691 (02/2021) §32.2.7: DATE is encoded as DATE-ENCODING.
        let encoding = super::DateEncoding::decode(self)?;
        encoding.into_date().ok_or_else(|| {
            crate::error::BerDecodeErrorKind::invalid_date(alloc::format!("{encoding:?}")).into()
        })
    }

    fn decode_sequence_of<D: Decode>(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> Result<Vec<D>, Self::Error> {
        self.check_recursion_depth()?;
        let mut sequence_of = Vec::new();
        let mut options = self.options;
        options.remaining_depth = options.remaining_depth.saturating_sub(1);
        self.decode_extensible_container(constraints, |mut input, length| {
            // Reserve for the claimed count only as far as the remaining input
            // could hold, so a length determinant alone cannot force a large
            // allocation.
            sequence_of.reserve(length.min(input.len()));
            for _ in 0..length {
                let mut decoder = Self::from_reader(input, options);
                sequence_of.push(D::decode(&mut decoder)?);
                input = decoder.input;
            }
            Ok(input)
        })?;

        Ok(sequence_of)
    }

    fn decode_set_of<D: Decode + Eq + core::hash::Hash>(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> Result<types::SetOf<D>, Self::Error> {
        self.decode_sequence_of(tag, constraints)
            .map(|seq| SetOf::from_vec(seq))
    }

    fn decode_sequence<const RC: usize, const EC: usize, D, DF, F>(
        &mut self,
        _: Tag,
        _: Option<DF>,
        decode_fn: F,
    ) -> Result<D, Self::Error>
    where
        D: crate::types::Constructed<RC, EC>,
        DF: FnOnce() -> D,
        F: FnOnce(&mut Self::AnyDecoder<RC, EC>) -> Result<D, Self::Error>,
    {
        self.check_recursion_depth()?;

        let is_extensible = D::IS_EXTENSIBLE
            .then(|| self.parse_one_bit())
            .transpose()?
            .unwrap_or_default();
        let bitmap = self.parse_optional_and_default_field_bitmap(&D::FIELDS)?;

        let value = {
            let mut sequence_decoder = Decoder::from_reader(self.input, self.options);
            sequence_decoder.options.remaining_depth =
                sequence_decoder.options.remaining_depth.saturating_sub(1);
            sequence_decoder.extension_fields = D::EXTENDED_FIELDS;
            sequence_decoder.extensions_present = is_extensible.then_some(None);
            let mut fields_data = [None; RC];
            for (i, (field, bit)) in D::FIELDS
                .optional_and_default_fields()
                .zip(bitmap.into_iter().map(|b| *b))
                .enumerate()
            {
                fields_data[i] = Some((field, bit));
            }
            sequence_decoder.fields = (0, fields_data);
            let value = (decode_fn)(&mut sequence_decoder)?;

            self.input = sequence_decoder.input;
            value
        };

        Ok(value)
    }
    fn decode_optional_with_explicit_prefix<D: Decode>(
        &mut self,
        tag: Tag,
    ) -> Result<Option<D>, Self::Error> {
        self.decode_optional_with_tag(tag)
    }

    fn decode_explicit_prefix<D: Decode>(&mut self, tag: Tag) -> Result<D> {
        // Whether we have a choice here
        if D::IS_CHOICE {
            D::decode(self)
        } else {
            D::decode_with_tag(self, tag)
        }
    }

    fn decode_set<const RC: usize, const EC: usize, FIELDS, SET, D, F>(
        &mut self,
        _: Tag,
        decode_fn: D,
        field_fn: F,
    ) -> Result<SET, Self::Error>
    where
        SET: Decode + crate::types::Constructed<RC, EC>,
        FIELDS: Decode,
        D: Fn(&mut Self::AnyDecoder<RC, EC>, usize, Tag) -> Result<FIELDS, Self::Error>,
        F: FnOnce(Vec<FIELDS>) -> Result<SET, Self::Error>,
    {
        self.check_recursion_depth()?;

        let is_extensible = SET::IS_EXTENSIBLE
            .then(|| self.parse_one_bit())
            .transpose()?
            .unwrap_or_default();

        let bitmap = self.parse_optional_and_default_field_bitmap::<RC>(&SET::FIELDS)?;

        // Build a presence map indexed by each field's definition-order index.
        // Required fields are always present, so only optional/default fields are tracked.
        let mut presence = [false; RC];
        {
            let mut bitmap_iter = bitmap.into_iter().map(|b| *b);
            for field in SET::FIELDS.iter() {
                if field.is_optional_or_default() {
                    presence[field.index] = bitmap_iter.next().unwrap_or(false);
                }
            }
        }

        let fields = {
            let mut fields = Vec::new();
            let mut set_decoder = Decoder::from_reader(self.input, self.options);
            set_decoder.options.remaining_depth =
                set_decoder.options.remaining_depth.saturating_sub(1);
            set_decoder.extension_fields = SET::EXTENDED_FIELDS;
            set_decoder.extensions_present = is_extensible.then_some(None);
            let mut fields_data = [None; RC];
            for (i, (field, bit)) in SET::FIELDS
                .optional_and_default_fields()
                .zip(bitmap.into_iter().map(|b| *b))
                .enumerate()
            {
                fields_data[i] = Some((field, bit));
            }
            set_decoder.fields = (0, fields_data);

            // Decode root fields in canonical tag order (no heap allocation).
            // field.index is the definition-order position, used to look up presence
            // and to pass the correct index to decode_fn.
            for field in SET::FIELDS.canonised().iter() {
                if !field.is_optional_or_default() || presence[field.index] {
                    fields.push((decode_fn)(&mut set_decoder, field.index, field.tag)?);
                }
            }

            for (indice, field) in SET::EXTENDED_FIELDS
                .iter()
                .flat_map(|fields| fields.iter())
                .enumerate()
            {
                fields.push((decode_fn)(
                    &mut set_decoder,
                    indice + SET::FIELDS.len(),
                    field.tag,
                )?)
            }

            self.input = set_decoder.input;
            fields
        };

        (field_fn)(fields)
    }

    fn decode_optional<D: Decode>(&mut self) -> Result<Option<D>, Self::Error> {
        self.decode_optional_with_tag(D::TAG)
    }

    /// Decode an the optional value in a `SEQUENCE` or `SET` with `tag`.
    /// Passing the correct tag is required even when used with codecs where
    /// the tag is not present.
    fn decode_optional_with_tag<D: Decode>(&mut self, tag: Tag) -> Result<Option<D>, Self::Error> {
        let is_present = self.require_field(tag)?;

        if is_present {
            D::decode_with_tag(self, tag).map(Some)
        } else {
            Ok(None)
        }
    }

    fn decode_optional_with_constraints<D: Decode>(
        &mut self,
        constraints: &Constraints,
    ) -> Result<Option<D>, Self::Error> {
        let is_present = self.require_field(D::TAG)?;

        if is_present {
            D::decode_with_constraints(self, constraints).map(Some)
        } else {
            Ok(None)
        }
    }

    fn decode_optional_with_tag_and_constraints<D: Decode>(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> Result<Option<D>, Self::Error> {
        let is_present = self.require_field(tag)?;

        if is_present {
            D::decode_with_tag_and_constraints(self, tag, constraints).map(Some)
        } else {
            Ok(None)
        }
    }

    fn decode_choice<D>(&mut self, constraints: &Constraints) -> Result<D, Self::Error>
    where
        D: crate::types::DecodeChoice,
    {
        self.check_recursion_depth()?;
        use crate::types::TagTree;
        let is_extensible = self.parse_extensible_bit(constraints)?;
        // The decoded index selects a leaf of the static tag tree, with
        // nested choices flattened.
        let variants = if is_extensible {
            D::EXTENDED_VARIANTS.unwrap_or(&[])
        } else {
            D::VARIANTS
        };
        let variance = TagTree::leaf_count(variants);

        let index = if variance != 1 || is_extensible {
            if is_extensible {
                self.parse_normally_small_integer::<usize>()
                    .map_err(|error| {
                        DecodeError::choice_index_exceeds_platform_width(
                            usize::BITS,
                            error,
                            self.codec(),
                        )
                    })?
            } else {
                debug_assert!(variance > 0);
                self.parse_integer(&D::VARIANCE_CONSTRAINT)
                    .map_err(|error| {
                        DecodeError::choice_index_exceeds_platform_width(
                            usize::BITS,
                            error,
                            self.codec(),
                        )
                    })?
            }
        } else {
            0
        };

        let tag = TagTree::leaf_at(variants, index).ok_or_else(|| {
            DecodeError::choice_index_not_found(
                index,
                crate::types::variants::Variants::from_static(variants),
                self.codec(),
            )
        })?;

        if is_extensible {
            let open = self.decode_open_type()?;
            let mut decoder = Decoder::<0, 0>::from_reader(open.reader(), self.options);
            decoder.options.remaining_depth = decoder.options.remaining_depth.saturating_sub(1);
            D::from_tag(&mut decoder, tag)
        } else {
            self.options.remaining_depth = self.options.remaining_depth.saturating_sub(1);
            let result = D::from_tag(self, tag);
            self.options.remaining_depth = self.options.remaining_depth.saturating_add(1);
            result
        }
    }

    fn decode_extension_addition_group<
        const RC: usize,
        const EC: usize,
        D: Decode + crate::types::Constructed<RC, EC>,
    >(
        &mut self,
    ) -> Result<Option<D>, Self::Error> {
        if !self.parse_extension_header()? {
            return Ok(None);
        }

        let extension_is_present = self
            .extension_is_present()?
            .map(|(_, b)| b)
            .unwrap_or_default();

        if !extension_is_present {
            return Ok(None);
        }

        let open = self.decode_open_type()?;
        let mut decoder = Decoder::<RC, EC>::from_reader(open.reader(), self.options);

        D::decode(&mut decoder).map(Some)
    }

    fn decode_extension_addition_with_explicit_tag_and_constraints<D>(
        &mut self,
        tag: Tag,
        constraints: &Constraints,
    ) -> core::result::Result<Option<D>, Self::Error>
    where
        D: Decode,
    {
        self.decode_extension_addition_with_tag_and_constraints::<D>(tag, constraints)
    }

    fn decode_extension_addition_with_tag_and_constraints<D>(
        &mut self,
        _: Tag,
        constraints: &Constraints,
    ) -> core::result::Result<Option<D>, Self::Error>
    where
        D: Decode,
    {
        if !self.parse_extension_header()? {
            return Ok(None);
        }

        let extension_is_present = self
            .extension_is_present()?
            .map(|(_, b)| b)
            .unwrap_or_default();

        if !extension_is_present {
            return Ok(None);
        }

        let open = self.decode_open_type()?;
        let mut decoder = Decoder::<0, 0>::from_reader(open.reader(), self.options);

        D::decode_with_constraints(&mut decoder, constraints).map(Some)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Decoder as _;

    fn unaligned(input: &[u8]) -> Decoder<'_, 0, 0> {
        Decoder::new(
            crate::types::BitStr::from_slice(input),
            DecoderOptions::unaligned(),
        )
    }

    fn aligned(input: &[u8]) -> Decoder<'_, 0, 0> {
        Decoder::new(
            crate::types::BitStr::from_slice(input),
            DecoderOptions::aligned(),
        )
    }

    /// Lengths of 16K and above are fragmented (X.691 §11.9.3.8). The tail
    /// fragment must carry the right items, and a field following the
    /// fragmented value must still decode.
    #[test]
    fn fragmented_length_round_trip() {
        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate")]
        struct Fragmented {
            octets: crate::types::OctetString,
            bits: crate::types::BitString,
            sequence: Vec<u16>,
            trailer: u8,
        }

        for length in [16_383usize, 16_384, 16_385, 32_768, 65_536, 65_537, 100_000] {
            let value = Fragmented {
                octets: (0..length)
                    .map(|i| (i / 256) as u8)
                    .collect::<Vec<u8>>()
                    .into(),
                bits: (0..length).map(|i| i % 3 == 0).collect(),
                sequence: (0..length).map(|i| (i % 65_536) as u16).collect(),
                trailer: 0xAB,
            };

            let encoded = crate::uper::encode(&value).unwrap();
            let decoded = crate::uper::decode::<Fragmented>(&encoded).unwrap();
            assert!(
                decoded == value,
                "UPER round trip failed for length {length}"
            );

            let encoded = crate::aper::encode(&value).unwrap();
            let decoded = crate::aper::decode::<Fragmented>(&encoded).unwrap();
            assert!(
                decoded == value,
                "APER round trip failed for length {length}"
            );
        }
    }

    /// Elements of a SEQUENCE OF align relative to the start of the whole
    /// encoding, not to the start of the element list (X.691 §11.1.2).
    #[test]
    fn aligned_sequence_of_element_alignment() {
        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate")]
        struct Inner {
            #[rasn(size("3"))]
            octets: crate::types::OctetString,
        }

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate")]
        struct Outer {
            flag: bool,
            #[rasn(size("2"))]
            fixed: Vec<Inner>,
            #[rasn(size("1..=4"))]
            ranged: Vec<Inner>,
            trailer: u8,
        }

        let value = Outer {
            flag: true,
            fixed: vec![
                Inner {
                    octets: crate::types::OctetString::from_static(&[1, 2, 3]),
                },
                Inner {
                    octets: crate::types::OctetString::from_static(&[4, 5, 6]),
                },
            ],
            ranged: vec![Inner {
                octets: crate::types::OctetString::from_static(&[7, 8, 9]),
            }],
            trailer: 0xAB,
        };

        // The flag occupies bit 0, so the first fixed-size octet string (which is
        // octet-aligned in APER) must be preceded by seven padding bits.
        let encoded = crate::aper::encode(&value).unwrap();
        assert_eq!(encoded, [0x80, 1, 2, 3, 4, 5, 6, 0x00, 7, 8, 9, 0xAB]);
        assert_eq!(crate::aper::decode::<Outer>(&encoded).unwrap(), value);
    }

    /// An octet string is borrowed from the input when it lies on octet
    /// boundaries and copied into one allocation otherwise.
    #[test]
    fn octet_string_borrows_aligned_input() {
        use crate::Decoder as _;
        use alloc::borrow::Cow;

        let mut decoder = aligned(&[0x03, 0xAA, 0xBB, 0xCC]);
        let octets = decoder
            .decode_octet_string::<Cow<[u8]>>(Tag::OCTET_STRING, &Constraints::default())
            .unwrap();
        assert!(matches!(octets, Cow::Borrowed([0xAA, 0xBB, 0xCC])));

        // One leading bit shifts the string off the octet boundary.
        let mut decoder = unaligned(&[0x81, 0xD5, 0x5D, 0xE6, 0x00]);
        decoder.decode_bool(Tag::BOOL).unwrap();
        let octets = decoder
            .decode_octet_string::<Cow<[u8]>>(Tag::OCTET_STRING, &Constraints::default())
            .unwrap();
        assert!(matches!(octets, Cow::Owned(_)));
        assert_eq!(&*octets, &[0xAA, 0xBB, 0xCC]);
    }

    /// UTCTime and GeneralizedTime are VisibleStrings holding the canonical
    /// time string (X.680 §46, §47), so UPER packs seven bits per character
    /// and APER one octet. DATE is encoded as DATE-ENCODING (X.691 §32.2.7).
    /// This pins those bytes.
    #[test]
    fn time_types() {
        use chrono::TimeZone;

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", automatic_tags)]
        struct Times {
            flag: bool,
            utc: crate::types::UtcTime,
            general: crate::types::GeneralizedTime,
            date: crate::types::Date,
            trailer: u8,
        }

        let value = Times {
            flag: true,
            utc: chrono::Utc
                .with_ymd_and_hms(2018, 6, 13, 11, 1, 59)
                .unwrap(),
            general: chrono::FixedOffset::east_opt(5 * 3600)
                .unwrap()
                .with_ymd_and_hms(2018, 6, 13, 11, 1, 58)
                .unwrap(),
            date: chrono::NaiveDate::from_ymd_opt(2024, 2, 29).unwrap(),
            trailer: 0xAB,
        };

        let mut expected = alloc::vec![0x80, 0x0D];
        expected.extend_from_slice(b"180613110159Z");
        expected.push(0x0F);
        expected.extend_from_slice(b"20180613060158Z");
        // DATE-ENCODING: choice index 1 (near-future) in two bits, then the
        // octet-aligned year offset 3, then month 2 and day 29 as offsets in
        // four and five bits, before the octet-aligned trailer.
        expected.extend_from_slice(&[0x40, 0x03, 0x1E, 0x00]);
        expected.push(0xAB);

        let encoded = crate::aper::encode(&value).unwrap();
        assert_eq!(encoded, expected);
        assert_eq!(crate::aper::decode::<Times>(&encoded).unwrap(), value);
        let encoded = crate::uper::encode(&value).unwrap();
        assert_eq!(crate::uper::decode::<Times>(&encoded).unwrap(), value);

        // Unaligned, the same date is nineteen bits: 01 00000011 0001 11100.
        assert_eq!(
            crate::uper::encode(&value.date).unwrap(),
            [0x40, 0xC7, 0x80]
        );
        // An immediate year (2005..2020) takes four bits: 00 0101 0000 00000.
        let immediate = chrono::NaiveDate::from_ymd_opt(2010, 1, 1).unwrap();
        assert_eq!(crate::uper::encode(&immediate).unwrap(), [0x14, 0x00]);
        // Every year range, including the unconstrained remainder, round-trips.
        for (year, month, day) in [
            (1, 1, 1),
            (1500, 6, 15),
            (1748, 12, 31),
            (1749, 1, 1),
            (2004, 12, 31),
            (2005, 1, 1),
            (2020, 12, 31),
            (2276, 12, 31),
            (2277, 1, 1),
            (9999, 12, 31),
        ] {
            let date = chrono::NaiveDate::from_ymd_opt(year, month, day).unwrap();
            let encoded = crate::uper::encode(&date).unwrap();
            assert_eq!(
                crate::uper::decode::<crate::types::Date>(&encoded).unwrap(),
                date
            );
            let encoded = crate::aper::encode(&date).unwrap();
            assert_eq!(
                crate::aper::decode::<crate::types::Date>(&encoded).unwrap(),
                date
            );
        }
        // Components that do not form a date are rejected: 30 February 2010.
        assert!(crate::uper::decode::<crate::types::Date>(&[0x14, 0x7A]).is_err());

        // Seven-bit characters after the length determinant in UPER.
        assert_eq!(
            crate::uper::encode(&value.utc).unwrap(),
            [
                0x0D, 0x62, 0xE1, 0x83, 0x66, 0x2C, 0xD8, 0xB1, 0x60, 0xC5, 0xAB, 0x9B, 0x40
            ]
        );
        assert_eq!(
            crate::uper::encode(&value.general).unwrap(),
            [
                0x0F, 0x64, 0xC1, 0x8B, 0x86, 0x0D, 0x98, 0xB3, 0x60, 0xD9, 0x83, 0x16, 0xAE, 0x2D,
                0x00
            ]
        );

        // A string that is not a canonical time is rejected.
        let mut short = alloc::vec![0x0C];
        short.extend_from_slice(b"18061311015Z");
        assert!(crate::aper::decode::<crate::types::UtcTime>(&short).is_err());
    }

    /// An extension alternative of a CHOICE is an open type (X.691 §23.8), so
    /// its contents align relative to their own start, while a root
    /// alternative continues in place after the index.
    #[test]
    fn aligned_choice_alternatives() {
        use crate::AsnType as _;

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", automatic_tags)]
        struct Inner {
            flag: bool,
            #[rasn(size("3"))]
            octets: crate::types::OctetString,
        }

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", choice, automatic_tags)]
        #[non_exhaustive]
        enum Alternative {
            Root(bool),
            RootSequence(Inner),
            #[rasn(extension_addition)]
            Extension(Inner),
        }

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", automatic_tags)]
        struct Outer {
            first: bool,
            root: Alternative,
            extension: Alternative,
            trailer: u8,
        }

        let inner = || Inner {
            flag: true,
            octets: crate::types::OctetString::from_static(&[1, 2, 3]),
        };
        let value = Outer {
            first: true,
            root: Alternative::RootSequence(inner()),
            extension: Alternative::Extension(inner()),
            trailer: 0xAB,
        };

        // first, extension bit 0, index 1, flag, then the octet-aligned string;
        // extension bit 1 and a normally small index 0; then the open type:
        // its length, then flag and seven padding bits before the string.
        let encoded = crate::aper::encode(&value).unwrap();
        assert_eq!(encoded, [0xB0, 1, 2, 3, 0x80, 0x04, 0x80, 1, 2, 3, 0xAB]);
        assert_eq!(crate::aper::decode::<Outer>(&encoded).unwrap(), value);
        let encoded = crate::uper::encode(&value).unwrap();
        assert_eq!(crate::uper::decode::<Outer>(&encoded).unwrap(), value);
    }

    /// An extension addition group is an open type (X.691 §19.9), so its
    /// contents align relative to their own start, not the enclosing sequence.
    #[test]
    fn aligned_extension_addition_group() {
        use crate::Encoder as _;

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", automatic_tags)]
        struct Group {
            flag: bool,
            #[rasn(size("3"))]
            octets: crate::types::OctetString,
        }

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", automatic_tags)]
        #[non_exhaustive]
        struct Outer {
            first: bool,
            second: bool,
            #[rasn(extension_addition_group)]
            group: Option<Group>,
            #[rasn(extension_addition)]
            #[rasn(size("3"))]
            after: Option<crate::types::OctetString>,
        }

        let value = Outer {
            first: true,
            second: false,
            group: Some(Group {
                flag: true,
                octets: crate::types::OctetString::from_static(&[1, 2, 3]),
            }),
            after: Some(crate::types::OctetString::from_static(&[7, 8, 9])),
        };

        // Extension bit, two root bits, the extension header, then the group's
        // open type: its flag bit is followed by seven padding bits before the
        // octet-aligned string, regardless of where the open type itself sits.
        let encoded = crate::aper::encode(&value).unwrap();
        assert_eq!(encoded, [0xC0, 0x70, 0x04, 0x80, 1, 2, 3, 0x03, 7, 8, 9]);
        assert_eq!(crate::aper::decode::<Outer>(&encoded).unwrap(), value);

        let encoded = crate::uper::encode(&value).unwrap();
        assert_eq!(crate::uper::decode::<Outer>(&encoded).unwrap(), value);
    }

    /// Known-multiplier character strings (X.691 §30.5): value and index
    /// encodings, permitted alphabets, single-character alphabets, and the
    /// aligned variant's width rounding and large-string padding.
    #[test]
    fn known_multiplier_string_round_trip() {
        use crate::AsnType as _;
        use crate::types::{Ia5String, NumericString, PrintableString, VisibleString};

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", delegate, from("A..=E"), size("1..=20"))]
        struct FiveLetters(VisibleString);

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(
            crate_root = "crate",
            delegate,
            from("a..=z", "A..=Z", "-", "."),
            size("1..=64")
        )]
        struct Name(VisibleString);

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", delegate, from("x"))]
        struct OnlyX(Ia5String);

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate", delegate, size("1..=10"))]
        struct Digits(NumericString);

        #[derive(crate::AsnType, crate::Encode, crate::Decode, Debug, PartialEq)]
        #[rasn(crate_root = "crate")]
        struct Strings {
            flag: bool,
            five: FiveLetters,
            name: Name,
            only_x: OnlyX,
            digits: Digits,
            printable: PrintableString,
            ia5: Ia5String,
            trailer: u8,
        }

        let value = Strings {
            flag: true,
            five: FiveLetters(VisibleString::try_from("ABCDEEDCBA").unwrap()),
            name: Name(VisibleString::try_from("Smith-Jones.Jr").unwrap()),
            only_x: OnlyX(Ia5String::try_from("xxxx").unwrap()),
            digits: Digits(NumericString::try_from("0123456789").unwrap()),
            printable: PrintableString::try_from("Hello, World?").unwrap(),
            ia5: Ia5String::try_from("The quick brown fox").unwrap(),
            trailer: 0xAB,
        };

        let encoded = crate::uper::encode(&value).unwrap();
        assert_eq!(crate::uper::decode::<Strings>(&encoded).unwrap(), value);
        let encoded = crate::aper::encode(&value).unwrap();
        assert_eq!(crate::aper::decode::<Strings>(&encoded).unwrap(), value);

        // Five letters take three bits unaligned and four aligned, by index.
        assert_eq!(
            crate::uper::encode(&FiveLetters(VisibleString::try_from("AE").unwrap())).unwrap(),
            [0x08, 0x80]
        );
        assert_eq!(
            crate::aper::encode(&FiveLetters(VisibleString::try_from("AE").unwrap())).unwrap(),
            [0x08, 0x04]
        );

        // Characters outside the permitted alphabet are rejected both ways.
        assert!(crate::uper::encode(&FiveLetters(VisibleString::try_from("AF").unwrap())).is_err());
        assert!(crate::uper::decode::<FiveLetters>(&[0x0F, 0]).is_err());
    }

    /// APER uses a two-octet constrained whole number for ranges from 257 to
    /// 64K, leaving surplus code points that must be rejected.
    #[test]
    fn aligned_integer_value_constraint() {
        const CONSTRAINTS: Constraints = constraints!(value_constraint!(1, 300));

        // 0x012c -> 300 + minimum 1 = 301, outside of 1..=300.
        let mut decoder = aligned(&[0x01, 0x2c]);
        assert!(matches!(
            *decoder
                .decode_integer::<u16>(Tag::INTEGER, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::ValueConstraintNotSatisfied { .. }
        ));

        // 0x012b -> 299 + minimum 1 = 300, the upper bound.
        let mut decoder = aligned(&[0x01, 0x2b]);
        assert_eq!(
            decoder
                .decode_integer::<u16>(Tag::INTEGER, &CONSTRAINTS)
                .unwrap(),
            300
        );
    }

    #[test]
    fn aligned_sequence_of_size_constraint() {
        const CONSTRAINTS: Constraints = constraints!(size_constraint!(1, 300));

        // A SEQUENCE OF NULL needs no payload bits, keeping the APER two-octet
        // length determinant test small.
        let mut decoder = aligned(&[0x01, 0x2c]);
        assert!(matches!(
            *decoder
                .decode_sequence_of::<()>(Tag::SEQUENCE, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::SizeConstraintNotSatisfied {
                size: Some(301),
                ..
            }
        ));

        let mut decoder = aligned(&[0x01, 0x2b]);
        assert_eq!(
            decoder
                .decode_sequence_of::<()>(Tag::SEQUENCE, &CONSTRAINTS)
                .unwrap(),
            vec![(); 300]
        );
    }

    #[test]
    fn visible_string_size_constraint() {
        // VisibleString (SIZE (1..10)) -> the length is counted in characters.
        const CONSTRAINTS: Constraints = constraints!(size_constraint!(1, 10));

        // 0b1111 -> 15 + 1 = 16 characters. The size is checked before the
        // characters are mapped, so this fails on the length, not the alphabet.
        let mut decoder = unaligned(&[0xff; 20]);
        assert!(matches!(
            *decoder
                .decode_visible_string(Tag::VISIBLE_STRING, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::SizeConstraintNotSatisfied { size: Some(16), .. }
        ));
    }

    /// Half-open size constraints have no `range()`, so they use the
    /// unconstrained length determinant and were previously never checked at
    /// all, even though the encoder rejects them.
    #[test]
    fn half_open_size_constraint() {
        const CONSTRAINTS: Constraints = constraints!(size_constraint!(end: 4));

        // 0b0_0000110 -> 6 octets, above the maximum of 4.
        let mut decoder = unaligned(&[0x06, 1, 2, 3, 4, 5, 6]);
        assert!(matches!(
            *decoder
                .decode_octet_string::<Vec<u8>>(Tag::OCTET_STRING, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::SizeConstraintNotSatisfied { size: Some(6), .. }
        ));

        // 0b0_0000011 -> 3 octets, within the maximum.
        let mut decoder = unaligned(&[0x03, 0xAA, 0xBB, 0xCC]);
        assert_eq!(
            decoder
                .decode_octet_string::<Vec<u8>>(Tag::OCTET_STRING, &CONSTRAINTS)
                .unwrap(),
            [0xAA, 0xBB, 0xCC]
        );
    }

    #[test]
    fn extensible_size_constraint() {
        const CONSTRAINTS: Constraints = constraints!(size_constraint!(1, 3, extensible));

        // Extension bit 0 selects the root. The spare length code 0b11 would
        // decode as four elements and must be rejected.
        let mut decoder = unaligned(&[0b0111_1110]);
        assert!(matches!(
            *decoder
                .decode_sequence_of::<bool>(Tag::SEQUENCE, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::SizeConstraintNotSatisfied { size: Some(4), .. }
        ));

        // Extension bit 1 selects unconstrained length encoding, so a value
        // outside the root remains valid.
        let value = crate::types::OctetString::from_static(&[1, 2, 3, 4, 5]);
        let encoded = crate::uper::encode_with_constraints(&CONSTRAINTS, &value).unwrap();
        assert_eq!(
            crate::uper::decode_with_constraints::<crate::types::OctetString>(
                &CONSTRAINTS,
                &encoded
            )
            .unwrap(),
            value
        );
    }

    #[test]
    fn extensible_integer_value_constraint() {
        const CONSTRAINTS: Constraints = constraints!(value_constraint!(1, 10, extensible));

        // Extension bit 0 selects the root, where 0b1111 is a spare code point.
        let mut decoder = unaligned(&[0b0111_1000]);
        assert!(matches!(
            *decoder
                .decode_integer::<u8>(Tag::INTEGER, &CONSTRAINTS)
                .unwrap_err()
                .kind,
            DecodeErrorKind::ValueConstraintNotSatisfied { .. }
        ));

        // Extension bit 1 selects unconstrained integer encoding, so an
        // outside-root value remains valid.
        let encoded = crate::uper::encode_with_constraints(&CONSTRAINTS, &16u8).unwrap();
        assert_eq!(
            crate::uper::decode_with_constraints::<u8>(&CONSTRAINTS, &encoded).unwrap(),
            16
        );
    }

    #[test]
    fn bitvec() {
        use bitvec::prelude::*;
        assert_eq!(
            bitvec::bits![u8, Msb0;       0, 0, 0, 1, 1, 1, 0, 1]
                .to_bitvec()
                .into_vec(),
            vec![29]
        );
        let bv = bitvec::bits![u8, Msb0; 1, 1, 0, 0, 0, 1, 1, 1, 0, 1];
        let slice = &bv[2..];
        let mut aligned = slice.to_bitvec();
        // Indexing results to different internal memory layout than we would expect when converting to u8 vec
        // We need to unify the layout as continuos bits after indexing to get the correct result
        aligned.force_align();
        assert_eq!(aligned.into_vec(), vec![29]);
    }
}