cmpa 0.1.6

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

//! Constant-time comparisons of [`usize`] values.
//!
//! Lengths, indices and bit positions are usually not sensitive. However,
//! some, like shift distances or the positions of a multiprecision integer's
//! least or most significant set bit, can be derived from secret values. The
//! primitives here compare such [`usize`] values without branching on them
//! and return the result as a [`LimbChoice`], suitable for subsequent
//! branchless selections, e.g. with [`LimbChoice::select_usize()`].

use super::limb::{LimbChoice, LimbType};
use core::arch::asm;

/// Hide a [`usize`] value from the optimizer.
///
/// Returns `v` unmodified, but prevents the compiler from reasoning about the
/// value and, in particular, from converting subsequent branchless
/// computations on it back into conditional branches. Unlike
/// [`core::hint::black_box()`], which writes to and reads from memory, this
/// keeps the value in a register.
///
/// # Arguments
///
/// * `v` - The value to hide.
#[inline(always)]
fn black_box_usize(v: usize) -> usize {
    let result: usize;
    unsafe {
        asm!("/* {v} */", v = inout(reg) v => result, options(pure, nomem, nostack));
    }
    result
}

/// Test a [`usize`] for being non-zero in constant time.
///
/// Returns one if `v` is non-zero and zero otherwise.
///
/// Runs in constant time, independent of the argument value. See
/// [`ct_is_zero_usize()`] for the negated test.
///
/// # Arguments
///
/// * `v` - The value to test.
fn ct_is_nonzero_usize(v: usize) -> LimbType {
    // This trick is from subtle::*::ct_eq():
    // if v is non-zero, then v or -v or both have the high bit set.
    black_box_usize((v | v.wrapping_neg()) >> (usize::BITS - 1)) as LimbType
}

/// Test a [`usize`] for being zero in constant time.
///
/// Returns one if `v` is zero and zero otherwise.
///
/// Runs in constant time, independent of the argument value. See
/// [`ct_is_nonzero_usize()`] for the negated test.
///
/// # Arguments
///
/// * `v` - The value to test.
pub(super) fn ct_is_zero_usize(v: usize) -> LimbType {
    (1 as LimbType) ^ ct_is_nonzero_usize(v)
}

/// Compare two [`usize`] values for `==` in constant time.
///
/// Returns a [`LimbChoice`] representing `true` if `v0` is equal to `v1` and
/// `false` otherwise.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The first operand.
/// * `v1` - The second operand.
pub fn ct_eq_usize_usize(v0: usize, v1: usize) -> LimbChoice {
    LimbChoice::from(ct_is_zero_usize(v0 ^ v1))
}

/// Subtract two [`usize`] values in constant time.
///
/// Returns a pair of the borrow, either zero or one, the latter if and only if
/// `v1` is greater than `v0`, and the difference *`v0` - `v1`* modulo
/// *2<sup>[`usize::BITS`]</sup>*.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The minuend.
/// * `v1` - The subtrahend.
fn ct_sub_usize_usize(v0: usize, v1: usize) -> (usize, usize) {
    // Don't rely on overflowing_sub() for determining the borrow -- that would
    // almost certainly branch and not be constant-time.
    let v0 = black_box_usize(v0);
    let v1 = black_box_usize(v1);
    let r = v0.wrapping_sub(v1);
    let borrow = black_box_usize((((r | v1) & !v0) | (v1 & r)) >> (usize::BITS - 1));
    (borrow, r)
}

#[test]
fn test_ct_sub_usize_usize() {
    assert_eq!(ct_sub_usize_usize(0, 0), (0, 0));
    assert_eq!(ct_sub_usize_usize(1, 0), (0, 1));
    assert_eq!(ct_sub_usize_usize(0, 1), (1, !0));
    assert_eq!(
        ct_sub_usize_usize(1 << (usize::BITS - 1), 1 << (usize::BITS - 1)),
        (0, 0)
    );
    assert_eq!(
        ct_sub_usize_usize(0, 1 << (usize::BITS - 1)),
        (1, 1 << (usize::BITS - 1))
    );
    assert_eq!(
        ct_sub_usize_usize(1 << (usize::BITS - 1), (1 << (usize::BITS - 1)) + 1),
        (1, !0)
    );
}

/// Compare two [`usize`] values for `<` in constant time.
///
/// Returns a [`LimbChoice`] representing `true` if `v0` is less than `v1` and
/// `false` otherwise.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The first operand.
/// * `v1` - The second operand.
pub fn ct_lt_usize_usize(v0: usize, v1: usize) -> LimbChoice {
    let (borrow, _) = ct_sub_usize_usize(v0, v1);
    LimbChoice::from(borrow as LimbType)
}

/// Compare two [`usize`] values for `<=` in constant time.
///
/// Returns a [`LimbChoice`] representing `true` if `v0` is
/// less than or equal to `v1` and `false` otherwise.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The first operand.
/// * `v1` - The second operand.
pub fn ct_leq_usize_usize(v0: usize, v1: usize) -> LimbChoice {
    !ct_lt_usize_usize(v1, v0)
}

/// Compare two [`usize`] values for `>` in constant time.
///
/// Returns a [`LimbChoice`] representing `true` if `v0` is greater than
/// `v1` and `false` otherwise.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The first operand.
/// * `v1` - The second operand.
pub fn ct_gt_usize_usize(v0: usize, v1: usize) -> LimbChoice {
    ct_lt_usize_usize(v1, v0)
}

/// Compare two [`usize`] values for `>=` in constant time.
///
/// Returns a [`LimbChoice`] representing `true` if `v0` is
/// greater than or equal to `v1` and `false` otherwise.
///
/// Runs in constant time, independent of the argument values.
///
/// # Arguments
///
/// * `v0` - The first operand.
/// * `v1` - The second operand.
pub fn ct_geq_usize_usize(v0: usize, v1: usize) -> LimbChoice {
    ct_leq_usize_usize(v1, v0)
}