Verbesserungswürdiger Assembler Code???

camper schrieb:

mov     ecx, dword ptr [Feld]
        mov     edx, dword ptr [Feld+4]
        xor     eax, eax
        not     ecx
        test    edx, edx
        jnz     @1
        test    ecx, 20020800h
        jz      @exit
        test    ecx,    20820h
        jz      @exit
        test    ecx,    10204h
        jmp     @exit
@1:     not     edx
        test    edx, 8h
        jnz     @2
        test    edx, 208h
        jz      @3
        test    ecx, 20020000h
        jmp     @exit
@3:     test    ecx, 20000000h
        jmp     @exit
@2:     test    edx, 42h
        jnz     @exit
        test    ecx, 10000000h
@exit:  setz    eax, 1
        ret

wäre handgeschrieben. maximal 3 bedingte Sprünge je nach gewähltem Pfad.

das sieht doch schon deutlich besser aus
Das vorherige Inverteiren macht deutlich mehr sinn als and/cmp

Lüttmoor

Franz von und zu Assisi schrieb:

Nachtrag:
Da die eigentliche Funktion aus einigen Hundert solcher if-Abfragen besteht, wird es schwer, den Code von Hand anzupassen. Vllt. hat ja jemand eine elegante Lösung in C parat ...

Also ich kenne kein Spiel, das zu Ende ist, wenn bestimmte Bits gesetzt sind. Vielleicht solltest du einfach einen anderen Algorithmus nehmen, um das Ende des Spiels zu bestimmen.

volkard

Franz von und zu Assisi schrieb:

Da die eigentliche Funktion aus einigen Hundert solcher if-Abfragen besteht, wird es schwer, den Code von Hand anzupassen. Vllt. hat ja jemand eine elegante Lösung in C parat ...

Die werden doch was gemeinsam haben, was man abfragen kann. Zur Not baut man eine perfekte oder nur gute hashtable. hab ich noch nie gemacht. poste doch mal ein array mit den 100 den werten.

Naja, viel hat die Änderung leider nicht gebracht, weil der Compiler ziemlichen Blödsinn daraus macht, so ähnlich wie bei dir camper. Das sieht in etwa so aus:

@4:
	mov       eax,dword ptr [_Feld1]
	add       esp,-8
	not       eax
	mov       edx,dword ptr [_Feld1+4]
	mov       dword ptr [esp],eax
	not       edx
	mov       dword ptr [esp+4],edx
@5:
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,536870912
	and       edx,520
	cmp       edx,0
	jne       short @8
	cmp       eax,0
@8:
	je        @7
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,537001984
	and       edx,8
	cmp       edx,0
	jne       short @9
	cmp       eax,0
@9:
	je        short @7
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,537004032
	xor       edx,edx
	cmp       edx,0
	jne       short @10
	cmp       eax,0
.
.
.
.

Naja, muss ich mir Morgen dann noch ein paar Gedanken zu machen. Vllt. hat auch jemand eine Idee, wie ich dem Compiler beibringen kann, einen Assembler-Code ohne diese cmp/and zu erzeugen...

volkard

EDIT: Alles falsch! Du sucht ja nicht bestimmte Werte, sondern welche der vielen Bitmaskee paßt. Alles vergebens. Ich bin ja soo doof.

Hab ein Testprogramm geschieben

#include <iostream>
#include <windows.h>

using namespace std;

typedef unsigned long long u64;
typedef unsigned int u32;

bool test(u64 x) {
	u32 t=u32(x)^u32(x>>32);
	u32 y=(t*2175734977u)>>29;
	static u64 table[]={
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x10204ull,
		0x4210000000ull,
		0x10204ull,
		0x20820ull,
		0x20820000000ull,
	};
	return x==table[y];
}

u64 goodValues[]={
	0x20820000000ull,
	0x820020000ull,
	0x20020800ull,
	0x20820ull,
	0x10204ull,
	0x4210000000ull,
};

int main() {
	size_t const goodValuesSize=sizeof(goodValues)/sizeof(goodValues[0]);
	size_t const tableSizeBits=3;
	size_t const tableSize=1<<tableSizeBits;
	u64 table[tableSize];
	u32 const step=2654435761u;
	for (u32 a=step;a!=0;a+=step) {
		if (a%1048576==0)
			cout<<"checking "<<a<<'\n';
		bool seen[tableSize]={};
		for (size_t i=0;i!=goodValuesSize;++i) {
			u64 x=goodValues[i];
			u32 t=u32(x)^u32(x>>(32-tableSizeBits));
			u32 y=(t*a)>>29;
//			cout<<x<<' '<<y<<'\n';
//			Sleep(1000);
			if (seen[y])
				goto collission;
			table[y]=x;
			seen[y]=true;
		}
		cout<<"found\n";
		cout<<"\ty=(t*"<<a<<"u)>>"<<32-tableSizeBits<<";\n";
		cout<<hex;
		cout<<"\tstatic u64 table[]={\n";
		for (size_t i=0;i!=tableSize;++i) {
			if (seen[i])
				cout<<"\t\t0x"<<table[i]<<"ull,\n";
			else
				cout<<"\t\t0x"<<table[0]<<"ull,\n";
		}
		cout<<"\t};\n";
		break;
collission:
		;
	}
	cout<<test(1)<<'\n';
	return 0;
}

