第15章 C语言字符串的函数

15.1 strlen()

本章是循环控制语句的具体应用。通常,strlen()函数由循环语句while()语句实现。参照MSVC标准库对strlen()函数的定义方法,我们讨论下述的程序:

int my_strlen (const char * str)
{
        const char *eos = str;

        while( *eos++ ) ;

        return( eos - str - 1 );
}

int main() 
{
        // test
        return my_strlen("hello!");
};
15.1.1 x86

Non-optimizing MSVC

使用MSVC 2010编译上述程序可得到:

_eos$ = -4                            ; size = 4
_str$ = 8                             ; size = 4
_strlen PROC
    push    ebp
    mov     ebp, esp
    push    ecx
    mov     eax, DWORD PTR _str$[ebp] ; 将指针指向字符串
    mov     DWORD PTR _eos$[ebp], eax ; 指向局部变量eos
$LN2@strlen_:
    mov     ecx, DWORD PTR _eos$[ebp] ; ECX=eos

    ; take 8-bit byte from address in ECX and place it as 32-bit value to EDX with sign extension

    movsx   edx, BYTE PTR [ecx]
    mov     eax, DWORD PTR _eos$[ebp] ; EAX=eos
    add     eax, 1                    ; EAX++
    mov     DWORD PTR _eos$[ebp], eax ; EAX还原为EOS
    test    edx, edx                  ; EDX = 0 ?
    je      SHORT $LN1@strlen_        ; yes, then finish loop
    jmp     SHORT $LN2@strlen_        ; continue loop
$LN1@strlen_:
    ; here we calculate the difference between two pointers

    mov    eax, DWORD PTR _eos$[ebp]
    sub    eax, DWORD PTR _str$[ebp]
    sub    eax, 1                     ; subtract 1 and return result
    mov    esp, ebp
    pop    ebp
    ret    0
_strlen_ ENDP

这里出现了两个新指令:MOVSX和TEST。

此处,MOVSX指令从内存中读取8位(单字节)数据,并把它存储到32位寄存器里。MOVSX是MOV with Sign-Extend的缩写。在把小空间数据转换为大空间数据时,存在填充高位数据的问题;本例中,MOVSX将用原始数据的8位数据填充EDX寄存器的低8位;如果原始数据是负数,该指令将使用1填充第8到第31位(高24位),否则使用0填充高24位。

这是为了保证有符号型数据在类型转换后的数值保持不变。

根据C/C++标准,char类型数据是signed(有符号型)数据。现在设想一下把char型数据转换为int型数据(都是有符号型数据)的情况:假如char型数据的原始值是−2(0xFE),直接把整个字节复制到int型数据的最低8位上时,int型数据的值就变成0x000000FE,以有符号型数据的角度看它被转换为254了,而没有保持原始值−2。−2对应的int型数据是0xFFFFFFFE。所以,在把原始数据复制到目标变量之后,还要使用符号标志位填充剩余的数据,而这就是MOVSX的功能。

本书第30章会更为详细地介绍有符号型数据的表示方法。

虽然不太确定寄存器是否有必要分配EDX寄存器专门保存char型数据,看上去它只使用了寄存器的低8位空间(相当于DL)。显然,编译器根据自身的寄存器分配规则进行了相应分配。

您将在后面看到“TEST EDX,EDX”指令。本书会在第19章详细介绍TEST指令。在本例中,它的功能是检查EDX的值是否是零,并设置相应的标志位。

Non-optimizing GCC

使用GCC 4.4.1(未启用优化选项)编译上述程序,可得到:

                 public strlen
strlen           proc near

eos              = dword ptr -4
arg_0            = dword ptr  8

                 push    ebp
                 mov     ebp, esp
                 sub     esp, 10h
                 mov     eax, [ebp+arg_0]
                 mov     [ebp+eos], eax
