【老刘谈算法】直接从内存中找答案——字符串转双字函数分析(3)

a2dw.asm

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

    ; --------------------------------------
    ; This procedure was written by Iczelion
    ; --------------------------------------

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

      include \MASM32\INCLUDE\kernel32.inc

    .code

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

a2dw proc uses ecx edi edx esi String:DWORD

      ;----------------------------------------
      ; Convert decimal string into dword value
      ; return value in eax
      ;----------------------------------------

      xor ecx, ecx
      mov edi, String
      invoke lstrlen, String	;在前面清空ecx是没用的,WinApi可能改变ecx、edx的值

      .while eax != 0
        xor edx, edx
        mov dl, byte ptr [edi]
        sub dl, "0" ; subtrack each digit with "0" to convert it to hex value
        mov esi, eax
        dec esi
        push eax
        mov eax, edx	;ascii对应的byte
        push ebx
        mov ebx, 10
          .while esi > 0	;num*10^esi
            mul ebx	;结果到eax(低位),edx(高位)中
            dec esi
          .endw
        pop ebx
        add ecx, eax		;ecx储存结果
        pop eax
        inc edi
        dec eax
      .endw

        mov eax, ecx
        ret

a2dw endp

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

end

以前听罗老师说不建议用masm32自带的宏、lib,可能有各种奇葩错误,我还不大相信,直到我看到了这个函数。
这个函数看着工工整整,算法的可行性也在上一篇分析过了,但其实完全无法工作。
为什么呢?请看第24、26行,
为了使ecx储存结果,函数在调用winAPI之前将ecx清零,
但这么做其实是徒劳的,WinAPI执行后,ebx、edi、esi和ebp的值总是不会被改变的,但 ecx 和 edx 的值有极大几率被改变。(同时这也是win对api调用的callback的要求)
这就导致ecx有了一个未知的初始值,导致累加发生在一个未知值的基础上,最终得到了没有任何意义的返回值。

atodw.asm

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

  ; ---------------------------------------------------------------
  ;      本程序最初由 Tim Roberts 编写
  ;
  ; 	Alexander Yackubtchik 优化了部分代码
  ; ---------------------------------------------------------------

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

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

atodw proc String:DWORD

  ; ----------------------------------------
  ; 十进制转dword
  ; eax储存返回值
  ; ----------------------------------------

    push esi
    push edi

    xor eax, eax
    mov esi, [String]
    xor ecx, ecx
    xor edx, edx
    mov al, [esi]
    inc esi
    cmp al, 2D	;检测负号
    jne proceed	;不是负号就跳转
    mov al, byte ptr [esi]
    not edx	;FFFFFFFF
    inc esi
    jmp proceed

  @@: 
    sub al, 30h	;ascii->byte
    lea ecx, dword ptr [ecx+4*ecx]	;ecx*=5
	lea ecx, dword ptr [eax+2*ecx]	;ecx=ecx*2+eax
    mov al, byte ptr [esi]
    inc esi

  proceed:
    or al, al
    jne @B	;非0(没处理完)上跳
    lea eax, dword ptr [edx+ecx]
    xor eax, edx

    pop edi
    pop esi

    ret

atodw endp

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

end

这个函数支持有符号数,好评。

补码

补码是当今广泛使用的有符号数编码规则,
负数表示为其绝对值表示的正数按位取反再+1(或-1后按位取反),
补码的优点是用无符号数规则进行有符号数加减计算,结果仍满足补码规则,且符合数学运算规定。

代码亮点:灵活的使用xor和lea

这个函数对有符号数的处理可谓颇为巧妙,
若字符串的第一个符号不是“-”,函数会将其按照正数处理,令edx为0,
在执行到49行时,ecx中就储存了正确的结果,而由于edx为0,不会改变ecx的值,就相当于执行了eax=ecx+0,eax中储存正确的结果。
由于0 xor any=any,下一行的xor不会改变eax的值。
若字符串的第一个符号是“-”,edx将会=0xFFFFFFFF,
这样,49行会使eax-=1,
由于edx的所有二进制位均为1,所以any xor edx=not any,50行实际上将eax进行了按位取反操作,
这样,eax正好满足补码规则,被顺利的转换为负数。

39~45行《字符串转双字函数分析(1)》已经做了详细讨论,不再赘述。

a2dw_ex.asm

; ?

    .486                      ; force 32 bit code
    .model flat, stdcall      ; memory model & calling convention
    option casemap :none      ; case sensitive

    EXTERNDEF decade :DWORD

    .code

; ?

align 4	;使指令从4整数倍的内存地址开始以加快速度。

