|
HexToDec optimieren
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:
Hat jemand eine Idee?
Label1.caption := HexToDec('017772D629D68F');
Label1.caption := HexToDec([$1, $77, $72, $D6, $29, $D6, $8F]); Gruß Kostas |
AW: HexToDec optimieren
Bei Letzerem (Array-Input) kann man natürlich die BCD-Berechnungen weglassen und einfach direkt jedes Byte in einen String umwandeln (
Delphi-Quellcode:
) und diese aneinanderhängen.
Format('$%d ', [s[i]]
Nee, falsch geguckt ... geht natürlich nicht. :oops: 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:
* oder man fasst zumindestens mehrere der Hexadezimalstellen zusammen (bis zu 8 oder 16, jenachdem ob man mit Integer oder Int64 weiterrechnen kann),
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; wobei man sich dann eben auch bis zu 93% der Berechnungsdurchläufe erspart. |
AW: HexToDec optimieren
Verwende einen Lookup. Schneller geht es nicht.
Delphi-Quellcode:
Dann noch (vermutlich) statt dem indizierten String ein PAnsiChar und es wäre vermutlich noch schneller.
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]]; |
AW: HexToDec optimieren
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:
Aber das ist für meinen Anwendungsfall völlig ausreichend.
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]); @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 |
AW: HexToDec optimieren
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ß.
Delphi-Quellcode:
oder
array['0'..'z']
Delphi-Quellcode:
wenn nur Großbuchstaben (array[48..122] oder array[48..90])
array['0'..'Z']
|
AW: HexToDec optimieren
Zitat:
Delphi-Quellcode:
Erstmal Fraction -> 32 Bytes und pro Byte 2 Dezimalstellen = maximal 10^64
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 } und dann vorallem die Konstanten :angel: |
AW: HexToDec optimieren
Zitat:
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:
Delphi-Quellcode:
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.
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; |
AW: HexToDec optimieren
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. :angel: 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:
PS: Oftmals arbeitet übrigens das CASE genau auf die gleiche Weise.
i := Ord(s[i]) - 48;
if i > 10 then Dec(i, 17); ShowMessage(IntToStr(i)); |
AW: HexToDec optimieren
Zitat:
|
AW: HexToDec optimieren
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; |
AW: HexToDec optimieren
:thumb: :-D Ich gebe mich in allen belangen und ausnahmslos geschlagen. :stupid:
|
AW: HexToDec optimieren
Daß die Varianten mit und ohne Ofset gleich schnell sind, hatte ich fast erwartet, wobei das früher aber auch mal von der größe des Offsets abhing, da kleinere Vielfache von 2 direkt in einem Index-Befehl kombiniert werden können.
Aber daß nun Byte und Integer gleich schnell sind, war bissl überraschen, aber das liegt wohl an der Ivy-Architektur. Eigentlich sind ja zusätzliche umkopieroperationen nötig, um nochmal aus den Byte einen Integer zu machen. Vorallem war ich etwas überascht, daß Zugriffe auf ein dynamisches Array manchmal schneller waren, als auf ein statisches Array, und selbst bei aktivierter Indexprüfung nicht viel langsamer wurden. :shock: > i7
Code:
Rein logisch sollte doch das Ergbnis im Random der Durchschnitt aus 3 und 8 sein, was beim Math bedeutet JUMP oder nicht JUMP und stattdessen DEC,
3:
HexB0 = 219 HexB1 = 203 HexI0 = 218 HexI1 = 218 HexS = 219 HexD = 327 Math = 312 B: HexB0 = 203 HexB1 = 219 HexI0 = 218 HexI1 = 203 HexS = 203 HexD = 312 Math = 421 Random: HexB0 = 234 HexB1 = 234 HexI0 = 219 HexI1 = 234 HexS = 218 HexD = 343 Math = 1529 also 10/16-tel von 3 und 6/16-tel vom B. Und wir hatten hier über die Jahre schon oftmals den Fall, wo man zwanghaft versuchte den Code via Assembler selber zu optimieren. Abgesehn davon, daß man jetzt den Spaß hat und sich nicht mehr nur überlegen muß "Windows" und später auch noch "Windows 64" und dann bei speziallfällen noch Intel, AMD und welche Revision davon usw. Jetzt auch noch OSx, iOS, Android, welcher Handyhersteller, ......... Aber das Krasseste war, daß oft sogar die Codeoptimierung vom Delphi schon so gut war, daß man manchmal nichtmal 'ne Millisekunde rausholen konnte. :shock: |
AW: HexToDec optimieren
Sehr schön, wenn man das einfach ausprobiert. Alles unter 5% würde ich als Rauschen erachten. Bei der Messdauer von 200ms pro Durchlauf bist Du aber bei einer Genauigkeit von +-18ms, sodaß ich hier die Anzahl der Durchläufe so erhöhen würde das ein Durchlauf mindestens 1-2 Sekunden dauert.
Ferner würde ich den Zugriff an die Erfordernisse anpassen, also nicht konstant immer auf den selben Array-Index zugreifen (man sieht sehr schön, wie Cache und Prediction hier zuschlagen) sondern eben z.B. zufällig. Ich habe die Durchlaufzahl verdreifacht und bei mir kommt dann raus:
Code:
3:
HexB0 = 1467 HexB1 = 1450 HexI0 = 1046 HexI1 = 920 HexS = 905 HexD = 920 Math = 921 B: HexB0 = 904 HexB1 = 921 HexI0 = 920 HexI1 = 905 HexS = 920 HexD = 921 Math = 1061 Random: HexB0 = 999 HexB1 = 1372 HexI0 = 1576 HexI1 = 1560 HexS = 1560 HexD = 1779 Math = 7644 |
AW: HexToDec optimieren
Ich hatte das auch schon länger laufen lassen. :angel2:
Aber ich hatte natürlich auch schon das verhalten, daß bei mehreren Durchgängen heute teilweise andere Ergebnisse rauskommen, als vor ein paar Stunden. Außer beim Math sollten die Werte der jeweiligen 3 und B-Durchläufe im Durchschnitt gleich sein und Random im gleichen Verhältnis ein bissl ansteigen. Und bei Math kommt es dann auf die CPU an. In einem uralten 8086 würde Dieses bestimmt plötzlich mit großer Sicherheit das Schnellste sein. :stupid: |
AW: HexToDec optimieren
hmm
Delphi-Quellcode:
Oder habe ich etwas falsch verstanden?
{--------------------------------------------------------------}
function HexToDec(const s: Array of Byte): AnsiString; overload; //Sehr grosse Hex-Zahlen Decimal umwandeln {--------------------------------------------------------------} var total : Int64; i,n: Integer; begin total := 0; if length(s) > 8 then Exit; for i := 0 to high(s)-1 do begin total := total or S[i]; total := total shl 8; end; total := total or S[7]; Result := inttostr(total); end; Mavarik |
AW: HexToDec optimieren
Ja, denn er braucht auch mal mehr, als nur 64 Bit.
Binär könnte man das über mehrere Int64 lösen, aber die Umwandlung nach Dezimal wird dann ein bissl umständlicher. |
AW: HexToDec optimieren
Zitat:
Denke nicht das es noch schneller geht...
Delphi-Quellcode:
Mavarik
function HexToDec(const s: Array of Byte): AnsiString; overload;
//Sehr grosse Hex-Zahlen Decimal umwandeln {--------------------------------------------------------------} var a : int64; b : array[0..3] of word absolute s; c : array[0..3] of word absolute a; begin c[3] := swap(b[0]); c[2] := swap(b[1]); c[1] := swap(b[2]); c[0] := swap(b[3]); result := inttostr(a); end; |
AW: HexToDec optimieren
Das soll funktionieren, wenn in s ein String aus Hex-Ziffern steht? :gruebel:
Allgemein würde ich mich zunächst auf ein Format für große Zahlen einigen (BigInt, string etc.). Für das entsprechende Format benötigt man dann nur die Addition und Multiplikation. Der Rest ist doch trivial:
Delphi-Quellcode:
Wenn ich es nicht komplett verrissen habe, sollte das doch so funktionieren. Zum Testen kann man ja eine Klasse schreiben, die IBigInteger implementiert und das ganze aber für Int64 umsetzt. Wenn das klappt, passt man das für BigInt oder ein eigenes Format an.
Type
IBigInteger = interface Procedure Assign (n : Integer); Procedure Add (n : Integer); Procedure Multiply (n : Integer); end; Function HexToNumber (aHugeHex : Array Of AnsiChar) : IBigInteger; Var i : Integer; Begin result := CoBigInteger.Create; result.Assign(0); for i:=high(aHugeHex) downto Low(aHugeHex) do begin result.Multiply (16); result.Add (hexLookup[aHugeHex[i]]); end; return result; end; |
AW: HexToDec optimieren
Zitat:
Zitat:
|
AW: HexToDec optimieren
Hier eine alte Routine für wirklich lange Umwandlungen von Bytearrays in Radix-B-Zahlen, schnell aufgebohrt für die Situation hier. Ist etwas allgemeiner da auch andere Ziel-Basen neben 10 nöglich sind.
Delphi-Quellcode:
Habe mir nicht die Mühe gemacht, die Routine so zu ändern, daß die Eingabe nicht überschrieben wird. Ein Testprogamm für die Funktion
function base256_to_baseB(var a: array of byte; n: integer; B: byte): string;
{-n byte of big-endian base 256 number to base B string, a is destroyed} const cmap: array[0..61] of char = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'; var i,k,m: integer; w: word; d: byte; s: string; begin s := ''; {k is index of MSB of a} k := low(a); m := low(a)+n-1; repeat {One repeat iteration calculates a := a div B; d := a mod B} {initialize "carry"} w := 0; for i:=k to m do begin {loop invariant: 0 <= w < B} w := (w shl 8) or a[i]; if w>=B then begin d := w div B; w := w mod B; end else d:=0; a[i] := d; end; {set d to remainder, w is still < B!} d := byte(w); {add base R digit to result if d is not out of range} if d<sizeof(cmap) then s := cmap[d]+s else s := '?'+s; {if MSB(a) is zero increment lower bound} if a[k]=0 then inc(k); until k>m; base256_to_baseB := s; end;
Delphi-Quellcode:
liefert dann Decimal number: 10000000000000000000000000000000000000000000000000 00000000042
const
Test: array[0..24] of byte = ( $9F,$4F,$27,$26,$17,$9A,$22,$45,$01,$D7,$62,$42,$2C, $94,$65,$90,$D9,$10,$00,$00,$00,$00,$00,$00,$2A); var s: string; tmp: array[0..100] of byte; i: integer; begin {Copy because arg is destroyed} for i:=0 to sizeof(Test)-1 do tmp[i] := Test[i]; s := base256_to_baseB(tmp, sizeof(Test), 10); writeln('Decimal number: ', s); end. |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 09:22 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz