Counting 1s in a Bit-Stream

[jj2007]

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

Code Select Expand


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]

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

Like this?

Code Select Expand

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

Code Select Expand

    mov eax, 0 ; 10101010101010101010101010101010b
    xor ecx, ecx
@@:
    shr    eax,1
    adc    ecx,0
    or    eax,eax
    jnz @B


[dedndave]

no - not like this - lol

Code Select Expand

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

Code Select Expand

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

moot point, really

[jj2007]

no - not like this - lol

Code Select Expand

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

Code Select Expand

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]

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