Warum wird hier der ggT berechnet? (C-Code inside)

Gausi · Verfasst: Do 15.11.12 15:08

Ist zwar eine Programmierfrage, aber ich pack das trotzdem ins OT. Es geht um (reines) C.

Aufgabe ist es, den größten gemeinsamen Teiler zweier natürlicher Zahlen zu berechnen. Im Laufe der Übung ist dabei folgender Code entstanden. Dabei wurde zuerst das Innere der Schleife programmiert (anhand eines Diagramms aus dem Vorlesungsskript), und dann die Schleife drumherum gebaut - daher auch die etwas merkwürdigen Bedingungen. ;-)

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

int ggt(int a, int b){   
  while (a != b)
    if (a==b) 
      return a;
    else
      if (b > a) 
        b = b-a;
      else 
        a = a-b;
}

Der Punkt ist: Die Zeile mit return a; wird nie erreicht, trotzdem scheint diese Funktion immer das korrekte Ergebnis zu liefern. Frage also, was macht der C-Compiler da? (Ganz normaler gcc, welche Version genau weiß ich nicht.)

(Hinweis: Ich weiß, dass das nicht der schnellste Weg ist, den ggT zu berechnen. Wer auf der Suche nach sowas ist, sollte diesen Code also nicht verwenden.)

_________________
We are, we were and will not be.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Das hängt vom Compiler und/oder Einstellungen ab. Die Werte von a oder b werden wohl in Registern gehalten. Der ggt ist fertig berechnet, wenn a=b ist und der Wert eines der Register wird geliefert.

Interessant ist der Fall, wenn am Start a=b ist, dann liefert zB BCC nicht den richtigen Wert. Im übrigen zeigen GCC und MSC Warnungen an:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:

cl ggt.c
ggt.c
ggt.c(13) : warning C4715: 'ggt' : Nicht alle Steuerelementpfade geben einen Wert zurück

gcc -Wall ggt.c
ggt.c: In function 'ggt':
ggt.c:12:1: warning: control reaches end of non-void function [-Wreturn-type]

Tranx · Verfasst: Do 15.11.12 16:26

Ich denke, dass dies funktionieren würde. Bin allerdings kein C-Programmierer:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

int ggt(int a, int b){   
  while (a != b)
  {
      if (b > a) 
        b = b-a;
      else 
        a = a-b;
  }
  return a;
}

Tut mir Leid, welchen Tag muss ich nehmen, um C-Source darzustellen Delphi gibt ja bei geschweiften Klammern einen Kommentar raus.

Moderiert von Gausi: Delphi- durch CS-Tags ersetzt

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Gausi · Verfasst: Do 15.11.12 16:33

@Gammatester:Ok, dann ist das zumindest schonmal kein Verhalten, was immer auftritt.

@Tranx: Wie man den Code passend korrigiert, ist mir klar ;-)

. Mir war nur nicht klar, warum der Code (zumindest bei den Einstellungen hier) auch so funktioniert, bzw. wie man den Code so um (unsinnigen Kram) erweitern kann, so dass am Ende halt nicht zufällig (?) der richtige Wert geliefert wird.

_________________
We are, we were and will not be.

Tranx · Verfasst: Do 15.11.12 16:38

Weiß leider nicht, was so ein Compiler alles im Hintergrund anstellt. Bei Delphi habe ich auch oft sehr extreme Effekte gehabt, dass irgendwelche Komponenten plötzlich nicht mehr definiert waren und dann Fehler verursachten, wenn man auf sie zugriff, ohne dass ich irgendwo eine Free oder Destroy hatte. Manchmal musste man nur die Komponente löschen und wieder einbinden und alles funktionierte. Vielleicht ist das ja - wenn Daten in Registern stehen, hier auch so. Dass die Funktion automatisch einen Register übergibt. Und da ja die Funktion letztlich ja zwei gleiche Werte in a udn b hat, ist es egal, welcher der beiden Registerwerte übergeben werden.

Das reime ich mir bei dem Code zusammen. Weiß aber nicth, ob es stimmt.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Delphi-Laie · Verfasst: Do 15.11.12 17:12

Welcher C-Compiler ist es denn?

Bei Pascal kenne ich Delphi und FPC (als Lazarus), ich glaube, bei beiden (auf jeden Fall aber beim ersten) kommt doch die Warnung, daß der Rückgabewert undefiniert sein kann.

Martok · Verfasst: Do 15.11.12 17:19

