HexToDec optimieren

[Kostas]

Hallo zusammen,

hier im Forum habe ich die Funktion "HexToDec" gefunden die beliebig lange Hex Zahlen in Dezimal umwandelt.
Als Beispiel eine IMEI:412810079753871 als Hex:01 77 72 D6 29 D6 8F
Ich benötige die gleiche function nur als weitere Variante die als Parameter ein "Array of Byte" bekommt.
Also habe sie umgebaut.
Die function HexToDec addiert einfach nibble für nibble. In meinem Fall "Array of Byte" müsste man Byte für Byte
addieren. Das geht sicherlich einfacher als jedes Byte in das höherwertige nibble bzw. niederwertige nibble zu
zerlegen und zusammen zu addieren.

Delphi-Quellcode:

{--------------------------------------------------------------}
function HexToDec(const s: AnsiString): AnsiString; overload;
//Sehr grosse Hex-Zahlen Decimal umwandeln
var
   total, nibble: TBcd;
   i,n: Integer;
begin
   total := IntegerToBcd(0);
   for i := 1 to Length(s) do
   begin
     n := StrToInt('$' + s[i]);
     nibble := IntegerToBcd(n);
     BcdMultiply(total, 16, total);
     BcdAdd(total, nibble, total);
   end;
   Result := BcdToStr(total);
end;

{--------------------------------------------------------------}
function HexToDec(const s: Array of Byte): AnsiString; overload;
//Sehr grosse Hex-Zahlen Decimal umwandeln
{--------------------------------------------------------------}
var
   total, nibble: TBcd;
   i,n: Integer;
begin
   total := IntegerToBcd(0);
   for i := 0 to Length(s)-1 do
   begin
     n := (s[i] and $F0) shr 4;
     nibble := IntegerToBcd(n);
     BcdMultiply(total, 16, total);
     BcdAdd(total, nibble, total);

     n := (s[i] and $F);
     nibble := IntegerToBcd(n);
     BcdMultiply(total, 16, total);
     BcdAdd(total, nibble, total);

   end;
   Result := BcdToStr(total);
end;

Delphi-Quellcode:

  Label1.caption := HexToDec('017772D629D68F');
  Label1.caption := HexToDec([$1, $77, $72, $D6, $29, $D6, $8F]);

Hat jemand eine Idee?

Gruß Kostas

[himitsu]

