x64 assembler int128

[stefc]

Ich habe folgende vier funktionen zum Thema Int128 verarbeitung (Multiplikation und Addition) die ich für krypto Methoden einsetze.

Ich habe die jeweils in reinem Pascal und x64 Assembler Code (weil der kürzer ist). Der Code funktioniert auch reibungslos solange ich mit ABI Calling Convention unterwegs bin. Da ich unter OSX entwickel bzw. Linux deployment stattfindet ist auch soweit alles ok.

Allerdings ist bei meinem Code derzeit Windows mit Assembler aussen vor, da dort eine andere Calling-Convention zum Einsatz kommt. u.a. kann ich einen Return Value vom Typ UInt128 nicht mit zwei 64-Bit Registern abbilden %rax:%rdx.

Frage: Fühlt sich jemand in der Lage die vier Assembler Methoden auch für Win64 Platform bereitzustellen ? Dann müsste ich auf der Platform nicht auf pascal Code zurückfallen.

Oder weiss jemand ob eine Int128 Unterstützung auf der Roadmap vom FPC irgendwo steht? Der Ursprungscode der mir vorliegt wurde mit gcc compiliert und dort ist eine native Int128 Unterstützung im Compiler vorhanden was den Assembler Code natürlich eleminieren würde

Es würde mich auch freuen wenn jemand die folgenden vier Methoden ebenfalls gebrauchen könnte, über jedweges Feedback freue ich mich.

Gruß Stefc

Code: Alles auswählen

 
{$IFDEF LITTLE_ENDIAN}
	UInt128 = packed record 
		Lo,Hi: UInt64;
	end;
{$ENDIF}
 
{$IFDEF BIG_ENDIAN}
	UInt128 = packed record 
		Hi,Lo: UInt64;
	end;
{$ENDIF}
{$IFDEF CPUX86_64}
function mul64x64_128(a,b: UInt64): UInt128; nostackframe; register; assembler;
asm
	mov rax, b
	mov rdx, a
	mul rdx 
end;
 
// %rdi,%rsi, %rdx => rax:rdx
 
function add128_64(a: UInt128; b: UInt64): UInt128; nostackframe; register; assembler;
asm
	add rdi, b
	jnc @1
	inc rsi
@1: 
	mov rdx, rsi
	mov rax, rdi
end;
 
function add128(a,b: UInt128): UInt128; nostackframe; register; assembler;
asm
	add rdi, rdx
	jnc @1
	inc rsi
@1:	
	add rsi, rcx
	mov rdx, rsi
	mov rax, rdi
end;
 
function create128(hi,lo: UInt64): UInt128; nostackframe; register; assembler;
asm
	mov rdx, hi 
	mov rax, lo  
end;
 
{$ELSE}
 
function mul64x64_128(a,b: UInt64): UInt128;
const
	HWORD_BITS = 32;
   	HWORD_MASK = $FFFFFFFF;  
 var
 	a_hi,a_lo,b_hi,b_lo: UInt32;
 	x0,x1,x2,x3: UInt64;
 begin
 	a_hi := a shr HWORD_BITS;
 	a_lo := a and HWORD_MASK;
 	b_hi := b shr HWORD_BITS;
 	b_lo := b and HWORD_MASK;
 
 	x0 := UInt64(a_hi) * b_hi;
 	x1 := UInt64(a_lo) * b_hi;
	x2 := UInt64(a_hi) * b_lo;
 	x3 := UInt64(a_lo) * b_lo;
 
	// this cannot overflow as (2^32-1)^2 + 2^32-1 < 2^64-1
	x2 := x2 + (x3 shr HWORD_BITS);
 
	// this one can overflow
	x2 := x2 + x1;
 
 	// propagate the carry if any
 	x0 := x0 + UInt64(x2 < x1) shl HWORD_BITS;
 
 	Result.Hi := x0 + (x2 shr HWORD_BITS);
 	Result.Lo := ((x2 and HWORD_MASK) shl HWORD_BITS) + (x3 and HWORD_MASK);
