Kurze Erläuterung: Bei der (ungepackten) BCD-Arithmetik wird jede Dezimal-Ziffer durch ein Byte repräsentiert, also analog einem (ASCII-) String. Ziel ist es, (fast) beliebig lange Strings effektiv zu addieren/subtrahieren.
Code: Alles auswählen
;- Addition und Subtraktion von Strings (kein Unicode!) mit SIMD
;- "Helle" Klaus Helbing, 24.06.2010, PB4.50 (x64)
;- Jede Ziffer belegt ein Byte, es werden also 16 Ziffern auf einmal verarbeitet
;- Hier für 64-Bit, kann aber leicht für 32-Bit angepasst werden (bewusst nur Nutzung von XMM0-XMM7),
;- Register-Sicherungen dann neu
Global Loops.q
Global LStr1.q
Global LStr2.q
Global ZStr1.q
Global ZStr2.q
Global ZErg.q
Global XMM_Sich.q = AllocateMemory(32) ;für XMM6 und XMM7, für 32-Bit sind alle XMM-Register zu sichern!
Global Value01h.q = AllocateMemory(16) : PokeQ(Value01h, $0000000000000000) : PokeQ(Value01h + 8, $0100000000000000)
Global Value02h.q = AllocateMemory(16) : PokeQ(Value02h, $0202020202020202) : PokeQ(Value02h + 8, $0202020202020202)
Global Value0Ah.q = AllocateMemory(16) : PokeQ(Value0Ah, $0A0A0A0A0A0A0A0A) : PokeQ(Value0Ah + 8, $0A0A0A0A0A0A0A0A)
Global Value2Fh.q = AllocateMemory(16) : PokeQ(Value2Fh, $2F2F2F2F2F2F2F2F) : PokeQ(Value2Fh + 8, $2F2F2F2F2F2F2F2F)
Global Value30h.q = AllocateMemory(16) : PokeQ(Value30h, $3030303030303030) : PokeQ(Value30h + 8, $3030303030303030)
Global Value39h.q = AllocateMemory(16) : PokeQ(Value39h, $3939393939393939) : PokeQ(Value39h + 8, $3939393939393939)
Global NullVor$ = "0000000000000000"
Global Str1$
Global Str2$
Global Diff$
Global Summ$
Procedure Addition() ;Str1+Str2, Reihenfolge egal
!mov rax,[v_XMM_Sich] ;XMM6 und XMM7 sichern, XMM0-XMM5 sind frei verfügbar (64-Bit-OS)
!movdqu dqword[rax],xmm6 ;generell: MOVDQA wenn sicher, dass jeweiliges Memory Alignment 16 hat
!movdqu dqword[rax+16],xmm7
!mov rcx,[v_Value30h] ;die Nutzung dieser XMM-Register ist für Addition und Subtraktion gleich
!movdqu xmm6,dqword[rcx]
!mov rax,[v_Value02h]
!movdqu xmm2,dqword[rax]
!mov rdx,[v_Value0Ah]
!movdqu xmm3,dqword[rdx]
!mov rcx,[v_Value01h]
!movdqu xmm7,dqword[rcx]
!mov rdx,[v_Value39h] ;XMM5 ist spezifisch
!movdqu xmm5,dqword[rdx]
!mov rax,[v_Loops]
!mov r10,rax
!dec rax
!shl rax,4
!mov rcx,[v_ZStr2]
!add rcx,rax
!mov rdx,[v_ZStr1]
!add rdx,rax
!add rax,[v_ZErg]
!xor r8d,r8d ;Merker für Überlauf
;alle Bytes von xmm4 auf Null
!pxor xmm4,xmm4
!ADDL01:
;1.Operanden einlesen
!movdqu xmm0,dqword[rdx]
;"normieren" auf Byte-Werte von 0-9
!psubb xmm0,xmm6 ;"0000000000000000"
;2.Operanden laden und addieren, zur Sicherheit über XMM-Register wegen Alignment 16
!movdqu xmm1,dqword[rcx]
!paddb xmm0,xmm1
;Test, ob Überlauf von letzter Schleife
!test r8d,1
!jz @f
!paddb xmm0,xmm7 ;+1 an letzter Stelle
;!xor r8d,r8d
!@@:
!xor r8d,r8d ;Merker für Überlauf, zur Sicherheit doch lieber hier
!@@:
;Zwischen-Summe sichern
!movdqa xmm1,xmm0
;Test, ob einer der Byte-Werte > 9, wenn ja, wird entsprechendes Byte auf $FF gesetzt, wenn nicht, auf 0
!pcmpgtb xmm1,xmm5 ;"9999999999999999"
;Test, ob Übertrag aufgetreten
!pmovmskb r9d,xmm1
!test r9d,0FFFFh
!jz @f
!add r8d,r9d ;Merker für Überlauf
;die $FF-Bytes mit 10d belegen
!pand xmm1,xmm3
;von Bytes > 9 wird 10 subtrahiert
!psubb xmm0,xmm1
;die 8 von der 10 aussieben, 2 bleibt übrig
!pand xmm1,xmm2
;von den verbliebenen 2 den Mittelwert mit 0 bilden, also 1 (mangels Shift innerhalb von Bytes)
!pavgb xmm1,xmm4
;alle 16 Bytes um eine Position verschieben (ist Übertrag)
!psrldq xmm1,1
;den Übertrag addieren
!paddb xmm0,xmm1
!jmp @b ;Test, ob wieder ein Übertrag entstanden ist
!@@:
;Ergebnis speichern
!movdqu dqword[rax],xmm0
!sub rax,16
!sub rcx,16
!sub rdx,16
!dec r10
!jnz ADDL01
!mov rax,[v_XMM_Sich] ;XMM6 und XMM7 zurück sichern
!movdqu xmm6,dqword[rax]
!movdqu xmm7,dqword[rax+16]
;letzter Überlauf
!test r8d,1
!jz @f
Summ$ = InsertString(PeekS(ZErg), "1", 1)
Str1$ = LTrim(Str1$, "0") ;falls erforderlich Strings wieder restaurieren
Str2$ = LTrim(Str2$, "0")
FreeMemory(ZErg)
ProcedureReturn
!@@:
Summ$ = LTrim(PeekS(ZErg), "0")
Str1$ = LTrim(Str1$, "0") ;falls erforderlich Strings wieder restaurieren
Str2$ = LTrim(Str2$, "0")
FreeMemory(ZErg)
EndProcedure
Procedure Subtraktion() ;Str1-Str2, Str1 muss absolut wertmäßig größer/gleich Str2 sein
!mov rax,[v_XMM_Sich] ;XMM6 und XMM7 sichern, XMM0-XMM5 sind frei verfügbar (64-Bit-OS)
!movdqu dqword[rax],xmm6 ;generell: MOVDQA wenn sicher, dass jeweiliges Memory Alignment 16 hat
!movdqu dqword[rax+16],xmm7
!mov rcx,[v_Value30h] ;die Nutzung dieser XMM-Register ist für Addition und Subtraktion gleich
!movdqu xmm6,dqword[rcx]
!mov rax,[v_Value02h]
!movdqu xmm2,dqword[rax]
!mov rdx,[v_Value0Ah]
!movdqu xmm3,dqword[rdx]
!mov rcx,[v_Value01h]
!movdqu xmm7,dqword[rcx]
!mov rdx,[v_Value2Fh] ;XMM5 ist spezifisch
!movdqu xmm5,dqword[rdx]
!mov rax,[v_Loops]
!mov r10,rax
!dec rax
!shl rax,4
!mov rcx,[v_ZStr2]
!add rcx,rax
!mov rdx,[v_ZStr1]
!add rdx,rax
!add rax,[v_ZErg]
!xor r8d,r8d
;alle Bytes von xmm4 auf Null
!pxor xmm4,xmm4
!SUBL01:
;1.Operanden einlesen
!movdqu xmm0,dqword[rdx]
;2.Operanden laden und subtrahieren, zur Sicherheit über XMM-Register wegen Alignment 16
!movdqu xmm1,dqword[rcx]
!psubb xmm0,xmm1
!paddb xmm0,xmm6 ;"0000000000000000"
;Test, ob Überlauf von letzter Schleife
!test r8d,1
!jz @f
!psubb xmm0,xmm7 ;-1 an letzter Stelle
;!xor r8d,r8d
!@@:
!xor r8d,r8d ;Merker für Überlauf, zur Sicherheit doch lieber hier
!@@:
;Zwischen-Summe sichern
!movdqa xmm1,xmm0
;Test, ob einer der Byte-Werte > "/", wenn ja, wird entsprechendes Byte auf $FF gesetzt, wenn nicht, auf 0
!pcmpgtb xmm1,xmm5 ;"2F2F2F2F2F2F2F2F"
;Test, ob Übertrag aufgetreten
!pmovmskb r9d,xmm1
!cmp r9d,0FFFFh
!je @f ;alle Bytes >= 0
!not r9d
!add r8d,r9d ;Merker für Überlauf
;erst "not" über alle Bits und dann die $FF-Bytes (alt "0") mit 10 belegen
!pandn xmm1,xmm3
;zu Bytes < 0 wird 10 addiert
!paddb xmm0,xmm1
;die 8 von der 10 aussieben, 2 bleibt übrig
!pand xmm1,xmm2
;von den verbliebenen 2 den Mittelwert mit 0 bilden, also 1 (mangels Shift innerhalb von Bytes)
!pavgb xmm1,xmm4
;alle 16 Bytes um eine Position verschieben (ist Borgbetrag)
!psrldq xmm1,1
;den Borgbetrag subtrahieren
!psubb xmm0,xmm1
!jmp @b ;Test, ob wieder ein Borgbetrag entstanden ist
!@@:
;Ergebnis speichern
!movdqu dqword[rax],xmm0
!sub rax,16
!sub rcx,16
!sub rdx,16
!dec r10
!jnz SUBL01
!mov rax,[v_XMM_Sich] ;XMM6 und XMM7 zurück sichern
!movdqu xmm6,dqword[rax]
!movdqu xmm7,dqword[rax+16]
Diff$ = LTrim(PeekS(ZErg), "0")
If Diff$ = ""
Diff$ = "0"
EndIf
Str1$ = LTrim(Str1$, "0") ;falls erforderlich Strings wieder restaurieren
Str2$ = LTrim(Str2$, "0")
FreeMemory(ZErg)
EndProcedure
Procedure StringAufbereitung() ;evtl Test auf ungültige Zeichen, Zuordnung String1 > String2, schon vorhandene (führende) Nullen, Komma-Entfernung, Signum usw.usf.
LStr1 = Len(Str1$) ;oder eigene Len-Routine
LStr2 = Len(Str2$)
;Aufbereitung String1 ;Länge auf Vielfaches von 16 bringen mittels Einfügung führender Nullen
NullVor1$ = ""
L1 = LStr1 + 16
L11 = 16 - (L1 % 16)
If L11 = 16
L11 = 0
EndIf
For i = 1 To L11
NullVor1$ + "0"
Next
If L11
Str1$ = InsertString(Str1$, NullVor1$, 1)
EndIf
L1 + L11 - 16
L1 >> 4 ;Anzahl benötigte Loops für (nur) String1
Loops = L1 ;erstmal Wert vergeben
;Aufbereitung String2 ;Länge auf Vielfaches von 16 bringen mittels Einfügung führender Nullen
NullVor2$ = ""
L2 = LStr2 + 16
L22 = 16 - (L2 % 16)
If L22 = 16
L22 = 0
EndIf
For i = 1 To L22
NullVor2$ + "0"
Next
If L22
Str2$ = InsertString(Str2$, NullVor2$, 1)
EndIf
L2 + L22 - 16
L2 >> 4 ;Anzahl benötigte Loops für (nur) String2
;beide Strings auf gleiche Länge bringen mittels führender Nullen
If L1 > L2
i = L1 - L2
For j = 1 To i
Str2$ = InsertString(Str2$, NullVor$, 1)
Next
ElseIf L2 > L1
Loops = L2
i = L2 - L1
For j = 1 To i
Str1$ = InsertString(Str1$, NullVor$, 1)
Next
EndIf
ZStr1 = @Str1$
ZStr2 = @Str2$
ZErg = AllocateMemory(Loops << 4)
EndProcedure
;die Einzel-Beispiele hier "komplett", in einem Programm sind Vereinfachungen möglich (schneller)
;Teststrings
Str1$ = "1234566666666666665487986458484884684145737458469659244125252362634719113453253487793"
Str2$ = "4152135156464321321156451313525645156341734769847345737373711118058795087095222223"
StringAufbereitung()
Addition()
;Teststrings
Str1$ = "1234566666666666665487986458484884684145737458469659244125252362634719113453253487793"
Str2$ = "4152135156464321321156451313525645156341734769847345737373711118058795087095222223"
StringAufbereitung()
Subtraktion()
Erg$ = #CRLF$ + "String1 = " + Str1$ + #CRLF$ + "String2 = " + Str2$ + #CRLF$
Erg$ + "Summe = " + Summ$ + #CRLF$ + "Differenz = " + Diff$
OpenWindow(0, 0, 0, 800, 100, "Addition und Subtraktion von Strings (kein Unicode!) mit SIMD, 64-Bit-OS", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
StringGadget(0, 10, 10, 780, 80, Erg$, #PB_String_ReadOnly | #ES_MULTILINE)
Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow
CloseWindow(0)
Helle
