不简单的strlen长度计算，

which

http://bbs.chinaunix.net/viewthread.php?tid=642853

daybreakcx

原帖由 snnn 于 2009-5-17 08:51 发表
int strlen（char *p）  // 注意！ 不允许定义任何变量
{
  if( *p )
  return strlen（p + 1）+ 1;
  return 0;
}

这个算tail recursive，和普通的for一样的效率。

尾递归？这里有吗？实在看不出来，严重质疑

baicj

原帖由 daybreakcx 于 2009-5-17 16:22 发表

尾递归？这里有吗？实在看不出来，严重质疑

被编译器优化掉了...

fedora:~ baicj$ cat strlen.c
int strlen(char *p)
{
        return *p ? strlen(p+1)+1 : 0;
}
fedora:~ baicj$ gcc -S -O -masm=intel strlen.c
fedora:~ baicj$ cat strlen.s
        .file   "strlen.c"
        .intel_syntax noprefix
        .text
.globl strlen
        .type   strlen, @function
strlen:
        push    ebp
        mov     ebp, esp
        push    edi
        mov     edx, DWORD PTR [ebp+8]
        mov     eax, 0
        cmp     BYTE PTR [edx], 0
        je      .L3
        lea     edi, [edx+1]
        mov     eax, 0
        mov     ecx, -1
        repnz scasb
        mov     eax, ecx
        not     eax
.L3:
        pop     edi
        pop     ebp
        ret
        .size   strlen, .-strlen
        .ident  "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"
        .section        .note.GNU-stack,"",@progbits
fedora:~ baicj$

[ 本帖最后由 baicj 于 2009-5-17 18:04 编辑 ]

mik

汗～
这个编译器还挺智能的。

daybreakcx

囧～
一般编译器不带这样吧，这是个比较简单的递归，中间没进行什么操作，如果是稍微复杂点的编译器敢这么做吗？貌似容易出错还

baicj

刚才想了一下， 觉得gcc的确不可能把这个递归演算成“repnz scasb”，又试了一下无穷递归：

fedora:~ baicj$ cat strlen.c
int strlen(char *p)
{
        return strlen(p);
}
fedora:~ baicj$ gcc -S -masm=intel -O1 strlen.c
fedora:~ baicj$ cat strlen.s
        .file   "strlen.c"
        .intel_syntax noprefix
        .text
.globl strlen
        .type   strlen, @function
strlen:
        push    ebp
        mov     ebp, esp
        push    edi
        mov     edi, DWORD PTR [ebp+8]
        mov     eax, 0
        mov     ecx, -1
        repnz scasb
        not     ecx
        lea     eax, [ecx-1]
        pop     edi
        pop     ebp
        ret
        .size   strlen, .-strlen
        .ident  "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"
        .section        .note.GNU-stack,"",@progbits
fedora:~ baicj$

奇怪，无穷递归也被解释成“repnz scasb”了，看来gcc的O1选项会把strlen当作替换成内置的字串算法，不知道算不算bug, 或者有别的参数可以设置？
O0和O2很正常：

fedora:~ baicj$ cat strlen.c
int strlen(char *p)
{
        return strlen(p);
}
fedora:~ baicj$ gcc -S -masm=intel -O0 strlen.c
fedora:~ baicj$ cat strlen.s
        .file   "strlen.c"
        .intel_syntax noprefix
        .text
.globl strlen
        .type   strlen, @function
strlen:
        push    ebp
        mov     ebp, esp
        sub     esp, 8
        mov     eax, DWORD PTR [ebp+8]
        mov     DWORD PTR [esp], eax
        call    strlen
        leave
        ret
        .size   strlen, .-strlen
        .ident  "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"
        .section        .note.GNU-stack,"",@progbits
fedora:~ baicj$ gcc -S -masm=intel -O2 strlen.c
fedora:~ baicj$ cat strlen.s
        .file   "strlen.c"
        .intel_syntax noprefix
        .text
        .p2align 4,,15
.globl strlen
        .type   strlen, @function
strlen:
        push    ebp
        mov     ebp, esp
.L2:
        jmp     .L2
        .size   strlen, .-strlen
        .ident  "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"
        .section        .note.GNU-stack,"",@progbits
fedora:~ baicj$

回过头来看原来的字串算法，用O2还是可以把递归变成循环， 不知道算不算尾递归？

fedora:~ baicj$ cat strlen.c
int strlen(char *p)
{
        return *p ? strlen(p+1)+1 : 0;
}
fedora:~ baicj$ gcc -S -masm=intel -O2 strlen.c
fedora:~ baicj$ cat strlen.s
        .file   "strlen.c"
        .intel_syntax noprefix
        .text
        .p2align 4,,15
.globl strlen
        .type   strlen, @function
strlen:
        push    ebp
        xor     ecx, ecx
        mov     ebp, esp
        mov     edx, 1
        push    ebx
        mov     ebx, DWORD PTR [ebp+8]
        cmp     BYTE PTR [ebx], 0
        je      .L3
        .p2align 4,,7
        .p2align 3
.L6:
        movzx   eax, BYTE PTR [ebx+edx]
        mov     ecx, edx
        add     edx, 1
        test    al, al
        jne     .L6
.L3:
        mov     eax, ecx
        pop     ebx
        pop     ebp
        ret
        .size   strlen, .-strlen
        .ident  "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"
        .section        .note.GNU-stack,"",@progbits
fedora:~ baicj$

ws00377531

slay78

递归实现真的跟库函数版本一样么，计算一个超长的字符串岂不是stack overflow了，所以此题无解

lxs_lover520

原帖由 暗底 于 2009-5-13 14:25 发表


当p指向最后的'\0'时, return 0, 再之后怎么算的? 我不明白strlen(p+1)出栈之后为什么能算出数啊?

这个有人尝试过没有哦？貌似不可以的哦……

lsupper

不错~~~