16Bit Zahlen ohne Wrap-around addieren bzw. subtrahieren

pock schrieb:

TactX schrieb:

Ich würde ja eher auf intrinsics statt auf inline assembler setzen.

Wenn es im konkreten Fall wichtigeres als bestmögliche Ausführungsgeschwindigkeit gibt, kann man das durchaus tun.

Wie kommst du darauf, dass deine selbsgeschriebene Funktion zwangsläufig schneller ist als die des Herstellers?

pock schrieb:

Überzeugende Vorteile sehe ich allerdings nicht.

Sich nicht mit Assembler rumschlagen zu müssen ist für mich ein sehr überzeugender Vorteil.

pock

TactX schrieb:

Wie kommst du darauf, dass deine selbsgeschriebene Funktion zwangsläufig schneller ist als die des Herstellers?

Naja, nicht zwangsläufig. Ich habe mir nicht die Mühe gemacht, den asm-Output zu vergleichen. Aber da _mm_adds_pu16 pro Aufruf 4 Words addiert, meine Funktion aber beliebig viele (mit (potenziell) minimalem Overhead), unterstelle ich einfach mal, dass ein Optimizer das wohl nur schwerlich so effizient hinkriegen wird.

Den Beweis bleibe ich schuldig, so sehr interessiert es mich dann doch nicht.

Sich nicht mit Assembler rumschlagen zu müssen ist für mich ein sehr überzeugender Vorteil.

Das kann man sehen, wie man will. Ich "schlage" mich nicht mit Assembler rum, sondern setze es dort gewinnbringend ein, wo es sinnvoll ist.

Der OP wollte ein Beispiel, nun hat er eins. Wie er es dann konkret umsetzt, ist seine Sache. Die Intrinsics sind für ihn vorerst vielleicht besser geeignet, insofern gebe ich dir Recht.
Letztendlich sind es aber trotzdem nur Wrapper über MMX-Opcodes, der fertige Code wird also ohnehin nicht weit von Assembler entfernt sein.

mgarza

Hallo,
vielen dank für die super Routine :-), ich werde das heute Abend gleich mal ausprobieren. Wenn ich es schaffe, versuche ich auch mal die Funktion als "intrinsic" einzusetzen und die beiden gegenüber zu stellen.

Noch eine kleine Frage zum Verständnis (Für mich als Newbie):
Die Pointer "u16 *dest und u16* src" sind 4*16Bit, oder?

Lg und vielen Dank,
Matthias

pock

mgarza schrieb:

Noch eine kleine Frage zum Verständnis (Für mich als Newbie):
Die Pointer "u16 *dest und u16* src" sind 4*16Bit, oder?

Sie zeigen auf Speicherbereiche mit jeweils mindestens vier 16-bit Werten (unsigned short in VC++). len gibt an, wie viele 16-bit Werte sich mindestens in jedem Speicherbereich befinden, dieser Wert muss ein Vielfaches von 4 sein (wird durch das assert-Statement geprüft). Die Funktion ist darauf ausgelegt, viele Werte auf einmal zu addieren. Je größer du len setzen kannst, desto effizienter wird die Funktion. Am ineffizientesten wäre es, wenn du die Funktion immer nur mit len=4 aufrufst.

/edit: Beispiel

unsigned short a0[8] = { 0x1000, 0x2000, 0x3000, 0x4000, 0x5000, 0x6000, 0x7000, 0x8000 };
unsigned short a1[8] = { 0x2000, 0x4000, 0x6000, 0x8000, 0xa000, 0xc000, 0xe000, 0xffff };

addSaturated(a0, a1, 8);  // addiert 8 16-bit werte, überschreibt a0 mit dem ergebnis

mgarza

Hi,
kann ich das in das alte Programm durch hinzufügen eines dummys (um 4 additionen gleichzeitig zu haben) und durch die eine Zeile am Ende ersetzten?

typedef struct pRGB {
unsigned short r;
unsigned short g;
unsigned short b;
unsigned short xxx; //dummy
} uiRGB;

typedef uiRGB *Buf,*Org;

//old function used in the past
for(x=0;x<Width;x++){
for(y=0;y<Height;y++){
Buf[x+Width*y].r=addsaturated(Buf[x+Width*y].r,Org[x+Widthy].r);
Buf[x+Width*y].g=addsaturated(Buf[x+Width*y].g,Org[x+Widthy].g);
Buf[x+Width*y].b=addsaturated(Buf[x+Width*y].b,Org[x+Width*y].b);
}
}