Es fand

bool test(u64 x) {
	u32 t=u32(x)^u32(x>>32);
	u32 y=(t*2175734977u)>>29;
	static u64 table[]={
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x10204ull,
		0x4210000000ull,
		0x10204ull,
		0x20820ull,
		0x20820000000ull,
	};
	return x==table[y];
}

Code aus dem Compilat von GCC kopiert:

LFE652:
	.text
	.p2align 4,,15
.globl __Z4testy
	.def	__Z4testy;	.scl	2;	.type	32;	.endef
__Z4testy:
LFB991:
	pushl	%ebp
LCFI2:
	movl	%esp, %ebp
LCFI3:
	movl	12(%ebp), %edx
	movl	8(%ebp), %ecx
	movl	%edx, %eax
	xorl	%ecx, %eax
	imull	$-2119232319, %eax, %eax
	shrl	$29, %eax
	xorl	__ZZ4testyE5table(,%eax,8), %ecx
	xorl	__ZZ4testyE5table+4(,%eax,8), %edx
	leave
	orl	%edx, %ecx
	sete	%al
	ret
LFE991:

nur ein MUL und kein bedingter Sprung.
Hunderte von Werten werden wohl eine kompliziertere Hash-Funktion als nur u32 t=u32(x)^u32(x>>32); u32 y=(t*2175734977u)>>29; brauchen, aber wer weiß, vielleicht nur wenige Takte schlimmer.

Wenns kein AMD ist, ist vielleicht

u32 y=(t*40004u)>>29;
	static u64 table[]={
		0x10204ull,
		0x20820ull,
		0x4210000000ull,
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x20820000000ull,
		0x10204ull,
	};

netter mit

__Z4testy:
LFB991:
	pushl	%ebp
LCFI2:
	movl	%esp, %ebp
LCFI3:
	pushl	%ebx
LCFI4:
	movl	8(%ebp), %ebx
	movl	12(%ebp), %ecx
	movl	%ecx, %eax
	xorl	%ebx, %eax
	leal	(%eax,%eax,4), %edx
	leal	(%edx,%edx,4), %edx
	leal	(%edx,%edx,4), %edx
	leal	(%edx,%edx,4), %edx
	sall	$4, %edx
	leal	(%edx,%eax), %eax
	sall	$2, %eax
	shrl	$29, %eax
	xorl	__ZZ4testyE5table(,%eax,8), %ebx
	xorl	__ZZ4testyE5table+4(,%eax,8), %ecx
	orl	%ecx, %ebx
	sete	%al
	popl	%ebx
	leave
	ret
LFE991:

Wow, Volkard, du sollst mir nicht das ganze Programm schreiben .Ich will auch noch was machen. Naja, das was ich jetzt mal versuche, sieht in etwa so aus(Hoffentlich ist das kein kompletter Blödsinn):

mov       eax,dword ptr [_Feld1]
	mov       edx,dword ptr [_Feld1+4]
	not       eax
	not       edx

	test      eax,536870912
	jnz       @7
	test      edx,520
	jz		  @exittrue

@7:
	test      eax,537001984
	jnz       @8
	test      edx,8
	jz		  @exittrue
@8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue

@11:
	test      eax,537001984
	jnz       @exitfalse
	test      edx,8
	jz		  @exittrue

Das entspräche diesem C-Code (Hoffe ich):

if(!(x & 0x20820000000i64 &&
			x & 0x820020000i64 &&
			x & 0x20020800i64 &&
			x & 0x20820i64 &&
			x & 0x10204i64 &&
			x & 0x4210000000i64)) return true;

volkard

Franz von und zu Assisi schrieb:

@8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue

Damit begehst DU meinen Fehler, fürchte ich, und Du testest nicht mehr, ob unter anderem diese 3 Bits gesetzt sind, sondern ob nur genau diese 3 Bits gesetzt sind.

volkard schrieb:

Franz von und zu Assisi schrieb:
@8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue
Damit begehst DU meinen Fehler, fürchte ich, und Du testest nicht mehr, ob unter anderem diese 3 Bits gesetzt sind, sondern ob nur genau diese 3 Bits gesetzt sind.

