I saw this video on Youtube the other day, where Low Level Learning used Assembly to solve a Leetcode problem. I decided to take the challenge up to solve at-least 10 leetcode problems using Assembly.
First of all, as he says in the video there is no Assembly option in Leetcode, so we need to improvise. I will do what he basically did, that is use Inline Assembly in C.
Also, I will not be using Intel Syntax, instead I am more comfortable using the AT&T version so I will do that.
The other thing that I will also change is, I will use Extended Assembly instead of Assembly.
Here are the 10 problems, these from the Array, Strings, Dynamic Programming problems.
1108. Defanging an IP Address
#include <stdio.h>
#include <string.h>
char * defangIPaddr(char * address){
int len_of_orig = strlen(address);
int len_of_new = strlen(address) + 7;
char* res = malloc(sizeof(char) * len_of_new);
res[len_of_new - 1] = '\0';
__asm__ __volatile__ (
"xor %%rcx, %%rcx;"
"xor %%rdx, %%rdx;"
"xor %%r9, %%r9;"
"mov $0, %%rcx;" // i the index for address
"mov $0, %%rdx;" // j the index for res
"loop%=:;"
"cmpl %1, %%ecx;"
"je end%=;"
"movb (%2, %%rcx, 1), %%r9b;"
"cmpb $46, %%r9b;"
"je is_dot%=;"
"movb %%r9b, (%0, %%rdx, 1);"
"inc %%rdx;"
"jmp continue_loop%=;"
"continue_loop%=:;"
"inc %%rcx;"
"jmp loop%=;"
"is_dot%=:;"
"movb $91, (%0, %%rdx, 1);"
"inc %%rdx;"
"movb $46, (%0, %%rdx, 1);"
"inc %%rdx;"
"movb $93, (%0, %%rdx, 1);"
"inc %%rdx;"
"jmp continue_loop%=;"
"end%=:;"
: "+r" (res)
: "r" (len_of_orig), "r" (address)
);
return res;
}1137. N-th Tribonacci Number
int tribonacci(int n){
int res = 0;
__asm__ __volatile__ (
"cmpl $0, %1;"
"je end_early_0%=;"
"cmp $1, %1;"
"je end_early_1%=;"
"movl $0, %%eax;"
"movl $1, %%ecx;"
"movl $1, %%edx;"
"movl $2, %%r8d;"
"loop%=:;"
"cmpl %%r8d, %1;"
"je end%=;"
"movl $0, %%r9d;"
"addl %%eax, %%r9d;"
"addl %%ecx, %%r9d;"
"addl %%edx, %%r9d;"
"movl %%ecx, %%eax;"
"movl %%edx, %%ecx;"
"movl %%r9d, %%edx;"
"incl %%r8d;"
"jmp loop%=;"
"end%=:;"
"movl %%edx, %0;"
"jmp last%=;"
"end_early_0%=:;"
"movl $0, %0;"
"jmp last%=;"
"end_early_1%=:;"
"movl $1, %0;"
"jmp last%=;"
"last%=:"
: "+r" (res)
: "r" (n)
);
return res;
}771. Jewels and Stones
#include <string.h>
int numJewelsInStones(char* jewels, char* stones) {
int res = -0;
int len_of_jewels = strlen(jewels);
int len_of_stones = strlen(stones);
__asm__ __volatile__ (
"xor %%rax, %%rax;"
"xor %%rcx, %%rcx;"
"xor %%rdx, %%rdx;"
"xor %%r9, %%r9;"
"xor %%r10, %%r10;"
"loop_i%=:;"
"cmpl %%ecx, %1;"
"je end_loop_i%=;"
"movb (%2, %%rcx, 1), %%r9b;"
"inc %%rcx;"
"loop_j%=:;"
"cmpl %%edx, %3;"
"je end_loop_j%=;"
"movb (%4, %%rdx, 1), %%r10b;"
"inc %%rdx;"
"cmpb %%r9b, %%r10b;"
"je add_to_result%=;"
"jmp loop_j%=;"
"add_to_result%=:;"
"incl %%eax;"
"jmp loop_j%=;"
"end_loop_j%=:;"
"movl $0, %%edx;"
"jmp loop_i%=;"
"end_loop_i%=:;"
"movl %%eax, %0;"
: "+r" (res)
: "r" (len_of_jewels), "r" (jewels), "r" (len_of_stones), "r" (stones)
);
return res;
}70. Climbing Stairs
__attribute__((naked))
int climbStairs(int n) {
__asm__(
"movl $1, %eax;" // pre_pre = 1
"movl $1, %ecx;" // pre = 1
"movl $2, %edx;" // res = 2
"loop:;" // while res > n
"cmpl %edi, %edx;"
"jg end;"
"movl %eax, %esi;" // tmp = pre_pre
"addl %ecx, %esi;" // tmp += pre
"movl %eax, %ecx;" // pre_pre = pre
"movl %esi, %eax;" // pre = tmp
"incl %edx;"
"jmp loop;"
"end:;"
"ret;"
);
}509. Fibonacci Number
__attribute__((naked))
int fib(int n){
__asm__(
"cmpl $0, %edi;" // if EDI == 0 {
"je end_immediate;"
"movl $0, %ecx;" // ECX = 0; pre
"movl $1, %eax;" // EAX = 1; Res
"movl $2, %edx;" // EDX = 2; n
"loop:;"
"cmpl %edi, %edx;" // EDI = n
"jg end;" // while ebx <= edi {
"movl %eax, %esi;" // ESI = EAX; temp
"addl %ecx, %esi;" // ESI += ECX; temp
"movl %eax, %ecx;" // ECX = EAX; pre
"movl %esi, %eax;" // EAX = ESI; res
"incl %edx;"
"jmp loop;"
"end:;"
"ret;"
"end_immediate:;"
"movl $0, %eax;" // EAX = 0; res
"ret;"
);
}1470. Shuffle the Array
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* shuffle(int* nums, int numsSize, int n, int* returnSize){
int* res = malloc(sizeof(int) * numsSize);
__asm__ __volatile__(
"movl $0, %%r8d;"
"movl %%edx, %%r9d;"
"mov $0, %%r10;"
"loop_i%=:;"
"cmpl %%edx, %%r8d;"
"je end_loop_i%=;"
"movl (%%rcx, %%r8, 4), %%esi;"
"movl %%esi, (%%rax, %%r10, 4);"
"inc %%r10;"
"movl (%%rcx, %%r9, 4), %%esi;"
"movl %%esi, (%%rax, %%r10, 4);"
"inc %%r10;"
"inc %%r8d;"
"inc %%r9d;"
"jmp loop_i%=;"
"end_loop_i%=:;"
: "=a" (res)
: "a" (res), "c" (nums), "d" (n)
: "r8", "r9", "r10", "memory"
);
*returnSize = numsSize;
return res;
}2798. Number of Employees Who Met the Target
int numberOfEmployeesWhoMetTarget(int* hours, int hoursSize, int target){
int res = 0;
__asm__ __volatile__ (
"mov $0, %%r8d;"
"movl $0, %%eax;"
"loop%=:;"
"cmpl %%r8d, %2;"
"je end%=;"
"movl (%1, %%r8, 4), %%r9d;"
"inc %%r8;"
"cmpl %3, %%r9d;"
"jge accumulate%=;"
"jmp loop%=;"
"accumulate%=:;"
"incl %%eax;"
"jmp loop%=;"
"end%=:;"
"movl %%eax, %0;"
: "=r" (res)
: "r" (hours), "r" (hoursSize), "r" (target)
: "r8", "r9", "memory", "eax"
);
return res;
}3110. Score of a String
int scoreOfString(char* s) {
int res = 0;
__asm__ __volatile__(
"mov $0, %%rax;"
"mov %%rcx, %%r8;"
"mov $0, %%r11;"
"loop%=:;"
"movb 1(%%r8), %%r9b;"
"cmpb $0, %%r9b;"
"je end%=;"
"movb (%%r8), %%r10b;"
"subb $97, %%r9b;"
"subb $97, %%r10b;"
"cmpb %%r10b, %%r9b;"
"jg go_to_10_g_9%=;"
"subl %%r9d, %%r10d;"
"addl %%r10d, %%r11d;"
"inc %%r8;"
"jmp loop%=;"
"go_to_10_g_9%=:;"
"subl %%r10d, %%r9d;"
"addl %%r9d, %%r11d;"
"inc %%r8;"
"jmp loop%=;"
"end%=:;"
"movl %%r11d, %%eax;"
: "+a" (res)
: "c" (s)
: "r8", "r9", "r10", "r11", "memory"
);
return res;
}121. Best Time to Buy and Sell Stock
int maxProfit(int* prices, int pricesSize) {
int res = 0;
__asm__ __volatile__(
"mov $0, %%r8;"
"mov (%%rcx), %%r10d;"
"mov $0, %%r11;"
"loop_i%=:;"
"cmpl %%edx, %%r8d;"
"je end%=;"
"movl (%%rcx, %%r8, 4), %%esi;"
"inc %%r8;"
"cmpl %%r10d, %%esi;"
"jl min_price_so_far%=;"
"max_profit_so_far%=:;"
"subl %%r10d, %%esi;"
"cmpl %%r11d, %%esi;"
"jg note_max%=;"
"jmp loop_i%=;"
"min_price_so_far%=:;"
"movl %%esi, %%r10d;"
"jmp max_profit_so_far%=;"
"note_max%=:;"
"movl %%esi, %%r11d;"
"jmp loop_i%=;"
"end%=:;"
"movl %%r11d, %%eax;"
: "=a" (res)
: "c" (prices), "d" (pricesSize)
: "r8", "r9", "r10", "r11", "esi", "edi", "memory"
);
return res;
}1929. Concatenation of Array
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getConcatenation(int* nums, int numsSize, int* returnSize) {
int* res = malloc(sizeof(int) * 2 * numsSize);
__asm__ __volatile__ (
"mov $0, %%r8;"
"mov $0, %%r9;"
"movl %%edx, %%r10d;"
"loop%=:;"
"cmpl %%r8d, %%edx;"
"je end_loop_first%=;"
"movl (%%rcx, %%r8, 4), %%r11d;"
"inc %%r8;"
"movl %%r11d, (%%rax, %%r9, 4);"
"inc %%r9;"
"movl %%r11d, (%%rax, %%r10, 4);"
"inc %%r10;"
"jmp loop%=;"
"end_loop_first%=:;"
: "+a" (res)
: "c" (nums), "d" (numsSize)
: "r8", "r9", "r10", "r11"
);
*returnSize = 2 * numsSize;
return res;
}Conclusion
Leetcode is a great place to hone your programming skills in almost any programming language possible. If you want to see the video from Low Level Learning, here you go:
