首页
社区
课程
招聘
[原创]【老刘谈算法002】反向快速比较——instring函数的汇编实现分析
发表于: 2018-7-9 14:27 3049

[原创]【老刘谈算法002】反向快速比较——instring函数的汇编实现分析

2018-7-9 14:27
3049
挂下代码先,
;注释修改&中文注释添加 by 老刘

; #########################################################################

;       这个算法的子循环代码被EKO重新设计来反向执行比较,
;       这种比较方法通过分支比较减少了需要执行的指令数。

; #########################################################################

    .486
    .model flat, stdcall  ; 32 bit memory model
    option casemap :none  ; case sensitive

    StrLen PROTO :DWORD

    .code

; ########################################################################

InString proc startpos:DWORD,lpSource:DWORD,lpPattern:DWORD

  ; ------------------------------------------------------------------
  ; InString函数在一个更大的“源字符串”中寻找“匹配字符串”,
  ; 如果找到了的话,“匹配字符串”在“源字符串”的位置会被放在eax中。 
  ;
  ; "StartPos"即“起始位”参数和返回值均使用1来作为首个字符的索引。
  ; (第一个字符是1,第二个字符是2,等等……)
  ; 
  ;
  ; 返回值:
  ; 如果函数执行成功,它将会返回“源字符串”的位置。
  ;  0 = 没找着
  ; -1 = “匹配字符串”的长度不短于“源字符串”
  ; -2 = "StartPos"参数越界。
  ; ------------------------------------------------------------------

    LOCAL sLen:DWORD
    LOCAL pLen:DWORD

    push ebx
    push esi
    push edi

    invoke StrLen,lpSource
    mov sLen, eax           ;源字符串长度
    invoke StrLen,lpPattern
    mov pLen, eax           ;匹配字符串长度

    cmp startpos, 1
    jge @F
    mov eax, -2
    jmp isOut               ;如果“起始位”参数为0则退出。
  @@:

    dec startpos            ;改成0为第一个字符的索引。

    cmp  eax, sLen			;这里的eax依旧=pLen
    jl @F
    mov eax, -1
    jmp isOut               ;匹配字符串不短于源字符串,退出。
  @@:

    sub sLen, eax           ;sLen-=pLen源字符串去尾
    inc sLen

    mov ecx, sLen
    cmp ecx, startpos
    jg @F
    mov eax, -2
    jmp isOut               ;不可能匹配上,退出
  @@:

  ; ----------------
  ; setup loop code
  ; ----------------
    mov esi, lpSource
    mov edi, lpPattern
    mov al, [edi]           ;al=匹配字符串中的第一个字符

    add esi, ecx            ;源字符串地址加上源字符串长(使esi指向源字符串末尾,以便倒序比较)
    neg ecx                 ;ecx=-ecx
    add ecx, startpos       ;加上起始位参数

    jmp Scan_Loop

    align 16		;使下条指令的地址从0x10倍数处开始,提升速度

  ; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

  Pre_Scan:
    inc ecx

  Scan_Loop:
    cmp al, [esi+ecx]       ;判断esi+ecx指向的第一个字符是否=匹配字符串中的第一个字符
    je Pre_Match            ;如果匹配,则跳到Pre_Match继续判断
    inc ecx
    js Scan_Loop            ;ecx为负时继续循环

    jmp No_Match

  Pre_Match:
    lea ebx, [esi+ecx]      ;ebx=第一个匹配的字符的地址
    mov edx, pLen

  Test_Match:
    mov ah, [ebx+edx-1]     ;ah=ebx+edx-1指向的字符
    cmp ah, [edi+edx-1]     ;与匹配字符串中对应的字符比较
    jne Pre_Scan            ;不匹配,跳到Pre_Scan
    dec edx
    jnz Test_Match          ;edx非0时继续倒序循环判断

  ; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

  Match:
    add ecx, sLen
    mov eax, ecx
    inc eax
    jmp isOut
    
  No_Match:
    xor eax, eax

  isOut:
    pop edi
    pop esi
    pop ebx

    ret

InString endp

; ########################################################################

    end
那么什么条件下可以直接判断不可能匹配呢?
我们设
a=startpos
b=sLen
c=pLen
令d=b-(a-1)
则d即为实际需要进行查找的字符串的长度,
那么当被查找的字符串长小于需要查找的字符串长度的时候,即
当(a-1)+c>b的时候,
显然不可能匹配上,
作者可谓考虑的十分周到了。

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 1
支持
分享
打赏 + 2.00雪花
打赏次数 1 雪花 + 2.00
 
赞赏  junkboy   +2.00 2018/07/09
最新回复 (7)
雪    币: 19
活跃值: (1086)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
短小精悍,不错
2018-7-9 15:10
0
雪    币: 12848
活跃值: (9142)
能力值: ( LV9,RANK:280 )
在线值:
发帖
回帖
粉丝
3
看毛片算法了解一下
2018-7-9 15:20
0
雪    币: 171
活跃值: (514)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
4
过来顶一下老刘!!!
2018-7-9 15:48
0
雪    币: 11716
活跃值: (133)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
hzqst 看毛片算法了解一下

看毛片的拍黄片实现

2018-7-9 16:00
0
雪    币: 10915
活跃值: (2880)
能力值: ( LV5,RANK:71 )
在线值:
发帖
回帖
粉丝
6
是sunday算法吗
2018-7-10 09:39
0
雪    币: 2058
活跃值: (1601)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
精辟,厉害了。学习了,
2018-7-10 11:15
0
雪    币: 2359
活跃值: (523)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
joker陈 是sunday算法吗
抱歉,没研究过,不太清楚
2018-7-11 12:18
0
游客
登录 | 注册 方可回帖
返回
//