Gesetzte Bits im Byte zählen

phreaking

Hast du auch schon im Forum gesucht?
Clock-Tabelle

lg, phreaking

Evil Azrael

nope, nur google. und bin nicht auf den begriff Clocks gekommen. Danke

mady

Original erstellt von Mr. n:
@mady: beim tabellenerstellen könntest du _viel_ *g* zeit sparen.

Naja ... mir ging's erstmal darum, ein Beispiel der Tab.Variante zu zeigen.

Normalerweise startet eine solche Initialisierung am Anfang eines Programms und damit ist das nicht so schlim, wenn's ein paar sek. länger dauert. Aber trotzdem bin ich auf Deinen Vorschlag gespannt, wie man das schneller machen kann!

phreaking

Ich denke, er meint damit, einfach die Tabelle fix in den Source hinein kompilieren, ich würde es nämlich auch so machen

lg, phreaking

Evil Azrael

dito. wird aber ein eklig langer maskierter string *g+

phreaking

Die Tabelle aus einer Datei in den Speicher zu holen, wäre auch möglich, aber ob das schneller ist...

lg, phreaking

Mr. N

beim hardcoding wirds doch auch aus ner datei in 'n speicher geladen *g* - meistens zumindest

Ich dachte aber eher an eine schnellere Methode, als die oben vorgestellte.... mir ist auch schon was eingefallen, wie man das besser machen kann ...

Aber dazu brauch' ich nen Compiler zum testen, den ich grad nicht hab....

Evil Azrael

www.cygwin.com *g*

void populate()
{
char *BitFeld; //nur definition, muss vorher generiert werden
char *felda,*feldb; //nur definition, sollten vorher geladen werden
short unterschiede=0; //char ist ein bit zu klein
char i; //reicht später für meine zwecke, schleife wird immer nur bis 64 gehen
for (i=0; i < 64;i++)
unterschiede += BitFeld[felda[i] ^ feldb[i]];
}

darf ich mal posten, was der GCC bei verschiedenen Optimierungsstufen draus gemacht hat? ich hab irgendwie das gefühl, das ab -O2 da nur noch mist rauskommt.

Mr. N

zeig her.

Evil Azrael

-O2

populate:
        pushl %ebp
        movl %esp,%ebp
        movl $63,%ecx
        .p2align 4,,7
.L6:
        decl %ecx
        jns .L6
        movl %ebp,%esp
        popl %ebp
        ret

hmm, so ohne XOR doch verdächtig *g*

-O

populate:
        pushl %ebp
        movl %esp,%ebp
        xorl %eax,%eax
        .p2align 4,,7
.L6:
        incl %eax
        cmpl $63,%eax
        jle .L6
        movl %ebp,%esp
        popl %ebp
        ret

wenigstens mal ein XOR, aber irgendwie sieht der code total komisch aus... kann jemand was dazu sagen?

Mr. N

kannste des mal in menschenlesbaren Code verwandeln *g*?

Evil Azrael

wenn ich den verstehen würde, dann vielleicht. aber ich bin eher ein assembler anfänger
schon die % vor den registern stört mich irgendwie.

eigentlich sieht der code doch ganz gut aus, nur der inhalt der schleife fehlt mir irgendwie
die % kommen von der AT&T syntax

-O2

populate:
pushl %ebp //
movl %esp,%ebp // Stack frame setzen
movl $63,%ecx // zähler setzen
.p2align 4,,7
.L6: // hier fehlt mir der inhalt
decl %ecx // zähler -1
jns .L6 // solange zähler > 0 loop zu .L6
movl %ebp,%esp // stack zurücksetzen
popl %ebp //
ret // return

hmm, so ohne XOR doch verdächtig *g*
-O

populate:
pushl %ebp
movl %esp,%ebp
xorl %eax,%eax // hier wird nur andersrum gezählt
.p2align 4,,7
.L6:
incl %eax
cmpl $63,%eax
jle .L6
movl %ebp,%esp
popl %ebp
ret

Evil Azrael

werd´s am WE mal ausprobieren. GCC wird bei so einfachem code wohl kaum mist machen.

TriPhoenix

Original erstellt von Evil Azrael:
werd´s am WE mal ausprobieren. GCC wird bei so einfachem code wohl kaum mist machen.

Ganz im Gegenteil, GCC ist ein Genie
ab O2 merkt GCC nämlich, dass du das Ergebnis garnicht weiter benutzt und schmeißt es einfach raus, weil wozu was berechnen, was keinen interessiert.

Hab den Code einfach mal Testweise so abgeändert, dass BitFeld nur 1en, felda nur einsen und feldb nur Nullen enthält. Desweiteren gibt die Funktion einen int zurück (nämlich unterschiede), der danach noch per printf ausgegeben wird. Und schon hast du einen Riesigen Klumpen asm-Code

Evil Azrael

der wäre dann auch interessanter.
ich hatte das auch so ausprobiert, dass ich den felder mit malloc speicher zugewiesen habe (später sollten dann über mmap die daten eingelesen werden (zum test)) , aber das hatte an der schleife nix geändert..
aber das es daran liegen könnte, dass das ergebnis nicht verwendet wird, daran hatte ich nicht gedacht. *kopf_gegen_die_wand_donnert*
wollte den code so gering wie möglich halten, um besser sehen zu können, was die schleife "kostet"
naja, geht auch so :

.L6:
        movb (%edx,%esi),%al
        xorb (%edx,%edi),%al
        movsbl %al,%eax
        incl %edx
        movsbw (%eax,%ebx),%ax
        addw %ax,%cx
        cmpl $63,%edx
        jle .L6

ist doch ok. dafür lohnt es sich doch echt nicht, da inline assembler zu verwenden und dafür die portabilität zu opfern. braver GCC!

ich glaube, bei großen datenmengen die verglichen werden müssen, könnte sich sogar lohnen, vorher eine tabelle mit 2^16 elementen zu generieren und die sich dann mit mmap (ich liebe diese funktion *g*) rein zu ziehen.

malfunction

Also Bits zählen würde ich ungefähr so machen (mal ganz ohne Optimierungen, Wert soll in EAX sein, Ergebnis in EDX):

xor edx,edx
   mov ecx,32
looping:
   ror eax,1
   jnc no_inc
   inc edx
no_inc:
   dec ecx
   jnz looping

Mr. N

lies dir mal den ganzen Thread durch. ab Seite 1.

-bg-

Das ist doch nahezu optimiert, allerdings auf Platz für selten ausgeführte BitCounts().
*ich glaube ich werde diesen thread noch richtig vermissen*

mfg
-bg-