5
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I figured how the setnz instruction works but how is it faster? \$\endgroup\$ – AdHominem Jul 19 '16 at 21:08
  • \$\begingroup\$ It's faster because yours always loops 32 times. CWallach's exits as soon as it runs out of bits. For 255, that's 8 loops. \$\endgroup\$ – David Wohlferd Jul 19 '16 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.