cmpa 0.1.6

// SPDX-License-Identifier: Apache-2.0
// Copyright 2023-2026 SUSE LLC
// Author: Nicolai Stange <nstange@suse.de>

//! Sealed supertraits of the public multiprecision integer traits.
//!
//! The traits in here are `pub`, but defined in a private module, so that they
//! can't be named, and thus not be implemented, from outside the crate. As
//! they're supertraits of the public multiprecision integer traits, this
//! prevents external implementations of the latter.

use core::{cmp, convert, fmt, mem};

use super::super::limb::{LIMB_BYTES, LimbType, ct_lsb_mask_l};
use super::{
    MpMutUInt, MpMutUIntSlice, MpUInt, MpUIntSlice, MpUIntSliceCommon, ct_mp_limbs_align_len,
};

/// Sealed supertrait of [`MpUIntCommon`](super::MpUIntCommon).
///
/// Provides the crate-internal parts of the common multiprecision integer
/// interface: the representation's length alignment properties and helpers for
/// handling a partially covered most significant limb.
pub trait MpUIntCommonPriv: Sized {
    /// Whether the representation supports [lengths in units of
    /// bytes](super::MpUIntCommon::len) that aren't a multiple of the
    /// [`LimbType`] size.
    ///
    /// `true` for the byte slice representations, like
    /// [`MpBigEndianUIntByteSlice`](super::MpBigEndianUIntByteSlice), `false`
    /// for the native-endian [`LimbType`] slice representations, like
    /// [`MpNativeEndianUIntLimbsSlice`](super::MpNativeEndianUIntLimbsSlice).
    /// If `false`, the most significant limb is always fully covered by the
    /// underlying buffer.
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool;

    /// The multiprecision integer's [length in units of
    /// bytes](super::MpUIntCommon::len).
    ///
    /// Implementation backing [`MpUIntCommon::len()`](super::MpUIntCommon::len),
    /// which should be used instead outside of this module.
    fn _len(&self) -> usize;

    /// Mask of the most significant limb's bits covered by the underlying
    /// buffer.
    ///
    /// Returns a [`LimbType`] with the bits corresponding to the most
    /// significant limb's bytes covered by the underlying buffer set and those
    /// corresponding to its excess high bytes, if any, clear. In particular,
    /// all bits are set if the most significant limb is fully covered. For an
    /// empty multiprecision integer, none are set if the representation
    /// [supports unaligned lengths](Self::SUPPORTS_UNALIGNED_BUFFER_LENGTHS),
    /// all otherwise.
    ///
    /// Useful for masking out the excess high bytes from a limb value before
    /// [storing](super::MpMutUInt::store_l) it as the most significant limb, or
    /// for extracting the bits that would overflow into them.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](super::MpUIntCommon::len) and is otherwise constant as
    /// far as branching is concerned.
    fn partial_high_mask(&self) -> LimbType {
        if Self::SUPPORTS_UNALIGNED_BUFFER_LENGTHS {
            let high_npartial = if self._len() != 0 {
                ((self._len()) - 1) % LIMB_BYTES + 1
            } else {
                0
            };
            ct_lsb_mask_l(8 * high_npartial as u32)
        } else {
            !0
        }
    }

    /// Bit position of the most significant limb's excess high bytes.
    ///
    /// Returns the number of the most significant limb's bits covered by the
    /// underlying buffer, if the limb is only partially covered, or zero
    /// otherwise. Shifting a limb value masked with the complement of
    /// [`partial_high_mask()`](Self::partial_high_mask) to the right by this
    /// distance yields the value of the bits that overflowed into the excess
    /// high bytes, e.g. for turning them into a carry.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](super::MpUIntCommon::len) and is otherwise constant as
    /// far as branching is concerned.
    fn partial_high_shift(&self) -> u32 {
        if Self::SUPPORTS_UNALIGNED_BUFFER_LENGTHS {
            let high_npartial = self._len() % LIMB_BYTES;
            if high_npartial == 0 {
                0
            } else {
                8 * high_npartial as u32
            }
        } else {
            0
        }
    }
}

/// Sealed supertrait of [`MpUIntSliceCommon`].
///
/// Provides the crate-internal handling of the single buffer slice backing a
/// multiprecision integer: its element type, the conversion between [lengths in
/// units of bytes](super::MpUIntCommon::len) and numbers of slice elements, as
/// well as splitting a multiprecision integer into a high and a low part.
pub trait MpUIntSliceCommonPriv: MpUIntCommonPriv {
    /// The element type of the backing buffer slice.
    ///
    /// `u8` for the byte slice representations, [`LimbType`] for the
    /// native-endian [`LimbType`] slice representations.
    type BackingSliceElementType: Sized + Copy + cmp::PartialEq + convert::From<u8> + fmt::Debug;

    /// The size of a
    /// [`BackingSliceElementType`](Self::BackingSliceElementType) in bytes.
    const BACKING_ELEMENT_SIZE: usize = mem::size_of::<Self::BackingSliceElementType>();

    /// Align a [length in units of bytes](super::MpUIntCommon::len) as required
    /// by the representation.
    ///
    /// Returns `nbytes` unchanged if the representation
    /// [supports unaligned lengths](MpUIntCommonPriv::SUPPORTS_UNALIGNED_BUFFER_LENGTHS),
    /// and `nbytes` rounded up to the next multiple of the [`LimbType`] size
    /// otherwise, c.f. [`ct_mp_limbs_align_len()`].
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](super::MpUIntCommon::len) to
    ///   align.
    fn _limbs_align_len(nbytes: usize) -> usize {
        if Self::SUPPORTS_UNALIGNED_BUFFER_LENGTHS {
            nbytes
        } else {
            ct_mp_limbs_align_len(nbytes)
        }
    }

    /// The number of backing slice elements needed for a given [length in units
    /// of bytes](super::MpUIntCommon::len).
    ///
    /// Returns the number of
    /// [`BackingSliceElementType`](Self::BackingSliceElementType) elements a
    /// backing buffer slice must have for holding a multiprecision integer of
    /// [length in units of bytes](super::MpUIntCommon::len) `nbytes`, after
    /// [alignment](Self::_limbs_align_len) as required by the representation.
    /// Useful for allocating suitably sized buffers.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The multiprecision integer's [length in units of
    ///   bytes](super::MpUIntCommon::len).
    fn n_backing_elements_for_len(nbytes: usize) -> usize {
        let nbytes = Self::_limbs_align_len(nbytes);
        nbytes / Self::BACKING_ELEMENT_SIZE + (nbytes % Self::BACKING_ELEMENT_SIZE != 0) as usize
    }

    /// The number of elements in the backing buffer slice.
    fn n_backing_elements(&self) -> usize;

    /// Split the multiprecision integer into a high and a low part.
    ///
    /// Consumes `self` and returns a pair of multiprecision integers of the
    /// same representation, wrapping the two parts of the original backing
    /// buffer slice: the high part first, and the low part, of [length in units
    /// of bytes](super::MpUIntCommon::len) `nbytes`, second.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](super::MpUIntCommon::len) of
    ///   the low part to split off. Must be at most the multiprecision
    ///   integer's [length in units of bytes](super::MpUIntCommon::len). If the
    ///   representation doesn't [support unaligned
    ///   lengths](MpUIntCommonPriv::SUPPORTS_UNALIGNED_BUFFER_LENGTHS), must be
    ///   a multiple of the [`LimbType`] size.
    fn take(self, nbytes: usize) -> (Self, Self);
}

/// Sealed supertrait of [`MpUIntSlice`].
///
/// Provides the crate-internal parts of the interface to read-only
/// multiprecision integers backed by a single buffer slice: generic
/// construction of a multiprecision integer from a backing buffer slice, as
/// well as the representation-specific part of
/// [`MpUIntSlice::shrink_to()`]. See [`MpMutUIntSlicePriv`] for the mutable
/// counterpart.
pub trait MpUIntSlicePriv: MpUIntSliceCommon + MpUInt {
    /// The implementing type, but with the backing buffer slice's lifetime
    /// set to `'a`.
    ///
    /// E.g. `MpBigEndianUIntByteSlice<'a>` for
    /// [`MpBigEndianUIntByteSlice`](super::MpBigEndianUIntByteSlice). Used as
    /// the type of the views derived from a multiprecision integer, whose
    /// lifetimes are bound to the borrow of the original one, rather than to
    /// its backing buffer slice.
    type SelfT<'a>: MpUIntSlice<BackingSliceElementType = Self::BackingSliceElementType>
    where
        Self: 'a;

    /// The error type returned by [`from_slice()`](Self::from_slice).
    ///
    /// [`Infallible`](convert::Infallible) for all of the current
    /// implementations, as any backing buffer slice can be wrapped.
    type FromSliceError: fmt::Debug;

