7
\$\begingroup\$

To practice learning x64 AT&T Assembly (GAS), I implemented three solutions for Project Euler Problem 1 (find the sum of all the multiples of 3 or 5 below 1000).

The codes and a rough pseudocode sketch of each are shown below. I'd like some open-ended feedback (some more specific questions are at the bottom). To clarify, I am not asking to compare the following solutions (I'm aware of their algorithmic complexities), but they are all working pieces of Assembly that I would like feedback on.

Sorry for the poor code formatting, looks like 8-width tabs didn't carry over so well.

For all versions, compilation is simply gcc pe001.S -no-pie.

Version 1:

    .global main

    .text
main:
    xor %rbx, %rbx  # sum = 0

    xor %rax, %rax  # i = 0
sum3:
    add %rax, %rbx  # sum += i
    add $3, %rax    # i += 3
    cmp max, %rax   # if(rax < max)
    jl  sum3        # goto sum3

    xor %rax, %rax
sum5:
    add %rax, %rbx
    add $5, %rax
    cmp max, %rax
    jl  sum5

    xor %rax, %rax
sub15:
    sub %rax, %rbx
    add $15, %rax
    cmp max, %rax
    jl  sub15

    mov $fmt, %rdi  # printf(fmt, sum)
    mov %rbx, %rsi
    xor %rax, %rax  # clear this (for printf to work properly)
    call    printf
    
    xor %rax, %rax  # return(0)
    ret

fmt:    .asciz  "%d\n"
max:    .quad   1000

Version 1 Algorithm:

int sum = 0;
for(int i=0; i<1000; i+=3)
    if(!(i%3))
        sum += i;
for(int i=0; i<1000; i+=5)
    if(!(i%5))
        sum += i;
for(int i=0; i<1000; i+=15)
    if(!(i%15))
        sum -= i;

Version 2:

    .global main

    .text
main:
    mov $999, %rax  # i = 999
    xor %rbx, %rbx  # sum = 0
    
    mov $3, %rcx    # dividends = 3, 5
    mov $5, %r8

iter:
    push    %rax        # save divisor (i)
    xor %rdx, %rdx  # set rdx to 0
    div %rcx        # i/3 => rax remainder rdx
    pop %rax        # restore divisor (i)
    test    %rdx, %rdx  # check if remainder == 0
    jz  addts       # if divides evenly, add to sum

    push    %rax
    xor %rdx, %rdx
    div %r8
    pop %rax
    test    %rdx, %rdx
    jz  addts

deci:               # decrement i
    dec %rax
    jnz iter    

    mov $fmt, %rdi  # printf("%d\n", rbx)
    mov %rbx, %rsi
    xor %rax, %rax
    call    printf

    xor %rax, %rax
    ret

addts:              # add to sum
    add %rax, %rbx
    jmp deci
    
fmt:    .asciz  "%d\n"

Version 2 Algorithm:

int sum;
for(int i=0; i<1000; i++)
    if(!(i%3) || !(i%5))
        sum += i;

Version 3:

    .global main

    .text
sumtm:              # arithmetic SUM up To Max: int sum(int n)
    mov max, %rax   # i = floor(max/n) (result in rax)
    xor %rdx, %rdx
    div %rdi
    mov %rax, %rcx  # j = i+1
    inc %rcx
    imul    %rcx, %rax  # j *= i (= i*(i+1))
    shr $1, %rax    # j >>= 1 (= i*(i+1)/2)
    imul    %rdi, %rax  # j *= n (= n*i*(i+1)/2)
    ret         # return j

main:
    xor %rsi, %rsi  # sum = 0
    mov $3, %rdi
    call    sumtm
    add %rax, %rsi  # sum += sumtm(3)
    mov $5, %rdi
    call    sumtm
    add %rax, %rsi  # sum += sumtm(5)
    mov $15, %rdi
    call    sumtm
    sub %rax, %rsi  # sum -= sumtm(15)

    mov $fmt, %rdi  # printf("%d\n", sum)
    xor %rax, %rax  # needed for printf to work correctly
    call    printf
    
    xor %rax, %rax  # return 0
    ret

fmt:    .asciz  "%d\n"
max:    .quad   999

Version 3 Algorithm:

int sumtm(int n) {
    int i = floor(999/n);
    return n*i*(i+1)/2;
}
int sum = sumtm(3) + sumtm(5) - sumtm(15);

Questions:

  • Best practices for naming? Is there a common length limit for labels? (From the examples I've seen, it seems like variable names are often very terse and somewhat cryptic.) Common casing convention?
  • Choosing registers? This is the biggest trouble for me. The names are not very intuitive to me, and I'm not sure if there's a commonly-accepted set of guidelines on when to choose what. I was slightly influenced by caller-saved/callee-saved (e.g., use caller-saved registers in a function so as to not worry about pushing/popping it) and the use of explicit registers in certain operations (e.g., reuse %rax as divisor, reuse %rsi as second parameter for printf).
  • Is it common/good practice to follow the ABI's callee/caller-saved registers even in small code snippets like this, and when you have complete control over the code? I'd assume that this is much more important when writing a library, but how important is it for completely self-contained code?
  • Verbosity/comment density? Is this abnormal?
  • Overall efficiency/operator choice?

I'm very new to Assembly, so any other open-ended feedback is welcome.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Hello, I suggest you to change the title of your question to one describing the task you are implementing, because the actual one is too general and could be applied to several other questions here. You could also add the tag comparative-review to your question. \$\endgroup\$ – dariosicily Jul 25 '20 at 6:09
  • \$\begingroup\$ @dariosicily I updated the title to be a little more specific to the questions, but I don't think comparative-review would be a good fit. (I'm not asking for a comparison of these solutions; these are all samples of code that I'd like some advice on.) If that makes the scope of this question off-topic, please let me know. \$\endgroup\$ – Jonathan Lam Jul 25 '20 at 6:13
  • 3
    \$\begingroup\$ For me your question is on-topic, mine was just a suggestion that about the title I would add some reference to the euler project. \$\endgroup\$ – dariosicily Jul 25 '20 at 6:36
  • 1
    \$\begingroup\$ It looks like you want all 3 versions reviewed. That's ok, but do note it's quite possible answerers will only pick a subset. I see nothing wrong with this question. \$\endgroup\$ – Mast Jul 25 '20 at 8:45
  • \$\begingroup\$ x86-64 Assembly - Sum of multiples of 3 or 5 is the same problem with NASM, including answers suggesting down-counters instead of division, or unrolling to hide the repeating patterns of 3 and/or 5. (LCM of only 15) \$\endgroup\$ – Peter Cordes Dec 22 '20 at 1:42
3
\$\begingroup\$

Sorry for the poor code formatting, looks like 8-width tabs didn't carry over so well.

A well known problem on StackExchange...
I looked at your text in a separate editor and can vouch that your indentations are fine except on the lines that define the labels deci, addts, and sumtm.

Best practices for naming? Is there a common length limit for labels? (From the examples I've seen, it seems like variable names are often very terse and somewhat cryptic.) Common casing convention?

Important identifiers should always have descriptive names. In the second snippet e.g. you used deci and addts. I find both not very informative. Since you've written them on a separate line (and thus could not claim 'lack of space'), there's nothing that prevents you from writing the longer DecrementIndex and AddToTheSum. Much clearer!

Choosing registers? This is the biggest trouble for me. The names are not very intuitive to me, and I'm not sure if there's a commonly-accepted set of guidelines on when to choose what. I was slightly influenced by caller-saved/callee-saved (e.g., use caller-saved registers in a function so as to not worry about pushing/popping it) and the use of explicit registers in certain operations (e.g., reuse %rax as divisor, reuse %rsi as second parameter for printf).

Because you know that division imperatively uses the %rax register, you should perhaps not put i in %rax. Maybe use mov $999, %r9 # i = 999. No more need for the many push/pop's around these divisions.

The clever choice you've made in the third program to build the sum in %rsi (for use by printf), would equally work in the other programs.

Is it common/good practice to follow the ABI's callee/caller-saved registers even in small code snippets like this, and when you have complete control over the code? I'd assume that this is much more important when writing a library, but how important is it for completely self-contained code?

In case you're writing your own code, you can and should make the most of the registers that you have at your disposal. Also don't put too much thought in this. Use the registers that give you a comfortable feeling and if need be, the occasional push/pop around a library call won't kill you.

Verbosity/comment density? Is this abnormal?

Your commenting is good, but keep in mind that these 3 code snippets must stand on their own. So if you find it useful to write next comments in the first and third programs:

xor     %rax, %rax  # clear this (for printf to work properly)
call    printf
xor     %rax, %rax  # return(0)
ret

you should also mention them in the second program, so that a person that only sees the second program can benefit from your observation.

Overall efficiency/operator choice?

Intel advices against using the 64-bit division with the 128-bit dividend %rdx:%rax. Whenever possible use the 32-bit division with the 64-bit dividend %edx:%eax. In all of these little programs there's nothing that stands in the way of following this advice.

In fact most everything in these here programs can benefit from using the 32-bit registers instead of the 64-bit registers. The REX prefix will not get encoded and the CPU will zero the high dword automatically. Read about this in the Intel manual.

Lastly and FWIW, a 1-instruction replacement for mov %rax, %rcx inc %rcx is lea 1(%rax), %rcx.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your answer, it really helps clarify some ideas! Everything you said makes sense. The only thing I’m wondering is what you mean by the indentations for the labels not correct \$\endgroup\$ – Jonathan Lam Aug 3 '20 at 14:55
  • \$\begingroup\$ @JonathanLam The 3 lines where you define the labels deci, addts, and sumtm all have a tail comment that is 1 tab further to the right than all of the other comments that you've written. \$\endgroup\$ – Sep Roland Aug 9 '20 at 14:32

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.