Kleiner Coding-Contest

hustbaer

Helmut.Jakoby schrieb:

Wie können zwei gesetzte Bits verschieden sein?

4 und 8 haben je nur ein Bit gesetzt, aber nicht das selbe Bit.

EDIT: OK, zu langsam.

Marthog

Mit

a!=0 && (a & (a-1))==0

muesste man schnell ueberpruefen koennen, ob genau ein bit gesetzt ist (nur kurze Ueberlegung, bitte um Bestaetigung).
Dann muss man noch ueberpruefen, ob die integer verschieden sind. Da es bitwise gemacht wird, kann, koennte man es mit (a & b)==0 schneller machen. Ich bin mir nicht sicher, ob die Compileroptimierer das selber koennen.

Columbo

bitte um Bestaetigung

Ja, das funktioniert.

Die erste funktionierende Lösung die mir eingefallen ist:

unsigned u = 0b00000000000000000000000000000000,
	         v = 0b00000000000000010000000000000000;

	bool B = !(u & (u - 1))
	      && !(v & (v - 1))
	      && u != v
	      && u && v;

Ist das aber wirklich schon die effizienteste Lösung? Kann ich gar nicht fassen.

Marthog

Durch die Wahl geeigneter Befehle, kann der compiler noch viele der Berechnungen in einem Schritt erledigen. Z.B. kann er statt expliziter ueberpruefung, ob die Zahl 0 ist, auch nachschauen, ob es in der Subtraktion einen ueberlauf gab.

Ich komme auf 16 Assemblerbefehle, die meisten davon auch nur sehr schnelle Bitvergleiche.

; parameter1: eax, parameter2: ebx

mov ecx, eax
sub eax, 1
jo RET_FALSE		 ; jump if overflow
test eax, ecx      ; bitwise compare
jnz RET_FALSE	; jump if not zero

mov ecx, ebx
sub ecx, 1
jo RET_FALSE		 ; jump if overflow
test ebx, ecx
jnz RET_FALSE	; jump if not zero

test eax, ebx		; bitwise and
jnz RET_FALSE
mov eax, 1
retn

RET_FALSE:
	mov eax, 0
	retn

macht 38 bytes binary

Vielleicht bekommt man es durch anderen Befehl, andere Registerwahl oder andere Reihenfolge noch ein bisschen schneller, aber ich bezweifel, dass man wirklich weniger schafft.
Nur die vielen Spruenge stoeren vielleicht, wenn die Branch-Prediction falsch liegt.

Und wie kann man damit jetzt was hacken?

Thilo87

Und wie kann man damit jetzt was hacken?

In die Eingabeaufforderung eingeben.

hustbaer

@Marthog
Ich denke das erste sub eax, 1 sollte sub ecx, 1 heissen -- so wie im 2. Block halt auch.
Sonst vergleicht das test eax, ebx zum Schluss die falschen Werte.

Und wieso test eax, ebx zum Schluss und nicht cmp bzw. sub ? Ist test in so einem Fall schneller?

EDIT: Grammatik + Tippfehler.

hustbaer

ps: Compiler sind schlauer als Menschen

bool foo(unsigned u, unsigned v) {
    return !(u & (u - 1)) 
		&& !(v & (v - 1)) 
		&& u != v 
		&& u && v;
}

// EDIT: Unsinn. Mein misglückter Versuch den Trick den Marthog in seinem Assembler-Beispiel verwendet hat in C++ nachzubilden.
//       Mit dem Hintergedanken dass ein C++ Compiler dadurch vielleicht besseren Code erzeugen könnte.
//       Funktioniert aber eben nur wenn u und v beide >= 0 sind, d.h. das MSB nicht verwendet wird.
//       => Nicht weiter beachten.
bool bar(int u, int v) {
	int temp1 = u - 1;
	int temp2 = v - 1;

	return temp1 >= 0 && !(temp1 & u)    //EDIT: (temp1 & u) => !(temp1 & u)
		&& temp2 >= 0 && !(temp2 & v)    //EDIT: (temp2 & v) => !(temp2 & v)
		&& u != v;
}

GCC 4.9:

foo(unsigned int, unsigned int):
	leal	-1(%rdi), %edx
	xorl	%eax, %eax
	testl	%edi, %edx
	jne	.L2
	leal	-1(%rsi), %edx
	testl	%esi, %edx
	jne	.L2
	cmpl	%esi, %edi
	setne	%dl
	testl	%edi, %edi
	setne	%al
	andl	%edx, %eax
	testl	%esi, %esi
	setne	%dl
	andl	%edx, %eax
.L2:
	rep ret

bar(int, int):
	movl	%edi, %edx
	xorl	%eax, %eax
	subl	$1, %edx
	js	.L7
	leal	-1(%rsi), %ecx
	testl	%edi, %edx
	sete	%dl
	movl	%ecx, %eax
	notl	%eax
	shrl	$31, %eax
	andb	%dl, %al
	je	.L7
	testl	%esi, %ecx
	sete	%dl
	cmpl	%esi, %edi
	setne	%al
	andl	%edx, %eax
