Problem im Kompressionsprogramm

[Hannes91]

Hallo zusammen,

zu Testzwecken habe ich vor kurzem mit der Arbeit an einem Kompressionsprogramm begonnen, welches auf der Burrows-Wheeler-Transformation aufbaut. Nachdem ich alle hierfür benötigten Module (BWT, Move-To-Front, RLE, Huffman) fertig gestellt hatte, wollte ich nun große Dateien hiermit blockweise kodieren, um die Performance zu steigern.

Folgenden Code (Auszug) verwende ich zur Kodierung im Modul "uHuffman.pas":

Delphi-Quellcode:

function THuffman.Kodieren (sText : TAusgabe) : TAusgabe;
var
   i, j, iPos: integer;
   sZeichenBin : TAusgabe;
   KodZeichen : Array [0..255] of Array of byte;
begin
     for i := 0 to 255
     do
       begin
            if Baum[i].iHaeufigkeit > 0
            then
                begin
                     iPos := i;
                   
                     while Baum[iPos].iVater > 0
                     do
                       begin 
                            setlength(KodZeichen[i], length(KodZeichen[i]) + 1); /// <-------

                            if Baum[Baum[iPos].iVater].iLinks = iPos
                            then KodZeichen[i, High(KodZeichen[i])] := 0
                            else KodZeichen[i, High(KodZeichen[i])] := 1;

                            iPos := Baum[iPos].iVater;
                       end;
                end;
       end;
     ...

TAusgabe ist ein dynamisches Array of Byte.
KodZeichen beinhaltet nach Durchlaufen obigen Codes alle 256 möglichen Kodierungen, so müssen sie nur einmal berechnet werden und können bei der eigentlichen Kodierung abgeschrieben werden.

Nach der erfolgreichen Kodierung einiger Blöcke stürzt das Programm jedoch irgendwann an der mit dem Pfeil markierten Stelle mit einer Access Violation ab. Liegt es vielleicht an den häufigen setlength() Aufrufen?

Ich hoffe, ihr habt dazu irgendwelche Vorschläge. Anbei der gesamte Quelltext mitsamt der zu kodierenden Datei test.txt (ist die Programmdatei einer früheren Version).


Liebe Grüße

Hannes



PS: Der Fehler von heute morgen tritt nun nicht mehr auf (kein Absturz beim Einlesen von Blöcken), vielleicht handelt es sich jedoch um dieselbe Ursache!?

[ASM]

Zitat:

PS: Der Fehler von heute morgen tritt nun nicht mehr auf (kein Absturz beim Einlesen von Blöcken)

Wie ist das möglich ? Der Code steckt nämlich voller Fehler. Oder sind die inzwischen beseitigt ?:

Zunächst einmal: Vermutlich hast Du in den Compileroptionen die Bereichsüberprüfung sowie die Überlaufprüfung abgeschaltet. Das aber sollte man während der Entwicklung nie machen. So siehst Du natürlich nicht, wo eklatante Fehler im Programm stecken und wann genau sie auftreten.

In der Methode THuffman.KodiereArray() heißt es:

Code:

for i := High(sOutput) - 2 downto 0 do
      sOutput[i + 3] := sOutput[i];

Du gibst also als oberen Grenzwert der Schleifenvariable 2 Positionen vor der oberen Grenze des Arrays an ("High(sOutput) - 2"), willst dann aber innerhalb dieer Schleife eine (nicht existente) Position des Arrays belegen ("sOutput[i + 3]") ! Im Klartext eines simplen virtuellen Beispiels: High(sArray) sei 100, i wird der maximale Wert i= High(sArray)-2 = 100-2 = 98 zugewiesen, aber dann auf die Position [i+3] = [101] des Arrays zugegriffen, was zwangsläufig in die Hose geht.

In der Methode THuffman.Dekodieren(): die Variable iPos ist genau wie die Felder iLinks und iRechts des Records Baum als Integer deklariert, alle können also im Laufe der Abarbeitung durchaus einen Wert >255 enthalten. Der Wert von iPos (geholt aus den Feldern des Records) wird aber übergeben an eine Instanz von TAusgabe, welche jedoch ein Array von Byte ist. Folglich (und beobachteterweise auch tatsächlich) kommt es im Verlauf irgendwann zu der dadurch provozierten Inkompatibilität, d.h. zum Bereichsüberlauf..

