]>
Commit | Line | Data |
---|---|---|
5099ac24 | 1 | /// These functions compute the integer logarithm of their type, assuming |
2b03887a | 2 | /// that someone has already checked that the value is strictly positive. |
5099ac24 FG |
3 | |
4 | // 0 < val <= u8::MAX | |
5 | #[inline] | |
6 | pub const fn u8(val: u8) -> u32 { | |
7 | let val = 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 | } | |
136023e0 | 24 | |
5099ac24 FG |
25 | // 0 < val < 100_000 |
26 | #[inline] | |
27 | const 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 | } | |
136023e0 | 45 | |
5099ac24 FG |
46 | // 0 < val <= u16::MAX |
47 | #[inline] | |
48 | pub const fn u16(val: u16) -> u32 { | |
49 | less_than_5(val as u32) | |
50 | } | |
136023e0 | 51 | |
5099ac24 FG |
52 | // 0 < val <= u32::MAX |
53 | #[inline] | |
54 | pub const fn u32(mut val: u32) -> u32 { | |
55 | let mut log = 0; | |
56 | if val >= 100_000 { | |
57 | val /= 100_000; | |
58 | log += 5; | |
136023e0 | 59 | } |
5099ac24 FG |
60 | log + less_than_5(val) |
61 | } | |
136023e0 | 62 | |
5099ac24 FG |
63 | // 0 < val <= u64::MAX |
64 | #[inline] | |
65 | pub const fn u64(mut val: u64) -> u32 { | |
66 | let mut log = 0; | |
67 | if val >= 10_000_000_000 { | |
68 | val /= 10_000_000_000; | |
69 | log += 10; | |
136023e0 | 70 | } |
5099ac24 FG |
71 | if val >= 100_000 { |
72 | val /= 100_000; | |
73 | log += 5; | |
136023e0 | 74 | } |
5099ac24 FG |
75 | log + less_than_5(val as u32) |
76 | } | |
136023e0 | 77 | |
5099ac24 FG |
78 | // 0 < val <= u128::MAX |
79 | #[inline] | |
80 | pub const fn u128(mut val: u128) -> u32 { | |
81 | let mut log = 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); | |
136023e0 | 86 | } |
5099ac24 FG |
87 | if val >= 10_000_000_000_000_000 { |
88 | val /= 10_000_000_000_000_000; | |
89 | log += 16; | |
136023e0 | 90 | } |
5099ac24 FG |
91 | log + u64(val as u64) |
92 | } | |
136023e0 | 93 | |
5099ac24 FG |
94 | #[cfg(target_pointer_width = "16")] |
95 | #[inline] | |
96 | pub const fn usize(val: usize) -> u32 { | |
97 | u16(val as _) | |
98 | } | |
136023e0 | 99 | |
5099ac24 FG |
100 | #[cfg(target_pointer_width = "32")] |
101 | #[inline] | |
102 | pub const fn usize(val: usize) -> u32 { | |
103 | u32(val as _) | |
104 | } | |
136023e0 | 105 | |
5099ac24 FG |
106 | #[cfg(target_pointer_width = "64")] |
107 | #[inline] | |
108 | pub const fn usize(val: usize) -> u32 { | |
109 | u64(val as _) | |
110 | } | |
111 | ||
112 | // 0 < val <= i8::MAX | |
113 | #[inline] | |
114 | pub const fn i8(val: i8) -> u32 { | |
115 | u8(val as u8) | |
136023e0 XL |
116 | } |
117 | ||
5099ac24 FG |
118 | // 0 < val <= i16::MAX |
119 | #[inline] | |
120 | pub const fn i16(val: i16) -> u32 { | |
121 | u16(val as u16) | |
136023e0 XL |
122 | } |
123 | ||
5099ac24 FG |
124 | // 0 < val <= i32::MAX |
125 | #[inline] | |
126 | pub const fn i32(val: i32) -> u32 { | |
127 | u32(val as u32) | |
128 | } | |
129 | ||
130 | // 0 < val <= i64::MAX | |
131 | #[inline] | |
132 | pub const fn i64(val: i64) -> u32 { | |
133 | u64(val as u64) | |
134 | } | |
135 | ||
136 | // 0 < val <= i128::MAX | |
137 | #[inline] | |
138 | pub const fn i128(val: i128) -> u32 { | |
139 | u128(val as u128) | |
140 | } |