The MASM Forum Archive 2004 to 2012
Welcome, Guest. Please login or register.
September 16, 2019, 03:18:54 PM

Login with username, password and session length
Search:     Advanced search
128553 Posts in 15254 Topics by 684 Members
Latest Member: mottt
* Home Help Search Login Register
+  The MASM Forum Archive 2004 to 2012
|-+  General Forums
| |-+  The Workshop
| | |-+  Counting 1s in a Bit-Stream
« previous next »
Pages: 1 2 [3] Print
Author Topic: Counting 1s in a Bit-Stream  (Read 11900 times)
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Counting 1s in a Bit-Stream
« Reply #30 on: November 18, 2010, 03:06:28 PM »

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

Code:
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

* PopCountMirno.zip (10.97 KB - downloaded 207 times.)
Logged

dedndave
Member
*****
Posts: 12523


Re: Counting 1s in a Bit-Stream
« Reply #31 on: November 18, 2010, 03:28:30 PM »

it needs a little test for the value EAX = 0   Tongue
as written, it will return a 1 count
Logged
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Counting 1s in a Bit-Stream
« Reply #32 on: November 18, 2010, 04:25:40 PM »

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

Like this?
Code:
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.
Logged

clive
Hardcore x86, ARM and MIPS toolsmith
Member
*****
Posts: 1230


Project Looking Glass. Following the white rabbit.


Re: Counting 1s in a Bit-Stream
« Reply #33 on: November 18, 2010, 05:12:26 PM »

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

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

It could be a random act of randomness. Those happen a lot as well.
dedndave
Member
*****
Posts: 12523


Re: Counting 1s in a Bit-Stream
« Reply #34 on: November 18, 2010, 06:00:37 PM »

no - not like this - lol
Code:
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:
xor ecx, ecx
test eax, eax
.if !Zero?
@@:
lea edx, [eax - 1]
inc ecx
and eax, edx
jnz @B
.endif

moot point, really
Logged
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Counting 1s in a Bit-Stream
« Reply #35 on: November 18, 2010, 06:31:59 PM »

no - not like this - lol
Code:
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:
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
Logged

dedndave
Member
*****
Posts: 12523


Re: Counting 1s in a Bit-Stream
« Reply #36 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   Tongue
Logged
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Counting 1s in a Bit-Stream
« Reply #37 on: November 18, 2010, 07:06:33 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   Tongue

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

dedndave
Member
*****
Posts: 12523


Re: Counting 1s in a Bit-Stream
« Reply #38 on: November 19, 2010, 03:48:43 AM »

i am giving you a hard time, my friend   BigGrin
Logged
Pages: 1 2 [3] Print 
« previous next »
Jump to:  

Powered by MySQL Powered by PHP The MASM Forum Archive 2004 to 2012 | Powered by SMF 1.0.12.
© 2001-2005, Lewis Media. All Rights Reserved.
Valid XHTML 1.0! Valid CSS!