Floyd-Steinberg Dithering

[Amateurprofi]

Zitat:

Zitat von Stevie (Beitrag 1529241)

In den Kommentaren verweist Peter Cordes auf einen Trick, der ermöglicht, direkt in eax zu laden und benötigt nicht das wiederholte nullen.

Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:

Code:

procedure TestCMov_Better;
asm
        push   esi
        push   edi

        xor    edx, edx
        mov    esi, 255          // High Limit
        mov    ecx, Count

@1:     mov    edi, 0

@2:     mov    eax, dword[Data + edi * 4]
        cmp    eax, esi    // compare v (eax) with high value
        cmovae eax, edx    // if negative (unsigned check) or 255 we fill 0 (edx)
        cmovge eax, esi    // if greater (signed check) or 255 we fill 255 (esi)
        mov    Byte[CData + edi], al
        inc    edi
        cmp    edi, DATA_LEN
        jl     @2
        dec    ecx
        jne    @1

        pop  edi
        pop  esi
end;

Wenn nicht genügend Register zur Verfügung sind, können wir auch das hier (nur die Stelle mit dem Vergleich) machen - ist ein kleines bisschen langsamer aber immernoch schneller als alles andere:

Code:

        xor    edx, edx
        cmp    eax, 255    // compare v (eax) with high value
        cmovae eax, edx    // if negative or 255 we fill 0 (edx)
        mov    edx, 255
        cmovge eax, edx    // if greater or 255 we fill 255 (edx)

Danke, Stevie
Zwei Fragen hätte ich:
1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"
Ich mache

Delphi-Quellcode:

push     edi
push     esi
...
...
pop      esi
pop      edi

Du machst

Delphi-Quellcode:

push   esi
push   edi
...
...
pop  edi
pop  esi

Was ist daran korrekter?

[Kas Ob.]

@Stevie, nice !

I was going to more generic reusable one like this:

Code:

{$ALIGN 16}
procedure TestCMovShort;
const
  LOWER_LIMIT = 0;
  HIGHER_LIMIT = 255;
asm
        mov     esi, HIGHER_LIMIT          // High Limit
        mov     ecx, Count
        db      $48, $48

@1:     mov     edi, 0
        db      $48, $48, $48

@2:     mov     edx, dword[Data + edi * 4]
        mov     eax, LOWER_LIMIT
        //XOR     eax, eax     // eax is destination value filled with the lowest value
        cmp     edx, esi     // comapare v (edx) with high value
        cmovg   eax, esi     // if bigger then take the highest esi
        cmovbe  eax, edx     // if below or equal we fill value v (edx)
        mov     Byte[CData + edi], al
        inc     edi
        cmp     edi, DATA_LEN
        jl      @2
        dec     ecx
        jne     @1
end;

But it is little slower than xor , and for sure slower then using cmovae and cmovge.

[Kas Ob.]

And of course i forgot about pop and push :oops:

[Kas Ob.]

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

Data comes from my earlier test

Code:

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;
....
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

Data is filled with arbitrary values bigger than 255 and lower than 0.

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"

no difference at all, both are correct, storing registers on stack by push and pop should be planned as First-In-Last-Out FILO, (same as Last-In-First-Out LIFO).

[Stevie]

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

1) Was ist "Data"?

Siehe Post #29

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"...

Das war auch auf Post #29 bezogen, wo die Benchmark routinen die Register nutzen, aber nicht gesichert haben.

[Amateurprofi]

Zitat:

Zitat von Stevie (Beitrag 1529288)

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

1) Was ist "Data"?

Siehe Post #29

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"...

Das war auch auf Post #29 bezogen, wo die Benchmark routinen die Register nutzen, aber nicht gesichert haben.

Oh, das habe ich missverstanden. Tschuldi.

[Amateurprofi]

Zitat:

Zitat von Kas Ob. (Beitrag 1529280)

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

Data comes from my earlier test

Code:

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;
....
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

Data is filled with arbitrary values bigger than 255 and lower than 0.

Zitat:

Zitat von Amateurprofi (Beitrag 1529266)

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"

no difference at all, both are correct, storing registers on stack by push and pop should be planned as First-In-Last-Out FILO, (same as Last-In-First-Out LIFO).

Thanks for clarification.

[Amateurprofi]

Zitat:

Zitat von Stevie (Beitrag 1529208)

Der Benchmark ist Blödsinn, denn in TestMov wird der erste jle immer genommen, also ist der Branchpredictor ziemlich happy.
Branchy Code, bei dem ein conditional branch immer genommen wird oder nie genommen wird, ist für einen solchen Test Unfug.

