Entwickler-Ecke
Off Topic - Warum wird hier der ggT berechnet? (C-Code inside)
Gausi - Do 15.11.12 15:08
Titel: Warum wird hier der ggT berechnet? (C-Code inside)
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. ;-)
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.)
Gammatester - Do 15.11.12 16:18
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:
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 - Do 15.11.12 16:26
Ich denke, dass dies funktionieren würde. Bin allerdings kein C-Programmierer:
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
Gausi - Do 15.11.12 16:33
@Gammatester:Ok, dann ist das zumindest schonmal kein Verhalten, was immer auftritt. :D
@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.
Tranx - 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.
Delphi-Laie - 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 - 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.
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); end. |
Als Hausaufgabe: Was wird hier ausgegeben, und welche Bedeutung hat dieser Wert? Belohnung: ein Gummipunkt :P
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. |
Gausi - 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.
Tranx - 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! ;)
Gausi - 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.
Horst_H - 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
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.
.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]
# [7] begin
subl $4,%esp
# Var a located in register edx
# Var b located in register ecx
# 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
# [10] Result:= a;
movl %edx,%eax
# [11] exit; |
Siehe:
http://www.delphibasics.co.uk/RTL.asp?Name=Self
Gruß Horst
Martok - 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
Horst_H :!:
Horst_H - Fr 16.11.12 13:09
Hallo,
Weil es so schön offtopic ist.
wer steht denn auf Gummi, was mache ich jetzt damit :?: :lol:
Delete - Fr 16.11.12 13:38
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 - Fr 16.11.12 14:02
So wir haben hier auch noch was rumgespielt, und die Funktion auf diese Art und Weise kaputt bekommen:
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).
Horst_H - 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
Geht es um Mikrocontroller, wobei c in einer Interrupt-Routine geändert werden kann?
Gruß Horst
Gausi - 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:
BenBE - Mi 21.11.12 23:44
Probier mal -Wall -Werror -Wextra ;-)
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!