A simple assembly program to count the number of ones in a register

Question

I made a simple assembly program to count the number of ones in a register. Since this is basically my first ever, I would like to hear what I can improve or if there are some major flaws in this one:

#PURPOSE:  Simple program which counts the number of ones in the edx register and returns them as a status code

#INPUT:    none

#OUTPUT:   Returns the number of ones as a status code.  This can be viewed
#          by typing
#
#          echo $?
#
#          after running the program

#VARIABLES:
#          %eax holds the carry flag bits and eventually the status code
#          %ebx holds the final return value
#          %ecx stores the loop index
#      %edx stores the register whose digits are examined
#      %edi accumulates the sum of ones

.section .data

.section .text
.globl _start
_start:

movl $255, %edx         # Initialize edx to some value
movl $0, %ecx       # Initialize ecx to zero
movl $0, %edi       # Initialize edi to zero
movl $0, %eax       # Initialize eax to zero

start_loop:
    cmpl $32, %ecx      # Loop runs over all 32 bits of the register
    jge loop_exit
    inc %ecx        # Increase the index variable
    shrl $1, %edx       # Right shift edx so the LSB moves into the carry-flag
    pushf           # Get the flags register
    pop %ax         # Put the least 16 bit of the flags into ax register
    and $01, %ax        # ... but store only the LSB
    add %ax, %di        # Now add the carry bit to the result
    jmp start_loop

loop_exit:
    movl $1, %eax       # We dont need eax any more at this point so we can use it for the syscall
    movl %edi, %ebx     # Return value will be edi
    int $0x80

Answer 1

Maybe you already know this and wanted to implement it yourself as an exercise nonetheless. Anyway, modern x86 CPUs have a special instruction for what you're trying to do.

From the Intel manual:

POPCNT — This instruction calculates of number of bits set to 1 in the second operand (source) and returns the count in the first operand (a destination register).

Note that “first” and “second” operand refers to Intel syntax where the operands are in the reverse order as in the AT&T syntax you are using.

Using this instruction, you wouldn't need a loop and your code would become trivial. I don't know whether it will also be faster. I've heard rumors that in some cases, well-written code can outperform special instructions implemented in microcode inside the CPU.

Answer 2

For some more advanced ideas, check out https://stackoverflow.com/a/109025/2189500.

But expanding on CWallach's code, how about:

mov edx, 255 ; setup edx with test value
xor eax, eax ; count

start_loop:
bt edx, 0 ; sets carry flag if bit 0 is set
adc al, 0 ; add with carry
shr edx, 1 ; drop off bit
jnz start_loop ; exit if edx is now 0

• xor is a smaller instruction for setting a register to zero.
• bt sets the carry flag for use in
• adc adds 0 to al, but also includes the contents of the carry flag.

And once you've got your head wrapped around that, how about:

mov edx, 255 ; setup edx with test value
xor eax, eax ; count

shr edx, 1 ; move rightmost bit to carry flag
start_loop:
adc al, 0 ; add with carry
shr edx, 1 ; move rightmost bit to carry flag
jnz start_loop ; exit if edx is now 0
adc al, 0 ; count last bit

This takes advantage of the fact that when shr shifts, it moves the shifted bit into the carry flag. And while there are more instructions overall (5 vs 6), there are fewer within the loop (4 vs 3).

Answer 3

Follow the ABI

This is optional when you’re writing code that will only be used inside your own assembly-language program. However, almost all real-world assembly-language consists of small routines called from a higher-level language. On the x86-64/x64 ABI, or the __msfastcall convention on 32-bit x86, the first two arguments would be passed in ecx and edx, and the return value would be in eax. This gets you a library routine you can call from other programs.

Your code needs to preserve the values of other registers, including ebx and edi, or you might get a bug when you return.

For the bespoke calling convention you use, you do a great job of documenting which registers you clobber, and for what.

Simplifying the Code

Other people have posted alternative implementations, but reviewing the code you actually wrote, you can simplify it a lot.

First, adc $0, %eax (I believe that’s the correct gas syntax) will add the value of the carry flag to eax, much more simply than pushing, popping and masking the flags register. Another very useful technique is clearing one register to zero (such as xor %edx, %edx) so you can adc %edx, %eax later.

You don’t need to use many registers at all. The algorithm really only needs the sum, and the residue of the input bits after shifting.

You can also simplify the loop condition, and stop looping when the shl instruction sets the zero flag. That is, when only zeroes remain in the source register, add the carry flag one last time, and return.

Finally, x86 assembly programs always clear registors by xor-ing them with themselves, especially %al or %eax. This instruction is slightly shorter than mov with an immediate operand.

This lends itself well to a do/while pattern, something like (WARNING: Untested!)

