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\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 numberOfChild(int n, int k) {\n\tint ret;\n\t__asm__(\n".intel_syntax noprefix\\n"\n"\t## DIL: n\\n"\n"\t## sil: k\\n"\n"\tmov dl, 1\t\t\t\t\t# CL = 1 if ball going right, else -1\\n"\n"\txor eax, eax\t\t\t\t# AL will be the current position\\n"\n"\tdec dil\t\t\t\t\t\t# DIL = n-1\\n"\n"loop:\\n"\n"\tcmp al, dil\t\t\t\t\t# check if AL == n-1\\n"\n"\tjne not_rightmost\t\t\t# jump if AL != n-1\\n"\n"\tmov dl, -1\t\t\t\t\t# set direction to -1\\n"\n"not_rightmost:\\n"\n"\ttest al, al\t\t\t\t\t# check if AL == 0\\n"\n"\tjne not_leftmost\t\t\t# jump if AL != 0\\n"\n"\tmov dl, 1\t\t\t\t\t# set direction to 1\\n"\n"not_leftmost:\\n"\n"\tadd al, dl\t\t\t\t\t# pass the ball (update AL with DL)\\n"\n"\tdec sil\t\t\t\t\t\t# decrease the number of remain passes\\n"\n"\tjnz loop\t\t\t\t\t# come back to loop if remain passes\\n"\n"epilog:\t\\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\tnumberOfChild\n\t\nnumberOfChild:\n\t## DIL: n\n\t## sil: k\n\tmov dl, 1\t\t\t\t\t# CL = 1 if ball going right, else -1\n\txor eax, eax\t\t\t\t# AL will be the current position\n\tdec dil\t\t\t\t\t\t# DIL = n-1\nloop:\n\tcmp al, dil\t\t\t\t\t# check if AL == n-1\n\tjne not_rightmost\t\t\t# jump if AL != n-1\n\tmov dl, -1\t\t\t\t\t# set direction to -1\nnot_rightmost:\n\ttest al, al\t\t\t\t\t# check if AL == 0\n\tjne not_leftmost\t\t\t# jump if AL != 0\n\tmov dl, 1\t\t\t\t\t# set direction to 1\nnot_leftmost:\n\tadd al, dl\t\t\t\t\t# pass the ball (update AL with DL)\n\tdec sil\t\t\t\t\t\t# decrease the number of remain passes\n\tjnz loop\t\t\t\t\t# come back to loop if remain passes\nepilog:\t\n\tret\n```\n```assembly [ASM (without comments)]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\n\t\nnumberOfChild:\n\n\n\tmov dl, 1\n\txor eax, eax\n\tdec dil\nloop:\n\tcmp al, dil\n\tjne not_rightmost\n\tmov dl, -1\nnot_rightmost:\n\ttest al, al\n\tjne not_leftmost\n\tmov dl, 1\nnot_leftmost:\n\tadd al, dl\n\tdec sil\n\tjnz loop\nepilog:\t\n\tret\n```\n```assembly [ASM (without comments)]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmov dl, 1\n\txor eax, eax\n\tdec dil\nloop:\n\tcmp al, dil\n\tjne not_rightmost\n\tmov dl, -1\nnot_rightmost:\n\ttest al, al\n\tjne not_leftmost\n\tmov dl, 1\nnot_leftmost:\n\tadd al, dl\n\tdec sil\n\tjnz loop\nepilog:\t\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 numberOfChild(const char n, char k) {\n\tchar pos = 0;\n\tchar direction = 1;\n\tdo {\n\t\tif (pos == n-1) {\n\t\t\tdirection = -1;\n\t\t}\n\t\tif (pos == 0) {\n\t\t\tdirection = 1;\n\t\t}\n\t\tpos += direction;\n\t\tk--;\n\t} while (k != 0);\n\n\treturn pos;\n}\n```\n```assembly [-gcc -O0]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tpush\trbp\n\tmov\trbp, rsp\n\tmov\tedx, edi\n\tmov\teax, esi\n\tmov\tBYTE PTR -20[rbp], dl\n\tmov\tBYTE PTR -24[rbp], al\n\tmov\tBYTE PTR -2[rbp], 0\n\tmov\tBYTE PTR -1[rbp], 1\n.L4:\n\tmovsx\tedx, BYTE PTR -2[rbp]\n\tmovsx\teax, BYTE PTR -20[rbp]\n\tsub\teax, 1\n\tcmp\tedx, eax\n\tjne\t.L2\n\tmov\tBYTE PTR -1[rbp], -1\n.L2:\n\tcmp\tBYTE PTR -2[rbp], 0\n\tjne\t.L3\n\tmov\tBYTE PTR -1[rbp], 1\n.L3:\n\tmovzx\tedx, BYTE PTR -2[rbp]\n\tmovzx\teax, BYTE PTR -1[rbp]\n\tadd\teax, edx\n\tmov\tBYTE PTR -2[rbp], al\n\tmovzx\teax, BYTE PTR -24[rbp]\n\tsub\teax, 1\n\tmov\tBYTE PTR -24[rbp], al\n\tcmp\tBYTE PTR -24[rbp], 0\n\tjne\t.L4\n\tmovsx\teax, BYTE PTR -2[rbp]\n\tpop\trbp\n\tret\n```\n```assembly [-gcc -O1]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmov\tedx, 1\n\tmov\tecx, 0\n\tmovsx\tedi, dil\n\tsub\tedi, 1\n\tmov\tr10d, -1\n\tmov\tr9d, 1\n.L4:\n\tmovsx\teax, cl\n\tcmp\teax, edi\n\tcmove\tedx, r10d\n\ttest\tcl, cl\n\tcmove\tedx, r9d\n\tlea\teax, [rcx+rdx]\n\tmov\tecx, eax\n\tlea\tr8d, -1[rsi]\n\tmov\tesi, r8d\n\ttest\tr8b, r8b\n\tjne\t.L4\n\tmovsx\teax, al\n\tret\n```\n```assembly [-gcc -O2]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmovsx\tedi, dil\n\tmov\tedx, 1\n\txor\teax, eax\n\tmov\tr8d, -1\n\tsub\tedi, 1\n.L4:\n\tmovsx\tecx, al\n\tcmp\tecx, edi\n\tcmove\tedx, r8d\n\tmov\tecx, edx\n\ttest\tal, al\n\tjne\t.L3\n\tmov\tecx, 1\n\tmov\tedx, 1\n.L3:\n\tadd\teax, ecx\n\tsub\tsil, 1\n\tjne\t.L4\n\tmovsx\teax, al\n\tret\n```\n```assembly [-gcc -Os]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmovsx\tedi, dil\n\tmov\tdl, 1\n\txor\teax, eax\n\tdec\tedi\n.L4:\n\tmovsx\tecx, al\n\tcmp\tecx, edi\n\tjne\t.L2\n\tmov\tdl, -1\n.L2:\n\ttest\tal, al\n\tjne\t.L3\n\tmov\tdl, 1\n.L3:\n\tadd\teax, edx\n\tdec\tsil\n\tjne\t.L4\n\tmovsx\teax, al\n\tret\n```\n```assembly [-gcc -Oz]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmovsx\tedi, dil\n\tmov\tdl, 1\n\txor\teax, eax\n\tdec\tedi\n.L4:\n\tmovsx\tecx, al\n\tcmp\tecx, edi\n\tjne\t.L2\n\tmov\tdl, -1\n.L2:\n\ttest\tal, al\n\tjne\t.L3\n\tmov\tdl, 1\n.L3:\n\tadd\teax, edx\n\tdec\tsil\n\tjne\t.L4\n\tmovsx\teax, al\n\tret\n```\n```assembly [-my ASM]\n\t.intel_syntax noprefix\n\t.globl\tnumberOfChild\nnumberOfChild:\n\tmov dl, 1\n\txor eax, eax\n\tdec dil\nloop:\n\tcmp al, dil\n\tjne not_rightmost\n\tmov dl, -1\nnot_rightmost:\n\ttest al, al\n\tjne not_leftmost\n\tmov dl, 1\nnot_leftmost:\n\tadd al, dl\n\tdec sil\n\tjnz loop\nepilog:\t\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 numberOfChild(int n, int k);\n\nint main(int argc, const char *argv[]) {\n    // Use numberOfChild 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']