Floyd-Steinberg Dithering

[shmia]

Ich hätte hier einen Floyd-Steinberg-Algorithmus, der allerdings noch etwas Optimierung benötigt.
Im Prinzip habe ich nur den Pseudocode auf Wikipedia in Delphi umgesetzt.

Wer also gerne mit Grafik spielt, ist aufgerufen, den Code mit Hilfe von Scanline[] und anderen Tricks zu beschleunigen. :hi:

Delphi-Quellcode:

function find_closest_palette_color(Color:TColor):TColor;
begin
//  Color := ColorToRGB(Color);  // wird nicht benötigt, da 24-Bit Bitmap vorhanden
  Result := GetBValue(Color) * 21      // Blue
    + GetGValue(Color) * 174   // Green
    + GetRValue(Color) * 61;  // Red
  if Result >= 32768 then  // 128*256
   Result := clWhite
  else
   Result := clBlack;
end;

type
TError = record
  R, G, B : integer;
end;

// Fehler zwischen zwei Farben berechnen
function CalcError(a,b : TColor):TError;
begin
   Result.R := GetRValue(a)-GetRValue(b);
   Result.G := GetGValue(a)-GetGValue(b);
   Result.B := GetBValue(a)-GetBValue(b);
end;

{**************************************************************************
 * NAME:    ApplyError
 * DESC:    Korrigiert die übergebene Farbe um den Wert err * mul/16
 * PARAMS:  color  - orginale Farbe
 *          err    - Farbabweichung
 *          factor - Korrekturfaktor
 * RESULT:  korrigierte Farbe
 *************************************************************************}
function ApplyError(color:TColor; err:TError; factor:Integer):TColor;
var
   r,g,b : Integer;
begin
   // Hinweis: div 16 lässt sich leider nicht durch shr 4 ersetzen
   // da dann anscheinend das Vorzeichen nicht richtig behandelt wird
   r := GetRValue(color) + ((err.R * factor) div 16);
   if r < 0 then r := 0
   else if r > 255 then r := 255;
   g := GetGValue(color) + ((err.G * factor) div 16);
   if g < 0 then g := 0
   else if g > 255 then g := 255;
   b := GetBValue(color) + ((err.B * factor) div 16);
   if b < 0 then b := 0
   else if b > 255 then b := 255;
   Result := RGB(r,g,b);
end;


procedure FloydSteinberg(bmp: TBitmap);
var
   oldpixel, newpixel: TColor;
   x,y: Integer;
   error : TError;
   y_ok:Boolean;
   cv : TCanvas;
begin
   bmp.PixelFormat := pf24bit;
   cv := bmp.Canvas;
   for y := 0 to bmp.Height-1 do
   begin
      y_ok := (y <> bmp.Height-1);


      x := 0;
      oldpixel := cv.Pixels[x,y];
      newpixel := find_closest_palette_color(oldpixel);
      cv.Pixels[x,y] := newpixel;
      error := CalcError(oldpixel, newpixel);
      cv.Pixels[x+1,y] := ApplyError(cv.Pixels[x+1,y], error, 7);
      if y_ok then
      begin
//      cv.Pixels[x-1,y+1] := ApplyError(cv.Pixels[x-1,y+1], error, 3);
      cv.Pixels[x,y+1] := ApplyError(cv.Pixels[x,y+1], error, 5);
      cv.Pixels[x+1,y+1] := ApplyError(cv.Pixels[x+1,y+1], error, 1);
      end;

      for x := 1 to bmp.Width-2 do
      begin
         oldpixel := cv.Pixels[x,y];
         newpixel := find_closest_palette_color(oldpixel);
         cv.Pixels[x,y] := newpixel;
         error := CalcError(oldpixel, newpixel);
         cv.Pixels[x+1,y] := ApplyError(cv.Pixels[x+1,y], error, 7);
         if y_ok then
         begin
         cv.Pixels[x-1,y+1] := ApplyError(cv.Pixels[x-1,y+1], error, 3);
         cv.Pixels[x,y+1] := ApplyError(cv.Pixels[x,y+1], error, 5);
         cv.Pixels[x+1,y+1] := ApplyError(cv.Pixels[x+1,y+1], error, 1);
         end;
      end;
      if y_ok then
      begin
      x := bmp.Width-1;
      oldpixel := cv.Pixels[x,y];
      newpixel := find_closest_palette_color(oldpixel);
      cv.Pixels[x,y] := newpixel;
      error := CalcError(oldpixel, newpixel);