loc_80483F0:
                 mov     eax, [ebp+eos]
                 movzx   eax, byte ptr [eax]
                 test    al, al
                 setnz   al
                 add     [ebp+eos], 1
                 test    al, al
                 jnz     short loc_80483F0
                 mov     edx, [ebp+eos]
                 mov     eax, [ebp+arg_0]
                 mov     ecx, edx
                 sub     ecx, eax
                 mov     eax, ecx
                 sub     eax, 1
                 leave
                 retn
strlen           endp

GCC编译的结果和MSVC差不多。这里它没有使用MOVSX指令,而是用了MOVZX指令。MOVZX是MOV with Zero-Extent的缩写。在将8位或16位数据转换为32位数据的时候,它直接复制原始数据到目标寄存器的相应低位,并且使用0填充剩余的高位。拆文解字的角度来看,这条指令相当于一步完成了“xor eax, eax”和“mov al,[源8/16位数据]”2条指令。

另一方面,编译器可以生成“mov al, byte ptr [eax] / test al, al”这样的代码,但是这样一来EAX寄存器的高位将会存在随机的噪声。不如说,这就是编译器的短板所在——在它生成汇编代码的时候,它不会照顾汇编代码的(人类)可读性。严格说来,编译器编译出来的代码本来就是给机器运行的,而不是给人阅读的。

本例还出现了未介绍过的SETNZ指令。从前面一条指令开始解释:如果AL的值不是0,则“test al, al”指令会设置标志寄存器ZF=0;而SETNZ(Not Zero)指令会在ZF=0的时候,设置AL=1。用白话解说,就是:如果AL不等于0,则跳到loc_80483F0处。编译器转译出来的代码中,有些代码确实没有实际意义,这是因为我们没有开启优化选项。

Optimizing MSVC

使用MSVC(启用优化选项/Ox /Ob0)编译上述程序,可得到如下所示的指令。

指令清单15.1 Optimizing MSVC 2012 /Ob0

_str$ = 8                                     ; size = 4
_strlen PROC
        mov     edx, DWORD PTR _str$[esp-4]   ;用EDX作字符串指针
        mov     eax, edx                      ;  复制到 EAX

$LL2@strlen:
        mov     cl, BYTE PTR [eax]            ; CL = *EAX
        inc     eax                           ; EAX++
        test    cl, cl                        ; CL==0?
        jne     SHORT $LL2@strlen             ; no, continue loop
        sub     eax, edx                      ; 计算指针的变化量
        dec     eax                           ; decrement EAX
        ret     0
_strlen ENDP

优化编译生成的程序短了很多。不必多说,只有在函数较短且局部变量较少的情况下,编译器才会做出这种程度的优化。

inc/dec指令就是递增、递减指令,换句话说它们相当于运算符“++”“−−”。

Optimizing MSVC + OllyDbg

我们使用OllyDbg打开MSVC优化编译后的可执行文件。程序在进行第一次迭代时的情况如图15.1所示。

..\TU\1501.tif{}

图15.1 OllyDbg:第一次迭代

OllyDbg识别出了循环结构,并且用方括号把整组循环体指令标示了出来。如需OllyDbg在内存窗口里显示对应的数据,可用右键单击EAX寄存器,然后选择“Follow in Dump”,OllyDbg将自动滚动到对应的地址。在内存数据的显示窗口里,我们可以看到字符串“hello!”。字符串会用数值为零的字节做结尾,在零之后的数据就是随机的噪音数据。如果OllyDbg发现某个寄存器的值是指向这片内存地址(某处)的指针,它就会把对应的字符串提示出来。

然后不停地按F8键,等待循环体进入下一次循环。

如图15.2所示,EAX寄存器的值是个指针,它指向字符串的第二个字符的地址。

..\TU\1502.tif{}

图15.2 OllyDbg:第二次迭代

继续按F8键,等待循环语句执行完毕。

如图15.3所示,EAX寄存器里的指针最终指向了数值为零的字符串终止字符。在循环过程中,EDX寄存器的值始终没有发生变化,它一直是字符串首地址的指针。在循环语句结束后,程序即将计算两个指针的差值。

