找回密码
 欢迎注册
楼主: 无心人

[擂台] x86上128位二进制乘法最快速算法征解

[复制链接]
 楼主| 发表于 2008-3-18 21:23:55 | 显示全部楼层
上面代码可修改所有的数据重排指令的源到寄存器
可能能节约时间
不过要占两个XMM
刚粗略看了,似乎可抽出XMM5, XMM6缓存left, right
==============
想到另外一种拆解方法
假设xmm0 = 1:0/0:1
movq xmm1, xmm0
pshufd xmm1, xmm1, 11011100b
psrldq mm0, 8
pshufd xmm0, xmm0, 11011100b
paddq xmm0, xmm1
明天测试, 感觉指令安排比原来的好, 运算冲突少, 还能节约个xmm7
另外
GxQ在CSDN上的96bit算法不知道怎么处理的进位?
通篇没有比较和置位处理
或者我没看懂?
恐怕128bit再加就没这么容易了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-19 08:44:18 | 显示全部楼层
我将续写“诡异”算法的传奇,请稍候。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 08:59:51 | 显示全部楼层
64位长加?
我考虑下
不过感觉应该不能达到最优化效果
即比我上面写的SSE2 107条代码做多节约30%时间
你先别发, 等我代码调试好了发上去
你再发,好对比
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 11:46:30 | 显示全部楼层
void UInt128x128To256_SSE2_54F( UINT32 * const result,
                                                           const UINT32 * const left,
                                                           const UINT32 * const right )
{
        //全SSE2版本
        __asm
        {
                /* 具体代码在下一个代码区,需登陆才可见 */
                mov esi, dword ptr [left]
                mov edi, dword ptr [right]
                mov ebx, dword ptr [result]
                movdqu xmm5, [esi]
                movdqu xmm6, [edi]
                pshufd xmm0, xmm5, 11011100b  //2008-03-21 有修改
                pshufd xmm1, xmm6, 11011100b  //2008-03-21 有修改
        pmuludq xmm0, xmm1
                pcmpeqd xmm7, xmm7
        psrlq xmm7, 32 //00000000FFFFFFFF00000000FFFFFFFF
                movd [ebx], xmm0 //0:0结果低位保存
                pshufd xmm1, xmm5, 00010000b
                pshufd xmm2, xmm6, 00000001b
                pmuludq xmm1, xmm2 //xmm1= 1:0/0:1
                movq xmm4, xmm0
        pshufd xmm4, xmm4, 11111101b
                pshufd xmm3, xmm1, 00010000b
                pand xmm3, xmm7
                pshufd xmm2, xmm1, 00110010b
                pand xmm2, xmm7
                paddq xmm2, xmm3 //0:1+1:0=xmm2
                paddq xmm2, xmm4
                psrldq xmm0, 8
//xmm0=1:1
                movd [ebx+4], xmm2
                psrldq xmm2, 4
                pshufd xmm3, xmm2, 11111001b
                pshufd xmm2, xmm2, 11111100b
                paddq xmm2, xmm3
//2:0 0:2
                pshufd xmm4, xmm5, 00100000b
                pshufd xmm3, xmm6, 00000010b
                pmuludq xmm4, xmm3 //xmm4=2:0/0:2
                pshufd xmm3, xmm4, 00010000b
                pand xmm3, xmm7
                pshufd xmm4, xmm4, 00110010b
                pand xmm4, xmm7
                paddq xmm3, xmm4 //xmm3=2:0 + 0:2 xmm0=1:1 xmm2=进位
                pshufd xmm0, xmm0, 11011100b
                paddq xmm3, xmm2
                paddq xmm3, xmm0
                movd [ebx+8], xmm3
                psrldq xmm3, 4
                pshufd xmm0, xmm3, 11111001b
                pshufd xmm3, xmm3, 11111100b
                paddq xmm0, xmm3 //xmm0=进位
//1:2 2:1 3:0 0:3
        pshufd xmm1, xmm5, 00010010b
                pshufd xmm4, xmm6, 00100001b
                pmuludq xmm1, xmm4
                pshufd xmm2, xmm5, 00110000b
                pshufd xmm3, xmm6, 00000011b
                pmuludq xmm2, xmm3 //xmm0进位 xmm1=1:2/2:1 xmm2=3:0/0:3
        pshufd xmm4, xmm1, 00010000b
                pand xmm4, xmm7
                pshufd xmm1, xmm1, 00110010b
                pand xmm1, xmm7
                paddq xmm1, xmm4
                paddq xmm0, xmm1
                pshufd xmm3, xmm2, 00010000b
                pand xmm3, xmm7
                pshufd xmm2, xmm2, 00110010b
                pand xmm2, xmm7
                paddq xmm2, xmm3
                paddq xmm0, xmm2
                movd [ebx+12], xmm0
                psrldq xmm0, 4
                pshufd xmm3, xmm0, 11111001b
                pshufd xmm0, xmm0, 11111100b
                paddq xmm0, xmm3 //xmm0进位
//1:3 2:2 3:1
        pshufd xmm1, xmm5, 00110010b
                pshufd xmm3, xmm6, 00110010b
                pmuludq xmm1, xmm3 //xmm1=3:3/2:2
                pshufd xmm2, xmm5, 00110001b
                pshufd xmm4, xmm6, 00010011b
        pmuludq xmm2, xmm4 //xmm2=3:1/1:3
        movdqa xmm4, xmm1
                psrldq xmm4, 8 //xmm4=3:3
                movq xmm1, xmm1 //xmm1=2:2
                pshufd xmm3, xmm2, 00110010b
                pand xmm3, xmm7
                pshufd xmm2, xmm2, 00010000b
                pand xmm2, xmm7
                paddq xmm2, xmm3
                pshufd xmm1, xmm1, 11011100b
                paddq xmm1, xmm2
                paddq xmm0, xmm1
                movd [ebx+16], xmm0
                psrldq xmm0, 4
                pshufd xmm3, xmm0, 11111001b
                pshufd xmm0, xmm0, 11111100b
                paddq xmm0, xmm3 //xmm0=进位
//2:3 3:2
        pshufd xmm1, xmm5, 00100011b
                pshufd xmm2, xmm6, 00110010b
                pmuludq xmm1, xmm2
                pshufd xmm3, xmm1, 00010000b
        pand xmm3, xmm7
                pshufd xmm1, xmm1, 00110010b
                pand xmm1, xmm7
                paddq xmm1, xmm3
                paddq xmm0, xmm1
                movd [ebx+20], xmm0
                psrldq xmm0, 4
                pshufd xmm2, xmm0, 11111001b
                pshufd xmm0, xmm0, 11111100b
                paddq xmm0, xmm2 //进位
        pshufd xmm4, xmm4, 11011100b
                paddq xmm0, xmm4
                movd [ebx+24], xmm0
                psrldq xmm0, 4
                pshufd xmm1, xmm0, 11111001b
                pshufd xmm0, xmm0, 11111100b
                paddq xmm0, xmm1
                movd [ebx+28], xmm0
        //                ret;
        }
}