//      cv.Pixels[x+1,y] := ApplyError(cv.Pixels[x+1,y], error, 7);
      cv.Pixels[x-1,y+1] := ApplyError(cv.Pixels[x-1,y+1], error, 3);
      cv.Pixels[x,y+1] := ApplyError(cv.Pixels[x,y+1], error, 5);
//      cv.Pixels[x+1,y+1] := ApplyError(cv.Pixels[x+1,y+1], error, 1);
      end;
   end;
end;

[Amateurprofi]

@shmia,
vielen herzlichen Dank!
Hab mich aufgerufen gefühlt.
Ist etwas schneller als das Original.
Zeitbedarf für ein Bild mit 4608 x 3456 Pixeln:
Original ca. 180 s
Fälschung ca. 1 s

Delphi-Quellcode:

PROCEDURE FloydSteinberg(Bmp:TBitmap);
resourcestring
   sNo24Bit='Bmp ist keine pf24bit-Bitmap';
   sSize='%S der Bitmap ist = 0';
type
   TBGR=packed record Blue,Green,Red:Byte; end;
   TxBGR=packed record xBlue,xGreen,xRed:Byte; end;
   TPBGR=^TBGR;
   TPxBGR=^TxBGR;
   TDelta=packed record B,G,R:Integer; end;
var
   LO:NativeInt; // Offset zur jeweils nächsten Zeile in Bmp
   Delta:TDelta; // Differenzen alte Farbanteile - neue Farbanteile
   P:TPBGR;      // Zeiger auf aktuelles Pixel
//------------------------------------------------------------------------------
PROCEDURE SetNearestColor;
const
   NC:Array[Boolean] of TBGR=
      ((Blue:255; Green:255; Red:255),(Blue:0; Green:0; Red:0));
var OldPixel:TBGR;
begin
   OldPixel:=P^;
   with OldPixel, TPxBGR(P)^, Delta do begin
       P^:=NC[Blue*21+Green*174+Red*61<32768];
       B:=Blue-xBlue;
       G:=Green-xGreen;
       R:=Red-xRed;
   end;
end;
//------------------------------------------------------------------------------
PROCEDURE SetPixel(XOffset,YOffset,Factor:Integer);
var AP:TPBGR;
begin
   // XOffset=Horizontaler Offset in Pixel
   // YOffset=Vertikaler Offset in Bytes
   AP:=P;
   Inc(AP,XOffset);
   Inc(NativeInt(AP),YOffset);
   with AP^, Delta do begin
      Blue:=EnsureRange(Blue+B*Factor div 16,0,255);
      Green:=EnsureRange(Green+G*Factor div 16,0,255);
      Red:=EnsureRange(Red+R*Factor div 16,0,255);
   end;
end;
//------------------------------------------------------------------------------
var W,H,X,Y:Integer; PP:TPBGR;
begin
   if Bmp.PixelFormat<>pf24Bit then raise Exception.Create(sNo24Bit);
   W:=Bmp.Width-1;  // Letztes Pixel einer Zeile
   H:=Bmp.Height-1; // Letzte Zeile
   if W<0 then raise Exception.CreateFmt(sSize,['Breite']);
   if H<0 then raise Exception.CreateFmt(sSize,['Höhe']);
   PP:=Bmp.ScanLine[0];
   if H>0 then LO:=NativeInt(Bmp.ScanLine[1])-NativeInt(PP) else LO:=0;
   for Y:=H downto 0 do begin
      P:=PP;
      for X:=W downto 0 do begin
         SetNearestColor;
         if X<>0 then SetPixel(1,0,7);
         if Y<>0 then  begin
            if X<>W then SetPixel(-1,LO,3);
            SetPixel(0,LO,5);
            if X<>0 then SetPixel(1,LO,1);
         end;
         Inc(P);
      end;
      Inc(NativeInt(PP),LO)
   end;