Das klappt unter bestimmten Umständen auch in Delphi, besonders wenn die Optimierung an ist.
Gammatester hat Recht: der erste Parameter landet in eax, und der Rückgabewert wird vom Caller aus eax gelesen. Bei der 192er-Optimierungsschlacht ist mir das auch mal auf die Füße gefallen.

Ist hier (Turbo2006) allerdings etwas schwierig nachzustellen, da genug Register frei sind und Delphi deswegen ecx (also ein drittes) für Result nimmt. D7 war da einfacher zu seinem Bug zu zwingen

Knapp vor "Thema verfehlt" landet allerdings das: direkte Übersetzung, einzige Änderung ist ein Spaß-Parameter c. Der wird nicht mal benutzt, trotzdem tritt der Effekt auf.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

{$optimization on}
function ggt(a, b,c: Integer): Integer;
begin
  while(a <> b) do begin
    if a=b then begin
      Result:= a;
      exit;
    end
    else begin
      if b>a then
        b:= b-a
      else
        a:= a-b;
    end;
  end;
end;

var
  g: integer;
begin
  g:= ggt(42, 14, 23);
  WriteLn(g);     // Writes '23'
end.

Als Hausaufgabe: Was wird hier ausgegeben, und welche Bedeutung hat dieser Wert? Belohnung: ein Gummipunkt

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

type
  TFoo=class
    function ggt(a, b: Integer): Integer;
  end;

function TFoo.ggt(a, b: Integer): Integer;
begin
  while(a <> b) do begin
    if a=b then begin
      Result:= a;
      exit;
    end
    else begin
      if b>a then
        b:= b-a
      else
        a:= a-b;
    end;
  end;
end;

var
  f: TFoo;
  g: integer;
begin
  f:= TFoo.Create;
  g:= f.ggt(42,14);
  WriteLn(g);
end.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Gausi · Verfasst: Do 15.11.12 18:01

Optimierung war schonmal ein gutes Stichwort. Wenn ich die anschalte, liefert mir die C-Funktion scheinbar den zweiten Parameter zurück. Weitere Spaßparameter führen aber zu keiner Verhaltensänderung, egal ob man die benutzt oder nicht.

_________________
We are, we were and will not be.

Tranx · Verfasst: Fr 16.11.12 07:42

Was man an dem Delphi-Text (für mich als Delphi-Programmierer) schön sehen kann, ist die Unsinnigkeit der Abfrage "if a = b", denn in der While-Schleife kann ja a nicht b sein, explizit als Bedingung (a <> b).

Martok: Zu Deiner Frage: selbstverständlich ein undefinierter Wert. Bei mir war das 100011110000100011001000!

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Gausi · Verfasst: Fr 16.11.12 08:38

Ob das ein zufälliger oder undefinierter Wert ist, bezweifle ich. Ich denke, dass bei dem Klassenkonstrukt nicht mehr mit Registern gearbeitet wird, sondern dass sowohl Parameterübergabe als auch Rückgabe des Ergebnis über den Stack läuft. Wenn das Ergebnis nicht auf den Stack geschrieben wird, dann steht an der vermuteten Stelle wohl noch der alte Inhalt, der da vorher hingeschrieben wurde. Und das dürfte dann eine Rücksprungadresse sein, aber welche genau kann ich jetzt nicht auseinanderfriemeln.

_________________
We are, we were and will not be.

Horst_H · Verfasst: Fr 16.11.12 11:42

Hallo,

bei Freepascal und auch Delphi wird in EAX der Parameter Self der Klasse übergeben.

mit -al -ar kompiliert

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:

type
  TFoo=class
    function ggt(a, b: Integer): Integer;
  end;

function TFoo.ggt(a, b: Integer): Integer;
begin
  while(a <> b) do begin
    if a=b then begin
      Result:= a;
      exit;
    end
    else begin
      if b>a then
        b:= b-a
      else
        a:= a-b;
    end;
  end;
end;

var
  f: TFoo;
  g: integer;
begin
  f:= TFoo.Create;
  g:= f.ggt(42,14);
  WriteLn(g);
  f.free;
end.


{Ergibt in der Assemblerausgabe }

.globl  P$PROGRAM_TFOO_$__GGT$LONGINT$LONGINT$$LONGINT
P$PROGRAM_TFOO_$__GGT$LONGINT$LONGINT$$LONGINT:
# Temps allocated between esp+0 and esp+4
  # Register esp allocated
# [TFoo.pas]
// in Zeile 7 steht begin
# [7] begin
  subl  $4,%esp
