cmpa 0.1.6

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

//! Accessors for multiprecision integers as stored in buffer slices of a number
//! of supported representations.
//!
//! Multiprecision integers are stored in caller provided buffer slices. For
//! operating on them, these get wrapped in one of the representation-specific
//! types listed below, each of which provides a view of the wrapped slice as a
//! multiprecision integer. The following representations are supported, each
//! with a variant for read-only access and a `Mut` variant for read-write
//! access:
//! - Big-endian byte slices: [`MpBigEndianUIntByteSlice`] and
//!   [`MpMutBigEndianUIntByteSlice`].
//! - Little-endian byte slices: [`MpLittleEndianUIntByteSlice`] and
//!   [`MpMutLittleEndianUIntByteSlice`].
//! - Native-endian [`LimbType`] slices: [`MpNativeEndianUIntLimbsSlice`] and
//!   [`MpMutNativeEndianUIntLimbsSlice`]. The
//!   [length of these in units of bytes](MpUIntCommon::len) is always a
//!   multiple of the [`LimbType`] size, c.f.
//!   [`MpNativeEndianUIntLimbsSlice::nlimbs_for_len()`] for allocating
//!   suitably sized buffers.
//!
//! All of these implement the [`MpUIntCommon`] trait and either of [`MpUInt`]
//! or [`MpMutUInt`], through which the arithmetic primitives access the
//! multiprecision integers in units of [`LimbType`]. The native-endian
//! representation is the most efficient one to operate on, because its
//! [`LimbType`] words can get accessed directly, whereas for the byte slice
//! representations, they need to get assembled from and disassembled into the
//! individual bytes. Nonetheless, all of the implemented multiprecision integer
//! arithmetic primitives support any of the representations, even in mixed
//! combinations for the different operands.
//!
//! For converting between the representations and to or from Rust's native
//! integer types, the following primitives are provided:
//! - [`MpMutUInt::copy_from()`] copies a multiprecision integer from any
//!   representation into another one, zero-extending it as needed.
//!   [`MpMutUInt::copy_from_cond()`] is its constant-time conditional
//!   counterpart.
//! - [`MpMutUInt::set_to_u8()`], [`MpMutUInt::set_to_u16()`],
//!   [`MpMutUInt::set_to_u32()`] and [`MpMutUInt::set_to_u64()`] set a
//!   multiprecision integer to a native integer value.
//! - [`MpUIntCommon::try_into_u8()`], [`MpUIntCommon::try_into_u16()`],
//!   [`MpUIntCommon::try_into_u32()`] and [`MpUIntCommon::try_into_u64()`]
//!   convert a multiprecision integer into a native integer, failing if the
//!   value doesn't fit.

use core::{self, convert, fmt, marker, mem, slice};

use super::limb::{
    LIMB_BITS, LIMB_BYTES, LimbChoice, LimbType, ct_find_first_set_bit_l, ct_find_last_set_bit_l,
    ct_find_last_set_byte_l, ct_is_nonzero_l, ct_is_zero_l, ct_lsb_mask_l,
};
use super::usize_ct_cmp::ct_eq_usize_usize;

mod private;
pub(super) use private::{
    MpMutUIntSlicePriv, MpUIntCommonPriv, MpUIntSliceCommonPriv, MpUIntSlicePriv,
};

/// Determine the number of [`LimbType`] limbs spanned by a multiprecision
/// integer of a given [length in units of bytes](MpUIntCommon::len).
///
/// That is, convert the length to units of [`LimbType`] limbs, rounding up.
/// This applies to any of the supported multiprecision integer representations.
///
/// Runs in constant time, independent of the argument value.
///
/// # Arguments
///
/// * `len` - The multiprecision integer's [length in units of
///   bytes](MpUIntCommon::len).
// Don't use usize::div_ceil(), which is implemented with a conditional:
// ct_lshift_mp() passes a secret shift distance here.
#[allow(clippy::manual_div_ceil)]
pub(super) const fn ct_mp_nlimbs(len: usize) -> usize {
    (len + LIMB_BYTES - 1) / LIMB_BYTES
}

/// Align a multiprecision integer's [length in units of
/// bytes](MpUIntCommon::len) to the [`LimbType`] size.
///
/// That is, round the length up to the next multiple of the [`LimbType`] size
/// in bytes, i.e. to the length of the [`LimbType`] limbs spanned by a
/// multiprecision integer of the given length, c.f. [`ct_mp_nlimbs()`].
///
/// Runs in constant time, independent of the argument value.
///
/// # Arguments
///
/// * `len` - The multiprecision integer's [length in units of
///   bytes](MpUIntCommon::len).
pub(super) const fn ct_mp_limbs_align_len(len: usize) -> usize {
    ct_mp_nlimbs(len) * LIMB_BYTES
}

#[test]
fn test_ct_mp_nlimbs() {
    assert_eq!(ct_mp_nlimbs(0), 0);
    assert_eq!(ct_mp_nlimbs(1), 1);
    assert_eq!(ct_mp_nlimbs(LIMB_BYTES - 1), 1);
    assert_eq!(ct_mp_nlimbs(LIMB_BYTES), 1);
    assert_eq!(ct_mp_nlimbs(LIMB_BYTES + 1), 2);
    assert_eq!(ct_mp_nlimbs(2 * LIMB_BYTES - 1), 2);
}

/// Internal helper to load some fully contained limb from a multiprecision
/// integer big-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is not such a partially
/// covered high limb.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `src_end` - The position past the end of the limb to be loaded from
///   `limbs`. Must be at least a [`LimbType`]'s size in bytes.
fn _be_mp_load_l_full(limbs: &[u8], src_end: usize) -> LimbType {
    debug_assert!(src_end >= LIMB_BYTES);
    let src_begin = src_end - LIMB_BYTES;
    let src = &limbs[src_begin..src_end];
    let src = <[u8; LIMB_BYTES] as TryFrom<&[u8]>>::try_from(src).unwrap();
    LimbType::from_be_bytes(src)
}

/// Internal helper to load some partially contained limb from a multiprecision
/// integer big-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is such a partially
/// covered high limb.
///
/// Execution time depends only on the `src_end` argument and is otherwise
/// constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `src_end` - The position past the end of the limb to be loaded from
///   `limbs`. Must be less than a [`LimbType`]'s size in bytes.
fn _be_mp_load_l_high_partial(limbs: &[u8], src_end: usize) -> LimbType {
    debug_assert!(src_end < LIMB_BYTES);
    let mut src: [u8; LIMB_BYTES] = [0; LIMB_BYTES];
    src[LIMB_BYTES - src_end..LIMB_BYTES].copy_from_slice(&limbs[0..src_end]);
    LimbType::from_be_bytes(src)
}

/// Load some fully contained limb from a multiprecision integer big-endian byte
/// buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. The
/// generic [`be_mp_load_l()`] implements some extra logic for handling this
/// special case of a partially stored high limb, which can be avoided if it is
/// known that the limb to be accessed is completely covered by the `limbs`
/// buffer. This function here provides such a less generic, but more performant
/// variant.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `i` - The index of the limb to load, counted from least to most
///   significant. The limb must be fully contained in `limbs`, i.e.
///   `limbs` must span at least `i + 1` [`LimbType`]s.
fn be_mp_load_l_full(limbs: &[u8], i: usize) -> LimbType {
    debug_assert!((i + 1) * LIMB_BYTES <= limbs.len());
    let src_end = limbs.len() - i * LIMB_BYTES;
    _be_mp_load_l_full(limbs, src_end)
}

/// Load some limb from a multiprecision integer big-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. If it
/// is known that the limb to be accessed at position `i` is fully covered by
/// the `limbs` buffer, consider using [`be_mp_load_l_full()`] for improved
/// performance instead.
///
/// Execution time depends only on the multiprecision integer's length and the
/// limb index argument `i`, and is otherwise constant as far as branching is
/// concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `i` - The index of the limb to load, counted from least to most
///   significant. The limb must be at least partially contained in
///   `limbs`.
fn be_mp_load_l(limbs: &[u8], i: usize) -> LimbType {
    debug_assert!(i * LIMB_BYTES < limbs.len());
    let src_end = limbs.len() - i * LIMB_BYTES;
    if src_end >= LIMB_BYTES {
        _be_mp_load_l_full(limbs, src_end)
    } else {
        _be_mp_load_l_high_partial(limbs, src_end)
    }
}

#[test]
fn test_be_mp_load_l() {
    let limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 0);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    limbs[LIMB_BYTES] = 0x80;
    limbs[LIMB_BYTES - 1] = 1;
    assert_eq!(be_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(be_mp_load_l_full(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(be_mp_load_l(&limbs, 1), 1);
    assert_eq!(be_mp_load_l_full(&limbs, 1), 1);

    let limbs: [u8; 1] = [0; 1];
    assert_eq!(be_mp_load_l(&limbs, 0), 0);

    let limbs: [u8; LIMB_BYTES + 1] = [0; LIMB_BYTES + 1];
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 0);

    let limbs: [u8; 2] = [0, 1];
    assert_eq!(be_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    limbs[1] = 1;
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 1);

    let limbs: [u8; 2] = [1, 0];
    assert_eq!(be_mp_load_l(&limbs, 0), 0x0100);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    limbs[0] = 1;
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 0x0100);
}

/// Internal helper to update some fully contained limb in a multiprecision
/// integer big-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is not such a partially
/// covered high limb.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `dst_end` - The position past the end of the limb to be updated in
///   `limbs`. Must be at least a [`LimbType`]'s size in bytes.
/// * `value` - The value to store in `limbs` at the specified position.
fn _be_mp_store_l_full(limbs: &mut [u8], dst_end: usize, value: LimbType) {
    debug_assert!(dst_end >= LIMB_BYTES);
    let dst_begin = dst_end - LIMB_BYTES;
    let dst = &mut limbs[dst_begin..dst_end];
    let dst = <&mut [u8; LIMB_BYTES] as TryFrom<&mut [u8]>>::try_from(dst).unwrap();
    *dst = value.to_be_bytes();
}

/// Internal helper to update some partially contained limb in a multiprecision
/// integer big-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is such a partially
/// covered high limb.
///
/// Execution time depends only on the `dst_end` argument and is otherwise
/// constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `dst_end` - The position past the end of the limb to be updated in
///   `limbs`. Must be less than a [`LimbType`]'s size in bytes.
/// * `value` - The value to store in `limbs` at the specified position. The
///   high bits corresponding to any of the excess limb bytes not covered by
///   `limbs` can have arbitrary values, but are ignored.
fn _be_mp_store_l_high_partial(limbs: &mut [u8], dst_end: usize, value: LimbType) {
    debug_assert!(dst_end < LIMB_BYTES);
    let dst = &mut limbs[0..dst_end];
    let src: [u8; LIMB_BYTES] = value.to_be_bytes();
    dst.copy_from_slice(&src[LIMB_BYTES - dst_end..LIMB_BYTES]);
}

/// Update some fully contained limb in a multiprecision integer big-endian byte
/// buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. The
/// generic [`be_mp_store_l()`] implements some extra logic for handling this
/// special case of a partially stored high limb, which can be avoided if it is
/// known that the limb to be accessed is completely covered by the `limbs`
/// buffer. This function here provides such a less generic, but more performant
/// variant.
///
/// Runs in constant time.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `i` - The index of the limb to update, counted from least to most
///   significant. The limb must be fully contained in `limbs`, i.e.
///   `limbs` must span at least `i + 1` [`LimbType`]s.
/// * `value` - The value to store at limb index `i` in `limbs`.
fn be_mp_store_l_full(limbs: &mut [u8], i: usize, value: LimbType) {
    debug_assert!((i + 1) * LIMB_BYTES <= limbs.len());
    let dst_end = limbs.len() - i * LIMB_BYTES;
    _be_mp_store_l_full(limbs, dst_end, value);
}

/// Update some limb in a multiprecision integer big-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. If the
/// most significant limb is to be stored, all bytes in `value` corresponding to
/// these excess bytes must be zero accordingly.
///
/// If it is known that the limb to be stored at position `i` is fully covered
/// by the `limbs` buffer, consider using [`be_mp_store_l_full()`] for improved
/// performance instead.
///
/// Execution time depends only on the multiprecision integer's length and the
/// limb index argument `i`, and is otherwise constant as far as branching is
/// concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `i` - The index of the limb to update, counted from least to most
///   significant. The limb must be at least partially contained in
///   `limbs`.
/// * `value` - The value to store at limb index `i` in `limbs`.
fn be_mp_store_l(limbs: &mut [u8], i: usize, value: LimbType) {
    debug_assert!(i * LIMB_BYTES < limbs.len());
    let dst_end = limbs.len() - i * LIMB_BYTES;
    if dst_end >= LIMB_BYTES {
        _be_mp_store_l_full(limbs, dst_end, value);
    } else {
        debug_assert_eq!(value >> (8 * dst_end), 0);
        _be_mp_store_l_high_partial(limbs, dst_end, value);
    }
}

#[test]
fn test_be_mp_store_l() {
    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    be_mp_store_l(&mut limbs, 0, 1 << (LIMB_BITS - 1));
    be_mp_store_l(&mut limbs, 1, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(be_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    be_mp_store_l_full(&mut limbs, 0, 1 << (LIMB_BITS - 1));
    be_mp_store_l_full(&mut limbs, 1, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(be_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; 1] = [0; 1];
    be_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES - 1] = [0; LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES - 1] = [0; LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, 1 << (LIMB_BITS - 8 - 1));
    assert_eq!(be_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 8 - 1));

    let mut limbs: [u8; 2] = [0; 2];
    be_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; 2] = [0; 2];
    be_mp_store_l(&mut limbs, 0, 0x0100);
    assert_eq!(be_mp_load_l(&limbs, 0), 0x0100);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    be_mp_store_l(&mut limbs, 1, 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    be_mp_store_l(&mut limbs, 1, 0x0100);
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), 0x0100);
}

/// Internal helper to clear the high bytes of a multiprecision integer
/// big-endian byte buffer.
///
/// Set all bytes at positions `>= begin` to zero, with positions counted in
/// units of bytes from least to most significant. That is, the multiprecision
/// integer gets truncated to its `begin` least significant bytes. If `begin` is
/// `>= limbs.len()`, nothing is cleared.
///
/// Execution time depends only on the length of `limbs` and the `begin`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `begin` - The position of the least significant byte to clear, counted
///   in units of bytes from least to most significant.
fn be_mp_clear_bytes_above(limbs: &mut [u8], begin: usize) {
    let limbs_len = limbs.len();
    if limbs_len <= begin {
        return;
    }
    limbs[..limbs_len - begin].fill(0);
}

#[test]
fn test_be_mp_clear_bytes_above() {
    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0 >> 8);
    be_mp_clear_bytes_above(&mut limbs, LIMB_BYTES + 1);
    assert_eq!(be_mp_load_l(&limbs, 0), !0);
    assert_eq!(be_mp_load_l(&limbs, 1), 0xff);

    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0 >> 8);
    be_mp_clear_bytes_above(&mut limbs, LIMB_BYTES - 1);
    assert_eq!(be_mp_load_l(&limbs, 0), !0 >> 8);
    assert_eq!(be_mp_load_l(&limbs, 1), 0);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0);
    be_mp_clear_bytes_above(&mut limbs, 2 * LIMB_BYTES);
    assert_eq!(be_mp_load_l(&limbs, 0), !0);
    assert_eq!(be_mp_load_l(&limbs, 1), !0);
}

/// Internal helper to clear the low bytes of a multiprecision integer
/// big-endian byte buffer.
///
/// Set all bytes at positions `< end` to zero, with positions counted in units
/// of bytes from least to most significant. If `end` is `>= limbs.len()`, all
/// of `limbs` is cleared.
///
/// Execution time depends only on the length of `limbs` and the `end`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   big-endian order.
/// * `end` - The position past the most significant byte to clear, counted
///   in units of bytes from least to most significant.
fn be_mp_clear_bytes_below(limbs: &mut [u8], end: usize) {
    let limbs_len = limbs.len();
    let end = end.min(limbs_len);
    limbs[limbs_len - end..].fill(0);
}

#[test]
fn test_be_mp_clear_bytes_below() {
    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0 >> 8);
    be_mp_clear_bytes_below(&mut limbs, LIMB_BYTES + 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 0);
    assert_eq!(be_mp_load_l(&limbs, 1), (!0 >> 8) & !0xff);

    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0 >> 8);
    be_mp_clear_bytes_below(&mut limbs, LIMB_BYTES - 1);
    assert_eq!(be_mp_load_l(&limbs, 0), 0xff << (8 * (LIMB_BYTES - 1)));
    assert_eq!(be_mp_load_l(&limbs, 1), !0 >> 8);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    be_mp_store_l(&mut limbs, 0, !0);
    be_mp_store_l(&mut limbs, 1, !0);
    be_mp_clear_bytes_below(&mut limbs, 0);
    assert_eq!(be_mp_load_l(&limbs, 0), !0);
    assert_eq!(be_mp_load_l(&limbs, 1), !0);
}

/// Internal helper to load some fully contained limb from a multiprecision
/// integer little-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is not such a partially
/// covered high limb.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `src_begin` - The position of the limb to be loaded from `limbs`.
///   At least a [`LimbType`]'s size in bytes must remain in `limbs` from
///   there on.
fn _le_mp_load_l_full(limbs: &[u8], src_begin: usize) -> LimbType {
    debug_assert!(src_begin + LIMB_BYTES <= limbs.len());
    let src_end = src_begin + LIMB_BYTES;
    let src = &limbs[src_begin..src_end];
    let src = <[u8; LIMB_BYTES] as TryFrom<&[u8]>>::try_from(src).unwrap();
    LimbType::from_le_bytes(src)
}

/// Internal helper to load some partially contained limb from a multiprecision
/// integer little-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is such a partially
/// covered high limb.
///
/// Execution time depends only on the length of `limbs` and the `src_begin`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `src_begin` - The position of the limb to be loaded from `limbs`. Must
///   be `<= limbs.len()`, with less than a [`LimbType`]'s size in bytes
///   remaining in `limbs` from there on.
fn _le_mp_load_l_high_partial(limbs: &[u8], src_begin: usize) -> LimbType {
    debug_assert!(src_begin <= limbs.len() && limbs.len() - src_begin < LIMB_BYTES);
    let mut src: [u8; LIMB_BYTES] = [0; LIMB_BYTES];
    src[..limbs.len() - src_begin].copy_from_slice(&limbs[src_begin..]);
    LimbType::from_le_bytes(src)
}

/// Load some fully contained limb from a multiprecision integer little-endian
/// byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. The
/// generic [`le_mp_load_l()`] implements some extra logic for handling this
/// special case of a partially stored high limb, which can be avoided if it is
/// known that the limb to be accessed is completely covered by the `limbs`
/// buffer. This function here provides such a less generic, but more performant
/// variant.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `i` - The index of the limb to load, counted from least to most
///   significant. The limb must be fully contained in `limbs`, i.e.
///   `limbs` must span at least `i + 1` [`LimbType`]s.
fn le_mp_load_l_full(limbs: &[u8], i: usize) -> LimbType {
    let src_begin = i * LIMB_BYTES;
    debug_assert!(src_begin + LIMB_BYTES <= limbs.len());
    _le_mp_load_l_full(limbs, src_begin)
}

/// Load some limb from a multiprecision integer little-endian byte buffer.
///
/// The specified limb is returned in the host's native endianess.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. If it
/// is known that the limb to be accessed at position `i` is fully covered by
/// the `limbs` buffer, consider using [`le_mp_load_l_full()`] for improved
/// performance instead.
///
/// Execution time depends only on the multiprecision integer's length and the
/// limb index argument `i`, and is otherwise constant as far as branching is
/// concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `i` - The index of the limb to load, counted from least to most
///   significant. The limb must be at least partially contained in
///   `limbs`.
fn le_mp_load_l(limbs: &[u8], i: usize) -> LimbType {
    let src_begin = i * LIMB_BYTES;
    debug_assert!(src_begin < limbs.len());
    if src_begin + LIMB_BYTES <= limbs.len() {
        _le_mp_load_l_full(limbs, src_begin)
    } else {
        _le_mp_load_l_high_partial(limbs, src_begin)
    }
}

#[test]
fn test_le_mp_load_l() {
    let limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 0);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    limbs[LIMB_BYTES - 1] = 0x80;
    limbs[LIMB_BYTES] = 1;
    assert_eq!(le_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(le_mp_load_l_full(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(le_mp_load_l(&limbs, 1), 1);
    assert_eq!(le_mp_load_l_full(&limbs, 1), 1);

    let limbs: [u8; 1] = [0; 1];
    assert_eq!(le_mp_load_l(&limbs, 0), 0);

    let limbs: [u8; LIMB_BYTES + 1] = [0; LIMB_BYTES + 1];
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 0);

    let limbs: [u8; 2] = [1, 0];
    assert_eq!(le_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    limbs[LIMB_BYTES] = 1;
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 1);

    let limbs: [u8; 2] = [0, 1];
    assert_eq!(le_mp_load_l(&limbs, 0), 0x0100);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    limbs[LIMB_BYTES + 1] = 1;
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l_full(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 0x0100);
}

/// Internal helper to update some fully contained limb in a multiprecision
/// integer little-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is not such a partially
/// covered high limb.
///
/// Runs in constant time as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `dst_begin` - The position of the limb to be updated in `limbs`.
///   At least a [`LimbType`]'s size in bytes must remain in `limbs` from
///   there on.
/// * `value` - The value to store in `limbs` at the specified position.
fn _le_mp_store_l_full(limbs: &mut [u8], dst_begin: usize, value: LimbType) {
    debug_assert!(dst_begin + LIMB_BYTES <= limbs.len());
    let dst_end = dst_begin + LIMB_BYTES;
    let dst = &mut limbs[dst_begin..dst_end];
    let dst = <&mut [u8; LIMB_BYTES] as TryFrom<&mut [u8]>>::try_from(dst).unwrap();
    *dst = value.to_le_bytes();
}

/// Internal helper to update some partially contained limb in a multiprecision
/// integer little-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. This
/// internal helper is used whenever the specified limb is such a partially
/// covered high limb.
///
/// Execution time depends only on the length of `limbs` and the `dst_begin`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `dst_begin` - The position of the limb to be updated in `limbs`. Must
///   be `<= limbs.len()`, with less than a [`LimbType`]'s size in bytes
///   remaining in `limbs` from there on.
/// * `value` - The value to store in `limbs` at the specified position. The
///   high bits corresponding to any of the excess limb bytes not covered by
///   `limbs` can have arbitrary values, but are ignored.
fn _le_mp_store_l_high_partial(limbs: &mut [u8], dst_begin: usize, value: LimbType) {
    debug_assert!(dst_begin <= limbs.len() && limbs.len() - dst_begin < LIMB_BYTES);
    let dst_end = limbs.len();
    let dst = &mut limbs[dst_begin..];
    let src: [u8; LIMB_BYTES] = value.to_le_bytes();
    dst.copy_from_slice(&src[0..dst_end - dst_begin]);
}

/// Update some fully contained limb in a multiprecision integer little-endian
/// byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. The
/// generic [`le_mp_store_l()`] implements some extra logic for handling this
/// special case of a partially stored high limb, which can be avoided if it is
/// known that the limb to be accessed is completely covered by the `limbs`
/// buffer. This function here provides such a less generic, but more performant
/// variant.
///
/// Runs in constant time.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `i` - The index of the limb to update, counted from least to most
///   significant. The limb must be fully contained in `limbs`, i.e.
///   `limbs` must span at least `i + 1` [`LimbType`]s.
/// * `value` - The value to store at limb index `i` in `limbs`.
fn le_mp_store_l_full(limbs: &mut [u8], i: usize, value: LimbType) {
    let dst_begin = i * LIMB_BYTES;
    debug_assert!(dst_begin + LIMB_BYTES <= limbs.len());
    _le_mp_store_l_full(limbs, dst_begin, value);
}

/// Update some limb in a multiprecision integer little-endian byte buffer.
///
/// The byte buffer's length doesn't necessarily align with the size of a
/// [`LimbType`], in which case the most significant limb's might be stored only
/// partially, with its virtual excess high bytes defined to equal zero. If the
/// most significant limb is to be stored, all bytes in `value` corresponding to
/// these excess bytes must be zero accordingly.
///
/// If it is known that the limb to be stored at position `i` is fully covered
/// by the `limbs` buffer, consider using [`le_mp_store_l_full()`] for improved
/// performance instead.
///
/// Execution time depends only on the multiprecision integer's length and the
/// limb index argument `i`, and is otherwise constant as far as branching is
/// concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `i` - The index of the limb to update, counted from least to most
///   significant. The limb must be at least partially contained in
///   `limbs`.
/// * `value` - The value to store at limb index `i` in `limbs`.
fn le_mp_store_l(limbs: &mut [u8], i: usize, value: LimbType) {
    let dst_begin = i * LIMB_BYTES;
    debug_assert!(dst_begin < limbs.len());
    if dst_begin + LIMB_BYTES <= limbs.len() {
        _le_mp_store_l_full(limbs, dst_begin, value);
    } else {
        debug_assert_eq!(value >> (8 * (limbs.len() - dst_begin)), 0);
        _le_mp_store_l_high_partial(limbs, dst_begin, value);
    }
}

#[test]
fn test_le_mp_store_l() {
    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    le_mp_store_l(&mut limbs, 0, 1 << (LIMB_BITS - 1));
    le_mp_store_l(&mut limbs, 1, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(le_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    le_mp_store_l_full(&mut limbs, 0, 1 << (LIMB_BITS - 1));
    le_mp_store_l_full(&mut limbs, 1, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 1));
    assert_eq!(le_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; 1] = [0; 1];
    le_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES - 1] = [0; LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; LIMB_BYTES - 1] = [0; LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, 1 << (LIMB_BITS - 8 - 1));
    assert_eq!(le_mp_load_l(&limbs, 0), 1 << (LIMB_BITS - 8 - 1));

    let mut limbs: [u8; 2] = [0; 2];
    le_mp_store_l(&mut limbs, 0, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 1);

    let mut limbs: [u8; 2] = [0; 2];
    le_mp_store_l(&mut limbs, 0, 0x0100);
    assert_eq!(le_mp_load_l(&limbs, 0), 0x0100);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    le_mp_store_l(&mut limbs, 1, 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 1);

    let mut limbs: [u8; LIMB_BYTES + 2] = [0; LIMB_BYTES + 2];
    le_mp_store_l(&mut limbs, 1, 0x0100);
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), 0x0100);
}

/// Internal helper to clear the high bytes of a multiprecision integer
/// little-endian byte buffer.
///
/// Set all bytes at positions `>= begin` to zero, with positions counted in
/// units of bytes from least to most significant. That is, the multiprecision
/// integer gets truncated to its `begin` least significant bytes. If `begin` is
/// `>= limbs.len()`, nothing is cleared.
///
/// Execution time depends only on the length of `limbs` and the `begin`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `begin` - The position of the least significant byte to clear, counted
///   in units of bytes from least to most significant.
fn le_mp_clear_bytes_above(limbs: &mut [u8], begin: usize) {
    if limbs.len() <= begin {
        return;
    }
    limbs[begin..].fill(0);
}

#[test]
fn test_le_mp_clear_bytes_above() {
    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0 >> 8);
    le_mp_clear_bytes_above(&mut limbs, LIMB_BYTES + 1);
    assert_eq!(le_mp_load_l(&limbs, 0), !0);
    assert_eq!(le_mp_load_l(&limbs, 1), 0xff);

    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0 >> 8);
    le_mp_clear_bytes_above(&mut limbs, LIMB_BYTES - 1);
    assert_eq!(le_mp_load_l(&limbs, 0), !0 >> 8);
    assert_eq!(le_mp_load_l(&limbs, 1), 0);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0);
    le_mp_clear_bytes_above(&mut limbs, 2 * LIMB_BYTES);
    assert_eq!(le_mp_load_l(&limbs, 0), !0);
    assert_eq!(le_mp_load_l(&limbs, 1), !0);
}

/// Internal helper to clear the low bytes of a multiprecision integer
/// little-endian byte buffer.
///
/// Set all bytes at positions `< end` to zero, with positions counted in units
/// of bytes from least to most significant. If `end` is `>= limbs.len()`, all
/// of `limbs` is cleared.
///
/// Execution time depends only on the length of `limbs` and the `end`
/// argument and is otherwise constant as far as branching is concerned.
///
/// # Arguments
///
/// * `limbs` - The multiprecision integer's underlying byte buffer in
///   little-endian order.
/// * `end` - The position past the most significant byte to clear, counted
///   in units of bytes from least to most significant.
fn le_mp_clear_bytes_below(limbs: &mut [u8], end: usize) {
    let end = end.min(limbs.len());
    limbs[..end].fill(0);
}

#[test]
fn test_le_mp_clear_bytes_below() {
    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0 >> 8);
    le_mp_clear_bytes_below(&mut limbs, LIMB_BYTES + 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 0);
    assert_eq!(le_mp_load_l(&limbs, 1), (!0 >> 8) & !0xff);

    let mut limbs: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0 >> 8);
    le_mp_clear_bytes_below(&mut limbs, LIMB_BYTES - 1);
    assert_eq!(le_mp_load_l(&limbs, 0), 0xff << (8 * (LIMB_BYTES - 1)));
    assert_eq!(le_mp_load_l(&limbs, 1), !0 >> 8);

    let mut limbs: [u8; 2 * LIMB_BYTES] = [0; 2 * LIMB_BYTES];
    le_mp_store_l(&mut limbs, 0, !0);
    le_mp_store_l(&mut limbs, 1, !0);
    le_mp_clear_bytes_below(&mut limbs, 0);
    assert_eq!(le_mp_load_l(&limbs, 0), !0);
    assert_eq!(le_mp_load_l(&limbs, 1), !0);
}

/// Error returned by the conversions of multiprecision integers into native
/// integer types.
///
/// Returned by [`MpUIntCommon::try_into_u8()`],
/// [`MpUIntCommon::try_into_u16()`], [`MpUIntCommon::try_into_u32()`] and
/// [`MpUIntCommon::try_into_u64()`] if the multiprecision integer's value
/// exceeds the range of the target native integer type.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct MpUIntCommonTryIntoNativeError;

macro_rules! _mpu_try_into_native_u {
    ($nt:ty, $name:ident) => {
        #[doc = concat!("Convert the multiprecision integer to a [`", stringify!($nt), "`].")]
        ///
        /// Execution time depends only on the multiprecision integer's [length
        /// in units of bytes](MpUIntCommon::len) and on whether its value fits,
        /// and is otherwise constant as far as branching is concerned.
        ///
        /// # Errors
        ///
        /// Returns [`MpUIntCommonTryIntoNativeError`] if the multiprecision
        /// integer's value exceeds the native type's range.
        fn $name(&self) -> Result<$nt, MpUIntCommonTryIntoNativeError> {
            let native_type_nlimbs = ct_mp_nlimbs(mem::size_of::<$nt>());
            let nbytes_from_last = ((mem::size_of::<$nt>() - 1) % LIMB_BYTES) + 1;
            let nlimbs = self.nlimbs();
            let mut head_is_nonzero = 0;
            for i in native_type_nlimbs..nlimbs {
                head_is_nonzero |= self.load_l(i);
            }
            // The multiprecision integer might be shorter than the native
            // type, with its missing high limbs defined to equal zero.
            let last_val = if native_type_nlimbs <= nlimbs {
                self.load_l(native_type_nlimbs - 1)
            } else {
                0
            };
            let last_mask = ct_lsb_mask_l(8 * nbytes_from_last as u32);
            head_is_nonzero |= last_val & !last_mask;
            if ct_is_nonzero_l(head_is_nonzero) != 0 {
                return Err(MpUIntCommonTryIntoNativeError);
            }
            let mut result: $nt = (last_val & last_mask) as $nt;
            let mut i = native_type_nlimbs - 1;
            while i > 0 {
                i -= 1;
                // This loop only gets executed in case
                // LIMB_BITS < $nt::BITS. Avoid a compiler error for smaller
                // native types due to a too large shift distance.
                result <<= LIMB_BITS.min(<$nt>::BITS - 1);
                if i < nlimbs {
                    result |= self.load_l(i) as $nt;
                }
            }
            Ok(result)
        }
    };
}

