Systemnahe Programmierung in Chome Systemnahe Programmierung 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 mit Glück (abhängig von der Version) die Endrekursion in eine Schleife.
 
Man erkennt an diesem kleinen Beispiel und den Codelängen der Assembler-Programme die Wirksamkeit der mit -O2 aktivierten Optimierungen.
 
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 $16, %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, %eax
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, %eax
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, %eax
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, %eax
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, %eax
56 jmp .L3
57 .L7:
58 movq -16(%rbp), %rax
59 leaq 1(%rax), %rdx
60 movq -8(%rbp), %rax
61 addq $1, %rax
62 movq %rdx, %rsi
63 movq %rax, %rdi
64 call strcmp1
65 .L3:
66 leave
67 ret
weiter
weiter

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

1 strcmp1:
2 subq $8, %rsp
3 movzbl (%rdi), %edx
4 testb %dl, %dl
5 jne .L2
6 cmpb $1, (%rsi)
7 sbbl %eax, %eax
8 notl %eax
9 jmp .L3
10 .L2:
11 movl $1, %eax
12 cmpb $0, (%rsi)
13 je .L3
14 movzbl (%rsi), %ecx
15 movl $-1, %eax
16 cmpb %cl, %dl
17 jl .L3
18 movl $1, %eax
19 jg .L3
20 addq $1, %rsi
21 addq $1, %rdi
22 call strcmp1
23 .L3:
24 addq $8, %rsp
25 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 .L3:
8 addq $1, %rsi
9 movzbl 1(%rdi), %edx
10 testb %dl, %dl
11 je .L2
12 addq $1, %rdi
13 cmpb (%rsi), %dl
14 je .L3
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, %eax
28 movsbl %cl, %ecx
29 subl %ecx, %eax
30 .L5:
31 rep
32 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: 22.11.2012
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel