malachite_base/num/arithmetic/
xx_add_yy_to_zz.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// Uses code adopted from the GNU MP Library.
4//
5//      Copyright © 1991-1994, 1996, 1997, 1999-2005, 2007-2009, 2011-2020 Free Software
6//      Foundation, Inc.
7//
8// This file is part of Malachite.
9//
10// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
11// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
12// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
13
14use crate::num::arithmetic::traits::XXAddYYToZZ;
15use crate::num::basic::integers::USIZE_IS_U32;
16use crate::num::basic::unsigneds::PrimitiveUnsigned;
17use crate::num::conversion::traits::{JoinHalves, SplitInHalf, WrappingFrom};
18
19fn implicit_xx_add_yy_to_zz<DT: JoinHalves + PrimitiveUnsigned + SplitInHalf>(
20    x_1: DT::Half,
21    x_0: DT::Half,
22    y_1: DT::Half,
23    y_0: DT::Half,
24) -> (DT::Half, DT::Half) {
25    DT::join_halves(x_1, x_0)
26        .wrapping_add(DT::join_halves(y_1, y_0))
27        .split_in_half()
28}
29
30pub_test! {
31explicit_xx_add_yy_to_zz<T: PrimitiveUnsigned>(x_1: T, x_0: T, y_1: T, y_0: T) -> (T, T) {
32    let (z_0, carry) = x_0.overflowing_add(y_0);
33    let mut z_1 = x_1.wrapping_add(y_1);
34    if carry {
35        z_1.wrapping_add_assign(T::ONE);
36    }
37    (z_1, z_0)
38}}
39
40macro_rules! implicit_xx_add_yy_to_zz {
41    ($t:ident, $dt:ident) => {
42        impl XXAddYYToZZ for $t {
43            /// Adds two numbers, each composed of two `Self` values, returning the sum as a pair of
44            /// `Self` values.
45            ///
46            /// The more significant value always comes first. Addition is wrapping, and overflow is
47            /// not indicated.
48            ///
49            /// $$
50            /// f(x_1, x_0, y_1, y_0) = (z_1, z_0),
51            /// $$
52            /// where $W$ is `Self::WIDTH`,
53            ///
54            /// $x_1, x_0, y_1, y_0, z_1, z_0 < 2^W$, and
55            /// $$
56            /// (2^Wx_1 + x_0) + (2^Wy_1 + y_0) \equiv 2^Wz_1 + z_0 \mod 2^{2W}.
57            /// $$
58            ///
59            /// # Worst-case complexity
60            /// Constant time and additional memory.
61            ///
62            /// # Examples
63            /// See [here](super::xx_add_yy_to_zz#xx_add_yy_to_zz).
64            ///
65            /// This is equivalent to `add_ssaaaa` from `longlong.h`, GMP 6.2.1, where `(sh, sl)` is
66            /// returned.
67            #[inline]
68            fn xx_add_yy_to_zz(x_1: $t, x_0: $t, y_1: $t, y_0: $t) -> ($t, $t) {
69                implicit_xx_add_yy_to_zz::<$dt>(x_1, x_0, y_1, y_0)
70            }
71        }
72    };
73}
74
75implicit_xx_add_yy_to_zz!(u8, u16);
76implicit_xx_add_yy_to_zz!(u16, u32);
77implicit_xx_add_yy_to_zz!(u32, u64);
78implicit_xx_add_yy_to_zz!(u64, u128);
79
80impl XXAddYYToZZ for usize {
81    /// Adds two numbers, each composed of two [`usize`] values, returning the sum as a pair of
82    /// `usize` values.
83    ///
84    /// The more significant value always comes first. Addition is wrapping, and overflow is not
85    /// indicated.
86    ///
87    /// $$
88    /// f(x_1, x_0, y_1, y_0) = (z_1, z_0),
89    /// $$
90    /// where $W$ is `Self::WIDTH`,
91    ///
92    /// $x_1, x_0, y_1, y_0, z_1, z_0 < 2^W$, and
93    /// $$
94    /// (2^Wx_1 + x_0) + (2^Wy_1 + y_0) \equiv 2^Wz_1 + z_0 \mod 2^{2W}.
95    /// $$
96    ///
97    /// # Worst-case complexity
98    /// Constant time and additional memory.
99    ///
100    /// # Examples
101    /// See [here](super::xx_add_yy_to_zz#xx_add_yy_to_zz).
102    ///
103    /// This is equivalent to `add_ssaaaa` from `longlong.h`, GMP 6.2.1, where `(sh, sl)` is
104    /// returned.
105    fn xx_add_yy_to_zz(x_1: usize, x_0: usize, y_1: usize, y_0: usize) -> (usize, usize) {
106        if USIZE_IS_U32 {
107            let (z_1, z_0) = u32::xx_add_yy_to_zz(
108                u32::wrapping_from(x_1),
109                u32::wrapping_from(x_0),
110                u32::wrapping_from(y_1),
111                u32::wrapping_from(y_0),
112            );
113            (usize::wrapping_from(z_1), usize::wrapping_from(z_0))
114        } else {
115            let (z_1, z_0) = u64::xx_add_yy_to_zz(
116                u64::wrapping_from(x_1),
117                u64::wrapping_from(x_0),
118                u64::wrapping_from(y_1),
119                u64::wrapping_from(y_0),
120            );
121            (usize::wrapping_from(z_1), usize::wrapping_from(z_0))
122        }
123    }
124}
125
126impl XXAddYYToZZ for u128 {
127    /// Adds two numbers, each composed of two [`u128`] values, returning the sum as a pair of
128    /// [`u128`] values.
129    ///
130    /// The more significant value always comes first. Addition is wrapping, and overflow is not
131    /// indicated.
132    ///
133    /// $$
134    /// f(x_1, x_0, y_1, y_0) = (z_1, z_0),
135    /// $$
136    /// where $W$ is `Self::WIDTH`,
137    ///
138    /// $x_1, x_0, y_1, y_0, z_1, z_0 < 2^W$, and
139    /// $$
140    /// (2^Wx_1 + x_0) + (2^Wy_1 + y_0) \equiv 2^Wz_1 + z_0 \mod 2^{2W}.
141    /// $$
142    ///
143    /// # Worst-case complexity
144    /// Constant time and additional memory.
145    ///
146    /// # Examples
147    /// See [here](super::xx_add_yy_to_zz#xx_add_yy_to_zz).
148    ///
149    /// This is equivalent to `add_ssaaaa` from `longlong.h`, GMP 6.2.1, where `(sh, sl)` is
150    /// returned.
151    #[inline]
152    fn xx_add_yy_to_zz(x_1: u128, x_0: u128, y_1: u128, y_0: u128) -> (u128, u128) {
153        explicit_xx_add_yy_to_zz(x_1, x_0, y_1, y_0)
154    }
155}
malachite_base/num/arithmetic/xx_add_yy_to_zz.rs

malachite_base/num/arithmetic/
xx_add_yy_to_zz.rs
