我们经常需要去除字符串里的开始符号或者结束符号。
本章介绍的程序,专门用于去除字符串的结尾部分的回车和换行字符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优化
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章。
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),那么计算机将不再检测第二个条件判断表达式。这种特性又称为“逻辑短路”。
概括地说,这个函数的执行流程如下:
运行for()语句的第一部分,也就是调用strlen()函数的循环初始化指令。
跳转到标号L2;检测循环条件是否成立。
跳转到标号L5,进入循环体;
再执行for()语句,如果条件不成立,则直接退出。
执行for()语句的第三部分,将变量str_len递减。
再次跳转到标号L2,检测循环条件是否成立、进入循环……周而复始,直到循环条件不成立。
跳转到L4标号,准备退出。
制备返回值,即变量s。
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 非优化的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
编译器采用了更为高级的优化技术。在程序开始时,首先调入第一个字符,并和十进制数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
这里我们会再次看到,编译器分配了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
在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 (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)的主要自动建构系统。