The following code computes the 128-bit product of two 64-bit signed values x and y and stores the result in memory: 1 typedef --int 128 int128 t 3 void store prod (int128 t *dest, int64 t x, int64_t y) t *dest x (int 128-t) y; Gcc generates the following assembly code implementing the computation: store prod movq %rdx, %rax Cqto movq

The following code computes the 128-bit product of two 64-bit signed values x and y and stores the result in memory: 1 typedef --int 128 int128 t 3 void store prod (int128 t *dest, int64 t x, int64_t y) t *dest x (int 128-t) y; Gcc generates the following assembly code implementing the computation: store prod movq %rdx, %rax Cqto movq. %rsi, r (CX Sara $63, CX imula %rax, %rcx 7 imulq %rsi %rdx %rdx add %rcx %r mulg S1 %rcx, %rdx 10 movq hrax, (%rdi) 11 12 movq %rdx, 8 (%rdi) 13 ret This code uses three multiplications for the muitiprecision arithmetic required to implement 128- bit arithmetic on a 64-bit machine. Describe the algorithm used to compute the product, and annotate the assembly code to show how it realizes your algorithm. Hint When extending arguments ofxand y to 128 bits, they can be rewritten as x 264 x 264 xh +xl and y 264 yh yl, where xin, xi, yh, and yi are 64-bit values. Similarly, the 128-bit product can be written as p 264 ph pl where Ph and pu are 64-bit values. Show how the code computes the values of ph and pl in terms of xh, xi, yh, and yi.