count:
    xorl %eax, %eax ; Return value: Initialize sum to 0
    movl %eax, %edx ; Not expected to preserve this: Set to 0.
    shrl $1, %ecx   ; Source operand
    jz count_exit   ; Loop condition: Are any remaining bits set?
count_loop:
    adcl %edx, %eax ; Add carry bit
    shrl $1, %ecx
    jnz count_loop  ; Loop condition: Are any remaining bits set?
count_exit:
    adcl %edx, %eax ; Add final carry bit
    ret

Please excuse me if I mix up gas and Intel syntax. This isn’t as clever as some of the other solutions, but shows how to refactor your approach to give a very tight inner loop. Initialization and exit code that only runs once is a low priority to optimize, and you normally want to focus on loops that run often on the critical path.

There are other approaches, such as unrolling the loop to eliminate the conditional jumps, storing the loop count in the cx register and using the loop instruction, or using setc or cmovc instrections.

Answer 4

While the program as written works and gets to the desired output, this is one of those cases where the selection of which algorithm to use can make a big impact in performance.

You can see this better by instead of focusing on the single given input 0xff looking at the range of possible inputs 0x0000_0000 through 0xffff_ffff

As you have done in your code using an algorithm to look at all 32bits one at a time will have 32 fixed iterations through the loop. This does have the benefit of a fixed runtime; however if one of your goals is to also reduce the runtime, it can be sped up by exiting the looping process early once the register value reaches zero and it no longer has any set bits left to be counted, as seen in CWallach. Making this simple change means that all values less than 0x8000_0000, i.e. between 0x0000_0000 and 0x7fff_ffff, or about 50% would take less than 32 iterations.

In fact taking the iteration reduction one step further by using Brian Kernighan's Set Bit Algorithm pointed out by Sufian Latif, you can reduce the number of iterations to only iterate the loop once each per bit set.

mov edx,255  ; given a value to check
xor eax,eax  ; quick zero eax

start_loop:
   mov   ecx,edx    ; eg 0110
   jecxz loop_exit
   dec   ecx        ;    0101
   and   edx,ecx    ;    0100  n = n & (n -1) removes right most set-bit
   inc   eax        ; count the number of times you've removed bits
   jmp   start_loop
loop_exit:

Now all values with at most one unset bit will take less than the 32 iterations((2^32 -33) / 2^32, or basically 100%).

These reductions in iterations however come at the cost of the algorithm no longer having a fixed runtime. It turns out that there is yet another algorithm from https://stackoverflow.com/a/109025/2189500 as point out by David Wholferd which actually has both a fixed runtime and low iteration count. In fact four-ish iterations for the whole range 0x0000_0000 through 0xffff_ffff, which we can just unroll to squeeze yet a little bit more speed out of.

mov  edx,255 ; given a value to check

;push edx
mov  eax,edx
shr  edx,1
and  edx,0x5555_5555 ; nibble bitmask 0101
sub  eax,edx         ; sub instead of add eliminates the need for an extra mask on eax

mov  edx,eax
shr  edx,2
and  edx,0x3333_3333 ; nibble bitmask 0011
and  eax,0x3333_3333
add  eax,edx

mov  edx,eax
shr  edx,4
and  edx,0x0F0F_0F0F ; byte bitmask 0000_1111
and  eax,0x0F0F_0F0F
add  eax,edx

; Long division example in base 10
;       :1234
;     x :1111
;     --------
;       :1234
;      1:234
;     12:34
;  + 123:4
;  -----------                                      
;    137:0974
;   edx : eax     mul returns the upper half in edx, and the lower in eax
;        ^
;        | This position is 1 + 2 + 3 + 4

; Let's do that except in base 256, where carry isn't an issue
mov  edx,0x0101_0101 ; similar to 1111 from the example
mul  edx    ; sets the high order byte = x + (x<<8) + (x<<16) + (x<<24)
shr  eax,24 ; return count
;pop  edx

A couple other added benefits of this algorithm are: the set of operations( shr,add,and,mov,mul) are generic enough that most assembly languages will have them, and since it can be unrolled without jumps depending on the architecture could lend itself to pipelining.

