Der DEC x32 ASM in x64/PurePascal Konvertierungsthread

[Assertor]

Hallo,

ich habe in den letzten Tagen einige Stunden mit der DEC verbracht. Nun sitze ich an einem kleinen Problem fest, wo ich Ideen brauche (Alternativtitel: DEC ASM Portierung 1 von vielen).

Delphi-Quellcode:

procedure Increment8(var Value; Add: LongWord); assembler;
// Value := Value + 8 * Add
// Value is array[0..7] of LongWord
asm
      MOV     ECX,EDX
      LEA     EDX,[EDX * 8]
      SHR     ECX,29 // 12/13/2011 Fixed
      ADD     [EAX].DWord[ 0],EDX
      ADC     [EAX].DWord[ 4],ECX
      ADC     [EAX].DWord[ 8],0
      ADC     [EAX].DWord[12],0
      ADC     [EAX].DWord[16],0
      ADC     [EAX].DWord[20],0
      ADC     [EAX].DWord[24],0
      ADC     [EAX].DWord[28],0
      JC      HashingOverflowError
end;

Das ganze findet bei Hashfunktionen seine Anwendung. Konkret geht es um die Bit-Zählung, die in Hashkalkulationen einfließt.

Ich habe jetzt die Wahl: x64 ASM oder PurePascal.

Anwendungsbeispiel für o.g. Funktion:

Delphi-Quellcode:

  SwapLongBuffer(FCount, FCount, 4);
  PLongWord(@FBuffer[FBufferSize - 16])^ := FCount[3];
  PLongWord(@FBuffer[FBufferSize - 12])^ := FCount[2];
  PLongWord(@FBuffer[FBufferSize -  8])^ := FCount[1];
  PLongWord(@FBuffer[FBufferSize -  4])^ := FCount[0];
  DoTransform(Pointer(FBuffer));

Ich habe da so meine Probleme, Increment8 ohne großen Aufwand in PurePascal umzusetzen (ich komme ja nicht an die Carry Flags).

Ideen für eine in dem Anwendungsbeispiel taugliche Umsetzung eines 256 bit Integers? 4 UInts, da auch 32 Byte? Wie sieht es da mit Problemen im oberen Bereich von 2^63−1 aus? Ich will ja alte Delphi Versionen ebenfalls unterstützen...

Gruß
Assertor

[NamenLozer]

Bezüglich Carry-Flag: Mein erster Gedanke war, die Überlaufprüfung des Compilers zu verwenden. Du könntest für die Funktion die Überlaufprüfung aktivieren und die EIntOverflow-Exception abfangen. Sonderlich schnell ist das vermutlich aber nicht, und auch nicht sonderlich schön zu schreiben. Vielleicht fällt mir ja noch was besseres ein...

Dein Anwendungsbeispiel verstehe ich übrigens nicht: Wo kommt da die Funktion Increment8 vor?

[Uwe Raabe]

Zitat von NamenLozer:

Dein Anwendungsbeispiel verstehe ich übrigens nicht: Wo kommt da die Funktion Increment8 vor?

Die ganze Prozedur heißt so...

Edit: Quatsch! Frage falsch verstanden...

[Assertor]

Zitat von Uwe Raabe:

Zitat von NamenLozer:

Dein Anwendungsbeispiel verstehe ich übrigens nicht: Wo kommt da die Funktion Increment8 vor?

Die ganze Prozedur heißt so...

Nein. Entschuldigung, war zu spät und ich steck gerade im Code.

Das Anwendungsbeispiel nutzt das Array of Longword (FCount), welches per Increment8(FCount, Size) vorher manipuliert wird.

@NamenLozer: Per Exception programmiere ich nicht

Kenn sich vielleicht jemand mit den FPC/XE2 kompatiblen x64 ABIs aus?

Gruß
Assertor

[BUG]

Für pures Pascal konnte ich mir vorstellen, dass man den Wert in kleinere Stücken zerlegt (63 oder 56 Bit) und sich damit quasi ein eigenes carry-Bit schafft.

Aber es wäre schon merkwürdig, wenn für x64 keine passende Instruktionen gäbe.

[NamenLozer]

Ich hab zwar keine Ahnung, was eine FPC/XE2 kompatible x64 ABI ist, aber ich habe einfach mal selbst eine PurePascal-Variante für 32-Bit geschrieben:

Delphi-Quellcode:

type
  TData = packed array[0..7] of LongWord;

