I am close to solving question 3.59 from Computer Systems: A Programmer's Perspective 3rd Editionby Randal E. Bryant and David R. O'Hallaron, however I am having difficulties with understanding the result.
Question 3.59 asks you to examine a sample of C and x86_64 assembly code that performs a full, signed multiplication of two 64-bit numbers, producing a 128-bit result, and explain how the code is working. The C and assembly is below.
1 #include <stdint.h>
2 typedef __int128 int128_t;
3
4 void store_prod(int128_t *dest, int64_t x, int64_t y) {
5 *dest = x * (int128_t) y;
6 }
# x in %rsi, y in %rdx
1 store_prod:
2 movq %rdx, %rax
3 cqto
4 movq %rsi, %rcx
5 sarq $63, %rcx
6 imulq %rax, %rcx
7 imulq %rsi, %rdx
8 addq %rdx, %rcx
9 mulq %rsi
10 addq %rcx, %rdx
11 movq %rax, (%rdi)
12 movq %rdx, 8(%rdi)
13 ret
The book suggests thinking about the problem by recognizing that when $x$ and $y$ are extended to 128-bits, they can be written as $x = 2^{64}x_{h} + x_{l}$ and $y = 2^{64}y_{h} + y_{l}$, where $x_{h}$, $x_{l}$, $y_{h}$, and $y_{l}$ are 64-bit values.
I see that mathematically
$$ \begin{align*} xy &= (2^{64}x_{h} + x_{l})(2^{64}y_{h} + y_{l}) \\ &= 2^{128}x_{h}y_{h} + 2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}. \end{align*} $$
Since $x_{h}$ and $y_{h}$ are the sign extended parts of $x$ and $y$, we do not care about the $2^{128}x_{h}y_{h}$ term in the final value, so we really only care about $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$, which is how the value is calculated in the assembly code.
My misunderstanding comes about in lines 8 and 10 in the assembly code. Line 8 calculates $x_{h}y_{l} + x_{l}y_{h}$ and line 10 calculates $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$.
My question is why do we not have to worry about overflows when executing the addition instructions on these lines. Even if an overflow occurs, why are the bits of the result correct? Is it because any value resulting from an overflow would en dup going beyond 128-bits, which we then don't care about?