Moreover one surprising(at least to me) aspect of this algorithm was that it did not take any more unrolled iterations to extend the input range out to 64-bit and beyond(definitely 128, probably 256-bit).

  mov  rdx, 0xFFFF_FFFF_FFFF_FFFF ; given 

  mov  rcx,0x5555_5555_5555_5555  ;       rax                     rdx
  mov  rax,rdx                    ;  0xFFFF_FFFF_FFFF_FFFF  0xFFFF_FFFF_FFFF_FFFF
  shr  rdx,1                      ;  0xFFFF_FFFF_FFFF_FFFF  0x7FFF_FFFF_FFFF_FFFF
  and  rdx,rcx                    ;  0xFFFF_FFFF_FFFF_FFFF  0x5555_5555_5555_5555
  sub  rax,rdx                    ;  0xAAAA_AAAA_AAAA_AAAA  0x5555_5555_5555_5555
  
  mov  rcx,0x3333_3333_3333_3333
  mov  rdx,rax                    ;  0xAAAA_AAAA_AAAA_AAAA  0xAAAA_AAAA_AAAA_AAAA
  shr  rdx,2                      ;  0xAAAA_AAAA_AAAA_AAAA  0x2AAA_AAAA_AAAA_AAAA
  and  rdx,rcx                    ;  0xAAAA_AAAA_AAAA_AAAA  0x2222_2222_2222_2222
  and  rax,rcx                    ;  0x2222_2222_2222_2222  0x2222_2222_2222_2222
  add  rax,rdx                    ;  0x4444_4444_4444_4444  0x2222_2222_2222_2222
  
  mov  rcx,0x0F0F_0F0F_0F0F_0F0F
  mov  rdx,rax                    ;  0x4444_4444_4444_4444  0x4444_4444_4444_4444
  shr  rdx,4                      ;  0x4444_4444_4444_4444  0x0444_4444_4444_4444
  and  rdx,rcx                    ;  0x4444_4444_4444_4444  0x0404_0404_0404_0404
  and  rax,rcx                    ;  0x0404_0404_0404_0404  0x0404_0404_0404_0404
  add  rax,rdx                    ;  0x0808_0808_0808_0808  0x0404_0404_0404_0404
  
  mov  rcx,0x0101_0101_0101_0101
  mul  rcx                        ;  0x4038_3028_2018_1008
  shr  rax,56                     ;  0x0000_0000_0000_0040

Comparing this algorithm to Brian's: Four bits set could possibly go either way depending on the architecture and the trade off between the speed of mul vs jmp. Being generous and saying four bits is faster on Brian's algo, then there are C(32,4) + C(32,3) + C(32,2) + C(32,1) + 1 = 35960 + 4960 + 496 + 32 + 1 = 41449 input values between 0x0000_0000 and 0xffff_ffff where it would be faster, or ever so slightly under 0.001% of the whole 32-bit range. (note: 64-bit is much worse)

All of that aside, apparently the task of calculating the number of set bits was important enough where some architectures have given it its very own instruction as mentioned by 5gon12eder.

mov edx,255    ; given a value to check

popcnt eax,edx ; special case single-instruction

Answer 5

I'm used to writing my assembly the other way round, so hopefully this wont be confusing.

Loops

You're using ecx as a counting register which is good, however there's a built in instruction that allows you to perform loops. So, rather than you having to do this:

start_loop:
    cmpl $32, %ecx      # Loop runs over all 32 bits of the register
    jge loop_exit
    inc %ecx        # Increase the index variable

    # body of code

    jmp start_loop
loop_exit:

You can simplify it to:

    mov ecx, 32  # I think this is movl $32, %ecx with the assembly you're doing

start_loop:

    # body of code

    loop start_loop

You load ecx with the number of times you want to run the loop, then the loop instruction basically, decrements ecx and jumps if the result isn't zero.

Testing bits

Your approach to testing bits works, but it's rather long winded having to push them onto the stack and pop them off into a register. Instead, you can use the test instruction, which ands two operands together without destroying them and sets the flags accordingly. So, you can perform this combination as the main body of your loop:

    test edx, 1        ; check low order bit set
    jz bit_processed   ; if not set, skip increment
    inc edi
bit_processed:
    shr edx, 1         ; shift to right 1 bit

Putting it together

Combing the loop and test functionality, the code becomes:

    mov edx, 255 ; setup edx with test value
    mov ecx, 32  ; number of bits in register under test
    mov edi, 0   ; setup for response

start_loop:
    test edx, 1          ; check low order bit set
    jz bit_processed     ; if not set, don't count this bit
    inc edi              ; keep track of set bits
bit_processed:
    shr edx, 1           ; shift bits down
    loop start_loop      ; loop until we've completed
                         ; di contains number of bits.

As I've said, I'm used to the operands being the other way around (destination, source), but hopefully this points you in the right direction.

Answer 6

It can run faster with an early exit.

    mov edx, 255 ; setup edx with test value
    mov edi, 0   ; setup for response
    mov eax, 0

start_loop:
    test edx, 1          ; check low order bit set
    setnz al             ; if nz al = 1 else al = 0
    add edi, eax         ; sum it
    shr edx, 1           ; shift bits down
    jnz start_loop      ; loop until remainder is zero