Division in MMX

sade

Ich habe ein recht zeitaufwendiges(3 fps auf nem P4 3GHz) Plugin geschrieben dessen zeitkritische Teile ich in MMX schreiben wollte.
Ich bin nun so gut wie fertig nur gibt es am Ende eine Division und anscheinend stellt der MMX Befehlssatz keine Instruktionen dafür bereitet.
Auch multiply & shift funktioniert nicht, da Dividend und Divisor erst ab Runtime bekannt sind.

Nun meine Frage:
Gibt es noch eine Möglichkeit oder muss ich doch alles in SSE schreiben?

Edit: Ich habe die aktuellen Sourcen mal angehangen. Eine vorcompilierte .dll ist auch dabei.
Usage ist drb( int diameter, int threshold, bool use_asm)
defaults sind drb(6,30,true).

sade

Anscheinend kann man divss/divds immer nur auf einem double bzw quadword ausführen. Also muss ich sie 4mal aufrufen und dabei immer Daten zwischen mmx und xmm Registern hin und her bewegen.
Und nur weil Intel keine Integerdivisonen bereitstellen kann.:mad:

Kopernikus

Du könntest dir im prinzip ein LookupTable bauen, aber so wie ich das auf die Schnelle verstanden habe, weiß man über count nix genaueres.

Was macht das plugin genau (es ist schon spät)?

sade

es macht folgendes:
- betrachte alle Pixel im Quadrat um den zu filternden Pixel
- die Größe des Quadrats wird durch Diameter festgelegt
bei Diameter == 10 betrachtet man dann 100 Pixel
- wenn ein Pixel innerhalb low & high liegt, addiere es zu der Summe u.
inkrementiere count
- high/low sind dabei: der zu filternde Pixel +/- threshold
- der zu filterne Pixel ist dann (sum + count/2) / count

Das hilft vor allem bei extremen Chroma - Unterschieden, v.a. bei Regenbogenartefakten.

Ich könnte ein LUT verwenden, aber die Division ist nicht das langsame daran. Das Problem ist das ich die Division innerhalb v. Assembler machen muss.

In Assembler gibt es m.W. nur 3 Verschiedene Möglichkeiten f. eine Division:
1. FPU
2. div auf general purpose Registern
3. SSE(2)

MMX blockiert die FPU also fällt 1. schonmal weg.
2. fällt auch weg weil Datenverschiebungen zwischen eax u. mmx registern extrem langsam sind.
also bleibt nur SSE.

sade

So habe jetzt die Divison doch in C gemacht (Danke für den Tipp mit dem LUT).
Damit sind die MMX und SSE Versionen fertig und stürzen natürlich beide ab.:D Dass heißt die SSE Version kompiliert nicht einmal.

Habe da noch 2 Fragen vielleicht kennt sich ja jemand mit x86 und SSE aus:
1. mit

Code

mov eax, [x]mul ecx

müsste eax jetzt x*ecx enthalten oder?

2. laut den Intel docs kopiert movq ein quadword von Speicher in ein xmm Register. Jedoch bekomm ich bei diesem Code:

Code

long one = 0x0001000100010001;
__asm{ movq xmm0, [one]}

den Fehler: improper operand type.

Edit: aktuelle Sourcen im ersten Post

incredible

Viell. solltest du mal Kassandro im doom9 Forum oder ihn in seinem eigenen Forum darauf ansprechen, denn genau DA geibts sogar eine eigene Sektion, Welche sich mit MMX/SSE Filter-Programmierung auseinandersetzt:
http://videoprocessing.11.forumer.com/viewforum.php?…474647fa1351010

sade

Danke für den Hinweis, aber ich werde mich erstmal aufs debuggen der mmx Version konzentrieren. Wenn sich mein Account auf Doom9 freigeschaltet hat, und ich es bis dahin immernoch nicht geschafft habe werde ich dort mal nachfragen.

Edit:
Ich kann die SSE Version nun kompilieren, wenn ich anstatt

