Floyd-Steinberg Dithering

[Mavarik]

Im Thread!

https://cs.wellesley.edu/~pmetaxas/pdcs99.pdf

[Amateurprofi]

Ich habe mir das Thema "Floyd Steinberg" noch einmal zu Gemüte geführt und einige Assembler-Prozeduren zusammengefrickelt, die das Dithering deutlich beschleunigen.
Laufzeiten für Bitmaps mit 2.4MPixel bzw. 13.3MPixel im 32Bit- und 64Bit-Modus

Code:

Pas:   149   209   /   857   1165 ms
Pas42:   529   531   /   3048   3027 ms
Pas48:   498   534   /   2866   3021 ms
Asm1:   53,5   54.8   /   342   343 ms
Asm2:   54.1   54.8   /   309   321 ms 
Asm3:   29.3   22.4   /   181   143 ms

Um die Testprozeduren zu nutzen, müssen in der Prozedur "TestFloydSteinberg" im
Array "Filenames:Array[TTestMode] of String"
die Dateinamen entsprechend angepasst werden.

Region "PurePascal"
Den Prozeduren FloydSteinberg, FloydSteinberg42 und FloydSteinberg48,werden als Parameter die Bitmap übergeben.
FloydSteinberg42 und FloydSteinberg48 dithern entsprechend den, in der von Mavarik in #23 geposteten PDF https://cs.wellesley.edu/~pmetaxas/pdcs99.pdf auf Seite 574 in Fig. 9 gezeigten Schemata.

Region "PureAssembler"
Die Assembler-Prozeduren FloydSteinbergAsm1, FloydSteinbergAsm2 und FloydSteinbergAsm3 werden direkt aufgerufen, als Parameter wird die Bitmap übergeben.

Region "Pascal/Assembler"
Die Prozeduren FloydSteinbergAsm1, FloydSteinbergAsm2 und FloydSteinbergAsm3 werden von der Prozedur FloydSteinbergPasAsm aufgerufen wobei folgende Parameter übergeben werden:
PP: Pointer auf das erste Pixel der Bitmap
LO: Offset zur jeweils nächsten Zeile in Bytes
W: Breite der Bitmap - 1
H: Höhe der Bitmap -1

In den Anhängen sind das Projekt "FloydSteinberg", die verwendeten Testbilder als JPEGs und die Protokolle der Umwandlungen.
Die in Schwarz/Weiß umgewandelten Bilder konnten aus mir nicht bekannten Gründen nicht hochgeladen werden.

[Kas Ob.]

You are really hardworking on this !

Are you familiar with CMOV instruction ?!!
Read about it from here https://www.felixcloutier.com/x86/cmovcc
Also search and research example for it and its usage, and trust me you will feel real good after that and your above code will go brrrrrrr faster.

eg. That part of clamping the slow one replacing values with

Code:

      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

This could be two CMP and two CMOV, with 0 branching/jumping, will boost the speed nicely, by relieving branch prediction (removing the jmps) letting out-of-order-execution kick in unhindered.
instead of

Code:

               jle      @BlueZero            // Ist <= 0
               cmp      eax,255
               jbe      @BlueSet             // Ist <= 255
               mov      byte[edx],255        // Blauanteil = 255 setzen
               jmp      @Green               // Gr&#1100;nanteil errechnen
@BlueZero:     xor      eax,eax              // Blau = 0
@BlueSet:      mov      [edx],al             // Blauanteil speichern

Also you could ditch all that and try SSE or MMX , both are supported on CPUs for almost 3 decades (MMX) and no need to check for CPU compatibility for it, MMX will perform the all these operation on one pixel (4 colors) in parallel, the speed should be around 4 times than simple plain linear assembly.

[Amateurprofi]

Zitat von Kas Ob.:

You are really hardworking on this !

Are you familiar with CMOV instruction ?!!
Read about it from here https://www.felixcloutier.com/x86/cmovcc
Also search and research example for it and its usage, and trust me you will feel real good after that and your above code will go brrrrrrr faster.

eg. That part of clamping the slow one replacing values with

Code:

      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

This could be two CMP and two CMOV, with 0 branching/jumping, will boost the speed nicely, by relieving branch prediction (removing the jmps) letting out-of-order-execution kick in unhindered.
instead of

Code:

               jle      @BlueZero            // Ist <= 0
               cmp      eax,255
               jbe      @BlueSet             // Ist <= 255
               mov      byte[edx],255        // Blauanteil = 255 setzen
               jmp      @Green               // Gr&#1100;nanteil errechnen
@BlueZero:     xor      eax,eax              // Blau = 0
@BlueSet:      mov      [edx],al             // Blauanteil speichern

Also you could ditch all that and try SSE or MMX , both are supported on CPUs for almost 3 decades (MMX) and no need to check for CPU compatibility for it, MMX will perform the all these operation on one pixel (4 colors) in parallel, the speed should be around 4 times than simple plain linear assembly.

SSE, MMX
Unfortunately Pixels are 3 Bytes, not 4 Bytes in pf24bit-Bitmaps.
Furthermore loading the r,g,b Values from memory into SSE/MMX registers and storing from SSE/MMX registers into memory is (my opinion) slower than my code.
Feel free to prove me wrong.
SSE, MMX
Unfortunately Pixels are 3 Bytes, not 4 Bytes in pf24bit-Bitmaps.
Furthermore loading the r,g,b Values from memory into SSE/MMX registers and storing from SSE/MMX registers into memory is (my opinion) slower than my code.
Feel free to prove me wrong.

CMOV
I am fully aware of that instruction.
However:
1) Would need 2 additional registers for the 0 and 255 (CMOV with #Values is not supported), alternatively I could push a 0 and a 255 on the Stack i.e. CMOV from memory.
2) Both CMOV from registers and CMOV from memory are significantly slower than my code.

1139 CMOV from registers
1123 CMOV from memory
842 my code
Times are ms.
May be, my codes contain errors (did not spend too much time).

PS:
I use the "Intel® 64 and IA-32 Architectures Software Developer’s Manual" to get informations about instructions.
(See Attachments)

Delphi-Quellcode:

const Count=1000000000;
PROCEDURE TestCMov1;
const S:String='  ';
asm
      push     edi
      push     esi
      push     0
      mov      edi,0
      mov      esi,255
      mov      ecx,Count
@1:   mov      edx,-255
@2:   mov      eax,edx
      cmp      edx,0
      cmovl    eax,edi
      cmp      edx,255
      cmova    eax,esi
      mov      [esp],al
      add      edx,1
      cmp      edx,255
      jbe      @2
      sub      ecx,1
      jne      @1
@End: pop      ecx
      pop      esi
      pop      edi
end;

Delphi-Quellcode:

PROCEDURE TestCMov2;
const S:String='  ';
asm
      push     0
      push     255
      push     0
      mov      edi,0
      mov      esi,255
      mov      ecx,Count
@1:   mov      edx,-255
@2:   mov      eax,edx
      cmp      edx,0
      cmovl    eax,[esp+8]
      cmp      edx,255
      cmova    eax,[esp+4]
      mov      [esp],al
      add      edx,1
      cmp      edx,255
      jbe      @2
      sub      ecx,1
      jne      @1
@End: add      esp,12
end;

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;

Delphi-Quellcode:

PROCEDURE Test;
var T0,T1,T2,T3:Cardinal;
begin
   T0:=GetTickCount;
   TestCMov1;
   T1:=GetTickCount;
   TestCMov2;
   T2:=GetTickCount;
   TestMov;
   T3:=GetTickCount;
   Dec(T3,T2);
   Dec(T2,T1);
   Dec(T1,T0);
   ShowMessage(Format('%D CMOV from registers'#13'%D CMOV from memory'#13+
                      '%D my code',[T1,T2,T3]));
end;

[Kas Ob.]

Zitat von Amateurprofi:

SSE, MMX
Unfortunately Pixels are 3 Bytes, not 4 Bytes in pf24bit-Bitmaps.
Furthermore loading the r,g,b Values from memory into SSE/MMX registers and storing from SSE/MMX registers into memory is (my opinion) slower than my code.
Feel free to prove me wrong.
SSE, MMX
Unfortunately Pixels are 3 Bytes, not 4 Bytes in pf24bit-Bitmaps.
Furthermore loading the r,g,b Values from memory into SSE/MMX registers and storing from SSE/MMX registers into memory is (my opinion) slower than my code.
Feel free to prove me wrong.

Does it matter what value in the fourth byte !?, no it doesn't, you can load four bytes and perform the same operation on them the cycles are the same and just drop the last value, if there is a fear of overflowing a buffer, perform the loop on all unless there except the last byte of them all.

Anyway i might find the mood and time to do it in MMX and SSE, why not !

Zitat von Amateurprofi:

CMOV
I am fully aware of that instruction.
However:
1) Would need 2 additional registers for the 0 and 255 (CMOV with #Values is not supported), alternatively I could push a 0 and a 255 on the Stack i.e. CMOV from memory.
2) Both CMOV from registers and CMOV from memory are significantly slower than my code.

1139 CMOV from registers
1123 CMOV from memory
842 my code
Times are ms.
May be, my codes contain errors (did not spend too much time).

Let do clamping right then discuss it, so here a version of that clamping which we should perform very similar or close to in SIMD (MMX/SSE)

Code:

procedure TestCMovShort;
asm
        push    0           // creating temp at [esp]
        mov     edi, 0
        mov     esi, 255
        mov     ecx, Count

@1:     mov     edx,  - 255

@2:     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     [esp], al

@N:     add     edx, 1
        cmp     edx, 255
        jbe     @2
        sub     ecx, 1
        jne     @1

@End:   pop     eax
end;

4 instructions and that is it, one CMP and two CMOV were enough here, why are they slower ? , they are in fact not slower but your code is faster, i am not sure if i can explain it enough to be clear, see, modern CPU do tricks, two of them play big role here in being your branching code faster than CMOV, branch prediction (BP) and Out-of-Order-Execution, OoOE window is getting bigger each CPU generation, the measurement in your code is gaining speed instead of being faster than CMOV basically, CMOV in the above are introducing data hazard by depending on eax in 3 of four consequence instructions, this will hinder OoOE, hence not gaining speed or lets say not gaining the boost, now returning to our case of 3 consequence clamping, this will put both BP and OoOE under stress and test them for size and speed, the bigger the code then they will start to fail to provide the boost in speed, here will CMOV will win.
I hope that was clear

I think CMOV (the short one) in the original code should perform better at wider CPU range specially the ones with few years back, larger and longer loop cmov will be better, also on stressed OS with many multitasking less branching means less cache shuffling, hence speed, with branching and multitasking the L1 cache specially will thrashed continuously, and BP will not boost anything.

PS my CPU is i2600k and it is old , TestMov result is ~890 and TestCMovShort is ~930, tested on the same code above not in the original with 3 clamping.

[Stevie]

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 dec ecx und nicht sub ecx, 1 - dec ist 1 byte instruction, sub benötigt 3 byte

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

[Kas Ob.]

Zitat von Stevie:

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 dec ecx und nicht sub ecx, 1 - dec ist 1 byte instruction, sub benötigt 3 byte

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

Thank you very much, i have no idea what i was thinking missing all that.

here revised version of that benchmark with some semi-real data simulation over 1kb repeated million time.

Code:

uses
  System.SysUtils,
  Windows;

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;

procedure TestMov;
asm
        mov     esi, 255
        mov     ecx, Count

@1:     mov     edi, 0

@2:     mov     edx, dword[Data + edi * 4]
        mov     eax, edx
        cmp     eax, 0
        jle     @Z
        cmp     eax, 255
        jbe     @S
        mov     Byte[CData + edi], 255
        jmp     @N

@Z:     xor     eax, eax

@S:     mov     Byte[CData + edi], al

@N:     inc     edi
        cmp     edi, DATA_LEN
        jle     @2
        dec     ecx
        jne     @1
end;

procedure TestCMovShort;
asm
        mov     esi, 255          // High Limit
        mov     ecx, Count

@1:     mov     edi, 0

@2:     mov     edx, dword[Data + edi * 4]
        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;

procedure Test;
var
  T: Cardinal;
  i: Integer;
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

  T := GetTickCount;
  TestMov;
  T := GetTickCount - T;
  Writeln('TestMov ' + IntToStr(T));

  T := GetTickCount;
  TestCMovShort;
  T := GetTickCount - T;
  Writeln('TestCMovShort ' + IntToStr(T));

end;

begin
  Test;
  Readln;
end.

and the result

Code:

TestMov 1703
TestCMovShort 969

CMOV is almost twice faster.

[Amateurprofi]

Zitat von Stevie:

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 dec ecx und nicht 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).