end;
 
function add128_64(a: UInt128; b: UInt64): UInt128; 
var
	p: UInt64;
begin
	p := a.Lo;
	Result.Lo := a.Lo + b;
	Result.Hi := a.Hi + Ord(Result.Lo < p);
end;
 
function add128(a,b: UInt128): UInt128;	
var
	p: UInt64;
begin
	p := a.Lo;
	Result.Lo := a.Lo + b.Lo;
	Result.Hi := a.Hi + b.Hi + Ord(Result.Lo < p);
end;
 
function create128(hi,lo: UInt64): UInt128; 
begin
	Result.Lo := lo;
	Result.Hi := hi;
end; 
 
{$ENDIF} 

[ruewa]

Allerdings ist bei meinem Code derzeit Windows mit Assembler aussen vor, da dort eine andere Calling-Convention zum Einsatz kommt. u.a. kann ich einen Return Value vom Typ UInt128 nicht mit zwei 64-Bit Registern abbilden %rax:%rdx.

Hallo Stefc,

richtig weiterhelfen kann ich Dir leider nicht, da ich ebenfalls Windows-Abstinenzler bin. Aber vielleicht hilft das schon mal:

1) Die Microsoft x64 calling convention sieht die Rückgabe eines i128-Resultats im Register xmm0 vor, siehe https://msdn.microsoft.com/en-us/library/7572ztz4.aspx:

Code: Alles auswählen

__m128 func2(float a, double b, int c, __m64 d); 
// Caller passes a in XMM0, b in XMM1, c in R8, d in R9, 
// callee returns __m128 result in XMM0.

Da gibt es m.E. aber zwei Probleme:

a) Mit den xmm-Registern zu arbeiten scheint nicht ganz trivial zu sein (hab mich da allerdings noch nicht eingefummelt), u.U. muß die CPU eine bestimmte SSE-Instructionsset-Erweiterung beherrschen, die dann erstmal abgefragt werden muß (wobei die FPC-Unit "CPU" von Haus aus eine boolsche Variable "is_sse3_cpu" zur Verfügung stellt). Das dürfte aber das kleinere Problem sein.

b) Ob sich der FPC-Compiler unter Windows nun an die Microsoft-Konvention hält oder ungerührt seine eigene "register"-Konvention durchzieht (deren x86_64-Variante ich, vielleicht irrtümlich, bisher immer für deckungsgleich mit der "System V AMD64 ABI" gehalten habe), ist ebenfalls unklar. Im FPC Programmers Guide findet man bestenfalls nebulöse Formulierungen wie

Code: Alles auswählen

Subroutines will modify a number of registers (the volatile registers). The list of registers that are modified is highly dependent on the processor, calling convention and ABI of the target platform.

Damit läßt sich nicht viel anfangen - die Welt ist halt kompliziert, aber das wußten wir auch so schon... Auch anderweitig habe ich trotz intensiver Recherche nie etwas Genaueres gefunden - und in meinem asm-Code deshalb sicherheitshalber Anweisungen eingefügt, Parameter explizit in Register zu schieben, wo sie auf meinem Rechner zwar ohnehin schon waren, woanders aber vielleicht auch nicht... Vielleicht wäre es eine dankbare Aufgabe, diese Dinge mal detailliert zu dokumentieren.

2) Eine nicht mal besonders kostspielige Möglichkeit, diesen gordischen Knoten zu durchschlagen, könnte m.E. sein, Deine Routinen nicht als Funktionen, sondern als Prozeduren zu implementieren, indem Du beim Aufruf als dritten Parameter die Adresse des Ziel-Records (d.h. als var bzw. const) übergibst und die Ergebnisse innerhalb des Assembler-Blocks direkt ins RAM schreibst (zugegeben, das Handling wäre dann nicht mehr so schön).

Natürlich muß man ein bißchen aufpassen, in welcher Reihenfolge man die Parameter in die Arbeitsregister verschiebt, die Record-Adresse als erstes nach RSI oder RDI zu schieben, ist keine gute Idee, weil man sich damit u.U. einen der anderen Parameter überschreibt. Die Reihenfolge der (Integer-) x86-64-Parameter-Übergabe ist nach der

• System V AMD64 ABI: RDI, RSI, RDX, RCX, R8, R9
• Microsoft x64 calling convention: RCX, RDX, R8, R9

Wie gesagt, es ist unklar, wie der FP-Compiler auf verschiedenen Plattformen hier genau verfährt, aber bei nur drei Parametern lassen sich ja problemlos Wege finden, alle eventuellen Konflikte zu umschiffen.

Gruß Rüdiger

[Horst_h]

Hallo,

ich konnte es nicht unter linux64 2.6.4 kompilieren.

Code: Alles auswählen

//Compiler Switches:
//http://www.freepascal.org/docs-html/prog/progap7.html dort heißt es :
{$IFDEF ENDIAN_LITTLE} // und nicht{$IFDEF LITTLE_ENDIAN}
 

gibt es kein ADC mehr.EIn Sprung ist doch viel Zeit intensiver?

Code: Alles auswählen

 
    function add128_64(a: UInt128; b: UInt64): UInt128; nostackframe; register; assembler;
// Var a located in register rdi / rsi
// Var b located in register rdx
// RAX = lo ; RDX = Hi
  asm
       add rdi, b
       mov rdx, rsi
       mov rax, rdi
       ADC RDX,0
    end;

Die 64 -Bit version von FPC nutzt doch für Fliesskommaberechnungen immer XMMx. Deshalb kann ich mir gut vorstellen, das man die in Assembler auch direkt nutzen kann.

Zudem finde ich ruewa Einwand mit der Nutzung von proceduren und var/const Parametern, besonders in 32-Bit und normalen Pascal sehr richtig.Es wird ja mehr Zeit mit Byte-schubsen als mit der Berechnung vertrödelt.

Gruß Horst

[stefc]

Hallo Horst,

vielen Dank für deine Anmerkungen. Das mit dem Define war mein Fehler ich habe falsch gelesen und einen Wort Dreher eingetippt. Da aber weder LITTLE_ENDIAN als auch BIG_ENDIAN bei mir gesetzt waren, habe ich fälschlicherweise vermutet das die nur beim Compilerbau gesetzt sind. Habe dann kurzerhand bei mir LITTLE_ENDIAN selbst gesetzt Habe ich jetzt aber korregiert, vielen Dank für den Hinweis.

Noch viel besser finde ich deine Frage bzgl. ADC, das gibt es natürlich noch und habe es gleich benutzt um die Routinen noch zu verbessern so das der Sprung entfällt.
Man sieht das mein Assemblerwissen doch ein wenig in die Jahre gekommen ist. Für andere nochmal ADD und ADC unterscheiden sich darin das ADC ein evtl. aus einer vorherigen ADD Operation gesetztes Carry-Flag (CF) mit addiert wird.

Code: Alles auswählen

function add128_64(a: UInt128; b: UInt64): UInt128; nostackframe; register; assembler;
asm
	add rdi, b
	mov rdx, rsi
	mov rax, rdi
	adc rdx, 0
end;
 
function add128(a,b: UInt128): UInt128; nostackframe; register; assembler;
asm
	add rdi, rdx
	adc rsi, rcx
	mov rdx, rsi
	mov rax, rdi
end;
 

Das mit dem XMM Register für die Rückgabe einer 128-Bit Struktur unter Windows kann ich leider nicht bestätigen. Ein kleiner Test unter Windows deutete eigentlich eher darauf hin das ein 64-Bit Register ein Pointer auf die 128-Bit Struktur des Result-Values zeigt. Die XMM Register kommen ausschliesslich bei Floating-Points zur Verwendung was bei mir ja mit Ganzzahlen nicht der Fall ist. Das was du aus dem Microsoft Calling convention zitierst. für die Rückgabe eines i128 Wertes sieht super aus ist allerdings vermutlich nicht vom FPC Compiler eingehalten
Ich muss aber nochmal meine Lanze brechen für die Umsetzung der AMD64 ABI Calling Convention. Ich finde es super gut das der FPC Compiler meine UInt128 Records als 2x 64-Bit Register übergibt und auch noch als zwei Register zurückgibt wenn ich mit register call convention arbeite. Und die 6 Register reichen auch prima aus. Wenn ich mit var oder const arbeite würde ich mit Speicher Pointern arbeiten was den derzeit einfachen Assembler Code mit Speicher-Adressierungen in meinen Augen verunglimpfen. Das passiert im Fallback Pascal Code vermutlich eh unter der Haupe, da finde ich es aber nicht so schlimm.

Meine Intention ist ja auch das es unter einem 64-Bit x64 Linux in Produktion geht, unter OSX entwickel ich, insofern ist für mich der Windows Bereich eher akademischer Natur. Und sobald der Compiler auch native mit 128-Bit Integern umgehen kann fällt eh alles weg

Hallo,

ich konnte es nicht unter linux64 2.6.4 kompilieren.

Code: Alles auswählen

//Compiler Switches:
//http://www.freepascal.org/docs-html/prog/progap7.html dort heißt es :
{$IFDEF ENDIAN_LITTLE} // und nicht{$IFDEF LITTLE_ENDIAN}
 

gibt es kein ADC mehr.EIn Sprung ist doch viel Zeit intensiver?

Code: Alles auswählen

 
    function add128_64(a: UInt128; b: UInt64): UInt128; nostackframe; register; assembler;
// Var a located in register rdi / rsi
// Var b located in register rdx
// RAX = lo ; RDX = Hi
  asm
       add rdi, b
       mov rdx, rsi
       mov rax, rdi
       ADC RDX,0
    end;

Die 64 -Bit version von FPC nutzt doch für Fliesskommaberechnungen immer XMMx. Deshalb kann ich mir gut vorstellen, das man die in Assembler auch direkt nutzen kann.

Zudem finde ich ruewa Einwand mit der Nutzung von proceduren und var/const Parametern, besonders in 32-Bit und normalen Pascal sehr richtig.Es wird ja mehr Zeit mit Byte-schubsen als mit der Berechnung vertrödelt.

Gruß Horst

[stefc]

Hallo Rüdiger,

siehe auch meine vorherige Antwort an Horst. Kurz gefasst ist mein Fazit mit der ABI AMD64 Calling Convention lässt es sich sehr gut leben, die MS Conventionen sind vermutlich gerade bei den i128 Werten vom FPC nicht so eingehalten, und mit XMM Registern möchte ich mich derzeit beschäftigen solange ich im Produktionscode eher mit Linux Rechner zu tun habe.

mit var & const Übergabe bin ich übrigends angefangen, finde den jetzigen register Code aber einfacher und somit schöner. Ich verstehe auch nicht weshalb bei MS mit nur 4 Registern bei der Calling Convention gearbeitet wird. Aber so ist das mit Standards.

Gruß Stefc

Allerdings ist bei meinem Code derzeit Windows mit Assembler aussen vor, da dort eine andere Calling-Convention zum Einsatz kommt. u.a. kann ich einen Return Value vom Typ UInt128 nicht mit zwei 64-Bit Registern abbilden %rax:%rdx.

Hallo Stefc,

richtig weiterhelfen kann ich Dir leider nicht, da ich ebenfalls Windows-Abstinenzler bin. Aber vielleicht hilft das schon mal:

1) Die Microsoft x64 calling convention sieht die Rückgabe eines i128-Resultats im Register xmm0 vor, siehe https://msdn.microsoft.com/en-us/library/7572ztz4.aspx:

Code: Alles auswählen

__m128 func2(float a, double b, int c, __m64 d); 
// Caller passes a in XMM0, b in XMM1, c in R8, d in R9, 
// callee returns __m128 result in XMM0.

Da gibt es m.E. aber zwei Probleme:

a) Mit den xmm-Registern zu arbeiten scheint nicht ganz trivial zu sein (hab mich da allerdings noch nicht eingefummelt), u.U. muß die CPU eine bestimmte SSE-Instructionsset-Erweiterung beherrschen, die dann erstmal abgefragt werden muß (wobei die FPC-Unit "CPU" von Haus aus eine boolsche Variable "is_sse3_cpu" zur Verfügung stellt). Das dürfte aber das kleinere Problem sein.

b) Ob sich der FPC-Compiler unter Windows nun an die Microsoft-Konvention hält oder ungerührt seine eigene "register"-Konvention durchzieht (deren x86_64-Variante ich, vielleicht irrtümlich, bisher immer für deckungsgleich mit der "System V AMD64 ABI" gehalten habe), ist ebenfalls unklar. Im FPC Programmers Guide findet man bestenfalls nebulöse Formulierungen wie

Code: Alles auswählen

Subroutines will modify a number of registers (the volatile registers). The list of registers that are modified is highly dependent on the processor, calling convention and ABI of the target platform.

Damit läßt sich nicht viel anfangen - die Welt ist halt kompliziert, aber das wußten wir auch so schon... Auch anderweitig habe ich trotz intensiver Recherche nie etwas Genaueres gefunden - und in meinem asm-Code deshalb sicherheitshalber Anweisungen eingefügt, Parameter explizit in Register zu schieben, wo sie auf meinem Rechner zwar ohnehin schon waren, woanders aber vielleicht auch nicht... Vielleicht wäre es eine dankbare Aufgabe, diese Dinge mal detailliert zu dokumentieren.

2) Eine nicht mal besonders kostspielige Möglichkeit, diesen gordischen Knoten zu durchschlagen, könnte m.E. sein, Deine Routinen nicht als Funktionen, sondern als Prozeduren zu implementieren, indem Du beim Aufruf als dritten Parameter die Adresse des Ziel-Records (d.h. als var bzw. const) übergibst und die Ergebnisse innerhalb des Assembler-Blocks direkt ins RAM schreibst (zugegeben, das Handling wäre dann nicht mehr so schön).

Natürlich muß man ein bißchen aufpassen, in welcher Reihenfolge man die Parameter in die Arbeitsregister verschiebt, die Record-Adresse als erstes nach RSI oder RDI zu schieben, ist keine gute Idee, weil man sich damit u.U. einen der anderen Parameter überschreibt. Die Reihenfolge der (Integer-) x86-64-Parameter-Übergabe ist nach der

• System V AMD64 ABI: RDI, RSI, RDX, RCX, R8, R9
• Microsoft x64 calling convention: RCX, RDX, R8, R9

Wie gesagt, es ist unklar, wie der FP-Compiler auf verschiedenen Plattformen hier genau verfährt, aber bei nur drei Parametern lassen sich ja problemlos Wege finden, alle eventuellen Konflikte zu umschiffen.

Gruß Rüdiger

[mschnell]

gibt es kein ADC mehr.EIn Sprung ist doch viel Zeit intensiver?

Ein bedingter Sprung ist extrem zeit-intensiv ! Wenn man den nicht vermeidet, nützt die ganze ASM-Geschihte nix.

Übrigens: Kann FPC die ASM-Funktion nicht inlinen ? Der Call und Return verbrät vermutlich auch mehr Zeit als der ganze Rest.

-Michael

[mschnell]

Wie gesagt, es ist unklar, wie der FP-Compiler auf verschiedenen Plattformen hier genau verfährt, aber bei nur drei Parametern lassen sich ja problemlos Wege finden, alle eventuellen Konflikte zu umschiffen.

Das dass kann nicht "unklar" sein, sondern MUSS irgendwo dokumentiert sein, sonst könnte keiner am Compiler und der RTL entwickeln . Im Zweifelsfall im fpc Source code.

Siehe z.B: http://wiki.lazarus.freepascal.org/Asse ... _Resources

Eigentlich sollte die ABI (solange man keine calling Konvention explizit angibt) überhaupt nicht vom OS sondern nur von der Prozessor-Architektur abhängen !

-Michael