end;

[haentschman]

Moin...8-)

Delphi-Quellcode:

with OldPixel, TPxBGR(P)^, Delta do begin
...

Sei bitte nicht böse...aber das mit dem WITH und noch mit mehreren Werten rollen sich mir die Fußnägel hoch. :roll:
Auch wenn es funktioniert...es wird heutzutage davor gewarnt. :warn: Den Neulingen, die auch mitlesen, sollte man das nicht mehr beibringen. :wink:

[Kas Ob.]

Excellent work.

I have few suggestion:
1) Switch from using Integer to NativeUInt or NativeInt, this will pay in x64, as the compiler will not have to insert resizing instructions like movzx and will have the ability to use full register operation.
2) Replace that EnsureRange with simple old fashion if-statement, saving a needless branch.
3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.
4) This is the meat of this and i think it should pay on low cache CPU's or big images or very busy CPU, instead of getting the last line which have the index 0 then go backward "PP:=Bmp.ScanLine[0];" replace with getting the first line and move forward, also for X there is no point of walking backward, see, with huge images, and walking backward the cache lines will continuously be read in backward causing violation and request to update, while the CPU request its cache lines in bulk forward most the time, so accessing the memory backward with thrash the cache and waste time and cycles waiting for memory.

[Kas Ob.]

Zitat:

Zitat von haentschman (Beitrag 1528355)

Sei bitte nicht böse...aber das mit dem WITH und noch mit mehreren Werten rollen sich mir die Fußnägel hoch.

I am more angry than you about the loss of readability and the risk with it :wall:, BUT the CPU is more retarded than a 15th century brick, and without pushing its face into the point with "with" it will not generate a decent code (in many cases anyway).

So yes, i am more angry about the compiler than the "with" or who use it.

[Uwe Raabe]

OT: Wie kommt man eigentlich auf die Idee, einen 15 Jahre alten Thread wieder aufleben zu lassen? Insbesondere, da die letzte Aktivität des Posters mittlerweile auch schon fast 11 Jahre zurück liegt.

[Kas Ob.]

Zitat:

Zitat von Uwe Raabe (Beitrag 1528372)

OT: Wie kommt man eigentlich auf die Idee, einen 15 Jahre alten Thread wieder aufleben zu lassen? Insbesondere, da die letzte Aktivität des Posters mittlerweile auch schon fast 11 Jahre zurück liegt.

:shock: :?

[Sinspin]

Zitat:

Zitat von Uwe Raabe (Beitrag 1528372)

OT: Wie kommt man eigentlich auf die Idee, einen 15 Jahre alten Thread wieder aufleben zu lassen? Insbesondere, da die letzte Aktivität des Posters mittlerweile auch schon fast 11 Jahre zurück liegt.

Warum nicht, es geht ums gleiche Thema.
Ist generell eine Überlegung wert da weiter zu machen wo jemand schonmal was gemacht hat. Fängt man halt nicht bei null an.
Interessant dazu ist auch der Einleitungstext:

Zitat:

Zitat von Amateurprofi (Beitrag 1528354)

@shmia,
vielen herzlichen Dank!
Hab mich aufgerufen gefühlt.
Ist etwas schneller als das Original.
Zeitbedarf für ein Bild mit 4608 x 3456 Pixeln:
Original ca. 180 s
Fälschung ca. 1 s

Es ist einfach nicht aufgefallen dass die Einladung alterstechnisch schon in der Oberstufe ist.
Ist noch keinem von uns passiert?