Code

movq xmm0, [x]

Code

movq mm0, [x]movq2dq xmm0, mm0

verwende. Crasht natürlich beides:D

Edit2: VS2003 verlangt einen expliziten Cast

Code

movq xmm0, qword ptr [x]

funktioniert

sade

Okay, entweder ich bin zu dumm oder es ist schon zu spät (oder beides ;))
aber wie allociere ich ein 2-dimensionales Array auf dem Heap?

Code

unsigned char lut[x][y] = new unsigned char lut[x][y];

funktioniert nicht.

Kopernikus

versuch mal

PHP

unsigned char lut[][] = new unsigned char lut[3][7];

sade

leider auch nicht:nein:

Zitat

drb.cpp(81) : error C2087: 'lut' : missing subscript
drb.cpp(81) : error C2440: 'initializing' : cannot convert from 'unsigned char *' to 'unsigned char [][1]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
drb.cpp(81) : error C2146: syntax error : missing ';' before identifier 'lut'

Kopernikus

Noch ein Versuch (C++ ist schon ne Weile her):

PHP

unsigned char* lut = new unsigned char[x][y];

Im Zweifelsfall (aber malloc und new zu mischen ist nicht gut):

PHP

unsigned char* lut = (unsigned char*) malloc(a*b*sizeof(unsigned char));

sade

Das zweite funktioniert, aber das ist ein eindimensionales Array, oder?

Edit:

Code

unsigned char (*lut)[7] = (unsigned char (*)[7]) malloc(3*7);

funktioniert

Kopernikus

Das ist egal. das malloc alloziert ein entsprechend großes stück Speicher, der Pointer drauf wird in lut gespeichert.

lut[x] ist dann eine kurzschreibweise für *(lut+x). lut[][] ist dann ein Array von arrays, da werden die Daten entsprechend hintereinander geschrieben. also für ein 3x4 großes Array sieht der Speicher dann so aus:

11 12 13 14 21 22 23 24 31 32 33 34

wobei 11 das element lut[1][1] bezeichnet.

Versuch mal nur ein eindimensionales Array mit new zu alloziieren, und dann zweidimensional zu indizeren. Das sollte der richtige Weg sein, C++ hat keine speziellen Konstruktoren für mehrdimensionale Arrays.

sade

Danke für die Erklärung.
Im Grunde brauch ich dann doch kein 2 dimensionales Array mehr, denn ich kann jedes
lut[x][y] mit *(lut + x*a + y) imitieren, wobei a die Länge der 2. Dimension ist

würde das dann funktionieren:

Code

unsigned char* lut = new unsigned char[255*pow(diameter,4);
...
if(!(dst[x] = *(lut + sum*pow(diameter,2) + count)) {
  dst[x] = sum/count;
  *(lut + sum*pow(diameter,2) + count) = dst[x];
}

Kopernikus

Nochmal eine Spur besser wäre es, das lut statisch und constant zu machen und von Hand in den Quelltext zu schreiben. Dann kann der Compiler u.U. noch irgendwelche Optimierungen anwenden, wenn die Konstanten schon zur Compilierzeit bekannt sind. Ist halt ein bisschen Schreibarbeit (aber das könnte man mit einem kurzen Programm automatisieren).

So kannst du nur mit Shifts und Multiplikationen auskommen, indem du (2^n)/i ausrechnest für i zwischen 1 und 144 (oder was auch immer die maximale Anzahl von Count ist), und dann die Division durch (erg*lut[i]) >> n ersetzt. n ist die genauigkeit, 8 sollte ausreichend sein. Vielleicht gibt es dann einige Fälle, in denen die Ergebnisse sich leicht unterscheiden.

In C kann man den Typ des Pointers auf (unsigned char[a][b]) casten, dann impliziert die schreibweise lut[x][y] die von dir genannte Schreibweise. C++ ist strenger getypt, wie gut das da funktioniert, weiß ich nicht.

sade

Danke für die Hilfe.
Ich werde n = 16 nehmen da mir 8 ein bisschen ungenau vorkommt.

Kopernikus

Warum so groß? ich seh nur ein 144 Einträge großes lut. sehr große luts sollte man auch nicht verwenden, die passen nicht in die schnellen caches, und das lohnt sich nicht, wenn nicht sehr komplizierte Berechnungen ersetzt werden.

Noch ein paar Anregungen für Optimierungen:

Die Makros MIN() und MAX() beim bestimmen von wend/wstart und hend/hstart könntest du weglassen, wenn du die Schleife ein bisschen aufdröselst, und die Ränder extra bearbeitest.

PHP

for(hi = hstart; hi <= hend; hi++) {					for(wi = wstart; wi <= wend; wi++) {						p = *(src + wi + hi*width);						if(p >= low && p <= high) {							sum += p;							count++;						}					}				}

könnte man die Sache etwas umschreiben:

PHP

unsigned char* ptr = src;				for(hi = hstart; hi <= hend; hi++) {					for(wi = wstart; wi <= wend; wi++) {						p = *ptr;						if(p >= low && p <= high) {							sum += p;							count++;						}						ptr++;					}					ptr += width;				}

Die Division hier:

PHP

*(dst + w + h*width) = (sum + count/2) / count;

ersetzen wir mit dem lookup:

PHP

*(dst + w + h*width) = ((sum + (count>>1)) *lut[count]) >>8;

Hier kann man den Pointer auch immer inkrementieren, anstatt ihn jedesmal neu auszurechnen.

Das ist mir jetzt spontan eingefallen. Die meisten Sachen sind nicht so arg ergiebig, aber wir befinden uns in einer sehr inneren Schleife, da macht das schon was aus. Je nachdem wieviel davon der Compiler schon intern macht.

sade

Zitat

Warum so groß? ich seh nur ein 144 Einträge großes lut. sehr große luts sollte man auch nicht verwenden, die passen nicht in die schnellen caches, und das lohnt sich nicht, wenn nicht sehr komplizierte Berechnungen ersetzt werden.

Das mit dem großen lut war ein Denkfehler von mir.

Zitat

Die Makros MIN() und MAX() beim bestimmen von wend/wstart und hend/hstart könntest du weglassen, wenn du die Schleife ein bisschen aufdröselst, und die Ränder extra bearbeitest.

Das war Absicht. Ich wollte erreichen das sich Quadrat den Rändern anpasst, dass z.B bei w = 2 und diameter = 10 das Quadrat von 0 - 10 geht. Wenn ich die Ränder extra bearbeite erstreckt sich das Quadrat von 2 -12. Dadurch ist es besser um den Pixel verteilt, Wieviel das ausmacht weiß ich nicht, aber so brauch ich auch weniger Code.

Den Rest schau ich mir mal an, Danke.

Edit: Also mit diesem lut:

Code

static const int lut8[100] = { 256, 128, 85, 64, 51, 42, 36, 32, 28, 25, 23, 21, 19,   18, 17, 16, 15, 14, 13, 12, 12, 11, 11, 10, 10, 9, 9,   9, 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 5,   5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,   4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,   3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,   2 };

und

Code

*(dst + w + h*width) = ((sum + (count>>1)) * lut8[count - 1]) >> 8;

bekomme ich nur buntes Rauschen.

sade

So ich hab die Vorschläge von Kopernikus mal übernommen, brachten aber keine Unterschiede (zumindest keine großen, AVSTimer zeigt nur ganzzahlige fps an). Nur das Lookup table funktioniert nicht. Stattdessen bekomme ich aber ein sehr schönes Aquarel.

Edit: jetzt weiß ich was falsch war: der/die/das table muss 11*11 und nicht 10*10 Einträge groß sein ('<' vs. '<='):ichdoof:

Eastermeyer

Darf man fragen , was das Plugin macht , wenn es so langsam ist ?

Jetzt mitmachen!