第47章 字符串剪切

我们经常需要去除字符串里的开始符号或者结束符号。

本章介绍的程序,专门用于去除字符串的结尾部分的回车和换行字符CR/LF。

#include <stdio.h>
#include <string.h>

char* str_trim (char *s)
{
         char c;
         size_t str_len;

         // work as long as \r or \n is at the end of string
         // stop if some other character there or its an empty string'
         // (at start or due to our operation)
         for (str_len=strlen(s); str_len>0 && (c=s[str_len-1]); str_len--)
         {
                   if (c=='\r' || c=='\n')
                             s[str_len-1]=0;
                   else
                             break;
         };
         return s;
};

int main()
{
         // test

         // strdup() is used to copy text string into data segment,
         // because it will crash on Linux otherwise,
         // where text strings are allocated in constant data segment,
         // and not modifiable.

         printf ("[%s]\n", str_trim (strdup("")));
         printf ("[%s]\n", str_trim (strdup("\n")));
         printf ("[%s]\n", str_trim (strdup("\r")));
         printf ("[%s]\n", str_trim (strdup("\n\r")));
         printf ("[%s]\n", str_trim (strdup("\r\n")));
         printf ("[%s]\n", str_trim (strdup("test1\r\n")));
         printf ("[%s]\n", str_trim (strdup("test2\n\r")));
         printf ("[%s]\n", str_trim (strdup("test3\n\r\n\r")));
         printf ("[%s]\n", str_trim (strdup("test4\n")));
         printf ("[%s]\n", str_trim (strdup("test5\r")));
         printf ("[%s]\n", str_trim (strdup("test6\r\r\r")));
};

输入参数总能正常返回并退出。当你需要对串进行批量处理时会非常方便,就像这里的main()函数一样。

在该程序循环体的for()语句里有两个判断条件表达式:一个条件表达式是str_len>0(字符串的长度大于零);另外一个是c=s[str_len-1](意思是取出的值不为0、不是终止符)。循环判断语句“str_len>0 && (c=s[str_len-1])”实际上利用了所谓“逻辑短路”的执行特性,因此可以这样书写第二个判断表达式(可以参考Yur13:p.1.3.8)。C/C++编译器自左至右的逐一检测判断条件。因为逻辑操作符是“&&”(与),所以一旦第一个条件表达式的值为假,计算机就不用再判断(执行)第二个条件判断表达式。实际上,第二个条件表达式是一种只能在相应的条件下才可以运行的语句。笔者综合利用了第一个条件表达式、逻辑操作符“&&”的逻辑含义以及“逻辑短路”的特性,为第二个条件判断表达式限定了执行条件。

47.1 x64下的MSVC 2013优化

指令清单47.1 x64下的MSVC 2013优化

s$ = 8
str_trim PROC

; RCX is the first function argument and it always holds pointer to the string

; this is strlen() function inlined right here:
; set RAX to 0xFFFFFFFFFFFFFFFF (-1)
         or     rax, -1
$LL14@str_trim:
         inc    rax
         cmp    BYTE PTR [rcx+rax], 0
         jne    SHORT $LL14@str_trim
; is string length zero? exit then
         test   eax, eax
$LN18@str_trim:
         je     SHORT $LN15@str_trim
; RAX holds string length
; here is probably disassembler (or assembler printing routine) error,
; LEA RDX... should be here instead of LEA EDX...
         lea    edx, DWORD PTR [rax-1]
; idle instruction: EAX will be reset at the next instructions execution'
         mov    eax, edx
; load character at address s[str_len-1]
         movzx  eax, BYTE PTR [rdx+rcx]
; save also pointer to the last character to R8
         lea    r8, QWORD PTR [rdx+rcx]
         cmp    al, 13 ; is it '\r'?
         je     SHORT $LN2@str_trim
         cmp    al, 10 ; is it '\n'?
         jne    SHORT $LN15@str_trim
