PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

Optimiert(est)er peek für einen unsigned long 32bit

https://www.purebasic.fr/german/viewtopic.php?t=27188

Seite 3 von 5

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 00:10
von STARGÅTE
So wie ich das verstehe, werden bei Base85 aus 4Bytes -> 5Bytes gemacht.
Dabei wird die 256er-Basis in eine 85er-Basis zerlegt.

Der ASM-Befehl DIV ist dafür natürlich optimal geeignet, weil er sowohl dividiert, als auch den Rest ausgibt.
Das heißt, eine LONG (4Bytes) in EAX werfen, fünf mal DIV 85 anwenden und die Reste jeweils auf die Zeichen im String addieren, der vorher aus "!" besteht.

Hier ist mal mein Code (x86 only):

Code: Alles auswählen

Procedure.s Base85Encoder(*Input, Length.i)
	Protected Result.s = RSet("", Length*5/4, "!")
	*Input + Length
	!MOV ebx, 85                 ; Divisor
	!MOV ecx, [p.p_Input]        ; Leseadresse
	!MOV edi, [p.v_Result]       ; Schreibadresse
	!SUB ecx, [p.v_Length]
	!base85_loop:
		!MOV eax, [ecx]            ; Tiefer Dividend-Teil
		!BSWAP eax
		!MOV edx, 0                ; Hoher Dividend-Teil = 0
		!DIV ebx                   ; Erste Division
		!ADD [edi+4], dl           ; Rest (nur das tiefste Byte) kommt in den String, addiert auf das "!"
		!MOV edx, 0
		!DIV ebx                   ; Zweite Division
		!ADD [edi+3], dl
		!MOV edx, 0
		!DIV ebx                   ; Dritte Division
		!ADD [edi+2], dl
		!MOV edx, 0
		!DIV ebx                   ; Vierte Division
		!ADD [edi+1], dl
		!MOV edx, 0
		!DIV ebx                   ; Fünfte Division
		!ADD [edi+0], dl
		!ADD ecx, 4                ; Leseadresse + 4
		!ADD edi, 5                ; Schreibadresse + 5
		!CMP ecx, [p.p_Input]      ; Fertig?
	!JNZ base85_loop
	ProcedureReturn Result
EndProcedure


Define *Buffer1 = AllocateMemory(9)
PokeS(*Buffer1, "Man sure")
Debug Base85Encoder(*Buffer1, 8)


Define *Buffer2 = AllocateMemory(1024*1024*10)
RandomData(*Buffer2, MemorySize(*Buffer2))
Define String.s = Base85Encoder(*Buffer2, MemorySize(*Buffer2))
Debug String
Debug "Länge: "+Str(Len(String))
Läuft bei 10MB trotz Debugger recht flott durch und gibt mir auch laut WIKI das richtige Ergebnis für "Man sure" zurück: "9jqo^F*2M7"
Hinweis: Der ASM-Code ist nicht ganz sauber, da ich die Register ebx und esi nicht sichere. Das müsste ggf. noch nachgetragen werden. Außerdem sind nur 4er-Längen erlaubt!

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 04:08
von melow
Hi Leute... und Danke für all die vielen Links und Tipps.
Wie Thorium richtig erwähnte muss ich aufjedenfall die Grundlagen von ASM nun einstudieren, dann erübrigen sich viele weitere Fragen von mir... will ja niemanden Nerven damit :oops:

Smypathisch ist mir ASM aber alle male (nun) :-)

@STARGÅTE
Dein Code läuft einwandfrei bei mir (für eine 32bit CPU kompiliert)
Und, vor allem, 10x so schnell wie meine bisherigen Optimierungen. Da bin ich seh angetan davon.

Meine "!DIV" Frage, denke ich, werd ich anhand Deines Codes auch lösen können.
Danke auch für Deine Kommentare im ASM Code... sind sehr nützlich für mich.
da ich die Register ebx und esi nicht sichere
Das versteh ich (noch) nicht. Meinst Du damit die 64bit Kompatibilität?
Außerdem sind nur 4er-Längen erlaubt!
Jo... aber halb so wild. Padding werd ich mittels PB Code erweitern. Das ist kein Problem.

Aber (bei mir) nun 10MB in ~0,25 sek. statt, wie Anfangs 10MB in ~100sek encodieren... ist schon ein gewaltiger Unterschied.

Danke Dir und Euch Allen für Eure Hilfe

