Suppose you want to multiply two double-word values producing a quad-word result, but your processor supports only single-word multiplication with a double-word result. For concreteness, let’s say that your processor supports 32 \u00d7 32 \u2192 64 multiplication and you want to implement 64 \u00d7 64 \u2192 128 multiplication. (Sound like any processor you know?)<\/p>\n
Oh boy, let’s do some high school algebra. Let’s start with unsigned multiplication.<\/p>\n
Let x<\/var> = A<\/var> \u00d7 2\u00b3\u00b2 + B<\/var> and y<\/var> = C<\/var> \u00d7 2\u00b3\u00b2 + D<\/var>, where A<\/var>, B<\/var>, C<\/var>, and D<\/var> are all in the range 0 \u2026 2\u00b3\u00b2 \u2212 1.<\/p>\n Each of the multiplications (not counting the power-of-two multiplications) is a 32 \u00d7 32 \u2192 64 multiplication, so they are something we have as a building block. And the basic implementation is simply to perform the four multiplications and add the pieces together. But if you have SSE, you can perform two multiplies in a single instruction.<\/p>\n The In two There we go, a 64 \u00d7 64 \u2192 128 multiply constructed from 32 \u00d7 32 \u2192 64 multiplies.<\/p>\n Exercise<\/b>: Why didn’t I use the That calculates an unsigned multiplication, but how do we do a signed multiplication? Let’s work modulo 2128<\/sup> so that signed and unsigned multiplication are equivalent. This means that we need to expand x<\/var> and y<\/var> to 128-bit values X<\/var> and Y<\/var>.<\/p>\n Let s<\/var> = the sign bit of x<\/var> expanded to a 64-bit value, and similarly t<\/var> = the sign bit of y<\/var> expanded to a 64-bit value. In other words, s<\/var> is The 128-bit values being multiplied are<\/p>\n The product is therefore<\/p>\n The first term is zero because it overflows the 128-bit result. That leaves the second term as the adjustment, which simplifies to “If x < 0<\/var> then subtract y<\/var> from the high 64 bits; if y < 0<\/var> then subtract x<\/var> from the high 64 bits.”<\/p>\n If we were still playing with SSE, we could compute this as follows:<\/p>\n The code is a bit strange because SSE2 doesn’t have a full set of 64-bit integer opcodes. We would have liked to have used a Suppose you want to multiply two double-word values producing a quad-word result, but your processor supports only single-word multiplication with a double-word result. For concreteness, let’s say that your processor supports 32 \u00d7 32 \u2192 64 multiplication and you want to implement 64 \u00d7 64 \u2192 128 multiplication. (Sound like any processor you know?) Oh […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-43453","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":" Suppose you want to multiply two double-word values producing a quad-word result, but your processor supports only single-word multiplication with a double-word result. For concreteness, let’s say that your processor supports 32 \u00d7 32 \u2192 64 multiplication and you want to implement 64 \u00d7 64 \u2192 128 multiplication. (Sound like any processor you know?) Oh […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43453","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=43453"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43453\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=43453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=43453"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=43453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n\n
\n x <\/var>\u00d7 y<\/var> =\u00a0<\/td>\n A<\/var>C<\/var> \u00d7 264<\/sup> + (A<\/var>D<\/var> + B<\/var>C<\/var>) \u00d7 232<\/sup> + B<\/var>D<\/var><\/td>\n<\/tr>\n \n =\u00a0<\/td>\n A<\/var>C<\/var> \u00d7 264<\/sup> + B<\/var>D<\/var><\/td>\n \u00a0+\u00a0<\/td>\n (A<\/var>D<\/var> + B<\/var>C<\/var>) \u00d7 232<\/sup><\/td>\n<\/tr>\n \n \u00a0<\/td>\n provisional result<\/td>\n <\/td>\n cross-terms<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \/\/ Prepare our source registers\r\n movq xmm0, x \/\/ xmm0 = { 0, 0, A, B } = { *, *, A, B }\r\n movq xmm1, y \/\/ xmm1 = { 0, 0, C, D } = { *, *, C, D }\r\n punpckldq xmm0, xmm0 \/\/ xmm0 = { A, A, B, B } = { *, A, *, B }\r\n punpckldq xmm1, xmm1 \/\/ xmm1 = { C, C, D, D } = { *, C, *, D }\r\n pshufd xmm2, xmm1, _MM_SHUFFLE(2, 0, 3, 1)\r\n \/\/ xmm2 = { D, D, C, C } = { *, D, *, C }\r\n<\/pre>\nPMULUDQ<\/code> instruction multiplies 32-bit lanes 0 and 2 of its source and destination registers, producing 64-bit results. The values in lanes 1 and 3 do not participate in the multiplication, so it doesn’t matter what we put there. It so happens that the PUNPCKLDQ<\/code> instruction duplicates the value, but we really don’t care. I used *<\/code> to represent a don’t-care value.<\/p>\n pmuludq xmm1, xmm0 \/\/ xmm1 = { AC, BD } \/\/ provisional result\r\n pmuludq xmm2, xmm0 \/\/ xmm2 = { AD, BC } \/\/ cross-terms\r\n<\/pre>\nPMULUDQ<\/code> instructions, we created the provisional result and the cross-terms. Now we just need to add the cross-terms to the provisional result. Unfortunately, SSE does not have a 128-bit addition (or at least SSE2 doesn’t; who knows what they’ll add in the future), so we need to do that the old-fashioned way.<\/p>\n movdqa result, xmm1\r\n movdqa crossterms, xmm2\r\n mov eax, crossterms[0]\r\n mov edx, crossterms[4] \/\/ edx:eax = BC\r\n add result[4], eax\r\n adc result[8], edx\r\n adc result[12], 0 \/\/ add the first cross-term\r\n mov eax, crossterms[8]\r\n mov edx, crossterms[12] \/\/ edx:eax = AD\r\n add result[4], eax\r\n adc result[8], edx\r\n adc result[12], 0 \/\/ add the second cross-term\r\n<\/pre>\n
rax<\/code> register to perform the 64-bit addition? (This is sort of a trick question.)<\/p>\n0xFFFFFFFF`FFFFFFFF<\/code> if x<\/var> < 0 and zero if x<\/var> \u2265 0.<\/p>\n\n\n
\n X<\/var> =\u00a0<\/td>\n s<\/var> \u00d7 264<\/sup> + x<\/var><\/td>\n<\/tr>\n \n Y<\/var> =\u00a0<\/td>\n t<\/var> \u00d7 264<\/sup> + y<\/var><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \n\n
\n X <\/var>\u00d7 Y<\/var> =\u00a0<\/td>\n s<\/var>t<\/var> \u00d7 2128<\/sup>\u00a0<\/td>\n +\u00a0<\/td>\n (s<\/var>y<\/var> + t<\/var>x<\/var>) \u00d7 264<\/sup>\u00a0<\/td>\n \u00a0+\u00a0<\/td>\n x<\/var>y<\/var><\/td>\n<\/tr>\n \n <\/td>\n zero<\/td>\n <\/td>\n adjustment<\/td>\n <\/td>\n unsigned product<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n if (x < 0) result.m128i_u64[1] -= y;\r\n if (y < 0) result.m128i_u64[1] -= x;\r\n<\/pre>\n
movdqa xmm0, result \/\/ xmm0 = { high, low }\r\n movq xmm1, x \/\/ xmm1 = { 0, x }\r\n movq xmm2, y \/\/ xmm2 = { 0, y }\r\n pshufd xmm3, xmm1, _MM_SHUFFLE(1, 1, 3, 2) \/\/ xmm3 = { xhi, xhi, 0, 0 }\r\n pshufd xmm1, xmm1, _MM_SHUFFLE(1, 0, 3, 2) \/\/ xmm1 = { x, 0 }\r\n pshufd xmm4, xmm2, _MM_SHUFFLE(1, 1, 3, 2) \/\/ xmm4 = { yhi, yhi, 0, 0 }\r\n pshufd xmm2, xmm2, _MM_SHUFFLE(1, 0, 3, 2) \/\/ xmm2 = { y, 0 }\r\n psrad xmm3, 31 \/\/ xmm3 = { s, s, 0, 0 } = { s, 0 }\r\n psrad xmm4, 31 \/\/ xmm4 = { t, t, 0, 0 } = { t, 0 }\r\n pand xmm3, xmm2 \/\/ xmm3 = { x < 0 ? y : 0, 0 }\r\n pand xmm4, xmm1 \/\/ xmm4 = { y < 0 ? x : 0, 0 }\r\n psubq xmm0, xmm3 \/\/ first adjustment\r\n psubq xmm0, xmm4 \/\/ second adjustment\r\n movdqa result, xmm0 \/\/ update result\r\n<\/pre>\npsraq<\/code> instruction to fill a 64-bit field with a sign bit. But there is no such instruction, so instead we duplicate the 64-bit sign bit into two 32-bit sign bits (one in lane 2 and one in lane 3) and then fill the lanes with that bit using psrad<\/code>.<\/p>\n","protected":false},"excerpt":{"rendered":"