$LN2@str_trim:
; store 0 to that place
         mov    BYTE PTR [r8], 0
         mov    eax, edx
; check character for 0, but conditional jump is above...
         test   edx, edx
         jmp    SHORT $LN18@str_trim
$LN15@str_trim:
; return "s"
         mov    rax, rcx
         ret    0
str_trim ENDP

第一个特征就是MSVC编译器对字符串长度函数strlen()进行了内联(inline)式的展开和嵌入处理。编译器认为,内联处理后的执行效率会比常规的函数调用(call)的效率更高 。有关内联函数可以参考本书的第43章。

内嵌处理之后,strlen()函数的第一个指令是:OR RAX,0xffffffffffffffff。我们不清楚为何MSVC采用OR(或)指令,而没有采用MOV RAX, 0xffffffffffffffff指令直接赋值。当然,这两条指令执行的是相同操作:将所有位设置为1。因此这个数值就是赋值为−1。可以参考本书的第30章。

你也可能会问,为什么strlen()函数会用到−1这个数。当然是出于优化的目的。这里我们列出了MSVC的编译代码。

指令清单47.2 x64下的MSVC 2013的内嵌函数strlen()

; RCX = pointer to the input string
; RAX = current string length
         or     rax, -1
label:
         inc    rax
         cmp    BYTE PTR [rcx+rax], 0
         jne    SHORT label
; RAX = string length

如果把这个变量的初始值设置为0,那么是否可以把代码压缩得更短一些呢?我们可以来试试。

指令清单47.3 我们的strlen()字符串长度函数版本

; RCX = pointer to the input string
; RAX = current string length
         xor    rax, rax
label:
         cmp    byte ptr [rcx+rax], 0
         jz     exit
         inc    rax
         jmp    label
exit:
; RAX = string length

我们没能成功。因为我们不得不加入了一个额外的指令:JMP跳转指令。

在使用“-1”作为初始值之后,MSVC 2013随即在加载字符的指令之前分配了一个INC指令。如果第一个字符是0(终止符),那么RAX就直接为0,返回的字符串长度还会是0。

函数中的其余部分还是很好懂的。当然在程序的最后有另外一个技巧。除去那些内联之后的strlen()函数的展开代码,整个函数就只有3个条件指令。其实,从道理上讲这里应该有4个转移指令:第4个应当位于函数的结尾部分,用于检查当前字符是不是0。然后这段代码使用了一个跳转到“$LN18@str_ trim”标签的无条件转移指令,而这个标签后面的第一个指令就是条件转移指令JE。编译器用这种指令组用来判断输入的字符串是不是空字符串(当前字符是不是终止符),而且直接就是在strlen()执行结束后。所以这里使用JE指令有两个目的。这也许杀鸡用宰牛刀,但是无论如何,MSVC就是这样做的。

要想提示程序性能,就应当尽量脱离条件转移指令进行程序作业。有关详情请参阅本书第33章。

47.2 x64下采用编译器GCC 4.9.1进行非优化操作

str_trim:
         push   rbp
         mov    rbp, rsp
         sub    rsp, 32
         mov    QWORD PTR [rbp-24], rdi
; for() first part begins here
         mov    rax, QWORD PTR [rbp-24]
         mov    rdi, rax
         call   strlen
         mov    QWORD PTR [rbp-8], rax      ; str_len
; for() first part ends here
         jmp    .L2
; for() body begins here
.L5:
         cmp    BYTE PTR [rbp-9], 13        ; c=='\r'?
         je     .L3
         cmp    BYTE PTR [rbp-9], 10        ; c=='\n'?
         jne    .L4
.L3:
         mov    rax, QWORD PTR [rbp-8]      ; str_len
         lea    rdx, [rax-1]                ; EDX=str_len-1
         mov    rax, QWORD PTR [rbp-24]     ; s
         add    rax, rdx                    ; RAX=s+str_len-1
         mov    BYTE PTR [rax], 0           ; s[str_len-1]=0
