The following code computes the 128-bit product of two 64-bit signed values x an

Question

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.

Explanation / Answer

/* Demonstration of division instructions */ /* $begin 100-umul-c */ #include typedef unsigned __int128 uint128_t; void store_uprod(uint128_t *dest, uint64_t x, uint64_t y) { *dest = x * (uint128_t) y; } /* $end 100-umul-c */ typedef __int128 int128_t; void store_prod(int128_t *dest, int64_t x, int64_t y) { *dest = x * (int128_t) y; } /* $begin 100-remdiv-c */ void remdiv(long x, long y, long *qp, long *rp) { long q = x/y; long r = x%y; *qp = q; *rp = r; } /* $end 100-remdiv-c */ /* $begin 100-uremdiv-c */ void uremdiv(unsigned long x, unsigned long y, unsigned long *qp, unsigned long *rp) { unsigned long q = x/y; unsigned long r = x%y; *qp = q; *rp = r; } /* $end 100-uremdiv-c */

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.