malachite_base/num/conversion/
half.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::basic::unsigneds::PrimitiveUnsigned;
10use crate::num::conversion::traits::{HasHalf, JoinHalves, SplitInHalf, WrappingFrom};
11
12#[inline]
13fn join_halves<T: From<H> + PrimitiveUnsigned, H: PrimitiveUnsigned>(upper: H, lower: H) -> T {
14    (T::from(upper) << H::WIDTH) | T::from(lower)
15}
16
17#[inline]
18fn upper_half<T: PrimitiveUnsigned, H: PrimitiveUnsigned + WrappingFrom<T>>(x: &T) -> H {
19    H::wrapping_from(*x >> H::WIDTH)
20}
21
22macro_rules! impl_half_traits {
23    ($t:ident, $ht: ident) => {
24        impl HasHalf for $t {
25            /// The primitive integer type whose width is half of `Self`'s.
26            type Half = $ht;
27        }
28
29        impl JoinHalves for $t {
30            /// Joins two unsigned integers to form an unsigned integer with twice the width.
31            ///
32            /// Let $W$ be the width of `Self` (the output type).
33            ///
34            /// $f(x, y) = 2^{W/2} x + y$.
35            ///
36            /// # Worst-case complexity
37            /// Constant time and additional memory.
38            ///
39            /// # Examples
40            /// See [here](super::half#join_halves).
41            #[inline]
42            fn join_halves(upper: Self::Half, lower: Self::Half) -> Self {
43                join_halves(upper, lower)
44            }
45        }
46
47        impl SplitInHalf for $t {
48            /// Extracts the lower, or least significant, half of an unsigned integer.
49            ///
50            /// Let $W$ be the width of `Self` (the input type).
51            ///
52            /// $f(n) = m$, where $m < 2^{W/2}$ and $n + 2^{W/2} k = m$ for some $k \in \Z$.
53            ///
54            /// # Worst-case complexity
55            /// Constant time and additional memory.
56            ///
57            /// # Examples
58            /// See [here](super::half#lower_half).
59            #[inline]
60            fn lower_half(&self) -> Self::Half {
61                $ht::wrapping_from(*self)
62            }
63
64            /// Extracts the upper, or most-significant, half of an unsigned integer.
65            ///
66            /// Let $W$ be the width of `Self` (the input type).
67            ///
68            /// $f(n) = \lfloor \frac{n}{2^{W/2}} \rfloor$.
69            ///
70            /// # Worst-case complexity
71            /// Constant time and additional memory.
72            ///
73            /// # Examples
74            /// See [here](super::half#upper_half).
75            #[inline]
76            fn upper_half(&self) -> Self::Half {
77                upper_half(self)
78            }
79        }
80    };
81}
82impl_half_traits!(u16, u8);
83impl_half_traits!(u32, u16);
84impl_half_traits!(u64, u32);
85impl_half_traits!(u128, u64);
86
87#[inline]
88fn wide_lower_half<T: PrimitiveUnsigned>(x: T) -> T {
89    x.mod_power_of_2(T::WIDTH >> 1)
90}
91
92#[inline]
93pub(crate) fn wide_upper_half<T: PrimitiveUnsigned>(x: T) -> T {
94    x >> (T::WIDTH >> 1)
95}
96
97#[inline]
98pub(crate) fn wide_split_in_half<T: PrimitiveUnsigned>(x: T) -> (T, T) {
99    (wide_upper_half(x), wide_lower_half(x))
100}
101
102#[inline]
103pub(crate) fn wide_join_halves<T: PrimitiveUnsigned>(hi: T, lo: T) -> T {
104    (hi << (T::WIDTH >> 1)) | lo
105}
malachite_base/num/conversion/half.rs

malachite_base/num/conversion/
half.rs
