fixed_bigint/fixeduint/
parity_impl.rs

1// Copyright 2021 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! `Parity` and `CtParity` implementations for FixedUInt.
16//!
17//! Parity is a pure low-bit query: `is_odd` ↔ LSB of word 0 is 1.
18//! Branchless on both personalities; safe to implement uniformly.
19//!
20//! `CtParity` (`ct_is_odd` / `ct_is_even`) is the masked counterpart;
21//! it routes the LSB-vs-zero comparison through `subtle::ConstantTimeEq`
22//! rather than `!=`, so the returned `Choice` stays masked under both
23//! `Nct` and `Ct` callers — `Odd::<FixedUInt<...>>::new_ct(v)` (the
24//! downstream consumer in `const-num-traits/src/ops/typestate.rs`) gets
25//! its `CtOption`-shaped construction path for free.
26
27use super::{FixedUInt, MachineWord};
28use crate::machineword::ConstMachineWord;
29use const_num_traits::ops::ct::CtParity;
30use const_num_traits::{ConstOne, ConstZero, Parity, Personality};
31use subtle::{Choice, ConstantTimeEq};
32
33c0nst::c0nst! {
34    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> Parity for FixedUInt<T, N, P> {
35        fn is_odd(self) -> bool {
36            // N=0 is a degenerate (zero-word) configuration; treat as even.
37            // Otherwise parity lives entirely in the LSB of word 0.
38            if N == 0 {
39                false
40            } else {
41                (self.array[0] & <T as ConstOne>::ONE)
42                    != <T as ConstZero>::ZERO
43            }
44        }
45        fn is_even(self) -> bool {
46            !<Self as Parity>::is_odd(self)
47        }
48    }
49
50    // The reference-receiver impl is provided by const_num_traits's blanket
51    // `impl<T: Parity + Copy> Parity for &T`; a manual impl here would
52    // conflict (E0119).
53}
54
55// `CtParity` is **not** a `c0nst trait` upstream — `subtle::Choice`
56// constructors aren't `const fn` yet (the upstream module doc spells this
57// out: "plain (never-const) traits: subtle's constructors are not const
58// fn"). So the impl is a plain `impl`, not wrapped in `c0nst::c0nst!`.
59impl<T, const N: usize, P: Personality> CtParity for FixedUInt<T, N, P>
60where
61    T: MachineWord + ConstantTimeEq,
62{
63    /// LSB of word 0, masked through `subtle::ConstantTimeEq` against
64    /// `ZERO`. Same body for both personalities — under `Nct`, the
65    /// branchless form is still correct, just unnecessary for CT
66    /// hygiene; under `Ct`, this is the path that keeps the result
67    /// masked all the way to `Odd::new_ct`.
68    fn ct_is_odd(&self) -> Choice {
69        if N == 0 {
70            // Degenerate (zero-word) configuration; treat as even.
71            return Choice::from(0);
72        }
73        let lsb = self.array[0] & <T as ConstOne>::ONE;
74        !lsb.ct_eq(&<T as ConstZero>::ZERO)
75    }
76
77    fn ct_is_even(&self) -> Choice {
78        !<Self as CtParity>::ct_is_odd(self)
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use const_num_traits::{Ct, Nct};
86
87    type U16Nct = FixedUInt<u8, 2, Nct>;
88    type U16Ct = FixedUInt<u8, 2, Ct>;
89
90    #[test]
91    fn parity_nct() {
92        assert!(Parity::is_odd(U16Nct::from(1u8)));
93        assert!(Parity::is_odd(U16Nct::from(3u8)));
94        assert!(Parity::is_odd(U16Nct::from(0xFFFFu16)));
95        assert!(!Parity::is_odd(U16Nct::from(0u8)));
96        assert!(!Parity::is_odd(U16Nct::from(2u8)));
97        assert!(!Parity::is_odd(U16Nct::from(0xFFFEu16)));
98
99        assert!(Parity::is_even(U16Nct::from(0u8)));
100        assert!(!Parity::is_even(U16Nct::from(1u8)));
101    }
102
103    #[test]
104    fn parity_ct() {
105        let one_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(1u8).into();
106        let two_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(2u8).into();
107        assert!(Parity::is_odd(one_ct));
108        assert!(Parity::is_even(two_ct));
109    }
110
111    #[test]
112    #[allow(clippy::needless_borrows_for_generic_args)]
113    fn parity_ref() {
114        let v = U16Nct::from(7u8);
115        assert!(Parity::is_odd(&v));
116        assert!(!Parity::is_even(&v));
117    }
118
119    // --- Const-eval smoke --------------------------------------------------
120    c0nst::c0nst! {
121        pub c0nst fn const_is_odd<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> bool {
122            Parity::is_odd(v)
123        }
124        pub c0nst fn const_is_even<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> bool {
125            Parity::is_even(v)
126        }
127    }
128
129    #[test]
130    fn nightly_const_eval_parity() {
131        // runtime smoke
132        assert!(const_is_odd(U16Nct::from(7u8)));
133        assert!(const_is_even(U16Nct::from(8u8)));
134
135        #[cfg(feature = "nightly")]
136        {
137            const ODD: U16Nct = FixedUInt::from_array([7, 0]);
138            const EVEN: U16Nct = FixedUInt::from_array([8, 0]);
139            const IS_ODD: bool = const_is_odd(ODD);
140            const IS_EVEN: bool = const_is_even(EVEN);
141            const IS_ODD_OF_EVEN: bool = const_is_odd(EVEN);
142            assert!(IS_ODD);
143            assert!(IS_EVEN);
144            assert!(!IS_ODD_OF_EVEN);
145        }
146    }
147
148    // ── CtParity (masked-return parity) ─────────────────────────────────
149
150    #[test]
151    fn ct_parity_nct() {
152        // Returns `Choice` regardless of personality; convert at the
153        // assertion site to compare.
154        assert!(bool::from(CtParity::ct_is_odd(&U16Nct::from(1u8))));
155        assert!(bool::from(CtParity::ct_is_odd(&U16Nct::from(3u8))));
156        assert!(bool::from(CtParity::ct_is_odd(&U16Nct::from(0xFFFFu16))));
157        assert!(!bool::from(CtParity::ct_is_odd(&U16Nct::from(0u8))));
158        assert!(!bool::from(CtParity::ct_is_odd(&U16Nct::from(2u8))));
159
160        assert!(bool::from(CtParity::ct_is_even(&U16Nct::from(0u8))));
161        assert!(!bool::from(CtParity::ct_is_even(&U16Nct::from(1u8))));
162    }
163
164    #[test]
165    fn ct_parity_ct() {
166        let one_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(1u8).into();
167        let two_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(2u8).into();
168        assert!(bool::from(CtParity::ct_is_odd(&one_ct)));
169        assert!(bool::from(CtParity::ct_is_even(&two_ct)));
170    }
171
172    #[test]
173    fn ct_parity_agrees_with_parity() {
174        // The masked-return and plain forms must agree on truth value
175        // for every input. Sweep a handful of representative values
176        // (full 16-bit sweep is overkill but cheap).
177        for v in [
178            0u16, 1, 2, 3, 7, 8, 0xFE, 0xFF, 0x100, 0x101, 0xFFFE, 0xFFFF,
179        ] {
180            let nct = U16Nct::from(v);
181            let ct: U16Ct = U16Nct::from(v).into();
182            assert_eq!(
183                bool::from(CtParity::ct_is_odd(&nct)),
184                Parity::is_odd(nct),
185                "Nct ct_is_odd disagrees with is_odd at v={v}"
186            );
187            assert_eq!(
188                bool::from(CtParity::ct_is_odd(&ct)),
189                Parity::is_odd(ct),
190                "Ct ct_is_odd disagrees with is_odd at v={v}"
191            );
192        }
193    }
194
195    /// `Odd::<FixedUInt<_, _, Ct>>::new_ct(n)` round-trips — exercises the
196    /// upstream typestate construction path on the Ct personality.
197    #[test]
198    fn odd_new_ct_round_trips_for_ct_carrier() {
199        use const_num_traits::Odd;
200
201        let odd_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(7u8).into();
202        let even_ct: U16Ct = FixedUInt::<u8, 2, Nct>::from(8u8).into();
203
204        let p_odd = Odd::<U16Ct>::new_ct(odd_ct);
205        let p_even = Odd::<U16Ct>::new_ct(even_ct);
206
207        assert!(
208            bool::from(p_odd.is_some()),
209            "Odd::new_ct(7) should mask Some"
210        );
211        assert!(
212            !bool::from(p_even.is_some()),
213            "Odd::new_ct(8) should mask None"
214        );
215
216        let recovered = p_odd.unwrap();
217        assert_eq!(recovered.get(), odd_ct);
218    }
219}
fixed_bigint/fixeduint/parity_impl.rs

fixed_bigint/fixeduint/
parity_impl.rs