/// Common interface to multiprecision integers of any of the supported
/// representations.
///
/// [`MpUIntCommon`] provides read access to a multiprecision integer in units
/// of [`LimbType`], independent of how it's stored in the underlying buffer.
/// Limbs are indexed from least to most significant.
///
/// A multiprecision integer's [length in units of bytes](MpUIntCommon::len)
/// doesn't need to be a multiple of the [`LimbType`] size for the byte slice
/// representations. If it isn't, the underlying buffer holds only the low
/// bytes of the most significant limb, and its missing high bytes read as
/// zero.
///
/// This trait is implemented by both the read-only and the mutable
/// representation-specific types, e.g. [`MpBigEndianUIntByteSlice`] and
/// [`MpMutBigEndianUIntByteSlice`], c.f. the [module level
/// documentation](self). The read-only ones implement [`MpUInt`] in addition,
/// the mutable ones [`MpMutUInt`]. Arithmetic primitives taking an operand
/// they only read from are generic over [`MpUIntCommon`], so that either kind
/// can be passed.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpUIntCommon: MpUIntCommonPriv + fmt::LowerHex {
    /// The multiprecision integer's length in units of bytes.
    fn len(&self) -> usize {
        self._len()
    }

    /// The number of [`LimbType`] limbs spanned by the multiprecision integer.
    ///
    /// That is, its [length in units of bytes](Self::len) converted to units of
    /// [`LimbType`] limbs, rounding up, c.f.
    /// [`MpNativeEndianUIntLimbsSlice::nlimbs_for_len()`].
    fn nlimbs(&self) -> usize {
        ct_mp_nlimbs(self.len())
    }

    /// Whether the multiprecision integer's [length in units of
    /// bytes](Self::len) is zero.
    fn is_empty(&self) -> bool;

    /// Load a limb fully covered by the underlying buffer.
    ///
    /// Returns the specified limb in the host's native endianess. Use
    /// [`load_l()`](Self::load_l) instead if the limb might be the partially
    /// covered most significant one.
    ///
    /// Runs in constant time as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to load, counted from least to most
    ///   significant. Must be less than [`nlimbs()`](Self::nlimbs). The limb
    ///   must be fully contained in the underlying buffer, i.e. if `i` refers
    ///   to the most significant limb, the latter must not be a partially
    ///   covered one.
    fn load_l_full(&self, i: usize) -> LimbType;

    /// Load a limb, which might be the partially covered most significant one.
    ///
    /// Returns the specified limb in the host's native endianess. Any of its
    /// high bytes not covered by the underlying buffer read as zero.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `i` argument and is otherwise
    /// constant as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to load, counted from least to most
    ///   significant. Must be less than [`nlimbs()`](Self::nlimbs).
    fn load_l(&self, i: usize) -> LimbType;

    /// Test a bit of the multiprecision integer.
    ///
    /// Returns a [`LimbChoice`] representing `true` if the bit is set and
    /// `false` otherwise. Bits at positions at or beyond 8 times the
    /// multiprecision integer's [length in units of bytes](Self::len) read as
    /// unset.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `pos` argument and is
    /// otherwise constant as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `pos` - The position of the bit to test, counted from least to most
    ///   significant.
    fn test_bit(&self, pos: usize) -> LimbChoice {
        let limb_index = pos / LIMB_BITS as usize;
        if limb_index >= self.nlimbs() {
            return LimbChoice::from(0);
        }
        let pos_in_limb = pos % LIMB_BITS as usize;
        let l = self.load_l(limb_index);
        LimbChoice::from((l >> pos_in_limb) & 1)
    }

    /// Format the multiprecision integer in lowercase hexadecimal.
    ///
    /// Helper for implementing [`fmt::LowerHex`]. The digits are written from
    /// most to least significant, with a `_` separating the limbs. The most
    /// significant limb gets only as many digits as it has bytes covered by
    /// the underlying buffer. With the alternate flag (`{:#x}`), a `0x` prefix
    /// is prepended. An empty multiprecision integer is written as `(empty)`.
    ///
    /// No constant-time guarantees are made.
    ///
    /// # Arguments
    ///
    /// * `f` - The [`fmt::Formatter`] to write to.
    fn fmt_lower_hex(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fn nibble_to_hexchar(nibble: u8) -> char {
            let c = match nibble {
                0x0..=0x9 => b'0' + nibble,
                0xa..=0xf => b'a' + (nibble - 0xa),
                _ => unreachable!(),
            };
            c as char
        }

        fn fmt_byte(f: &mut fmt::Formatter<'_>, v: u8) -> fmt::Result {
            <fmt::Formatter<'_> as fmt::Write>::write_char(f, nibble_to_hexchar(v >> 4))?;
            <fmt::Formatter<'_> as fmt::Write>::write_char(f, nibble_to_hexchar(v & 0xf))?;
            Ok(())
        }

        fn fmt_l(f: &mut fmt::Formatter<'_>, v: LimbType, len: usize) -> fmt::Result {
            for i in 0..len {
                fmt_byte(f, (v >> (8 * (len - i - 1))) as u8)?;
            }
            Ok(())
        }

        if f.alternate() {
            f.write_str("0x")?;
        }
        if self.is_empty() {
            f.write_str("(empty)")?;
            return Ok(());
        }

        let v = self.load_l(self.nlimbs() - 1);
        fmt_l(f, v, (self.len() - 1) % LIMB_BYTES + 1)?;

        let mut i = 0;
        while i + 1 < self.nlimbs() {
            <fmt::Formatter<'_> as fmt::Write>::write_char(f, '_')?;
            let v = self.load_l(self.nlimbs() - 2 - i);
            fmt_l(f, v, LIMB_BYTES)?;
            i += 1;
        }

        Ok(())
    }

    /// Check whether the multiprecision integer fits into a given [length in
    /// units of bytes](MpUIntCommon::len).
    ///
    /// Returns true if the multiprecision integer's [length in units of
    /// bytes](Self::len) is at most `len`. For representations whose [length in
    /// units of bytes](MpUIntCommon::len) is always a multiple of the
    /// [`LimbType`] size, like [`MpNativeEndianUIntLimbsSlice`], the length may
    /// also exceed `len` by less than a [`LimbType`]'s size, as long as all of
    /// the excess high bytes are zero. This accommodates the alignment excess
    /// of a buffer allocated for a length of `len`.
    ///
    /// Note that the relation isn't symmetric:
    /// `a.len_is_compatible_with(b.len())` doesn't imply
    /// `b.len_is_compatible_with(a.len())`. Requiring two multiprecision
    /// integers to be of equal [length in units of bytes](MpUIntCommon::len),
    /// within the alignment excess, needs both checks.
    ///
    /// In the alignment excess case, the result and the execution time depend
    /// on the value of the multiprecision integer's excess high bytes.
    ///
    /// # Arguments
    ///
    /// * `len` - The [length in units of bytes](MpUIntCommon::len) to check
    ///   against.
    fn len_is_compatible_with(&self, len: usize) -> bool {
        if self._len() <= len {
            true
        } else if !Self::SUPPORTS_UNALIGNED_BUFFER_LENGTHS && self._len() - len < LIMB_BYTES {
            // Allow for aligment excess
            self.load_l(self.nlimbs() - 1) >> (8 * (LIMB_BYTES - (self._len() - len))) == 0
        } else {
            false
        }
    }

    _mpu_try_into_native_u!(u8, try_into_u8);
    _mpu_try_into_native_u!(u16, try_into_u16);
    _mpu_try_into_native_u!(u32, try_into_u32);
    _mpu_try_into_native_u!(u64, try_into_u64);
}

/// Marker trait for read-only multiprecision integers.
///
/// Implemented by the read-only representation-specific types, i.e.
/// [`MpBigEndianUIntByteSlice`], [`MpLittleEndianUIntByteSlice`] and
/// [`MpNativeEndianUIntLimbsSlice`], and thereby distinguishes them from their
/// mutable counterparts, which implement [`MpMutUInt`] instead. It doesn't add
/// any methods on its own, all read access is provided through the
/// [`MpUIntCommon`] supertrait. Arithmetic primitives only reading from an
/// operand are generic over [`MpUIntCommon`] rather than [`MpUInt`], so that
/// mutable multiprecision integers can be passed as well.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpUInt: MpUIntCommon {}

macro_rules! _mpu_set_to_native_u {
    ($nt:ty, $name:ident) => {
        #[doc = concat!("Set the multiprecision integer to a [`", stringify!($nt), "`] value.")]
        ///
        /// Execution time depends only on the multiprecision integer's [length
        /// in units of bytes](MpUIntCommon::len) and is otherwise constant as
        /// far as branching is concerned.
        ///
        /// # Arguments
        ///
        /// * `value` - The value to set the multiprecision integer to. The
        ///   multiprecision integer's [length in units of
        ///   bytes](MpUIntCommon::len) must be at least the native type's size
        ///   in bytes.
        fn $name(&mut self, mut value: $nt) {
            debug_assert!(self.len() >= mem::size_of::<$nt>());
            self.clear_bytes_above(mem::size_of::<$nt>());
            let native_type_nlimbs = ct_mp_nlimbs(mem::size_of::<$nt>());
            for i in 0..native_type_nlimbs {
                self.store_l(i, (value & (!(0 as LimbType) as $nt)) as LimbType);
                // This loop only gets executed more than once in case LIMB_BITS < $nt::BITS.
                // Avoid a compiler error for smaller native types due to a too large
                // shift distance.
                value >>= LIMB_BITS.min(<$nt>::BITS - 1);
            }
        }
    };
}

/// Interface to mutable multiprecision integers.
///
/// Implemented by the mutable representation-specific types, i.e.
/// [`MpMutBigEndianUIntByteSlice`], [`MpMutLittleEndianUIntByteSlice`] and
/// [`MpMutNativeEndianUIntLimbsSlice`]. In addition to the read access provided
/// through the [`MpUIntCommon`] supertrait, [`MpMutUInt`] provides write access
/// in units of [`LimbType`], as well as primitives for clearing byte ranges,
/// setting bits and for copying values from other multiprecision integers or
/// from native integers. Arithmetic primitives are generic over [`MpMutUInt`]
/// for any operand they write to.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpMutUInt: MpUIntCommon {
    /// Store a limb fully covered by the underlying buffer.
    ///
    /// Use [`store_l()`](Self::store_l) instead if the limb might be the
    /// partially covered most significant one.
    ///
    /// Runs in constant time as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to update, counted from least to most
    ///   significant. Must be less than [`nlimbs()`](MpUIntCommon::nlimbs).
    ///   The limb must be fully contained in the underlying buffer, i.e. if `i`
    ///   refers to the most significant limb, the latter must not be a
    ///   partially covered one.
    /// * `value` - The value to store, in the host's native endianess.
    fn store_l_full(&mut self, i: usize, value: LimbType);

    /// Store a limb, which might be the partially covered most significant
    /// one.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `i` argument and is otherwise
    /// constant as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to update, counted from least to most
    ///   significant. Must be less than [`nlimbs()`](MpUIntCommon::nlimbs).
    /// * `value` - The value to store, in the host's native endianess. The
    ///   bits corresponding to any of the limb's excess high bytes not covered
    ///   by the underlying buffer are ignored.
    fn store_l(&mut self, i: usize, value: LimbType);

    /// Clear the multiprecision integer's high bytes.
    ///
    /// Set all bytes at positions `>= begin` to zero, with positions counted in
    /// units of bytes from least to most significant. That is, the
    /// multiprecision integer gets truncated to its `begin` least significant
    /// bytes. If `begin` is `>= len()`, nothing is cleared.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `begin` argument and is
    /// otherwise constant as far as branching is concerned. See
    /// [`ct_clear_bits_above_mp()`] for clearing at bit granularity, with an
    /// execution time independent of the position.
    ///
    /// # Arguments
    ///
    /// * `begin` - The position of the least significant byte to clear,
    ///   counted in units of bytes from least to most significant.
    fn clear_bytes_above(&mut self, begin: usize);

    /// Clear the multiprecision integer's low bytes.
    ///
    /// Set all bytes at positions `< end` to zero, with positions counted in
    /// units of bytes from least to most significant. If `end` is `>= len()`,
    /// all of the multiprecision integer is cleared.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `end` argument and is
    /// otherwise constant as far as branching is concerned. See
    /// [`ct_clear_bits_below_mp()`] for clearing at bit granularity, with an
    /// execution time independent of the position.
    ///
    /// # Arguments
    ///
    /// * `end` - The position past the most significant byte to clear, counted
    ///   in units of bytes from least to most significant.
    fn clear_bytes_below(&mut self, end: usize);

    /// Conditionally clear the multiprecision integer's high bytes.
    ///
    /// If `cond` is true, set all bytes at positions `>= begin` to zero, like
    /// [`clear_bytes_above()`](Self::clear_bytes_above). Otherwise leave the
    /// multiprecision integer unmodified.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `begin` argument and is
    /// otherwise constant as far as branching is concerned. In particular, it
    /// doesn't depend on `cond`.
    ///
    /// # Arguments
    ///
    /// * `begin` - The position of the least significant byte to clear,
    ///   counted in units of bytes from least to most significant.
    /// * `cond` - Whether or not to clear the bytes.
    fn clear_bytes_above_cond(&mut self, begin: usize, cond: LimbChoice) {
        if begin >= self.len() {
            return;
        }

        let mask = cond.select(!0, 0);
        let begin_limb = begin / LIMB_BYTES;
        let begin_in_limb = begin % LIMB_BYTES;
        let val = self.load_l(begin_limb);
        let first_mask = !ct_lsb_mask_l(8 * begin_in_limb as u32) | mask;
        let val = val & first_mask;
        self.store_l(begin_limb, val);

        for i in begin_limb + 1..self.nlimbs() {
            self.store_l(i, self.load_l(i) & mask);
        }
    }

    /// Copy a multiprecision integer's value.
    ///
    /// Set this multiprecision integer to the value of `src`, which may be of
    /// any representation. If `src` is shorter, the value gets zero-extended.
    /// Otherwise its value must fit into this multiprecision integer. That is,
    /// all of `src`'s bytes at positions `>= len()`, counted from least to most
    /// significant, must be zero. The [length in units of
    /// bytes](MpUIntCommon::len) of `src` itself isn't restricted.
    ///
    /// Execution time depends only on the two multiprecision integers' [lengths
    /// in units of bytes](MpUIntCommon::len) and is otherwise constant as far
    /// as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `src` - The multiprecision integer to copy the value from.
    fn copy_from<S: MpUIntCommon>(&'_ mut self, src: &S) {
        let src_nlimbs = src.nlimbs();
        let dst_nlimbs = self.nlimbs();
        debug_assert!(find_last_set_byte_mp(src) <= self.len());

        if src_nlimbs == 0 {
            self.clear_bytes_above(0);
            return;
        } else if dst_nlimbs == 0 {
            return;
        }
        let common_nlimbs = src_nlimbs.min(dst_nlimbs);
        for i in 0..common_nlimbs - 1 {
            self.store_l_full(i, src.load_l_full(i));
        }
        let high_limb = src.load_l(common_nlimbs - 1);
        debug_assert!(src_nlimbs < dst_nlimbs || (high_limb & !self.partial_high_mask()) == 0);
        self.store_l(common_nlimbs - 1, high_limb);
        self.clear_bytes_above(src.len());
    }

    /// Conditionally copy a multiprecision integer's value.
    ///
    /// If `cond` is true, set this multiprecision integer to the value of
    /// `src`, like [`copy_from()`](Self::copy_from). Otherwise leave it
    /// unmodified. The same requirements on `src` apply in either case.
    ///
    /// Execution time depends only on the two multiprecision integers' [lengths
    /// in units of bytes](MpUIntCommon::len) and is otherwise constant as far
    /// as branching is concerned. In particular, it doesn't depend on `cond`.
    ///
    /// # Arguments
    ///
    /// * `src` - The multiprecision integer to copy the value from.
    /// * `cond` - Whether or not to copy the value.
    fn copy_from_cond<S: MpUIntCommon>(&'_ mut self, src: &S, cond: LimbChoice) {
        let src_nlimbs = src.nlimbs();
        let dst_nlimbs = self.nlimbs();
        debug_assert!(find_last_set_byte_mp(src) <= self.len());

        if src_nlimbs == 0 {
            self.clear_bytes_above_cond(0, cond);
            return;
        } else if dst_nlimbs == 0 {
            return;
        }
        let common_nlimbs = src_nlimbs.min(dst_nlimbs);
        for i in 0..common_nlimbs - 1 {
            let val = cond.select(self.load_l_full(i), src.load_l_full(i));
            self.store_l_full(i, val);
        }
        let high_limb = cond.select(
            self.load_l(common_nlimbs - 1),
            src.load_l(common_nlimbs - 1),
        );
        debug_assert!(src_nlimbs < dst_nlimbs || (high_limb & !self.partial_high_mask()) == 0);
        self.store_l(common_nlimbs - 1, high_limb);
        self.clear_bytes_above_cond(src.len(), cond);
    }

    /// Set a bit of the multiprecision integer to a given value.
    ///
    /// Execution time depends only on the multiprecision integer's [length in
    /// units of bytes](MpUIntCommon::len) and the `pos` argument and is
    /// otherwise constant as far as branching is concerned. In particular, it
    /// doesn't depend on `val`.
    ///
    /// # Arguments
    ///
    /// * `pos` - The position of the bit to set, counted from least to most
    ///   significant. Must be less than 8 times the multiprecision integer's
    ///   [length in units of bytes](MpUIntCommon::len).
    /// * `val` - The value to set the bit to.
    fn set_bit_to(&mut self, pos: usize, val: bool) {
        let limb_index = pos / LIMB_BITS as usize;
        debug_assert!(limb_index < self.nlimbs());
        let pos_in_limb = pos % LIMB_BITS as usize;
        let mut l = self.load_l(limb_index);
        let bit_pos_mask = (1 as LimbType) << pos_in_limb;
        let val_mask = LimbChoice::from(val as LimbType).select(0, bit_pos_mask);
        l &= !bit_pos_mask;
        l |= val_mask;
        self.store_l(limb_index, l)
    }

    _mpu_set_to_native_u!(u8, set_to_u8);
    _mpu_set_to_native_u!(u16, set_to_u16);
    _mpu_set_to_native_u!(u32, set_to_u32);
    _mpu_set_to_native_u!(u64, set_to_u64);
}

/// Common interface to multiprecision integers backed by a single buffer
/// slice.
///
/// Implemented by all of the representation-specific types, read-only and
/// mutable, each of which wraps a single contiguous slice of `u8` or
/// [`LimbType`] elements. It's the common supertrait of [`MpUIntSlice`], for
/// the read-only types, and [`MpMutUIntSlice`], for the mutable ones. It
/// doesn't add any public methods on its own; the slice handling it stands
/// for, like splitting a multiprecision integer into a high and a low part,
/// is crate-internal.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpUIntSliceCommon: MpUIntSliceCommonPriv + MpUIntCommon {}

/// Interface to read-only multiprecision integers backed by a single buffer
/// slice.
///
/// Implemented by the read-only representation-specific types, i.e.
/// [`MpBigEndianUIntByteSlice`], [`MpLittleEndianUIntByteSlice`] and
/// [`MpNativeEndianUIntLimbsSlice`]. In addition to what's provided through the
/// [`MpUInt`] and [`MpUIntSliceCommon`] supertraits, [`MpUIntSlice`] provides
/// for deriving new views of the same representation on the backing buffer
/// slice. See [`MpMutUIntSlice`] for the mutable counterpart.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpUIntSlice: MpUIntSlicePriv + MpUInt {
    /// Reborrow the multiprecision integer with a lifetime bound to `self`.
    ///
    /// Returns a view of the same representation on the same backing buffer
    /// slice, but with its lifetime shortened to that of the `self` borrow.
    /// This makes it the same type as other views derived from `self`, like
    /// the ones returned by [`shrink_to()`](Self::shrink_to), so that these
    /// can be used interchangeably.
    fn coerce_lifetime(&self) -> Self::SelfT<'_>;

    /// Get a view on the multiprecision integer's low part.
    ///
    /// Returns a view of the same representation on the part of the backing
    /// buffer slice holding the `nbytes` least significant bytes, with
    /// `nbytes` aligned upwards if the representation doesn't support
    /// unaligned lengths. The multiprecision integer's value must fit into
    /// this length. That is, all of its bytes at positions `>= nbytes`, counted
    /// from least to most significant, must be zero.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](MpUIntCommon::len) to shrink
    ///   the view to. If it's larger than the multiprecision integer's [length
    ///   in units of bytes](MpUIntCommon::len), the latter is retained.
    fn shrink_to(&self, nbytes: usize) -> Self::SelfT<'_> {
        let nbytes = nbytes.min(self._len());
        debug_assert!(nbytes >= find_last_set_byte_mp(self));
        self._shrink_to(nbytes)
    }
}