//new function use MMX
addSaturated(Buf,Org,Width*Height*4);

Vielen Dank,
Matthias

pock

Bitte benutze die Code-Tags.

Das kannst du so machen, wenn dein Compiler die Daten korrekt ausrichtet. Du brauchst ein Aligment von höchstens 8 Bytes, damit das funktioniert. Das ist AFAIK standardmäßig schon so und sollte deshalb funktionieren.

Theoretisch brauchst du das Dummyelement nicht, wenn z. B. Höhe und Breite konstant sind und die Gesamtgröße "zufällig" sowieso schon ein Vielfaches von 4 ist. Wenn z.B. Width=640, Height=480, dann hast du 640*480*3 Words, die sich prima ohne Rest durch 4 teilen lassen. Dadurch sparst du 307200 unnütze Additionen.
Aber auch wenn das nicht so ist, könnte man unnütze Rechnerei verhindern, wenn man die Daten in 2 Brocken teilt; ein Brocken

len=(Width*Height*sizeof(BGR))>>2

erfüllt die Anforderungen und kann wie beschrieben abgearbeitet werden, die übrigen paar Werte

len=(Width*Height*sizeof(BGR))&3

können "von Hand" addiert werden. Das wäre dann immer noch ziemlich effizient.

Ich habe es allerdings nicht getestet und diesen Low-Level Kram schon länger nicht mehr gemacht. Unter Umständen liege ich falsch. Probier es doch einfach mal aus.

mgarza

Hi,
ich hab sicher gestellt, daß die Länge durch 4 teilbar ist. Aber leider stürtzt das Programm ständig ab.

045B17F5   emms
045B17F7   mov         ecx,dword ptr [ebp+10h]
045B17FA   mov         esi,dword ptr [ebp+0Ch]
045B17FD   mov         edi,dword ptr [ebp+8]
045B1800   shr         ecx,2
045B1803   movq        mm0,mmword ptr [edi]     <--------- Fehler hier
045B1806   movq        mm1,mmword ptr [esi]
045B1809   paddusw     mm0,mm1
045B180C   movq        mmword ptr [edi],mm0
045B180F   add         edi,8
045B1812   add         esi,8
045B1815   dec         ecx
045B1816   jne         045B1803

Programm:

typedef struct ssiBGR{
	unsigned short b;
	unsigned short g;
	unsigned short r;
} siBGR;

typedef siBGR *piBGR;
piBGR stack,dark,ibuf;

void addSaturated(unsigned short *dest, const unsigned short* src, unsigned long len)
{
    //assert((len&3)==0);            // muss durch 4 teilbar sein
    __asm
    {
            emms                   // mmx-register vorbereiten
            mov ecx, len
            mov esi, src
            mov edi, dest
            shr ecx, 2             // durch 4 teilen, wir bearbeiten qwords
        l0:
            movq mm0, [edi]        // dest[ecx*4] in mmx-register 0
            movq mm1, [esi]        // src[ecx*4] in mmx-register 1
            paddusw mm0, mm1       // packed add of unsigned saturated words, summe in mm0
            movq [edi], mm0        // summe in dest schreiben
            add edi, 8             // nächstes qword aus dest
            add esi, 8             // nächstes qword aus src
            dec ecx                // zähler verringern
            jnz l0                 // weiter kopieren, wenn werte übrig
            emms                   // mmx-register als unbenutzt markieren
    }
}

extern "C" __declspec( dllexport ) long OpenStack (long Wd,long Hg) {
  Width=Wd;
  Height=Hg;
  stack = (piBGR) malloc(Width*3*Height*2);
  ibuf = (piBGR) malloc(Width*3*Height*2);
  return 0;
}

extern "C" __declspec( dllexport ) long StackImage (void) {
  addSaturated((unsigned short*)stack,(unsigned short*)ibuf,Width*Height*6);
  return 0;
}

pock

Wie groß sind width und height?

mgarza

const int WIDTH = 1280;
const int HEIGHT = 1024;

mgarza

Hab ich evtl. etwas mit den Pointern falsch gemacht?

pock

Du übergibst addSaturated die Größe des Speichers, das ist aber nicht richtig. Die Funktion erwartet die Anzahl der zu bearbeitenden unsigned shorts.