.L7:
	rep ret

Nur zwei bedingte Sprünge, booyah!

Clang 3.4.1

foo(unsigned int, unsigned int):                               # @foo(unsigned int, unsigned int)
	leal	-1(%rdi), %eax
	testl	%edi, %eax
	jne	.LBB0_3
	leal	-1(%rsi), %eax
	testl	%esi, %eax
	je	.LBB0_2
.LBB0_3:
	xorl	%eax, %eax
	ret
.LBB0_2:
	cmpl	%esi, %edi
	setne	%al
	testl	%edi, %edi
	setne	%cl
	andb	%al, %cl
	testl	%esi, %esi
	setne	%al
	andb	%cl, %al
	ret

bar(int, int):                               # @bar(int, int)
	testl	%edi, %edi
	jle	.LBB1_2
	leal	-1(%rsi), %eax
	leal	-1(%rdi), %ecx
	testl	%edi, %ecx
	sete	%cl
	testl	%esi, %esi
	setg	%dl
	andb	%cl, %dl
	testl	%esi, %eax
	sete	%cl
	andb	%dl, %cl
	cmpl	%esi, %edi
	setne	%al
	andb	%cl, %al
	ret
.LBB1_2:
	xorl	%eax, %eax
	ret

Nur zwei bedingte Sprünge bzw. bei bar sogar nur einer. BOOYAH!

ICC 13.0.1

L__routine_start__Z3foojj_0:
foo(unsigned int, unsigned int):
        lea       -1(%rdi), %eax                                #2.23
        testl     %eax, %edi                                    #2.23
        jne       ..B1.6        # Prob 50%                      #2.23
        lea       -1(%rsi), %eax                                #3.17
        testl     %eax, %esi                                    #3.17
        jne       ..B1.6        # Prob 50%                      #3.17
        cmpl      %esi, %edi                                    #4.11
        je        ..B1.6        # Prob 50%                      #4.11
        testl     %edi, %edi                                    #5.6
        je        ..B1.6        # Prob 50%                      #5.6
        movl      $1, %eax                                      #2.23
        testl     %esi, %esi                                    #2.23
        cmove     %esi, %eax                                    #2.23
        ret                                                     #2.23
..B1.6:                         # Preds ..B1.4 ..B1.1 ..B1.2 ..B1.3
        xorl      %eax, %eax                                    #2.23
        ret                                                     #2.23

L__routine_start__Z3barii_1:
bar(int, int):
        movl      %edi, %eax                                    #9.18
        decl      %eax                                          #9.18
        lea       -1(%rsi), %edx                                #10.18
        js        ..B2.6        # Prob 16%                      #12.18
        testl     %eax, %edi                                    #12.33
        jne       ..B2.6        # Prob 50%                      #12.33
        testl     %edx, %edx                                    #13.15
        js        ..B2.6        # Prob 16%                      #13.15
        testl     %edx, %esi                                    #13.30
        jne       ..B2.6        # Prob 50%                      #13.30
        movl      $1, %edx                                      #12.18
        xorl      %eax, %eax                                    #12.18
        cmpl      %esi, %edi                                    #12.18
        cmovne    %edx, %eax                                    #12.18
        ret                                                     #12.18
..B2.6:                         # Preds ..B2.4 ..B2.1 ..B2.2 ..B2.3
        xorl      %eax, %eax                                    #12.18
        ret                                                     #12.18

4 bedingte Sprünge. Hmpf.

ps: Wer die Seite nicht kennt: http://gcc.godbolt.org/
Sehr cooles Tool wenn man schnell mal den ASM Output verschiedener Compiler vergleichen will.

EDIT: Fehler in "bar" korrigiert, ASM Output entsprechend upgedated (die Anzahl der jcc hat sich dadurch nicht verändert).

ps2: bar funktioniert natürlich nur wenn das MSB Bit immer 0 ist. Fällt mir auch jetzt erst auf, manchmal steh ich ganz schön aufm Schlauch

EDIT: Kommentar über die (nicht vorhandene) Sinnhaftigkeit von "bar" hinzugefügt.

Marthog

hustbaer schrieb:

Ich denke das erste sub eax, 1 sollte sub ecx, 1 heissen -- so wie im 1. Block halt auch.
Sonst vergleicht das test eax, ebx zum Schluss die falschen Werte.

Und wieso test eax, ebx zum Schluss und nicht cmp bzw. sub ? Ist test schneller in so einem Fall schneller?

Beim ersten hast du recht.
cmp subtrahiert ja die Werte, verwirft das Ergebnis und setzt die flags. Test macht ein bitand, verwirft das Ergebnis und setzt die flags. Bitwise-and ist deutlich einfacher zu implementieren. Ich weiss nicht, ob test heute noch schneller ist, aber frueher hat man das immer so gemacht und Compiler uebersetzen heutzutage auch x==0 meistens mit test eax, eax statt mit cmp eax, 0.
In diesem Fall hat man nur zwei Moeglichkeiten, naemlich das bit ist an der gleichen Stelle (bitand ergibt nicht 0) und das bit ist verschoben (bitand ergibt 0) und man kann test problemlos einsetzen.