/// Interface to mutable multiprecision integers backed by a single buffer
/// slice.
///
/// Implemented by the mutable representation-specific types, i.e.
/// [`MpMutBigEndianUIntByteSlice`], [`MpMutLittleEndianUIntByteSlice`] and
/// [`MpMutNativeEndianUIntLimbsSlice`]. In addition to what's provided through
/// the [`MpMutUInt`] and [`MpUIntSliceCommon`] supertraits, [`MpMutUIntSlice`]
/// provides for deriving new mutable views of the same representation on the
/// backing buffer slice. See [`MpUIntSlice`] for the read-only counterpart.
///
/// The trait is sealed, i.e. it cannot be implemented outside of this crate.
pub trait MpMutUIntSlice: MpMutUIntSlicePriv + MpMutUInt {
    /// Reborrow the multiprecision integer with a lifetime bound to `self`.
    ///
    /// Returns a mutable view of the same representation on the same backing
    /// buffer slice, but with its lifetime shortened to that of the `self`
    /// borrow. This makes it the same type as other views derived from
    /// `self`, like the ones returned by [`shrink_to()`](Self::shrink_to), so
    /// that these can be used interchangeably. `self` remains mutably borrowed
    /// for as long as the view is alive.
    fn coerce_lifetime(&mut self) -> Self::SelfT<'_>;

    /// Get a mutable view on the multiprecision integer's low part.
    ///
    /// Returns a mutable view of the same representation on the part of the
    /// backing buffer slice holding the `nbytes` least significant bytes, with
    /// `nbytes` aligned upwards if the representation doesn't support
    /// unaligned lengths. Writes through the view modify the original
    /// multiprecision integer's low part, while its high part beyond the view
    /// is left alone. `self` remains mutably borrowed for as long as the view
    /// is alive. The multiprecision integer's value must fit into this length.
    /// That is, all of its bytes at positions `>= nbytes`, counted from least
    /// to most significant, must be zero.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The [length in units of bytes](MpUIntCommon::len) to shrink
    ///   the view to. If it's larger than the multiprecision integer's [length
    ///   in units of bytes](MpUIntCommon::len), the latter is retained.
    fn shrink_to(&mut self, nbytes: usize) -> Self::SelfT<'_> {
        let nbytes = nbytes.min(self._len());
        debug_assert!(nbytes >= find_last_set_byte_mp(self));
        self._shrink_to(nbytes)
    }
}

/// Read-only multiprecision integer stored in a big-endian byte slice.
///
/// Wraps a `u8` slice holding a multiprecision integer in big-endian order,
/// i.e. most significant byte first. The integer's [length in units of
/// bytes](MpUIntCommon::len) equals the slice's length and doesn't need to be a
/// multiple of the [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_bytes()`](Self::from_bytes) wraps a `u8` slice.
/// - [`as_bytes()`](Self::as_bytes) and the [`From`] implementation for
///   `&[u8]` return the wrapped slice.
/// - The [`From`] implementation for `&MpMutBigEndianUIntByteSlice` creates a
///   read-only view on a [`MpMutBigEndianUIntByteSlice`].
///
/// See [`MpMutBigEndianUIntByteSlice`] for the mutable variant.
#[derive(Clone, Copy)]
pub struct MpBigEndianUIntByteSlice<'a> {
    /// The wrapped byte slice, holding the multiprecision integer in
    /// big-endian order, i.e. most significant byte first.
    bytes: &'a [u8],
}

impl<'a> MpBigEndianUIntByteSlice<'a> {
    /// Wrap a big-endian byte slice as a multiprecision integer.
    ///
    /// # Arguments
    ///
    /// * `bytes` - The byte slice holding the multiprecision integer in
    ///   big-endian order.
    pub fn from_bytes(bytes: &'a [u8]) -> Self {
        Self { bytes }
    }

    /// Get the wrapped big-endian byte slice.
    ///
    /// The returned slice has the full lifetime `'a` of the wrapped one.
    pub fn as_bytes(&self) -> &'a [u8] {
        self.bytes
    }
}

impl<'a> MpUIntCommonPriv for MpBigEndianUIntByteSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = true;

    fn _len(&self) -> usize {
        self.bytes.len()
    }
}

impl<'a> MpUIntCommon for MpBigEndianUIntByteSlice<'a> {
    fn is_empty(&self) -> bool {
        self.bytes.is_empty()
    }

    fn load_l_full(&self, i: usize) -> LimbType {
        be_mp_load_l_full(self.bytes, i)
    }

    fn load_l(&self, i: usize) -> LimbType {
        be_mp_load_l(self.bytes, i)
    }
}

impl<'a> MpUInt for MpBigEndianUIntByteSlice<'a> {}

impl<'a> MpUIntSliceCommonPriv for MpBigEndianUIntByteSlice<'a> {
    type BackingSliceElementType = u8;

    fn n_backing_elements(&self) -> usize {
        self.bytes.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        let (h, l) = self.bytes.split_at(self.bytes.len() - nbytes);
        (Self { bytes: h }, Self { bytes: l })
    }
}

impl<'a> MpUIntSliceCommon for MpBigEndianUIntByteSlice<'a> {}

impl<'a> MpUIntSlicePriv for MpBigEndianUIntByteSlice<'a> {
    type SelfT<'b>
        = MpBigEndianUIntByteSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { bytes: s })
    }

    fn _shrink_to(&self, nbytes: usize) -> Self::SelfT<'_> {
        MpBigEndianUIntByteSlice {
            bytes: &self.bytes[self.bytes.len() - nbytes..],
        }
    }
}

impl<'a> MpUIntSlice for MpBigEndianUIntByteSlice<'a> {
    fn coerce_lifetime(&self) -> Self::SelfT<'_> {
        MpBigEndianUIntByteSlice { bytes: self.bytes }
    }
}

impl<'a> fmt::LowerHex for MpBigEndianUIntByteSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a MpMutBigEndianUIntByteSlice<'b>> for MpBigEndianUIntByteSlice<'a> {
    fn from(value: &'a MpMutBigEndianUIntByteSlice<'b>) -> Self {
        Self { bytes: value.bytes }
    }
}

impl<'a> From<MpBigEndianUIntByteSlice<'a>> for &'a [u8] {
    fn from(value: MpBigEndianUIntByteSlice<'a>) -> Self {
        value.bytes
    }
}

/// Mutable multiprecision integer stored in a big-endian byte slice.
///
/// Wraps a mutable `u8` slice holding a multiprecision integer in big-endian
/// order, i.e. most significant byte first. The integer's [length in units of
/// bytes](MpUIntCommon::len) equals the slice's length and doesn't need to be a
/// multiple of the [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_bytes()`](Self::from_bytes) wraps a mutable `u8` slice.
/// - [`as_bytes()`](Self::as_bytes) and [`as_bytes_mut()`](Self::as_bytes_mut),
///   as well as the [`From`] implementations of `&[u8]` and `&mut [u8]` for
///   references to a [`MpMutBigEndianUIntByteSlice`], borrow the wrapped slice.
///
/// A read-only [`MpBigEndianUIntByteSlice`] view can be obtained through the
/// latter's [`From`] implementation for `&MpMutBigEndianUIntByteSlice`.
pub struct MpMutBigEndianUIntByteSlice<'a> {
    /// The wrapped byte slice, holding the multiprecision integer in
    /// big-endian order, i.e. most significant byte first.
    bytes: &'a mut [u8],
}

impl<'a> MpMutBigEndianUIntByteSlice<'a> {
    /// Wrap a mutable big-endian byte slice as a multiprecision integer.
    ///
    /// # Arguments
    ///
    /// * `bytes` - The byte slice holding the multiprecision integer in
    ///   big-endian order.
    pub fn from_bytes(bytes: &'a mut [u8]) -> Self {
        Self { bytes }
    }

    /// Borrow the wrapped big-endian byte slice.
    pub fn as_bytes(&self) -> &[u8] {
        self.bytes
    }

    /// Mutably borrow the wrapped big-endian byte slice.
    pub fn as_bytes_mut(&mut self) -> &mut [u8] {
        self.bytes
    }
}

impl<'a> MpUIntCommonPriv for MpMutBigEndianUIntByteSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = true;

    fn _len(&self) -> usize {
        self.bytes.len()
    }
}

impl<'a> MpUIntCommon for MpMutBigEndianUIntByteSlice<'a> {
    fn is_empty(&self) -> bool {
        self.bytes.is_empty()
    }

    fn load_l_full(&self, i: usize) -> LimbType {
        be_mp_load_l_full(self.bytes, i)
    }

    fn load_l(&self, i: usize) -> LimbType {
        be_mp_load_l(self.bytes, i)
    }
}

impl<'a> MpMutUInt for MpMutBigEndianUIntByteSlice<'a> {
    fn store_l_full(&mut self, i: usize, value: LimbType) {
        be_mp_store_l_full(self.bytes, i, value)
    }

    fn store_l(&mut self, i: usize, value: LimbType) {
        be_mp_store_l(self.bytes, i, value)
    }

    fn clear_bytes_above(&mut self, begin: usize) {
        be_mp_clear_bytes_above(self.bytes, begin)
    }

    fn clear_bytes_below(&mut self, end: usize) {
        be_mp_clear_bytes_below(self.bytes, end)
    }
}

impl<'a> MpUIntSliceCommonPriv for MpMutBigEndianUIntByteSlice<'a> {
    type BackingSliceElementType = u8;

    fn n_backing_elements(&self) -> usize {
        self.bytes.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        let (h, l) = self.bytes.split_at_mut(self.bytes.len() - nbytes);
        (Self { bytes: h }, Self { bytes: l })
    }
}

impl<'a> MpUIntSliceCommon for MpMutBigEndianUIntByteSlice<'a> {}

impl<'a> MpMutUIntSlicePriv for MpMutBigEndianUIntByteSlice<'a> {
    type SelfT<'b>
        = MpMutBigEndianUIntByteSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b mut [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { bytes: s })
    }

    fn _shrink_to(&mut self, nbytes: usize) -> Self::SelfT<'_> {
        let l = self.bytes.len();
        MpMutBigEndianUIntByteSlice {
            bytes: &mut self.bytes[l - nbytes..],
        }
    }
}

impl<'a> MpMutUIntSlice for MpMutBigEndianUIntByteSlice<'a> {
    fn coerce_lifetime(&mut self) -> Self::SelfT<'_> {
        MpMutBigEndianUIntByteSlice { bytes: self.bytes }
    }
}

impl<'a> fmt::LowerHex for MpMutBigEndianUIntByteSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a mut MpMutBigEndianUIntByteSlice<'b>> for &'a mut [u8] {
    fn from(value: &'a mut MpMutBigEndianUIntByteSlice<'b>) -> Self {
        value.bytes
    }
}

impl<'a, 'b> From<&'a MpMutBigEndianUIntByteSlice<'b>> for &'a [u8] {
    fn from(value: &'a MpMutBigEndianUIntByteSlice<'b>) -> Self {
        value.bytes
    }
}

/// Read-only multiprecision integer stored in a little-endian byte slice.
///
/// Wraps a `u8` slice holding a multiprecision integer in little-endian order,
/// i.e. least significant byte first. The integer's [length in units of
/// bytes](MpUIntCommon::len) equals the slice's length and doesn't need to be a
/// multiple of the [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_bytes()`](Self::from_bytes) wraps a `u8` slice.
/// - [`as_bytes()`](Self::as_bytes) and the [`From`] implementation for
///   `&[u8]` return the wrapped slice.
/// - The [`From`] implementation for `&MpMutLittleEndianUIntByteSlice` creates a
///   read-only view on a [`MpMutLittleEndianUIntByteSlice`].
///
/// See [`MpMutLittleEndianUIntByteSlice`] for the mutable variant.
#[derive(Clone, Copy)]
pub struct MpLittleEndianUIntByteSlice<'a> {
    /// The wrapped byte slice, holding the multiprecision integer in
    /// little-endian order, i.e. least significant byte first.
    bytes: &'a [u8],
}

impl<'a> MpLittleEndianUIntByteSlice<'a> {
    /// Wrap a little-endian byte slice as a multiprecision integer.
    ///
    /// # Arguments
    ///
    /// * `bytes` - The byte slice holding the multiprecision integer in
    ///   little-endian order.
    pub fn from_bytes(bytes: &'a [u8]) -> Self {
        Self { bytes }
    }

    /// Get the wrapped little-endian byte slice.
    ///
    /// The returned slice has the full lifetime `'a` of the wrapped one.
    pub fn as_bytes(&self) -> &'a [u8] {
        self.bytes
    }
}

impl<'a> MpUIntCommonPriv for MpLittleEndianUIntByteSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = true;

    fn _len(&self) -> usize {
        self.bytes.len()
    }
}

impl<'a> MpUIntCommon for MpLittleEndianUIntByteSlice<'a> {
    fn is_empty(&self) -> bool {
        self.bytes.is_empty()
    }

    fn load_l_full(&self, i: usize) -> LimbType {
        le_mp_load_l_full(self.bytes, i)
    }

    fn load_l(&self, i: usize) -> LimbType {
        le_mp_load_l(self.bytes, i)
    }
}

impl<'a> MpUInt for MpLittleEndianUIntByteSlice<'a> {}

impl<'a> MpUIntSliceCommonPriv for MpLittleEndianUIntByteSlice<'a> {
    type BackingSliceElementType = u8;

    fn n_backing_elements(&self) -> usize {
        self.bytes.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        let (l, h) = self.bytes.split_at(nbytes);
        (Self { bytes: h }, Self { bytes: l })
    }
}

impl<'a> MpUIntSliceCommon for MpLittleEndianUIntByteSlice<'a> {}

impl<'a> MpUIntSlicePriv for MpLittleEndianUIntByteSlice<'a> {
    type SelfT<'b>
        = MpLittleEndianUIntByteSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { bytes: s })
    }

    fn _shrink_to(&self, nbytes: usize) -> Self::SelfT<'_> {
        MpLittleEndianUIntByteSlice {
            bytes: &self.bytes[..nbytes],
        }
    }
}

impl<'a> MpUIntSlice for MpLittleEndianUIntByteSlice<'a> {
    fn coerce_lifetime(&self) -> Self::SelfT<'_> {
        MpLittleEndianUIntByteSlice { bytes: self.bytes }
    }
}

impl<'a> fmt::LowerHex for MpLittleEndianUIntByteSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a MpMutLittleEndianUIntByteSlice<'b>> for MpLittleEndianUIntByteSlice<'a> {
    fn from(value: &'a MpMutLittleEndianUIntByteSlice<'b>) -> Self {
        Self { bytes: value.bytes }
    }
}

impl<'a> From<MpLittleEndianUIntByteSlice<'a>> for &'a [u8] {
    fn from(value: MpLittleEndianUIntByteSlice<'a>) -> Self {
        value.bytes
    }
}

/// Mutable multiprecision integer stored in a little-endian byte slice.
///
/// Wraps a mutable `u8` slice holding a multiprecision integer in little-endian
/// order, i.e. least significant byte first. The integer's [length in units of
/// bytes](MpUIntCommon::len) equals the slice's length and doesn't need to be a
/// multiple of the [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_bytes()`](Self::from_bytes) wraps a mutable `u8` slice.
/// - [`as_bytes()`](Self::as_bytes) and [`as_bytes_mut()`](Self::as_bytes_mut),
///   as well as the [`From`] implementations of `&[u8]` and `&mut [u8]` for
///   references to a [`MpMutLittleEndianUIntByteSlice`], borrow the wrapped slice.
///
/// A read-only [`MpLittleEndianUIntByteSlice`] view can be obtained through the
/// latter's [`From`] implementation for `&MpMutLittleEndianUIntByteSlice`.
pub struct MpMutLittleEndianUIntByteSlice<'a> {
    /// The wrapped byte slice, holding the multiprecision integer in
    /// little-endian order, i.e. least significant byte first.
    bytes: &'a mut [u8],
}

impl<'a> MpMutLittleEndianUIntByteSlice<'a> {
    /// Wrap a mutable little-endian byte slice as a multiprecision integer.
    ///
    /// # Arguments
    ///
    /// * `bytes` - The byte slice holding the multiprecision integer in
    ///   little-endian order.
    pub fn from_bytes(bytes: &'a mut [u8]) -> Self {
        Self { bytes }
    }

    /// Borrow the wrapped little-endian byte slice.
    pub fn as_bytes(&self) -> &[u8] {
        self.bytes
    }

    /// Mutably borrow the wrapped little-endian byte slice.
    pub fn as_bytes_mut(&mut self) -> &mut [u8] {
        self.bytes
    }
}

impl<'a> MpUIntCommonPriv for MpMutLittleEndianUIntByteSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = true;

    fn _len(&self) -> usize {
        self.bytes.len()
    }
}

impl<'a> MpUIntCommon for MpMutLittleEndianUIntByteSlice<'a> {
    fn is_empty(&self) -> bool {
        self.bytes.is_empty()
    }

    fn load_l_full(&self, i: usize) -> LimbType {
        le_mp_load_l_full(self.bytes, i)
    }

    fn load_l(&self, i: usize) -> LimbType {
        le_mp_load_l(self.bytes, i)
    }
}

impl<'a> MpMutUInt for MpMutLittleEndianUIntByteSlice<'a> {
    fn store_l_full(&mut self, i: usize, value: LimbType) {
        le_mp_store_l_full(self.bytes, i, value)
    }

    fn store_l(&mut self, i: usize, value: LimbType) {
        le_mp_store_l(self.bytes, i, value)
    }

    fn clear_bytes_above(&mut self, begin: usize) {
        le_mp_clear_bytes_above(self.bytes, begin)
    }

    fn clear_bytes_below(&mut self, end: usize) {
        le_mp_clear_bytes_below(self.bytes, end)
    }
}

impl<'a> MpUIntSliceCommonPriv for MpMutLittleEndianUIntByteSlice<'a> {
    type BackingSliceElementType = u8;

    fn n_backing_elements(&self) -> usize {
        self.bytes.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        let (l, h) = self.bytes.split_at_mut(nbytes);
        (Self { bytes: h }, Self { bytes: l })
    }
}

impl<'a> MpUIntSliceCommon for MpMutLittleEndianUIntByteSlice<'a> {}

impl<'a> MpMutUIntSlicePriv for MpMutLittleEndianUIntByteSlice<'a> {
    type SelfT<'b>
        = MpMutLittleEndianUIntByteSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b mut [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { bytes: s })
    }

    fn _shrink_to(&mut self, nbytes: usize) -> Self::SelfT<'_> {
        MpMutLittleEndianUIntByteSlice {
            bytes: &mut self.bytes[..nbytes],
        }
    }
}

impl<'a> MpMutUIntSlice for MpMutLittleEndianUIntByteSlice<'a> {
    fn coerce_lifetime(&mut self) -> Self::SelfT<'_> {
        MpMutLittleEndianUIntByteSlice { bytes: self.bytes }
    }
}

impl<'a> fmt::LowerHex for MpMutLittleEndianUIntByteSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a mut MpMutLittleEndianUIntByteSlice<'b>> for &'a mut [u8] {
    fn from(value: &'a mut MpMutLittleEndianUIntByteSlice<'b>) -> Self {
        value.bytes
    }
}

impl<'a, 'b> From<&'a MpMutLittleEndianUIntByteSlice<'b>> for &'a [u8] {
    fn from(value: &'a MpMutLittleEndianUIntByteSlice<'b>) -> Self {
        value.bytes
    }
}

/// Read-only multiprecision integer stored in a native-endian [`LimbType`]
/// slice.
///
/// Wraps a [`LimbType`] slice holding a multiprecision integer in units of
/// [`LimbType`], least significant limb first, with each limb in the host's
/// native endianess. This is the most efficient representation to operate on.
/// The integer's [length in units of bytes](MpUIntCommon::len) equals the
/// slice's length in units of bytes and thus is always a multiple of the
/// [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_limbs()`](Self::from_limbs) wraps a [`LimbType`] slice. Use
///   [`nlimbs_for_len()`](Self::nlimbs_for_len) for allocating a suitably
///   sized one.
/// - [`as_limbs()`](Self::as_limbs) and the [`From`] implementation for
///   `&[LimbType]` return the wrapped slice.
/// - The [`From`] implementation for `&MpMutNativeEndianUIntLimbsSlice` creates a
///   read-only view on a [`MpMutNativeEndianUIntLimbsSlice`].
///
/// See [`MpMutNativeEndianUIntLimbsSlice`] for the mutable variant.
#[derive(Clone, Copy)]
pub struct MpNativeEndianUIntLimbsSlice<'a> {
    /// The wrapped [`LimbType`] slice, holding the multiprecision integer's
    /// limbs least significant first, each in the host's native endianess.
    limbs: &'a [LimbType],
}

impl<'a> MpNativeEndianUIntLimbsSlice<'a> {
    /// Wrap a native-endian [`LimbType`] slice as a multiprecision integer.
    ///
    /// # Arguments
    ///
    /// * `limbs` - The [`LimbType`] slice holding the multiprecision integer,
    ///   least significant limb first.
    pub fn from_limbs(limbs: &'a [LimbType]) -> Self {
        Self { limbs }
    }

    /// Get the wrapped native-endian [`LimbType`] slice.
    ///
    /// The returned slice has the full lifetime `'a` of the wrapped one.
    pub fn as_limbs(&self) -> &'a [LimbType] {
        self.limbs
    }

    /// The number of [`LimbType`]s needed for a given [length in units of
    /// bytes](MpUIntCommon::len).
    ///
    /// Returns the number of [`LimbType`] elements a slice must have for
    /// holding a multiprecision integer of [length in units of
    /// bytes](MpUIntCommon::len) `nbytes`, i.e. `nbytes` converted to units of
    /// [`LimbType`], rounding up. Useful for allocating suitably sized buffers.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The multiprecision integer's [length in units of
    ///   bytes](MpUIntCommon::len).
    pub fn nlimbs_for_len(nbytes: usize) -> usize {
        Self::n_backing_elements_for_len(nbytes)
    }
}

impl<'a> MpUIntCommonPriv for MpNativeEndianUIntLimbsSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = false;

    fn _len(&self) -> usize {
        self.limbs.len() * Self::BACKING_ELEMENT_SIZE
    }
}

impl<'a> MpUIntCommon for MpNativeEndianUIntLimbsSlice<'a> {
    fn is_empty(&self) -> bool {
        self.limbs.is_empty()
    }

    #[inline(always)]
    fn load_l_full(&self, i: usize) -> LimbType {
        self.limbs[i]
    }

    #[inline(always)]
    fn load_l(&self, i: usize) -> LimbType {
        self.load_l_full(i)
    }
}

impl<'a> MpUInt for MpNativeEndianUIntLimbsSlice<'a> {}

impl<'a> MpUIntSliceCommonPriv for MpNativeEndianUIntLimbsSlice<'a> {
    type BackingSliceElementType = LimbType;

    fn n_backing_elements(&self) -> usize {
        self.limbs.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        debug_assert_eq!(nbytes % LIMB_BYTES, 0);
        let (l, h) = self
            .limbs
            .split_at(Self::n_backing_elements_for_len(nbytes));
        (Self { limbs: h }, Self { limbs: l })
    }
}

impl<'a> MpUIntSliceCommon for MpNativeEndianUIntLimbsSlice<'a> {}

impl<'a> MpUIntSlicePriv for MpNativeEndianUIntLimbsSlice<'a> {
    type SelfT<'b>
        = MpNativeEndianUIntLimbsSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { limbs: s })
    }

    fn _shrink_to(&self, nbytes: usize) -> Self::SelfT<'_> {
        let nlimbs = Self::n_backing_elements_for_len(nbytes);
        MpNativeEndianUIntLimbsSlice {
            limbs: &self.limbs[..nlimbs],
        }
    }
}

impl<'a> MpUIntSlice for MpNativeEndianUIntLimbsSlice<'a> {
    fn coerce_lifetime(&self) -> Self::SelfT<'_> {
        MpNativeEndianUIntLimbsSlice { limbs: self.limbs }
    }
}

impl<'a> fmt::LowerHex for MpNativeEndianUIntLimbsSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a MpMutNativeEndianUIntLimbsSlice<'b>> for MpNativeEndianUIntLimbsSlice<'a> {
    fn from(value: &'a MpMutNativeEndianUIntLimbsSlice<'b>) -> Self {
        Self { limbs: value.limbs }
    }
}

impl<'a> From<MpNativeEndianUIntLimbsSlice<'a>> for &'a [LimbType] {
    fn from(value: MpNativeEndianUIntLimbsSlice<'a>) -> Self {
        value.limbs
    }
}

/// Mutable multiprecision integer stored in a native-endian [`LimbType`] slice.
///
/// Wraps a mutable [`LimbType`] slice holding a multiprecision integer in units
/// of [`LimbType`], least significant limb first, with each limb in the host's
/// native endianess. This is the most efficient representation to operate on.
/// The integer's [length in units of bytes](MpUIntCommon::len) equals the
/// slice's length in units of bytes and thus is always a multiple of the
/// [`LimbType`] size.
///
/// For converting from and to the wrapped slice, the following primitives are
/// provided:
/// - [`from_limbs()`](Self::from_limbs) wraps a mutable [`LimbType`] slice. Use
///   [`nlimbs_for_len()`](Self::nlimbs_for_len) for allocating a suitably
///   sized one.
/// - [`as_limbs()`](Self::as_limbs) and [`as_limbs_mut()`](Self::as_limbs_mut),
///   as well as the [`From`] implementations of `&[LimbType]` and
///   `&mut [LimbType]` for references to a [`MpMutNativeEndianUIntLimbsSlice`],
///   borrow the wrapped slice.
///
/// A read-only [`MpNativeEndianUIntLimbsSlice`] view can be obtained through the
/// latter's [`From`] implementation for `&MpMutNativeEndianUIntLimbsSlice`.
pub struct MpMutNativeEndianUIntLimbsSlice<'a> {
    /// The wrapped [`LimbType`] slice, holding the multiprecision integer's
    /// limbs least significant first, each in the host's native endianess.
    limbs: &'a mut [LimbType],
}

impl<'a> MpMutNativeEndianUIntLimbsSlice<'a> {
    /// Wrap a mutable native-endian [`LimbType`] slice as a multiprecision
    /// integer.
    ///
    /// # Arguments
    ///
    /// * `limbs` - The [`LimbType`] slice holding the multiprecision integer,
    ///   least significant limb first.
    pub fn from_limbs(limbs: &'a mut [LimbType]) -> Self {
        Self { limbs }
    }

    /// Borrow the wrapped native-endian [`LimbType`] slice.
    pub fn as_limbs(&self) -> &[LimbType] {
        self.limbs
    }

    /// Mutably borrow the wrapped native-endian [`LimbType`] slice.
    pub fn as_limbs_mut(&mut self) -> &mut [LimbType] {
        self.limbs
    }

    /// The number of [`LimbType`]s needed for a given [length in units of
    /// bytes](MpUIntCommon::len).
    ///
    /// Returns the number of [`LimbType`] elements a slice must have for
    /// holding a multiprecision integer of [length in units of
    /// bytes](MpUIntCommon::len) `nbytes`, i.e. `nbytes` converted to units of
    /// [`LimbType`], rounding up. Useful for allocating suitably sized buffers.
    ///
    /// # Arguments
    ///
    /// * `nbytes` - The multiprecision integer's [length in units of
    ///   bytes](MpUIntCommon::len).
    pub fn nlimbs_for_len(nbytes: usize) -> usize {
        Self::n_backing_elements_for_len(nbytes)
    }
}

impl<'a> MpUIntCommonPriv for MpMutNativeEndianUIntLimbsSlice<'a> {
    const SUPPORTS_UNALIGNED_BUFFER_LENGTHS: bool = false;

    fn _len(&self) -> usize {
        self.limbs.len() * Self::BACKING_ELEMENT_SIZE
    }
}

impl<'a> MpUIntCommon for MpMutNativeEndianUIntLimbsSlice<'a> {
    fn is_empty(&self) -> bool {
        self.limbs.is_empty()
    }

    #[inline(always)]
    fn load_l_full(&self, i: usize) -> LimbType {
        self.limbs[i]
    }

    #[inline(always)]
    fn load_l(&self, i: usize) -> LimbType {
        self.load_l_full(i)
    }
}

impl<'a> MpMutUInt for MpMutNativeEndianUIntLimbsSlice<'a> {
    #[inline(always)]
    fn store_l_full(&mut self, i: usize, value: LimbType) {
        self.limbs[i] = value;
    }

    #[inline(always)]
    fn store_l(&mut self, i: usize, value: LimbType) {
        self.store_l_full(i, value);
    }

    fn clear_bytes_above(&mut self, begin: usize) {
        let mut begin_limb = begin / LIMB_BYTES;
        if begin_limb >= self.limbs.len() {
            return;
        }
        let begin_in_limb = begin % LIMB_BYTES;
        if begin_in_limb != 0 {
            self.limbs[begin_limb] &= ct_lsb_mask_l(8 * begin_in_limb as u32);
            begin_limb += 1;
        }
        self.limbs[begin_limb..].fill(0);
    }

    fn clear_bytes_below(&mut self, end: usize) {
        let end = end.min(self.len());
        let mut end_limb = ct_mp_nlimbs(end);
        let end_in_limb = end % LIMB_BYTES;
        if end_in_limb != 0 {
            end_limb -= 1;
            let mut l = self.load_l(end_limb);
            l >>= 8 * end_in_limb;
            l <<= 8 * end_in_limb;
            self.limbs[end_limb] = l;
        }
        self.limbs[..end_limb].fill(0);
    }
}

#[cfg(test)]
fn test_clear_bytes_below_with_aligned_lengths<T0: MpMutUIntSlice>() {
    let mut op0 = tst_mk_mp_backing_vec!(T0, 0);
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.clear_bytes_below(1);
    assert!(op0.is_empty());

    let mut op0 = tst_mk_mp_backing_vec!(T0, 2 * LIMB_BYTES);
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, !0);
    op0.store_l(1, !0);
    op0.clear_bytes_below(0);
    assert_eq!(op0.load_l(0), !0);
    assert_eq!(op0.load_l(1), !0);

    op0.clear_bytes_below(LIMB_BYTES + 1);
    assert_eq!(op0.load_l(0), 0);
    assert_eq!(op0.load_l(1), !0 << 8);

    op0.store_l(0, !0);
    op0.store_l(1, !0);
    op0.clear_bytes_below(2 * LIMB_BYTES);
    assert_eq!(op0.load_l(0), 0);
    assert_eq!(op0.load_l(1), 0);

    op0.store_l(0, !0);
    op0.store_l(1, !0);
    op0.clear_bytes_below(2 * LIMB_BYTES + 1);
    assert_eq!(op0.load_l(0), 0);
    assert_eq!(op0.load_l(1), 0);
}

#[test]
fn test_clear_bytes_below_be() {
    test_clear_bytes_below_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_clear_bytes_below_le() {
    test_clear_bytes_below_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_clear_bytes_below_ne() {
    test_clear_bytes_below_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

impl<'a> MpUIntSliceCommonPriv for MpMutNativeEndianUIntLimbsSlice<'a> {
    type BackingSliceElementType = LimbType;

    fn n_backing_elements(&self) -> usize {
        self.limbs.len()
    }

    fn take(self, nbytes: usize) -> (Self, Self) {
        debug_assert_eq!(nbytes % LIMB_BYTES, 0);
        let (l, h) = self
            .limbs
            .split_at_mut(Self::n_backing_elements_for_len(nbytes));
        (Self { limbs: h }, Self { limbs: l })
    }
}

impl<'a> MpUIntSliceCommon for MpMutNativeEndianUIntLimbsSlice<'a> {}

impl<'a> MpMutUIntSlicePriv for MpMutNativeEndianUIntLimbsSlice<'a> {
    type SelfT<'b>
        = MpMutNativeEndianUIntLimbsSlice<'b>
    where
        Self: 'b;

    type FromSliceError = convert::Infallible;

    fn from_slice<'b: 'c, 'c>(
        s: &'b mut [Self::BackingSliceElementType],
    ) -> Result<Self::SelfT<'c>, Self::FromSliceError>
    where
        Self: 'c,
    {
        Ok(Self::SelfT::<'c> { limbs: s })
    }

    fn _shrink_to(&mut self, nbytes: usize) -> Self::SelfT<'_> {
        let nlimbs = Self::n_backing_elements_for_len(nbytes);
        MpMutNativeEndianUIntLimbsSlice {
            limbs: &mut self.limbs[..nlimbs],
        }
    }
}

impl<'a> MpMutUIntSlice for MpMutNativeEndianUIntLimbsSlice<'a> {
    fn coerce_lifetime(&mut self) -> Self::SelfT<'_> {
        MpMutNativeEndianUIntLimbsSlice { limbs: self.limbs }
    }
}

impl<'a> fmt::LowerHex for MpMutNativeEndianUIntLimbsSlice<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.fmt_lower_hex(f)
    }
}

impl<'a, 'b> From<&'a mut MpMutNativeEndianUIntLimbsSlice<'b>> for &'a mut [LimbType] {
    fn from(value: &'a mut MpMutNativeEndianUIntLimbsSlice<'b>) -> Self {
        value.limbs
    }
}

impl<'a, 'b> From<&'a MpMutNativeEndianUIntLimbsSlice<'b>> for &'a [LimbType] {
    fn from(value: &'a MpMutNativeEndianUIntLimbsSlice<'b>) -> Self {
        value.limbs
    }
}

/// Find a multiprecision integer's most significant non-zero limb.
///
/// Returns the position past the most significant non-zero limb in units of
/// [`LimbType`], if any, zero otherwise. That is, return the number of limbs
/// needed for representing the value.
///
/// Execution time depends on the multiprecision integer's value. Not to be
/// used with secret values.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer whose most significant non-zero limb
///   to find.
fn find_last_set_limb<T0: MpUIntCommon>(op0: &T0) -> usize {
    let mut nlimbs = op0.nlimbs();
    if nlimbs == 0 {
        return 0;
    }

    if op0.load_l(nlimbs - 1) == 0 {
        nlimbs -= 1;
        while nlimbs > 0 {
            if op0.load_l_full(nlimbs - 1) != 0 {
                break;
            }
            nlimbs -= 1;
        }
    }

    nlimbs
}

#[cfg(test)]
fn test_find_last_set_limb_with_unaligned_lengths<
    T0: MpMutUIntSlice<BackingSliceElementType = u8>,
>() {
    let mut op0 = [0u8; 2 * LIMB_BYTES + 2];
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, 1);
    assert_eq!(find_last_set_limb(&op0), 1);

    op0.store_l(1, 1);
    assert_eq!(find_last_set_limb(&op0), 2);

    op0.store_l(2, 1);
    assert_eq!(find_last_set_limb(&op0), 3);
}

#[cfg(test)]
fn test_find_last_set_limb_with_aligned_lengths<T0: MpMutUIntSlice>() {
    let mut op0 = tst_mk_mp_backing_vec!(T0, 0);
    let op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    assert_eq!(find_last_set_limb(&op0), 0);

    let mut op0 = tst_mk_mp_backing_vec!(T0, 2 * LIMB_BYTES);
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    assert_eq!(find_last_set_limb(&op0), 0);

    op0.store_l(0, 1);
    assert_eq!(find_last_set_limb(&op0), 1);

    op0.store_l(1, 1);
    assert_eq!(find_last_set_limb(&op0), 2);
}

#[test]
fn test_find_last_set_limb_be() {
    test_find_last_set_limb_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_find_last_set_limb_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_find_last_set_limb_le() {
    test_find_last_set_limb_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_find_last_set_limb_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_find_last_set_limb_ne() {
    test_find_last_set_limb_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Find a multiprecision integer's most significant non-zero byte.
///
/// Returns the position past the most significant non-zero byte in units of
/// bytes, if any, zero otherwise. That is, return the number of bytes needed
/// for representing the value.
///
/// Execution time depends on the multiprecision integer's value. Not to be
/// used with secret values. See [`ct_find_last_set_byte_mp()`] for the
/// constant-time variant and [`ct_find_last_set_bit_mp()`] for finding the
/// most significant set bit instead.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer whose most significant non-zero byte
///   to find.
pub fn find_last_set_byte_mp<T0: MpUIntCommon>(op0: &T0) -> usize {
    let nlimbs = find_last_set_limb(op0);
    if nlimbs == 0 {
        return 0;
    }
    let nlimbs = nlimbs - 1;
    nlimbs * LIMB_BYTES + ct_find_last_set_byte_l(op0.load_l(nlimbs))
}

#[cfg(test)]
fn test_find_last_set_byte_mp_with_unaligned_lengths<
    T0: MpMutUIntSlice<BackingSliceElementType = u8>,
>() {
    let mut op0 = [0u8; 2 * LIMB_BYTES + 2];
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, 1);
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, 1);

    op0.store_l(1, 1);
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, LIMB_BYTES + 1);

    op0.store_l(2, 1);
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, 2 * LIMB_BYTES + 1);
}

#[cfg(test)]
fn test_find_last_set_byte_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    let mut op0 = tst_mk_mp_backing_vec!(T0, 0);
    let op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, 0);

    let mut op0 = tst_mk_mp_backing_vec!(T0, 2 * LIMB_BYTES);
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, (1 as LimbType) << (LIMB_BITS - 1));
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, LIMB_BYTES);

    op0.store_l(1, (1 as LimbType) << (LIMB_BITS - 1));
    assert_eq!(ct_find_last_set_byte_mp(&op0).1, 2 * LIMB_BYTES);
}

#[test]
fn test_find_last_set_byte_be() {
    test_find_last_set_byte_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_find_last_set_byte_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_find_last_set_byte_le() {
    test_find_last_set_byte_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_find_last_set_byte_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_find_last_set_byte_ne() {
    test_find_last_set_byte_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Find a multiprecision integer's most significant non-zero byte in constant
/// time.
///
/// Returns a pair of a [`LimbChoice`] representing whether the
/// multiprecision integer is non-zero, and the position past its most
/// significant non-zero byte in units of bytes, if any, zero otherwise. That
/// is, the latter is the number of bytes needed for representing the value.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and is otherwise constant as far as branching
/// is concerned. See [`find_last_set_byte_mp()`] for the non-constant-time
/// variant and [`ct_find_last_set_bit_mp()`] for finding the most significant
/// set bit instead.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer whose most significant non-zero byte
///   to find.
pub fn ct_find_last_set_byte_mp<T0: MpUIntCommon>(op0: &T0) -> (LimbChoice, usize) {
    let mut head_is_zero = LimbChoice::from(1);
    let mut nleading_zeroes: usize = 0;
    let mut i = op0.nlimbs();
    while i > 0 {
        i -= 1;
        let op0_val = op0.load_l(i);
        nleading_zeroes += head_is_zero.select(
            0,
            LIMB_BYTES as LimbType - ct_find_last_set_byte_l(op0_val) as LimbType,
        ) as usize;
        head_is_zero &= LimbChoice::from(ct_is_zero_l(op0_val));
    }
    (!head_is_zero, op0.nlimbs() * LIMB_BYTES - nleading_zeroes)
}

#[cfg(test)]
fn test_ct_find_last_set_byte_mp_with_unaligned_lengths<
    T0: MpMutUIntSlice<BackingSliceElementType = u8>,
>() {
    let mut op0 = [0u8; 2 * LIMB_BYTES + 2];
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, 1);
    assert_eq!(find_last_set_byte_mp(&op0), 1);

    op0.store_l(1, 1);
    assert_eq!(find_last_set_byte_mp(&op0), LIMB_BYTES + 1);

    op0.store_l(2, 1);
    assert_eq!(find_last_set_byte_mp(&op0), 2 * LIMB_BYTES + 1);
}

#[cfg(test)]
fn test_ct_find_last_set_byte_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    let mut op0 = tst_mk_mp_backing_vec!(T0, 0);
    let op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    assert_eq!(find_last_set_byte_mp(&op0), 0);

    let mut op0 = tst_mk_mp_backing_vec!(T0, 2 * LIMB_BYTES);
    let mut op0 = T0::from_slice(op0.as_mut_slice()).unwrap();
    op0.store_l(0, (1 as LimbType) << (LIMB_BITS - 1));
    assert_eq!(find_last_set_byte_mp(&op0), LIMB_BYTES);

    op0.store_l(1, (1 as LimbType) << (LIMB_BITS - 1));
    assert_eq!(find_last_set_byte_mp(&op0), 2 * LIMB_BYTES);
}

#[test]
fn test_ct_find_last_set_byte_be() {
    test_ct_find_last_set_byte_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_ct_find_last_set_byte_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_ct_find_last_set_byte_le() {
    test_ct_find_last_set_byte_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_ct_find_last_set_byte_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_ct_find_last_set_byte_ne() {
    test_ct_find_last_set_byte_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Find a multiprecision integer's least significant set bit in constant time.
///
/// Returns a pair of a [`LimbChoice`] representing whether the
/// multiprecision integer is non-zero, and the position of its least
/// significant set bit, if any, zero otherwise. That is, the latter is the
/// number of trailing zero bits.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and is otherwise constant as far as branching
/// is concerned.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer whose least significant set bit to
///   find.
pub fn ct_find_first_set_bit_mp<T0: MpUIntCommon>(op0: &T0) -> (LimbChoice, usize) {
    let mut tail_is_zero = LimbChoice::from(1);
    let mut ntrailing_zeroes: usize = 0;
    for i in 0..op0.nlimbs() {
        let op0_val = op0.load_l(i);
        ntrailing_zeroes +=
            tail_is_zero.select(0, ct_find_first_set_bit_l(op0_val) as LimbType) as usize;
        tail_is_zero &= LimbChoice::from(ct_is_zero_l(op0_val));
    }
    (
        !tail_is_zero,
        tail_is_zero.select_usize(ntrailing_zeroes, 0),
    )
}

#[cfg(test)]
fn test_ct_find_first_set_bit_mp<T0: MpMutUIntSlice>() {
    let mut limbs = tst_mk_mp_backing_vec!(T0, 3 * LIMB_BYTES);
    let limbs = T0::from_slice(&mut limbs).unwrap();
    let (is_nonzero, first_set_bit_pos) = ct_find_first_set_bit_mp(&limbs);
    assert_eq!(is_nonzero.unwrap(), 0);
    assert_eq!(first_set_bit_pos, 0);

    for i in 0..3 * LIMB_BITS as usize {
        let mut limbs = tst_mk_mp_backing_vec!(T0, 3 * LIMB_BYTES);
        let mut limbs = T0::from_slice(&mut limbs).unwrap();
        let limb_index = i / LIMB_BITS as usize;
        let bit_pos_in_limb = i % LIMB_BITS as usize;

        limbs.store_l(limb_index, 1 << bit_pos_in_limb);
        let (is_nonzero, first_set_bit_pos) = ct_find_first_set_bit_mp(&limbs);
        assert!(is_nonzero.unwrap() != 0);
        assert_eq!(first_set_bit_pos, i);

        limbs.store_l(limb_index, !((1 << bit_pos_in_limb) - 1));
        for j in limb_index + 1..limbs.nlimbs() {
            limbs.store_l(j, !0);
        }
        let (is_nonzero, first_set_bit_pos) = ct_find_first_set_bit_mp(&limbs);
        assert!(is_nonzero.unwrap() != 0);
        assert_eq!(first_set_bit_pos, i);
    }
}

#[test]
fn test_ct_find_first_set_bit_be() {
    test_ct_find_first_set_bit_mp::<MpMutBigEndianUIntByteSlice>()
}

#[test]
fn test_ct_find_first_set_bit_le() {
    test_ct_find_first_set_bit_mp::<MpMutLittleEndianUIntByteSlice>()
}

#[test]
fn test_ct_find_first_set_bit_ne() {
    test_ct_find_first_set_bit_mp::<MpMutNativeEndianUIntLimbsSlice>()
}

/// Find a multiprecision integer's most significant set bit in constant time.
///
/// Returns a pair of a [`LimbChoice`] representing whether the
/// multiprecision integer is non-zero, and the position past its most
/// significant set bit, if any, zero otherwise. That is, the latter is the
/// effective bit width of the value.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and is otherwise constant as far as branching
/// is concerned. See [`ct_find_last_set_byte_mp()`] and its non-constant-time
/// variant [`find_last_set_byte_mp()`] for finding the most significant
/// non-zero byte instead.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer whose most significant set bit to
///   find.
pub fn ct_find_last_set_bit_mp<T0: MpUIntCommon>(op0: &T0) -> (LimbChoice, usize) {
    let mut head_is_zero = LimbChoice::from(1);
    let mut nleading_zeroes: usize = 0;
    let mut i = op0.nlimbs();
    while i > 0 {
        i -= 1;
        let op0_val = op0.load_l(i);
        nleading_zeroes += head_is_zero.select(
            0,
            LIMB_BITS as LimbType - ct_find_last_set_bit_l(op0_val) as LimbType,
        ) as usize;
        head_is_zero &= LimbChoice::from(ct_is_zero_l(op0_val));
    }
    (
        !head_is_zero,
        op0.nlimbs() * LIMB_BITS as usize - nleading_zeroes,
    )
}

#[cfg(test)]
fn test_ct_find_last_set_bit_mp<T0: MpMutUIntSlice>() {
    let mut limbs = tst_mk_mp_backing_vec!(T0, 3 * LIMB_BYTES);
    let limbs = T0::from_slice(&mut limbs).unwrap();
    let (is_nonzero, first_set_bit_pos) = ct_find_last_set_bit_mp(&limbs);
    assert_eq!(is_nonzero.unwrap(), 0);
    assert_eq!(first_set_bit_pos, 0);

    for i in 0..3 * LIMB_BITS as usize {
        let mut limbs = tst_mk_mp_backing_vec!(T0, 3 * LIMB_BYTES);
        let mut limbs = T0::from_slice(&mut limbs).unwrap();
        let limb_index = i / LIMB_BITS as usize;
        let bit_pos_in_limb = i % LIMB_BITS as usize;

        limbs.store_l(limb_index, 1 << bit_pos_in_limb);
        let (is_nonzero, last_set_bit_pos) = ct_find_last_set_bit_mp(&limbs);
        assert!(is_nonzero.unwrap() != 0);
        assert_eq!(last_set_bit_pos, i + 1);

        limbs.store_l(limb_index, (1 << bit_pos_in_limb) - 1);
        for j in 0..limb_index {
            limbs.store_l(j, !0);
        }
        let (is_nonzero, last_set_bit_pos) = ct_find_last_set_bit_mp(&limbs);
        assert_eq!(is_nonzero.unwrap() != 0, i != 0);
        assert_eq!(last_set_bit_pos, i);
    }
}

#[test]
fn test_ct_find_last_set_bit_be() {
    test_ct_find_last_set_bit_mp::<MpMutBigEndianUIntByteSlice>()
}

#[test]
fn test_ct_find_last_set_bit_le() {
    test_ct_find_last_set_bit_mp::<MpMutLittleEndianUIntByteSlice>()
}

#[test]
fn test_ct_find_last_set_bit_ne() {
    test_ct_find_last_set_bit_mp::<MpMutNativeEndianUIntLimbsSlice>()
}

/// Clear a multiprecision integer's high bits in constant time.
///
/// Set all bits at positions `>= begin` to zero, with positions counted from
/// least to most significant. That is, the multiprecision integer gets
/// truncated to its `begin` least significant bits. If `begin` is at or beyond
/// the multiprecision integer's bit length, nothing is cleared.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and is otherwise constant as far as branching
/// is concerned. In particular, it doesn't depend on `begin`, which may
/// therefore be secret. See [`clear_bits_above_mp()`] for the non-constant-time
/// variant, whose execution time depends on the position, and
/// [`MpMutUInt::clear_bytes_above()`] for a variant operating at byte
/// granularity.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer to clear the high bits of.
/// * `begin` - The position of the least significant bit to clear, counted
///   from least to most significant.
pub fn ct_clear_bits_above_mp<T0: MpMutUInt>(op0: &mut T0, begin: usize) {
    let first_limb_index = begin / LIMB_BITS as usize;
    let first_limb_retain_nbits = begin % LIMB_BITS as usize;
    let first_limb_mask = ct_lsb_mask_l(first_limb_retain_nbits as u32);
    let mut next_mask = !0;
    for i in 0..op0.nlimbs() {
        let is_first_limb = ct_eq_usize_usize(i, first_limb_index);
        let mask = is_first_limb.select(next_mask, first_limb_mask);
        next_mask = is_first_limb.select(next_mask, 0);
        let val = op0.load_l(i);
        op0.store_l(i, val & mask)
    }
}

#[cfg(test)]
fn test_ct_clear_bits_above_mp_common<T0: MpMutUIntSlice>(op0_len: usize) {
    fn fill_with_ones<T0: MpMutUInt>(op0: &mut T0) {
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                op0.store_l_full(i, !0);
            } else {
                op0.store_l(i, op0.partial_high_mask());
            }
        }
    }

    let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
    let mut op0 = T0::from_slice(&mut op0).unwrap();
    fill_with_ones(&mut op0);
    for begin in [
        8 * op0_len,
        8 * op0_len + 1,
        8 * op0.nlimbs() * LIMB_BYTES,
        8 * op0.nlimbs() * LIMB_BYTES + 1,
    ] {
        ct_clear_bits_above_mp(&mut op0, begin);
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l_full(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }

    for j in 0..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize;

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        ct_clear_bits_above_mp(&mut op0, begin);
        for i in 0..j {
            assert_eq!(op0.load_l_full(i), !0);
        }

        for i in j..op0.nlimbs() {
            assert_eq!(op0.load_l(i), 0);
        }
    }

    for j in 1..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize - 1;
        let begin = begin.min(8 * op0_len - 1);

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        ct_clear_bits_above_mp(&mut op0, begin);
        for i in 0..j - 1 {
            assert_eq!(op0.load_l_full(i), !0);
        }

        let expected = ct_lsb_mask_l((begin % LIMB_BITS as usize) as u32);
        assert_eq!(op0.load_l(j - 1), expected);

        for i in j..op0.nlimbs() {
            assert_eq!(op0.load_l(i), 0);
        }
    }
}

#[cfg(test)]
fn test_ct_clear_bits_above_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    test_ct_clear_bits_above_mp_common::<T0>(0);
    test_ct_clear_bits_above_mp_common::<T0>(LIMB_BYTES);
    test_ct_clear_bits_above_mp_common::<T0>(2 * LIMB_BYTES);
    test_ct_clear_bits_above_mp_common::<T0>(3 * LIMB_BYTES);
}

#[cfg(test)]
fn test_ct_clear_bits_above_mp_with_unaligned_lengths<T0: MpMutUIntSlice>() {
    test_ct_clear_bits_above_mp_common::<T0>(LIMB_BYTES - 1);
    test_ct_clear_bits_above_mp_common::<T0>(2 * LIMB_BYTES - 1);
    test_ct_clear_bits_above_mp_common::<T0>(3 * LIMB_BYTES - 1);
}

#[test]
fn test_ct_clear_bits_above_be() {
    test_ct_clear_bits_above_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_ct_clear_bits_above_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_ct_clear_bits_above_le() {
    test_ct_clear_bits_above_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_ct_clear_bits_above_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_ct_clear_bits_above_ne() {
    test_ct_clear_bits_above_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Clear a multiprecision integer's high bits.
///
/// Set all bits at positions `>= begin` to zero, with positions counted from
/// least to most significant. That is, the multiprecision integer gets
/// truncated to its `begin` least significant bits. If `begin` is at or beyond
/// the multiprecision integer's bit length, nothing is cleared.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and the `begin` argument and is otherwise
/// constant as far as branching is concerned. See [`ct_clear_bits_above_mp()`]
/// for the constant-time variant, whose execution time doesn't depend on
/// `begin`, and [`MpMutUInt::clear_bytes_above()`] for a variant operating at
/// byte granularity.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer to clear the high bits of.
/// * `begin` - The position of the least significant bit to clear, counted
///   from least to most significant.
pub fn clear_bits_above_mp<T0: MpMutUInt>(op0: &mut T0, begin: usize) {
    let first_limb_index = begin / LIMB_BITS as usize;
    if op0.nlimbs() <= first_limb_index {
        return;
    }
    let first_limb_retain_nbits = begin % LIMB_BITS as usize;
    let first_limb_mask = ct_lsb_mask_l(first_limb_retain_nbits as u32);
    op0.store_l(
        first_limb_index,
        op0.load_l(first_limb_index) & first_limb_mask,
    );

    op0.clear_bytes_above(begin.div_ceil(LIMB_BITS as usize) * LIMB_BYTES);
}

#[cfg(test)]
fn test_clear_bits_above_mp_common<T0: MpMutUIntSlice>(op0_len: usize) {
    fn fill_with_ones<T0: MpMutUInt>(op0: &mut T0) {
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                op0.store_l_full(i, !0);
            } else {
                op0.store_l(i, op0.partial_high_mask());
            }
        }
    }

    let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
    let mut op0 = T0::from_slice(&mut op0).unwrap();
    fill_with_ones(&mut op0);
    for begin in [
        8 * op0_len,
        8 * op0_len + 1,
        8 * op0.nlimbs() * LIMB_BYTES,
        8 * op0.nlimbs() * LIMB_BYTES + 1,
    ] {
        clear_bits_above_mp(&mut op0, begin);
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l_full(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }

    for j in 0..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize;

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        clear_bits_above_mp(&mut op0, begin);
        for i in 0..j {
            assert_eq!(op0.load_l_full(i), !0);
        }

        for i in j..op0.nlimbs() {
            assert_eq!(op0.load_l(i), 0);
        }
    }

    for j in 1..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize - 1;
        let begin = begin.min(8 * op0_len - 1);

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        clear_bits_above_mp(&mut op0, begin);
        for i in 0..j - 1 {
            assert_eq!(op0.load_l_full(i), !0);
        }

        let expected = ct_lsb_mask_l((begin % LIMB_BITS as usize) as u32);
        assert_eq!(op0.load_l(j - 1), expected);

        for i in j..op0.nlimbs() {
            assert_eq!(op0.load_l(i), 0);
        }
    }
}

#[cfg(test)]
fn test_clear_bits_above_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    test_clear_bits_above_mp_common::<T0>(0);
    test_clear_bits_above_mp_common::<T0>(LIMB_BYTES);
    test_clear_bits_above_mp_common::<T0>(2 * LIMB_BYTES);
    test_clear_bits_above_mp_common::<T0>(3 * LIMB_BYTES);
}

#[cfg(test)]
fn test_clear_bits_above_mp_with_unaligned_lengths<T0: MpMutUIntSlice>() {
    test_clear_bits_above_mp_common::<T0>(LIMB_BYTES - 1);
    test_clear_bits_above_mp_common::<T0>(2 * LIMB_BYTES - 1);
    test_clear_bits_above_mp_common::<T0>(3 * LIMB_BYTES - 1);
}

#[test]
fn test_clear_bits_above_be() {
    test_clear_bits_above_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_clear_bits_above_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_clear_bits_above_le() {
    test_clear_bits_above_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_clear_bits_above_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_clear_bits_above_ne() {
    test_clear_bits_above_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Clear a multiprecision integer's low bits in constant time.
///
/// Set all bits at positions `< end` to zero, with positions counted from
/// least to most significant. If `end` is at or beyond the multiprecision
/// integer's bit length, all of it is cleared.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and is otherwise constant as far as branching
/// is concerned. In particular, it doesn't depend on `end`, which may therefore
/// be secret. See [`clear_bits_below_mp()`] for the non-constant-time variant,
/// whose execution time depends on the position, and
/// [`MpMutUInt::clear_bytes_below()`] for a variant operating at byte
/// granularity.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer to clear the low bits of.
/// * `end` - The position past the most significant bit to clear, counted
///   from least to most significant.
pub fn ct_clear_bits_below_mp<T0: MpMutUInt>(op0: &mut T0, end: usize) {
    let last_limb_index = end / LIMB_BITS as usize;
    let last_limb_clear_nbits = end % LIMB_BITS as usize;
    let last_limb_mask = !ct_lsb_mask_l(last_limb_clear_nbits as u32);
    let mut next_mask = 0;
    for i in 0..op0.nlimbs() {
        let is_last_limb = ct_eq_usize_usize(i, last_limb_index);
        let mask = is_last_limb.select(next_mask, last_limb_mask);
        next_mask = is_last_limb.select(next_mask, !0);
        let val = op0.load_l(i);
        op0.store_l(i, val & mask)
    }
}

#[cfg(test)]
fn test_ct_clear_bits_mp_below_common<T0: MpMutUIntSlice>(op0_len: usize) {
    fn fill_with_ones<T0: MpMutUInt>(op0: &mut T0) {
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                op0.store_l_full(i, !0);
            } else {
                op0.store_l(i, op0.partial_high_mask());
            }
        }
    }

    let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
    let mut op0 = T0::from_slice(&mut op0).unwrap();
    fill_with_ones(&mut op0);
    ct_clear_bits_below_mp(&mut op0, 0);
    for i in 0..op0.nlimbs() {
        if i + 1 != op0.nlimbs() {
            assert_eq!(op0.load_l_full(i), !0);
        } else {
            assert_eq!(op0.load_l(i), op0.partial_high_mask());
        }
    }

    for j in 0..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize;

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        ct_clear_bits_below_mp(&mut op0, begin);
        for i in 0..j {
            assert_eq!(op0.load_l_full(i), 0);
        }

        for i in j..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }

    for j in 1..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize - 1;
        let begin = begin.min(8 * op0_len - 1);

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        ct_clear_bits_below_mp(&mut op0, begin);
        for i in 0..j - 1 {
            assert_eq!(op0.load_l_full(i), 0);
        }

        let expected = !ct_lsb_mask_l((begin % LIMB_BITS as usize) as u32);
        assert_eq!(op0.load_l(j - 1), expected);

        for i in j..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }
}

#[cfg(test)]
fn test_ct_clear_bits_below_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    test_ct_clear_bits_mp_below_common::<T0>(0);
    test_ct_clear_bits_mp_below_common::<T0>(LIMB_BYTES);
    test_ct_clear_bits_mp_below_common::<T0>(2 * LIMB_BYTES);
    test_ct_clear_bits_mp_below_common::<T0>(3 * LIMB_BYTES);
}

#[cfg(test)]
fn test_ct_clear_bits_below_mp_with_unaligned_lengths<T0: MpMutUIntSlice>() {
    test_ct_clear_bits_mp_below_common::<T0>(LIMB_BYTES - 1);
    test_ct_clear_bits_mp_below_common::<T0>(2 * LIMB_BYTES - 1);
    test_ct_clear_bits_mp_below_common::<T0>(3 * LIMB_BYTES - 1);
}

#[test]
fn test_ct_clear_bits_below_be() {
    test_ct_clear_bits_below_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_ct_clear_bits_below_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_ct_clear_bits_below_le() {
    test_ct_clear_bits_below_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_ct_clear_bits_below_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_ct_clear_bits_below_ne() {
    test_ct_clear_bits_below_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Clear a multiprecision integer's low bits.
///
/// Set all bits at positions `< end` to zero, with positions counted from
/// least to most significant. If `end` is at or beyond the multiprecision
/// integer's bit length, all of it is cleared.
///
/// Execution time depends only on the multiprecision integer's [length in units
/// of bytes](MpUIntCommon::len) and the `end` argument and is otherwise
/// constant as far as branching is concerned. See [`ct_clear_bits_below_mp()`]
/// for the constant-time variant, whose execution time doesn't depend on `end`,
/// and [`MpMutUInt::clear_bytes_below()`] for a variant operating at byte
/// granularity.
///
/// # Arguments
///
/// * `op0` - The multiprecision integer to clear the low bits of.
/// * `end` - The position past the most significant bit to clear, counted
///   from least to most significant.
pub fn clear_bits_below_mp<T0: MpMutUInt>(op0: &mut T0, end: usize) {
    let last_limb_index = end / LIMB_BITS as usize;
    op0.clear_bytes_below(last_limb_index * LIMB_BYTES);
    if last_limb_index >= op0.nlimbs() {
        return;
    }
    let last_limb_clear_nbits = end % LIMB_BITS as usize;
    let last_limb_mask = !ct_lsb_mask_l(last_limb_clear_nbits as u32);
    op0.store_l(
        last_limb_index,
        op0.load_l(last_limb_index) & last_limb_mask,
    );
}

#[cfg(test)]
fn test_clear_bits_below_mp_common<T0: MpMutUIntSlice>(op0_len: usize) {
    fn fill_with_ones<T0: MpMutUInt>(op0: &mut T0) {
        for i in 0..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                op0.store_l_full(i, !0);
            } else {
                op0.store_l(i, op0.partial_high_mask());
            }
        }
    }

    let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
    let mut op0 = T0::from_slice(&mut op0).unwrap();
    fill_with_ones(&mut op0);
    clear_bits_below_mp(&mut op0, 0);
    for i in 0..op0.nlimbs() {
        if i + 1 != op0.nlimbs() {
            assert_eq!(op0.load_l_full(i), !0);
        } else {
            assert_eq!(op0.load_l(i), op0.partial_high_mask());
        }
    }

    for j in 0..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize;

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        clear_bits_below_mp(&mut op0, begin);
        for i in 0..j {
            assert_eq!(op0.load_l_full(i), 0);
        }

        for i in j..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }

    for j in 1..ct_mp_nlimbs(op0_len) {
        let begin = j * LIMB_BITS as usize - 1;
        let begin = begin.min(8 * op0_len - 1);

        let mut op0 = tst_mk_mp_backing_vec!(T0, op0_len);
        let mut op0 = T0::from_slice(&mut op0).unwrap();
        fill_with_ones(&mut op0);
        clear_bits_below_mp(&mut op0, begin);
        for i in 0..j - 1 {
            assert_eq!(op0.load_l_full(i), 0);
        }

        let expected = !ct_lsb_mask_l((begin % LIMB_BITS as usize) as u32);
        assert_eq!(op0.load_l(j - 1), expected);

        for i in j..op0.nlimbs() {
            if i + 1 != op0.nlimbs() {
                assert_eq!(op0.load_l(i), !0);
            } else {
                assert_eq!(op0.load_l(i), op0.partial_high_mask());
            }
        }
    }
}

#[cfg(test)]
fn test_clear_bits_below_mp_with_aligned_lengths<T0: MpMutUIntSlice>() {
    test_clear_bits_below_mp_common::<T0>(0);
    test_clear_bits_below_mp_common::<T0>(LIMB_BYTES);
    test_clear_bits_below_mp_common::<T0>(2 * LIMB_BYTES);
    test_clear_bits_below_mp_common::<T0>(3 * LIMB_BYTES);
}

#[cfg(test)]
fn test_clear_bits_below_mp_with_unaligned_lengths<T0: MpMutUIntSlice>() {
    test_clear_bits_below_mp_common::<T0>(LIMB_BYTES - 1);
    test_clear_bits_below_mp_common::<T0>(2 * LIMB_BYTES - 1);
    test_clear_bits_below_mp_common::<T0>(3 * LIMB_BYTES - 1);
}

