Floyd-Steinberg Dithering

[Stevie]

Zitat von Amateurprofi:

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.

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      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;

Ich erkläre nochmal warum diese Funktion für die Messung, ob conditional jumps oder conditional mov besser sind, so nützlich wie nen Abgastest bei VW ist:

Wie du selbst erklärt hast, wird hier von -255 bis 255 gezählt - die ersten 256 mal wird der jle genommen, die nächsten 255 mal nicht. Der folgende jbe wird immer genommen, denn da kommt man überhaupt nie mit nem Wert von über 255 an. Glücklicher kann man die Sprungvorhersage fast gar nicht machen, die liegt vermutlich zu 99% richtig (genaue Zahl kommt auf die CPU an und selbst Intel hat keine genauen Dokumentationen, wie die exakt funktionieren - Matt Godbolt hat vor Jahren mal ein bisschen was gemessen und einige Blog Artikel dazu geschrieben).

Das heißt, um Code wie diesen richtig zu vergleichen, muss man Daten erzeugen, die eine realistische Verteilung haben - ob das nun Daten sind, wie Kas in #34 generiert hat oder ob sie in Realität anders aussehen, kann ich nicht beurteilen, aber ich bin mir sicher, dass sie nicht in der Sequenz -255..255 vorliegen.

[Amateurprofi]

Zitat von Stevie:

Zitat von Amateurprofi:

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.

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      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;

Ich erkläre nochmal warum diese Funktion für die Messung, ob conditional jumps oder conditional mov besser sind, so nützlich wie nen Abgastest bei VW ist:

Wie du selbst erklärt hast, wird hier von -255 bis 255 gezählt - die ersten 256 mal wird der jle genommen, die nächsten 255 mal nicht. Der folgende jbe wird immer genommen, denn da kommt man überhaupt nie mit nem Wert von über 255 an. Glücklicher kann man die Sprungvorhersage fast gar nicht machen, die liegt vermutlich zu 99% richtig (genaue Zahl kommt auf die CPU an und selbst Intel hat keine genauen Dokumentationen, wie die exakt funktionieren - Matt Godbolt hat vor Jahren mal ein bisschen was gemessen und einige Blog Artikel dazu geschrieben).

Das heißt, um Code wie diesen richtig zu vergleichen, muss man Daten erzeugen, die eine realistische Verteilung haben - ob das nun Daten sind, wie Kas in #34 generiert hat oder ob sie in Realität anders aussehen, kann ich nicht beurteilen, aber ich bin mir sicher, dass sie nicht in der Sequenz -255..255 vorliegen.

Du hast da uneingeschränkt Recht.
Viel schlimmer ist jedoch das:

Delphi-Quellcode:

@N:   add edx,1
      cmp edx,255
      jbe @2

Da wird das jbe nie ausgeführt.
Aber den Fehler hatte ich in alle Testprozeduren gleichermaßen eingebaut.

Was den Wert in EDX betrifft, hab ich noch mal geprüft, welche Werte in Frage kommen.
Dieser wird so ermittelt (am Beispiel des Blau-Anteils) zweier Pixel).

P1 = Pixel[0,0]
P2 = Pixel[1,0]
OldBlue = P1.Blue
NewBlue = 0 oder 255
Delta = OldBlue - NewBlue; // kann sein -255..255
Offset = (Delta * Faktor) div 16 // kann bei Faktor 7 sein -111..111
NewVal = P2.Blue + Offset // kann sein -111..366
P2.Blue = EnsureRange(NewVal, 0, 255)

Ich hab noch mal getestet, dieses Mal habe ich aber nicht Laufzeiten mit GetTickCount gemessen, sondern die benötigten CPU-Ticks mit TimeStampCounter.
Das ist (meine Meinung) realistischer, weil die CPU mit unterschiedlichen Geschwindigkeiten laufen kann.
Bei GetTickCount werden die Laufzeiten dadurch mal länger, mal kürzer, beim TimeStampCounter (wiederum meine Meinung) nicht.
Hoffentlich nicht wieder dumme Fehler eingebaut.

Aber auch hier ergeben sich unterschiedliche Resultate.

13,917 15,052 3,967,047 CPU-Ticks TestCMovShort
14,246 14,977 83,528 CPU-Ticks TestMov

13,556 14,994 126,734 CPU-Ticks TestCMovShort
13,884 15,276 65,974 CPU-Ticks TestMov

Die jeweils 3 Werte sind Minimum, Average, Maximum.

Was sich bei vielen Testläufen herauskristallisiert hat, ist, dass TestCMovShort etwas schneller ist.
Bin jetzt überzeugt.

Für Interessierte:

Delphi-Quellcode:

{$IFDEF CPUX86}
procedure TestCMovShort(Count:Integer);
asm
               push   esi           // Save ESI
               push   0             // Memory
               mov    esi,255       // Max-Value
               mov    ecx,eax       // Counter from Count downto 1