..\TU\1503.tif{}

图15.3 OllyDbg:即将计算指针(地址)之间的差值

把这两个寄存器的值(指针)相减,再减去1,就可得到字符串的长度,如图15.4所示。

..\TU\1504.tif{}

图15.4 OllyDbg:EAX递减

经计算,指针之间的差值为7。实际上我们的字符串“hello!”只有6个字节,算上结束标志字节才是7个字节。很明显字符串以外的那个数值为零的字节不应当纳入字符串的长度,所以函数最后做了递减运算,把这个字节去掉。

Optimizing GCC

使用GCC 4.4.1编译(启用优化选项“-O3”)上述程序,可得到:

                public strlen
strlen          proc near

arg_0           = dword ptr  8

                push    ebp
                mov     ebp, esp
                mov     ecx, [ebp+arg_0]
                mov     eax, ecx

loc_8048418:
                movzx   edx, byte ptr [eax]
                add     eax, 1
                test    dl, dl
                jnz     short loc_8048418
                not     ecx
                add     eax, ecx
                pop     ebp
                retn
strlen          endp

GCC编译的结果和MSVC差不多,主要区别体现在MOVZX指令上。

即使把这条MOVZX指令替换为“mov dl, byte ptr [eax]”也没问题。

GCC编译器的代码生成器这样做,或许是为了便于“记住”整个寄存器已经分配给了char型变量,以保证寄存器的高地址位(bits)不会含有噪音数据。

接下来将要介绍的是NOT指令。NOT指令对操作数的所有位(bit)都进行非运算。可以说,这条指令和XOR ECX, 0xffffffffh指令等价。“not ecx”的结果与某数相加,相当于某数减去ECX和1。在程序开始的时候,ECX保存了字符串首个字符的地址(指针),EAX寄存器存储的是终止符的地址。对ECX求非、再与eax相加,就是在计算eax−ecx−1的值。这种运算可以得到正确的字符串长度。

其中的数学问题,请参见第30章。

换句话说,在执行完循环语句之后,函数进行了如下操作:

ecx=str;
eax=eos;
ecx=(-ecx)-1; 
eax=eax+ecx
return eax

它得到的结果与下述运算完全相同:

ecx=str;
eax=eos;
eax=eax-ecx;
eax=eax-1;
return eax

GCC编译器这么编译代码的具体原因不明。我们能够确定的是,即使GCC和MSVC分别选择不同的算法,计算的结果肯定相同。

15.1.2 ARM

32bit ARM

Non-optimizing Xcode 4.6.3 (LLVM) (ARM mode)

指令清单15.2 Non-optimizing Xcode 4.6.3 (LLVM) (ARM mode)