Zitat:

Zitat von Kas Ob. (Beitrag 1528371)

I am more angry than you about the loss of readability and the risk with it :wall:, BUT the CPU is more retarded than a 15th century brick, and without pushing its face into the point with "with" it will not generate a decent code (in many cases anyway).

So yes, i am more angry about the compiler than the "with" or who use it.

Delphi-Quellcode:

With

have no effect for the compiler. Its just a help for lazy programmer to save some time (they think at least that they save time). Later on, when they have to review or extend the code, they have an high chance to get confused and make errors. Which will then, for sure, cost more time than they have saved in first instance.

[himitsu]

Delphi-Quellcode:

var R: TRect;

with R do
  Width := Right - Left + 1;

Also ich fand es witzig, als so ein Code urplötzlich nichts mehr machte, also nicht mehr die Breite der Form zu setzen,
weil TRect plötzlich ein Property Width bekommen hatte und Dieses dann eben nicht mehr das Width der Form war. :lol:

PS: Inline-Variablen, wenn es unbedingt sein muß.

[Amateurprofi]

Zitat:

Zitat von haentschman (Beitrag 1528355)

Moin...8-)

Delphi-Quellcode:

with OldPixel, TPxBGR(P)^, Delta do begin
...

Sei bitte nicht böse...aber das mit dem WITH und noch mit mehreren Werten rollen sich mir die Fußnägel hoch. :roll:
Auch wenn es funktioniert...es wird heutzutage davor gewarnt. :warn: Den Neulingen, die auch mitlesen, sollte man das nicht mehr beibringen. :wink:

Nee, warum sollte ich böse sein.
Ich verstehe, dass es im Profi-Bereich notwendig, oder zumindest sinnvoll ist, sich an ein bestimmtes Regelwerk zu halten.
Wie jedoch mein Username vermuten lässt bin ich, IT-bezogen, eher Amateur.
Und ich liebe "with", weil es kompakteren Source-Code ermöglicht.
Aus der Delphi Hilfe "When you use the with statement, your code becomes shorter and easier to read".
Letzteres würde ich allerdings nicht unterschreiben.
Zu

Zitat:

rollen sich mir die Fußnägel hoch

Mal zur Fußpflege gehen? (Nicht böse gemeint.)

[Amateurprofi]

Zitat:

Zitat von himitsu (Beitrag 1528391)

Delphi-Quellcode:

var R: TRect;

with R do
  Width := Right - Left + 1;

Also ich fand es witzig, als so ein Code urplötzlich nichts mehr machte, also nicht mehr die Breite der Form zu setzen,
weil TRect plötzlich ein Property Width bekommen hatte und Dieses dann eben nicht mehr das Width der Form war. :lol:

PS: Inline-Variablen, wenn es unbedingt sein muß.

Ja, genau das ist mir mal mit einem Uralt-Programm passiert, das (neu kompiliert) auf einmal nicht mehr lief.
Hab damals ziemlich lange gebraucht, um zu begreifen, woran es lag.

[Amateurprofi]

Zitat:

Zitat von Uwe Raabe (Beitrag 1528372)

OT: Wie kommt man eigentlich auf die Idee, einen 15 Jahre alten Thread wieder aufleben zu lassen? Insbesondere, da die letzte Aktivität des Posters mittlerweile auch schon fast 11 Jahre zurück liegt.

Weil ich auf der Suche nach einem Floyd-Steinberg Algo auf den Thread gestoßen bin und wirklich happy war, als ich den bei shmia fand.
Ich hätte das ja auch als neuen Thread, ohne Bezug auf shmia, posten können, aber ich schmücke mich nicht gern mit fremden Federn.
Übrigens: Die Pyramiden bei Gizeh sind etwas älter als 15 Jahre und werden trotzdem gern und oft besucht.

[Amateurprofi]

Zitat:

Zitat von Kas Ob. (Beitrag 1528370)

Excellent work.