    /// Construct a multiprecision integer from a backing buffer slice.
    ///
    /// Wraps `s` in a [`SelfT`](Self::SelfT) of this representation. Useful
    /// for generic code, which can't name the representation-specific
    /// constructors like
    /// [`MpBigEndianUIntByteSlice::from_bytes()`](super::MpBigEndianUIntByteSlice::from_bytes).
    ///
    /// # Arguments
    ///
    /// * `s` - The backing buffer slice to wrap. Its lifetime `'a` may be
    ///   shortened to the returned multiprecision integer's lifetime `'b`.
    ///
    /// # Errors
    ///
    /// Returns [`FromSliceError`](Self::FromSliceError) if `s` can't be
    /// wrapped.
    fn from_slice<'a: 'b, 'b>(
        s: &'a [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'b>, Self::FromSliceError>
    where
        Self: 'b;

    /// Representation-specific implementation of
    /// [`MpUIntSlice::shrink_to()`].
    ///
    /// Returns a view on the part of the backing buffer slice holding the
    /// `nbytes` least significant bytes, with `nbytes` [aligned as required by
    /// the representation](MpUIntSliceCommonPriv::_limbs_align_len). Unlike
    /// [`MpUIntSlice::shrink_to()`], it neither caps `nbytes` at the
    /// multiprecision integer's [length in units of
    /// bytes](super::MpUIntCommon::len), nor checks that its value fits.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](super::MpUIntCommon::len) to
    ///   shrink the view to. Must be at most the multiprecision integer's
    ///   [length in units of bytes](super::MpUIntCommon::len).
    fn _shrink_to(&self, nbytes: usize) -> Self::SelfT<'_>;
}

/// Sealed supertrait of [`MpMutUIntSlice`].
///
/// Provides the crate-internal parts of the interface to mutable
/// multiprecision integers backed by a single buffer slice: generic
/// construction of a multiprecision integer from a mutable backing buffer
/// slice, as well as the representation-specific part of
/// [`MpMutUIntSlice::shrink_to()`]. See [`MpUIntSlicePriv`] for the read-only
/// counterpart.
pub trait MpMutUIntSlicePriv: MpUIntSliceCommon + MpMutUInt {
    /// The implementing type, but with the backing buffer slice's lifetime
    /// set to `'a`.
    ///
    /// E.g. `MpMutBigEndianUIntByteSlice<'a>` for
    /// [`MpMutBigEndianUIntByteSlice`](super::MpMutBigEndianUIntByteSlice).
    /// Used as the type of the views derived from a multiprecision integer,
    /// whose lifetimes are bound to the mutable borrow of the original one,
    /// rather than to its backing buffer slice.
    type SelfT<'a>: MpMutUIntSlice<BackingSliceElementType = Self::BackingSliceElementType>
    where
        Self: 'a;

    /// The error type returned by [`from_slice()`](Self::from_slice).
    ///
    /// [`Infallible`](convert::Infallible) for all of the current
    /// implementations, as any backing buffer slice can be wrapped.
    type FromSliceError: fmt::Debug;

    /// Construct a multiprecision integer from a mutable backing buffer slice.
    ///
    /// Wraps `s` in a [`SelfT`](Self::SelfT) of this representation. Useful
    /// for generic code, which can't name the representation-specific
    /// constructors like
    /// [`MpMutBigEndianUIntByteSlice`](super::MpMutBigEndianUIntByteSlice)'s
    /// [`from_bytes()`](super::MpMutBigEndianUIntByteSlice::from_bytes).
    ///
    /// # Arguments
    ///
    /// * `s` - The backing buffer slice to wrap. Its lifetime `'a` may be
    ///   shortened to the returned multiprecision integer's lifetime `'b`.
    ///
    /// # Errors
    ///
    /// Returns [`FromSliceError`](Self::FromSliceError) if `s` can't be
    /// wrapped.
    fn from_slice<'a: 'b, 'b>(
        s: &'a mut [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'b>, Self::FromSliceError>
    where
        Self: 'b;

    /// Representation-specific implementation of
    /// [`MpMutUIntSlice::shrink_to()`].
    ///
    /// Returns a mutable view on the part of the backing buffer slice holding
    /// the `nbytes` least significant bytes, with `nbytes` [aligned as required
    /// by the representation](MpUIntSliceCommonPriv::_limbs_align_len). `self`
    /// remains mutably borrowed for as long as the view is alive. Unlike
    /// [`MpMutUIntSlice::shrink_to()`], it neither caps `nbytes` at the
    /// multiprecision integer's [length in units of
    /// bytes](super::MpUIntCommon::len), nor checks that its value fits.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](super::MpUIntCommon::len) to
    ///   shrink the view to. Must be at most the multiprecision integer's
    ///   [length in units of bytes](super::MpUIntCommon::len).
    fn _shrink_to(&mut self, nbytes: usize) -> Self::SelfT<'_>;
}