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).

zusammenfalten · markieren

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:

markieren

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

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?

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...

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

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.

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:

zusammenfalten · markieren

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.

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:

zusammenfalten · markieren

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:

zusammenfalten · markieren

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}

Wie sieht es denn eigentlich mit dem Projekt aus? 64-Bit wären schon interessant dabei.

Ich halte die Konvertierung auf 64-Bit-Assembler für eine Sackgasse. Delphi-64 ist auch ohne ASM für bestimmt 99% aller Cryptoanwendungen schnell genug, überhaupt sind 64-Bit für die meisten DEC-Algos irrelevant. Interressant ist es zB für SHA512 und abgeleitete, siehe zB die Cycles/Byte-Werte für meine Implementationen in der Tabelle.

Im übrigen reicht eine Konvertierung kaum aus; was DEC mM am meisten fehlt sind neue Entwicklungen: CTR, EAX, GCM, CMAC - Modi für die Blockchiffren, neue Stromchiffren wie Salsa/Chacha oder Sosemanuk, die neuen Hashfunktionen SHA512/tt, vom kommenden SHA3/Keccak ganz zu schweigen.

Da es scheinbar kein Feedback gibt, möchte ich doch kurz auf die Alternative DCPcrypt hinweisen.
Läuft angeblich auch mit XE2 und x64.
Werde es heute mal testweise als Ersatz für die DEC einsetzen.

Vg,
Hugie