x86上128位二进制乘法最快速算法征解

gxqcn

函数 UInt128x128To256_SSE2_11F() 代码如下（登陆bbs才可见）：

游客，本帖隐藏的内容需要积分高于 2 才可浏览，您当前积分为 0

无心人

总指令数肯定过200的
呵呵
稍微写差点就差好多时钟

gxqcn

我心中已经形成了一个较好的方案，是 SSE2 版本的，等调好后再发给大家测试测试。。。
在 6# 的压缩包中我给出了一个ANSI C版的函数，应该是很高效的了，谁可以再来突破？

大家在发代码之前务必进行一些自测，尤其是算法正确性方面的测试，可对比我给的那版标准C写的函数的结果进行必要的验证。

无心人

我也想到一个
但太复杂
刚才倒来倒去
终于倒乱了
等会重来

无心人

//全部16个乘法， 49条指令
//明天再研究加法
mov esi, left
mov edi, right
mov ebx, result
xor xmm0, xmm0
movd xmm0, [esi]
movq mm0, mm0
xor xmm1, xmm1
movd xmm1, [edi]
movq mm1, xmm1
xor xmm2, xmm2
movd xmm2, [esi+4]
movq mm2, xmm2
xor xmm3, xmm3
movd xmm3, [edi+4]
movq mm3, xmm3
xor xmm4, xmm4
movd xmm4, [esi+8]
movq mm4, xmm4
xor xmm5, xmm5
movd xmm5, [edi+8]
movq mm5, xmm5
xor xmm6, xmm6
movd xmm6, [esi+12]
movq mm6, xmm6
xor xmm7, xmm7
movd xmm7, [edi+12]
movq mm7, xmm7
// mm0:2:4:6=l:0:1:2:3
// mm1:3:5:7=r:0:1:2:3
//xmm0:2:4:6=l:0:1:2:3
//xmm1:3:5:7=r:0:1:2:3
pmuludq mm0, xmm1 //mm0=0:0
movd eax, mm3
pmuludq mm2, xmm3 //mm2=1:1
movd edx, mm6
pmuludq mm4, xmm5 //mm4=2:2
pmuludq mm6, xmm7 //mm6=3:3
pmuludq mm1, xmm2 //mm1=1:0
pmuludq mm3, xmm0 //mm3=0:1
pmuludq mm5, xmm0 //mm5=0:2
pmuludq mm7, xmm2 //mm7=3:0
pmuludq xmm0, xmm7 //xmm0=0:3
pmuludq xmm2, xmm5 //xmm2=1:2
pmuludq xmm1, xmm4 //xmm1=2:0
pmuludq xmm3, xmm4 //xmm3=2:1
pmuludq xmm4, xmm7 //xmm4=2:3
pmuludq xmm6, xmm5 //xmm6=3:2
//xmm5=r2
//xmm7=r3
movd xmm5, [esi+4]
pmuludq xmm5, xmm7 //xmm5=1:3
mul edx
movd xmm7, edx
pshlq xmm7, 32
movd xmm7, eax //xmm7=3:1

无心人

//一次计算出16个乘法
//全SSE2版本， 40条, 15楼宣布作废
//未做优化, 还存在不完美地方和错误
mov esi, left
mov edi, right
mov ebx, result
movd xmm0, [esi]
movdq2q mm0, xmm0
movd xmm1, [edi]
movdq2q mm1, xmm1
movd xmm2, [esi+4]
movdq2q mm2, xmm2
movd xmm3, [edi+4]
movdq2q mm3, xmm3
movd xmm4, [esi+8]
movdq2q mm4, xmm4
movd xmm5, [edi+8]
movdq2q mm5, xmm5
movd xmm6, [esi+12]
movdq2q mm6, xmm6
movd xmm7, [edi+12]
movdq2q mm7, xmm7
// mm0:2:4:6=l:0:1:2:3
// mm1:3:5:7=r:0:1:2:3
//xmm0:2:4:6=l:0:1:2:3
//xmm1:3:5:7=r:0:1:2:3
pmuludq mm0, [edi] //mm0=0:0
pmuludq mm2, [edi+4] //mm2=1:1
pmuludq mm4, [edi+8] //mm4=2:2
pmuludq mm6, [edi+12] //mm6=3:3
pmuludq mm1, [esi+4] //mm1=1:0
pmuludq mm3, [esi] //mm3=0:1
pmuludq mm5, [esi] //mm5=0:2
pmuludq mm7, [esi+3] //mm7=3:0
pmuludq xmm0, xmm7 //xmm0=0:3
pmuludq xmm2, xmm5 //xmm2=1:2
pmuludq xmm1, xmm4 //xmm1=2:0
pmuludq xmm3, xmm4 //xmm3=2:1
pmuludq xmm4, xmm7 //xmm4=2:3
pmuludq xmm6, xmm5 //xmm6=3:2
//xmm5=r2
//xmm7=r3
movd xmm5, [esi+4]
pmuludq xmm5, xmm7 //xmm5=1:3
movq xmm7, [esi+12]
pmuludq xmm7, [edi+4] //xmm7=3:1

无心人

//并行调整1, SSE2, 35条指令, 得到全部16个乘法
//是否可以更精简, 有待考虑, 压缩到28条以下?
mov esi, left
mov edi, right
mov ebx, result
movd xmm0, [esi]
movdq2q mm0, xmm0
pmuludq mm0, [edi] //mm0=0:0
pmuludq xmm0, [edi+12] //xmm0=0:3
movd xmm1, [edi]
movdq2q mm1, xmm1
pmuludq mm1, [esi+4] //mm1=1:0
pmuludq xmm1, [edi] //xmm1=2:0
movd xmm2, [esi+4]
movdq2q mm2, xmm2
pmuludq mm2, [edi+4] //mm2=1:1
pmuludq xmm2, [edi+8] //xmm2=1:2
movd xmm3, [edi+4]
movdq2q mm3, xmm3
pmuludq mm3, [esi] //mm3=0:1
pmuludq xmm3, [esi+8] //xmm3=2:1
movd xmm4, [esi+8]
movdq2q mm4, xmm4
pmuludq mm4, [edi+8] //mm4=2:2
pmuludq xmm4, [edi+12] //xmm4=2:3
movd mm5, [edi+8]
pmuludq mm5, [esi] //mm5=0:2
movd xmm5, [esi+4]
pmuludq xmm5, [edi+12] //xmm5=1:3
movd xmm6, [esi+12]
movdq2q mm6, xmm6
pmuludq mm6, [edi+12] //mm6=3:3
pmuludq xmm6, [edi+8] //xmm6=3:2
movd mm7, [edi+12]
pmuludq mm7, [esi+12] //mm7=3:0
movd xmm7, [esi+12]
pmuludq xmm7, [edi+4] //xmm7=3:1

liangbch

PMULUDQ 一次可以计算 2个 32bit * 32bit, 理论上，如果用PMULUDQ计算乘法，最少只需8次。楼上却用了16次PMULUDQ，远远没有发挥 SSE2指令的优势。

无心人

然后陷于解开包装的麻烦里?
等搞清混乱的顺序再考虑那个吧

这16个乘就够麻烦算加法的

无心人

而且, 我仔细查了SSE2指令
并无直接包装两个32位整数到0:31/64:95的
需要自己写多指令
并不能抵消少写乘法的开销

你自己写下看看?

我想到的法子现在暂时没心情写
因为可能不能达到最理想方式
即一次两个