Floyd-Steinberg Dithering

[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}