I have few suggestion:
1) Switch from using Integer to NativeUInt or NativeInt, this will pay in x64, as the compiler will not have to insert resizing instructions like movzx and will have the ability to use full register operation.
2) Replace that EnsureRange with simple old fashion if-statement, saving a needless branch.
3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.
4) This is the meat of this and i think it should pay on low cache CPU's or big images or very busy CPU, instead of getting the last line which have the index 0 then go backward "PP:=Bmp.ScanLine[0];" replace with getting the first line and move forward, also for X there is no point of walking backward, see, with huge images, and walking backward the cache lines will continuously be read in backward causing violation and request to update, while the CPU request its cache lines in bulk forward most the time, so accessing the memory backward with thrash the cache and waste time and cycles waiting for memory.

Zitat:

3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.

No!
shr with negative numbers?
The compiler converts "Div 16" to "sar 4".

[himitsu]

Zitat:

Regelwerk

Ja, teilweise wird es verboten,

aber im Grunde ist es einfach ein "es gibt massenhaft Probleme damit, von nervt beim Debuggen, über CodeInsight/Refactoring dreht durch, bis zu Programmfehler, weil sich was geändert hat .... drum sollte man es besser garnicht erst verwenden"

Zitat:

with shr n, so div 16 can be shr 4.

only for unsigned integers

[Amateurprofi]

[QUOTE=Amateurprofi;1528396]

Zitat:

Zitat von Kas Ob. (Beitrag 1528370)

Excellent work.

I have few suggestion:
1) Switch from using Integer to NativeUInt or NativeInt, this will pay in x64, as the compiler will not have to insert resizing instructions like movzx and will have the ability to use full register operation.
2) Replace that EnsureRange with simple old fashion if-statement, saving a needless branch.
3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.
4) This is the meat of this and i think it should pay on low cache CPU's or big images or very busy CPU, instead of getting the last line which have the index 0 then go backward "PP:=Bmp.ScanLine[0];" replace with getting the first line and move forward, also for X there is no point of walking backward, see, with huge images, and walking backward the cache lines will continuously be read in backward causing violation and request to update, while the CPU request its cache lines in bulk forward most the time, so accessing the memory backward with thrash the cache and waste time and cycles waiting for memory.

Have tested your suggestions.
1) NativeInt instead of Integers
Doubles the used time.
2) Replacing EnsureRange bei If then ..,
Adds another few ms
3) shr instead of Div 16
Commented earlier
4) Starting with the Bottom Line
Not tested, would expect advantages
4) X forward
Not tested would expect disadvantages (see the "if X<>..." in the X-Loop)

The measured runtimes
1339 With Integers
2559 With NativeInts
2606 EnsureRange replaced by If-Then

[Kas Ob.]

Hi for all,
Please bare a little with me, i mean really don't take my calling the Delphi Compiler as an offense toward anyone, it is just i know it, i used to be and still earning my bread from optimizing old and new code, i know the compiler very intimately to call it a fucking centuries old brick.

I will explain just this piece of code, and if you want to expand on it, but first and foremost please, at least consider your knowledge of the code generated by Delphi is wrong(outdated or naively trusting) or unoptimized (inefficient) and will go from there to proof a contradiction, how about that ?.. it is my best method as mathematician by education.

so many agreed on div 16 is always shr 4 or to be more concise should be sar 4, i agree and i know that the compiler wrongly do it for unsigned integers, but this is not the case, as i was talking about that specific case at hand, may be it is my mistake may to not wrote an essay for each line i wrote.

So here a proof that the compiler doesn't use sar 4 or shr 4 for div 16, the proof is just look at x64 version of it !! :shock:

try this function in the above optimized version

Code:

PROCEDURE SetPixel(XOffset,YOffset,Factor:NativeInt);
var AP:TPBGR;
begin
   // XOffset=Horizontaler Offset in Pixel
   // YOffset=Vertikaler Offset in Bytes
   AP:=P;
   Inc(AP,XOffset);
   Inc(NativeInt(AP),YOffset);
   with AP^, Delta do begin
      Blue:=EnsureRange(Blue+B*Factor shr 4,0,255);
      Green:=EnsureRange(Green+G*Factor shr 4,0,255);
      Red:=EnsureRange(Red+R*Factor shr 4,0,255);
   end;
end;

My speed shows that it is faster by 18% in Win32 and 29% on Win64 !! do it please, it is not slower by 200%, and these values as positive so no problem here.
also if you look at the generated assembly code, then this is it
Anhang 56355

Also try this

Code:

  procedure SetPixel(XOffset, YOffset, Factor: NativeInt);
  var
    AP: TPBGR;
    v: NativeInt;
  begin
    AP := P;
    Inc(AP, XOffset);
    Inc(NativeInt(AP), YOffset);
    with AP^, Delta do
    begin
      v := Blue + B * Factor shr 4;
      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

      v := Green + G * Factor shr 4;
      if v < 0 then
        Green := 0
      else if v > 255 then
        Green := 255
      else
        Green := v;

      v := Red + R * Factor shr 4;
      if v < 0 then
        Red := 0
      else if v > 255 then
        Red := 255
      else
        Red := v;
    end;
  end;

The above function makes the whole process around double the speed, 8-) for both platform .

and again not saying that i know it all, i do mistakes, but not in this case, would love to be proven wrong, but with factual code done right not with you assumptions based on something you didn't see for sure.

My test is attached here Anhang 56359 and hope it is working unlike the above attached project as it is empty.

As for "with" the compiler might fail to generate nice assembly and will revert to shuffle the data and access them continuously on the stack introducing unneeded memory access, this happen with complex loops also, with "with" it in many case will resolve the pointer and reused it from a register, alas it seems no gain in the above mentioned function, but once the function have few more local variables and it will go 90s turbo pascal mode specially in x64 platforms, i don't have the mood to sit and tweak such case for you now, but the effect is there.

ps re-reading before posting this, i sound retarded and offended, and i am sorry for that, i don't mean to offend anyone and never meant to, just had very bad experience from an neighbor forum and trying to be triggered by personal sentences.

[Kas Ob.]

Forgot to attach a screenshot of my result
Anhang 56358

May be not in everyone interest to notice that, but do you see the consistency in the result, or the closeness of the result, this show the relax and the ability of the cache on CPU level, just by removing the EnsureRange branching for each pixel 3 times.

[skybibo]

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Daher würde ich eine Zweite Bitmap für das Ergebnis verwenden. Der nächste Schritt wäre dann die Verwendung von TParallel.For um noch schneller zu werden. Optimal wäre dann als nächstes die Verwendung von Cuda oder OpenCL.

[Kas Ob.]

Zitat:

Zitat von skybibo (Beitrag 1528442)

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Yes, and thank you, i see my mistake, though the difference should not negate the gain in performance from using removing EnsureRange and replacing shr 4 with div on x64.

The code can be rearranged little more.

[himitsu]

Zitat:

Zitat von skybibo (Beitrag 1528442)

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Daher würde ich eine Zweite Bitmap für das Ergebnis verwenden. Der nächste Schritt wäre dann die Verwendung von TParallel.For um noch schneller zu werden. Optimal wäre dann als nächstes die Verwendung von Cuda oder OpenCL.

Das ist hier kein Problem, da hier für jedes Pixel extra nicht die umgebenden Pixel betrachtet werden (wo bereits bearbeitete enthalten wären),
sondern ausschließlich nur nachfolgende Pixel "leicht geändert" werden, welche später dran kommen.

https://youtu.be/PyRrgjwpzYE?si=mG1QEo_MAYzSqJXW&t=444

Zitat:

Threads, TParallel.For usw.

