cnfy-uint 0.2.3

Zero-dependency 256-bit unsigned integer arithmetic for cryptographic applications
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

//! Bit-level leading zero count for [`U512`].
use super::U512;

impl U512 {
    /// Returns the number of leading zero bits in the 512-bit value.
    ///
    /// Scans from the most significant limb (`w0`) downward. Returns 512
    /// for zero, 0 for any value with the MSB set, and `512 - bit_len()`
    /// in general.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u512::U512;
    ///
    /// assert_eq!(U512::ZERO.leading_zeros(), 512);
    /// assert_eq!(U512::ONE.leading_zeros(), 511);
    /// assert_eq!(U512::MAX.leading_zeros(), 0);
    /// ```
    #[inline]
    pub const fn leading_zeros(&self) -> u32 {
        if self.0[7] != 0 {
            self.0[7].leading_zeros()
        } else if self.0[6] != 0 {
            64 + self.0[6].leading_zeros()
        } else if self.0[5] != 0 {
            128 + self.0[5].leading_zeros()
        } else if self.0[4] != 0 {
            192 + self.0[4].leading_zeros()
        } else if self.0[3] != 0 {
            256 + self.0[3].leading_zeros()
        } else if self.0[2] != 0 {
            320 + self.0[2].leading_zeros()
        } else if self.0[1] != 0 {
            384 + self.0[1].leading_zeros()
        } else if self.0[0] != 0 {
            448 + self.0[0].leading_zeros()
        } else {
            512
        }
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;

    /// Zero has 512 leading zeros.
    #[test]
    fn zero() {
        assert_eq!(U512::ZERO.leading_zeros(), 512);
    }

    /// One has 511 leading zeros.
    #[test]
    fn one() {
        assert_eq!(U512::ONE.leading_zeros(), 511);
    }

    /// MAX has 0 leading zeros.
    #[test]
    fn max() {
        assert_eq!(U512::MAX.leading_zeros(), 0);
    }

    /// Consistent with bit_len: leading_zeros + bit_len = 512 (nonzero).
    #[test]
    fn consistent_with_bit_len() {
        let cases = [
            U512::ONE,
            U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 0xFF]),
            U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]),
            U512::from_be_limbs([0, 0, 0, 0, 1, 0, 0, 0]),
            U512::from_be_limbs([1, 0, 0, 0, 0, 0, 0, 0]),
            U512::MAX,
        ];
        for v in &cases {
            assert_eq!(v.leading_zeros() + v.bit_len(), 512);
        }
    }

    /// Powers of two have leading_zeros = 511 - exponent.
    #[test]
    fn powers_of_two() {
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 1]).leading_zeros(), 511);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]).leading_zeros(), 447);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 1, 0, 0]).leading_zeros(), 383);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 1, 0, 0, 0]).leading_zeros(), 319);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 1, 0, 0, 0, 0]).leading_zeros(), 255);
        assert_eq!(U512::from_be_limbs([0, 0, 1, 0, 0, 0, 0, 0]).leading_zeros(), 191);
        assert_eq!(U512::from_be_limbs([0, 1, 0, 0, 0, 0, 0, 0]).leading_zeros(), 127);
        assert_eq!(U512::from_be_limbs([1, 0, 0, 0, 0, 0, 0, 0]).leading_zeros(), 63);
    }

    /// Limb boundary values.
    #[test]
    fn limb_boundaries() {
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, u64::MAX]).leading_zeros(), 448);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 0, u64::MAX, 0]).leading_zeros(), 384);
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, u64::MAX, 0, 0, 0]).leading_zeros(), 256);
        assert_eq!(U512::from_be_limbs([u64::MAX, 0, 0, 0, 0, 0, 0, 0]).leading_zeros(), 0);
    }

    /// Value 0x80 in the LSB limb.
    #[test]
    fn byte_boundary() {
        assert_eq!(U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 0x80]).leading_zeros(), 504);
    }
}