strcpy当初没有考虑到的地方
原贴地址:
http://eparg.spaces.live.com/blog/cns!59BFC22C0E7E1A76!1498.entry
原贴时间:
2006-08-16
原贴作者:
eparg
当年的讨论在:
http://eparg.spaces.live.com/blog/cns!59BFC22C0E7E1A76!533.entry
http://eparg.spaces.live.com/blog/cns!59BFC22C0E7E1A76!875.entry
最开始考虑strcpy的性能的时候,只考虑了要4bytes一起拷贝。但是忽略了一个关键问题,就是如何判断字符串的结束。由于字符串可以从4bytes中任意一个byte结束,所以需要判断是否有任何一个byte为0。
如果对一个4bytes拆分成4个byte分别判断,那4bytes一起拷贝节省下拉性能立刻浪费掉了。今天看到Newer2k的回复,才重新开始考虑这个问题。
拿到C++的strcpy函数一看,源代码如下:
mov edi,[esp+8] ; edi points to dest string
copy_start::
mov ecx,[esp+0ch] ; ecx -> sorc string
test ecx,3 ; test if string is aligned on 32 bits
je short main_loop_entrance
src_misaligned: ; simple byte loop until string is aligned
mov dl,byte ptr [ecx]
add ecx,1
test dl,dl
je short byte_0
mov [edi],dl
add edi,1
test ecx,3
jne short src_misaligned
jmp short main_loop_entrance
main_loop: ; edx contains first dword of sorc string
mov [edi],edx ; store one more dword
add edi,4 ; kick dest pointer
main_loop_entrance:
mov edx,7efefeffh
mov eax,dword ptr [ecx] ; read 4 bytes
add edx,eax
xor eax,-1
xor eax,edx
mov edx,[ecx] ; it's in cache now
add ecx,4 ; kick dest pointer
test eax,81010100h
je short main_loop
; found zero byte in the loop
; main_loop_end:
test dl,dl ; is it byte 0
je short byte_0
test dh,dh ; is it byte 1
je short byte_1
test edx,00ff0000h ; is it byte 2
je short byte_2
test edx,0ff000000h ; is it byte 3
je short byte_3
jmp short main_loop ; taken if bits 24-30 are clear and bit
; 31 is set
byte_3:
mov [edi],edx
mov eax,[esp+8] ; return in eax pointer to dest string
pop edi
ret
byte_2:
mov [edi],dx
mov eax,[esp+8] ; return in eax pointer to dest string
mov byte ptr [edi+2],0
pop edi
ret
byte_1:
mov [edi],dx
mov eax,[esp+8] ; return in eax pointer to dest string
pop edi
ret
byte_0:
mov [edi],dl
mov eax,[esp+8] ; return in eax pointer to dest string
pop edi
ret
这里对一个DWORD (EAX)的判断方法是:
1. 对EAX+0x7efefeff
2. 对EAX取反
3. 把1和2的结果作XOR,然后跟0x81010100h作test运算
研究了好久,理解如下:
问题的关键点在于,当且仅当EAX四个byte都不为0的时候,运算结果会是下面的pattern:
0??? ???0 ???? ???0 ???? ???0 ???? ????
分别解释如下:
如果第一个byte为0, 考虑第二个byte的最后一个bit。不管这个bit是0还是1,计算公式是:
(x+0) XOR (!x) =x xor !x=0
如果第一个byte不为0,肯定产生进位,考虑第二个byte的最后一个bit。不管这个bit是0还是1,计算公式是:
(x+1)XOR(!x)=!x xor !x=1
这就是上面0??? ???0 ???? ???0 ???? ???0 ???? ????第二个byte的第一个bit是0的来历
同理,第二,三,四个byte中的的第一个bit的0也是在前面所有的byte都不为0的时候才会出现,否则就会出现至少一个1
最后再来看最一个byte的最高位。根据前面的分析,我们已经可以确保前面三个byte为0的pattern。所以我们只需要考虑前面三个byte都不是0,然后检测最后一个byte是否为0的情况。这里分成三种情况来考虑最高一个bit的情况:
1) 最高byte为0
由于前面三个byte都不是0,所以相加后最高byte肯定拿到一个进位,所以最高byte的加法变成了跟7f相加。所以公式:
(0+0) XOR (!0) =1
2) 最高byte不为0,最高bit为0。这种情况下跟7f相加,相加结果最高bit肯定会变成1:
1 XOR (!0) =0
3) 最高byte不为0,最高bit为1。这种情况下跟7f相加,不管相加后最高为是0还是1,都有:
1 XOR (!1) =0
0 XOR (!1) =0
所以,如果EAX最高byte为0,结果的最高bit为1. 如果EAX最高byte不为0,结果最高的bit为0
综上,如果所有四个byte都不为0,最后得到的pattern是:
0??? ???0 ???? ???0 ???? ???0 ???? ????
于是我们可以拿结果跟0x81010100 作TEST运算,当且仅当四个byte都不为0的时候,ZR寄存器的值为0。
大家注意看,我上面的分析有一个错误!
1 XOR (!1) =0
错了,这里应该是1
换句话说,上面的代码无法区分最高一个byte最高bit为0,其他bit为1的情况。这是这种算法的一个死穴。当出现比如0x80112233这样的DWORD的时候,test eax,81010100h 计算的结果跟0x00112233一样。当然最后的结果不会有问题,因为byte_3 -- byte_0里面会再次作判断。所以,如果用一连串的0x80112233作为字符串内容,strcpy的效率会大大下降
谢谢newer2k帮我找到我分析中的错误!
分享到:
相关推荐
网上参考资料写的memcpy以及strcpy的源码,希望能帮助大家。
strcpy原型 笔试题目
编写_strcpy函数 函数原型 char* _strcpy(char *strDest, const char *strSrc)
strcpy函数的编写 C++ VS2010 源代码
C语言字符串复制库函数strcpy和strncpy区别
出现频率最高的笔试题strcpy写法出现频率最高的笔试题strcpy写法出现频率最高的笔试题strcpy写法出现频率最高的笔试题strcpy写法出现频率最高的笔试题strcpy写法出现频率最高的笔试题strcpy写法
编写 strcpy函数
关于strcpy 的解析,对程序员很有用
实现strcpy,strcpy的功能的实现原理
strcpy的详细简绍 关于strcpy的处理方式的简绍和一些相关的习题,以及其简答
strcpy的c语言的实现方法,大家一起学习一起进步!加油!
strcpy,strcmp,strlen,strcat函数的实现过程
嵌入式实验课程中的各项实验如编写strcpy函数: 已知strcpy函数的原型是 char *strcpy(char *strDest, const char *strSrc); 其中strDest是目的字符串,strSrc是源字符串。不调用C++/C的字符串库函数,请编写...
strcpy() 拷贝字符串,它直到发现'\0'字符串结束符才结束,所以,有时候使用它会出现错误。
strcpy函数的用法[总结].pdf
C程序_不调用库函数,实现strcpy函数
不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将...
strcpy,strcat,strcmp,strlen,strchr
strcpy函数的自定义方法(指针、指针的指针、指针的引用等) 希望对大家有帮助
C语言程序设计-用函数实现字符串的复制, 不允许用strcpy()函数.c