@CounterLoop:  mov    edx,-111      // Value from -111 to 366
@ValueLoop:    mov    eax,0         // Min-Value
               cmp    edx,esi       // Value vs. Max-Value
               cmovg  eax,esi       // Load Max-Value if Value > Max-Value
               cmovbe eax,edx       // Load Value if Value <= Max-Value
               mov    [esp],al      // Store New Value
               inc    edx           // Value + 1
               cmp    edx,367       // Value vs. 367
               jne    @ValueLoop    // Loop until Value = 367
               dec    ecx           // Counter - 1
               jne    @CounterLoop  // Loop until Counter = 0
               pop    ecx           // Remove Memory from Stack
               pop    esi           // Restore ESI
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE TestMov(Count:Integer);
asm
               push     0             // Memory
               mov      ecx,eax       // Counter from Count downto 1
@CounterLoop:  mov      edx,-111      // Value from -111 to 366
@ValueLoop:    mov      eax,edx       // New-Value = Value
               cmp      eax,0         // New-Value vs. 0
               jle      @Zero         // Jump if New-Value <= 0
               cmp      eax,255       // New-Value vs. 255
               jbe      @Store        // Jump if New-Value <= 255
               mov      byte[esp],255 // Store 255 as New Value
               jmp      @NextValue    // Next Value
@Zero:         xor      eax,eax       // New-Value=0
@Store:        mov      [esp],al      // Store New Value
@NextValue:    inc      edx          // Value + 1
               cmp      edx,367       // Value vs. 367
               jne      @ValueLoop    // Loop until Value = 367
               sub      ecx,1         // Counter - 1
               jne      @CounterLoop  // Loop until Counter = 0
               pop      ecx           // Remove Memory from Stack
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE TestAsm(Count:Integer; var Ticks1,Ticks2:Int64);
asm  // EAX=Count, EDX=@Ticks1, ECX=@Ticks2
    push    eax         // Count
    push    edx         // @Ticks1
    push    ecx         // @Ticks2
    // CPU auf Trab bingen
    mov     ecx,100000
@1: dec     ecx
    jne     @1
    // TestCMovShort
    mov     ecx,[esp+4] // @Ticks1
    rdtsc
    mov     [ecx],eax   // Ticks1.Lo
    mov     [ecx+4],edx // Ticks1.Hi
    mov     eax,[esp+8] // Count
    call    TestCMovShort
    rdtsc
    mov     ecx,[esp+4] // @Ticks1
    sub     eax,[ecx]   // = Ticks1.Lo
    sbb     edx,[ecx+4] // = Ticks1.Hi
    mov     [ecx],eax   // Ticks1.Lo
    mov     [ecx+4],edx // Ticks1.Hi
    // TestMov
    mov     ecx,[esp]   // @Ticks2
    rdtsc
    mov     [ecx],eax   // Ticks2.Lo
    mov     [ecx+4],edx // Ticks2.Hi
    mov     eax,[esp+8] // Count
    call    TestMov
    rdtsc
    mov     ecx,[esp]   // @Ticks2
    sub     eax,[ecx]   // = Ticks2.Lo
    sbb     edx,[ecx+4] // = Ticks2.Hi
    mov     [ecx],eax   // Ticks2.Lo
    mov     [ecx+4],edx // Ticks2.Hi
    add     esp,12
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE Test;
const Count1=10; Count2=10000;
var I:Integer;
    SaMask,PaMask,TaMask:NativeUInt;
    T1,T2,T1Min,T2Min,T1Max,T2Max,T1Sum,T2Sum,T1Avg,T2Avg:Int64;
begin
   // Thread auf eine CPU fixieren
   GetProcessAffinityMask(GetCurrentProcess,PaMask,SaMask);
   TaMask:=1;
   while TaMask and PaMask=0 do TaMask:=TaMask shl 1;
   SetThreadAffinityMask(GetCurrentThread,TaMask);
   // Laufzeiten von TestCMovShort (T1) und TestMov (T2) ermitteln
   TestAsm(Count1,T1Min,T2Min);
   T1Max:=T1Min;
   T2Max:=T2Min;
   T1Sum:=T1Min;
   T2Sum:=T2Min;
   for I:=1 to Count2 do begin
      TestAsm(Count1,T1,T2);
      T1Min:=Min(T1Min,T1);
      T1Max:=Max(T1Max,T1);
      T2Min:=Min(T2Min,T2);
      T2Max:=Max(T2Max,T2);
      Inc(T1Sum,T1);
      Inc(T2Sum,T2);
   end;
   T1Avg:=T1Sum div (Count2+1);
   T2Avg:=T2Sum div (Count2+1);
   // Thread für alle CPUs freigeben und Priorität auf alten Wert stellen
   SetThreadAffinityMask(GetCurrentThread,PaMask);
   ShowMessage(Format('%.0N  %.0N  %.0N  CPU-Ticks TestCMovShort'#13+
                      '%.0N  %.0N  %.0N  CPU-Ticks TestMov',
                      [T1Min+0.0, T1Avg+0.0, T1Max+0.0,
                       T2Min+0.0, T2Avg+0.0, T2Max+0.0]));
end;
{$ENDIF}

[Stevie]