; for() body ends here
; for() third part begins here
         sub    QWORD PTR [rbp-8], 1        ; str_len--
; for() third part ends here
.L2:
; for() second part begins here
         cmp    QWORD PTR [rbp-8], 0        ; str_len==0?
         je     .L4                         ; exit then
; check second clause, and load "c"
         mov    rax, QWORD PTR [rbp-8]      ; RAX=str_len
         lea    rdx, [rax-1]                ; RDX=str_len-1
         mov    rax, QWORD PTR [rbp-24]     ; RAX=s
         add    rax, rdx                    ; RAX=s+str_len-1
         movzx  eax, BYTE PTR [rax]         ; AL=s[str_len-1]
         mov    BYTE PTR [rbp-9], al        ; store loaded char into "c"
         cmp    BYTE PTR [rbp-9], 0         ; is it zero?
         jne    .L5                         ; yes? exit then
; for() second part ends here
.L4:
; return "s"
         mov    rax, QWORD PTR [rbp-24]
         leave
         ret

笔者在程序中增加了注释。执行完长度计算函数strlen()后,控制权将传递给标号为L2的语句。接着注意检查两个条件表达式。如果第一判断条件表达式为真,也就是说如果长度为0(str_len的值为0),那么计算机将不再检测第二个条件判断表达式。这种特性又称为“逻辑短路”。

概括地说,这个函数的执行流程如下:

47.3 x64下的GCC 4.9.1优化

str_trim:
         push   rbx
         mov    rbx, rdi
; RBX will always be "s"
         call   strlen
; check for str_len==0 and exit if its so'
         test   rax, rax
         je     .L9
         lea    rdx, [rax-1]
; RDX will always contain str_len-1 value, not str_len
; so RDX is more like buffer index variable
         lea    rsi, [rbx+rdx]       ; RSI=s+str_len-1
         movzx  ecx, BYTE PTR [rsi]  ; load character
         test   cl, cl
         je     .L9                  ; exit if its zero'
         cmp    cl, 10
         je     .L4
         cmp    cl, 13               ; exit if its not' '\n' and not '\r'
         jne    .L9
.L4:
; this is weird instruction. we need RSI=s-1 here.
; its possible to get it by' MOV RSI, EBX / DEC RSI
; but this is two instructions instead of one
         sub    rsi, rax
; RSI = s+str_len-1-str_len = s-1
; main loop begin
.L12:
         test   rdx, rdx
; store zero at address s-1+str_len-1+1 = s-1+str_len = s+str_len-1
         mov    BYTE PTR [rsi+1+rdx], 0
; check for str_len-1==0. exit if so.
         je     .L9
         sub    rdx, 1               ; equivalent to str_len--
; load next character at address s+str_len-1
         movzx  ecx, BYTE PTR [rbx+rdx]
         test   cl, cl               ; is it zero? exit then
         je     .L9
         cmp    cl, 10               ; is it '\n'?
         je     .L12
         cmp    cl, 13               ; is it '\r'?
         je     .L12
.L9:
; return "s"
         mov    rax, rbx
         pop    rbx
         ret

GCC的实现方式更为复杂。在循环体执行前的代码只执行一次,而且它还会检查结束符是不是回车和换行CR/LF。这难道不是多此一举吗?

一般来说,实现主循环体的流程是这样的:

① 循环开始,检查CR/LF结束符,进行判断。

② 保存零字符。

但是,GCC编译器会将这两步逆序执行。因此,第一步肯定不会是保存零字符,而是进行下述判断:

① 看看第一个字符是不是CR/LF,如果不是的话,就会退出。

② 循环开始,保存零字符。

③ 根据检查字符是不是CR/LF来决定程序的执行。

这样处理之后,主循环体就小了很多,更适用于目前的CPU了。这种代码的中间变量不是str_len,而是str_len-1。或许是因为后者更适用于用作缓冲区型数据的索引标号(数组下标)。很明显,GCC注意到了,str_len-1使用了两次。因此最好的办法是分配一个变量,其值总是比目前的字符串的长度小1,然后再将其递减(按照变量str_len的递减方式递减)。

