kmp代码编译分析
//下面是kmp算法
//*********************************************************//
void get_next(char* s,int* next) //s表示模式串，next表示next数组的头指针
{
int length=strlen(s);
int i=1,j=0;
//i表示模式串的每一个元素的指针，每次加1递增，j表示前缀串中，每一个元素的位置。
next=-1;
for(;i<length;i++){ //开始递归模式串中每一个元素
if(s==s){ //如果当前元素和前缀的第一个元素相等，表示开始匹配前缀和后缀串，j++表示前缀的下一个位置的元素。
next=j; //同时把当前next设置成为前缀中的位置。
j++;
}else{ //当前位置和前缀串中的不一致，
if(s==s){ //如果当前位置和前缀串中的第一个元素相同，那么表示又重新开始匹配新一轮后缀
next=0; //重新开始匹配后缀，所以next的值是0，表示前缀的第一个元素的位置
j=1; //前缀的指针变成下一个位置
}
else{ //如果当前位置和第一个位置的元素也不相同，表示没有这样的以这个元素为前缀的字符串，把这个next值变成-1.
next=-1;
j=0;
}
}
}
}
//target是目标串，s是模式串，data是next数组
void find(char *target,char *s,int* data){
int i=0; //i是目标串的指针
int j=0; //j是模式串的指针
for(;i<strlen(s);){
if(s==target){ //如果模式串和目标串匹配
if(j==strlen(target)-1){//如果完全匹配，就说明在目标串中找到了模式串
printf("start:%d\n",i-j+1);
break;
}else{
j++;//否则继续比较下一个字符
i++;
}
}else{ //如果这两个字符不匹配
if(j==0||data==-1){ //如果是和模式串的第一个字符做匹配失败，或者next数组的前一个值是-1，表示前一个位置的后缀，在当前模式串中找不到前缀，所以这时，i指针需要向前移动，
j=0;
i++;
}else{ //表示匹配前缀的后一个位置的元素。
j=data+1;
}
}
}
}
这个代码表面看起来没有什么问题，但编译的时候就出问题了。
我们看看编译后的void find(char *target,char *s,int* data) 函数
00401430/$53 push ebx
00401431|.8B5C24 0C mov ebx, dword ptr
00401435|.55 push ebp
00401436|.56 push esi
00401437|.57 push edi
00401438|.8BFB mov edi, ebx
0040143A|.83C9 FF or ecx, 0xFFFFFFFF
0040143D|.33C0 xor eax, eax
0040143F|.33F6 xor esi, esi
00401441|.33D2 xor edx, edx
00401443|.F2:AE repne scas byte ptr es: ;垃圾代码
00401445|.F7D1 not ecx ;垃圾代码
00401447|.49 dec ecx ;垃圾代码
00401448|.74 60 je short 004014AA ;垃圾代码
0040144A|.8B6C24 14 mov ebp, dword ptr
0040144E|>8A041E /mov al, byte ptr
00401451|.8A0C2A |mov cl, byte ptr
00401454|.3AC1 |cmp al, cl
00401456|.75 15 |jnz short 0040146D
00401458|.8BFD |mov edi, ebp
0040145A|.83C9 FF |or ecx, 0xFFFFFFFF
0040145D|.33C0 |xor eax, eax
0040145F|.F2:AE |repne scas byte ptr es:
00401461|.F7D1 |not ecx
00401463|.83C1 FE |add ecx, -0x2
00401466|.3BD1 |cmp edx, ecx
00401468|.74 2F |je short 00401499
0040146A|.42 |inc edx
0040146B|.EB 16 |jmp short 00401483
0040146D|>85D2 |test edx, edx
0040146F|.74 10 |je short 00401481
00401471|.8B4C24 1C |mov ecx, dword ptr
00401475|.8B5491 FC |mov edx, dword ptr
00401479|.83FA FF |cmp edx, -0x1
0040147C|.74 03 |je short 00401481
0040147E|.42 |inc edx
0040147F|.EB 03 |jmp short 00401484
00401481|>33D2 |xor edx, edx
00401483|>46 |inc esi
00401484|>8BFB |mov edi, ebx ;垃圾代码
00401486|.83C9 FF |or ecx, 0xFFFFFFFF ;垃圾代码
00401489|.33C0 |xor eax, eax ;垃圾代码
0040148B|.F2:AE |repne scas byte ptr es: ;垃圾代码
0040148D|.F7D1 |not ecx ;垃圾代码
0040148F|.49 |dec ecx ;垃圾代码
00401490|.3BF1 |cmp esi, ecx ;垃圾代码
00401492|.^ 72 BA \jb short 0040144E
00401494|.5F pop edi
00401495|.5E pop esi
00401496|.5D pop ebp
00401497|.5B pop ebx
00401498|.C3 retn
这样的后果就是程序遇到0x00就会退出比较。
将那些垃圾代码删除即可，修改如下：
00401430/$53 push ebx
00401431|.8B5C24 0C mov ebx, dword ptr
00401435|.55 push ebp
00401436|.56 push esi
00401437|.57 push edi
00401438|.8BFB mov edi, ebx
0040143A|.83C9 FF or ecx, 0xFFFFFFFF
0040143D|.33C0 xor eax, eax
0040143F|.33F6 xor esi, esi
00401441|.33D2 xor edx, edx
00401443 90 nop ;垃圾代码
00401444 90 nop
00401445 90 nop ;垃圾代码
00401446 90 nop
00401447 90 nop ;垃圾代码
00401448 90 nop ;垃圾代码
00401449 90 nop
0040144A|.8B6C24 14 mov ebp, dword ptr
0040144E|>8A041E /mov al, byte ptr
00401451|.8A0C2A |mov cl, byte ptr
00401454|.3AC1 |cmp al, cl
00401456|.75 15 |jnz short 0040146D
00401458|.8BFD |mov edi, ebp
0040145A|.83C9 FF |or ecx, 0xFFFFFFFF
0040145D|.33C0 |xor eax, eax
0040145F|.F2:AE |repne scas byte ptr es:
00401461|.F7D1 |not ecx
00401463|.83C1 FE |add ecx, -0x2
00401466|.3BD1 |cmp edx, ecx
00401468|.74 2F |je short 00401499
0040146A|.42 |inc edx
0040146B|.EB 16 |jmp short 00401483
0040146D|>85D2 |test edx, edx
0040146F|.74 10 |je short 00401481
00401471|.8B4C24 1C |mov ecx, dword ptr
00401475|.8B5491 FC |mov edx, dword ptr
00401479|.83FA FF |cmp edx, -0x1
0040147C|.74 03 |je short 00401481
0040147E|.42 |inc edx
0040147F|.EB 03 |jmp short 00401484
00401481|>33D2 |xor edx, edx
00401483|>46 |inc esi
00401484|>8BFB |mov edi, ebx ;垃圾代码
00401486 ^ EB C6 jmp short 0040144E ;垃圾代码
00401488 90 nop
00401489 90 |nop ;垃圾代码
0040148A 90 nop
0040148B 90 |nop ;垃圾代码
0040148C 90 nop
0040148D 90 |nop ;垃圾代码
0040148E 90 nop
0040148F 90 |nop ;垃圾代码
00401490 90 |nop ;垃圾代码
00401491 90 nop
00401492 90 \nop
00401493 90 nop
00401494|.5F pop edi
00401495|.5E pop esi
00401496|.5D pop ebp
00401497|.5B pop ebx
00401498|.C3 retn
00401499|>2BF2 sub esi, edx
0040149B|.46 inc esi
0040149C|.56 push esi
0040149D|.68 B0704200 push 004270B0 ;start:%d\n
004014A2|.E8 18210100 call 004135BF
004014A7|.83C4 08 add esp, 0x8
004014AA|>5F pop edi
004014AB|.5E pop esi
004014AC|.5D pop ebp
004014AD|.5B pop ebx
004014AE\.C3 retn
至于速度是确实一般！
看来那些垃圾代码确实是strlen，那个代码之前是字符串查找的，而strlen遇到0x00会停止。
我将其改成hex查找，所以出错。
现在修正一下就可以用了：
{:soso_e100:}/...你把char 换成 unsigned char
len 传进来不就好了？ 本帖最后由 menglv 于 2015-6-4 09:53 编辑
//下面是kmp算法，可以查找hex
//*********************************************************//
void get_next(char* s,int* next,int length) //s表示模式串，next表示next数组的头指针
{
//int length=strlen(s);
int i=1,j=0;
//i表示模式串的每一个元素的指针，每次加1递增，j表示前缀串中，每一个元素的位置。
next=-1;
for(;i<length;i++){ //开始递归模式串中每一个元素
if(s==s){ //如果当前元素和前缀的第一个元素相等，表示开始匹配前缀和后缀串，j++表示前缀的下一个位置的元素。
next=j; //同时把当前next设置成为前缀中的位置。
j++;
}else{ //当前位置和前缀串中的不一致，
if(s==s){ //如果当前位置和前缀串中的第一个元素相同，那么表示又重新开始匹配新一轮后缀
next=0; //重新开始匹配后缀，所以next的值是0，表示前缀的第一个元素的位置
j=1; //前缀的指针变成下一个位置
}
else{ //如果当前位置和第一个位置的元素也不相同，表示没有这样的以这个元素为前缀的字符串，把这个next值变成-1.
next=-1;
j=0;
}
}
}
}
//target是目标串，s是模式串，data是next数组
void find(char *target,char *s,int* data,int l,int l2){
//l 为文件长度，l2 为特征码长度
int i=0; //i是目标串的指针
int j=0; //j是模式串的指针
for(;i<l;){
if(s==target){ //如果模式串和目标串匹配
if(j==l2-1){//如果完全匹配，就说明在目标串中找到了模式串
printf("start:%d\n",i-j+1);
break;
}else{
j++;//否则继续比较下一个字符
i++;
}
}else{ //如果这两个字符不匹配
if(j==0||data==-1){ //如果是和模式串的第一个字符做匹配失败，或者next数组的前一个值是-1，表示前一个位置的后缀，在当前模式串中找不到前缀，所以这时，i指针需要向前移动，
j=0;
i++;
}else{ //表示匹配前缀的后一个位置的元素。
j=data+1;
}
}
}
}
飘云 发表于 2015-6-4 09:46
/...你把char 换成 unsigned char
len 传进来不就好了？
主要是strlen遇到0x00就会截止，所以我将len传进来就可以了，char倒是无所谓。
menglv 发表于 2015-6-4 09:52
主要是strlen遇到0x00就会截止，所以我将len传进来就可以了，char倒是无所谓。
.。不用strlen啊，，len外部算好~~ 随便改改源代码就OK了
页:
[1]