Generell gilt: Conditional branches sind ok, wenn sie sehr predictable sind - d.h. es wird meist der eine Branch und selten der andere genommen. Sie funktionieren auch, wenn es immer abwechselnd ist, die Branchpredictors auf modernen CPUs sind ziemlich schlau. Schlimm wird es allerdings, wenn sie nicht vorhersehbar sind - selbst wenn es im Schnitt 50/50 ist aber ob der Sprung genommen wird oder nicht, ist z.B nicht immer abwechselnd, dann wirds schlimm und man ist mit einem cmov besser aufgehoben.

Übrigens schreibt man

Delphi-Quellcode:

dec ecx

und nicht

Delphi-Quellcode:

sub ecx, 1

- dec ist 1 byte instruction, sub benötigt 3 byte

FWIW: https://codereview.stackexchange.com...he-range-0-255

Zu "Übrigens schreibt man dec ecx und nicht sub ecx, 1 - dec ist 1 byte instruction, sub benötigt 3 byte"
Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Zitat:

The inc and dec instructions should always be avoided. Using add
and sub instructions instead avoids data dependence and improves
performance.

Merke: Kürzere Instruction bedeutet nicht automatisch "schneller".
Mir ist bewusst, dass bei heutigen Prozessoren (auch bei meinem schon etwas älteren I7 2600K) ein dec/inc und sub 1/add 1 gleich schnell abgearbeitet werden, bei früheren Prozessoren war sub/add (mit #-Werten) deutlich schneller als dec/inc.
Ich benutze trotzdem i.d.R. sub/add weil hier, anders als bei dec/inc, auch das CF Flag gesetzt wird.


Zu "Der Benchmark ist Blödsinn, denn in TestMov wird der erste jle immer genommen"
Nein. Der jle @Z wird nur dann genommen, wenn eax <= 0 ist.
Bei @1 wird edx = -255 gesetzt.
Bei @2 wird edx in eax kopiert und dann eax mit 0 verglichen und gejumpt, wenn eax <= 0 ist.
Bei @N wird edx um 1 erhöht und zu @2 gejumpt, solange edx <= 255 ist.
Bei @2 kann edx und dann eax also Werte im Bereich -255 bis 255 haben.
Merke: Worte wie "Blödsinn" oder"Quatsch" sollte man vermeiden,

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      mov edi,0
      mov esi,255
      mov ecx,Count
@1:   mov edx,-255
@2:   mov eax,edx
      cmp eax,0
      jle @Z
      cmp eax,255
      jbe @S
      mov byte[esp],255
      jmp @N
@Z:   xor eax,eax
@S:   mov [esp],al
@N:   add edx,1
      cmp edx,255
      jbe @2
      sub ecx,1
      jne @1
@End: pop ecx
end;

Das mov edi,0 und mov esi,255 ist übrigens überflüssig (resultierte aus copy/paste).

[Stevie]

Zitat:

Zitat von Amateurprofi (Beitrag 1529321)

Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Stand 2006 - sorry, aber das war ja schon zum Release des i7-2600 in 2011 veraltet.
Dass speziell das mit dem dec/inc vs add/sub dort noch zutreffend war, mag ich nicht in Abrede stellen.

Mehr zu der Thematik guckst du hier: https://stackoverflow.com/questions/...does-it-matter

Aber mein Fehler, ich geh in aller Regel davon aus, dass wenn man asm redet, sich zumindest innerhalb derselben Dekade bewegt und nicht im Jahr des Releases von Windows Vista :mrgreen:

Und die Aussage zu dem jle war selbstverständlich auch auf die Benchmark von Kas bezogen, die dort nämlich immer den jump genommen hat, damit beweist man nämlich gar nix, außer dass der Branchpredictor gut funktioniert (vermutlich auch 2006 schon) ;)

[Amateurprofi]

Zitat:

Zitat von Stevie (Beitrag 1529327)

Zitat:

Zitat von Amateurprofi (Beitrag 1529321)

Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Stand 2006 - sorry, aber das war ja schon zum Release des i7-2600 in 2011 veraltet.
Dass speziell das mit dem dec/inc vs add/sub dort noch zutreffend war, mag ich nicht in Abrede stellen.

Mehr zu der Thematik guckst du hier: https://stackoverflow.com/questions/...does-it-matter

Aber mein Fehler, ich geh in aller Regel davon aus, dass wenn man asm redet, sich zumindest innerhalb derselben Dekade bewegt und nicht im Jahr des Releases von Windows Vista :mrgreen:

Und die Aussage zu dem jle war selbstverständlich auch auf die Benchmark von Kas bezogen, die dort nämlich immer den jump genommen hat, damit beweist man nämlich gar nix, außer dass der Branchpredictor gut funktioniert (vermutlich auch 2006 schon) ;)

OK.
Wie wäre es, wenn Du bei einer Antwort (wenn Du nicht den Beitrag zitierst), angibst, auf welchen Beitrag Du Dich beziehst?
Zum Beispiel ein "Zu #25:" würde helfen, Missverständnisse zu vermeiden.
Ist nur eine Anregung.