compiler_builtins/int/specialized_div_rem/
norm_shift.rs

1/// Creates a function used by some division algorithms to compute the "normalization shift".
2#[allow(unused_macros)]
3macro_rules! impl_normalization_shift {
4    (
5        $name:ident, // name of the normalization shift function
6        // boolean for if `$uX::leading_zeros` should be used (if an architecture does not have a
7        // hardware instruction for `usize::leading_zeros`, then this should be `true`)
8        $use_lz:ident,
9        $n:tt, // the number of bits in a $iX or $uX
10        $uX:ident, // unsigned integer type for the inputs of `$name`
11        $iX:ident, // signed integer type for the inputs of `$name`
12        $($unsigned_attr:meta),* // attributes for the function
13    ) => {
14        /// Finds the shift left that the divisor `div` would need to be normalized for a binary
15        /// long division step with the dividend `duo`. NOTE: This function assumes that these edge
16        /// cases have been handled before reaching it:
17        /// `
18        /// if div == 0 {
19        ///     panic!("attempt to divide by zero")
20        /// }
21        /// if duo < div {
22        ///     return (0, duo)
23        /// }
24        /// `
25        ///
26        /// Normalization is defined as (where `shl` is the output of this function):
27        /// `
28        /// if duo.leading_zeros() != (div << shl).leading_zeros() {
29        ///     // If the most significant bits of `duo` and `div << shl` are not in the same place,
30        ///     // then `div << shl` has one more leading zero than `duo`.
31        ///     assert_eq!(duo.leading_zeros() + 1, (div << shl).leading_zeros());
32        ///     // Also, `2*(div << shl)` is not more than `duo` (otherwise the first division step
33        ///     // would not be able to clear the msb of `duo`)
34        ///     assert!(duo < (div << (shl + 1)));
35        /// }
36        /// if full_normalization {
37        ///     // Some algorithms do not need "full" normalization, which means that `duo` is
38        ///     // larger than `div << shl` when the most significant bits are aligned.
39        ///     assert!((div << shl) <= duo);
40        /// }
41        /// `
42        ///
43        /// Note: If the software bisection algorithm is being used in this function, it happens
44        /// that full normalization always occurs, so be careful that new algorithms are not
45        /// invisibly depending on this invariant when `full_normalization` is set to `false`.
46        $(
47            #[$unsigned_attr]
48        )*
49        fn $name(duo: $uX, div: $uX, full_normalization: bool) -> usize {
50            // We have to find the leading zeros of `div` to know where its msb (most significant
51            // set bit) is to even begin binary long division. It is also good to know where the msb
52            // of `duo` is so that useful work can be started instead of shifting `div` for all
53            // possible quotients (many division steps are wasted if `duo.leading_zeros()` is large
54            // and `div` starts out being shifted all the way to the msb). Aligning the msbs of
55            // `div` and `duo` could be done by shifting `div` left by
56            // `div.leading_zeros() - duo.leading_zeros()`, but some CPUs without division hardware
57            // also do not have single instructions for calculating `leading_zeros`. Instead of
58            // software doing two bisections to find the two `leading_zeros`, we do one bisection to
59            // find `div.leading_zeros() - duo.leading_zeros()` without actually knowing either of
60            // the leading zeros values.
61
62            let mut shl: usize;
63            if $use_lz {
64                shl = (div.leading_zeros() - duo.leading_zeros()) as usize;
65                if full_normalization {
66                    if duo < (div << shl) {
67                        // when the msb of `duo` and `div` are aligned, the resulting `div` may be
68                        // larger than `duo`, so we decrease the shift by 1.
69                        shl -= 1;
70                    }
71                }
72            } else {
73                let mut test = duo;
74                shl = 0usize;
75                let mut lvl = $n >> 1;
76                loop {
77                    let tmp = test >> lvl;
78                    // It happens that a final `duo < (div << shl)` check is not needed, because the
79                    // `div <= tmp` check insures that the msb of `test` never passes the msb of
80                    // `div`, and any set bits shifted off the end of `test` would still keep
81                    // `div <= tmp` true.
82                    if div <= tmp {
83                        test = tmp;
84                        shl += lvl;
85                    }
86                    // narrow down bisection
87                    lvl >>= 1;
88                    if lvl == 0 {
89                        break
90                    }
91                }
92            }
93            // tests the invariants that should hold before beginning binary long division
94            /*
95            if full_normalization {
96                assert!((div << shl) <= duo);
97            }
98            if duo.leading_zeros() != (div << shl).leading_zeros() {
99                assert_eq!(duo.leading_zeros() + 1, (div << shl).leading_zeros());
100                assert!(duo < (div << (shl + 1)));
101            }
102            */
103            shl
104        }
105    }
106}
compiler_builtins/int/specialized_div_rem/norm_shift.rs

compiler_builtins/int/specialized_div_rem/
norm_shift.rs
