bitmap32 and xor

[Trinity.dp]

Hallo liebe "Praxler"!

Gestern habe ich eine neue "Rückgängig"-Funktion für mein Bildbearbeitungsprogramm geschrieben. Dabei bin ich auf eine interessantes Phänomen gestoßen, welches mir schon viel Kopfzerbrechen bereitet hat.

Ich benutze xor um die Differenz von zwei Bitmap32 Bildern zu ermitteln. Das funktioniert auch wunderbar, falls diese Bilder nicht 1x1 Pixel große sind (dann funktioniert xor nämlich nicht). Ich habe eine kleines Testprogramm geschrieben, welches den Fehler verdeutlicht. Auf der Form befinden sich ein Button und ein Memo. Weitere Anmerkungen stehen unten beim Output.

Bitte helft mir! Ich habe schon sehr viel Zeit investiert diese Verhalten zu verstehen, aber es ist mir immer noch unerklärlich und für mein Programm leider zentral.

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, gr32;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

 // xor two memory blocks
 procedure MemBlockXOR(const Source1, Source2, Destination: Pointer;
                            Blocksize: Integer); assembler;
    asm
      push edi
      push esi
      push ebx
      mov esi,eax
      mov edi,ecx
      mov ecx,Blocksize;
      mov eax,[esi]
      and eax,[edx]
      mov [edi],eax
      mov eax,[esi+4]
      and eax,[edx+4]
      mov [edi+4],eax
      add esi,ecx
      add edx,ecx
      add edi,ecx
      shr ecx,3
      test ecx,ecx
      jz @@ending
      neg ecx
    @@doit:
      mov eax,[esi+ecx*8]
      mov ebx,[esi+ecx*8+4]
      xor eax,[edx+ecx*8]
      xor ebx,[edx+ecx*8+4]
      mov [edi+ecx*8],eax
      mov [edi+ecx*8+4],ebx
      inc ecx
      jnz @@doit
    @@ending:
      pop ebx
      pop esi
      pop edi
 end;

 // helper function for testing only
 function IntToBin ( value: LongInt; digits: integer ): string;
  begin
    result := StringOfChar ( '0', digits ) ;
    while value > 0 do begin
      if ( value and 1 ) = 1 then
        result [ digits ] := '1';
      dec ( digits ) ;
      value := value shr 1;
    end;
  end;
  

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
  var bmp1, bmp2, xbmp : TBitmap32;
begin
// create bitmaps
bmp1 := TBitmap32.Create;
bmp2 := TBitmap32.create;
xbmp := TBitmap32.create;

// FIRST test, everything works
bmp1.SetSize(2,2);
bmp1.Clear(tcolor32($124423213));
bmp2.SetSize(2,2);
bmp2.Clear(tcolor32(clblue));
xbmp.setSize(2,2);

// check what we get
memo1.Lines.Add('TEST 1: ');

// xbmp := bmp1 xor bmp2;
MemBlockXOR(@bmp1.Bits[0], @bmp2.Bits[0], @xbmp.bits[0], sizeof(tcolor32) * (bmp1.width * bmp1.height));

memo1.lines.add(inttobin(bmp1.Pixels[0,0],32) + ' xor');
memo1.lines.add(inttobin(bmp2.Pixels[0,0],32) + ' =');
memo1.lines.add(inttobin(xbmp.Pixels[0,0],32));

// SECOND test, fail
bmp1.SetSize(1,1);
bmp1.Clear(tcolor32($124423213));
bmp2.SetSize(1,1);
bmp2.Clear(tcolor32(clblue));
xbmp.setSize(1,1);

// check what we get
memo1.Lines.Add('TEST 2: ');

// xbmp := bmp1 xor bmp2;
MemBlockXOR(bmp1.ScanLine[0], bmp2.ScanLine[0], xbmp.ScanLine[0], sizeof(tcolor32) * (bmp1.width * bmp1.height));

memo1.lines.add(inttobin(bmp1.Pixels[0,0],32) + ' xor');
memo1.lines.add(inttobin(bmp2.Pixels[0,0],32) + ' =');
memo1.lines.add(inttobin(xbmp.Pixels[0,0],32));

// free bitmaps
bmp1.free;
bmp2.free;
xbmp.free;

end;

end.

Output:

Code:

TEST 1: 
00100100010000100011001000010011 xor
00000000111111110000000000000000 =
00100100101111010011001000010011
TEST 2: 
00100100010000100011001000010011 xor
00000000111111110000000000000000 =
00000000010000100000000000000000

Man sieht, dass die xor Funktion im zweiten Fall nicht richtig funktioniert.

[Aphton]

1. Ich verstehe nicht, was das Problem ist, weil du es nicht genau formuliert hast.
Was genau ist der Fehler; was soll geschehen, was geschieht?

2. In der Funktion IntToBin() ist ein potenzieller Fehler:
Wenn Digits < als Anzahl der tatsächlichen Stellen (Index Fehler, da digits < 1 aber einer gewissen Anzahl von Schleifendurchläufen -> anders lösen)!

[Trinity.dp]

Hallo Aphton!

Zitat von Aphton:

1. Ich verstehe nicht, was das Problem ist, weil du es nicht genau formuliert hast.
Was genau ist der Fehler; was soll geschehen, was geschieht?

Das tut mir Leid. Ich war wohl zu sehr in der Materie. Ich habe oben den Output und das konkrete Problem ergänzt.

Zitat von Aphton:

2. In der Funktion IntToBin() ist ein potenzieller Fehler:
Wenn Digits < als Anzahl der tatsächlichen Stellen (Index Fehler, da digits < 1 aber einer gewissen Anzahl von Schleifendurchläufen -> anders lösen)!

Die IntToBin Funktion dient nur zum Testen. Aber danke für den Hinweis!

[Aphton]

Oh warte mal. (Alles wieder löschen...)

Deine MemoryAsString() ist auch fehlerhaft. Per CopyMemory kopierst du nicht einzelne Bits, sondern ganze Bytes. Deshalb ist diese Codesequenz auch falsch:

Delphi-Quellcode:

  CopyMemory(@buffer, p, 1);
  if buffer then
    result := result + '1'

Dh. der Output ist womöglich auch inkorrekt!

Den Assembler Code möchte ich momentan nicht entziffern, aber ich schätze mal, da sind auch welche Fehler. Und warum das Ganze in Assembler? Geht ja auch ganz normal?!

probier

Delphi-Quellcode:

procedure XorMemBlock(Source1, Source2, Destination: PByte; Count: Integer);
begin
  while Count > 0 do
  begin
    Destination^ := Source1^ xor Source2^;
    inc(Source1);
    inc(Source2);
    inc(Destination);
  end;
end;

[Trinity.dp]

Zitat von Aphton:

Oh warte mal. (Alles wieder löschen...)

Deine MemoryAsString() ist auch fehlerhaft. Per CopyMemory kopierst du nicht einzelne Bits, sondern ganze Bytes. Deshalb ist diese Codesequenz auch falsch:

Delphi-Quellcode:

  CopyMemory(@buffer, p, 1);
  if buffer then
    result := result + '1'

Dh. der Output ist womöglich auch inkorrekt!

Der Output müsste stimmen. Die Funktion war nur ein Überbleibsel von meinem weiteren Test und wird an keiner Stelle benutzt (hab sie jetzt auch gelöscht).

Zitat von Aphton:

Den Assembler Code möchte ich momentan nicht entziffern, aber ich schätze mal, da sind auch welche Fehler. Und warum das Ganze in Assembler? Geht ja auch ganz normal?!

probier

Delphi-Quellcode:

procedure XorMemBlock(Source1, Source2, Destination: PByte; Count: Integer);
begin
  while Count > 0 do
  begin
    Destination^ := Source1^ xor Source2^;
    inc(Source1);
    inc(Source2);
    inc(Destination);
  end;
end;

Assembler Code müsste eigentlich auch stimmen. Ich brauche Geschwindigkeit. Dein Code gibt leider einen Fehler. Ich schaue mal ob ich diesen finden kann!

Vielen Dank schon mal, auch wenn ich immer noch ganz am Anfang stehe.

Edit: Ok es fehlte wirklich nur das decrease. Und mit deinem Code funktioniert es auch. Dann muss ich wohl noch mal den Assembler-Code anschauen.

Edit2: Vielen lieben Dank! Du hast mir sehr geholfen.

[Aphton]

Ach echt? Habs ja auch nicht getestet, nur schnell hingetippt. Mal kucken...
Ok. Stimmt sry, habe dec(Count) in der Schleife vergessen:

Delphi-Quellcode:

procedure XorMemBlock(Source1, Source2, Destination: PByte; Count: Integer);
begin
  while Count > 0 do
  begin
    Destination^ := Source1^ xor Source2^;
    inc(Source1);
    inc(Source2);
    inc(Destination);
    dec(Count);
  end;
end;

Assembler <> Geschwindigkeit, denn letzendlich wird der Delphi-Code, sofern richtig programmiert, auch in Assembler-Code konvertiert (kompiliert)!
Außer du wendest Assembler-eigene Tricks an, die ich nirgends sehe!

[Trinity.dp]

Zitat von Aphton:

Assembler <> Geschwindigkeit, denn letzendlich wird der Delphi-Code, sofern richtig programmiert, auch in Assembler-Code konvertiert (kompiliert)!
Außer du wendest Assembler-eigene Tricks an, die ich nirgends sehe!

Du hast recht. Dein Code ist nur unwesentlich langsamer als der Assembler-Code (~600ms vs ~450ms). Das sollte für meine Zwecke immer noch reichen. Du kannst dir gar nicht vorstellen wie glücklich ich bin! Vielen, vielen Dank!

[Namenloser]

Man kann übrigens auch verständlichen Assembler-Code schreiben

Delphi-Quellcode:

procedure MemBlockXOR_2(Source1, Source2, Destination: Pointer; Count: Integer);
asm
  push edi;
  push esi;

  mov esi, eax;
  mov edi, ecx;
  mov ecx, Count;
  shr ecx, 2; // div by 4 (sizeof int)

  // esi <- Source1
  // edx <- Source2
  // edi <- Destination
  // ecx <- Count

  // exit if count = 0
  test ecx, ecx;
  jz @@end;

  @@loop:
  mov eax, [esi];
  xor eax, [edx];
  mov [edi], eax;

  add esi, 4;
  add edx, 4;
  add edi, 4;

  dec ecx;
  jnz @@loop;

  @@end:

  pop esi;
  pop edi;
end;

Einen Tick schneller als dein ursprünglicher Code ist er zudem auch noch, und er besteht alle Tests. Allerdings funktioniert er nur bei ganzen Integer-Grenzen, also wenn Count durch 4 teilbar ist, sonst wird der Rest abgeschnitten (nicht ge-xor’t). Wie dein Original-Code das handhabt, konnte ich nicht entziffern. Aphtons Variante funktioniert immer, ist jedoch langsamer, weil sie mit Bytes arbeitet.

[Trinity.dp]

Hallo NamenLozer,

für mein Beispiel funktioniert dein Code zwar, allerdings muss er irgendwo einen Fehler enthalten. In meinem "richtigen" Programm funktioniert er jedenfalls gar nicht. Der Parameter Count ist bei mir immer eine durch vier teilbare Zahl, da dieser als Faktor sizeof(tcolor32) beinhaltet.

Ich werde mir deinen asm morgen (ausgeschlafen) mal zu Gemüt führen.

Schöne Grüße,
trin

[Namenloser]

Hmm, seltsam, eigentlich sehe ich keinen Grund, warum er nicht funktionieren sollte. Aber ist ja auch nicht so wichtig... so groß ist der Geschindigkeitsvorteil ja auch nicht – im Zweifelsfalle sollte man da eh die lesbarere und portablere Variante bevorzugen.

Wenn die Länge immer durch 4 teilbar ist, kannst du den Code ja auch noch ein bisschen optimieren, indem du es PByte in PInteger änderst:

Delphi-Quellcode:

procedure XorMemBlock(Source1, Source2, Destination: PInteger; Count: Integer);
begin
  while Count > 0 do
  begin
    Destination^ := Source1^ xor Source2^;
    inc(Source1);
    inc(Source2);
    inc(Destination);
    dec(Count);
  end;
end;

Wie viel das in der Praxis ausmacht, kann ich nicht sagen, aber theoretisch sollte es schneller sein, weil der Prozessor eh immer 4 Bytes auf einmal lädt und somit weniger oft Daten aus dem RAM holen muss, wenn man immer in Vierer-Schritten arbeitet, als wenn man sich byteweise durcharbeitet.

Count musst du dann natürlich auch durch den Faktor 4 teilen.