Algorithmen und Datenstrukturen in Chome Algorithmen und Datenstrukturen in C: strcmp Prof. Dr. Uwe Schmidt FH Wedel
String-Funktionen
strcpyInhaltsverzeichnis

strcmp

weiter
weiter

Implementierung der strcmp-Funktion

strcmp
zum Vergleich zweier Zeichenreihen kann auf verschiedene Arten formuliert werden.
 
 Die 1. Version ist eine erste einfache Lösung, in der jeder Fall in eine bedingte Anweisung umgesetzt ist, die aber noch mit einer Endrekursion arbeitet und noch einige redundante Tests enthält.
 
 Diese Lösung ist für eine Referenzimplementierung geeignet. Mit angeschalteter Optimierung transformiert der gcc die Endrekursion in eine Schleife.
 
 In der zweiten Lösung ist die Endrekursion durch eine Schleife ersetzt worden, außerdem wird, wie auch nur im ANSI-Standard gefordert, ein Wert > 0, == 0 oder < 0 als Resultat geliefert, nicht wie in der 1. Lösung +1, 0 oder -1.
weiter
weiter

Die 1. Version: strcmp1.c

   1#include <stdlib.h>
   2
   3int
   4strcmp1 (char *s1, char *s2)
   5{
   6  if (*s1 == 0 && *s2 == 0)
   7    return 0;
   8
   9  if (*s1 == 0 && *s2 != 0)
  10    return -1;
  11
  12  if (*s1 != 0 && *s2 == 0)
  13    return +1;
  14
  15  if (*s1 < *s2)
  16    return -1;
  17
  18  if (*s1 > *s2)
  19    return +1;
  20
  21  /* if (*s1 == *s2) */
  22    return strcmp1 (s1 + 1, s2 + 1);
  23}
weiter
weiter

Der Assembler-Code: gcc -S strcmp1.c

1 strcmp1:
2 pushq %rbp
3 movq %rsp, %rbp
4 subq $32, %rsp
5 movq %rdi, -8(%rbp)
6 movq %rsi, -16(%rbp)
7 movq -8(%rbp), %rax
8 movzbl (%rax), %eax
9 testb %al, %al
10 jne .L2
11 movq -16(%rbp), %rax
12 movzbl (%rax), %eax
13 testb %al, %al
14 jne .L2
15 movl $0, -20(%rbp)
16 jmp .L3
17 .L2:
18 movq -8(%rbp), %rax
19 movzbl (%rax), %eax
20 testb %al, %al
21 jne .L4
22 movq -16(%rbp), %rax
23 movzbl (%rax), %eax
24 testb %al, %al
25 je .L4
26 movl $-1, -20(%rbp)
27 jmp .L3
28 .L4:
29 movq -8(%rbp), %rax
30 movzbl (%rax), %eax
31 testb %al, %al
32 je .L5
33 movq -16(%rbp), %rax
34 movzbl (%rax), %eax
35 testb %al, %al
36 jne .L5
37 movl $1, -20(%rbp)
38 jmp .L3
39 .L5:
40 movq -8(%rbp), %rax
41 movzbl (%rax), %edx
42 movq -16(%rbp), %rax
43 movzbl (%rax), %eax
44 cmpb %al, %dl
45 jge .L6
46 movl $-1, -20(%rbp)
47 jmp .L3
48 .L6:
49 movq -8(%rbp), %rax
50 movzbl (%rax), %edx
51 movq -16(%rbp), %rax
52 movzbl (%rax), %eax
53 cmpb %al, %dl
54 jle .L7
55 movl $1, -20(%rbp)
56 jmp .L3
57 .L7:
58 movq -8(%rbp), %rax
59 movzbl (%rax), %edx
60 movq -16(%rbp), %rax
61 movzbl (%rax), %eax
62 cmpb %al, %dl
63 jne .L8
64 movq -16(%rbp), %rax
65 leaq 1(%rax), %rsi
66 movq -8(%rbp), %rax
67 leaq 1(%rax), %rdi
68 call strcmp1
69 movl %eax, -20(%rbp)
70 jmp .L3
71 .L8:
72 jmp .L1
73 .L3:
74 movl -20(%rbp), %eax
75 movl %eax, -24(%rbp)
76 .L1:
77 movl -24(%rbp), %eax
78 leave
79 ret
weiter
weiter

Der optimierte Assembler-Code: gcc -O2 -o strcmp1-O.s -S strcmp1.c

