blob: 0ce31b40a3845b877311ae66ab0a73bf88dc2df1 (
plain)
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
/// These functions compute the integer logarithm of their type, assuming
/// that someone has already checked that 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 <= 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 <= 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 <= 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)
}
#[cfg(target_pointer_width = "16")]
#[inline]
pub const fn usize(val: usize) -> u32 {
u16(val as _)
}
#[cfg(target_pointer_width = "32")]
#[inline]
pub const fn usize(val: usize) -> u32 {
u32(val as _)
}
#[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)
}
// 0 < val <= i16::MAX
#[inline]
pub const fn i16(val: i16) -> u32 {
u16(val as u16)
}
// 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)
}
/// Instantiate this panic logic once, rather than for all the ilog methods
/// on every single primitive type.
#[cold]
#[track_caller]
pub const fn panic_for_nonpositive_argument() -> ! {
panic!("argument of integer logarithm must be positive")
}
|