# Var a located in register edx
# Var b located in register ecx
// Hier ist $self in EAX
# Var $self located in register eax
# Var $result located in register eax
  movl  %ebx,(%esp)
  # Register eax,edx,ecx allocated
  # Register eax released
  # Register eax allocated
# [8] while(a <> b) do begin
  jmp  .Lj6
  .balign 4,0x90
.Lj5:
# [9] if a=b then begin
  cmpl  %ecx,%edx
  jne  .Lj9
// Result wird wie ueblich in EAX zurückgegeben 
# [10] Result:= a;
  movl  %edx,%eax
# [11] exit;

Siehe:
www.delphibasics.co.uk/RTL.asp?Name=Self

Gruß Horst

Martok · Verfasst: Fr 16.11.12 11:49

Uuuund wir haben einen Gewinner :lol:

Horst_H hat folgendes geschrieben :

bei Freepascal und auch Delphi wird in EAX der Parameter Self der Klasse übergeben.

Ganz genau, "Self" ist ein implizierter erster Parameter. Bei class functions übrigens auch, dort zeigt er allerdings auf die TClass.

Einen Gummipunkt für user profile icon

Horst_H

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Fr 16.11.12 13:09

Hallo,

Weil es so schön offtopic ist.
wer steht denn auf Gummi, was mache ich jetzt damit :?:

Gausi · Ehemaliges Mitglied Erhaltene Danke: 1

Bei dem Phänomen handelt es sich nicht um eine sprachspezifische Eigenart oder sonstiges, sondern einfach nur um die korrekte Umsetzung der CDECL Aufrufkonvention. CDECL erfordert, dass das Ergebnis einer Funktion im EAX Register gespeichert wird. Register werden hier nicht für die Übergabe der Parameter genutzt, sondern sollen laut Definition der Aufrufkonvention nur von der aufgerufenen Funktion genutzt werden. EAX ist somit ein temporäres Register der Funktion, welches für die interne Berechnung des GGT genutzt wird.

Da Register nie aufgeräumt bzw. genullt werden, enthält das EAX Register am Ende noch den validen Wert. Gleiches geht auch mit der STDCALL Aufrufkonvention. Ich nehme aber an, dass hier eher eine CDECL Konvention verwendet wurde, da das meist der Standard des GCC-Compilers ist.

Gausi · Verfasst: Fr 16.11.12 14:02

So wir haben hier auch noch was rumgespielt, und die Funktion auf diese Art und Weise kaputt bekommen:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

volatile int c = 5;
int ggt( int a, int b){   
  while (a != b) {
    if (a==b) 
      return a;
    else {
      if (b > a) 
        b = b-a;
      else 
        a = a-b;
      }
    }
  c = c + a;
}

Dann steht halt am Ende der Wert von c in EAX.

Was wir noch nicht geschafft haben, dass der Compiler mit einem Fehler abbricht (-ansi -pedantic etc bringt da irgendwie auch nichts).

_________________
We are, we were and will not be.

Horst_H · Verfasst: Fr 16.11.12 18:16

Hallo,

tranx hat doch eine funktionierende Version gepostet.Es ist müßig das Ergebnis einer Funktino zu betrachten, die nicht tut, wofür sie vorgesehen ist.
Was mich hier nun wundert, ist ein

markieren

C#-Quelltext

1:	volatile inc c = 5;

Geht es um Mikrocontroller, wobei c in einer Interrupt-Routine geändert werden kann?

Gruß Horst

Gausi · Verfasst: Sa 17.11.12 01:17

Ich hab das Topic eröffnet, weil die Funktion tut, was sie soll, das aber eigentlich dem Code nach nicht dürfte. ;-)

Dass sie das richtige Ergebnis liefert, ist mehr oder weniger Zufall, bzw. von den Compiler-Einstellungen abhängig. Mir ging es darum, zu verstehen, was da passiert, bzw. warum der falsche Code das richtige Ergebnis liefert. Über volatile wird hier verhindert, dass der Compiler die Variable c wegoptimiert, sodass am Ende das Ergebnis der letzten Addition in EAX steht, wo eigentlich (bei korrekter Funktion) der Rückgabewert stehen sollte. Die Funktion wurde also um nutzlosen Code erweitert, der die korrekte Funktion der falsch implementierten Funktion unterbindet. Sind jetzt genug doppelte Verneinungen nicht aus diesem Text gelöscht? :nut:

_________________
We are, we were and will not be.

BenBE · Verfasst: Mi 21.11.12 23:44

Probier mal -Wall -Werror -Wextra ;-)

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme