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

use num::basic::unsigneds::PrimitiveUnsigned;
use num::conversion::traits::{HasHalf, JoinHalves, SplitInHalf, WrappingFrom};

#[inline]
fn join_halves<T: From<H> + PrimitiveUnsigned, H: PrimitiveUnsigned>(upper: H, lower: H) -> T {
    T::from(upper) << H::WIDTH | T::from(lower)
}

#[inline]
fn upper_half<T: PrimitiveUnsigned, H: PrimitiveUnsigned + WrappingFrom<T>>(x: &T) -> H {
    H::wrapping_from(*x >> H::WIDTH)
}

macro_rules! impl_half_traits {
    ($t:ident, $ht: ident) => {
        impl HasHalf for $t {
            /// The primitive integer type whose width is half of `Self`'s.
            type Half = $ht;
        }

        impl JoinHalves for $t {
            /// Joins two unsigned integers to form an unsigned integer with twice the width.
            ///
            /// Let $W$ be the width of `Self` (the output type).
            ///
            /// $f(x, y) = 2^{W/2} x + y$.
            ///
            /// # Worst-case complexity
            /// Constant time and additional memory.
            ///
            /// # Examples
            /// See [here](super::half#join_halves).
            #[inline]
            fn join_halves(upper: Self::Half, lower: Self::Half) -> Self {
                join_halves(upper, lower)
            }
        }

        impl SplitInHalf for $t {
            /// Extracts the lower, or least significant, half of an unsigned integer.
            ///
            /// Let $W$ be the width of `Self` (the input type).
            ///
            /// $f(n) = m$, where $m < 2^{W/2}$ and $n + 2^{W/2} k = m$ for some $k \in \Z$.
            ///
            /// # Worst-case complexity
            /// Constant time and additional memory.
            ///
            /// # Examples
            /// See [here](super::half#lower_half).
            #[inline]
            fn lower_half(&self) -> Self::Half {
                $ht::wrapping_from(*self)
            }

            /// Extracts the upper, or most-significant, half of an unsigned integer.
            ///
            /// Let $W$ be the width of `Self` (the input type).
            ///
            /// $f(n) = \lfloor \frac{n}{2^{W/2}} \rfloor$.
            ///
            /// # Worst-case complexity
            /// Constant time and additional memory.
            ///
            /// # Examples
            /// See [here](super::half#upper_half).
            #[inline]
            fn upper_half(&self) -> Self::Half {
                upper_half(self)
            }
        }
    };
}
impl_half_traits!(u16, u8);
impl_half_traits!(u32, u16);
impl_half_traits!(u64, u32);
impl_half_traits!(u128, u64);

#[inline]
fn wide_lower_half<T: PrimitiveUnsigned>(x: T) -> T {
    x.mod_power_of_2(T::WIDTH >> 1)
}

#[inline]
pub(crate) fn wide_upper_half<T: PrimitiveUnsigned>(x: T) -> T {
    x >> (T::WIDTH >> 1)
}

#[inline]
pub(crate) fn wide_split_in_half<T: PrimitiveUnsigned>(x: T) -> (T, T) {
    (wide_upper_half(x), wide_lower_half(x))
}

#[inline]
pub(crate) fn wide_join_halves<T: PrimitiveUnsigned>(hi: T, lo: T) -> T {
    (hi << (T::WIDTH >> 1)) | lo
}