Im übrigen:
Sämtliche Konstruktoren der Objekte sind im nachfolgenden nicht durch Try..Finally Blöcke gesichert, so dass im Falle eines Crashs (wie er beim derzeitigen Stand der Programmierung an verschiedenen Stellen ausgelöst wird) nicht zu einer Freigabe der von den Objekten belegten Speicherbereiche kommt. Die Folgen dürften ja bekannt sein.

Es gibt ebenso nicht einen einzigen Versuch, evt. Fehler in kritischen Passagen durch Exception-Blöcke abzufangen und dadurch genauer zu lokalisieren.

Wenig professionel ist auch die ständige Längenveränderung der dynamischen Arrays innerhalb der zahlreichen Schleifen: teilweise nehmen die Schleifenzähler enorm hohe Werte an, und bei jedem Durchgang muss das komplette betroffene Array wegen seiner Verlängerung (um gerade mal 1) immer wieder neu im Speicher umkopiert werden. Die Möglichkeit, dass sich der Rechner bei dieser extrem aufwändigen und gleichzeitig extrem schnellen Veränderung in der Verwaltung des Heaps schon mal verhaspeln könnte, ist vielleicht nicht ganz abwegig (nobody is perfect).

Es mag im Code durchaus noch weitere Stellen geben, wo derart Unzulässiges oder Fragwürdiges passiert. Ich habe die Analyse wegen der vielen Unzulänglichkeiten irgendwann aufgegeben.

[Hannes91]

Hi ASM,

zunächst möchte ich mich bei dir für deine Mühe bedanken . Schönheit und Sauberkeit sowie Optimierung des Quellcodes sind wohl hier bei mir allesamt auf der Strecke geblieben. An die try..finally - Blöcke hatte ich gar nicht mehr gedacht, zumal wir in der Schule sowieso über absolut notwendige Grundlagen (if .. then .. else ..) nicht hinausgekommen sind.

Zitat:

Vermutlich hast Du in den Compileroptionen die Bereichsüberprüfung sowie die Überlaufprüfung abgeschaltet. Das aber sollte man während der Entwicklung nie machen. So siehst Du natürlich nicht, wo eklatante Fehler im Programm stecken und wann genau sie auftreten.

Du hast ja so Recht, es war tatsächlich abgeschaltet. Sonst hätte ich wohl auch einige Unzulänglichkeiten selbst entdeckt.

Zitat:

In der Methode THuffman.Dekodieren(): die Variable iPos ist genau wie die Felder iLinks und iRechts des Records Baum als Integer deklariert, alle können also im Laufe der Abarbeitung durchaus einen Wert >255 enthalten. Der Wert von iPos (geholt aus den Feldern des Records) wird aber übergeben an eine Instanz von TAusgabe, welche jedoch ein Array von Byte ist. Folglich (und beobachteterweise auch tatsächlich) kommt es im Verlauf irgendwann zu der dadurch provozierten Inkompatibilität, d.h. zum Bereichsüberlauf..

Dieser Baum (also das Array) ist in zwei Bereiche geteilt:
- 0..255 enthält die eigentlichen Zeichen
- 256..510 beinhaltet die Knoten/Väter
Beim Dekodieren beginnt der Algorithmus am obersten Knoten/ der Wurzel und arbeitet sich zunehmend tiefer in die Äste, sodass als Rückgabewert von iPos nur der Wertebereich 0..255 in Frage kommt. Ist leider nicht richtig geglückt, da eigentlich Byte ausreichen würde, iPos jedoch als integer deklariert ist.

Zitat:

Wenig professionel ist auch die ständige Längenveränderung der dynamischen Arrays[...]

Zu meiner Verteidigung: Ich wollte die Speicherverwaltung lieber nicht antasten, bevor nicht der Rest soweit steht (zugegeben mit Schwächen).

---
Ich habe kaum deine Anmerkungen berücktsichtigt, schon funktioniert's. (Oh, was für eine Überaschung. )

So, nochmals vielen Dank für die Opferung deiner Zeit, ich nehme mir deine Ratschläge sehr zu Herzen.

Liebe Grüße und noch einen schönen Nachmittag

Hannes

[himitsu]

Projektoptionen > Bereichsprüfung aktivieren