Euler's Totient Function in x86 assembly (MASM)

Question

My task was to implement Euler's totient function, and I'm looking for any and all criticism.

.386 
.model flat, stdcall
.stack 4096

ExitProcess PROTO, dwExitCode:DWORD 

.code
;------------------------------------------------------------------------------
; _phi@4 (int x)
;
; Calculates Euler's totient function using the product formula.
;
; param:
  x     TEXTEQU <[ebp+8]>       ;integer argument
;
; Exit: The result is stored in eax
;------------------------------------------------------------------------------
_phi@4:
        push    ebp             ; setup stack, save regs
        mov     ebp, esp
        push    ebx
        push    ecx
        push    edx

        mov     ecx, x          ; init result as x

; Consider the prime factors of x and subtract their multiples
; from the result
        mov     ebx, 2          ; initialize loop counter p
L3:     mov     eax, ebx
        mul     ebx 
        cmp     DWORD PTR x, eax ; loop if( x >= p * p)
        jnge    endL3;

; Check if p is a prime factor
        cdq
        mov     eax, x
        div     ebx 
        cmp     edx, 0          ; if(x % p == 0)
        jne     noprime

;if yes, update x and result 
L2:     cdq 
        mov     eax, x
        div     ebx
        cmp     edx, 0          ; if(x % p == 0)
        jne     endL2
        mov     x  , eax        ; x /= p            
        jmp     L2
endL2:
        cdq
        mov     eax, ecx
        div     ebx
        sub     ecx, eax        ;result -= result / p
noprime:    
        inc     ebx 
        jmp     L3
endL3:      

; If x has a prime factor greater than sqrt(x)
        cmp     DWORD PTR x, 1
        jle     finish
        cdq
        mov     eax, ecx
        div     DWORD PTR x
        sub     ecx, eax
finish:
        mov     eax, ecx

        pop     edx
        pop     ecx
        pop     ebx
        pop     ebp
        ret     4

main:
        push    100
        call    _phi@4
        INVOKE  ExitProcess, 0

        END     main

Is there any way I can make the code more efficient? - possibly with fewer instructions? Also, I'm looking for pointers on style. Is the code readable?

Answer 1

You're not using cdq properly. cdq sign extends EAX into EDX usually in preparation for an idiv (signed division) instruction. However, you're using div (unsigned division), so instead of using cdq (which can potentially fill EDX with 0xFFFFFFFF), you should zero out that register instead. If you were doing an idiv, though, the cdq is in the wrong place since it needs to come after loading data into EAX. And there are a couple of places where you already know that EDX will be 0 so you don't need the instruction at all.

In place of cmp edx,0, you can use test edx,edx. It sets the zero and sign flags the same way but does so with a smaller instruction.

Your L2 loop can be shortened a bit. If EDX is zero (no remainder after the division), you already know that EDX is zero, so you don't need to zero it out, and that x is already in EAX. So you can loop back to the div instruction.

Answer 2

I don't see any reason to write this function in assembler. The effect is currently that you prevent the compiler from optimizing anything about the code since you are dictating every single machine instruction.

If you wrote the code in a high-level language, the compiler would be allowed to apply several optimizations that you probably never heard of. That would be my first try. Rewrite the code in C, C++, Go or a similar language and look at the generated machine code, at different optimization levels. Also try different compilers, such as GCC, Clang, Intel C++.