procedure Increment8Pure(var Value; Add: LongWord);
var
  HiBits: LongWord;
  Add8: LongWord;
  Data: TData absolute Value;
  Carry: Boolean;
  procedure AddC(var Value: LongWord; const Add: LongWord; var Carry: Boolean); inline;
  begin
    if Carry then
    begin
      Value := Value + 1;
      Carry := (Value = 0); // we might cause another overflow by adding the carry bit
    end
    else
      Carry := False;

    Value := Value + Add;
    Carry := Carry or (Value < Add); // set Carry Flag on overflow
  end;
begin
  HiBits := Add shr 29; // Save most significant 3 bits in case an overflow occurs
  Add8 := Add * 8;
  Carry := False;

  AddC(Data[0], Add8, Carry);
  AddC(Data[1], HiBits, Carry);
  AddC(Data[2], 0, Carry);
  AddC(Data[3], 0, Carry);
  AddC(Data[4], 0, Carry);
  AddC(Data[5], 0, Carry);
  AddC(Data[6], 0, Carry);
  AddC(Data[7], 0, Carry);

  if Carry then
    HashingOverflowError;
end;

Im Anhang befindet sich zur Sicherheit ein Testprogramm, das einige Werte addiert und dabei die Ergebnisse meiner Funktion mit dem Original vergleicht. Es werden ein paar Werte übersprungen („boost“), weil es natürlich im wahrsten Sinne des Wortes ewig dauern würde, alle 2^XXX Werte durchzuiterieren, aber die relevanten Konstellationen sind denke ich abgedeckt. Natürlich besteht meine Funktion den Test, sonst würde ich sie ja nicht hier posten

Wie gesagt ist die Funktion für 32-Bit-Systeme ausgelegt, da ich 1. nur ein 32-Bit-Windows und 2. nur ein 32-Bit-Delphi besitze. Sollte aber kein Problem sein, sie ggf. auf 64 Bit anzupassen.

[jaenicke]

Zitat von NamenLozer:

Wie gesagt ist die Funktion für 32-Bit-Systeme ausgelegt, da ich 1. nur ein 32-Bit-Windows und 2. nur ein 32-Bit-Delphi besitze. Sollte aber kein Problem sein, sie ggf. auf 64 Bit anzupassen.

Sie funktioniert mit XE2 für 64-Bit 1:1 genauso. Zum Vergleich habe ich kurz die Assemblervariante auf 64-Bit umgeschrieben:

Delphi-Quellcode:

procedure Increment8(var Value; Add: LongWord); assembler;
asm
  MOV EBX,EDX
  LEA EDX,[EDX * 8]
  SHR EBX,29 // 12/13/2011 Fixed
  ADD [ECX].DWord[ 0],EDX
  ADC [ECX].DWord[ 4],EBX
  ADC [ECX].DWord[ 8],0
  ADC [ECX].DWord[12],0
  ADC [ECX].DWord[16],0
  ADC [ECX].DWord[20],0
  ADC [ECX].DWord[24],0
  ADC [ECX].DWord[28],0
  JC HashingOverflowError
end;

Der Test läuft 1:1 durch.

Insgesamt sieht das also so aus mit deiner Variante integriert:

Delphi-Quellcode:

procedure Increment8(var Value; Add: LongWord); {$IFNDEF PUREPASCAL} assembler; {$ENDIF !PUREPASCAL}
// Value := Value + 8 * Add
// Value is array[0..7] of LongWord
{$IFDEF PUREPASCAL}
var
  HiBits: LongWord;
  Add8: LongWord;
  Data: TData absolute Value;
  Carry: Boolean;
  procedure AddC(var Value: LongWord; const Add: LongWord; var Carry: Boolean); inline;
  begin
    if Carry then
    begin
      Value := Value + 1;
      Carry := (Value = 0); // we might cause another overflow by adding the carry bit
    end
    else
      Carry := False;

    Value := Value + Add;
    Carry := Carry or (Value < Add); // set Carry Flag on overflow
  end;
begin
  HiBits := Add shr 29; // Save most significant 3 bits in case an overflow occurs
  Add8 := Add * 8;
  Carry := False;

  AddC(Data[0], Add8, Carry);
  AddC(Data[1], HiBits, Carry);
  AddC(Data[2], 0, Carry);
  AddC(Data[3], 0, Carry);
  AddC(Data[4], 0, Carry);
  AddC(Data[5], 0, Carry);
  AddC(Data[6], 0, Carry);
  AddC(Data[7], 0, Carry);

  if Carry then
    HashingOverflowError;
end;
{$ELSE !PUREPASCAL}
  {$IFDEF CPUX86}
  asm
    MOV ECX,EDX
    LEA EDX,[EDX * 8]
    SHR ECX,29 // 12/13/2011 Fixed
    ADD [EAX].DWord[ 0],EDX
    ADC [EAX].DWord[ 4],ECX
    ADC [EAX].DWord[ 8],0
    ADC [EAX].DWord[12],0
    ADC [EAX].DWord[16],0
    ADC [EAX].DWord[20],0
    ADC [EAX].DWord[24],0
    ADC [EAX].DWord[28],0
    JC HashingOverflowError
  end;
  {$ENDIF CPUX86}
  {$IFDEF CPUX64}
  asm
    MOV EBX,EDX
    LEA EDX,[EDX * 8]
    SHR EBX,29 // 12/13/2011 Fixed
    ADD [ECX].DWord[ 0],EDX
    ADC [ECX].DWord[ 4],EBX
    ADC [ECX].DWord[ 8],0
    ADC [ECX].DWord[12],0
    ADC [ECX].DWord[16],0
    ADC [ECX].DWord[20],0
    ADC [ECX].DWord[24],0
    ADC [ECX].DWord[28],0
    JC HashingOverflowError
  end;
  {$ENDIF CPUX64}
{$ENDIF !PUREPASCAL}

[himitsu]

Eventuell so?

Die höherbittigen Additionen müssen ja nicht mehr ausgeführt werden, wenn sie nicht nötig sind.
Bin noch etwas müde, aber ich glaube, man kann die beiden IFs auch noch kombinieren, falls nötig.
(also nicht nur über ein billiges OR diese 1-zu-1 zusammenzuhängen)

Delphi-Quellcode:

{$IFDEF PUREPASCAL}
  function AddV(var Value: LongWord; const Add: LongWord): Boolean; inline;
  var
    Temp: LongWord;
  begin
    Temp := Value;
    Value := Value + Add;
    Result := Value < Temp;
  end;
  function AddC(var Value: LongWord): Boolean; inline;
  begin
    Inc(Value);
    Result := Value = 0;
  end;
var
  Data: TData absolute Value;
begin
  if AddV(Data[0], Add shl 3) and AddC(Data[1]) and AddC(Data[2]) and AddC(Data[3])
      and AddC(Data[4]) and AddC(Data[5]) and AddC(Data[6]) and AddC(Data[7]) then
    HashingOverflowError;
  if AddV(Data[1], Add shr 29) and AddC(Data[2]) and AddC(Data[3])
      and AddC(Data[4]) and AddC(Data[5]) and AddC(Data[6]) and AddC(Data[7]) then
    HashingOverflowError;
end;
{$ELSE !PUREPASCAL}

Natürlich ohne vollständige Auswertung der booleanische Ausdrücke und ohne Überlaufprüfung.


[add]

Delphi-Quellcode:

  if ((AddV(Data[0], Add shl 3) and AddC(Data[1])) or AddV(Data[1], Add shr 29)) and AddC(Data[2])
      and AddC(Data[3]) and AddC(Data[4]) and AddC(Data[5]) and AddC(Data[6]) and AddC(Data[7]) then
    HashingOverflowError;

Hoffentlich isses richtig.

Aber für 64 Bit würde ich das auch noch auf 64 Bit umstellen und es so weiter zu verkürzen.

Delphi-Quellcode:

{$IFDEF PUREPASCAL}
  function AddV(var Value: UInt64; const Add: UInt64): Boolean; inline;
  var
    Temp: UInt64;
  begin
    Temp := Value;
    Value := Value + Add;
    Result := Value < Temp;
  end;
  function AddC(var Value: UInt64): Boolean; inline;
  begin
    Inc(Value);
    Result := Value = 0;
  end;
var
  Data: TData64 absolute Value;  // array[0..3] of UInt64;
begin
  if AddV(Data[0], UInt64(Add) shl 3) and AddC(Data[1]) and AddC(Data[2]) and AddC(Data[3]) then
    HashingOverflowError;
end;

//////////////////////////////////////

{$IFDEF PUREPASCAL}
  function AddC(var Value: UInt64): Boolean; inline;
  begin
    Inc(Value);
    Result := Value = 0;
  end;
var
  Data: TData64 absolute Value; // array[0..3] of UInt64;
  Temp: UInt64;