Bei Letzerem (Array-Input) kann man natürlich die BCD-Berechnungen weglassen und einfach direkt jedes Byte in einen String umwandeln (Format('$%d ', [s[i]] ) und diese aneinanderhängen.
Nee, falsch geguckt ... geht natürlich nicht.
Aber jenachdem wie schnell die BCD-Berechnugen sind, kann man hier auch erstmal je 4 bis 8 der Bytes zu Integer oder Int64 zusammenfassen und dann damit weiterrechnen.


Bei Ersterem (String-Input) ist es eventuell nicht ganz so optimal jede Ziffer (Hexadezimalstelle) einzeln via StrToInt umzuwandeln und einzeln zu verrechnen.
* Da kann man entweder das StrToInt weglassen und das Char direkt umrechnen

Delphi-Quellcode:

case s[i] of
  '0'..'9': n := Ord(s[i]) - Ord('0');
  'a'..'F': n := Ord(s[i]) - Ord('a') + 10;
  'A'..'F': n := Ord(s[i]) - Ord('A') + 10;
end;

* oder man fasst zumindestens mehrere der Hexadezimalstellen zusammen (bis zu 8 oder 16, jenachdem ob man mit Integer oder Int64 weiterrechnen kann),
wobei man sich dann eben auch bis zu 93% der Berechnungsdurchläufe erspart.

[Dejan Vu]

Verwende einen Lookup. Schneller geht es nicht.

Delphi-Quellcode:

Var
  hexDigits : Array [AnsiChar] of Byte;

Procedure SetupLookup();
Begin
  hexDigits['0'] := 0;
  hexDigits['1'] := 1;
  ..
  hexDigits['9'] := 9;
  hexDigits['A'] := 10;
  ..
  hexDigits['F'] := 15;
...
End;

// Statt dem Case-Konstrukt dann
n := hexDigits[s[i]];

Dann noch (vermutlich) statt dem indizierten String ein PAnsiChar und es wäre vermutlich noch schneller.

[Kostas]

Mit dem Windows eigenen Rechner funktioniert die Umrechnung auch.
Deshalb ging ich eigentlich davon aus, es gibt einen sehr einfachen Weg Byteweise zusammenzuführen.

Ich merke gerade, mein Umbau funktioniert doch nicht auf beliebig lange Zahlen.
Es geh bis hierher:

Delphi-Quellcode:

  Label2.caption := HexToDec([$FF, $FF, $FF, $FF, $FF,
                              $FF, $FF, $FF, $FF, $FF,
                              $FF, $FF, $FF, $FF, $FF,
                              $FF, $FF, $FF, $FF, $FF,
                              $FF, $FF, $FF, $FF, $FF,
                              $FF]);

Aber das ist für meinen Anwendungsfall völlig ausreichend.

@Dejan Vu
wie ist das gemeint? es reicht nicht Bytes einzeln in Dezimal umzuwandeln und als String auszugeben.
Bei den Hex-Zahlen "01 77 72 D6 29 D6 8F" soll danach 412810079753871 herauskommen.

Gruß Kostas

[himitsu]

Das Setup kann man weglassen, wenn man stattdessen eine Konstente verwendet.
Aber zumindestens kann man mit 2 Schleifen das Var-Array befüllen.

Oder besser man macht das als Konstante, wobei es, wenn man davon ausgehen würde, daß immer nur Hex-Werte im String stehen, das Array nicht komplett von #0 bis #255 (AnsiChar) groß sein muß.
array['0'..'z'] oder array['0'..'Z'] wenn nur Großbuchstaben (array[48..122] oder array[48..90])

[himitsu]

Zitat von Kostas:

Ich merke gerade, mein Umbau funktioniert doch nicht auf beliebig lange Zahlen.
Es geh bis hierher:

Das hätte man sich auch denken können.

Delphi-Quellcode:

  MaxFMTBcdFractionSize = 64;
  { Max supported by Midas }
  MaxFMTBcdDigits =   32;
  DefaultFMTBcdScale = 6;
  MaxBcdPrecision =   18;
  MaxBcdScale     =   4;
  SizeOfFraction  = 32;
  SizeOfTBCD      = 2 + SizeOfFraction;

type
  PBcd = ^TBcd;
  TBcd  = record
    Precision: Byte;                        { 1..64 }
    SignSpecialPlaces: Byte;                { Sign:1, Special:1, Places:6 }
    Fraction: packed array [0..31] of Byte; { BCD Nibbles, 00..99 per Byte, high Nibble 1st }

Erstmal Fraction -> 32 Bytes und pro Byte 2 Dezimalstellen = maximal 10^64
und dann vorallem die Konstanten

[Dejan Vu]

Zitat von himitsu:

Das Setup kann man weglassen, wenn man stattdessen eine Konstente verwendet.
Aber zumindestens kann man mit 2 Schleifen das Var-Array befüllen.

Klar. Muss man aber nicht.

Deine zweite Idee (array ['0'..z']) würde ich nicht machen, weil der Compiler dann unnötigerweise eine Subtraktion bei jedem Arrayzugriff einfügt, und wir wollen das ja optimal schnell haben. Da denke ich, sind die paar Bytes zu verschmerzen, die man da vergeudet.

Zitat von Kostas:

@Dejan Vu
wie ist das gemeint? es reicht nicht Bytes einzeln in Dezimal umzuwandeln und als String auszugeben.
Bei den Hex-Zahlen "01 77 72 D6 29 D6 8F" soll danach 412810079753871 herauskommen.

Delphi-Quellcode:

Function FasterHexToInt (hexString : String) : LongInt; // Besser : TBigInt
Var i : Integer;
Begin
  result := 0;
  for i:=1 to length(hexString) do result*16+hexLookup[hexString[i]];
end;

So ist das gemeint. Wenn Du beliebig lange Zahlen willst, dann nimm einen Datentyp für beliebig lange Zahlen z.B. BigInt o.ä. Such mal. Findest Du schon.

[himitsu]

Es kommt drauf an, wie der Compiler der Zugriff optimiert, denn durch verschieben des Offsets (genauer der Startadresse des Arrays, für die Berechnung der Indexposition) kann man diese Substraction entfernen.
Aber man kann ja das Array auch nur hinten kürzen.

Wobei diese kleine Offset-Berechnung am Ende eh nicht auffallen würde, falls Delphi das nicht wegoptimiert, da der restliche Code dennoch wesentlich größer ist.



für 0-9 und A-F:

Delphi-Quellcode:

i := Ord(s[i]) - 48;
if i > 10 then Dec(i, 17);

ShowMessage(IntToStr(i));

PS: Oftmals arbeitet übrigens das CASE genau auf die gleiche Weise.

[Dejan Vu]

Zitat von himitsu:

für 0-9 und A-F:
[DELPHI]i := Ord(s[i]) - 48;
if i > 10 then Dec(i, 17);

Ist langsamer als ein Arrayzugriff. Egal, ob als Konstante oder mit Setup gefüllt. Bezüglich der anderen Frage: Probiere es doch einfach mal aus

[himitsu]

Nja, eigentlich ist ein INC innerhalb der Register schneller, als ein Aufruf, der sich erst an den RAM wendet.

Aber heutzutage darf man sich oftmals nicht mit mehr nur mit den Taktzyklen eines Befehls auseinandersetzen.
Vorallem da in Richtung ARM oftmals versucht wird alle Befehle möglichst gleich lange laufen zu lassen.

Und dazu kommen dann auch noch Optimierungen beim Codepfad, welches krasse auswirkungen zeigen kann, welche es früher nicht gab.
So versucht die CPU schon vorher zu bestimmen, wo der Programmcode lang läuft, steuert entsprechend die Codecache und wenn das Programm dann doch oftmals wo anders lang geht, als das Programm dachte...... siehe das letzte Messergebnis

Delphi-Quellcode:

const
  HexB0: array[#0..'F'] of Byte =  // ist egal, daß es nicht bis 255 geht
   (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    2, 3, 4, 5, 6, 7, 8, 9, 0, 0,
    0, 0, 0, 0, 0, 10, 11, 12, 13, 14,
    15);
  HexB1: array['0'..'F'] of Byte =
   (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15);

  HexI0: array[#0..'F'] of Integer =
   (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    2, 3, 4, 5, 6, 7, 8, 9, 0, 0,
    0, 0, 0, 0, 0, 10, 11, 12, 13, 14,
    15);
  HexI1: array['0'..'F'] of Integer =
   (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15);
  HexX: array[0..15] of AnsiChar = '0123456789ABCDEF';

var
  HexS: array[AnsiChar] of Byte;
  HexD: array of Byte;

procedure TForm22.FormCreate(Sender: TObject);
var
  C: AnsiChar;
  T: Cardinal;
  i, X, L, A, B: Integer;
  S: AnsiString;
  P: PAnsiChar;

begin
  A := 300000000;
  B := 300000000;

  // Hochheizen
  for i := A * 3 downto 0 do ;

  SetLength(HexD, 256);
  for i := 0 to 255 do begin
    HexS[AnsiChar(i)] := 0;
    HexD[         i ] := 0;
  end;
  for i := 0 to 9 do begin
    HexS[AnsiChar(Ord('0') + i)] := i;
    HexD[         Ord('0') + i ] := i;
  end;
  for i := 0 to 5 do begin
    HexS[AnsiChar(Ord('A') + i)] := i + 10;
    HexD[         Ord('A') + i ] := i + 10;
  end;

  SetLength(S, B);
  for i := 1 to B do
    S[i] := HexX[Random(16)];
  P := PAnsiChar(S);

  for L := 0 to 1 do begin
    if L = 0 then Tag := Ord('3') else Tag := Ord('B');
    Memo1.Lines.Add('');
    Memo1.Lines.Add(Chr(Tag) + ':');
    Memo1.Lines.Add('');

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexB0[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB0 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexB1[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB1 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexI0[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI0 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexI1[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI1 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexS[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexS = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexD[Ord(C)];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexD = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := Ord(C) - 48;
      if X > 10 then Dec(X, 17);
      if X = 0 then ;
    end;
    Memo1.Lines.Add('Math = ' + IntToStr(GetTickCount - T));
  end;

  begin
    Memo1.Lines.Add('');
    Memo1.Lines.Add('Random:');
    Memo1.Lines.Add('');

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexB0[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB0 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexB1[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB1 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexI0[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI0 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexI1[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI1 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexS[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexS = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexD[Ord(P[i])];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexD = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := Ord(P[i]) - 48;
      if X > 10 then Dec(X, 17);
      if X = 0 then ;
    end;
    Memo1.Lines.Add('Math = ' + IntToStr(GetTickCount - T));
  end;
end;