47.4 ARM64:非优化的GCC(Linaro)4.9

它将生成近乎“一一对应”的汇编指令。具体代码如下所示。

指令清单47.4 非优化的GCC(Linaro[1])4.9

str_trim:
         stp     x29, x30, [sp, -48]!
         add     x29, sp, 0
         str     x0, [x29,24] ; copy input argument into local stack
         ldr     x0, [x29,24] ; s
         bl      strlen
         str     x0, [x29,40] ; str_len variable in local stack
         b       .L2
; main loop begin
.L5:
         ldrb    w0, [x29,39]
; W0=c
         cmp     w0, 13         ; is it '\r'?
         beq     .L3
         ldrb    w0, [x29,39]
; W0=c
         cmp     w0, 10         ; is it '\n'?
         bne     .L4            ; goto exit if it is not
.L3:
         ldr     x0, [x29,40]
; X0=str_len
         sub     x0, x0, #1
; X0=str_len-1
         ldr     x1, [x29,24]
; X1=s
         add     x0, x1, x0
; X0=s+str_len-1
         strb    wzr, [x0]    ; write byte at s+str_len-1
; decrement str_len:
         ldr     x0, [x29,40]
; X0=str_len
         sub     x0, x0, #1
; X0=str_len-1
         str     x0, [x29,40]
; save X0 (or str_len-1) to local stack
.L2:
         ldr     x0, [x29,40]
; str_len==0?
         cmp     x0, xzr
; goto exit then
         beq     .L4
         ldr     x0, [x29,40]
; X0=str_len
         sub     x0, x0, #1
; X0=str_len-1
         ldr     x1, [x29,24]
; X1=s
         add     x0, x1, x0
; X0=s+str_len-1
; load byte at address s+str_len-1 to W0
         ldrb    w0, [x0]
         strb    w0, [x29,39] ; store loaded byte to "c"
         ldrb    w0, [x29,39] ; reload it
; is it zero byte?
         cmp     w0, wzr
; goto exit, if its zero or to L5 if its not''
         bne     .L5
.L4:
; return s
         ldr     x0, [x29,24]
         ldp     x29, x30, [sp], 48
         ret

47.5 ARM64:优化GCC(Linaro)4.9

编译器采用了更为高级的优化技术。在程序开始时,首先调入第一个字符,并和十进制数10进行比对(也就是换行LF的数值)。此后,后续字符相继被调入主循环。这种处理方法和本书第47章第3节中的例子类似。

指令清单47.5 GCC(Linaro)4.9的优化

str_trim:
         stp     x29, x30, [sp, -32]!
         add     x29, sp, 0
         str     x19, [sp,16]
         mov     x19, x0
; X19 will always hold value of "s"
         bl      strlen
; X0=str_len
         cbz     x0, .L9          ; goto L9 (exit) if str_len==0
         sub     x1, x0, #1
; X1=X0-1=str_len-1
         add     x3, x19, x1
; X3=X19+X1=s+str_len-1
         ldrb    w2, [x19,x1]    ; load byte at address X19+X1=s+str_len-1
; W2=loaded character
         cbz     w2, .L9         ; is it zero? jump to exit then
         cmp     w2, 10          ; is it '\n'?
         bne     .L15
.L12:
; main loop body. loaded character is always 10 or 13 at this moment!
         sub     x2, x1, x0
; X2=X1-X0=str_len-1-str_len=-1
         add     x2, x3, x2
; X2=X3+X2=s+str_len-1+(-1)=s+str_len-2
         strb    wzr, [x2,1]     ; store zero byte at address s+str_len-2+1=s+str_len-1
         cbz     x1, .L9         ; str_len-1==0? goto exit, if so
         sub     x1, x1, #1      ; str_len--
         ldrb    w2, [x19,x1]    ; load next character at address X19+X1=s+str_len-1
         cmp     w2, 10          ; is it '\n'?
         cbz     w2, .L9         ; jump to exit, if its zero'
         beq     .L12            ; jump to begin loop, if its' '\n'
