1// TODO: when `unsafe_block_in_unsafe_fn` is stabilized, remove this
2#![allow(unused_unsafe)]
3// The functions are complex with many branches, and explicit
4// `return`s makes it clear where function exit points are
5#![allow(clippy::needless_return)]
6#![allow(clippy::comparison_chain)]
7// Clippy is confused by the complex configuration
8#![allow(clippy::if_same_then_else)]
9#![allow(clippy::needless_bool)]
10
11//! This `specialized_div_rem` module is originally from version 1.0.0 of the
12//! `specialized-div-rem` crate. Note that `for` loops with ranges are not used in this
13//! module, since unoptimized compilation may generate references to `memcpy`.
14//!
15//! The purpose of these macros is to easily change the both the division algorithm used
16//! for a given integer size and the half division used by that algorithm. The way
17//! functions call each other is also constructed such that linkers will find the chain of
18//! software and hardware divisions needed for every size of signed and unsigned division.
19//! For example, most target compilations do the following:
20//!
21//! - Many 128 bit division functions like `u128::wrapping_div` use
22//! `std::intrinsics::unchecked_div`, which gets replaced by `__udivti3` because there
23//! is not a 128 bit by 128 bit hardware division function in most architectures.
24//! `__udivti3` uses `u128_div_rem` (this extra level of function calls exists because
25//! `__umodti3` and `__udivmodti4` also exist, and `specialized_div_rem` supplies just
26//! one function to calculate both the quotient and remainder. If configuration flags
27//! enable it, `impl_trifecta!` defines `u128_div_rem` to use the trifecta algorithm,
28//! which requires the half sized division `u64_by_u64_div_rem`. If the architecture
29//! supplies a 64 bit hardware division instruction, `u64_by_u64_div_rem` will be
30//! reduced to those instructions. Note that we do not specify the half size division
31//! directly to be `__udivdi3`, because hardware division would never be introduced.
32//! - If the architecture does not supply a 64 bit hardware division instruction, u64
33//! divisions will use functions such as `__udivdi3`. This will call `u64_div_rem`
34//! which is defined by `impl_delegate!`. The half division for this algorithm is
35//! `u32_by_u32_div_rem` which in turn becomes hardware division instructions or more
36//! software division algorithms.
37//! - If the architecture does not supply a 32 bit hardware instruction, linkers will
38//! look for `__udivsi3`. `impl_binary_long!` is used, but this algorithm uses no half
39//! division, so the chain of calls ends here.
40//!
41//! On some architectures like x86_64, an asymmetrically sized division is supplied, in
42//! which 128 bit numbers can be divided by 64 bit numbers. `impl_asymmetric!` is used to
43//! extend the 128 by 64 bit division to a full 128 by 128 bit division.
44
45// `allow(dead_code)` is used in various places, because the configuration code would otherwise be
46// ridiculously complex
47
48#[macro_use]
49mod norm_shift;
50
51#[macro_use]
52mod binary_long;
53
54#[macro_use]
55mod delegate;
56
57// used on SPARC
58#[allow(unused_imports)]
59#[cfg(not(feature = "public-test-deps"))]
60pub(crate) use self::delegate::u128_divide_sparc;
61
62#[cfg(feature = "public-test-deps")]
63pub use self::delegate::u128_divide_sparc;
64
65#[macro_use]
66mod trifecta;
67
68#[macro_use]
69mod asymmetric;
70
71/// The behavior of all divisions by zero is controlled by this function. This function should be
72/// impossible to reach by Rust users, unless `compiler-builtins` public division functions or
73/// `core/std::unchecked_div/rem` are directly used without a zero check in front.
74fn zero_div_fn() -> ! {
75 // Calling the intrinsic directly, to avoid the `assert_unsafe_precondition` that cannot be used
76 // here because it involves non-`inline` functions
77 // (https://github.com/rust-lang/compiler-builtins/issues/491).
78 unsafe { core::intrinsics::unreachable() }
79}
80
81const USE_LZ: bool = {
82 if cfg!(target_arch = "arm") {
83 if cfg!(target_feature = "thumb-mode") {
84 // ARM thumb targets have CLZ instructions if the instruction set of ARMv6T2 is
85 // supported. This is needed to successfully differentiate between targets like
86 // `thumbv8.base` and `thumbv8.main`.
87 cfg!(target_feature = "v6t2")
88 } else {
89 // Regular ARM targets have CLZ instructions if the ARMv5TE instruction set is
90 // supported. Technically, ARMv5T was the first to have CLZ, but the "v5t" target
91 // feature does not seem to work.
92 cfg!(target_feature = "v5te")
93 }
94 } else if cfg!(any(target_arch = "sparc", target_arch = "sparc64")) {
95 // LZD or LZCNT on SPARC only exists for the VIS 3 extension and later.
96 cfg!(target_feature = "vis3")
97 } else if cfg!(any(target_arch = "riscv32", target_arch = "riscv64")) {
98 // The 'Zbb' Basic Bit-Manipulation extension on RISC-V
99 // determines if a CLZ assembly instruction exists
100 cfg!(target_feature = "zbb")
101 } else {
102 // All other common targets Rust supports should have CLZ instructions
103 true
104 }
105};
106
107impl_normalization_shift!(
108 u32_normalization_shift,
109 USE_LZ,
110 32,
111 u32,
112 i32,
113 allow(dead_code)
114);
115impl_normalization_shift!(
116 u64_normalization_shift,
117 USE_LZ,
118 64,
119 u64,
120 i64,
121 allow(dead_code)
122);
123
124/// Divides `duo` by `div` and returns a tuple of the quotient and the remainder.
125/// `checked_div` and `checked_rem` are used to avoid bringing in panic function
126/// dependencies.
127#[inline]
128fn u64_by_u64_div_rem(duo: u64, div: u64) -> (u64, u64) {
129 if let Some(quo: u64) = duo.checked_div(div) {
130 if let Some(rem: u64) = duo.checked_rem(div) {
131 return (quo, rem);
132 }
133 }
134 zero_div_fn()
135}
136
137// Whether `trifecta` or `delegate` is faster for 128 bit division depends on the speed at which a
138// microarchitecture can multiply and divide. We decide to be optimistic and assume `trifecta` is
139// faster if the target pointer width is at least 64.
140#[cfg(all(
141 not(any(target_pointer_width = "16", target_pointer_width = "32")),
142 not(all(not(feature = "no-asm"), target_arch = "x86_64")),
143 not(any(target_arch = "sparc", target_arch = "sparc64"))
144))]
145impl_trifecta!(
146 u128_div_rem,
147 zero_div_fn,
148 u64_by_u64_div_rem,
149 32,
150 u32,
151 u64,
152 u128
153);
154
155// If the pointer width less than 64, then the target architecture almost certainly does not have
156// the fast 64 to 128 bit widening multiplication needed for `trifecta` to be faster.
157#[cfg(all(
158 any(target_pointer_width = "16", target_pointer_width = "32"),
159 not(all(not(feature = "no-asm"), target_arch = "x86_64")),
160 not(any(target_arch = "sparc", target_arch = "sparc64"))
161))]
162impl_delegate!(
163 u128_div_rem,
164 zero_div_fn,
165 u64_normalization_shift,
166 u64_by_u64_div_rem,
167 32,
168 u32,
169 u64,
170 u128,
171 i128
172);
173
174/// Divides `duo` by `div` and returns a tuple of the quotient and the remainder.
175///
176/// # Safety
177///
178/// If the quotient does not fit in a `u64`, a floating point exception occurs.
179/// If `div == 0`, then a division by zero exception occurs.
180#[cfg(all(not(feature = "no-asm"), target_arch = "x86_64"))]
181#[inline]
182unsafe fn u128_by_u64_div_rem(duo: u128, div: u64) -> (u64, u64) {
183 let duo_lo: u64 = duo as u64;
184 let duo_hi: u64 = (duo >> 64) as u64;
185 let quo: u64;
186 let rem: u64;
187 unsafe {
188 // divides the combined registers rdx:rax (`duo` is split into two 64 bit parts to do this)
189 // by `div`. The quotient is stored in rax and the remainder in rdx.
190 // FIXME: Use the Intel syntax once we drop LLVM 9 support on rust-lang/rust.
191 core::arch::asm!(
192 "div {0}",
193 in(reg) div,
194 inlateout("rax") duo_lo => quo,
195 inlateout("rdx") duo_hi => rem,
196 options(att_syntax, pure, nomem, nostack)
197 );
198 }
199 (quo, rem)
200}
201
202// use `asymmetric` instead of `trifecta` on x86_64
203#[cfg(all(not(feature = "no-asm"), target_arch = "x86_64"))]
204impl_asymmetric!(
205 u128_div_rem,
206 zero_div_fn,
207 u64_by_u64_div_rem,
208 u128_by_u64_div_rem,
209 32,
210 u32,
211 u64,
212 u128
213);
214
215/// Divides `duo` by `div` and returns a tuple of the quotient and the remainder.
216/// `checked_div` and `checked_rem` are used to avoid bringing in panic function
217/// dependencies.
218#[inline]
219#[allow(dead_code)]
220fn u32_by_u32_div_rem(duo: u32, div: u32) -> (u32, u32) {
221 if let Some(quo: u32) = duo.checked_div(div) {
222 if let Some(rem: u32) = duo.checked_rem(div) {
223 return (quo, rem);
224 }
225 }
226 zero_div_fn()
227}
228
229// When not on x86 and the pointer width is not 64, use `delegate` since the division size is larger
230// than register size.
231#[cfg(all(
232 not(all(not(feature = "no-asm"), target_arch = "x86")),
233 not(target_pointer_width = "64")
234))]
235impl_delegate!(
236 u64_div_rem,
237 zero_div_fn,
238 u32_normalization_shift,
239 u32_by_u32_div_rem,
240 16,
241 u16,
242 u32,
243 u64,
244 i64
245);
246
247// When not on x86 and the pointer width is 64, use `binary_long`.
248#[cfg(all(
249 not(all(not(feature = "no-asm"), target_arch = "x86")),
250 target_pointer_width = "64"
251))]
252impl_binary_long!(
253 u64_div_rem,
254 zero_div_fn,
255 u64_normalization_shift,
256 64,
257 u64,
258 i64
259);
260
261/// Divides `duo` by `div` and returns a tuple of the quotient and the remainder.
262///
263/// # Safety
264///
265/// If the quotient does not fit in a `u32`, a floating point exception occurs.
266/// If `div == 0`, then a division by zero exception occurs.
267#[cfg(all(not(feature = "no-asm"), target_arch = "x86"))]
268#[inline]
269unsafe fn u64_by_u32_div_rem(duo: u64, div: u32) -> (u32, u32) {
270 let duo_lo = duo as u32;
271 let duo_hi = (duo >> 32) as u32;
272 let quo: u32;
273 let rem: u32;
274 unsafe {
275 // divides the combined registers rdx:rax (`duo` is split into two 32 bit parts to do this)
276 // by `div`. The quotient is stored in rax and the remainder in rdx.
277 // FIXME: Use the Intel syntax once we drop LLVM 9 support on rust-lang/rust.
278 core::arch::asm!(
279 "div {0}",
280 in(reg) div,
281 inlateout("rax") duo_lo => quo,
282 inlateout("rdx") duo_hi => rem,
283 options(att_syntax, pure, nomem, nostack)
284 );
285 }
286 (quo, rem)
287}
288
289// use `asymmetric` instead of `delegate` on x86
290#[cfg(all(not(feature = "no-asm"), target_arch = "x86"))]
291impl_asymmetric!(
292 u64_div_rem,
293 zero_div_fn,
294 u32_by_u32_div_rem,
295 u64_by_u32_div_rem,
296 16,
297 u16,
298 u32,
299 u64
300);
301
302// 32 bits is the smallest division used by `compiler-builtins`, so we end with binary long division
303impl_binary_long!(
304 u32_div_rem,
305 zero_div_fn,
306 u32_normalization_shift,
307 32,
308 u32,
309 i32,
310 allow(dead_code)
311);
312