begin
  Temp := Value;
  Inc(Data[0], UInt64(Add) shl 3);
  if (Value < Temp) and AddC(Data[1]) and AddC(Data[2]) and AddC(Data[3]) then
    HashingOverflowError;
end;

[Assertor]

Hallo,

Wahnsinn! Ihr habt mich gerade wieder daran erinnert, warum ich mich in der DP angemeldet habe

Mit FPC kompatibles x64 ABI (Application Binary Interface) meinte ich Instruktionen, die auch der FPC compiler schluckt, u.U. wegen geänderter Calling Convention. Ob das hier relevant ist, ist eine andere Frage. Leider haben sowohl Delphi als auch FPC so ihre Probleme mit x64 Inline Assembler...

Ich werde das ganze Testen und gebe Feedback, ich sitze noch an den Unittests für die LowLevel (SwapBits etc) und Formatklassen, dann geht es weiter

Zwischenstand zur DEC ist: Was bisher wieder läuft, läuft überall (x32/x64 Delphi, x32 C++ Builder soweit ich es testen kann, FPC x64). Es fehlen noch ein ASM Block im Cipher, sowie die CRCs und Randomfunktionen. Letzteres wird Tricky, weil Hagen mit QueryPerformanceCounter arbeitet - unter FPC oder OSX geht das nicht so gut

Ich stelle hier schonmal die nächste ASM Funktion zur Diskussion und Hijacke damit meinen eigenen Thread:

Delphi-Quellcode:

{ TODO : Consider implementing IDEAMul() as PurePascal if porting to FPC }
function IDEAMul(X, Y: LongWord): LongWord; assembler;
asm
       AND    EAX,0FFFFh
       JZ     @@1
       AND    EDX,0FFFFh
       JZ     @@1
       MUL    EDX
       MOV    EDX,EAX
       MOV    ECX,EAX
       SHR    EDX,16
       SUB    EAX,EDX
       SUB    CX,AX
       ADC    EAX,0
       RET
@@1:   LEA    EAX,[EAX + EDX - 1]
       NEG    EAX
end;

Ich habe übrigens auch bisher alle Änderungen, Wünsche und validen Bugmeldungen, die im Laufe der letzten 2 Jahre in der DP zur DEC eingegangen sind, verarbeitet. Der Text im ChangeLog hat schon gut 22 Lines von großen Änderungen.

Jetzt erstmal Kaffee...

Gruß
Assertor

[jbg]

Zitat von jaenicke:

Delphi-Quellcode:

procedure Increment8(var Value; Add: LongWord); assembler;
asm
  MOV EBX,EDX
  LEA EDX,[EDX * 8]
  SHR EBX,29 // 12/13/2011 Fixed
  ADD [ECX].DWord[ 0],EDX
  ADC [ECX].DWord[ 4],EBX
  ADC [ECX].DWord[ 8],0
  ADC [ECX].DWord[12],0
  ADC [ECX].DWord[16],0
  ADC [ECX].DWord[20],0
  ADC [ECX].DWord[24],0
  ADC [ECX].DWord[28],0
  JC HashingOverflowError
end;

1. Das "assembler" ist in Delphi nicht mehr notwendig und wird nur zur Abwärtskompatibilität zu Turbo Pascal unterstützt.
2. Ein [ECX] reicht nicht aus, da dadurch nur auf Speicher in den ersten 4 GB zugegriffen werden kann. Der Addressraum unter x64 aber um einiges größer ist. Also muss [RCX] benutzt werden.
3. Du zerstörst das non-volatile RBX Register. Da hat man nun so viele "Freiwild" Register und du nimmst gerade eines, dass beim Rücksprung wieder seinen originalen Inhalt haben muss.
   Also am besten RBX durch EAX, R9D, R10D oder R11D ersetzen.
4. Ob das "JC HashingOverflowError" so gut mit der strikten Aufrufkonvention unter x64 vereinbar ist, kann ich jetzt nicht beurteilen, da ich den Code des Sprungziels nicht kenne.

Und wenn man schon 64bit Assembler hat kann man den auch gleich verwenden:

Delphi-Quellcode:

procedure Increment8(var Value; Add: LongWord);
asm
  SHL RDX, 3 // the caller writes to EDX what automatically clears the high DWORD of RDX
  ADD QWORD PTR [RCX     ], RDX
  ADC QWORD PTR [RCX +  8], 0
  ADC QWORD PTR [RCX + 16], 0
  ADC QWORD PTR [RCX + 24], 0
  JC HashingOverflowError
end;