Ne, meine Lösung müsste richtig sein. Ich hab sie mit allen relevanten Spielstellungen getestet. Ich hab meinen Assembler-Code auch auf Laufzeit getestet, erstaunlicherweise ist der aber langsamer als der reine C-Code. Daher gehe ich davon aus, dass der Assembler-Code, den der Compiler ausspuckt, noch nicht optimiert ist, die Optimierung also zu einem späteren Zeitpunkt erfolgt. Daher macht eine Optimierung von Hand meiner Meinung nach keinen Sinn mehr (außer im C-Code), obwohl meine Lösung sicherlich noch nicht optimal ist.
Trotzdem hat Campers Idee

bool SpielBeenden1()
{
    i64 x = ~Feld1;
    return !( x & 0x20820000000i64 && x & 0x00820020000i64 && x & 0x00020020800i64 && x & 0x00000020820i64 && x & 0x00000010204i64 && x & 0x04210000000i64 );
}

einiges gebracht (5-10% Laufzeitvorteil). Und damit kann ich ganz gut leben. Meiner Meinung nach kann der Thread jetzt auch geschlossen werden.

Vielen Dank an alle Helfer

camper

volkard schrieb:

EDIT: Alles falsch! Du sucht ja nicht bestimmte Werte, sondern welche der vielen Bitmaskee paßt. Alles vergebens. Ich bin ja soo doof.

Der Ansatz ist vielleicht trotzdem nicht so doof. Jedenfalls die Faltung könnte brauchbar sein:
Wenn im echten Programm so wie hier nur ein Teil aller bits überhaupt an der Ergebnisfindung teilnimmt (einfach alle Masken ver-or-en), könnte man den Rest vergessen und aus einem 64bittigen Problem z.B. wie hier ein 12bittiges machen. Klein genug für eine lookup-table.

camper schrieb:

Der Ansatz ist vielleicht trotzdem nicht so doof. Jedenfalls die Faltung könnte brauchbar sein:
Wenn im echten Programm so wie hier nur ein Teil aller bits überhaupt an der Ergebnisfindung teilnimmt (einfach alle Masken ver-or-en), könnte man den Rest vergessen und aus einem 64bittigen Problem z.B. wie hier ein 12bittiges machen. Klein genug für eine lookup-table.

Alle diese Konstanten bestehen aus genau drei gesetzten Bits. Das mit der lookup-Tabelle habe ich aber nicht so ganz verstanden

camper

Franz von und zu Assisi schrieb:

Alle diese Konstanten bestehen aus genau drei gesetzten Bits. Das mit der lookup-Tabelle habe ich aber nicht so ganz verstanden

Wie viele Bits sind gesetzt, wenn alle Konstanten or-verknüpft werden?

camper schrieb:

Wie viele Bits sind gesetzt, wenn alle Konstanten or-verknüpft werden?

Das kann man so nicht ohne weiteres sagen, das hängt von den einzelnen Cases der Switch-Anweisung ab. Ich weiß jetzt nicht genau auf was du hinaus willst, ich poste einfach mal den ersten Teil meiner Funktion:

Boolean SpielBeenden1(void)
{
	const __int64 x = ~Feld1;
    switch(Hoehe[3])
    {
		case 0:
			if(!(x & 0x20820000000i64 &&
			x & 0x820020000i64 &&
			x & 0x20020800i64 &&
			x & 0x20820i64 &&
			x & 0x10204i64 &&
			x & 0x4210000000i64)) return true;
            break;
        case 1:
			if(!(x & 0x20008100i64 &&
			x & 0x10410i64 &&
			x & 0x10410000000i64 &&
			x & 0x2108000000i64 &&
			x & 0x108020000i64 &&
			x & 0x10010400i64 &&
			x & 0x8102i64 &&
			x & 0x410010000i64)) return true;
            break;
		case 2:
			if(!(x & 0x810004000i64 &&
			x & 0x4010800i64 &&
			x & 0x8208000000i64 &&
			x & 0x208008000i64 &&
			x & 0x8008200i64 &&
			x & 0x8208i64 &&
			x & 0x84010000i64 &&
			x & 0x10004080i64 &&
			x & 0x4081i64 &&
			x & 0x1084000000i64)) return true;
            break;
        case 3:
.
.
.
.
.
        case 5:
			if(!(x & 0x380000i64 &&
			x & 0x8102000000i64 &&
			x & 0x2108i64 &&
			x & 0x1041000000i64 &&
			x & 0x41001000i64 &&
			x & 0x1001040i64 &&
			x & 0x1041i64)) return true;
            break;
        default:
            break;
}

switch(Hoehe[4])
{
.
.
.
.
}

Darf man fragen wie das Spiel heißt?

Nobuo T

Der Fluch der Mumie...