Wednesday, September 25, 2013

Problem 47 - x86 assembly

Yesterday I wrote my first x86 assembly code for one of my cs classes, and after finishing the assignment, rather than being exhausted from the effort or frustration or anything else, I had a feeling of satisfaction, having found working in assembly somewhat fun (at least at the relatively small scales I am still working at). So, as not to let that fun end, I decided to use x86 assembly on a Project Euler problem, and, as luck would have it, the problem I was up to, problem 47, was one that was not particular hard (for me, at least) to write in assembly - no need for copious variables, arrays, or any other sort of high-level language features that I would not be able to deal with. I am starting to think that all the drudgery with esoteric and otherwise dumb languages that I have had to put up with in the last month has made me immune to frustrations with programming languages or having too many difficulties switching between modes of computation - after learning how to write whitespace well, assembly is hardly a challenge, even if imul is implemented in a really stupid manner. Anyway, without further ado, here is my code, which runs in about .6s (to see the answer, I call e47 and use printf from a C program - the extra linking, etc that would be required to do this without touching C seemed unnecessary).
    .text
    .globl  isPrime
    .type   isPrime,@function
isPrime:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    cmpl    $2,%ebx     # n < 2
    jl      finif       # return 0
    movl    %ebx,%eax   # temp = 2
    andl    $1,%eax     # temp&= 1
    cmpl    $0,%eax     # n % 2 == 0
    je      finic       # return n == 2
    movl    $3,%r12d    # i = 3
loop:
    movq    $0,%rdx     # clear rdx for mul
    movl    %r12d,%eax  # put i in eax for mul
    imull   %r12d       # eax = i * i
    cmpl    %ebx,%eax   # i * i <= n
    jg      overloop
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # edx = n % i
    cmpl    $0,%edx     # n % i == 0
    je      finif       # return 0
    addl    $2,%r12d    # i+=2
    jmp     loop
overloop:
    movq    $1,%rax     # return 1
    jmp     fini
finif:
    movq    $0,%rax     # return 0
    jmp     fini
finic:
    cmpl    $2,%ebx     # n == 2
    jne     finif
    movq    $1,%rax     # return 1
fini:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size   isPrime,.-isPrime

    .text
    .globl  pfc
    .type   pfc,@function
pfc:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    movl    $0,%r13d    # fc  = 0
    movl    $2,%r12d    # i = 2
loop2:
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # isPrime(n)
    cmpl    $1,%eax     # if true
    je      finish
    cmpl    $3,%r13d    # if fc is 3 and not prime, return false
    je      finishFalse
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # eax: n%i, edx: n/i
    cmpl    $0,%edx     # n%i == 0
    jne     overif
    movl    %eax,%ebx   # n /= i
    incl    %r13d       # fc++
divloop:                # perform extra divisions of the factor
    movq    $0,%rdx     # clear rdx for division
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # compute division again
    cmpl    $0,%edx     # n%i == 0
    jne     overdivloop
    movl    %eax,%ebx   # n /= i
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # we must recheck primality here
    cmpl    $1,%eax     # if isPrime
    je      finish
    cmpl    $1,%ebx     # if 1
    je      finish
    jmp     divloop
overdivloop:
overif:
    incl    %r12d       # i++
    jmp     loop2
overloop2:
finish:
    cmpl    $3,%r13d    # fc == 3
    je      finishTrue
finishFalse:
    movq    $0,%rax  
    jmp     veryend
finishTrue:
    movq    $1,%rax
veryend:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size pfc,.-pfc
    
    .text
    .globl  e47
    .type   e47,@function
e47:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    $210,%ebx   # N = 210 (lowest possible num)
    movl    $0,%r12d    # count = 0
loop3:
    movl    %ebx,%edi   # N is param 1
    call    pfc
    cmpl    $1,%eax     # pfc(N) == 1
    jne     elsepart
    incl    %r12d       # count++
    cmpl    $1,%r12d    # count == 1
    jne     overif2
    movl    %ebx,%r13d  # r13d = first in seq
overif2:
    cmpl    $4,%r12d    # count == 4
    je      thefinish   # we are done
    jmp     overif3
elsepart:
    movl    $0,%r12d    # clear the count
overif3:
    incl    %ebx
    jmp     loop3
thefinish:
    movl    %r13d,%eax
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    
    .size e47,.-e47

No comments:

Post a Comment