Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers

Question

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?

Answer 1

Your explanations are a bit incorrect. What line 10 does is to add the high 64-bit word of $x_l y_l$ (%rdx after line 9) to $2^{64} (x_h y_l + x_l y_h)$. The low 64-bit word has been computed in line 9 and is in %rax.

Now, all the overflows that have been ignored will affect bit 128 only, i.e. the obtained result can differ from the correct result only by a multiple of $2^{128}$. But since one is interested in the result modulo $2^{128}$, such overflows do not matter.