33,007
社区成员
发帖
与我相关
我的任务
分享嘿嘿，昨天终于调试成了SSE2代码的大数普通乘法
晚上贴上来
就是速度不太理想，不知道如何优化，请大家指教
计算了(2 ^ (32 * 65536) - 1)的平方,P4 2.0 256 DDR 大概30秒的任务管理器时间，真实的时间可能少点
大概是63万位十进制的乘法吧，对于大家一直讨论的输出问题，我估计大概能在2秒内转换成十进制吧
刚才进入了GMP主页，同样的问题GMP 203ms完成，750M AMD + FreeBSD ：）
没有输出时间，因为数据太大 ：），遗憾了
不过，GMP转换3万多十进制位的数大概24ms，配置同上面
就是速度不太理想，不知道如何优化，请大家指教
计算了(2 ^ (32 * 65536) - 1)的平方,P4 2.0 256 DDR 大概30秒的任务管理器时间，真实的时间可能少点
大概是63万位十进制的乘法吧，对于大家一直讨论的输出问题，我估计大概能在2秒内转换成十进制吧
刚才进入了GMP主页，同样的问题GMP 203ms完成，750M AMD + FreeBSD ：）
没有输出时间，因为数据太大 ：），遗憾了
不过，GMP转换3万多十进制位的数大概24ms，配置同上面
...全文
请发表友善的回复…
发表回复
shines77 2004-07-24
- 打赏
- 举报
MMX只支持16位的乘法吧？如果是128 bit的MMX那就是SSE2了，比如PMULUDQ指令，它是SSE2才有的指令，也支持MMX寄存器
shines77 2004-07-24
- 打赏
- 举报
终于找到了SSE 内存拷贝的那个帖子
http://bbs.gameres.com/showthread.asp?threadid=6792
http://bbs.gameres.com/showthread.asp?threadid=6792
yaos 2004-07-24
- 打赏
- 举报
嘿嘿，建议别用SSE寄存器
比MMX慢，我乘法改MMX，愣从SSE的30秒降到了23秒
比MMX慢，我乘法改MMX，愣从SSE的30秒降到了23秒
yaos 2004-07-24
- 打赏
- 举报
global _fast_memcpy9
%define param esp+12+4
%define src param+0
%define dst param+4
%define len param+8
%define CACHEBLOCK 400h
_fast_memcpy9:
push esi
push edi
push ebx
mov esi, [src] ; source array
mov edi, [dst] ; destination array
mov ecx, [len] ; number of QWORDS (8 bytes) assumes len / CACHEBLOCK is an integer
shr ecx, 3
lea esi, [esi+ecx*8] ; end of source
lea edi, [edi+ecx*8] ; end of destination
neg ecx ; use a negative offset as a combo pointer-and-loop-counter
.mainloop:
mov eax, CACHEBLOCK / 16 ; note: .prefetchloop is unrolled 2X
add ecx, CACHEBLOCK ; move up to end of block
.prefetchloop:
mov ebx, [esi+ecx*8-64] ; read one address in this cache line...
mov ebx, [esi+ecx*8-128] ; ... and one in the previous line
sub ecx, 16 ; 16 QWORDS = 2 64-byte cache lines
dec eax
jnz .prefetchloop
mov eax, CACHEBLOCK / 8
.writeloop:
prefetchnta [esi+ecx*8 + 512] ; fetch ahead by 512 bytes
movq mm0, qword [esi+ecx*8]
movq mm1, qword [esi+ecx*8+8]
movq mm2, qword [esi+ecx*8+16]
movq mm3, qword [esi+ecx*8+24]
movq mm4, qword [esi+ecx*8+32]
movq mm5, qword [esi+ecx*8+40]
movq mm6, qword [esi+ecx*8+48]
movq mm7, qword [esi+ecx*8+56]
movntq qword [edi+ecx*8], mm0
movntq qword [edi+ecx*8+8], mm1
movntq qword [edi+ecx*8+16], mm2
movntq qword [edi+ecx*8+24], mm3
movntq qword [edi+ecx*8+32], mm4
movntq qword [edi+ecx*8+40], mm5
movntq qword [edi+ecx*8+48], mm6
movntq qword [edi+ecx*8+56], mm7
add ecx, 8
dec eax
jnz .writeloop
or ecx, ecx ; assumes integer number of cacheblocks
jnz .mainloop
sfence ; flush write buffer
emms
pop ebx
pop edi
pop esi
ret
也发现了一个 :)
%define param esp+12+4
%define src param+0
%define dst param+4
%define len param+8
%define CACHEBLOCK 400h
_fast_memcpy9:
push esi
push edi
push ebx
mov esi, [src] ; source array
mov edi, [dst] ; destination array
mov ecx, [len] ; number of QWORDS (8 bytes) assumes len / CACHEBLOCK is an integer
shr ecx, 3
lea esi, [esi+ecx*8] ; end of source
lea edi, [edi+ecx*8] ; end of destination
neg ecx ; use a negative offset as a combo pointer-and-loop-counter
.mainloop:
mov eax, CACHEBLOCK / 16 ; note: .prefetchloop is unrolled 2X
add ecx, CACHEBLOCK ; move up to end of block
.prefetchloop:
mov ebx, [esi+ecx*8-64] ; read one address in this cache line...
mov ebx, [esi+ecx*8-128] ; ... and one in the previous line
sub ecx, 16 ; 16 QWORDS = 2 64-byte cache lines
dec eax
jnz .prefetchloop
mov eax, CACHEBLOCK / 8
.writeloop:
prefetchnta [esi+ecx*8 + 512] ; fetch ahead by 512 bytes
movq mm0, qword [esi+ecx*8]
movq mm1, qword [esi+ecx*8+8]
movq mm2, qword [esi+ecx*8+16]
movq mm3, qword [esi+ecx*8+24]
movq mm4, qword [esi+ecx*8+32]
movq mm5, qword [esi+ecx*8+40]
movq mm6, qword [esi+ecx*8+48]
movq mm7, qword [esi+ecx*8+56]
movntq qword [edi+ecx*8], mm0
movntq qword [edi+ecx*8+8], mm1
movntq qword [edi+ecx*8+16], mm2
movntq qword [edi+ecx*8+24], mm3
movntq qword [edi+ecx*8+32], mm4
movntq qword [edi+ecx*8+40], mm5
movntq qword [edi+ecx*8+48], mm6
movntq qword [edi+ecx*8+56], mm7
add ecx, 8
dec eax
jnz .writeloop
or ecx, ecx ; assumes integer number of cacheblocks
jnz .mainloop
sfence ; flush write buffer
emms
pop ebx
pop edi
pop esi
ret
也发现了一个 :)
yaos 2004-07-24
- 打赏
- 举报
晕，说得不清楚，是MMX寄存器和SSE寄存器 ：）
yaos 2004-07-23
- 打赏
- 举报
终于测试karatsuba乘法成功了
这个帖子到此为止，新的源代码将重新开贴子贴
这个帖子到此为止，新的源代码将重新开贴子贴
yaos 2004-07-22
- 打赏
- 举报
嘿嘿，发现一个大错误
在测试3 * 32Bit时结果错误 ：）
有朋友指出Bug么？
在测试3 * 32Bit时结果错误 ：）
有朋友指出Bug么？
yaos 2004-07-21
- 打赏
- 举报
嘿嘿，在看小说，100多万字，暂时不干别的了
：）
测试的事情后延
65536 * 32 Bit相当于63万位十进制
：）
测试的事情后延
65536 * 32 Bit相当于63万位十进制
yaos 2004-07-20
- 打赏
- 举报
我？
不是10^9啊，是2^32
晚上测试普通的情况，包括karatsuba主函数
不是10^9啊，是2^32
晚上测试普通的情况，包括karatsuba主函数
kerbcurb 2004-07-20
- 打赏
- 举报
看来汇编就是快，我的普通算法，普通10进制12万位*12万位用时11.7秒
kerbcurb 2004-07-19
- 打赏
- 举报
我的机子用时1200毫秒左右，但是结果好象有点问题
我使用这样显示函数
typedef unsigned long* LARGENUMPTR;
void LargeNumDisplay(unsigned long n, LARGENUMPTR & c,int bit,ostream& ostr)
{
char temp[20],fmt[10],ch[4];
unsigned long k;
sprintf(fmt,"%s","\%0");
sprintf(ch,"%d",bit);
strcat(fmt,ch);
strcat(fmt,"u");
for(k = 0;k < n;k++)
{
sprintf(temp,fmt,c[k]);
ostr << temp;
}
}
其中bit是进制的零（0）的位数，在你的程序中等于9
我在程序中相应缩短数组长度，直接从显示器输出，结果有问题，最简单的办法是设置a 和b都为零，这样c应该为零，但是不是。
我使用这样显示函数
typedef unsigned long* LARGENUMPTR;
void LargeNumDisplay(unsigned long n, LARGENUMPTR & c,int bit,ostream& ostr)
{
char temp[20],fmt[10],ch[4];
unsigned long k;
sprintf(fmt,"%s","\%0");
sprintf(ch,"%d",bit);
strcat(fmt,ch);
strcat(fmt,"u");
for(k = 0;k < n;k++)
{
sprintf(temp,fmt,c[k]);
ostr << temp;
}
}
其中bit是进制的零（0）的位数，在你的程序中等于9
我在程序中相应缩短数组长度，直接从显示器输出，结果有问题，最简单的办法是设置a 和b都为零，这样c应该为零，但是不是。
yaos 2004-07-19
- 打赏
- 举报
//双字串减双字, 调试完成，还可以优化 ：）
unsigned long AsmSubLS(unsigned long * pL, unsigned long pR, unsigned long * pA, unsigned long t)
{
if (t == 0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
movd mm2, dword ptr [pR]
lea ebx, [ebx+4*ecx]
mov eax, 0
neg ecx
asmsub1:
movd mm1, dword ptr [esi+ecx*4]
psubq mm1, mm2
psubq mm1, mm0
movd dword ptr [ebx+ecx*4], mm1
psrlq mm1, 63
movq mm0, mm1
add ecx, 1
movd mm2, eax
jne asmsub1
movd eax, mm0
emms
}
}
//自减，默认减少1,未完成
unsigned long AsmDec(unsigned long * pL, unsigned long t, unsigned long pR = 1)
{
if (t == 0)
return 0;
}
//找到比n大的第一个２的方幂,n不能为2方幂，否则出错 ：）
unsigned long find2k(unsigned long n) {
if (n == 0)
return 0;
__asm
{
mov ebx, n
bsr ecx, ebx
inc ecx
mov eax, 1
shl eax, cl
}
}
//双字串清零，要重新设计
void AsmMemZero(unsigned long * p, unsigned long s)
{
if (s == 0)
return;
__asm
{
mov eax, dword ptr [p]
mov edx, s
mov ebx, edx
shr ebx, 2
mov ecx, ebx
shl ebx, 2
sub edx, ebx
cmp ecx, 0
jz asmmemzero1
pxor xmm0, xmm0
asmmemzero0:
movdqu [eax], xmm0 //要修改为movdqa
add eax, 16
loop asmmemzero0
asmmemzero1:
cmp edx, 0
jz asmmemzero3
mov ecx, edx
mov ebx ,0
asmmemzero2:
mov dword ptr [eax], ebx
add eax, 4
loop asmmemzero2
asmmemzero3:
}
}
//双字串除双字
void AsmDivLS(unsigned long * pR, unsigned long pL, unsigned long pA, unsigned long t)
{
if (t == 0)
return;
}
//双字串对双字求余
unsigned long AsmModLS(unsigned long * pR, unsigned long pL, unsigned long t)
{
if (t ==0)
return 0;
}
//karatsuba核心函数
//u = 2 ^ n * U1 + U0
//v = 2 ^ n * V1 + V0
//uv = (2 ^ 2n + 2 ^ n) U1 * V1 + 2 ^ n (U1 - U0) * (V0 - V1) + (2 ^ n + 1) U0 * V0
void mul_karatsuba_core(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long t)
{
if (t <= 32)
return AsmMulLL(pL, pR, pA, t, t);
unsigned long * tmp, * tmp1, * tmp2;
long carry1 = 1, carry2 = 1, carry;
tmp = new unsigned long [t];
tmp1 = new unsigned long [t / 2];
tmp2 = new unsigned long [t / 2];
AsmMemZero(tmp, t);
AsmMemZero(tmp1, t / 2);
AsmMemZero(tmp2, t / 2);
mul_karatsuba_core(pL, pR, pA, t / 2);
mul_karatsuba_core(pL + t / 2, pR + t / 2, pA + t, t / 2);
if (AsmSubLL(pL + t / 2, pL, tmp1, t / 2) == 1)
carry1 = - 1;
if (AsmSubLL(pR, pR + t / 2, tmp2, t / 2) == 1)
carry2 = - 1;
mul_karatsuba_core(tmp1, tmp2, tmp, t / 2);
carry = carry1 * carry2;
if (carry == 1)
carry = 0;
else
carry = - 1;
carry += AsmAddLL(pA, tmp, tmp, t);
carry += AsmAddLL(pA + t, tmp, tmp, t);
carry += AsmAddLL(pA + t / 2, tmp, pA + t / 2, t);
if (carry > 0)
AsmAddLS(pA + t / 2 + t, (unsigned long)carry, pA + t / 2 + t, t / 2);
delete []tmp;
delete []tmp1;
delete []tmp2;
}
//太乱了，准备重新设计
void mul_karatsuba(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long tL, unsigned long tR)
{
if (tL < tR) //保证第一个乘数更大
{
mul_karatsuba(pR, pL, pA, tR, tL);
return;
}
if (tR <= 32) //常规方法更好
{
AsmMulLL(pL, pR, pA, tL, tR);
return;
}
unsigned long t = tL / tR;
if (t >= 2) //两个数字长度差别太大
{
unsigned long * pT = new unsigned long[2 * tR];
for (unsigned long i = 0; i < t; i ++)
{
AsmMemZero(pT, 2 * tR);
mul_karatsuba(pL + i * tR, pR, pT, tR, tR); //部分乘法
AsmAddLL(pT, pA + i * tR, pA + i * tR, 2 * tR); //加结果到pA, 不应该有进位
}
unsigned long r = tL % tR;
if (r > 0) //处理余下的部分
{
AsmMemZero(pT, 2 * tR);
mul_karatsuba(pL + tL - r, pR, pT, r, tR);
AsmAddLL(pT, pA + tL - r, pA + tL - r, tR + r);
}
delete []pT;
return;
}
unsigned long l = find2k(tL);
if (l == 2 * tL)
l = l / 2;
unsigned long * src1 = new unsigned long [l];
unsigned long * src2 = new unsigned long [l];
unsigned long * dest = new unsigned long [2 * l];
AsmMemZero(src1, l);
AsmMemZero(src2, l);
AsmMemZero(dest, 2 * l);
memcpy(src1, pL, 4 * tL);
memcpy(src2, pR, 4 * tR);
mul_karatsuba_core(src1, src2, dest, l);
memcpy(pA, dest, (tL + tR) * 4);
delete []src1;
delete []src2;
delete []dest;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long i;
for (i = 0; i < 65536; i ++)
{
a[i] = 0xFFFFFFFF;
b[i] = 0xFFFFFFFF;
c[i] = 0;
}
for (i = 65536; i < 131072; i ++)
c[i] = 0;
mul_karatsuba(a, b, c, 65536, 65536);
return 0;
}
哈,终于调试成功了karatsuba乘法了
P4 2.0 256 DDR Win2000 65536 * 32位 乘 时间 2秒
哈,高兴中,另外有的地方可以优化,请大家提意见
还没有测试普通的情况,先发上来
unsigned long AsmSubLS(unsigned long * pL, unsigned long pR, unsigned long * pA, unsigned long t)
{
if (t == 0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
movd mm2, dword ptr [pR]
lea ebx, [ebx+4*ecx]
mov eax, 0
neg ecx
asmsub1:
movd mm1, dword ptr [esi+ecx*4]
psubq mm1, mm2
psubq mm1, mm0
movd dword ptr [ebx+ecx*4], mm1
psrlq mm1, 63
movq mm0, mm1
add ecx, 1
movd mm2, eax
jne asmsub1
movd eax, mm0
emms
}
}
//自减，默认减少1,未完成
unsigned long AsmDec(unsigned long * pL, unsigned long t, unsigned long pR = 1)
{
if (t == 0)
return 0;
}
//找到比n大的第一个２的方幂,n不能为2方幂，否则出错 ：）
unsigned long find2k(unsigned long n) {
if (n == 0)
return 0;
__asm
{
mov ebx, n
bsr ecx, ebx
inc ecx
mov eax, 1
shl eax, cl
}
}
//双字串清零，要重新设计
void AsmMemZero(unsigned long * p, unsigned long s)
{
if (s == 0)
return;
__asm
{
mov eax, dword ptr [p]
mov edx, s
mov ebx, edx
shr ebx, 2
mov ecx, ebx
shl ebx, 2
sub edx, ebx
cmp ecx, 0
jz asmmemzero1
pxor xmm0, xmm0
asmmemzero0:
movdqu [eax], xmm0 //要修改为movdqa
add eax, 16
loop asmmemzero0
asmmemzero1:
cmp edx, 0
jz asmmemzero3
mov ecx, edx
mov ebx ,0
asmmemzero2:
mov dword ptr [eax], ebx
add eax, 4
loop asmmemzero2
asmmemzero3:
}
}
//双字串除双字
void AsmDivLS(unsigned long * pR, unsigned long pL, unsigned long pA, unsigned long t)
{
if (t == 0)
return;
}
//双字串对双字求余
unsigned long AsmModLS(unsigned long * pR, unsigned long pL, unsigned long t)
{
if (t ==0)
return 0;
}
//karatsuba核心函数
//u = 2 ^ n * U1 + U0
//v = 2 ^ n * V1 + V0
//uv = (2 ^ 2n + 2 ^ n) U1 * V1 + 2 ^ n (U1 - U0) * (V0 - V1) + (2 ^ n + 1) U0 * V0
void mul_karatsuba_core(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long t)
{
if (t <= 32)
return AsmMulLL(pL, pR, pA, t, t);
unsigned long * tmp, * tmp1, * tmp2;
long carry1 = 1, carry2 = 1, carry;
tmp = new unsigned long [t];
tmp1 = new unsigned long [t / 2];
tmp2 = new unsigned long [t / 2];
AsmMemZero(tmp, t);
AsmMemZero(tmp1, t / 2);
AsmMemZero(tmp2, t / 2);
mul_karatsuba_core(pL, pR, pA, t / 2);
mul_karatsuba_core(pL + t / 2, pR + t / 2, pA + t, t / 2);
if (AsmSubLL(pL + t / 2, pL, tmp1, t / 2) == 1)
carry1 = - 1;
if (AsmSubLL(pR, pR + t / 2, tmp2, t / 2) == 1)
carry2 = - 1;
mul_karatsuba_core(tmp1, tmp2, tmp, t / 2);
carry = carry1 * carry2;
if (carry == 1)
carry = 0;
else
carry = - 1;
carry += AsmAddLL(pA, tmp, tmp, t);
carry += AsmAddLL(pA + t, tmp, tmp, t);
carry += AsmAddLL(pA + t / 2, tmp, pA + t / 2, t);
if (carry > 0)
AsmAddLS(pA + t / 2 + t, (unsigned long)carry, pA + t / 2 + t, t / 2);
delete []tmp;
delete []tmp1;
delete []tmp2;
}
//太乱了，准备重新设计
void mul_karatsuba(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long tL, unsigned long tR)
{
if (tL < tR) //保证第一个乘数更大
{
mul_karatsuba(pR, pL, pA, tR, tL);
return;
}
if (tR <= 32) //常规方法更好
{
AsmMulLL(pL, pR, pA, tL, tR);
return;
}
unsigned long t = tL / tR;
if (t >= 2) //两个数字长度差别太大
{
unsigned long * pT = new unsigned long[2 * tR];
for (unsigned long i = 0; i < t; i ++)
{
AsmMemZero(pT, 2 * tR);
mul_karatsuba(pL + i * tR, pR, pT, tR, tR); //部分乘法
AsmAddLL(pT, pA + i * tR, pA + i * tR, 2 * tR); //加结果到pA, 不应该有进位
}
unsigned long r = tL % tR;
if (r > 0) //处理余下的部分
{
AsmMemZero(pT, 2 * tR);
mul_karatsuba(pL + tL - r, pR, pT, r, tR);
AsmAddLL(pT, pA + tL - r, pA + tL - r, tR + r);
}
delete []pT;
return;
}
unsigned long l = find2k(tL);
if (l == 2 * tL)
l = l / 2;
unsigned long * src1 = new unsigned long [l];
unsigned long * src2 = new unsigned long [l];
unsigned long * dest = new unsigned long [2 * l];
AsmMemZero(src1, l);
AsmMemZero(src2, l);
AsmMemZero(dest, 2 * l);
memcpy(src1, pL, 4 * tL);
memcpy(src2, pR, 4 * tR);
mul_karatsuba_core(src1, src2, dest, l);
memcpy(pA, dest, (tL + tR) * 4);
delete []src1;
delete []src2;
delete []dest;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long i;
for (i = 0; i < 65536; i ++)
{
a[i] = 0xFFFFFFFF;
b[i] = 0xFFFFFFFF;
c[i] = 0;
}
for (i = 65536; i < 131072; i ++)
c[i] = 0;
mul_karatsuba(a, b, c, 65536, 65536);
return 0;
}
哈,终于调试成功了karatsuba乘法了
P4 2.0 256 DDR Win2000 65536 * 32位 乘 时间 2秒
哈,高兴中,另外有的地方可以优化,请大家提意见
还没有测试普通的情况,先发上来
yaos 2004-07-19
- 打赏
- 举报
// multest.cpp : 定义控制台应用程序的入口点。
//
//Intel P4 SSE2 修改的版本
#include "stdafx.h"
unsigned long a[65536];
unsigned long b[65536];
unsigned long c[131072];
//双字串乘法,已经调试完成
void AsmMulLL(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long tL, unsigned long tR)
{
if ((tL == 0) || (tR == 0))
return;
__asm {
mov ecx, tL
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm3, mm3
mbinmul2:
mov edx, ecx
mov eax, ebx
pxor mm0, mm0
mov ecx, tR
movd mm1, dword ptr [esi]
movd mm4, edi
mbinmul3:
movd mm2, dword ptr [edi]
lea edi, [edi+4]
pmuludq mm2, mm1
movd mm3, dword ptr [ebx]
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr [ebx], mm0
psrlq mm0, 32
lea ebx, [ebx+4]
loop mbinmul3
movd edi, mm4
movd dword ptr [ebx], mm0
mov ebx, eax
lea esi, [esi+4]
lea ebx, [ebx+4]
mov ecx, edx
loop mbinmul2
emms
}
}
//双字串乘双字,调试完成
unsigned long AsmMulLS(unsigned long *pL, unsigned long pR, unsigned long *pA, unsigned long t)
{
if (t == 0)
return 0;
__asm {
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
movd mm1, dword ptr [pR]
mbinmul0:
movd mm2, dword ptr [esi]
lea esi, [esi+4]
pmuludq mm2, mm1
paddq mm0, mm2
movd dword ptr [ebx], mm0
psrlq mm0, 32
lea ebx, [ebx+4]
loop mbinmul0
movd eax, mm0
emms
}
}
//双字串加法，已经调试完成
unsigned long AsmAddLL(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long t)
{
if (t ==0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
lea edi, [edi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmadd1:
movd mm1, dword ptr [esi+ecx*4]
movd mm2, dword ptr [edi+ecx*4]
paddq mm0, mm1
paddq mm0, mm2
movd dword ptr [ebx+ecx*4], mm0
psrlq mm0, 32
add ecx, 1
jne asmadd1
movd eax, mm0
emms
}
}
//双字串加双字, 调试完成， 还可以优化 ：）
unsigned long AsmAddLS(unsigned long *pL, unsigned long pR, unsigned long *pA, unsigned long t)
{
if (t ==0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
movd mm0, dword ptr [pR]
lea esi, [esi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmadd1:
movd mm1, dword ptr [esi+ecx*4]
paddq mm0, mm1
movd dword ptr [ebx+ecx*4], mm0
psrlq mm0, 32
add ecx, 1
jne asmadd1
movd eax, mm0
emms
}
}
//自增，默认增加1,未完成
unsigned long AsmInc(unsigned long * pL, unsigned long t, unsigned long pR = 1)
{
if (t == 0)
return 0;
}
//求负, 调试完成
void AsmNeg(unsigned long * p, unsigned long t)
{
if (t == 0)
return;
__asm
{
//mm1 $FFFFFFFF
//mm0 $100000000
mov eax, dword ptr [p]
mov ecx, t
mov edx, 1
movd mm0, edx
psllq mm0, 32
pxor mm1, mm1
mov edx, 0xFFFFFFFF
movd mm1, edx
pxor mm3, mm3
asmneg0:
movq mm2, mm0
psrlq mm2, 32
paddq mm2, mm1
movd mm3, [eax]
psubq mm2, mm3
movq mm0, mm2
movd [eax], mm2
lea eax, [eax+4]
loop asmneg0
emms
}
}
//双字串减法, 调试完成
unsigned long AsmSubLL(unsigned long * pL, unsigned long * pR, unsigned long * pA, unsigned long t)
{
if (t == 0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
lea edi, [edi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmsub1:
movd mm1, dword ptr [esi+ecx*4]
movd mm2, dword ptr [edi+ecx*4]
psubq mm1, mm2
psubq mm1, mm0
movd dword ptr [ebx+ecx*4], mm1
psrlq mm1, 63
movq mm0, mm1
add ecx, 1
jne asmsub1
movd eax, mm0
emms
}
}
//
//Intel P4 SSE2 修改的版本
#include "stdafx.h"
unsigned long a[65536];
unsigned long b[65536];
unsigned long c[131072];
//双字串乘法,已经调试完成
void AsmMulLL(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long tL, unsigned long tR)
{
if ((tL == 0) || (tR == 0))
return;
__asm {
mov ecx, tL
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm3, mm3
mbinmul2:
mov edx, ecx
mov eax, ebx
pxor mm0, mm0
mov ecx, tR
movd mm1, dword ptr [esi]
movd mm4, edi
mbinmul3:
movd mm2, dword ptr [edi]
lea edi, [edi+4]
pmuludq mm2, mm1
movd mm3, dword ptr [ebx]
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr [ebx], mm0
psrlq mm0, 32
lea ebx, [ebx+4]
loop mbinmul3
movd edi, mm4
movd dword ptr [ebx], mm0
mov ebx, eax
lea esi, [esi+4]
lea ebx, [ebx+4]
mov ecx, edx
loop mbinmul2
emms
}
}
//双字串乘双字,调试完成
unsigned long AsmMulLS(unsigned long *pL, unsigned long pR, unsigned long *pA, unsigned long t)
{
if (t == 0)
return 0;
__asm {
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
movd mm1, dword ptr [pR]
mbinmul0:
movd mm2, dword ptr [esi]
lea esi, [esi+4]
pmuludq mm2, mm1
paddq mm0, mm2
movd dword ptr [ebx], mm0
psrlq mm0, 32
lea ebx, [ebx+4]
loop mbinmul0
movd eax, mm0
emms
}
}
//双字串加法，已经调试完成
unsigned long AsmAddLL(unsigned long *pL, unsigned long *pR, unsigned long *pA, unsigned long t)
{
if (t ==0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
lea edi, [edi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmadd1:
movd mm1, dword ptr [esi+ecx*4]
movd mm2, dword ptr [edi+ecx*4]
paddq mm0, mm1
paddq mm0, mm2
movd dword ptr [ebx+ecx*4], mm0
psrlq mm0, 32
add ecx, 1
jne asmadd1
movd eax, mm0
emms
}
}
//双字串加双字, 调试完成， 还可以优化 ：）
unsigned long AsmAddLS(unsigned long *pL, unsigned long pR, unsigned long *pA, unsigned long t)
{
if (t ==0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
movd mm0, dword ptr [pR]
lea esi, [esi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmadd1:
movd mm1, dword ptr [esi+ecx*4]
paddq mm0, mm1
movd dword ptr [ebx+ecx*4], mm0
psrlq mm0, 32
add ecx, 1
jne asmadd1
movd eax, mm0
emms
}
}
//自增，默认增加1,未完成
unsigned long AsmInc(unsigned long * pL, unsigned long t, unsigned long pR = 1)
{
if (t == 0)
return 0;
}
//求负, 调试完成
void AsmNeg(unsigned long * p, unsigned long t)
{
if (t == 0)
return;
__asm
{
//mm1 $FFFFFFFF
//mm0 $100000000
mov eax, dword ptr [p]
mov ecx, t
mov edx, 1
movd mm0, edx
psllq mm0, 32
pxor mm1, mm1
mov edx, 0xFFFFFFFF
movd mm1, edx
pxor mm3, mm3
asmneg0:
movq mm2, mm0
psrlq mm2, 32
paddq mm2, mm1
movd mm3, [eax]
psubq mm2, mm3
movq mm0, mm2
movd [eax], mm2
lea eax, [eax+4]
loop asmneg0
emms
}
}
//双字串减法, 调试完成
unsigned long AsmSubLL(unsigned long * pL, unsigned long * pR, unsigned long * pA, unsigned long t)
{
if (t == 0)
return 0;
__asm
{
mov ecx, t
mov esi, dword ptr [pL]
mov edi, dword ptr [pR]
mov ebx, dword ptr [pA]
pxor mm0, mm0
pxor mm1, mm1
pxor mm2, mm2
lea esi, [esi+4*ecx]
lea edi, [edi+4*ecx]
lea ebx, [ebx+4*ecx]
neg ecx
asmsub1:
movd mm1, dword ptr [esi+ecx*4]
movd mm2, dword ptr [edi+ecx*4]
psubq mm1, mm2
psubq mm1, mm0
movd dword ptr [ebx+ecx*4], mm1
psrlq mm1, 63
movq mm0, mm1
add ecx, 1
jne asmsub1
movd eax, mm0
emms
}
}
yaos 2004-07-19
- 打赏
- 举报
修改了一下mul_karatsuba乘法的结构，分成2函数了，发现简单了很多，能通过编译和运行了
速度很快 上边的65536 * 32 Bit运算，不过1-2秒，就是结果完全错误，哈哈
可惜在修改了一个主要错误后，停电了，无法看到结果了，只能今天晚上继续了]
由于程序给大幅度简化，估计出错概率不大了，等我的好消息
另外，开始计划实现3个普通除法了
还是无法实现SSE2内存拷贝功能，想起来一个缓冲区算法，不大有信心，没有头绪 ：）
速度很快 上边的65536 * 32 Bit运算，不过1-2秒，就是结果完全错误，哈哈
可惜在修改了一个主要错误后，停电了，无法看到结果了，只能今天晚上继续了]
由于程序给大幅度简化，估计出错概率不大了，等我的好消息
另外，开始计划实现3个普通除法了
还是无法实现SSE2内存拷贝功能，想起来一个缓冲区算法，不大有信心，没有头绪 ：）
yaos 2004-07-18
- 打赏
- 举报
清零好处理
就是可惜，白SSE了，还不如386呢 ：）
不过movdqa速度还是比较理想的
准备实现对齐 ：）
内存拷贝涉及到两个地址，暂时不知道如何做
就是可惜，白SSE了，还不如386呢 ：）
不过movdqa速度还是比较理想的
准备实现对齐 ：）
内存拷贝涉及到两个地址，暂时不知道如何做
wsmagic 2004-07-18
- 打赏
- 举报
favorite
shines77 2004-07-17
- 打赏
- 举报
每个地址的前40个字节都包含new对象的信息，相关地址指针，由于不了解其具体的数据结构，只是猜测而已
shines77 2004-07-17
- 打赏
- 举报
我随便写了下面的代码：
char *buf, *buf1;
long *buflong;
buf = new char [13];
buf1 = new char [1];
buflong = new long [13];
buf = new char [1];
buf1 = new char [13];
五次new的地址分别为：
0x01780a48
0x01780a90
0x01780b68
0x01780bd0
0x01780c08
每个对象的地址的前8个字节好像保存的是在堆中的序号（因为new是在堆中分配的），后面至少预留了一些剩余空间（具体规则不明），所以整体看来，是8字节对齐的，这也是我的MMX加减法不必对齐的原因，SSE数据对齐是一个很麻烦的东西，有点掉胃口，但是要用就必须对齐
char *buf, *buf1;
long *buflong;
buf = new char [13];
buf1 = new char [1];
buflong = new long [13];
buf = new char [1];
buf1 = new char [13];
五次new的地址分别为：
0x01780a48
0x01780a90
0x01780b68
0x01780bd0
0x01780c08
每个对象的地址的前8个字节好像保存的是在堆中的序号（因为new是在堆中分配的），后面至少预留了一些剩余空间（具体规则不明），所以整体看来，是8字节对齐的，这也是我的MMX加减法不必对齐的原因，SSE数据对齐是一个很麻烦的东西，有点掉胃口，但是要用就必须对齐
yaos 2004-07-17
- 打赏
- 举报
不过，我用的指令是写未对齐的数据的 ：）
暂时没读数据
至少VC的数据是64位对齐的吧？
暂时没读数据
至少VC的数据是64位对齐的吧？
yaos 2004-07-17
- 打赏
- 举报
嘿嘿，除了个别的函数，都是32位内存操作，估计没问题
就AsmMemZero和准备实现的AsmMemCopy是
谢谢指教，我看来要加判断语句了
就AsmMemZero和准备实现的AsmMemCopy是
谢谢指教，我看来要加判断语句了
加载更多回复（22）
