Counting 1s in a Bit-Stream

[Torben]

Hello.

I want to count 1s in one byte of data in Assembler, but I dont get it work. Assembling the code is working, but the programs counting is wrong. Seems that the last bit is not counted. Here is my code:

.data
    intout db "Einser in EAX: ", 0
.code                             ; Tell MASM where the code starts
start:                              ; The CODE entry point to the program
    call main
    exit
main proc
    print OFFSET intout      ; achtung: print-makro verändert eax!
    xor ebx, ebx                ; clear ebx register
    mov eax, 00010111b          ; 8-Bit Daten
    mov ecx, 8                  ; Länge der Daten in Bit
    xor edx, edx                ; clear counter fuer einser
einser_zaehler:                 ; zaehlt 1er, die in eax enthalten sind
    clc
    bt eax, ecx                  ; if bit = 1 then carry flag = 1
    jnc not_a_one              ; jump if not Carry = 1
    inc edx                        ; If bit = 1 then increment edx
not_a_one:
    loop einser_zaehler        ; ecx = ecx-1 if ecx!=0 then loop again  
    print str$(edx)  
    ret
main endp
end start                          ; Tell MASM where the program ends

THX for all help!
Greetings from Germany

[dedndave]

it might be easier to just shift it out of EAX

Code Select Expand

        xor     edx,edx
        mov     ecx,8

loop_start:
        shr     eax,1
        adc     dl,dh
        dec     ecx
        jnz     loop_start

oh - willkommen auf dem forum  :U

[Torben]

Wow, that was fast!
Thank you very much!

[qWord]

willkommen auf dem forum :U

:naughty:

wilkommen im Forum

  :P

[dedndave]

my pleasure - that one was easy
i wish all the questions were as easy to answer   :P

well - i got that from google translate   :lol

[clive]

Personally I'd just use the POPCNT command, but as it looks like homework, the following is an interesting method to think about

Code Select Expand

    mov al,byte ptr [i]

    mov ah,al
    shr ah,1
    and ax,05555h
    add al,ah
    mov ah,al
    shr ah,2
    and ax,03333h
    add al,ah
    mov ah,al
    shr ah,4
    and ax,00F0Fh
    add al,ah

    mov byte ptr [j],al


[dedndave]

POPCNT is nice, if the CPU in use supports it   :bg

but, i like the "wiggle and jiggle" method - lol
(i am sure it has a better name)

[Torben]

Personally I'd just use the POPCNT command, but as it looks like homework, the following is an interesting method to think about

Code Select Expand

    mov al,byte ptr [i]

    mov ah,al
    shr ah,1
    and ax,05555h
    add al,ah
    mov ah,al
    shr ah,2
    and ax,03333h
    add al,ah
    mov ah,al
    shr ah,4
    and ax,00F0Fh
    add al,ah

    mov byte ptr [j],al


Thank you, too. Its good to know.

[clive]

but, i like the "wiggle and jiggle" method - lol (i am sure it has a better name)

Don't know, I coded it off my head from first principles, I've seen it used before, and it is consistent with a hardware construct I would use. Pretty sure AMD or Intel has it in an optimization paper. Uses the rule that any two 2**n binary digits added together will always fit in 2**(n+1), the new bit is a carry.

Full-Adder Pyramid, Sieve, Shake-n-Bake?

[dedndave]

lol - shake-n-bake - let's go with that one   :bg

i have seen something similar in a previous thread
i believe they were using it to reverse the bit order in a dword register, which was a little more complicated
but, the same principal was used
let me see if i can find it...

http://www.masm32.com/board/index.php?topic=12722.msg98224#msg98224
as i recall, Drizz found it in some other forum

MichaelW dubbed it "stir-fry" - lol
very close to your "shake-n-bake" moniker

[clive]

Here's one that cites AMD/Norbert

http://www.df.lth.se/~john_e/gems/gem002d.html

PDF Page 195 (Printed 179)
http://support.amd.com/us/Processor_TechDocs/25112.PDF

The 8-bit version was a quick hack interview answer, show's you're thinking.

[dedndave]

yes - Norbert Jaffa says he derived it from the K6 docs

[clive]

yes - Norbert Juffa says he derived it from the K6 docs

He worked/works for AMD, worked on floating point stuff among other things as I recall.

[jj2007]

Sorry, I couldn't resist :bg

mov eax, 10101010b

Code Select Expand

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
16      cycles for Clive, result=4
22      cycles for Dave, result=4
15      cycles for Jochen, result=4

16      cycles for Clive, result=4
22      cycles for Dave, result=4
16      cycles for Jochen, result=4

[clive]

Code Select Expand

Intel(R) Pentium(R) 4 CPU 3.00GHz (SSE3)
28      cycles for Clive, result=4
105     cycles for Dave, result=4
111     cycles for Jochen, result=4
41      cycles for Brute1, result=4
44      cycles for Brute2, result=4

28      cycles for Clive, result=4
103     cycles for Dave, result=4
113     cycles for Jochen, result=4
41      cycles for Brute1, result=4
41      cycles for Brute2, result=4


Code Select Expand

Intel(R) Atom(TM) CPU N450   @ 1.66GHz (SSE4)
14      cycles for Clive, result=4
46      cycles for Dave, result=4
115     cycles for Jochen, result=4
24      cycles for Brute1, result=4
26      cycles for Brute2, result=4

16      cycles for Clive, result=4
47      cycles for Dave, result=4
115     cycles for Jochen, result=4
24      cycles for Brute1, result=4
25      cycles for Brute2, result=4