//MMX    1 681 885us
//SSE2s  1 841 345us
//SSE2   1 841 528us 
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-19 11:48:01 | 显示全部楼层
111行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-23 21:15:41 | 显示全部楼层

我的“诡异”算法

  1. _declspec(naked)
  2. void UInt128x128To256_SSE2_56F( UINT32 * const result,
  3.                                 const UINT32 * const left,
  4.                                 const UINT32 * const right )
  5. {
  6.     __asm
  7.     {
  8.         mov         ecx, dword ptr[esp + 04h]   ; result
  9.         mov         eax, dword ptr[esp + 08h]   ; left
  10.         mov         edx, dword ptr[esp + 0Ch]   ; right

  11.         movdqa      xmm2, xmmword ptr[eax]      ; load left
  12.         movdqa      xmm0, xmmword ptr[edx]      ; load right

  13.         pshufd      xmm7, xmm2, 11111111b       ; xmm7 = L3:L3:L3:L3
  14.         pshufd      xmm1, xmm0, 11110101b       ; xmm1 = R3:R3:R1:R1
  15.         movdqa      xmm6, xmm7                  ; xmm6 = L3:L3:L3:L3

  16.         pmuludq     xmm7, xmm1                  ; xmm7 = L3*R3:L3*R1 ->V7-4
  17.         pmuludq     xmm6, xmm0                  ; xmm6 = L3*R2:L3*R0 ->V6-3

  18.         movdqa      xmm5, xmm7                  ;
  19.         movdqa      xmm4, xmm6                  ;
  20.         movdqa      xmm3, xmm6                  ;

  21.         pslldq      xmm5, 4                     ; xmm5 <<= 32
  22.         psrldq      xmm4, 4                     ; xmm4 >>= 32
  23.         pslldq      xmm3, 12                    ; L3*R2:L3*R0 ->V3-0

  24.         paddq       xmm6, xmm5                  ; L3*R3:L3*R1 ->V6-3
  25.         paddq       xmm7, xmm4                  ; L3*R2:L3*R0 ->V7-4


  26.         pshufd      xmm5, xmm2, 10101010b       ; xmm5 = L2:L2:L2:L2
  27.         pmuludq     xmm5, xmm1                  ; xmm5 = L2*R3:L2*R1

  28.         paddq       xmm6, xmm5                  ; L2*R3:L2*R1 ->V6-3
  29.         movdqa      xmm4, xmm5                  ;

  30.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  31.         pslldq      xmm4, 12                    ; xmm4 <<= 96

  32.         paddq       xmm7, xmm5                  ; L2*R3:L2*R1 ->V7-4
  33.         paddq       xmm3, xmm4                  ; L2*R3:L2*R1 ->V3-0


  34.         pshufd      xmm5, xmm2, 10101010b       ; xmm5 = L2:L2:L2:L2
  35.         pshufd      xmm4, xmm2, 01010101b       ; xmm4 = L1:L1:L1:L1
  36.         pshufd      xmm2, xmm2, 00000000b       ; xmm2 = L0:L0:L0:L0

  37.         pmuludq     xmm5, xmm0                  ; xmm5 = L2*R2:L2*R0

  38.         movdqa      xmmword ptr[ecx+0x10], xmm4 ; xmm4 = L1:L1:L1:L1
  39.         movdqa      xmmword ptr[ecx+0x00], xmm2 ; xmm2 = L0:L0:L0:L0
  40.         movdqa      xmm2, xmm5                  ; xmm2 = L2*R2:L2*R0

  41.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  42.         pslldq      xmm2, 8                     ; xmm4 <<= 64

  43.         paddq       xmm6, xmm5                  ; L2*R2:L2*R0 ->V6-3
  44.         paddq       xmm3, xmm2                  ; L2*R2:L2*R0 ->V3-0

  45.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  46.         pslldq      xmm2, 4                     ; L2*R2:L2*R0 ->V2-1H

  47.         paddq       xmm7, xmm5                  ; L2*R2:L2*R0 ->V7-4


  48.         movdqa      xmm5, xmmword ptr[ecx+0x10] ; xmm5 = L1:L1:L1:L1
  49.         pmuludq     xmm5, xmm1                  ; xmm5 = L1*R3:L1*R1
  50.         movdqa      xmm4, xmm5                  ;

  51.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  52.         pslldq      xmm4, 8                     ; xmm4 >>= 64

  53.         paddq       xmm6, xmm5                  ; L1*R3:L1*R1 ->V6-3
  54.         paddq       xmm3, xmm4                  ; L1*R3:L1*R1 ->V3-0

  55.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  56.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  57.         paddq       xmm7, xmm5                  ; L1*R3:L1*R1 ->V7-4
  58.         paddq       xmm2, xmm4                  ; L1*R3:L1*R1 ->V2-1H

  59.         movdqa      xmm5, xmmword ptr[ecx+0x10] ; xmm5 = L1:L1:L1:L1
  60.         pmuludq     xmm5, xmm0                  ; xmm5 = L1*R2:L1*R0

  61.         movdqa      xmm4, xmm5                  ;

  62.         psrldq      xmm5, 8                     ; xmm5 >>= 64
  63.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  64.         paddq       xmm6, xmm5                  ; L1*R2:L1*R0 ->V6-3
  65.         paddq       xmm3, xmm4                  ; L1*R2:L1*R0 ->V3-0

  66.         psrldq      xmm5, 4                     ; xmm5 >>= 32
  67.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  68.         paddq       xmm7, xmm5                  ; L1*R2:L1*R0 ->V7-4
  69.         paddq       xmm2, xmm4                  ; L1*R2:L1*R0 ->V2-1H


  70.         movdqa      xmm5, xmmword ptr[ecx+0x00] ; xmm5 = L0:L0:L0:L0
  71.         pmuludq     xmm5, xmm1                  ; xmm5 = L0*R3:L0*R1

  72.         movdqa      xmm4, xmm5                  ;

  73.         psrldq      xmm5, 8                     ; xmm5 >>= 64
  74.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  75.         paddq       xmm6, xmm5                  ; L0*R3:L0*R1 ->V6-3
  76.         paddq       xmm3, xmm4                  ; L0*R3:L0*R1 ->V3-0

  77.         psrldq      xmm5, 4                     ; xmm5 >>= 64
  78.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  79.         paddq       xmm7, xmm5                  ; L0*R3:L0*R1 ->V7-4
  80.         paddq       xmm2, xmm4                  ; L0*R3:L0*R1 ->V2-1H

  81.         movdqa      xmm5, xmmword ptr[ecx+0x00] ; xmm5 = L0:L0:L0:L0
  82.         pmuludq     xmm5, xmm0                  ; xmm5 = L0*R2:L0*R0

  83.         paddq       xmm3, xmm5                  ; L0*R2:L0*R0 ->V3-0
  84.         movdqa      xmm4, xmm5                  ;

  85.         psrldq      xmm5, 12                    ; xmm5 >>= 96
  86.         pslldq      xmm4, 4                     ; xmm4 >>= 32

  87.         paddq       xmm6, xmm5                  ; L0*R2:L0*R0 ->V6-3
  88.         paddq       xmm2, xmm4                  ; L0*R2:L0*R0 ->V2-1H


  89.         ; now, V[1:0]=xmm3[63:0] ->OK
  90.         psrldq      xmm2, 4                     ; xmm2 >>= 32
  91.         movdqa      xmm4, xmm3                  ;
  92.         pcmpeqd     xmm0, xmm0                  ; xmm0 = FF:FF:FF:FF
  93.         pandn       xmm4, xmm2                  ;
  94.         psubd       xmm2, xmm3                  ; xmm2 -= xmm3
  95.         psrldq      xmm0, 12                    ; xmm0 = 00:00:00:FF

  96.         pslldq      xmm4, 4                     ; xmm4 <<= 32
  97.         psrld       xmm4, 31                    ; CF
  98.         pshufd      xmm1, xmm0, 01001110b       ; xmm1 = 00:FF:00:00
  99.         paddd       xmm2, xmm4                  ;
  100.         pand        xmm2, xmm1                  ;
  101.         paddq       xmm3, xmm2                  ; V[3:0]=xmm3 ->OK
  102.         movdqa      xmmword ptr[ecx+0x00], xmm3 ; store V[3:0]


  103.         psrldq      xmm3, 12                    ; xmm3 >>= 96
  104.         psubd       xmm3, xmm6                  ; xmm3 -= xmm6
  105.         pand        xmm3, xmm0                  ;
  106.         paddq       xmm6, xmm3                  ; V[4:3]=xmm6[63:0] ->OK
  107.         pxor        xmm1, xmm0                  ; xmm1 = 00:FF:00:FF
  108.         psrldq      xmm6, 4                     ; V[4]=xmm6[31:0] ->OK


  109.         movdqa      xmm2, xmm6                  ; xmm2 = xmm6
  110.         psubd       xmm6, xmm7                  ; xmm6 -= xmm0
  111.         pand        xmm6, xmm1                  ;
  112.         paddq       xmm7, xmm6                  ; now, xmm7[63-0] bits OK!

  113.         psubusb     xmm2, xmm7                  ;
  114.         psrlq       xmm2, 63                    ; CF
  115.         pslldq      xmm2, 8                     ;
  116.         paddq       xmm7, xmm2                  ; xmm7[127-64] += CF
  117.         movdqa      xmmword ptr[ecx+0x10], xmm7 ; store V[7:4]

  118.         ret;
  119.     }
  120. }
