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

/// Creates a function used by some division algorithms to compute the "normalization shift".
#[macro_export]
macro_rules! impl_normalization_shift {
    (
        $name:ident, // name of the normalization shift function
        // boolean for if `$uX::leading_zeros` should be used (if an architecture does not have a
        // hardware instruction for `usize::leading_zeros`, then this should be `true`)
        $use_lz:ident,
        $n:tt, // the number of bits in a $iX or $uX
        $uX:ident, // unsigned integer type for the inputs of `$name`
        $iX:ident, // signed integer type for the inputs of `$name`
        $($unsigned_attr:meta),* // attributes for the function
    ) => {
        /// Finds the shift left that the divisor `div` would need to be normalized for a binary
        /// long division step with the dividend `duo`. NOTE: This function assumes that these edge
        /// cases have been handled before reaching it:
        /// `
        /// if div == 0 {
        ///     panic!("attempt to divide by zero")
        /// }
        /// if duo < div {
        ///     return (0, duo)
        /// }
        /// `
        ///
        /// Normalization is defined as (where `shl` is the output of this function):
        /// `
        /// if duo.leading_zeros() != (div << shl).leading_zeros() {
        ///     // If the most significant bits of `duo` and `div << shl` are not in the same place,
        ///     // then `div << shl` has one more leading zero than `duo`.
        ///     assert_eq!(duo.leading_zeros() + 1, (div << shl).leading_zeros());
        ///     // Also, `2*(div << shl)` is not more than `duo` (otherwise the first division step
        ///     // would not be able to clear the msb of `duo`)
        ///     assert!(duo < (div << (shl + 1)));
        /// }
        /// if full_normalization {
        ///     // Some algorithms do not need "full" normalization, which means that `duo` is
        ///     // larger than `div << shl` when the most significant bits are aligned.
        ///     assert!((div << shl) <= duo);
        /// }
        /// `
        ///
        /// Note: If the software bisection algorithm is being used in this function, it happens
        /// that full normalization always occurs, so be careful that new algorithms are not
        /// invisibly depending on this invariant when `full_normalization` is set to `false`.
        $(
            #[$unsigned_attr]
        )*
        fn $name(duo: $uX, div: $uX, full_normalization: bool) -> usize {
            // We have to find the leading zeros of `div` to know where its msb (most significant
            // set bit) is to even begin binary long division. It is also good to know where the msb
            // of `duo` is so that useful work can be started instead of shifting `div` for all
            // possible quotients (many division steps are wasted if `duo.leading_zeros()` is large
            // and `div` starts out being shifted all the way to the msb). Aligning the msbs of
            // `div` and `duo` could be done by shifting `div` left by
            // `div.leading_zeros() - duo.leading_zeros()`, but some CPUs without division hardware
            // also do not have single instructions for calculating `leading_zeros`. Instead of
            // software doing two bisections to find the two `leading_zeros`, we do one bisection to
            // find `div.leading_zeros() - duo.leading_zeros()` without actually knowing either of
            // the leading zeros values.

            let mut shl: usize;
            if $use_lz {
                shl = (div.leading_zeros() - duo.leading_zeros()) as usize;
                if full_normalization {
                    if duo < (div << shl) {
                        // when the msb of `duo` and `div` are aligned, the resulting `div` may be
                        // larger than `duo`, so we decrease the shift by 1.
                        shl -= 1;
                    }
                }
            } else {
                let mut test = duo;
                shl = 0usize;
                let mut lvl = $n >> 1;
                loop {
                    let tmp = test >> lvl;
                    // It happens that a final `duo < (div << shl)` check is not needed, because the
                    // `div <= tmp` check insures that the msb of `test` never passes the msb of
                    // `div`, and any set bits shifted off the end of `test` would still keep
                    // `div <= tmp` true.
                    if div <= tmp {
                        test = tmp;
                        shl += lvl;
                    }
                    // narrow down bisection
                    lvl >>= 1;
                    if lvl == 0 {
                        break
                    }
                }
            }
            // tests the invariants that should hold before beginning binary long division
            /*
            if full_normalization {
                assert!((div << shl) <= duo);
            }
            if duo.leading_zeros() != (div << shl).leading_zeros() {
                assert_eq!(duo.leading_zeros() + 1, (div << shl).leading_zeros());
                assert!(duo < (div << (shl + 1)));
            }
            */
            shl
        }
    }
}