atodw_ex proc lpstring:DWORD

    mov [ebp+12], edi	;备份edi

  ; ----------------------------------------------------
  ; 用展开的strlen函数测试12个byte中是否有0。
  ; ----------------------------------------------------
    mov eax,lpstring                    
    lea edx,[eax+3]                     ; pointer+3 used in the end

    mov edi,[eax]                       ; read first 4 bytes
    add eax,4                           ; increment pointer
    lea ecx,[edi-01010101h]             ; subtract 1 from each byte
    not edi                             ; invert all bytes
    and ecx,edi                         ; and these two
    and ecx,80808080h
    jnz @F

    mov edi,[eax]                       ; read next 4 bytes
    add eax,4                           ; increment pointer
    lea ecx,[edi-01010101h]             ; subtract 1 from each byte
    not edi                             ; invert all bytes
    and ecx,edi                         ; and these two
    and ecx,80808080h
    jnz @F

    mov edi,[eax]                       ; read last 4 bytes
    add eax,4                           ; increment pointer
    lea ecx,[edi-01010101h]             ; subtract 1 from each byte
    not edi                             ; invert all bytes
    and ecx,edi                         ; and these two
    and ecx,80808080h

  @@:
    test ecx,00008080h                  ; test first two bytes
    jnz @F
    shr ecx,16                          ; not in the first 2 bytes
    add eax,2
  @@:
    shl cl,1                            ; use carry flag to avoid branch
    sbb eax,edx                         ; compute length
  ; -------------------------------------------

    mov edi, eax                        ; EDI放字符串长度
    mov edx, lpstring
    sub edx, 1	;使得edx+edi刚好可以指向最后一个字符

    xor eax, eax

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+40]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+80]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+120]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+160]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+200]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+240]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+280]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+320]
    sub edi, 1
    jz atout

    movzx ecx, BYTE PTR [edx+edi]
    add eax, [ecx*4+decade-192+360]

  atout:

    mov edi, [ebp+12]

    ret

atodw_ex endp

; ?

end

masm32的lib帮助文件中居然说这个函数没有返回值(黑人问号脸),其实是有的(要不咱执行这个函数图个什么),在eax中。

dectbl.asm

; ?

    .486                      ; force 32 bit code
    .model flat, stdcall      ; memory model & calling convention
    option casemap :none      ; case sensitive

    PUBLIC decade

  .data
    align 16	;使数据从16整数倍的内存地址开始以加快速度。
    decade \
      dd 0,1,2,3,4,5,6,7,8,9
      dd 0,10,20,30,40,50,60,70,80,90
      dd 0,100,200,300,400,500,600,700,800,900
      dd 0,1000,2000,3000,4000,5000,6000,7000,8000,9000
      dd 0,10000,20000,30000,40000,50000,60000,70000,80000,90000
      dd 0,100000,200000,300000,400000,500000,600000,700000,800000,900000
      dd 0,1000000,2000000,3000000,4000000,5000000,6000000,7000000,8000000,9000000
      dd 0,10000000,20000000,30000000,40000000,50000000,60000000,70000000,80000000,90000000
      dd 0,100000000,200000000,300000000,400000000,500000000,600000000,700000000,800000000,900000000
      dd 0,1000000000,2000000000,3000000000,4000000000,0,0,0,0,0

    end

; ?

从文件名就能看出,这个asm里面有十进制(dec)的表(tbl)。有什么用呢?请看下文。

代码亮点:极致高效

牺牲空间换效率

由于返回值的最大值为0xFFFFFFFF,即无符号数4294967295,所以string的长度应<=10,
由于是使用位运算来一次判断4个byte,所以只需要三次就能达到要求,为了提高效率,此代码采用了重复代码的方式,避免了多余的跳转。
一次判断4个byte的分析可见《老刘谈算法001》,不再赘述。

直接查表取结果

在执行到64行时,ecx中得到的是字符串的最后一个字符(个位)的ascii码,下面的一条指令却难以理解,add eax, [ecx*4+decade-192]是什么意思呢?
观察dectbl.asm中decade的定义,发现其共有10行,从个位向高位递增,每列都有10个dword数据,其最高位从0~9递增,超过dword无符号范围的数则被定义成0。
ecx中的值经过*4后,得到的是4x30H+4x(ascii对应的数),而4x30H正好=192,即那行指令中的-192是为了将ascii码转为byte,
这样,由于dword为4字节,[ecx*4+decade-192]就能正确将ascii码对应到表中第一行的数据。
同理,70行的decade+40将起始地址指向了表中的第二行,正好ecx中储存的是string中的十位对应的ascii码。
该算法虽浪费了一些空间,但免去了10的幂的计算,换得了实在的效率。

调用方法

由于该代码在第17行需要用到[ebp+12],即调用函数前的[esp],
所以需要这样调用才能避免函数执行后[esp]被改变。

Sub Esp,4
Invoke atodw_ex,...
Add Esp,4

其它

  • 这是字符串转双字函数分析的最后一篇。
  • lz才疏学浅,若有不足,请不吝赐教;若有错误,请指出。
上一篇:【老刘谈算法】这位运算玩的真溜—strlen函数的汇编实现分析


下一篇:rdi