复制代码
SSE2 指令,XMM 寄存器,110行(包含最后那个 ret 指令)。
(费了不少功夫,但效果没有预期的好)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-23 21:22:05 | 显示全部楼层
你算法优势不大了

movdqa                xmm2, xmmword ptr[eax]                ; load        left
  movdqa                xmm0, xmmword ptr[edx]                ; load        right
最好用pshufd代替, 有性能改进的
==============================================================================
就不另外开新回复了
我想在我代码测试里你也看到了
明明SSE2一次乘两个,却和一个乘一个的差不多,更离谱的是和用MMX寄存器的时间差了好多
关键是
1、目前的乘法,SSE2乘一次延迟是5,用MMX一次是3,这个影响不大
2、简单乘一个导致后期处理简单
3、似乎某些设计导致MMX寄存器快
如果有Core 2的结果最好了,Core 2应该能改进甚至导致SSE2的双乘算法超过MMX寄存器
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-24 10:49:01 | 显示全部楼层

改进版

在 56# 基础上改进,主要目的是让 pmuludq 指令集中执行,消除其延时,代码如下:
  1. _declspec(naked)
  2. void UInt128x128To256_SSE2_58F( UINT32 * const result,
  3.                                 const UINT32 * const left,
  4.                                 const UINT32 * const right )
  5. {
  6.     __asm
  7.     {
  8.         mov         ecx, dword ptr[esp + 04h]   ; result
  9.         mov         eax, dword ptr[esp + 08h]   ; left
  10.         mov         edx, dword ptr[esp + 0Ch]   ; right

  11.         movdqa      xmm5, xmmword ptr[eax]      ; load left
  12.         movdqa      xmm4, xmmword ptr[edx]      ; load right

  13.         mov         eax, esp                    ;
  14.         sub         esp, 0x4F                   ;
  15.         and         esp, -16                    ;

  16.         pshufd      xmm0, xmm5, 00000000b       ; xmm0 = L0:L0:L0:L0
  17.         pshufd      xmm1, xmm5, 01010101b       ; xmm1 = L1:L1:L1:L1
  18.         pshufd      xmm2, xmm5, 10101010b       ; xmm2 = L2:L2:L2:L2
  19.         pshufd      xmm3, xmm5, 11111111b       ; xmm3 = L3:L3:L3:L3

  20.         movdqa      xmmword ptr[ecx+0x00], xmm0 ; xmm0 = L0:L0:L0:L0
  21.         movdqa      xmmword ptr[ecx+0x10], xmm1 ; xmm1 = L1:L1:L1:L1
  22.         movdqa      xmm6, xmm2                  ; xmm6 = L2:L2:L2:L2
  23.         movdqa      xmm7, xmm3                  ; xmm7 = L3:L3:L3:L3

  24.         pmuludq     xmm0, xmm4                  ; xmm0 = L0*R2:L0*R0
  25.         pmuludq     xmm1, xmm4                  ; xmm1 = L1*R2:L1*R0
  26.         pmuludq     xmm2, xmm4                  ; xmm2 = L2*R2:L2*R0
  27.         pmuludq     xmm3, xmm4                  ; xmm3 = L3*R2:L3*R0

  28.         movdqa      xmmword ptr[esp+0x00], xmm0 ;
  29.         movdqa      xmmword ptr[esp+0x10], xmm1 ;
  30.         movdqa      xmmword ptr[esp+0x20], xmm2 ;
  31.         movdqa      xmmword ptr[esp+0x30], xmm3 ;

  32.         psrldq      xmm4, 4                     ; xmm4 = 00:R3:R2:R1
  33.         movdqa      xmm1, xmmword ptr[ecx+0x10] ; xmm1 = L1:L1:L1:L1
  34.         movdqa      xmm0, xmmword ptr[ecx+0x00] ; xmm0 = L0:L0:L0:L0

  35.         pmuludq     xmm7, xmm4                  ; xmm3 = L3*R3:L3*R1 ->V7-4
  36.         pmuludq     xmm6, xmm4                  ; xmm2 = L2*R3:L2*R1 ->V6-3
  37.         pmuludq     xmm1, xmm4                  ; xmm1 = L1*R3:L1*R1
  38.         pmuludq     xmm0, xmm4                  ; xmm0 = L0*R3:L0*R1


  39.         movdqa      xmm5, xmm7                  ;
  40.         movdqa      xmm4, xmm6                  ;
  41.         movdqa      xmm3, xmm6                  ;

  42.         pslldq      xmm5, 4                     ; xmm5 <<= 32
  43.         psrldq      xmm4, 4                     ; xmm4 >>= 32
  44.         pslldq      xmm3, 12                    ; L3*R3:L3*R1 ->V3-0

  45.         paddq       xmm7, xmm4                  ; L2*R3:L2*R1 ->V7-4
  46.         paddq       xmm6, xmm5                  ; L3*R3:L3*R1 ->V6-3


  47.         movdqa      xmm2, xmm0                  ;
  48.         movdqa      xmm4, xmm0                  ;
  49.         movdqa      xmm5, xmm1                  ;

  50.         psrldq      xmm0, 8                     ; xmm0 >>= 64
  51.         psrldq      xmm1, 4                     ; xmm1 >>= 32
  52.         pslldq      xmm2, 8                     ; L0*R3:L0*R1 ->V2-1H
  53.         pslldq      xmm4, 4                     ; xmm4 <<= 32
  54.         pslldq      xmm5, 8                     ; xmm5 <<= 64

  55.         paddq       xmm6, xmm0                  ; L0*R3:L0*R1 ->V6-3
  56.         paddq       xmm3, xmm4                  ; L0*R3:L0*R1 ->V3-0
  57.         paddq       xmm6, xmm1                  ; L1*R3:L1*R1 ->V6-3
  58.         paddq       xmm3, xmm5                  ; L1*R3:L1*R1 ->V3-0

  59.         psrldq      xmm0, 4                     ; xmm0 >>= 32
  60.         psrldq      xmm1, 4                     ; xmm1 >>= 32
  61.         pslldq      xmm5, 4                     ; xmm5 <<= 32

  62.         paddq       xmm7, xmm0                  ; L0*R3:L0*R1 ->V7-4
  63.         paddq       xmm2, xmm5                  ; L1*R3:L1*R1 ->V2-1H
  64.         paddq       xmm7, xmm1                  ; L1*R3:L1*R1 ->V7-4


  65.         movdqa      xmm5, xmmword ptr[esp+0x30] ; xmm5 = L3*R2:L3*R0
  66.         movdqa      xmm4, xmmword ptr[esp+0x20] ; xmm4 = L2*R2:L2*R0

  67.         movdqa      xmm1, xmm5                  ;
  68.         movdqa      xmm0, xmm4                  ;
  69.         paddq       xmm6, xmm5                  ; L3*R2:L3*R0 ->V6-3

  70.         psrldq      xmm0, 4                     ; xmm0 >>= 32
  71.         psrldq      xmm1, 4                     ; xmm1 >>= 32
  72.         pslldq      xmm4, 8                     ; xmm4 <<= 64
  73.         pslldq      xmm5, 12                    ; xmm5 <<= 96

  74.         paddq       xmm6, xmm0                  ; L2*R2:L2*R0 ->V6-3
  75.         paddq       xmm3, xmm4                  ; L2*R2:L2*R0 ->V3-0
  76.         paddq       xmm7, xmm1                  ; L3*R2:L3*R0 ->V7-4
  77.         paddq       xmm3, xmm5                  ; L3*R2:L3*R0 ->V3-0

  78.         psrldq      xmm0, 4                     ; xmm0 >>= 32
  79.         pslldq      xmm4, 4                     ; xmm4 <<= 32

  80.         paddq       xmm7, xmm0                  ; L2*R2:L2*R0 ->V7-4
  81.         paddq       xmm2, xmm4                  ; L2*R2:L2*R0 ->V2-1H


  82.         movdqa      xmm0, xmmword ptr[esp+0x00] ; xmm0 = L0*R2:L0*R0
  83.         movdqa      xmm1, xmmword ptr[esp+0x10] ; xmm1 = L1*R2:L1*R0

  84.         mov         esp, eax                    ;

  85.         paddq       xmm3, xmm0                  ; L0*R2:L0*R0 ->V3-0

  86.         movdqa      xmm4, xmm0                  ;
  87.         movdqa      xmm5, xmm1                  ;

  88.         pslldq      xmm0, 4                     ; xmm0 <<= 32
  89.         pslldq      xmm1, 4                     ; xmm1 <<= 32
  90.         psrldq      xmm4, 12                    ; xmm4 >>= 96
  91.         psrldq      xmm5, 8                     ; xmm5 >>= 64

  92.         paddq       xmm2, xmm0                  ; L0*R2:L0*R0 ->V2-1H
  93.         paddq       xmm6, xmm4                  ; L0*R2:L0*R0 ->V6-3
  94.         paddq       xmm3, xmm1                  ; L1*R2:L1*R0 ->V3-0
  95.         paddq       xmm6, xmm5                  ; L1*R2:L1*R0 ->V6-3

  96.         pslldq      xmm1, 4                     ; xmm1 <<= 32
  97.         psrldq      xmm5, 4                     ; xmm5 >>= 32

  98.         paddq       xmm2, xmm1                  ; L1*R2:L1*R0 ->V2-1H
  99.         paddq       xmm7, xmm5                  ; L1*R2:L1*R0 ->V7-4


  100.         ; now, V[1:0]=xmm3[63:0] ->OK
  101.         psrldq      xmm2, 4                     ; xmm2 >>= 32
  102.         movdqa      xmm4, xmm3                  ;
  103.         pcmpeqd     xmm0, xmm0                  ; xmm0 = FF:FF:FF:FF
  104.         pandn       xmm4, xmm2                  ;
  105.         psubd       xmm2, xmm3                  ; xmm2 -= xmm3
  106.         psrldq      xmm0, 12                    ; xmm0 = 00:00:00:FF

  107.         pslldq      xmm4, 4                     ; xmm4 <<= 32
  108.         psrld       xmm4, 31                    ; CF
  109.         pshufd      xmm1, xmm0, 01001110b       ; xmm1 = 00:FF:00:00
  110.         paddd       xmm2, xmm4                  ;
  111.         pand        xmm2, xmm1                  ;
  112.         paddq       xmm3, xmm2                  ; V[3:0]=xmm3 ->OK
  113.         movdqa      xmmword ptr[ecx+0x00], xmm3 ; store V[3:0]


  114.         psrldq      xmm3, 12                    ; xmm3 >>= 96
  115.         psubd       xmm3, xmm6                  ; xmm3 -= xmm6
  116.         pand        xmm3, xmm0                  ;
  117.         paddq       xmm6, xmm3                  ; V[4:3]=xmm6[63:0] ->OK
  118.         pxor        xmm1, xmm0                  ; xmm1 = 00:FF:00:FF
  119.         psrldq      xmm6, 4                     ; V[4]=xmm6[31:0] ->OK


  120.         movdqa      xmm2, xmm6                  ; xmm2 = xmm6
  121.         psubd       xmm6, xmm7                  ; xmm6 -= xmm0
  122.         pand        xmm6, xmm1                  ;
  123.         paddq       xmm7, xmm6                  ; now, xmm7[63-0] bits OK!

  124.         psubusb     xmm2, xmm7                  ;
  125.         psrlq       xmm2, 63                    ; CF
  126.         pslldq      xmm2, 8                     ;
  127.         paddq       xmm7, xmm2                  ; xmm7[127-64] += CF
  128.         movdqa      xmmword ptr[ecx+0x10], xmm7 ; store V[7:4]

  129.         ret;
  130.     }
  131. }