#[test]
fn test_clear_bits_below_be() {
    test_clear_bits_below_mp_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_clear_bits_below_mp_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_clear_bits_below_le() {
    test_clear_bits_below_mp_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_clear_bits_below_mp_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_clear_bits_below_ne() {
    test_clear_bits_below_mp_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// Conditionally swap two multiprecision integers' values in constant time.
///
/// If `cond` is true, exchange the values of `op0` and `op1`. Otherwise leave
/// both unmodified. The two multiprecision integers may be of different
/// representations.
///
/// Execution time depends only on the multiprecision integers' [lengths in
/// units of bytes](MpUIntCommon::len) and is otherwise constant as far as
/// branching is concerned. In particular, it doesn't depend on `cond`.
///
/// # Arguments
///
/// * `op0` - The first multiprecision integer.
/// * `op1` - The second multiprecision integer. Its [length in units of
///   bytes](MpUIntCommon::len) must [fit
///   into](MpUIntCommon::len_is_compatible_with) `op0`'s and vice versa.
/// * `cond` - Whether or not to swap the values.
pub fn ct_swap_cond_mp<T0: MpMutUInt, T1: MpMutUInt>(op0: &mut T0, op1: &mut T1, cond: LimbChoice) {
    debug_assert!(op0.len_is_compatible_with(op1.len()));
    debug_assert!(op1.len_is_compatible_with(op0.len()));
    let nlimbs = op0.nlimbs();
    debug_assert_eq!(nlimbs, op1.nlimbs());
    let cond_mask = cond.select(0, !0);
    for i in 0..nlimbs {
        let mut op0_val = op0.load_l(i);
        let mut op1_val = op1.load_l(i);
        op0_val ^= op1_val;
        op1_val ^= op0_val & cond_mask;
        op0_val ^= op1_val;
        op0.store_l(i, op0_val);
        op1.store_l(i, op1_val);
    }
}

#[cfg(test)]
fn test_ct_swap_cond_mp<T0: MpMutUIntSlice, T1: MpMutUIntSlice>() {
    use super::cmp::ct_eq_mp_mp;

    let len = 2 * LIMB_BYTES - 1;
    let mut op0_orig = tst_mk_mp_backing_vec!(T0, len);
    op0_orig.fill(0xccu8.into());
    let mut op0 = op0_orig.clone();
    let op0_orig = T0::from_slice(&mut op0_orig).unwrap();
    let mut op0 = T0::from_slice(&mut op0).unwrap();

    let mut op1_orig = tst_mk_mp_backing_vec!(T1, len);
    op1_orig.fill(0xbbu8.into());
    let mut op1 = op1_orig.clone();
    let op1_orig = T1::from_slice(&mut op1_orig).unwrap();
    let mut op1 = T1::from_slice(&mut op1).unwrap();

    ct_swap_cond_mp(&mut op0, &mut op1, LimbChoice::from(0));
    assert_ne!(ct_eq_mp_mp(&op0, &op0_orig).unwrap(), 0);
    assert_ne!(ct_eq_mp_mp(&op1, &op1_orig).unwrap(), 0);

    ct_swap_cond_mp(&mut op0, &mut op1, LimbChoice::from(1));
    assert_ne!(ct_eq_mp_mp(&op0, &op1_orig).unwrap(), 0);
    assert_ne!(ct_eq_mp_mp(&op1, &op0_orig).unwrap(), 0);
}

#[test]
fn test_ct_swap_cond_be_be() {
    test_ct_swap_cond_mp::<MpMutBigEndianUIntByteSlice, MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_ct_swap_cond_le_le() {
    test_ct_swap_cond_mp::<MpMutLittleEndianUIntByteSlice, MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_ct_swap_cond_ne_ne() {
    test_ct_swap_cond_mp::<MpMutNativeEndianUIntLimbsSlice, MpMutNativeEndianUIntLimbsSlice>();
}

/// Internal data structure describing a single one of a
/// [`CompositeLimbsBuffer`]'s constituting segments.
struct CompositeLimbsBufferSegment<'a, ST: MpUIntCommon> {
    /// The total number of limbs whose least significant bytes are held in this
    /// or less significant segments each (note that a limb may span
    /// multiple segments).
    end: usize,
    /// The actual data, interpreted as a segment within the composed
    /// multiprecision integer.
    ///
    /// The `segment` slice, if non-empty, will be made to align with the least
    /// significant limb whose least significant byte is found in this
    /// segment. That is, for e.g. [`MpBigEndianUIntByteSlice`] the slice's last
    /// byte (in memory order) corresponds to the least significant byte of the
    /// least significant limb.
    segment: ST,
    /// Continuation bytes of this or preceding, less significant segment's
    /// most significant limb.
    ///
    /// A segment's most significant limb might be covered only partially by it
    /// and extend across one or more subsequent, more significant segments.
    /// In this case its remaining, more significant continuation bytes are
    /// collected from this and the subsequent, more significant
    /// segments' `high_next_partial` slices.
    high_next_partial: ST,

    _phantom: marker::PhantomData<&'a [u8]>,
}

/// Access multiprecision integers composed of multiple virtually concatenated
/// buffer slices in units of [`LimbType`].
///
/// A [`CompositeLimbsBuffer`] provides a composed multiprecision integer view
/// on `N_SEGMENTS` virtually concatenated buffer slices, each wrapped in the
/// same representation-specific multiprecision integer slice type `ST`, like
/// e.g. [`MpBigEndianUIntByteSlice`]. Primitives are provided alongside for
/// accessing the composed integer in units of [`LimbType`].
///
/// Certain applications need to truncate the result of some multiprecision
/// integer arithmetic operation result and dismiss the rest. An example would
/// be key generation modulo some large integer by the method of oversampling. A
/// `CompositeLimbsBuffer` helps such applications to reduce the memory
/// footprint of the truncation operation: instead of allocating a smaller
/// destination buffer and copying the to be retained parts over from the
/// result, the arithmetic primitive can, if supported, operate directly on a
/// multiprecision integer composed of several independent smaller slices by
/// virtual concatenation. Assuming the individual segments' slice
/// lengths align properly with the needed and unneeded parts of the result, the
/// latter ones can get truncated away trivially when done by simply dismissing
/// the corresponding underlying buffers.
///
/// Read access is provided for any multiprecision integer slice type `ST`,
/// write access in addition if `ST` implements [`MpMutUIntSlice`].
pub(super) struct CompositeLimbsBuffer<'a, ST: MpUIntCommon, const N_SEGMENTS: usize> {
    /// The composed view's individual segments, ordered from least to most
    /// significant.
    segments: [CompositeLimbsBufferSegment<'a, ST>; N_SEGMENTS],
}

impl<'a, ST: MpUIntSliceCommon, const N_SEGMENTS: usize> CompositeLimbsBuffer<'a, ST, N_SEGMENTS> {
    /// Construct a `CompositeLimbsBuffer` view from the individual buffer
    /// segments.
    ///
    /// # Arguments
    ///
    /// * `segments` - An array of `N_SEGMENTS` multiprecision integer slices to
    ///   compose the multiprecision integer view from by virtual concatenation.
    ///   Ordered from least to most significant with respect to their position
    ///   within the resulting view.
    pub fn new(segments: [ST; N_SEGMENTS]) -> Self {
        let mut segments = <[ST; N_SEGMENTS] as IntoIterator>::into_iter(segments);
        let mut segments: [Option<ST>; N_SEGMENTS] = core::array::from_fn(|_| segments.next());
        let mut n_bytes_total = 0;
        let mut create_segment = |i: usize| {
            let segment = segments[i].take().unwrap();
            let segment_len = segment.len();
            n_bytes_total += segment_len;

            let n_high_partial = n_bytes_total % LIMB_BYTES;
            let (high_next_partial, segment) = if i + 1 != segments.len() && n_high_partial != 0 {
                let next_segment = segments[i + 1].take().unwrap();
                let next_segment_len = next_segment.len();
                let n_from_next = (LIMB_BYTES - n_high_partial).min(next_segment_len);
                let (next_segment, high_next_partial) = next_segment.take(n_from_next);
                segments[i + 1] = Some(next_segment);
                (high_next_partial, segment)
            } else {
                let (high_next_partial, segment) = segment.take(segment_len);
                (high_next_partial, segment)
            };

            let high_next_partial_len = high_next_partial.len();
            n_bytes_total += high_next_partial_len;
            let end = ct_mp_nlimbs(n_bytes_total);
            CompositeLimbsBufferSegment {
                end,
                segment,
                high_next_partial,
                _phantom: marker::PhantomData,
            }
        };

        let segments: [CompositeLimbsBufferSegment<'a, ST>; N_SEGMENTS] =
            core::array::from_fn(&mut create_segment);
        Self { segments }
    }

    /// Lookup the least significant buffer segment holding the specified limb's
    /// least significant byte.
    ///
    /// Returns a pair of segment index and, as a by-product of the search, the
    /// corresponding segment's offset within the composed multiprecision
    /// integer in units of limbs.
    ///
    /// Execution time depends on the composed multiprecision integer's
    /// underlying segment layout as well as on the limb index
    /// argument `i` as far as branching is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to look up, counted from least to most
    ///   significant. Must be less than the composed multiprecision
    ///   integer's total number of limbs.
    fn limb_index_to_segment(&self, i: usize) -> (usize, usize) {
        let mut segment_offset = 0;
        for (segment_index, segment) in self.segments.iter().enumerate() {
            let segment_end = segment.end;
            if i < segment_end {
                return (segment_index, segment_offset);
            } else {
                segment_offset = segment_end;
            }
        }
        unreachable!();
    }

    /// Load a limb from the composed multiprecision integer.
    ///
    /// Execution time depends on the composed multiprecision integer's
    /// underlying segment layout as well as on the limb index
    /// argument `i`, and is otherwise constant as far as branching
    /// is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to load, counted from least to most
    ///   significant. Must be less than the composed multiprecision
    ///   integer's total number of limbs.
    pub fn load(&self, i: usize) -> LimbType {
        let (segment_index, segment_offset) = self.limb_index_to_segment(i);
        let segment = &self.segments[segment_index];
        let segment_slice = &segment.segment;
        if i != segment.end - 1 || !ST::SUPPORTS_UNALIGNED_BUFFER_LENGTHS {
            segment_slice.load_l_full(i - segment_offset)
        } else if segment_index + 1 == N_SEGMENTS || segment_slice.len().is_multiple_of(LIMB_BYTES)
        {
            // The last (highest) segment's most significant bytes don't necessarily occupy
            // a full limb.
            segment_slice.load_l(i - segment_offset)
        } else {
            let mut npartial = segment_slice.len() % LIMB_BYTES;
            let mut value = segment_slice.load_l(i - segment_offset);
            let mut segment_index = segment_index;
            while npartial != LIMB_BYTES && segment_index < self.segments.len() {
                let partial = &self.segments[segment_index].high_next_partial;
                if !partial.is_empty() {
                    value |= partial.load_l(0) << (8 * npartial);
                    npartial += partial.len();
                }
                segment_index += 1;
            }
            value
        }
    }
}

impl<'a, ST: MpMutUIntSlice, const N_SEGMENTS: usize> CompositeLimbsBuffer<'a, ST, N_SEGMENTS> {
    /// Update a limb in the composed multiprecision integer.
    ///
    /// Execution time depends on the composed multiprecision integer's
    /// underlying segment layout as well as on the limb index
    /// argument `i`, and is otherwise constant as far as branching
    /// is concerned.
    ///
    /// # Arguments
    ///
    /// * `i` - The index of the limb to update, counted from least to most
    ///   significant. Must be less than the composed multiprecision
    ///   integer's total number of limbs.
    /// * `value` - The value to store in the i'th limb. If the most
    ///   significant limb is to be stored, all bytes in `value` corresponding
    ///   to its excess bytes not covered by the composed multiprecision
    ///   integer must be zero.
    pub fn store(&mut self, i: usize, value: LimbType) {
        let (segment_index, segment_offset) = self.limb_index_to_segment(i);
        let segment = &mut self.segments[segment_index];
        let segment_slice = &mut segment.segment;
        if i != segment.end - 1 || !ST::SUPPORTS_UNALIGNED_BUFFER_LENGTHS {
            segment_slice.store_l_full(i - segment_offset, value);
        } else if segment_index + 1 == N_SEGMENTS || segment_slice.len().is_multiple_of(LIMB_BYTES)
        {
            // The last (highest) part's most significant bytes don't necessarily occupy a
            // full limb.
            segment_slice.store_l(i - segment_offset, value)
        } else {
            let mut value = value;
            let mut npartial = segment_slice.len() % LIMB_BYTES;
            let value_mask = ct_lsb_mask_l(8 * npartial as u32);
            segment_slice.store_l(i - segment_offset, value & value_mask);
            value >>= 8 * npartial;
            let mut segment_index = segment_index;
            while npartial != LIMB_BYTES && segment_index < self.segments.len() {
                let partial = &mut self.segments[segment_index].high_next_partial;
                if !partial.is_empty() {
                    let value_mask = ct_lsb_mask_l(8 * partial.len() as u32);
                    partial.store_l(0, value & value_mask);
                    value >>= 8 * partial.len();
                    npartial += partial.len();
                }
                segment_index += 1;
            }
            debug_assert!(value == 0);
        }
    }
}

#[test]
fn test_composite_limbs_buffer_load_be() {
    let mut buf0: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    let buf1: [u8; 0] = [0; 0];
    let mut buf2: [u8; 2 * LIMB_BYTES + 2] = [0; 2 * LIMB_BYTES + 2];

    // 0x02 00 .. 00 01 00 .. 00
    buf0[LIMB_BYTES - 1 + LIMB_BYTES / 2] = 0x1;
    buf0[LIMB_BYTES - 1] = 0x2;

    // 0x05 04 00 .. 00 03 .. 00
    buf0[LIMB_BYTES / 2 - 1] = 0x3;
    buf0[0] = 0x4;
    buf2[1 + 2 * LIMB_BYTES] = 0x5;

    // 0x07 00 .. 00 06 00 .. 00
    buf2[1 + LIMB_BYTES + LIMB_BYTES / 2] = 0x6;
    buf2[1 + LIMB_BYTES] = 0x7;

    // 0x09 00 .. 00 08 00 .. 00
    buf2[1 + LIMB_BYTES / 2] = 0x8;
    buf2[1] = 0x9;

    // 0x00 .. 00 0x0a
    buf2[0] = 0xa;

    let buf0 = MpBigEndianUIntByteSlice::from_bytes(buf0.as_slice());
    let buf1 = MpBigEndianUIntByteSlice::from_bytes(buf1.as_slice());
    let buf2 = MpBigEndianUIntByteSlice::from_bytes(buf2.as_slice());
    let limbs = CompositeLimbsBuffer::new([buf0, buf1, buf2]);

    let l0 = limbs.load(0);
    assert_eq!(l0, 0x2 << (LIMB_BITS - 8) | 0x1 << (LIMB_BITS / 2 - 8));
    let l1 = limbs.load(1);
    assert_eq!(l1, 0x0504 << (LIMB_BITS - 16) | 0x3 << (LIMB_BITS / 2 - 8));
    let l2 = limbs.load(2);
    assert_eq!(l2, 0x7 << (LIMB_BITS - 8) | 0x6 << (LIMB_BITS / 2 - 8));
    let l3 = limbs.load(3);
    assert_eq!(l3, 0x9 << (LIMB_BITS - 8) | 0x8 << (LIMB_BITS / 2 - 8));
    let l4 = limbs.load(4);
    assert_eq!(l4, 0xa);
}

#[test]
fn test_composite_limbs_buffer_load_le() {
    let mut buf0: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    let buf1: [u8; 0] = [0; 0];
    let mut buf2: [u8; 2 * LIMB_BYTES + 2] = [0; 2 * LIMB_BYTES + 2];

    // 0x00 .. 00 01 00 .. 00 02
    buf0[LIMB_BYTES / 2 - 1] = 0x1;
    buf0[LIMB_BYTES - 1] = 0x2;

    // 0x00 .. 03 00 .. 00 04 05
    buf0[LIMB_BYTES + LIMB_BYTES / 2 - 1] = 0x3;
    buf0[2 * LIMB_BYTES - 2] = 0x4;
    buf2[0] = 0x5;

    // 0x00 .. 00 06 00 .. 00 07
    buf2[1 + LIMB_BYTES / 2 - 1] = 0x6;
    buf2[1 + LIMB_BYTES - 1] = 0x7;

    // 0x00 .. 00 08 00 .. 00 09
    buf2[1 + LIMB_BYTES + LIMB_BYTES / 2 - 1] = 0x8;
    buf2[1 + 2 * LIMB_BYTES - 1] = 0x9;

    // 0x00 .. 00 0x0a
    buf2[1 + 2 * LIMB_BYTES] = 0xa;

    let buf0 = MpLittleEndianUIntByteSlice::from_bytes(buf0.as_slice());
    let buf1 = MpLittleEndianUIntByteSlice::from_bytes(buf1.as_slice());
    let buf2 = MpLittleEndianUIntByteSlice::from_bytes(buf2.as_slice());
    let limbs = CompositeLimbsBuffer::new([buf0, buf1, buf2]);

    let l0 = limbs.load(0);
    assert_eq!(l0, 0x2 << (LIMB_BITS - 8) | 0x1 << (LIMB_BITS / 2 - 8));
    let l1 = limbs.load(1);
    assert_eq!(l1, 0x0504 << (LIMB_BITS - 16) | 0x3 << (LIMB_BITS / 2 - 8));
    let l2 = limbs.load(2);
    assert_eq!(l2, 0x7 << (LIMB_BITS - 8) | 0x6 << (LIMB_BITS / 2 - 8));
    let l3 = limbs.load(3);
    assert_eq!(l3, 0x9 << (LIMB_BITS - 8) | 0x8 << (LIMB_BITS / 2 - 8));
    let l4 = limbs.load(4);
    assert_eq!(l4, 0xa);
}

#[test]
fn test_composite_limbs_buffer_load_ne() {
    let mut buf0 = [0 as LimbType; 2];
    let buf1 = [0 as LimbType; 0];
    let mut buf2 = [0 as LimbType; 2 * LIMB_BYTES];

    buf0[0] = 0x1;
    buf0[1] = 0x2;
    buf2[0] = 0x3;
    buf2[1] = 0x4;

    let buf0 = MpNativeEndianUIntLimbsSlice::from_limbs(buf0.as_slice());
    let buf1 = MpNativeEndianUIntLimbsSlice::from_limbs(buf1.as_slice());
    let buf2 = MpNativeEndianUIntLimbsSlice::from_limbs(buf2.as_slice());
    let limbs = CompositeLimbsBuffer::new([buf0, buf1, buf2]);

    let l0 = limbs.load(0);
    assert_eq!(l0, 0x1);
    let l1 = limbs.load(1);
    assert_eq!(l1, 0x2);
    let l2 = limbs.load(2);
    assert_eq!(l2, 0x3);
    let l3 = limbs.load(3);
    assert_eq!(l3, 0x4);
}

#[cfg(test)]
fn test_composite_limbs_buffer_store_with_unaligned_lengths<
    ST: MpMutUIntSlice<BackingSliceElementType = u8>,
>() {
    debug_assert!(ST::SUPPORTS_UNALIGNED_BUFFER_LENGTHS);

    let mut buf0: [u8; 2 * LIMB_BYTES - 1] = [0; 2 * LIMB_BYTES - 1];
    let mut buf1: [u8; 0] = [0; 0];
    let mut buf2: [u8; 2 * LIMB_BYTES + 2] = [0; 2 * LIMB_BYTES + 2];
    let buf0 = ST::from_slice(&mut buf0).unwrap();
    let buf1 = ST::from_slice(&mut buf1).unwrap();
    let buf2 = ST::from_slice(&mut buf2).unwrap();
    let mut limbs = CompositeLimbsBuffer::new([buf0, buf1, buf2]);

    let l0 = 0x2 << (LIMB_BITS - 8) | 0x1 << (LIMB_BITS / 2 - 8);
    let l1 = 0x0504 << (LIMB_BITS - 16) | 0x3 << (LIMB_BITS / 2 - 8);
    let l2 = 0x7 << (LIMB_BITS - 8) | 0x6 << (LIMB_BITS / 2 - 8);
    let l3 = 0x9 << (LIMB_BITS - 8) | 0x8 << (LIMB_BITS / 2 - 8);
    let l4 = 0xa;

    limbs.store(0, l0);
    limbs.store(1, l1);
    limbs.store(2, l2);
    limbs.store(3, l3);
    limbs.store(4, l4);
    assert_eq!(l0, limbs.load(0));
    assert_eq!(l1, limbs.load(1));
    assert_eq!(l2, limbs.load(2));
    assert_eq!(l3, limbs.load(3));
    assert_eq!(l4, limbs.load(4));
}

#[cfg(test)]
fn test_composite_limbs_buffer_store_with_aligned_lengths<ST: MpMutUIntSlice>() {
    let mut buf0 = tst_mk_mp_backing_vec!(ST, 2 * LIMB_BYTES);
    let mut buf1 = tst_mk_mp_backing_vec!(ST, 0);
    let mut buf2 = tst_mk_mp_backing_vec!(ST, 2 * LIMB_BYTES);
    let buf0 = ST::from_slice(&mut buf0).unwrap();
    let buf1 = ST::from_slice(&mut buf1).unwrap();
    let buf2 = ST::from_slice(&mut buf2).unwrap();
    let mut limbs = CompositeLimbsBuffer::new([buf0, buf1, buf2]);

    let l0 = 0x2 << (LIMB_BITS - 8) | 0x1 << (LIMB_BITS / 2 - 8);
    let l1 = 0x0504 << (LIMB_BITS - 16) | 0x3 << (LIMB_BITS / 2 - 8);
    let l2 = 0x7 << (LIMB_BITS - 8) | 0x6 << (LIMB_BITS / 2 - 8);
    let l3 = 0x9 << (LIMB_BITS - 8) | 0x8 << (LIMB_BITS / 2 - 8);

    limbs.store(0, l0);
    limbs.store(1, l1);
    limbs.store(2, l2);
    limbs.store(3, l3);
    assert_eq!(l0, limbs.load(0));
    assert_eq!(l1, limbs.load(1));
    assert_eq!(l2, limbs.load(2));
    assert_eq!(l3, limbs.load(3));
}

#[test]
fn test_composite_limbs_buffer_store_be() {
    test_composite_limbs_buffer_store_with_unaligned_lengths::<MpMutBigEndianUIntByteSlice>();
    test_composite_limbs_buffer_store_with_aligned_lengths::<MpMutBigEndianUIntByteSlice>();
}

#[test]
fn test_composite_limbs_buffer_store_le() {
    test_composite_limbs_buffer_store_with_unaligned_lengths::<MpMutLittleEndianUIntByteSlice>();
    test_composite_limbs_buffer_store_with_aligned_lengths::<MpMutLittleEndianUIntByteSlice>();
}

#[test]
fn test_composite_limbs_buffer_store_ne() {
    test_composite_limbs_buffer_store_with_aligned_lengths::<MpMutNativeEndianUIntLimbsSlice>();
}

/// View a mutable [`LimbType`] slice as a mutable byte slice.
///
/// Returns a mutable byte slice covering the same memory as `limbs`, of length
/// `limbs.len()` times the [`LimbType`] size in bytes. The bytes are in memory
/// order, i.e. each limb's bytes appear in the host's native endianess.
///
/// This is useful for filling a [`LimbType`] slice, e.g. one to be wrapped in
/// a [`MpMutNativeEndianUIntLimbsSlice`], from a source producing bytes, most
/// notably a random number generator. As all bytes produced by a random number
/// generator are equally random, the host's endianess doesn't matter in this
/// case. As any bit pattern is a valid [`LimbType`] value, any byte values may
/// be written.
///
/// # Arguments
///
/// * `limbs` - The [`LimbType`] slice to view as bytes.
pub fn limb_slice_as_bytes_mut(limbs: &mut [LimbType]) -> &mut [u8] {
    let len = mem::size_of_val(limbs);
    let ptr = limbs.as_mut_ptr() as *mut u8;
    unsafe { slice::from_raw_parts_mut(ptr, len) }
}

/// View a [`LimbType`] slice as a byte slice.
///
/// Returns a byte slice covering the same memory as `limbs`, of length
/// `limbs.len()` times the [`LimbType`] size in bytes. The bytes are in memory
/// order, i.e. each limb's bytes appear in the host's native endianess.
///
/// See [`limb_slice_as_bytes_mut()`] for the mutable variant, e.g. for filling
/// a [`LimbType`] slice from a random number generator.
///
/// # Arguments
///
/// * `limbs` - The [`LimbType`] slice to view as bytes.
pub fn limb_slice_as_bytes(limbs: &[LimbType]) -> &[u8] {
    let len = mem::size_of_val(limbs);
    let ptr = limbs.as_ptr() as *const u8;
    unsafe { slice::from_raw_parts(ptr, len) }
}