Verbesserungswürdiger Assembler Code???

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