News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

Counting 1s in a Bit-Stream

Started by Torben, November 10, 2010, 04:11:38 PM

Previous topic - Next topic

jj2007

It works fine, but it's not particularly fast, about 66 cycles on a P4:


mov eax, 10101010101010101010101010101010b
...
Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
1213    cycles for 100*MasmBasic, res=  16
6614    cycles for 100*Mirno, res=      16

1119    cycles for 100*MasmBasic, res=  16
6668    cycles for 100*Mirno, res=      16

dedndave

it needs a little test for the value EAX = 0   :P
as written, it will return a 1 count

jj2007

Quote from: dedndave on November 18, 2010, 03:28:30 PM
it needs a little test for the value EAX = 0   :P
as written, it will return a 1 count

Like this?
mov eax, 0 ; 10101010101010101010101010101010b
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif


The MasmBasic PopCount (here) works correctly. If only a handful of bits are set, Mirno's algo becomes competitive.

clive

Clearly not as effective at finding bits, but easier to explain to the professor

    mov eax, 0 ; 10101010101010101010101010101010b
    xor ecx, ecx
@@:
    shr    eax,1
    adc    ecx,0
    or    eax,eax
    jnz @B
It could be a random act of randomness. Those happen a lot as well.

dedndave

no - not like this - lol
mov eax, 0 ; 10101010101010101010101010101010b
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif


more like this
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif


moot point, really

jj2007

Quote from: dedndave on November 18, 2010, 06:00:37 PM
no - not like this - lol
mov eax, 0 ; 10101010101010101010101010101010b
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif


more like this
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif


moot point, really

I'm afraid I fail to see the difference, Dave :dazzled:

dedndave

mov eax, 0 ; 10101010101010101010101010101010b

i don't think you want this line
if you MOV EAX,0 - the answer will always be 0 
at least it will be nice and fast   :P

jj2007

Quote from: dedndave on November 18, 2010, 06:47:37 PM
mov eax, 0 ; 10101010101010101010101010101010b

i don't think you want this line
if you MOV EAX,0 - the answer will always be 0 
at least it will be nice and fast   :P

But that was the whole point: That Mirno's algo returned 1 for eax=0...

dedndave

i am giving you a hard time, my friend   :bg