pack-Funktion optimieren

[luke2]

Hallo!

Ich habe folgende Funktion um eine große Zahl mit Hilfe der Ascii-Tabelle "einzupacken" und somit zu komprimieren.

Delphi-Quellcode:

const base=255;
var chtab:array[0..base-1] of char;

procedure initchtab;
var i,j:byte;
begin
  j:=0;
  for i := 0 to 255 do
    if i<>10 then
    begin
      chtab[j]:=chr(i);
      inc(j);
    end;
end;

function cvbase(n:int64): string;
begin
  Result := '';
  while n > 0 do
  begin
    Result := chtab[n mod base] + Result;
    n := n div base;
  end;
end;

Also wir Ihr seht sollen zum "einpacken" alle Zeichen außer das Zeilenumbruchzeichen (#10 = LF) benutzt werden.
Die Funktion initchtab, zum Initialisieren der Zeichentabelle, wird nur einmal beim Start aufgerufen.
Die Funktion cvbase dagegen wird sehr oft aufgerufen und deshalb wollte ich mal fragen, ob jemand eine Möglichkeit sieht wie ich diese Funktion noch optimieren/beschleunigen könnte?

[jaenicke]

Viel lässt sich da nicht optimieren. Du könntest vorher einmal die Stringlänge setzen und danach nur noch Zeichen an die Stellen schreiben, aber so viel wird das nicht bringen.

Was meinst du eigentlich mit komprimieren? Schließlich vergrößerst du mit deinen Funktionen ja eher die Datenmenge und komprimieren heißt doch eigentlich das Gegenteil.

[jbg]

Zitat von jaenicke:

Viel lässt sich da nicht optimieren.

Oh, doch. Die 64bit Div- und Mod-Operationen sind sehr teuer und zudem auch nicht für Divisoren kleiner 2^32 optimiert. Und wenn man dann noch das Div und Mod in einem Schwung ermittelt, kann man da noch einiges rausholen.
Aber auch entfernen der String-Konkatenation tut sein übriges dazu.

Delphi-Quellcode:

function UDivMod6432(const Dividend: Int64; Divisor: LongWord; var Rest: LongWord): Int64;
// DivMod64 für "Divisor < 2^32"
{$IFDEF CPUX64}
asm
  // in:  RCX = Dividend
  //      EDX = Divisor
  //      R8  = @Rest
  // out: RAX = Quotient
  mov rax, rcx              // Register für die Division (RDX:RAX / RCX) vorbereiten
  mov ecx, edx              // Divisor in ECX für die Division schieben
  xor rdx, rdx

  //div ecx                   // "Divisor < 2^32" ausnutzen
  db $F7, $F1  // XE2 compiler bug, es wird immer "div rcx" generiert

  mov dword ptr [r8], edx     // Rest in "Rest" schreiben
end;
{$ELSE}
asm
  // in:  [ebp+$0c]:[ebp+$08] = Dividend
  //      EAX     = Divisor
  //      EDX     = @Rest
  // out: EDX:EAX = Quotient
  push ebx
  push edx                      // Zeiger auf Rest sichern
  mov ecx, eax

  mov eax, dword ptr [ebp+$0c]  // HIGH DWORD des Dividenden als LOW DWORD für die Division laden
  xor edx, edx                  // kein HIGH DWORD bei der Division
  div ecx                       // und dividieren (EDX enthält Rest, der als Übertrag genutzt wird)

  mov ebx, eax                  // HIGH DWORD des Quotienten sichern
  mov eax, dword ptr [ebp+$08]  // LOW DWORD des Dividenden laden
  div ecx                       // und dividieren (EDX enthält Rest)

  pop ecx                       // Zeiger auf Rest wiederherstellen
  mov dword ptr [ecx], edx        // Rest in "Rest" schreiben
  mov edx, ebx                  // HIGH DWORD des Quotienten wiederherstellen
  pop ebx
end;
{$ENDIF CPUX64}

function cvbase_ANSI(n: Int64): AnsiString;
var
  Buf: array[0..7] of AnsiChar;
  Index: Integer;
  r: LongWord;
begin
  Index := Length(Buf);
  while n > 0 do
  begin
    Dec(Index);
    n := UDivMod6432(n, 255, r);
    Buf[Index] := chtab[r];
  end;
  SetString(Result, PAnsiChar(@Buf[Index]), Length(Buf) - Index);
end;

function cvbase(n: Int64): string;
var
  Buf: array[0..7] of Char;
  Index: Integer;
  r: LongWord;
begin
  Index := Length(Buf);
  while n > 0 do
  begin
    Dec(Index);
    n := UDivMod6432(n, 255, r);
    Buf[Index] := chtab[r];
  end;
  SetString(Result, PChar(@Buf[Index]), Length(Buf) - Index);
end;

UPDATE: Die 32bit assembler Version nahm eine falsche Parameterreihenfolge an.

[Aphton]

Ne Frage, warum wird #10 ignoriert? (Sag nicht, wegen dem Zeilenumbruch)
Falls du nämlich mit der Basis 256 (und nicht 255) arbeiten könntest, wäre das um einiges einfacher:

Delphi-Quellcode:

function cvbase(n:int64): string;
begin
  SetLength(Result, 8);
  Move(n, Result[1], 8);
end;

[himitsu]

string AnsiString

[luke2]

Danke jbg, das sieht schon sehr gut aus, allerdings erhalte ich in der Zeile
div ecx // und dividieren (EDX enthält Rest, der als Übertrag genutzt wird) immer den Fehler Division durch Null, egal mit welchen Werten ich cvbase aufrufe.

Zitat von Aphton:

Ne Frage, warum wird #10 ignoriert? (Sag nicht, wegen dem Zeilenumbruch)

Die Strings werden später in eine Datei gespeichert und deshalb wird ein (beliebiges) Zeichen benötigt um einen string von dem anderen zu unterscheiden.

[jbg]

Der Fehler sollte jetzt ausgebessert sein. Ich hatte noch ein wenig mit der Reihenfolge der Parameter gespielt und dabei die 32bit Assemblerversion nicht richtig angepasst.

[luke2]

Dann sage ich mal vielen Dank, es ist ungefähr 4x schneller als meine Version!

[Aphton]

Zitat von luke2:

Zitat von Aphton:

Ne Frage, warum wird #10 ignoriert? (Sag nicht, wegen dem Zeilenumbruch)

Die Strings werden später in eine Datei gespeichert und deshalb wird ein (beliebiges) Zeichen benötigt um einen string von dem anderen zu unterscheiden.

Machs doch anders:

Code:

<Länge des Blcoks><Block> <Länge des Blcoks><Block> <Länge des Blcoks><Block>