Ich bin mir nicht sicher, ob du meine Ausführung mit der Sprungvorhersage verstanden hast, wenn du eine aufsteigende Sequenz zwischen x und y testest, ist das witzlos, denn die Daten bei einer reellen Berechnung liegen nicht in dieser Form vor. In den Daten im Test, wo du von -111 bis 366 gehst hast du nun 112 mal jle jump taken, 366 mal non taken, und dann 255 mal jbe jump taken, 111 mal non taken, immer hintereinander, da ist die Sprungvorhersage immernoch fast immer richtig.
Realistische Werte erhälst du nur, wenn du die Werte nicht in auf- oder absteigender Reihenfolge an die Funktion fütterst sondern in einer realistischen Verteilung durchgemischt.

[Amateurprofi]

Zitat von Stevie:

Ich bin mir nicht sicher, ob du meine Ausführung mit der Sprungvorhersage verstanden hast, wenn du eine aufsteigende Sequenz zwischen x und y testest, ist das witzlos, denn die Daten bei einer reellen Berechnung liegen nicht in dieser Form vor. In den Daten im Test, wo du von -111 bis 366 gehst hast du nun 112 mal jle jump taken, 366 mal non taken, und dann 255 mal jbe jump taken, 111 mal non taken, immer hintereinander, da ist die Sprungvorhersage immernoch fast immer richtig.
Realistische Werte erhälst du nur, wenn du die Werte nicht in auf- oder absteigender Reihenfolge an die Funktion fütterst sondern in einer realistischen Verteilung durchgemischt.

Danke Stevie,
tschuldi, dass ich so spät antworte. Ich hatte diesen Text schon vor 2 Wochen geschrieben, mich dann aber um andere Themen gekümmert.

Ich bin mir sicher, dass ich Deine Ausführungen verstanden hatte und ich bin mir auch sicher, dass ich das auch schon vorher wusste.
Ich habe die CMOV-Instruktion immer gemieden, weil sie nicht von allen Prozessoren unterstützt wird, was allerdings eine recht alte Information ist.
Ich habe die Testprozeduren noch einmal überarbeitet.
Die zu vergleichenden Werte kommen jetzt aus einem Daten-Array, das mit Zufallswerten, und bei einem zweiten Testlauf mit aufsteigenden Werten gefüllt ist.
Die Laufzeiten sind immer recht unterschiedlich, typische Werte waren:

Code:

Zufallswerte 
1,360  2,184  3,926  CPU-Ticks TestCMovShort
2,602  4,243  20,340  CPU-Ticks TestMov 
1,242  2,059  16,414  CPU-Ticks Differenz 
Aufsteigende Werte 
1,360  1,501  27,828  CPU-Ticks TestCMovShort 
1,614  1,755  27,457  CPU-Ticks TestMov 
254  254  -371  CPU-Ticks Differenz

Der fragliche Code wird für jedes Pixel der Bitmap 4 Mal ausgeführt.
Ausgehend von dem Gewinn von 1242 CPU-Ticks für 478 Vergleiche, einer Bitmap mit 2.4 MPixel, und einer CPU-Frequenz von 3.4GHz ergibt sich ein Gewinn von
1242/478*2.4M/3.4G*4*1000 = 7.3 ms.
Bei einer Laufzeit von 63 ms für die Umwandlung der Bitmap ist der Gewinn von 7 ms nicht unbedeutend.

Delphi-Quellcode:

var
   Data:Array[0..366+111] of Integer;

Delphi-Quellcode:

procedure TestCMovShort;
const HI=High(Data);
asm
               push     esi               // Save ESI
               push     0                 // Memory
               mov      esi,255           // Max-Value
               mov      ecx,HI            // Index from High(Data) downto 0
@Loop:         mov      edx,[ecx*4+Data]  // Value
               mov      eax,0             // Min-Value
               cmp      edx,esi           // Value vs. Max-Value
               cmovg    eax,esi           // Load Max-Value if Value > Max-Value
               cmovbe   eax,edx           // Load Value if Value <= Max-Value
               mov      [esp],al          // Store New Value
               dec      ecx               // Index - 1
               jns      @Loop             // Loop until Index = 0
               pop      ecx               // Remove Memory from Stack
               pop      esi               // Restore ESI
end;

Delphi-Quellcode:

PROCEDURE TestMov;
const HI=High(Data);
asm
               push     0                 // Memory
               mov      ecx,HI            // Index from High(Data) downto 0
@Loop:         mov      eax,[ecx*4+Data]  // Value
               cmp      eax,0             // Value vs. 0
               jle      @Zero             // Jump if New-Value <= 0
               cmp      eax,255           // Value vs. 255
               jbe      @Store            // Jump if Value <= 255
               mov      byte[esp],255     // Store 255 as New Value
               jmp      @Next             // Next Index
@Zero:         mov      byte[esp],0       // Store 0 as New Value
               jmp      @Next             // Next Index
@Store:        mov      [esp],al          // Store New Value
@Next:         dec      ecx               // Index - 1
               jns      @Loop             // Loop until Index < 0
               pop      ecx               // Remove Memory from Stack
end;