lg Melow :-)

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 04:36
von Regenduft
Ich bin zwar nicht angesprochen worden aber antworte mal ganz frech stellvertretend. (Sind ja nimmer so viele wach :mrgreen:)
melow hat geschrieben:
da ich die Register ebx und esi nicht sichere
Das versteh ich (noch) nicht. Meinst Du damit die 64bit Kompatibilität?
Er meint damit, dass er einfach ebx und esi verwendet ohne sie vorher per "push" auf den Stack abzulegen und nach Verwendung mit "pop" wiederherzustellen (falls Du schon weit genug bist um das zu verstehen :wink:).
PureBasic-Hilfe (Inline x86 ASM) hat geschrieben:Die verwendbaren Register sind: eax, edx und ecx. Alle anderen müssen immer reserviert bleiben.
EDIT: Habe gerade Deine "Location" bemerkt. Hatte mich schon gewundert, dass noch andere Freaks Dienstags morgens nach 4:00 Uhr am Rechner sitzen, aber Du hast ja gerade "Frühstückspausenzeit"! <)

EDIT 2: Mellow in Thailand. Das klingt mal echt "doppelrelaxt", wenn ich mir das Späßle erlauben darf! :lol:

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 04:56
von melow
Hallo Regenduft (wir haben bei uns grad Regenzeit... Duftet alles nach Regen deshalb :-) )
Er meint damit, dass er einfach ebx und esi verwendet ohne sie vorher per "push" auf den Stack abzulegen und nach Verwendung mit "pop" wiederherzustellen (falls Du schon weit genug bist um das zu verstehen :wink:).
Soweit bin ich zwar noch nicht gekommen... aber, versteh ich (nun). Könnte demnach also sein daß die register ebx und esi von anderswo noch Werte beinhalten die, nachdem wir sie ja überschrieben haben, wieder hergestellt werden sollten. oki. Alles kar.

Mellow in Thailand. Das klingt mal echt "doppelrelaxt", wenn ich mir das Späßle erlauben darf! :lol:
:lol:
Aber der Schein trügt. Nach über 10 Jahren Thailand empfind ich es als ganz normal... wie damals in DE.

lg Melow :-)

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 05:45
von Regenduft
melow hat geschrieben:Könnte demnach also sein daß die register ebx und esi von anderswo noch Werte beinhalten die, nachdem wir sie ja überschrieben haben, wieder hergestellt werden sollten. oki. Alles kar.
Um ein bisschen genauer zu sein: ebx ist das "base" Register und wird traditionell bei indirekter Adressierung (Basis+Offset) verwendet. esi ist das "source index" Register und wird zusammen mit edi - dem "destination index" - für Strings verwendet. Da gibt's ein paar coole ASM-Anweisungen, die bei Verwendung automatisch esi und/oder edi inkrementieren! Ich empfehle nochmals "The Art of Assemly Language", das war für mich "der totale Augenöffner" wieso wann welche Register (oft inzwischen nurnoch traditionell) verwendet werden! <)

(EDIT: Offtopic-Overload entfernt)

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 06:40
von melow
Um ein bisschen genauer zu sein: ebx ist das "base" Register und wird traditionell bei indirekter Adressierung (Basis+Offset) verwendet. esi ist das "source index" Register und wird zusammen mit edi - dem "destination index" - für Strings verwendet. Da gibt's ein paar coole ASM-Anweisungen, die bei Verwendung automatisch esi und/oder edi inkrementieren!
Sehr Interessant.
Ich empfehle nochmals "The Art of Assemly Language"
Gemerkt. Zieh ich mir rein... Also das Buch :-D

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 10:33
von NicTheQuick
Das ist fies! Da geht man mal früher ins Bett und schon bastelt Stargate den ganzen Code in hübschen ASM um, obwohl man selbst noch dabei war. :wink:
Aber ich glaube ich bräuchte auch mal ein bisschen ASM-Nachhilfe. Ich habe versucht mir ein bisschen was aus dem PB-ASM-Output anzuschaue, aber da hat mich so einiges verwirrt. Da werden Werte wild zwischen Registern herum kopiert, was gar nicht notwenig gewesen wäre (dword in r15, dann r15 in rax) und dann wird das gepusht und gepopt, was für mich auch keinen Sinn ergab (PUSH rax, POP rax, MOV dword [rsp+112], eax). Aber ohne das Push-Pop geht's trotzdem nicht. :freak:
Ich zeige euch meinen bisherigen Code lieber nicht. :D

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 11:13
von Regenduft
@ NicTheQuick: Erst gacken und dann nicht legen... Tse! :wink:
Schau Dir mal den x86- im Vergleich zum x64-ASM-Output an. Ich finde die extremen Unterschiede hammerhart! x86 kann ich noch teilweise nachzuvollziehen (obwohl ich in ASM echt nix drauf habe), aber x64 finde ich einfach nur stier! Schon ein einfacher Prozeduraufruf in x64 ist einfach nur :o !

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 11:23
von STARGÅTE
NicTheQuick hat geschrieben:Ich habe versucht mir ein bisschen was aus dem PB-ASM-Output anzuschaue, aber da hat mich so einiges verwirrt. Da werden Werte wild zwischen Registern herum kopiert, was gar nicht notwenig gewesen wäre (dword in r15, dann r15 in rax) und dann wird das gepusht und gepopt, was für mich auch keinen Sinn ergab
Da stimme ich dir zu. Das liegt aber nur daran, dass der ASM-Output nicht "selbst" geschrieben wird, sondern vom Compiler erzeugt wird. Das ist zwar kein Grund, dass der Compiler "sinnlose" Befehle erzeugt, aber er ist halt dahingehend nicht optimiert.

Schreibt man selbst etwas in ASM, so versucht man natürlich, Laufvariablen (in Schleifen) möglichst in den Registern zu behalten, darüber denkt der Compiler nicht mal im Traum nach^^.
Trotzdem bin ich mit der geschwindigkeit von PB sehr zufrieden, und wenn ich mal wirklich das Optimum erreichen möchte, muss ich eben selbst schreiben.

Noch mal zur Sicherung der Register:
Man kann natürlich ebx, esi und edi (wenn man sie nutzen möchte) mit PUSH sichern und danach mit POP wiederherstellen.
Problem an dieser Sache ist dann nur, dass durch das PUSH der Stack-Pointer verändert wird.
Da Sachen wie: "p.p_Input" aber PB-Konstrukte sind, und auf den Prozedur-Stack mit zB "esp+10" zugreifen, würde das zu Fehler führen. Man muss den Stackpointer also ebenfalls anpassen. Wenn man also 3 mal 4Byte pushed, muss esp + 12 gerechnet werden (weil der Stackpointer nach unten wächst). Dann darf man aber "innen" nicht PUSH benutzen, weil ja sonst die Sicherungen überschrieben werden.
Hier die korrigierte Version:

Code: Alles auswählen

Procedure.s Base85Encoder(*Input, Length.i)
   Protected Result.s = RSet("", Length*5/4, "!")
   *Input + Length
   !PUSH ebx                    ; ebx und edi
   !PUSH edi                    ; sichern und
   !ADD esp, 8                  ; Stackpointer anpassen
   !MOV ebx, 85                 ; Divisor
   !MOV ecx, [p.p_Input]        ; Leseadresse
   !MOV edi, [p.v_Result]       ; Schreibadresse
   !SUB ecx, [p.v_Length]
   !base85_loop:
      !MOV eax, [ecx]              ; Tiefer Dividend-Teil
      !BSWAP eax
      !MOV edx, 0                  ; Hoher Dividend-Teil = 0
      !DIV ebx                     ; Erste Division
      !ADD [edi+4], dl             ; Rest (nur das tiefste Byte) kommt in den String, addiert auf das "!"
      !MOV edx, 0
      !DIV ebx                     ; Zweite Division
      !ADD [edi+3], dl
      !MOV edx, 0
      !DIV ebx                     ; Dritte Division
      !ADD [edi+2], dl
      !MOV edx, 0
      !DIV ebx                     ; Vierte Division
      !ADD [edi+1], dl
      !MOV edx, 0
      !DIV ebx                     ; Fünfte Division
      !ADD [edi+0], dl
      !ADD ecx, 4                  ; Leseadresse + 4
      !ADD edi, 5                  ; Schreibadresse + 5
      !CMP ecx, [p.p_Input]        ; Fertig?
   !JNZ base85_loop
   !SUB esp, 8                  ; Stackpointer anpassen
   !POP edi                     ; und edi und ebx
   !POP ebx                     ; wiederherstellen
   ProcedureReturn Result
EndProcedure
Code ist nachwievor nur für x86!

Natürlich bin ich auch kein ASM-Profi, und hab mir auch alles nur "zusammengereimt". Daher bin auch ich für Verbesserungsvorschläge offen ... Helle? ^^

@Regenduft:
Um deinen eigenen ASM Code von x86 auf x64 kompatibel zu machen, recht es aber die Register die Adressen beinhalten von eax, ebx, edx nach rax, rbx, rdx umzuschreiben, die sind dann 8Byte lang statt 4Byte (also Achtung bei Offsets und PUSH und POP).

Re: Optimiert(est)er peek für einen unsigned long 32bit

Verfasst: 03.09.2013 11:45
von Regenduft
Wenn man EnableASM und Inline-ASM anstatt Direkt-ASM verwendet (hoffe man versteht was ich meine...) dann passt PureBasic inzwischen sogar teilweise - wenn ich mich recht entsinne - automatisch den Stackpointer an. Teilweise "pusht und poppt" PB ja auch generell automatisch bei Inline-ASM wild herum. Wann und wie ist mir aber absolut schleierhaft!
Alle Zeiten sind UTC+02:00
Seite 3 von 5

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de