_strlen
eos  =-8 
str  =-4

     SUB    SP, SP, #8 ; allocate 8 bytes for local variables
     STR    R0, [SP,#8+str]
     LDR    R0, [SP,#8+str]
     STR    R0, [SP,#8+eos]

loc_2CB8 ; CODE XREF: _strlen+28
     LDR    R0, [SP,#8+eos]
     ADD    R1, R0, #1
     STR    R1, [SP,#8+eos]
     LDRSB  R0, [R0]
     CMP    R0, #0
     BEQ    loc_2CD4
     B      loc_2CB8
loc_2CD4 ; CODE XREF: _strlen+24
     LDR    R0, [SP,#8+eos]
     LDR    R1, [SP,#8+str]
     SUB    R0, R0, R1 ; R0=eos-str
     SUB    R0, R0, #1 ; R0=R0-1
     ADD    SP, SP, #8 ; deallocate 8 bytes
     BX     LR

如果不指定优化选项,LLVM编译器所生成的代码会很啰唆。但是这种冗长的代码有助于我们理解它处理局部变量所用的栈结构。本例只用到了2个局部变量,即eos和str。

在IDA的反编译结果中,我把变量var_8重命名为原始变量名eos,把var_4重命名为str。

程序的前几条指令把输入值传递给变量str和eos。

循环体的起始地址是loc_2CB8。

循环体内的前3条指令(LDR,ADD,STR)把eos的值保存在R0寄存器里,然后将这个值递增(+1),再把修改后的值直接赋值给栈内的局部变量eos。

接着“LDRSB RO,[R0]” (Load Register Signed Byte)指令从R0所指向的地址处读取1个字节,并将之转换为32位有符号数据(Keil也把Char型数据视为有符号数据)。这条指令类似于x86的MOVSX指令(参见15.1.1节)。既然在C标准里char类型数据是Signed类型数据,编译器就把这个值当作Signed型数据处理。

应当注意的是,虽然x86系统可以把一个32位寄存器拆分为8位寄存器或16位寄存器单独调用,但是ARM系统没有把寄存器拆解出来、分别使用的助记符。确切地说,x86的这种特性是兼容性的要求:为了运行16位8086指令甚至是8位8080指令,它的指令集必须向下兼容。而ARM系统的处理器最初就是32位RISC处理器。所以,在使用ARM系统的寄存器时,只能把它当作完整的32位寄存器使用。

此后,LDRSB指令把字符串中的字符逐字节地传递到R0寄存器。其后的CMP和BEQ指令,会检查这个字节是不是零字节。如果这个字节不是0,则再次进行循环;如果这个字节是0,则结束循环语句。

函数在结束以前计算eos和str的差值,再把这个差值减去1,然后作为函数的返回值、保存在R0寄存器里。

整个函数没有把寄存器推送入栈的操作。按照ARM调用函数的约定,R0~R3寄存器的作用是传递参数的暂存寄存器;函数在退出以后它们已经完成使命了,也不必恢复它们的初始值。在被调用方函数结束之后,再怎么操作它们都行。另外,这个程序没有用到其他的寄存器,也没必要使用栈。所以在函数结束时,唯一需要做的工作就是使用跳转指令(BX)把控制权交给LR寄存器保存的返回地址。

Optimizing Xcode 4.6.3 (LLVM) (Thumb mode)

指令清单15.3 Optimizing Xcode 4.6.3 (LLVM) (Thumb mode)

_strlen
           MOV       R1, R0

loc_2DF6
           LDRB.W    R2, [R1],#1
           CMP       R2, #0
           BNE       loc_2DF6
           MVNS      R0, R0
           ADD       R0, R1
           BX        LR

在进行优化编译的时候,编译器认为寄存器已经足够用了,不必使用栈来保管变量eos和str。在开始循环之前,编译器使用R0寄存器存储变量str、用R1寄存器存储变量eos。

“LDRB.W R2, [R1],#1”从R1所指向的地址里读取1个字节,将其转换为32位有符号数据(signed)之后存储在R2寄存器里。指令末端的立即数#1将在上述操作之后,把R1寄存器的值加1(递增)。这种指令属于延迟索引寻址(Post-indexed address,又称后变址寻址)指令,便于操作数组。

本书的28.2节会详细介绍延迟索引寻址。

循环体的CMP和BNE指令负责判断循环结束的条件。它们在读取到数值为零的字节之前会保证循环语句处于的迭代状态。

MVNS(MoVe Not)指令相当于x86指令集中的NOT指令,与后面的ADD指令配合完成“eos-str-1”的运算。在15.1.1节里,我们详细介绍过其中的各种细节,这里不再复述。

LLVM编译器与GCC都认为这种代码的效率更高。

Optimizing Keil 6/2013 (ARM mode)

使用Keil(启用优化选项)编译上述程序,可得到如下所示的指令。

指令清单15.4 Optimizing Keil 6/2013 (ARM mode)

_strlen
           MOV   R1, R0

loc_2C8
           LDRB  R2, [R1],#1
           CMP   R2, #0
           SUBEQ R0, R1, R0
           SUBEQ R0, R0, #1
           BNE   loc_2C8
           BX    LR

这段代码与前面的LLVM优化编译生成的Thumb代码相似。区别在于前面的例子在循环结束后才运算str−eos−1,而本例则是在循环体内进行表达式演算。前文介绍过,条件执行指令中的-EQ后缀表示其运行条件为“当前面的CMP比较的两个值相等/EQ时,才会执行该指令”。所以,如果R0寄存器的值是0,则会触发CMP指令之后的两条SUBEQ指令。其运算结果会被保留在R0寄存器,迭代结束之后就自然成为函数的返回值。

ARM64

Optimizing GCC (Linaro) 4.9

my_strlen:
        mov     x1, x0
        ; X1 is now temporary pointer (eos), acting like cursor
.L58:
        ; load byte from X1 to W2, increment X1 (post-index)
        ldrb    w2, [x1],1
        ; Compare and Branch if NonZero: compare W2 with 0, jump to .L58 if it is not
        cbnz    w2, .L58
        ; calculate difference between initial pointer in X0 and current address in X1
        sub     x0, x1, x0
        ; decrement lowest 32-bit of result
        sub     w0, w0, #1
        ret

本例的算法与指令清单15.11的算法相同。它计算首字符和终止符地址的差值,然后再从差里减去1。指令清单中的注释详细介绍了具体的演算方法。不过,我的源程序有问题:my_strlen()的返回值是32位int型数据,但是它应当返回size_t或者另外一种64位数据。理论上讲,在64位平台上,strlen()函数的参数地址可能是4GB以上的内存地址,所以它在64位平台上的返回值应当是64位数据。由于源程序存在这个缺陷,所以最后一条SUB指令只对寄存器的低32位进行操作,但是倒数第二条SUB指令依然是对完整的64位寄存器进行减法运算。虽说程序存在缺陷,但是出于演示的目的,我还是把这个样本保留了下来。

Non-optimizing GCC (Linaro) 4.9

my_strlen:
; function prologue
        sub      sp, sp, #32
; first argument (str) will be stored in [sp,8]
        str      x0, [sp,8]
        ldr      x0, [sp,8]
; copy "str" to "eos" variable
        str      x0, [sp,24]
        nop 
.L62:
; eos++
        ldr      x0, [sp,24]  ; load "eos" to X0
        add      x1, x0, 1    ; increment X0
        str      x1, [sp,24]  ; save X0 to "eos"
; load byte from memory at address in X0 to W0
        ldrb     w0, [x0]
; is it zero? (WZR is the 32-bit register always contain zero)
        cmp      w0, wzr
; jump if not zero (Branch Not Equal)
        bne      .L62
; zero byte found. now calculate difference. 
; load "eos" to X1
        ldr      x1, [sp,24]
; load "str" to X0
        ldr      x0, [sp,8]
; calculate difference
        sub      x0, x1, x0
; decrement result
        sub      w0, w0, #1
; function epilogue
        add      sp, sp, 32
        ret

关闭优化功能之后,编译器生成的代码就长了许多。在操作变量时,程序频繁地访问内存中的栈。此外,由于源程序的设计缺陷,最后一条SUB指令只对寄存器的低32位数据进行了减法运算。

15.1.3 MIPS

指令清单15.5 Optimizing GCC 4.4.5 (IDA)

my_strlen:
; "eos" variable will always reside in $v1:
                move    $v1, $a0
loc_4:
; load byte at address in "eos" into $a1:
                lb      $a1, 0($v1)
                or      $at, $zero ; load delay slot, NOP
; if loaded byte is not zero, jump to loc_4:
                bnez    $a1, loc_4
; increment "eos" anyway:
                addiu   $v1, 1 ; branch delay slot 
; loop finished. invert "str" variable:
                nor     $v0, $zero, $a0
; $v0=-str-1
                jr      $ra
; return value = $v1 + $v0 = eos + ( -str-1 ) = eos - str - 1
                addu    $v0, $v1, $v0 ; branch delay slot

MIPS的指令集里没有求非(NOT)运算指令,但是它有非或NOR(即OR+NOT)指令。在数字电路领域,非或运算电路十分普遍;但是在计算机编程领域,它还比较冷门。借助非或运算指令,求非的NOT运算指令可由“NOR DST,$ZERO,SRC”指令变相实现。

前文介绍过,求非运算相当于“求负、再减1”的运算。与后面的ADDU指令配合,可完成“eos−str−1”的运算,求得正确的字符串长度。

15.2 练习题

15.2.1 题目1

请描述下列代码的功能。

指令清单15.6 Optimizing MSVC 2010

_s$   =  8
_f    PROC
           mov  edx, DWORD PTR _s$[esp-4]
           mov  cl, BYTE PTR [edx]
           xor  eax, eax
           test cl, cl
           je   SHORT $LN2@f
           npad 4    ; align next label
$LL4@f:
           cmp  cl, 32
           jne  SHORT $LN3@f
           inc  eax
$LN3@f:
           mov  cl, BYTE PTR [edx+1]
           inc  edx
           test cl, cl
           jne  SHORT $LL4@f
$LN2@f:
           ret  0
_f         ENDP

指令清单15.7 GCC 4.8.1 -O3

f:
.LFB24:
        push      ebx
        mov       ecx, DWORD PTR [esp+8]
        xor       eax, eax
        movzx     edx, BYTE PTR [ecx]
        test      dl, dl
        je        .L2
.L3:
        cmp       dl, 32
        lea       ebx, [eax+1]
        cmove     eax, ebx
        add       ecx, 1
        movzx     edx, BYTE PTR [ecx]
        test      dl, dl
        jne       .L3
.L2:
        pop       ebx
        ret

指令清单15.8 Optimizing Keil 6/2013 (ARM mode)

f   PROC
        MOV     r1,#0
|L0.4|
        LDRB    r2,[r0,#0]
        CMP     r2,#0
        MOVEQ   r0,r1
        BXEQ    lr
        CMP     r2,#0x20
        ADDEQ   r1,r1,#1
        ADD     r0,r0,#1
        B       |L0.4|
        ENDP

指令清单15.9 Optimizing Keil 6/2013 (Thumb mode)

f PROC
        MOVS    r1,#0
        B       |L0.12|
|L0.4|
        CMP     r2,#0x20
        BNE     |L0.10|
        ADDS    r1,r1,#1
|L0.10|
        ADDS    r0,r0,#1
|L0.12|
        LDRB    r2,[r0,#0]
        CMP     r2,#0
        BNE     |L0.4|
        MOVS    r0,r1
        BX      lr
        ENDP

指令清单15.10 Optimizing GCC 4.9 (ARM64)

f:
        ldrb    w1, [x0]
        cbz     w1, .L4
        mov     w2, 0
.L3:
        cmp     w1, 32
        ldrb    w1, [x0,1]!
        csinc   w2, w2, w2, ne
        cbnz    w1, .L3
.L2:
        mov     w0, w2
        ret 
.L4:
        mov     w2, w1
        b       .L2

指令清单15.11 Optimizing GCC 4.4.5 (MIPS) (IDA)

f:
                lb         $v1, 0($a0)
                or         $at, $zero
                beqz       $v1, locret_48 
                li         $a1,0x20#''
                b          loc_28
                move       $v0, $zero
loc_18:                                       # CODE XREF: f:loc_28
                lb         $v1, 0($a0)
                or         $at, $zero
                beqz       $v1, locret_40
                or         $at, $zero
loc_28:                                       # CODE XREF: f+10
                                              # f+38
                bne        $v1, $a1, loc_18
                addiu      $a0, 1
                lb         $v1, 0($a0)
                or         $at, $zero
                bnez       $v1, loc_28
                addiu      $v0, 1
locret_40:                                    # CODE XREF: f+20
                jr         $ra
                or         $at, $zero
locret_48:                                    # CODE XREF: f+8
                jr         $ra
                move       $v0, $zero