fixed_bigint/heapless/
has_nonzero.rs

1//! `HasNonZero` / `DivNonZero` / `CtNonZero` for `HeaplessBigInt`, plus the
2//! [`NonZeroHeaplessBigInt`] proof-type they hand out.
3//!
4//! Mirrors `FixedUInt`'s `has_nonzero_impl.rs`: `into_nonzero` returns a
5//! branchful `Option` (fine for public moduli); secret-derived proofs go
6//! through `CtNonZero::into_nonzero_ct`, a masked-return `CtOption`. None of
7//! this needs `const_ct_select` — `into_nonzero_ct` masks with `ct_is_zero`
8//! and `subtle::CtOption`, both of which heapless already carries.
9
10// `let _ = <Self as AssertNonzeroCarrier>::CHECK;` in `Default::default()`
11// forces monomorphization-time evaluation of the `CAP > 0` assertion (same
12// idiom as `AssertCapFits` in this module).
13#![allow(clippy::let_unit_value)]
14
15use super::HeaplessBigInt;
16use crate::MachineWord;
17use const_num_traits::{CarryingMul, Ct, DivNonZero, HasNonZero, Nct, One, Personality, Zero};
18
19/// Non-zero [`HeaplessBigInt`]. Constructed via [`HasNonZero::into_nonzero`].
20///
21/// `#[repr(transparent)]` over the inner value: identical layout, so the
22/// wrapper round-trips at the same ABI. Always `Copy` (matches
23/// `HasNonZero::NonZero: Copy`).
24#[repr(transparent)]
25#[derive(Clone, Copy, PartialEq, Eq)]
26pub struct NonZeroHeaplessBigInt<T, const CAP: usize, P: Personality>(HeaplessBigInt<T, CAP, P>)
27where
28    T: MachineWord;
29
30// Manual `Debug` (not derive): the Nct arm needs `T: Debug`, the Ct arm is
31// opaque, matching `HeaplessBigInt`'s own personality-split `Debug`.
32impl<T: MachineWord + core::fmt::Debug, const CAP: usize> core::fmt::Debug
33    for NonZeroHeaplessBigInt<T, CAP, Nct>
34{
35    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
36        write!(f, "NonZero({:?})", self.0)
37    }
38}
39
40impl<T: MachineWord, const CAP: usize> core::fmt::Debug for NonZeroHeaplessBigInt<T, CAP, Ct> {
41    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
42        write!(f, "NonZero({:?})", self.0)
43    }
44}
45
46impl<T, const CAP: usize, P: Personality> NonZeroHeaplessBigInt<T, CAP, P>
47where
48    T: MachineWord,
49{
50    /// Recover the underlying [`HeaplessBigInt`].
51    #[inline]
52    pub fn get(self) -> HeaplessBigInt<T, CAP, P> {
53        self.0
54    }
55}
56
57// Type-level `CAP > 0` guard — a `CAP == 0` carrier can't store the `1` that
58// `Default` produces. Associated-const form so it fires at monomorphization.
59trait AssertNonzeroCarrier {
60    const CHECK: ();
61}
62impl<T: MachineWord, const CAP: usize, P: Personality> AssertNonzeroCarrier
63    for NonZeroHeaplessBigInt<T, CAP, P>
64{
65    const CHECK: () = assert!(
66        CAP > 0,
67        "NonZeroHeaplessBigInt::default() requires CAP > 0 (a CAP=0 carrier can only hold zero)"
68    );
69}
70
71// `Default` is the non-zero value 1, the same convention as
72// `core::num::NonZero`, carried at **full capacity** (`len == CAP`) — the
73// CAP-width analog of FixedUInt's N-width `NonZeroFixedUInt::default()`. Built
74// value-based via `One` (not the source-width `From<u8>`) then widened. Needed
75// by `subtle::CtOption` combinators whose bound is `T: Default +
76// ConditionallySelectable`; `conditional_select` handles any len safely
77// (output width is `max(len)`, choice-independent), but matching FixedUInt's
78// full width keeps the two carriers' Default shapes aligned.
79impl<T, const CAP: usize, P: Personality> Default for NonZeroHeaplessBigInt<T, CAP, P>
80where
81    T: MachineWord,
82{
83    fn default() -> Self {
84        let _ = <Self as AssertNonzeroCarrier>::CHECK;
85        NonZeroHeaplessBigInt(<HeaplessBigInt<T, CAP, P> as One>::one().widened(CAP as u16))
86    }
87}
88
89// Ct-only, mirroring `HeaplessBigInt`'s own `ConditionallySelectable`. Both
90// arms carry the "value != 0" invariant, so the selected value is non-zero
91// regardless of which is taken.
92impl<T, const CAP: usize> subtle::ConditionallySelectable for NonZeroHeaplessBigInt<T, CAP, Ct>
93where
94    T: MachineWord + subtle::ConditionallySelectable,
95{
96    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
97        Self(
98            <HeaplessBigInt<T, CAP, Ct> as subtle::ConditionallySelectable>::conditional_select(
99                &a.0, &b.0, choice,
100            ),
101        )
102    }
103}
104
105impl<T, const CAP: usize, P: Personality> HasNonZero for HeaplessBigInt<T, CAP, P>
106where
107    T: MachineWord,
108{
109    type NonZero = NonZeroHeaplessBigInt<T, CAP, P>;
110
111    /// `Option` is branchful at the call site — fine for public inputs; a
112    /// secret-derived `self` should route through
113    /// [`CtNonZero::into_nonzero_ct`](const_num_traits::CtNonZero) instead.
114    #[inline]
115    fn into_nonzero(self) -> Option<Self::NonZero> {
116        if <Self as Zero>::is_zero(&self) {
117            None
118        } else {
119            Some(NonZeroHeaplessBigInt(self))
120        }
121    }
122
123    #[inline]
124    fn nonzero_get(nz: Self::NonZero) -> Self {
125        nz.0
126    }
127}
128
129// `DivNonZero` is Nct-only because `Div`/`Rem` on `HeaplessBigInt` are
130// (long division is value-dependent).
131//
132// Panic-freeness: the API contract ("no `Result`/`.unwrap()` at the caller
133// boundary") is met — the `NonZeroHeaplessBigInt` proof-type discharges the
134// divide-by-zero check statically. But `self / d.0` still routes through
135// `div_rem_impl`, which keeps a runtime divisor-non-zero assert LLVM can't
136// prove unreachable through the `#[repr(transparent)]` wrapper, so the binary
137// retains a `panic_fmt` symbol. Same accepted residual as
138// `FixedUInt`'s `DivNonZero`; a truly no-check divide would be a separate
139// cross-carrier change. Consumers needing a *binary-level* panic-free divide
140// should audit downstream.
141impl<T, const CAP: usize> DivNonZero for HeaplessBigInt<T, CAP, Nct>
142where
143    T: MachineWord + CarryingMul<Unsigned = T, Output = T>,
144{
145    type Output = Self;
146
147    #[inline]
148    fn div_nonzero(self, d: Self::NonZero) -> Self::Output {
149        self / d.0
150    }
151
152    #[inline]
153    fn rem_nonzero(self, d: Self::NonZero) -> Self::Output {
154        self % d.0
155    }
156}
157
158// `CtNonZero` — masked-return `into_nonzero`; the `Choice` mask is value-level
159// and CT-uniform across personalities. No `const_ct_select` needed.
160impl<T, const CAP: usize, P: Personality> const_num_traits::CtNonZero for HeaplessBigInt<T, CAP, P>
161where
162    T: MachineWord + subtle::ConstantTimeEq,
163{
164    fn into_nonzero_ct(self) -> subtle::CtOption<Self::NonZero> {
165        use const_num_traits::ops::ct::CtIsZero;
166        let zero = self.ct_is_zero();
167        subtle::CtOption::new(NonZeroHeaplessBigInt(self), !zero)
168    }
169}
170
171#[cfg(test)]
172mod tests {
173    use super::*;
174    use const_num_traits::CtNonZero;
175
176    type H = HeaplessBigInt<u8, 4, Nct>;
177    type HCt = HeaplessBigInt<u8, 4, Ct>;
178
179    #[test]
180    fn into_nonzero_some_none() {
181        assert!(H::from(5u32).into_nonzero().is_some());
182        assert!(H::from(0u32).into_nonzero().is_none());
183    }
184
185    #[test]
186    fn default_is_one_at_full_capacity() {
187        // Value 1, carried at CAP (matching FixedUInt's full-width default).
188        let d = <NonZeroHeaplessBigInt<u8, 4, Nct> as Default>::default();
189        assert_eq!(d.get(), H::from(1u8));
190        assert_eq!(d.get().len(), 4);
191    }
192
193    #[test]
194    fn nonzero_round_trip() {
195        let v = H::from(42u32);
196        let nz = v.into_nonzero().unwrap();
197        assert_eq!(<H as HasNonZero>::nonzero_get(nz), v);
198        assert_eq!(nz.get(), v);
199    }
200
201    #[test]
202    fn div_rem_nonzero_match_operators() {
203        let a = H::from(100u32);
204        let m = H::from(7u32);
205        let nz = m.into_nonzero().unwrap();
206        assert_eq!(<H as DivNonZero>::div_nonzero(a, nz), a / m);
207        assert_eq!(<H as DivNonZero>::rem_nonzero(a, nz), a % m);
208    }
209
210    // `DivNonZero for HeaplessBigInt<_, _, Ct>` must NOT exist (Div is
211    // Nct-only); the `HasNonZero` proof-type is still P-generic.
212    static_assertions::assert_not_impl_any!(HeaplessBigInt<u8, 4, Ct>: DivNonZero);
213
214    #[test]
215    fn into_nonzero_ct_masks_zero() {
216        let nz = H::from(5u32).into_nonzero_ct();
217        assert!(bool::from(nz.is_some()));
218        assert_eq!(nz.unwrap().get(), H::from(5u32));
219        assert!(!bool::from(H::from(0u32).into_nonzero_ct().is_some()));
220
221        // Ct carrier: masking works without revealing the zero-ness branchfully.
222        let nz_ct = HCt::from(42u32);
223        assert!(bool::from(nz_ct.into_nonzero_ct().is_some()));
224        let z_ct = HCt::from(0u32);
225        assert!(!bool::from(z_ct.into_nonzero_ct().is_some()));
226    }
227}
fixed_bigint/heapless/has_nonzero.rs

fixed_bigint/heapless/
has_nonzero.rs
