असेंबली में यह 128 बिट पूर्णांक गुणा कैसे काम करता है (x86-64)?

Question

मैं Computer Systems: A Programmer's Perspective पढ़ रहा हूं और होमवर्क यह वर्णन करना था कि यह एल्गोरिदम कैसे काम करता है।

सी समारोह:

void store_prod(__int128 *dest, int64_t x, int64_t y) { 
    *dest = x * (__int128)y; 
} 

विधानसभा:

movq %rdx, %rax 
cqto 
movq %rsi, %rcx 
sarq $63, %rcx 
imulq %rax, %rcx 
imulq %rsi, %rdx 
addq %rdx, %rcx 
mulq %rsi 
addq %rcx, %rdx 
movq %rax, (%rdi) 
movq %rdx, 8(%rdi) 
ret 

मैं नहीं जानता कि क्यों यह करता है: xh * yl + yh * xl = value which we add after unsigned multiplication

Answer 1

क्या जीसीसी कर रहा है संपत्ति है कि गुणा हस्ताक्षर किए the following formula उपयोग किया जा सकता का उपयोग कर रहा है।

(hi,lo) = unsigned(x*y) 
hi -= ((x<0) ? y : 0) + ((y<0) ? x : 0) 

तथ्य इस मामले में के बाद से ऐसा करने के लिए कोई जरूरत नहीं है कि बावजूद x86-64 अनुदेश सेट है एक हस्ताक्षरित 64-बिट * (एक संकार्य साथ imul) 128 बिट अनुदेश के 64-बिट इस फॉर्मूला अन्य मामलों में उपयोगी है। उदाहरण के लिए signed 128-bit multiplication with SSE2/AVX2/AVX512 लागू करने या 256-bit multiplication when the instruction set only does 128-bit multiplication (जैसे x86-64 के साथ) लागू करने के लिए।

जीसीसी थोड़ा अलग है, हालांकि यह फार्मूला लागू किया। हम संकेत बिट लेते हैं और इसे पूरे शब्द का विस्तार करते हैं, तो फोन इस समारोह sign_ext, तो फ़ंक्शन -1 या 0। तो क्या जीसीसी किया है:

hi += sign_ext(x)*y + sign_ext(y)*x 

64-bit शब्दों के लिए छद्म निर्देश में उदाहरण sign_ext(x)*y के लिए

sarq $63, x ; sign_ext(x) 
imulq y, x ; sign_ext(x)*y 

है तो अब आप से पूछना (या पूछने का मतलब):

यह सूत्र सच क्यों है?

एक अच्छा qeustion है यही कारण है कि। मैं भी यह एक ही प्रश्न पूछा और njuffa wrote

@Zboson: यह दो के पूरक पूरक प्रतिनिधित्व से सीधे इस प्रकार है। जैसे 32-बिट पूर्णांक -n और -m को हस्ताक्षर किए गए नंबर x=2**32-n, y=2**32-m के रूप में दर्शाया गया है। यदि आप उनको गुणा करते हैं तो आपके पास x*y = 2**64 - 2**32*n - 2**32*m + n*m है। मध्य शब्द उत्पाद के ऊपरी हिस्से में आवश्यक सुधार दर्शाते हैं। -1 * -1 का उपयोग करके एक साधारण उदाहरण के माध्यम से काम करना बहुत ही निर्देशक साबित होना चाहिए।

Answer 2

हमेशा की तरह, संकलक विकल्पों बात। gcc -Og (डीबगिंग के लिए ऑप्टिमाइज़) के साथ वह स्रोत कोड produces very similar asm to your listing (कास्ट साइन-पूर्ण 128x128-> 128 गुणा करने से पहले दोनों ऑपरेटरों को 128 बिट तक बढ़ाता है)। यह वही है जो सी मानक कहता है (पूर्णांक पदोन्नति) होना चाहिए। यदि आप कंपाइलर आउटपुट के बारे में बात करने जा रहे हैं, तो आपको हमेशा यह कहना चाहिए कि कौन सा संस्करण किस संकलक के साथ संकलक है। या बस ऊपर दिए गए की तरह godbolt पर एक लिंक पोस्ट करें।

(संपादित करें:। उफ़, स्रोत और एएसएम एक किताब है कि जानकारी नहीं दी से थे)

gcc -O3 के साथ, जीसीसी तथ्य यह है कि दोनों ऑपरेंड अभी भी वास्तव में केवल 64 बिट कर रहे हैं, so a single imul is enough का लाभ लेता है।

---

sar $63, %rcx, साइन-विस्तार rcx:rsi में rsi का हिस्सा है जैसे cqto साइन-फैली rdx:rax में rax।

---

इस जवाब से अधिकांश पहले से टिप्पणी में अन्य लोगों द्वारा दिया गया था, लेकिन मुझे नहीं लगता कि किसी और को देखा है कि gcc -Og/-O1 लगभग ठीक है कि एएसएम उत्पादन देता है।

Answer 3

यह समझने के लिए कारण है कि हम इस आपरेशन करते हैं, int128_t के रूप में व्याख्या करने की कोशिश में: 2^64 * xh + xl

इसलिए यदि हम दो int128_t पूर्णांक गुणा करने के लिए चाहते हैं, तो हम क्या करेंगे निम्नलिखित:

एक्स = 2^64 * xh + xl

y = 2^64 * yh + yl

इतना x * y = (2^128 * xh * yh) + (2^64 * xh * yl) + (2^64 * yh * xl) + (yl * xl)

और यह ठीक है, क्या विधानसभा कोड है:

yh =% RDX yl =% Rax

xh =% RCX एक्स्ट्रा लार्ज =% RSI

2^64 * xh * yl: imulq %rax, %rcx है 2^64 इंगित करता है, कि हम उच्च आदेश को यह जोड़ने की जरूरत बिट्स

2^64 * yh * xl: है imulq %rsi, %rdx 2^64 इंगित करता है, कि हम उच्च आदेश बिट्स को यह जोड़ने की जरूरत है

2^128 * xh * yh: इस ऑपरेशन की आवश्यकता नहीं है, पाप सीई 2^128 * xh * yh 128 बिट पूर्णांक में फिट नहीं होगा।यह केवल साइन बिट जानकारी का प्रतिनिधित्व करता है और इसे अनदेखा किया जा सकता है।

xl * yl: mulq %rsi

है मुझे आशा है कि यह चीजों को साफ करता है!