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