Solve leetcode climbing stairs problem in x86_64 assembly language

Can a leetcode question be answered in x86–64 assembly language?

Technically, no, since leetcode sadly 😞 does not offer the ability to code in assembly. Fortunately 🤞, inline assembly in C still allows us to code in assembly language.

So in this post, I will let you know how you can solve a problem in assembly language in leetcode. So let’s start 🥳.

Feel free to skip this section if you are already familiar with AT&T syntax for x86–64 assembly programming. A register’s width on an x86–64 CPU is 64 bits, meaning it can store 8 bytes of data. 64-bit CPUs include 16 general-purpose registers in addition to a few special registers. The general-purpose registers rdi, rsi, rax, rbx, rcx and rdx are a few that are highly helpful. Nearly every assembly code contains these registers.

Using the mov instruction, data can be transferred from memory to these registers. The add and sub instructions can be used to add and subtract values from the register, respectively. The push and pop operations can be used to add and remove values to and from the stack, respectively.

Please check out my repository on x86 assembly on GitHub for a detailed guide on x86 32-bit and 64-bit assembly programming.

So those were some x86_64 assembly fundamentals. Once you start working with code, it will all make more sense. Therefore, we will address the “climbing stairs” topic from the _leetcode _ “dynamic programming” question today. I will thus start by writing a C implementation of the code that we will use as a guide for writing the final assembly code.

#include <stdio.h>

int climbStairs_c(int n) {
    int pre_pre = 1, pre = 1, i = 2;
    while (i<=n) {
        int tmp = pre + pre_pre;
        pre_pre = pre;
        pre = tmp;
        i++;
    }
    return pre;
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d", climbStairs(n));
}

Now to write the corresponding C function in assembly we use “attribute((naked))” before the function definition to inform the compiler that the function body contains raw assembly code and “asm()” to encapsulate the assembly string.

Below is the assembly code corresponding to the C code

#include <stdio.h>

__attribute__((naked))
int climbStairs_c(int n) {
    __asm__(
        // the paramater n value is passed in register %rdi

        // int pre_pre = 1, pre = 1, i = 2;
        "movl $1, %eax;" // pre_pre = 1
        "movl $1, %ecx;" // pre = 1
        "movl $2, %edx;" // i = 2
    "l1:;"
        // while (i<=n) {
        "cmpl %edi, %edx;"
        "jg end;"  // on condition fail jump to end

        // int tmp = pre + pre_pre;
        "movl %eax, %esi;" // tmp = pre
        "addl %ecx, %esi;" // tmp += pre_pre
        // pre_pre = pre;
        "movl %eax, %ecx;"
        // pre = tmp;
        "movl %esi, %eax;"

        // i++;
        "incl %edx;"
        "jmp l1;"    // jump to loop start again

    "end:;"
        // return pre which is already in %rax register;
        "ret;"
    );
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d", climbStairs(n));
}

Now let's understand our code step by step:

• When a function (procedure) is called in C its param is passed in rdi the register.
• Now, we initialize some values using the mov instruction. Since an int is four bytes in size, we prefixed the instruction with l and used eax rather than rax, and the same for other registers, because we only want to read the register’s lower four bytes.
• Next, to use a loop we need a checkpoint to come back to. So we define a block named l1 to and use jmp instructions to come back to it.
• We use cmp instruction to compare values and in the next line we have used jl instruction to jump to the end of the condition meets otherwise continue to the next instructions.
• Once the loop exit and the program reach to end block we can return the answer using eax the register, Since the value is already stored in it we simply return by using ret instruction.

Hooray 🥳, If you reached here it means you have an interest in learning assembly programming. For this, I highly recommend you to check out my repository x86 assembly which I created with a lot of effort, There I have solved a lot of leetcode problems which uses some advanced concept like allocating memory using malloc function calling, nested loops, complex conditions, etc.

If you have any doubts or find any mistakes please let me know in the comments.

Thanks 🙏 for reading this blog, If you find it informative and useful please do like it and follow me for such awesome content.