EDIT: Achja, der gute lea-Befehl. Mit dem uebertrumpfen mich die Compiler jedes Mal.

hustbaer

@Marthog
Dass man es verwenden kann hab ich schon gecheckt, bin ja ein Schlauer
Ich hätte dort halt vermutlich einfach cmp verwendet, weil ich es mit cmp einfacher zu verstehen finde was abgeht. Und daher hab' ich nachgefragt.

hustbaer

Und ich meinte natürlich "so wie im 2. Block halt auch". Aber du bist ja auch ein Schlauer und hast es trotzdem verstanden

Bitte ein Bit

Toller Hacker Contest.

Und morgen kommt der Wettbewerb "Wer schreibt zuerst ein kompilierbares Program".

WinAPI Forum lässt grüßen.

Mechanics

Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth. Und klein wahrscheinlich weil er noch ein Schüler ist/war.

Columbo

Mechanics schrieb:

Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth.

Völlig falsch.

Und klein wahrscheinlich weil er noch ein Schüler ist/war.

Ebenfalls völliger Unsinn.

Ich habe den Titel entsprechend angepasst... hier muss man wirklich das niedrigste Niveau voraussehen.

Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?

Ich verstehe denn code nicht kann ihn mir jemand kurz erklären?

bool foo(unsigned u, unsigned v) {
    return !(u & (u - 1)) // bitweise UND sagt einen doch ob u und u-1 beide ein bit an der gleiche position auf 1 gesetzt haben?
        && !(v & (v - 1)) // gleiche
        && u != v // u ist nicht gleich v
        && u && v; // das hier verstehe ich nicht :/
}

bool bar(int u, int v) {
    int temp1 = u - 1;
    int temp2 = v - 1;

    return temp1 >= 0 && !(temp1 & u)    //EDIT: (temp1 & u) => !(temp1 & u)
        && temp2 >= 0 && !(temp2 & v)    //EDIT: (temp2 & v) => !(temp2 & v)
        && u != v;
}

hustbaer

Ach, Leute...

http://www.catb.org/jargon/html/H/hacker.html

Mechanics

Arcoth schrieb:

Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?

Natürlich nicht. Sorry, ich konnte einfach nicht widerstehen.

hustbaer

theconflict schrieb:

Ich verstehe denn code nicht kann ihn mir jemand kurz erklären?

bool foo(unsigned u, unsigned v) {
    return !(u & (u - 1)) // bitweise UND sagt einen doch ob u und u-1 beide ein bit an der gleiche position auf 1 gesetzt haben?
        && !(v & (v - 1)) // gleiche
        && u != v // u ist nicht gleich v
        && u && v; // das hier verstehe ich nicht :/
}

(u & (u - 1))
Wenn du dir "u - 1" binär anguckst, wirst du feststellen, dass dabei das erste 1er Bit (=das mit dem niedrigsten Stellenwert) zu 0 geflippt wird, und alle 0er Bits davor werden zu 1 geflippt:

u           u - 1
--------------------
xxxxxxx1    xxxxxxx0
xxxxxx10    xxxxxx01
xxxxx100    xxxxx011
xxxx1000    xxxx0111

etc.
Wenn man jetzt die linke und rechte Seite bitweise verundet, dann kommt dabei raus:

u           u - 1       u & (u - 1)
-------------------------------------------
xxxxxxx1    xxxxxxx0    xxxxxxx0
xxxxxx10    xxxxxx01    xxxxxx00
xxxxx100    xxxxx011    xxxxx000
xxxx1000    xxxx0111    xxxx0000

D.h. u & (u - 1) setzt einfach das erste 1er Bit auf 0.

Und wenn das Ergebnis von "erstes 1er Bit auf 0 setzen" 0 ist, dann war vorher maximal ein Bit gesetzt.

D.h. !(u & (u - 1)) heisst: hat u genau ein 1er Bit oder ist u gleich 0?

Den "oder ist u gleich 0" Teil will man aber nicht, es sind ja nur Werte erwünscht die genau ein 1er Bit haben.
=> !(u & (u - 1)) && u

Das ganze dann nochmal für v , und dann noch den Test ob u und v ungleich sind drangehängt:

!(u & (u - 1))
&& u
&& !(v & (v - 1))
&& v
&& u != v

Etwas umsortiert:

!(u & (u - 1))
&& !(v & (v - 1))
&& u != v
&& u && v

Tadaaa.

Danke jetzt habe ich es verstanden :}

Aufbauend auf hustbaer's Ansatz komme ich auf folgendes:

bool foo2(unsigned u, unsigned v) { 
    return !(u & (u - 1)) 
    && !(v & (v - 1)) 
    && (u | v) != u
    && u;
}

So macht der Clang nur noch einen Sprung

Warum reicht es? Wenn das bitweise Oder von u und v wieder u ergibt, gilt entweder u == v oder v == 0. Es bleibt also zu überprüfen, ob u == 0 ist.