Rollup merge of #92956 - scottmcm:nonzero-log2, r=dtolnay

Add `log2` and `log10` to `NonZeroU*`

This version is nice in that it doesn't need to worry about zeros, and thus doesn't have any error cases.

cc `int_log` tracking issue #70887

(I didn't add them to `NonZeroI*` despite it being on `i*` since allowing negatives bring back the error cases again.)

5 files changed, 197 insertions, 141 deletions

diff --git a/library/core/src/num/int_log10.rs b/library/core/src/num/int_log10.rs
index a8455fb355b..cc26c04a5d4 100644
--- a/library/core/src/num/int_log10.rs
+++ b/library/core/src/num/int_log10.rs
@@ -1,141 +1,140 @@
-mod unchecked {
-    // 0 < val <= u8::MAX
-    #[inline]
-    pub const fn u8(val: u8) -> u32 {
-        let val = val as u32;
-
-        // For better performance, avoid branches by assembling the solution
-        // in the bits above the low 8 bits.
-
-        // Adding c1 to val gives 10 in the top bits for val < 10, 11 for val >= 10
-        const C1: u32 = 0b11_00000000 - 10; // 758
-        // Adding c2 to val gives 01 in the top bits for val < 100, 10 for val >= 100
-        const C2: u32 = 0b10_00000000 - 100; // 412
-
-        // Value of top bits:
-        //            +c1  +c2  1&2
-        //     0..=9   10   01   00 = 0
-        //   10..=99   11   01   01 = 1
-        // 100..=255   11   10   10 = 2
-        ((val + C1) & (val + C2)) >> 8
-    }
+/// These functions compute the integer logarithm of their type, assuming
+/// that someone has already checked that the the value is strictly positive.
+
+// 0 < val <= u8::MAX
+#[inline]
+pub const fn u8(val: u8) -> u32 {
+    let val = val as u32;
+
+    // For better performance, avoid branches by assembling the solution
+    // in the bits above the low 8 bits.
+
+    // Adding c1 to val gives 10 in the top bits for val < 10, 11 for val >= 10
+    const C1: u32 = 0b11_00000000 - 10; // 758
+    // Adding c2 to val gives 01 in the top bits for val < 100, 10 for val >= 100
+    const C2: u32 = 0b10_00000000 - 100; // 412
+
+    // Value of top bits:
+    //            +c1  +c2  1&2
+    //     0..=9   10   01   00 = 0
+    //   10..=99   11   01   01 = 1
+    // 100..=255   11   10   10 = 2
+    ((val + C1) & (val + C2)) >> 8
+}
 
-    // 0 < val < 100_000
-    #[inline]
-    const fn less_than_5(val: u32) -> u32 {
-        // Similar to u8, when adding one of these constants to val,
-        // we get two possible bit patterns above the low 17 bits,
-        // depending on whether val is below or above the threshold.
-        const C1: u32 = 0b011_00000000000000000 - 10; // 393206
-        const C2: u32 = 0b100_00000000000000000 - 100; // 524188
-        const C3: u32 = 0b111_00000000000000000 - 1000; // 916504
-        const C4: u32 = 0b100_00000000000000000 - 10000; // 514288
-
-        // Value of top bits:
-        //                +c1  +c2  1&2  +c3  +c4  3&4   ^
-        //         0..=9  010  011  010  110  011  010  000 = 0
-        //       10..=99  011  011  011  110  011  010  001 = 1
-        //     100..=999  011  100  000  110  011  010  010 = 2
-        //   1000..=9999  011  100  000  111  011  011  011 = 3
-        // 10000..=99999  011  100  000  111  100  100  100 = 4
-        (((val + C1) & (val + C2)) ^ ((val + C3) & (val + C4))) >> 17
-    }
+// 0 < val < 100_000
+#[inline]
+const fn less_than_5(val: u32) -> u32 {
+    // Similar to u8, when adding one of these constants to val,
+    // we get two possible bit patterns above the low 17 bits,
+    // depending on whether val is below or above the threshold.
+    const C1: u32 = 0b011_00000000000000000 - 10; // 393206
+    const C2: u32 = 0b100_00000000000000000 - 100; // 524188
+    const C3: u32 = 0b111_00000000000000000 - 1000; // 916504
+    const C4: u32 = 0b100_00000000000000000 - 10000; // 514288
+
+    // Value of top bits:
+    //                +c1  +c2  1&2  +c3  +c4  3&4   ^
+    //         0..=9  010  011  010  110  011  010  000 = 0
+    //       10..=99  011  011  011  110  011  010  001 = 1
+    //     100..=999  011  100  000  110  011  010  010 = 2
+    //   1000..=9999  011  100  000  111  011  011  011 = 3
+    // 10000..=99999  011  100  000  111  100  100  100 = 4
+    (((val + C1) & (val + C2)) ^ ((val + C3) & (val + C4))) >> 17
+}
 
-    // 0 < val <= u16::MAX
-    #[inline]
-    pub const fn u16(val: u16) -> u32 {
-        less_than_5(val as u32)
-    }
+// 0 < val <= u16::MAX
+#[inline]
+pub const fn u16(val: u16) -> u32 {
+    less_than_5(val as u32)
+}
 
-    // 0 < val <= u32::MAX
-    #[inline]
-    pub const fn u32(mut val: u32) -> u32 {
-        let mut log = 0;
-        if val >= 100_000 {
-            val /= 100_000;
-            log += 5;
-        }
-        log + less_than_5(val)
+// 0 < val <= u32::MAX
+#[inline]
+pub const fn u32(mut val: u32) -> u32 {
+    let mut log = 0;
+    if val >= 100_000 {
+        val /= 100_000;
+        log += 5;
     }
+    log + less_than_5(val)
+}
 
-    // 0 < val <= u64::MAX
-    #[inline]
-    pub const fn u64(mut val: u64) -> u32 {
-        let mut log = 0;
-        if val >= 10_000_000_000 {
-            val /= 10_000_000_000;
-            log += 10;
-        }
-        if val >= 100_000 {
-            val /= 100_000;
-            log += 5;
-        }
-        log + less_than_5(val as u32)
+// 0 < val <= u64::MAX
+#[inline]
+pub const fn u64(mut val: u64) -> u32 {
+    let mut log = 0;
+    if val >= 10_000_000_000 {
+        val /= 10_000_000_000;
+        log += 10;
     }
-
-    // 0 < val <= u128::MAX
-    #[inline]
-    pub const fn u128(mut val: u128) -> u32 {
-        let mut log = 0;
-        if val >= 100_000_000_000_000_000_000_000_000_000_000 {
-            val /= 100_000_000_000_000_000_000_000_000_000_000;
-            log += 32;
-            return log + u32(val as u32);
-        }
-        if val >= 10_000_000_000_000_000 {
-            val /= 10_000_000_000_000_000;
-            log += 16;
-        }
-        log + u64(val as u64)
+    if val >= 100_000 {
+        val /= 100_000;
+        log += 5;
     }
+    log + less_than_5(val as u32)
+}
 
-    // 0 < val <= i8::MAX
-    #[inline]
-    pub const fn i8(val: i8) -> u32 {
-        u8(val as u8)
+// 0 < val <= u128::MAX
+#[inline]
+pub const fn u128(mut val: u128) -> u32 {
+    let mut log = 0;
+    if val >= 100_000_000_000_000_000_000_000_000_000_000 {
+        val /= 100_000_000_000_000_000_000_000_000_000_000;
+        log += 32;
+        return log + u32(val as u32);
     }
-
-    // 0 < val <= i16::MAX
-    #[inline]
-    pub const fn i16(val: i16) -> u32 {
-        u16(val as u16)
+    if val >= 10_000_000_000_000_000 {
+        val /= 10_000_000_000_000_000;
+        log += 16;
     }
+    log + u64(val as u64)
+}
 
-    // 0 < val <= i32::MAX
-    #[inline]
-    pub const fn i32(val: i32) -> u32 {
-        u32(val as u32)
-    }
+#[cfg(target_pointer_width = "16")]
+#[inline]
+pub const fn usize(val: usize) -> u32 {
+    u16(val as _)
+}
 
-    // 0 < val <= i64::MAX
-    #[inline]
-    pub const fn i64(val: i64) -> u32 {
-        u64(val as u64)
-    }
+#[cfg(target_pointer_width = "32")]
+#[inline]
+pub const fn usize(val: usize) -> u32 {
+    u32(val as _)
+}
 
-    // 0 < val <= i128::MAX
-    #[inline]
-    pub const fn i128(val: i128) -> u32 {
-        u128(val as u128)
-    }
+#[cfg(target_pointer_width = "64")]
+#[inline]
+pub const fn usize(val: usize) -> u32 {
+    u64(val as _)
+}
+
+// 0 < val <= i8::MAX
+#[inline]
+pub const fn i8(val: i8) -> u32 {
+    u8(val as u8)
 }
 
-macro_rules! impl_checked {
-    ($T:ident) => {
-        #[inline]
-        pub const fn $T(val: $T) -> Option<u32> {
-            if val > 0 { Some(unchecked::$T(val)) } else { None }
-        }
-    };
+// 0 < val <= i16::MAX
+#[inline]
+pub const fn i16(val: i16) -> u32 {
+    u16(val as u16)
 }
 
-impl_checked! { u8 }
-impl_checked! { u16 }
-impl_checked! { u32 }
-impl_checked! { u64 }
-impl_checked! { u128 }
-impl_checked! { i8 }
-impl_checked! { i16 }
-impl_checked! { i32 }
-impl_checked! { i64 }
-impl_checked! { i128 }
+// 0 < val <= i32::MAX
+#[inline]
+pub const fn i32(val: i32) -> u32 {
+    u32(val as u32)
+}
+
+// 0 < val <= i64::MAX
+#[inline]
+pub const fn i64(val: i64) -> u32 {
+    u64(val as u64)
+}
+
+// 0 < val <= i128::MAX
+#[inline]
+pub const fn i128(val: i128) -> u32 {
+    u128(val as u128)
+}
diff --git a/library/core/src/num/int_macros.rs b/library/core/src/num/int_macros.rs
index 6f7c5a6d119..79436c8e8ed 100644
--- a/library/core/src/num/int_macros.rs
+++ b/library/core/src/num/int_macros.rs
@@ -2362,7 +2362,11 @@ macro_rules! int_impl {
                       without modifying the original"]
         #[inline]
         pub const fn checked_log10(self) -> Option<u32> {
-            int_log10::$ActualT(self as $ActualT)
+            if self > 0 {
+                Some(int_log10::$ActualT(self as $ActualT))
+            } else {
+                None
+            }
         }
 
         /// Computes the absolute value of `self`.
diff --git a/library/core/src/num/mod.rs b/library/core/src/num/mod.rs
index e3eab07b9df..721c030b410 100644
--- a/library/core/src/num/mod.rs
+++ b/library/core/src/num/mod.rs
@@ -264,7 +264,7 @@ const ASCII_CASE_MASK: u8 = 0b0010_0000;
 
 #[lang = "u8"]
 impl u8 {
-    uint_impl! { u8, u8, i8, 8, 255, 2, "0x82", "0xa", "0x12", "0x12", "0x48", "[0x12]",
+    uint_impl! { u8, u8, i8, NonZeroU8, 8, 255, 2, "0x82", "0xa", "0x12", "0x12", "0x48", "[0x12]",
     "[0x12]", "", "" }
     widening_impl! { u8, u16, 8, unsigned }
 
@@ -813,21 +813,21 @@ impl u8 {
 
 #[lang = "u16"]
 impl u16 {
-    uint_impl! { u16, u16, i16, 16, 65535, 4, "0xa003", "0x3a", "0x1234", "0x3412", "0x2c48",
+    uint_impl! { u16, u16, i16, NonZeroU16, 16, 65535, 4, "0xa003", "0x3a", "0x1234", "0x3412", "0x2c48",
     "[0x34, 0x12]", "[0x12, 0x34]", "", "" }
     widening_impl! { u16, u32, 16, unsigned }
 }
 
 #[lang = "u32"]
 impl u32 {
-    uint_impl! { u32, u32, i32, 32, 4294967295, 8, "0x10000b3", "0xb301", "0x12345678",
+    uint_impl! { u32, u32, i32, NonZeroU32, 32, 4294967295, 8, "0x10000b3", "0xb301", "0x12345678",
     "0x78563412", "0x1e6a2c48", "[0x78, 0x56, 0x34, 0x12]", "[0x12, 0x34, 0x56, 0x78]", "", "" }
     widening_impl! { u32, u64, 32, unsigned }
 }
 
 #[lang = "u64"]
 impl u64 {
-    uint_impl! { u64, u64, i64, 64, 18446744073709551615, 12, "0xaa00000000006e1", "0x6e10aa",
+    uint_impl! { u64, u64, i64, NonZeroU64, 64, 18446744073709551615, 12, "0xaa00000000006e1", "0x6e10aa",
     "0x1234567890123456", "0x5634129078563412", "0x6a2c48091e6a2c48",
     "[0x56, 0x34, 0x12, 0x90, 0x78, 0x56, 0x34, 0x12]",
     "[0x12, 0x34, 0x56, 0x78, 0x90, 0x12, 0x34, 0x56]",
@@ -837,7 +837,7 @@ impl u64 {
 
 #[lang = "u128"]
 impl u128 {
-    uint_impl! { u128, u128, i128, 128, 340282366920938463463374607431768211455, 16,
+    uint_impl! { u128, u128, i128, NonZeroU128, 128, 340282366920938463463374607431768211455, 16,
     "0x13f40000000000000000000000004f76", "0x4f7613f4", "0x12345678901234567890123456789012",
     "0x12907856341290785634129078563412", "0x48091e6a2c48091e6a2c48091e6a2c48",
     "[0x12, 0x90, 0x78, 0x56, 0x34, 0x12, 0x90, 0x78, \
@@ -850,7 +850,7 @@ impl u128 {
 #[cfg(target_pointer_width = "16")]
 #[lang = "usize"]
 impl usize {
-    uint_impl! { usize, u16, isize, 16, 65535, 4, "0xa003", "0x3a", "0x1234", "0x3412", "0x2c48",
+    uint_impl! { usize, u16, isize, NonZeroUsize, 16, 65535, 4, "0xa003", "0x3a", "0x1234", "0x3412", "0x2c48",
     "[0x34, 0x12]", "[0x12, 0x34]",
     usize_isize_to_xe_bytes_doc!(), usize_isize_from_xe_bytes_doc!() }
     widening_impl! { usize, u32, 16, unsigned }
@@ -858,7 +858,7 @@ impl usize {
 #[cfg(target_pointer_width = "32")]
 #[lang = "usize"]
 impl usize {
-    uint_impl! { usize, u32, isize, 32, 4294967295, 8, "0x10000b3", "0xb301", "0x12345678",
+    uint_impl! { usize, u32, isize, NonZeroUsize, 32, 4294967295, 8, "0x10000b3", "0xb301", "0x12345678",
     "0x78563412", "0x1e6a2c48", "[0x78, 0x56, 0x34, 0x12]", "[0x12, 0x34, 0x56, 0x78]",
     usize_isize_to_xe_bytes_doc!(), usize_isize_from_xe_bytes_doc!() }
     widening_impl! { usize, u64, 32, unsigned }
@@ -867,7 +867,7 @@ impl usize {
 #[cfg(target_pointer_width = "64")]
 #[lang = "usize"]
 impl usize {
-    uint_impl! { usize, u64, isize, 64, 18446744073709551615, 12, "0xaa00000000006e1", "0x6e10aa",
+    uint_impl! { usize, u64, isize, NonZeroUsize, 64, 18446744073709551615, 12, "0xaa00000000006e1", "0x6e10aa",
     "0x1234567890123456", "0x5634129078563412", "0x6a2c48091e6a2c48",
     "[0x56, 0x34, 0x12, 0x90, 0x78, 0x56, 0x34, 0x12]",
     "[0x12, 0x34, 0x56, 0x78, 0x90, 0x12, 0x34, 0x56]",
diff --git a/library/core/src/num/nonzero.rs b/library/core/src/num/nonzero.rs
index 8f895c33a63..e21ae489179 100644
--- a/library/core/src/num/nonzero.rs
+++ b/library/core/src/num/nonzero.rs
@@ -302,7 +302,7 @@ nonzero_integers_div! {
 
 // A bunch of methods for unsigned nonzero types only.
 macro_rules! nonzero_unsigned_operations {
-    ( $( $Ty: ident($Int: ty); )+ ) => {
+    ( $( $Ty: ident($Int: ident); )+ ) => {
         $(
             impl $Ty {
                 /// Add an unsigned integer to a non-zero value.
@@ -442,6 +442,56 @@ macro_rules! nonzero_unsigned_operations {
                         None
                     }
                 }
+
+                /// Returns the base 2 logarithm of the number, rounded down.
+                ///
+                /// This is the same operation as
+                #[doc = concat!("[`", stringify!($Int), "::log2`],")]
+                /// except that it has no failure cases to worry about
+                /// since this value can never be zero.
+                ///
+                /// # Examples
+                ///
+                /// ```
+                /// #![feature(int_log)]
+                #[doc = concat!("# use std::num::", stringify!($Ty), ";")]
+                ///
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(7).unwrap().log2(), 2);")]
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(8).unwrap().log2(), 3);")]
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(9).unwrap().log2(), 3);")]
+                /// ```
+                #[unstable(feature = "int_log", issue = "70887")]
+                #[must_use = "this returns the result of the operation, \
+                              without modifying the original"]
+                #[inline]
+                pub const fn log2(self) -> u32 {
+                    <$Int>::BITS - 1 - self.leading_zeros()
+                }
+
+                /// Returns the base 10 logarithm of the number, rounded down.
+                ///
+                /// This is the same operation as
+                #[doc = concat!("[`", stringify!($Int), "::log10`],")]
+                /// except that it has no failure cases to worry about
+                /// since this value can never be zero.
+                ///
+                /// # Examples
+                ///
+                /// ```
+                /// #![feature(int_log)]
+                #[doc = concat!("# use std::num::", stringify!($Ty), ";")]
+                ///
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(99).unwrap().log10(), 1);")]
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(100).unwrap().log10(), 2);")]
+                #[doc = concat!("assert_eq!(", stringify!($Ty), "::new(101).unwrap().log10(), 2);")]
+                /// ```
+                #[unstable(feature = "int_log", issue = "70887")]
+                #[must_use = "this returns the result of the operation, \
+                              without modifying the original"]
+                #[inline]
+                pub const fn log10(self) -> u32 {
+                    super::int_log10::$Int(self.0)
+                }
             }
         )+
     }
diff --git a/library/core/src/num/uint_macros.rs b/library/core/src/num/uint_macros.rs
index 1dd8b0a18ab..0bb65497776 100644
--- a/library/core/src/num/uint_macros.rs
+++ b/library/core/src/num/uint_macros.rs
@@ -1,5 +1,6 @@
 macro_rules! uint_impl {
-    ($SelfT:ty, $ActualT:ident, $SignedT:ident, $BITS:expr, $MaxV:expr,
+    ($SelfT:ty, $ActualT:ident, $SignedT:ident, $NonZeroT:ident,
+        $BITS:expr, $MaxV:expr,
         $rot:expr, $rot_op:expr, $rot_result:expr, $swap_op:expr, $swapped:expr,
         $reversed:expr, $le_bytes:expr, $be_bytes:expr,
         $to_xe_bytes_doc:expr, $from_xe_bytes_doc:expr) => {
@@ -839,12 +840,10 @@ macro_rules! uint_impl {
                       without modifying the original"]
         #[inline]
         pub const fn checked_log2(self) -> Option<u32> {
-            if self <= 0 {
-                None
+            if let Some(x) = <$NonZeroT>::new(self) {
+                Some(x.log2())
             } else {
-                // SAFETY: We just checked that this number is positive
-                let log = (Self::BITS - 1) - unsafe { intrinsics::ctlz_nonzero(self) as u32 };
-                Some(log)
+                None
             }
         }
 
@@ -863,7 +862,11 @@ macro_rules! uint_impl {
                       without modifying the original"]
         #[inline]
         pub const fn checked_log10(self) -> Option<u32> {
-            int_log10::$ActualT(self as $ActualT)
+            if let Some(x) = <$NonZeroT>::new(self) {
+                Some(x.log10())
+            } else {
+                None
+            }
         }
 
         /// Checked negation. Computes `-self`, returning `None` unless `self ==