Assembly with explanation and comparison with C
\n# Rationale\n\nI\'ve solved this LeetCode problem using inline assembly in C. My goal isn\'t to showcase complexity, but rather to challenge myself and deepen
\n# Rationale\n\nI\'ve solved this LeetCode problem using inline assembly in C. My goal isn\'t to showcase complexity, but rather to challenge myself and deepen my understanding of assembly language. \n\nAs a beginner in assembly, I welcome any improvements or comments on my code.\n\nAdditionally, I aim to share insights on practicing assembly on LeetCode.\n\n# Intuition\n\nIterate through all pair and check if `num1` is divisible by `(num2 * k)`\n\n# Approach\n\nMake two loops to iterate through all pairs. Use `mul` for multiplication and `div` for remainder. In this problem I have to use callee-saved register, so I have to push them to the stack. Use View [code](#assembly-code) comments for explanation.\n\n# Complexity\n- Time complexity: $$O(\\text{nums1Size}\\times\\text{nums2Size})$$. Fortunately, $$\\text{nums1Size}, \\text{nums2Size} \\le 50$$.\n- Space complexity: $$O(1)$$, I have to push 3 64bits register to stack.\n\n# Assembly Code\nThis mixed block shows the C code with inline assembly and the assembly code.  View [Notes about assembly](#notes-about-assembly) for notes about the syntax used. Moreover, It shows the assembly code without comment for [comparision with C](#comparison-with-c). If you want to test this code you can [run locally](#run-locally).\n\n```c [C (inline asm)]\nint numberOfPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {\n\tint ret;\n\t__asm__(\n".intel_syntax noprefix\\n"\n"\t## rdi: nums1\\n"\n"\t## esi -> sil: 1 <=nums1Size <= 50\\n"\n"\t## rdx: nums2 # will be replaced by r14\\n"\n"\t## ecx -> cl: 1 <= nums2Size <= 50\\n"\n"\t## r8 -> r8b: 1 <= k <= 50\\n"\n"\txor r9, r9\t\t\t\t\t# loop counter for nums1\\n"\n"\txor r10, r10\t\t\t\t# loop counter for nums2\\n"\n"\tpush r12\t\t\t\t\t# temporal value that will be restored\\n"\n"\tpush r13\t\t\t\t\t# Counter of good pairs (would be RAX\\n"\n"\t\t\t\t\t\t\t\t# but will be overwriten by div)\\n"\n"\txor r13, r13\\n"\n"\t\\n"\n"\tpush r14\t\t\t\t\t# store nums2 because rdx is volatile\\n"\n"\t\t\t\t\t\t\t\t# when using div\\n"\n"\tmov r14, rdx\\n"\n"\\n"\n"\\n"\n"loop1:\\n"\n"\tmov r11b, BYTE PTR[rdi+r9*4] # Get the current num1 in R11b\\n"\n"\txor r10b, r10b\t\t\t\t # Reset the loop counter for num2\\n"\n"loop2:\\n"\n"\tmov al, BYTE PTR[r14+r10*4]\t# Get the current num2 in AL\\n"\n"\tmul r8b\t\t\t\t\t\t# multiply by k. Then AX = k*num2\\n"\n"\tmov r12w, ax\t\t\t\t# R12w = k*num2\\n"\n"\\n"\n"\tmovzx ax, r11b\t\t\t\t# Set AX = num1\\n"\n"\txor dx, dx\t\t\t\t\t# Reset DX to 0 for division\\n"\n"\tdiv r12w\t\t\t\t\t# Divide DX:AX by R12w (num1/(k*num2))\\n"\n"\\n"\n"\ttest dx, dx\t\t\t\t\t# Check if remainder (DX) is 0\\n"\n"\tjnz not_divisor\\n"\n"\tinc r13w\t\t\t\t\t# if remainder is 0, increase R13\\n"\n"not_divisor:\\n"\n"\tinc r10b\t\t\t\t\t# loop2 update\\n"\n"\tcmp r10b, cl\t\t\t\t# loop2 condition\\n"\n"\tjl loop2\t\t\t\t\t# jump if loop2 condition\\n"\n"\t\\n"\n"\tinc r9b\t\t\t\t\t\t# loop1 update\\n"\n"\tcmp r9b, sil\t\t\t\t# loop2 condition\\n"\n"\tjl loop1\t\t\t\t\t# jump if jump1 condition\\n"\n"\\n"\n"\tmovzx eax, r13w\t\t\t\t# Assign R13w to EAX to return\\n"\n"epilog:\\n"\n"\tpop r14\\n"\n"\tpop r13\\n"\n"\tpop r12\\n"\n".att_syntax\\n"\n\t\t: "=a"(ret)\n\t);\n\treturn ret;\n}\n```\n```assembly [ASM (with comments)]\n\t.intel_syntax noprefix\n\t.globl  numberOfPairs\n\nnumberOfPairs:\n\t## rdi: nums1\n\t## esi -> sil: 1 <=nums1Size <= 50\n\t## rdx: nums2 ; will be replaced by r14\n\t## ecx -> cl: 1 <= nums2Size <= 50\n\t## r8 -> r8b: 1 <= k <= 50\n\txor r9, r9\t\t\t\t\t# loop counter for nums1\n\txor r10, r10\t\t\t\t# loop counter for nums2\n\tpush r12\t\t\t\t\t# temporal value that will be restored\n\tpush r13\t\t\t\t\t# Counter of good pairs (would be RAX\n\t\t\t\t\t\t\t\t# but will be overwriten by div)\n\txor r13, r13\n\t\n\tpush r14\t\t\t\t\t# store nums2 because rdx is volatile\n\t\t\t\t\t\t\t\t# when using div\n\tmov r14, rdx\n\n\nloop1:\n\tmov r11b, BYTE PTR[rdi+r9*4] # Get the current num1 in R11b\n\txor r10b, r10b\t\t\t\t # Reset the loop counter for num2\nloop2:\n\tmov al, BYTE PTR[r14+r10*4]\t# Get the current num2 in AL\n\tmul r8b\t\t\t\t\t\t# multiply by k. Then AX = k*num2\n\tmov r12w, ax\t\t\t\t# R12w = k*num2\n\n\tmovzx ax, r11b\t\t\t\t# Set AX = num1\n\txor dx, dx\t\t\t\t\t# Reset DX to 0 for division\n\tdiv r12w\t\t\t\t\t# Divide DX:AX by R12w (num1/(k*num2))\n\n\ttest dx, dx\t\t\t\t\t# Check if remainder (DX) is 0\n\tjnz not_divisor\n\tinc r13w\t\t\t\t\t# if remainder is 0, increase R13\nnot_divisor:\n\tinc r10b\t\t\t\t\t# loop2 update\n\tcmp r10b, cl\t\t\t\t# loop2 condition\n\tjl loop2\t\t\t\t\t# jump if loop2 condition\n\t\n\tinc r9b\t\t\t\t\t\t# loop1 update\n\tcmp r9b, sil\t\t\t\t# loop2 condition\n\tjl loop1\t\t\t\t\t# jump if jump1 condition\n\n\tmovzx eax, r13w\t\t\t\t# Assign R13w to EAX to return\nepilog:\n\tpop r14\n\tpop r13\n\tpop r12\n\tret\n```\n```assembly [ASM (without comments)]\n\t.intel_syntax noprefix\n\t.globl  numberOfPairs\n\nnumberOfPairs:\n\n\n\n\n\n\txor r9, r9\n\txor r10, r10\n\tpush r12\n\tpush r13\n\n\txor r13, r13\n\t\n\tpush r14\n\n\tmov r14, rdx\n\n\nloop1:\n\tmov r11b, BYTE PTR[rdi+r9*4]\n\txor r10b, r10b\nloop2:\n\tmov al, BYTE PTR[r14+r10*4]\n\tmul r8b\n\tmov r12w, ax\n\n\tmovzx ax, r11b\n\txor dx, dx\n\tdiv r12w\n\n\ttest dx, dx\n\tjnz not_divisor\n\tinc r13w\nnot_divisor:\n\tinc r10b\n\tcmp r10b, cl\n\tjl loop2\n\t\n\tinc r9b\n\tcmp r9b, sil\n\tjl loop1\n\n\tmovzx eax, r13w\nepilog:\n\tpop r14\n\tpop r13\n\tpop r12\n\tret\n```\n```assembly [ASM (without comments)]\n\t.intel_syntax noprefix\n\t.globl  numberOfPairs\nnumberOfPairs:\n\txor r9, r9\n\txor r10, r10\n\tpush r12\n\tpush r13\n\txor r13, r13\n\tpush r14\n\tmov r14, rdx\nloop1:\n\tmov r11b, BYTE PTR[rdi+r9*4]\n\txor r10b, r10b\nloop2:\n\tmov al, BYTE PTR[r14+r10*4]\n\tmul r8b\n\tmov r12w, ax\n\tmovzx ax, r11b\n\txor dx, dx\n\tdiv r12w\n\ttest dx, dx\n\tjnz not_divisor\n\tinc r13w\nnot_divisor:\n\tinc r10b\n\tcmp r10b, cl\n\tjl loop2\n\tinc r9b\n\tcmp r9b, sil\n\tjl loop1\n\tmovzx eax, r13w\nepilog:\n\tpop r14\n\tpop r13\n\tpop r12\n\tret\n```\n\n# Notes about assembly\n\n- This code is written Intel syntax using the `.intel_syntax noprefix` directive.\n- This code uses `#` for comments because GAS (GNU Assembler) uses this syntax and Leetcode uses GCC for compiling.\n- The reason I return from the "function" by jumping to the `.epilog` is that it\'s easier to remove everything after the `.epilog` to obtain the C code with inline assembly. I am aware that in assembly I can have multiple ret instructions in my "function", but in inline assembly I need to replace those `ret` instructions with a jump to the end of the inline assembly block.\n\n# Comparison with C\n\nThis my solution using C and the assembly code generated by `gcc -S`. I removed unnecesary lines with the following shell command. I also generated the code with optimization level `-O0`, `-O1`, `-O2`, `-Os`, `-Oz` for comparison.\n\n```bash\n$ gcc -O2 -fno-asynchronous-unwind-tables -masm=intel -S code.c -o- | \n    sed \'/^\\(.LCOLD\\|.LHOT\\|\\s*\\(\\.file\\|\\.type\\|\\.text\\|\\.p2align\\|\\.size\\|\\.ident\\|\\.section\\)\\)/d\'\n```\n\nNote that the C code may use `restrict`s, `const`s and type castings in order to get optimized code. Moreover, after the generated assembly code, I have also included my solution using assembly without comments for comparison.\n\n```C [-C code]\nint numberOfPairs(const int* restrict nums1, const char nums1Size, const int* restrict nums2, const char nums2Size, const char k) {\n\tunsigned short res = 0;\n\tfor (char i = 0; i < nums1Size; i++) {\n\t\tchar x = nums1[i];\n\t\tfor (char j = 0; j < nums2Size; j++) {\n\t\t\tif (x % (((char) nums2[j]) * k) == 0) {\n\t\t\t\tres++;\n\t\t\t}\n\t\t}\n\t}\n\treturn res;\n}\n```\n```assembly [-gcc -O0]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfPairs\nnumberOfPairs:\n\tpush\trbp\n\tmov\trbp, rsp\n\tmov\tQWORD PTR -24[rbp], rdi\n\tmov\tQWORD PTR -40[rbp], rdx\n\tmov\teax, ecx\n\tmov\tecx, r8d\n\tmov\tedx, esi\n\tmov\tBYTE PTR -28[rbp], dl\n\tmov\tBYTE PTR -32[rbp], al\n\tmov\teax, ecx\n\tmov\tBYTE PTR -44[rbp], al\n\tmov\tWORD PTR -2[rbp], 0\n\tmov\tBYTE PTR -5[rbp], 0\n\tjmp\t.L2\n.L6:\n\tmovsx\trax, BYTE PTR -5[rbp]\n\tlea\trdx, 0[0+rax*4]\n\tmov\trax, QWORD PTR -24[rbp]\n\tadd\trax, rdx\n\tmov\teax, DWORD PTR [rax]\n\tmov\tBYTE PTR -3[rbp], al\n\tmov\tBYTE PTR -4[rbp], 0\n\tjmp\t.L3\n.L5:\n\tmovsx\teax, BYTE PTR -3[rbp]\n\tmovsx\trdx, BYTE PTR -4[rbp]\n\tlea\trcx, 0[0+rdx*4]\n\tmov\trdx, QWORD PTR -40[rbp]\n\tadd\trdx, rcx\n\tmov\tedx, DWORD PTR [rdx]\n\tmovsx\tecx, dl\n\tmovsx\tedx, BYTE PTR -44[rbp]\n\tmov\tedi, edx\n\timul\tedi, ecx\n\tcdq\n\tidiv\tedi\n\tmov\tecx, edx\n\tmov\teax, ecx\n\ttest\teax, eax\n\tjne\t.L4\n\tmovzx\teax, WORD PTR -2[rbp]\n\tadd\teax, 1\n\tmov\tWORD PTR -2[rbp], ax\n.L4:\n\tmovzx\teax, BYTE PTR -4[rbp]\n\tadd\teax, 1\n\tmov\tBYTE PTR -4[rbp], al\n.L3:\n\tmovzx\teax, BYTE PTR -4[rbp]\n\tcmp\tal, BYTE PTR -32[rbp]\n\tjl\t.L5\n\tmovzx\teax, BYTE PTR -5[rbp]\n\tadd\teax, 1\n\tmov\tBYTE PTR -5[rbp], al\n.L2:\n\tmovzx\teax, BYTE PTR -5[rbp]\n\tcmp\tal, BYTE PTR -28[rbp]\n\tjl\t.L6\n\tmovzx\teax, WORD PTR -2[rbp]\n\tpop\trbp\n\tret\n```\n```assembly [-gcc -O1]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfPairs\nnumberOfPairs:\n\ttest\tsil, sil\n\tjle\t.L7\n\tpush\tr12\n\tpush\trbp\n\tpush\trbx\n\tmov\trbx, rdx\n\tmov\tebp, ecx\n\tmov\tr11, rdi\n\tmovsx\trsi, sil\n\tlea\tr12, [rdi+rsi*4]\n\tmovsx\trcx, cl\n\tlea\tr10, [rdx+rcx*4]\n\tmov\tr9d, 0\n\tmovsx\tr8d, r8b\n.L6:\n\tmovzx\tedi, BYTE PTR [r11]\n\ttest\tbpl, bpl\n\tjle\t.L3\n\tmov\trsi, rbx\n\tmovsx\tedi, dil\n.L5:\n\tmovsx\tecx, BYTE PTR [rsi]\n\timul\tecx, r8d\n\tmov\teax, edi\n\tcdq\n\tidiv\tecx\n\tcmp\tedx, 1\n\tadc\tr9w, 0\n\tadd\trsi, 4\n\tcmp\trsi, r10\n\tjne\t.L5\n.L3:\n\tadd\tr11, 4\n\tcmp\tr11, r12\n\tjne\t.L6\n\tmovzx\teax, r9w\n\tpop\trbx\n\tpop\trbp\n\tpop\tr12\n\tret\n.L7:\n\tmov\tr9d, 0\n\tmovzx\teax, r9w\n\tret\n```\n```assembly [-gcc -O2]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfPairs\nnumberOfPairs:\n\ttest\tsil, sil\n\tjle\t.L9\n\tmov\teax, ecx\n\tmovsx\trsi, sil\n\tmovsx\trcx, cl\n\tpush\trbp\n\tmov\tr10, rdx\n\tpush\trbx\n\tlea\trbp, [rdi+rsi*4]\n\tmov\trbx, rdi\n\tlea\tr11, [rdx+rcx*4]\n.L8:\n\ttest\tal, al\n\tjg\t.L17\n\tadd\trbx, 4\n\tcmp\trbx, rbp\n\tjne\t.L8\n\txor\tr9d, r9d\n.L6:\n\tmovzx\teax, r9w\n\tpop\trbx\n\tpop\trbp\n\tret\n.L17:\n\tmovsx\tedi, BYTE PTR [rbx]\n\txor\tr9d, r9d\n\tmovsx\tr8d, r8b\n.L7:\n\tmov\trsi, r10\n.L5:\n\tmovsx\tecx, BYTE PTR [rsi]\n\tmov\teax, edi\n\tcdq\n\timul\tecx, r8d\n\tidiv\tecx\n\tcmp\tedx, 1\n\tadc\tr9w, 0\n\tadd\trsi, 4\n\tcmp\tr11, rsi\n\tjne\t.L5\n\tadd\trbx, 4\n\tcmp\trbp, rbx\n\tje\t.L6\n\tmovsx\tedi, BYTE PTR [rbx]\n\tjmp\t.L7\n.L9:\n\txor\teax, eax\n\tret\n```\n```assembly [-gcc -Os]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfPairs\nnumberOfPairs:\n\tpush\tr12\n\tmov\tr10d, esi\n\tmov\tr11, rdi\n\txor\tesi, esi\n\tpush\trbp\n\tmovsx\tr8d, r8b\n\tmov\tebp, ecx\n\txor\tecx, ecx\n\tpush\trbx\n\tmov\trbx, rdx\n.L2:\n\tcmp\tr10b, sil\n\tjle\t.L9\n\tmovsx\tr12d, BYTE PTR [r11+rsi*4]\n\txor\tedi, edi\n.L3:\n\tcmp\tbpl, dil\n\tjle\t.L10\n\tmovsx\tr9d, BYTE PTR [rbx+rdi*4]\n\tmov\teax, r12d\n\tcdq\n\timul\tr9d, r8d\n\tidiv\tr9d\n\tcmp\tedx, 1\n\tadc\tcx, 0\n\tinc\trdi\n\tjmp\t.L3\n.L10:\n\tinc\trsi\n\tjmp\t.L2\n.L9:\n\tpop\trbx\n\tmovzx\teax, cx\n\tpop\trbp\n\tpop\tr12\n\tret\n```\n```assembly [-gcc -Oz]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfPairs\nnumberOfPairs:\n\tpush\tr12\n\tmov\tr10d, esi\n\tmov\tr11, rdi\n\txor\tesi, esi\n\tpush\trbp\n\tmovsx\tr8d, r8b\n\tmov\tebp, ecx\n\txor\tecx, ecx\n\tpush\trbx\n\tmov\trbx, rdx\n.L2:\n\tcmp\tr10b, sil\n\tjle\t.L9\n\tmovsx\tr12d, BYTE PTR [r11+rsi*4]\n\txor\tedi, edi\n.L3:\n\tcmp\tbpl, dil\n\tjle\t.L10\n\tmovsx\tr9d, BYTE PTR [rbx+rdi*4]\n\tmov\teax, r12d\n\tcdq\n\timul\tr9d, r8d\n\tidiv\tr9d\n\tcmp\tedx, 1\n\tadc\tcx, 0\n\tinc\trdi\n\tjmp\t.L3\n.L10:\n\tinc\trsi\n\tjmp\t.L2\n.L9:\n\tpop\trbx\n\tmovzx\teax, cx\n\tpop\trbp\n\tpop\tr12\n\tret\n```\n```assembly [-my ASM]\n\t.intel_syntax noprefix\n\t.globl  numberOfPairs\nnumberOfPairs:\n\txor r9, r9\n\txor r10, r10\n\tpush r12\n\tpush r13\n\txor r13, r13\n\tpush r14\n\tmov r14, rdx\nloop1:\n\tmov r11b, BYTE PTR[rdi+r9*4]\n\txor r10b, r10b\nloop2:\n\tmov al, BYTE PTR[r14+r10*4]\n\tmul r8b\n\tmov r12w, ax\n\tmovzx ax, r11b\n\txor dx, dx\n\tdiv r12w\n\ttest dx, dx\n\tjnz not_divisor\n\tinc r13w\nnot_divisor:\n\tinc r10b\n\tcmp r10b, cl\n\tjl loop2\n\tinc r9b\n\tcmp r9b, sil\n\tjl loop1\n\tmovzx eax, r13w\nepilog:\n\tpop r14\n\tpop r13\n\tpop r12\n\tret\n```\n\n\n# Run locally\n\nCompile locally the assembly code with GAS or the inline assembly with GCC.\n\n```bash\n$ as -o code.o assembly_code.s\n$ # or\n$ gcc -c -o code.o c_with_inline_assembly_code.c \n```\n\nThen, create a `main.c` file with the function prototype. Here you can include your tests.\n\n```c\n/* main.c */\n\nint numberOfPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k);\n\nint main(int argc, const char *argv[]) {\n    // Use numberOfPairs function\n    return 0;\n}\n```\n\nThen, compile `main.c` and link to create the executable\n\n```bash\n$ gcc main.c code.o -o main\n```\n\nFinally, execute\n\n```bash\n$ ./main\n```\n\n
['C']