Problem ist hier auch, dass es sich nicht parallelisieren lässt, da es immer Überschneidungen gibt, außer du hast irgendwo 100% schwarze bzw. weiße Pixel, welche keinen Fehler verursachen.
Denn nur nach solchen Zeilen (oder Spalten) kannst du "neu" beginnen, ohne dass die nachfolgende Zeile einen Einfluß hat.

Würden der "Fehler" nur auf nachfolgene in der eigenen Zeile verteilt, dann gäbe es zwischen den Zeilen keine Beziehung und du könntest es parallelisieren.
Ausnahme: man teilt das Bild vorher in Blöcke und berechnet jeden Block für sich, aber da kann es gerade "kanten" im Bild geben, wo sich optisch sichtbar die Verteilung ändert.



JA, es lässt sich "theoretisch" parallelisieren, also die nächste Zeile lässt sich schon berechnen, während die vorhergehende Zeile noch arbeitet (Zeilen übersrpingen geht nicht),
aber der Aufwand das zu synchronisieren frißt bestimmt die Ersparnis auf,
denn es muß immer 2 Pixel hinter der jeweils vorherigen Zeile bleiben, weil dort da dann die Fehlerwerte bereits fest stehen.
Je Zeile ein Thread würde es sich dann von der Ecke links-oben nach rechts-unten bewegen.
Außerdem würden dann die Threads gegenseitig in gleichen Speicherblöcken arbeiten, was dem Cache der CPU komplett entgegen wirkt und es nur noch bremst.

[Amateurprofi]

Zitat:

Zitat von Kas Ob. (Beitrag 1528417)

Hi for all,
Please bare a little with me, i mean really don't take my calling the Delphi Compiler as an offense toward anyone, it is just i know it, i used to be and still earning my bread from optimizing old and new code, i know the compiler very intimately to call it a fucking centuries old brick.

I will explain just this piece of code, and if you want to expand on it, but first and foremost please, at least consider your knowledge of the code generated by Delphi is wrong(outdated or naively trusting) or unoptimized (inefficient) and will go from there to proof a contradiction, how about that ?.. it is my best method as mathematician by education.

so many agreed on div 16 is always shr 4 or to be more concise should be sar 4, i agree and i know that the compiler wrongly do it for unsigned integers, but this is not the case, as i was talking about that specific case at hand, may be it is my mistake may to not wrote an essay for each line i wrote.

So here a proof that the compiler doesn't use sar 4 or shr 4 for div 16, the proof is just look at x64 version of it !! :shock:

try this function in the above optimized version

Code:

PROCEDURE SetPixel(XOffset,YOffset,Factor:NativeInt);
var AP:TPBGR;
begin
   // XOffset=Horizontaler Offset in Pixel
   // YOffset=Vertikaler Offset in Bytes
   AP:=P;
   Inc(AP,XOffset);
   Inc(NativeInt(AP),YOffset);
   with AP^, Delta do begin
      Blue:=EnsureRange(Blue+B*Factor shr 4,0,255);
      Green:=EnsureRange(Green+G*Factor shr 4,0,255);
      Red:=EnsureRange(Red+R*Factor shr 4,0,255);
   end;
end;

My speed shows that it is faster by 18% in Win32 and 29% on Win64 !! do it please, it is not slower by 200%, and these values as positive so no problem here.
also if you look at the generated assembly code, then this is it
Anhang 56355

Also try this

Code:

  procedure SetPixel(XOffset, YOffset, Factor: NativeInt);
  var
    AP: TPBGR;
    v: NativeInt;
  begin
    AP := P;
    Inc(AP, XOffset);
    Inc(NativeInt(AP), YOffset);
    with AP^, Delta do
    begin
      v := Blue + B * Factor shr 4;
      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

      v := Green + G * Factor shr 4;
      if v < 0 then
        Green := 0
      else if v > 255 then
        Green := 255
      else
        Green := v;

      v := Red + R * Factor shr 4;
      if v < 0 then
        Red := 0
      else if v > 255 then
        Red := 255
      else
        Red := v;
    end;
  end;