复制代码
全函数 121 条汇编指令(含 ret 指令),无跳转,无 adc 指令。

测试结果如下:
UInt128x128To256_ANSI_C32(..): 679.753ms
UInt128x128To256_SSE2_40F(..): 479.048ms
UInt128x128To256_SSE2_42F(..): 809.487ms
UInt128x128To256_SSE2_54F(..): 754.158ms
UInt128x128To256_SSE2_56F(..): 640.666ms
UInt128x128To256_SSE2_58F(..): 625.339ms

测试环境:Windows XP SP2,AMD Athlon 64 Processor 3200+,1GB DDR - 200MHz
(欢迎大家在本地机上测试)

当前所有版本测试源代码及编译好的程序压缩包: UInt128x128To256.zip (31.96 KB, 下载次数: 9)
注意:69# 有更新更全的压缩包)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-24 11:27:32 | 显示全部楼层
报个到先. 本来说不打算参与了,看你们写了这么多版本,我也试一试写SSE2版的。
主要采用SSE2指令乘,一次只做一个32bit*32bit,进位部分采用利用 SSE2指令做 64bit + 32bit的运算,中间结果使用 MMX存储。
预期的速度应该难以超越gxq,但应该不会太慢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-24 11:43:28 | 显示全部楼层
我写的仍无法超越楼主在 40# 里的“SSE2指令/MMX寄存器”版本。
不知在 Core 2 上的结果会如何?

这次与先前的 UInt96x96To192 不一样,对进位处理更麻烦,
而我的所谓“诡异算法”似乎并不凑效,所以比我快的可能性仍很高。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 18:36 , Processed in 0.045430 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表