1/// These functions compute the integer logarithm of their type, assuming
2/// that someone has already checked that the value is strictly positive.
3
4// 0 < val <= u8::MAX
5#[inline]
6pub(super) const fn u8(val: u8) -> u32 {
7 let val: u32 = val as u32;
8
9 // For better performance, avoid branches by assembling the solution
10 // in the bits above the low 8 bits.
11
12 // Adding c1 to val gives 10 in the top bits for val < 10, 11 for val >= 10
13 const C1: u32 = 0b11_00000000 - 10; // 758
14 // Adding c2 to val gives 01 in the top bits for val < 100, 10 for val >= 100
15 const C2: u32 = 0b10_00000000 - 100; // 412
16
17 // Value of top bits:
18 // +c1 +c2 1&2
19 // 0..=9 10 01 00 = 0
20 // 10..=99 11 01 01 = 1
21 // 100..=255 11 10 10 = 2
22 ((val + C1) & (val + C2)) >> 8
23}
24
25// 0 < val < 100_000
26#[inline]
27const fn less_than_5(val: u32) -> u32 {
28 // Similar to u8, when adding one of these constants to val,
29 // we get two possible bit patterns above the low 17 bits,
30 // depending on whether val is below or above the threshold.
31 const C1: u32 = 0b011_00000000000000000 - 10; // 393206
32 const C2: u32 = 0b100_00000000000000000 - 100; // 524188
33 const C3: u32 = 0b111_00000000000000000 - 1000; // 916504
34 const C4: u32 = 0b100_00000000000000000 - 10000; // 514288
35
36 // Value of top bits:
37 // +c1 +c2 1&2 +c3 +c4 3&4 ^
38 // 0..=9 010 011 010 110 011 010 000 = 0
39 // 10..=99 011 011 011 110 011 010 001 = 1
40 // 100..=999 011 100 000 110 011 010 010 = 2
41 // 1000..=9999 011 100 000 111 011 011 011 = 3
42 // 10000..=99999 011 100 000 111 100 100 100 = 4
43 (((val + C1) & (val + C2)) ^ ((val + C3) & (val + C4))) >> 17
44}
45
46// 0 < val <= u16::MAX
47#[inline]
48pub(super) const fn u16(val: u16) -> u32 {
49 less_than_5(val as u32)
50}
51
52// 0 < val <= u32::MAX
53#[inline]
54pub(super) const fn u32(mut val: u32) -> u32 {
55 let mut log: u32 = 0;
56 if val >= 100_000 {
57 val /= 100_000;
58 log += 5;
59 }
60 log + less_than_5(val)
61}
62
63// 0 < val <= u64::MAX
64#[inline]
65pub(super) const fn u64(mut val: u64) -> u32 {
66 let mut log: u32 = 0;
67 if val >= 10_000_000_000 {
68 val /= 10_000_000_000;
69 log += 10;
70 }
71 if val >= 100_000 {
72 val /= 100_000;
73 log += 5;
74 }
75 log + less_than_5(val as u32)
76}
77
78// 0 < val <= u128::MAX
79#[inline]
80pub(super) const fn u128(mut val: u128) -> u32 {
81 let mut log: u32 = 0;
82 if val >= 100_000_000_000_000_000_000_000_000_000_000 {
83 val /= 100_000_000_000_000_000_000_000_000_000_000;
84 log += 32;
85 return log + u32(val as u32);
86 }
87 if val >= 10_000_000_000_000_000 {
88 val /= 10_000_000_000_000_000;
89 log += 16;
90 }
91 log + u64(val as u64)
92}
93
94#[cfg(target_pointer_width = "16")]
95#[inline]
96pub(super) const fn usize(val: usize) -> u32 {
97 u16(val as _)
98}
99
100#[cfg(target_pointer_width = "32")]
101#[inline]
102pub(super) const fn usize(val: usize) -> u32 {
103 u32(val as _)
104}
105
106#[cfg(target_pointer_width = "64")]
107#[inline]
108pub(super) const fn usize(val: usize) -> u32 {
109 u64(val as _)
110}
111
112// 0 < val <= i8::MAX
113#[inline]
114pub(super) const fn i8(val: i8) -> u32 {
115 u8(val as u8)
116}
117
118// 0 < val <= i16::MAX
119#[inline]
120pub(super) const fn i16(val: i16) -> u32 {
121 u16(val as u16)
122}
123
124// 0 < val <= i32::MAX
125#[inline]
126pub(super) const fn i32(val: i32) -> u32 {
127 u32(val as u32)
128}
129
130// 0 < val <= i64::MAX
131#[inline]
132pub(super) const fn i64(val: i64) -> u32 {
133 u64(val as u64)
134}
135
136// 0 < val <= i128::MAX
137#[inline]
138pub(super) const fn i128(val: i128) -> u32 {
139 u128(val as u128)
140}
141
142/// Instantiate this panic logic once, rather than for all the ilog methods
143/// on every single primitive type.
144#[cold]
145#[track_caller]
146pub(super) const fn panic_for_nonpositive_argument() -> ! {
147 panic!("argument of integer logarithm must be positive")
148}
149