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的 需要自己写多指令 并不能抵消少写乘法的开销 你自己写下看看? 我想到的法子现在暂时没心情写 因为可能不能达到最理想方式 即一次两个