.L15:
         cmp     w2, 13          ; is it '\r'?
         beq     .L12            ; yes, jump to the loop body begin
.L9:
; return "s"
         mov     x0, x19
         ldr     x19, [sp,16]
         ldp     x29, x30, [sp], 32
         ret

47.6 ARM: Keil 6/2013优化(ARM模式)

这里我们会再次看到,编译器分配了ARM模式下的条件指令,使整个代码更为紧凑。

指令清单47.6 Keil 6/2013优化(ARM模式)

str_trim PROC
         PUSH    {r4,lr}
; R0=s
         MOV     r4,r0
; R4=s
         BL      strlen         ; strlen() takes "s" value from R0
; R0=str_len
         MOV     r3,#0
; R3 will always hold 0
|L0.16|
         CMP     r0,#0          ; str_len==0?
         ADDNE   r2,r4,r0       ; (if str_len!=0) R2=R4+R0=s+str_len
         LDRBNE  r1,[r2,#-1]    ; (if str_len!=0) R1=load byte at address R2-1=s+str_len-1
         CMPNE   r1,#0          ; (if str_len!=0) compare loaded byte against 0
         BEQ     |L0.56|        ; jump to exit if str_len==0 or loaded byte is 0
         CMP     r1,#0xd        ; is loaded byte '\r'?
         CMPNE   r1,#0xa        ; (if loaded byte is not '\r') is loaded byte '\r'?
         SUBEQ   r0,r0,#1       ; (if loaded byte is '\r' or '\n') R0-- or str_len--
         STRBEQ  r3,[r2,#-1]    ; (if loaded byte is '\r' or '\n') store R3 (zero) at
    address R2-1=s+str_len-1
         BEQ     |L0.16|        ; jump to loop begin if loaded byte was '\r' or '\n'
|L0.56|
; return "s"
         MOV     r0,r4
         POP     {r4,pc}
         ENDP

47.7 ARM:Keil 6/2013(Thumb模式)优化

在Thumb模式指令集的条件执行指令比ARM模式指令集的少,因此这种代码更接近x86的指令。但是在程序的22和23行处的偏移量0x20和0x1f,会令多数人感到匪夷所思。为什么Keil 6编译器会分配这些指令?老实说,很难讲。也许这就是Keil 6优化进程的诡异之处。不管这种代码多么令人费解,整个程序的功能确实忠实于我们的源代码。

指令清单47.7 Keil 6/2013(Thumb模式)优化

1     str_trim PROC
1             PUSH    {r4,lr}
2             MOVS    r4,r0
4     ; R4=s
5             BL      strlen          ; strlen() takes "s" value from R0
6     ; R0=str_len
7             MOVS    r3,#0
8     ; R3 will always hold 0
9             B       |L0.24|
10    |L0.12|
11            CMP     r1,#0xd         ; is loaded byte '\r'?
12            BEQ     |L0.20|
13            CMP     r1,#0xa         ; is loaded byte '\n'?
14            BNE     |L0.38|         ; jump to exit, if no
15    |L0.20|
16            SUBS    r0,r0,#1        ; R0-- or str_len--
17            STRB    r3,[r2,#0x1f]   ; store 0 at address R2+0x1F=s+str_len-0x20+0x1F=s+str_len-1
18    |L0.24|
19            CMP     r0,#0           ; str_len==0?
20            BEQ     |L0.38|         ; yes? jump to exit
21            ADDS    r2,r4,r0        ; R2=R4+R0=s+str_len
22            SUBS    r2,r2,#0x20     ; R2=R2-0x20=s+str_len-0x20
23            LDRB    r1,[r2,#0x1f]   ; load byte at
24        address R2+0x1F=s+str_len-0x20+0x1F=s+str_len-1 to R1
25            CMP     r1,#0           ; is loaded byte 0?
26            BNE     |L0.12|         ; jump to loop begin, if its not 0'
27     |L0.38|
28     ; return "s"
29            MOVS    r0,r4
30            POP     {r4,pc}
31            ENDP

47.8 MIPS

指令清单47.8 (IDA)GCC 4.4.5优化

str_trim:
; IDA is not aware of local variable names, we gave them manually:
saved_GP         = -0x10
saved_S0         = -8
saved_RA         = -4

                lui      $gp, (__gnu_local_gp >> 16)
                addiu    $sp, -0x20
                la       $gp, (__gnu_local_gp & 0xFFFF)
                sw       $ra, 0x20+saved_RA($sp)
                sw       $s0, 0x20+saved_S0($sp)
                sw       $gp, 0x20+saved_GP($sp)
; call strlen(). input string address is still in $a0, strlen() will take it from there:
                lw       $t9, (strlen & 0xFFFF)($gp)
                or       $at, $zero ; load delay slot, NOP
                jalr     $t9
; input string address is still in $a0, put it to $s0:
                move     $s0, $a0 ; branch delay slot
; result of strlen() (i.e, length of string) is in $v0 now
; jump to exit if $v0==0 (i.e., if length of string is 0):
                beqz     $v0, exit
                or       $at, $zero ; branch delay slot, NOP
                addiu    $a1, $v0, -1
; $a1 = $v0-1 = str_len-1
                addu     $a1, $s0, $a1
; $a1 = input string address + $a1 = s+strlen-1
; load byte at address   $a1:
                lb       $a0, 0($a1)
                or       $at, $zero ; load delay slot, NOP
; loaded byte is zero? jump to exit if its so':
                beqz     $a0, exit
                or       $at, $zero ; branch delay slot, NOP
                addiu    $v1, $v0, -2
; $v1 = str_len-2
                addu     $v1, $s0, $v1
; $v1 = $s0+$v1 = s+str_len-2
                li       $a2, 0xD
; skip loop body:
                b         loc_6C
                li        $a3, 0xA ; branch delay slot
loc_5C:
; load next byte from memory to $a0:
                lb        $a0, 0($v1)
                move      $a1, $v1
; $a1=s+str_len-2
; jump to exit if loaded byte is zero:
                beqz      $a0, exit
; decrement str_len:
                addiu     $v1, -1     ; branch delay slot
loc_6C:
; at this moment, $a0=loaded byte, $a2=0xD (CR symbol) and $a3=0xA (LF symbol)
; loaded byte is CR? jump to loc_7C then:
                beq       $a0, $a2, loc_7C
                addiu     $v0, -1     ; branch delay slot
; loaded byte is LF? jump to exit if its not LF':
                bne       $a0, $a3, exit
                or        $at, $zero  ; branch delay slot, NOP
loc_7C:
; loaded byte is CR at this moment
; jump to loc_5c (loop body begin) if str_len (in $v0) is not zero:
                bnez      $v0, loc_5C
; simultaneously, store zero at that place in memory:
                sb        $zero, 0($a1) ; branch delay slot
; "exit" label was named by me manually:
exit:
                lw        $ra, 0x20+saved_RA($sp)
                move      $v0, $s0
                lw        $s0, 0x20+saved_S0($sp)
                jr        $ra
                addiu     $sp, 0x20     ; branch delay slot

S-字头的寄存器就是保存寄存器(saved temporaries)。在过程调用过程中,保存寄存器的值需要保留(被调用方函数保存和恢复),因此$S0的值保存在局部栈里,在完成任务后恢复其初始状态。


[1] Linaro是一家开源的基于ARM操作平台的组织,由多家业内公司联合成立。其开发了ARM开发工具、Linux内核以及Linux发行版(包括Android及Ubuntu)的主要自动建构系统。