1 strcmp1:
2 movzbl (%rdi), %edx
3 testb %dl, %dl
4 je .L2
5 movzbl (%rsi), %eax
6 testb %al, %al
7 je .L3
8 cmpb %dl, %al
9 jg .L4
10 jl .L3
11 cmpb %dl, %al
12 je .L10
13 jmp .L6
14 .L13:
15 movzbl (%rsi), %eax
16 testb %al, %al
17 je .L3
18 cmpb %al, %dl
19 jl .L4
20 jg .L3
21 cmpb %al, %dl
22 jne .L6
23 .L10:
24 addq $1, %rdi
25 addq $1, %rsi
26 movzbl (%rdi), %edx
27 testb %dl, %dl
28 jne .L13
29 .L2:
30 xorl %eax, %eax
31 cmpb $0, (%rsi)
32 je .L1
33 .L4:
34 movl $-1, %eax
35 ret
36 .L3:
37 movl $1, %eax
38 .L1:
39 rep
40 ret
41 .L6:
42 rep
43 ret
weiter
weiter

Die 2. Version: strcmp2.c

   1#include <stdlib.h>
   2
   3int
   4strcmp2 (char *s1, char *s2)
   5{
   6
   7  while (*s1 != 0 && *s1 == *s2)
   8    {
   9      ++s1;
  10      ++s2;
  11    }
  12
  13  return
  14    (*s2 == 0)
  15    ? (*s1 != 0)
  16    : (*s1 == 0)
  17    ? -1
  18    : (*s1 - *s2);
  19}
weiter
weiter

Der Assembler-Code: gcc -O -o strcmp2-O.s -S strcmp2.c

1 strcmp2:
2 movzbl (%rdi), %edx
3 testb %dl, %dl
4 je .L2
5 cmpb (%rsi), %dl
6 jne .L2
7 .L8:
8 addq $1, %rdi
9 addq $1, %rsi
10 movzbl (%rdi), %edx
11 testb %dl, %dl
12 je .L2
13 cmpb (%rsi), %dl
14 je .L8
15 .L2:
16 movzbl (%rsi), %ecx
17 testb %cl, %cl
18 jne .L4
19 testb %dl, %dl
20 setne %al
21 movzbl %al, %eax
22 ret
23 .L4:
24 movl $-1, %eax
25 testb %dl, %dl
26 je .L5
27 movsbl %dl,%edx
28 movsbl %cl,%eax
29 subl %eax, %edx
30 movl %edx, %eax
31 .L5:
32 rep
33 ret
weiter
weiter

Der Assembler-Code: gcc -O2 -o strcmp2-O2.s -S strcmp2.c

1 strcmp2:
2 jmp .L14
3 .L2:
4 movzbl (%rsi), %eax
5 cmpb %al, %dl
6 jne .L3
7 addq $1, %rdi
8 addq $1, %rsi
9 .L14:
10 movzbl (%rdi), %edx
11 testb %dl, %dl
12 jne .L2
13 movzbl (%rsi), %eax
14 .L3:
15 testb %al, %al
16 je .L16
17 testb %dl, %dl
18 movl $-1, %ecx
19 jne .L17
20 movl %ecx, %eax
21 ret
22 .L17:
23 movsbl %dl,%ecx
24 movsbl %al,%eax
25 subl %eax, %ecx
26 movl %ecx, %eax
27 ret
28 .L16:
29 xorl %ecx, %ecx
30 testb %dl, %dl
31 setne %cl
32 movl %ecx, %eax
33 ret
weiter
weiter

Ein sehr einfaches Testprogramm: Teststrcmp.c

   1#include <stdio.h>
   2#include <assert.h>
   3
   4#include "strcmp1.c"
   5#include "strcmp2.c"
   6
   7int
   8main (void)
   9{
  10  assert ((strcmp1 ("", "") != 0) == (strcmp2 ("", "") != 0));
  11  assert ((strcmp1 ("x", "") != 0) == (strcmp2 ("x", "") != 0));
  12  assert ((strcmp1 ("", "x") != 0) == (strcmp2 ("", "x") != 0));
  13  assert ((strcmp1 ("x", "z") != 0) == (strcmp2 ("x", "z") != 0));
  14  assert ((strcmp1 ("z", "x") != 0) == (strcmp2 ("z", "x") != 0));
  15  assert ((strcmp1 ("x", "x") != 0) == (strcmp2 ("x", "x") != 0));
  16
  17  printf ("strcmp test passed\n");
  18  return 0;
  19}
weiter
weiter

Übersetzen

cc -Wall -pedantic -o strcmpTest Teststrcmp.c
weiter
weiter

Testen

strcmpTest
weiter
SeitenanfangString-Funktionen
strcpyInhaltsverzeichnis
Letzte Änderung: 12.11.2009
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel