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}
107