The above function makes the whole process around double the speed, 8-) for both platform .

and again not saying that i know it all, i do mistakes, but not in this case, would love to be proven wrong, but with factual code done right not with you assumptions based on something you didn't see for sure.

My test is attached here Anhang 56359 and hope it is working unlike the above attached project as it is empty.

As for "with" the compiler might fail to generate nice assembly and will revert to shuffle the data and access them continuously on the stack introducing unneeded memory access, this happen with complex loops also, with "with" it in many case will resolve the pointer and reused it from a register, alas it seems no gain in the above mentioned function, but once the function have few more local variables and it will go 90s turbo pascal mode specially in x64 platforms, i don't have the mood to sit and tweak such case for you now, but the effect is there.

ps re-reading before posting this, i sound retarded and offended, and i am sorry for that, i don't mean to offend anyone and never meant to, just had very bad experience from an neighbor forum and trying to be triggered by personal sentences.

Delphi-Quellcode:

    with AP^, Delta do
    begin
      v := Blue + B * Factor shr 4;

Please be aware of that the values in Delta (R,G,B) may be negative.
Assume AP.Blue=200 and Delta.B=-10 and Factor=7.
Then V will evaluated as
V := Blue + ((B * Factor) shr 4);
V := 200 + ((-10 * 7) shr 4);
V := 200 + (-70 shr 4);
V := 200 + 268435451;
V := 268435651;
Korrekt is
V := Blue + ((B * Factor) div 16);
V := 200 + ((-10 * 7) div 16);
V := 200 + (-70 div 16);
V := 200 + -4;
V := 196;

[Kas Ob.]

[QUOTE=himitsu;1528459]

Zitat:

Zitat von skybibo (Beitrag 1528442)

Please be aware of that the values in Delta (R,G,B) may be negative.
Assume AP.Blue=200 and Delta.B=-10 and Factor=7.
Then V will evaluated as
V := Blue + ((B * Factor) shr 4);
V := 200 + ((-10 * 7) shr 4);
V := 200 + (-70 shr 4);
V := 200 + 268435451;
V := 268435651;
Korrekt is
V := Blue + ((B * Factor) div 16);
V := 200 + ((-10 * 7) div 16);
V := 200 + (-70 div 16);
V := 200 + -4;
V := 196;

Thank you, and i was wrong, it is a mistake, as i was after the speed not the functionality per se, and that is wrong, i was aware of of negative values, but was after proving a different thing.

So here fixed a function that will generate the right image, (well i hope so this time :oops: )

Code:

  procedure SetPixel(XOffset, YOffset: NativeInt; Factor: NativeUInt);
  var
    AP: TPBGR;
    v: Int16;
  begin
    AP := P;
    Inc(AP, XOffset);
    Inc(NativeInt(AP), YOffset);
    with AP^ do
    begin
      v := Int16(Blue) + Int16(Delta.B) * Uint16(Factor) shr 4;
      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

      v := Int16(Green) + Int16(Delta.G) * Uint16(Factor) shr 4;
      if v < 0 then
        Green := 0
      else if v > 255 then
        Green := 255
      else
        Green := v;

      v := Int16(Red) + Int16(Delta.R) * Uint16(Factor) shr 4;
      if v < 0 then
        Red := 0
      else if v > 255 then
        Red := 255
      else
        Red := v;
    end;
  end;

and that shows another inefficiency in the compiler as we can't control the size of the operation and it will insist on using what ever get in its little brain, so i had to use (U)Int16 to force the compiler to use iMul, losing speed in the process.
This can be fixed but will need change the structure of the data in overall, but this still faster though we went from Native(U)Int instructions to much slower 16 bit instructions.

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

Zitat von Kas Ob. (Beitrag 1529149)

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:

Zitat von Amateurprofi (Beitrag 1529173)

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:

Zitat von Amateurprofi (Beitrag 1529173)

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 :oops:

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

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

[Kas Ob.]

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

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.

[Stevie]

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)

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