Du kannst einfach die Zeile

shr ecx, 2

durch

shr ecx, 3

ersetzen, dann funktioniert es auch mit deiner Größenangabe.

/edit: Erklärung: "shr ecx, 2" teilt die Größenangabe durch 4, konvertiert also von word nach qword. "shr ecx, 3" teilt die Größenangabe durch 8, konvertiert also von octet nach qword

Btw, die Casts bei malloc kannst du dir sparen.

long OpenStack (long Wd,long Hg) {
  Width=Wd;
  Height=Hg;
  stack = malloc(Width*Height*sizeof(siBGR));
  ibuf = malloc(Width*Height*sizeof(siBGR));
  return 0;
}

Swordfish

Ich würd' die Anzahl der Berechnungen schon in unsigned shorts und nicht in sizeof( unsigned short ) angeben wollen müssen...

pock schrieb:

Btw, die Casts bei malloc kannst du dir sparen.

Immer wieder. Ich hab's auch erst hier im Forum gelernt ;). Stinkt förmlich nach FAQ...

Greetz, Swordfish

PS @ OP: Gewöhn Dir bitte intrinsics an.

mgarza

Du kannst einfach die Zeile

shr ecx, 2

durch

shr ecx, 3

ersetzen, dann funktioniert es auch mit deiner Größenangabe.

Super es funktioniert!!!!!!
Ich hab auch das Subtrahieren umgesetzt - perfekt. Genau so hab ich mir das vorgestellt. Die Routine ist super schnell!!!!

Ich hab noch zwei weitere Funktionen, die ich gern umsetzen würde:

for(x=0;x<Width;x++){
	     for(y=0;y<Height;y++){
			a=x+y*Width;
			ibuf[a].g=(unsigned short)buf[a].g;
			ibuf[a].r=(unsigned short)buf[a].r;
			ibuf[a].b=(unsigned short)buf[a].b;		  
		 }
	   }

Kann man diese Funktion mit unpack umsetzen?

for(x=startx;x<sizex+startx;x++){
	  for(y=starty;y<sizey+starty;y++){
		buf[x+(Height-y-1)*Width].g=limit(stack[x+y*Width].g);
		buf[x+(Height-y-1)*Width].r=limit(tack[x+y*Width].r);
		buf[x+(Height-y-1)*Width].b=limit(stack[x+y*Width].b);
	  }
  }

limit: limit to 0...255
Ich bin mir bei dem Teil nicht ganz sicher, ob man hier "packuswb" verwenden kann, da diese Funktion signed short erwartet?

Lg und vielen DANK!!!!!

pock

Du kennst ja nun das Prinzip, alles weitere kannst du dir sicher selbst erarbeiten

Wenn du den Assembler-Part nicht komplett verstehst und du nicht absolut optimale Performance brauchst, solltest du vielleicht die Routine mit Intrinsics in C implementieren. Damit kannst du dann nach Belieben experimentieren.

Noch ein genereller Performance-Tip: dieses Schleifenkonstrukt

for(x=0; x<w; x++)
    for(y=0; y<h; y++)
        buf[x+y*w] = ibuf[x+y*w];

ist performancetechnisch ungünstig.

1. Die Schleife über die Breite sollte generell immer die Innerste sein, um maximalen Vorteil aus Caching und Prefetching zu ziehen.

2. Wenn dein Buffer x*y Elemente hat und du alle Elemente anfassen musst, musst du nicht Zeilen/Spaltenweise über die Buffer laufen, sondern kannst das auch Elementweise tun. Das spart Multiplikationen.

3. Möglicherweise ist es schneller, wenn die Schleife rückwärts läuft. Ein Check auf 0 ist schneller als ein Check auf einen anderen Wert.

So umgeschrieben läuft obige Schleife erheblich schneller:

c = w*h;
foo = buf;
bar = ibuf;
for(i=c; i>0; i--)
    *foo++ = *bar++;

Das entspricht einem simplen memcpy, das Prinzip ist natürlich auch auf andere Operationen anwendbar.

mgarza

Hi,
vielen Dank für den Hinweis, ich werde Ihn umsetzen. Ich bin zwar nicht so vertraut mit ASM, aber der Startpunkt reicht mir um weiterzukommen.

Nochmal vielen Dank,
Matthias