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\nAdd the even numbers and substract the odd\n\n# Approach\n\nLoop through all digits of `num` incrementing the `RDI` register. Initialize AX to zero. In the loop, update the value of `AX` adding the even numbers and substracting the odds. Then return. View [code](#assembly-code) comments for explanation.\n\n# Complexity\n- Time complexity: $$O(\\text{num.length})$$, because It will execute the code in `loop` as many times as number of digits in `num`. Moreover, $$\\text{num.length} \\le 100$$.\n- Space complexity: $$O(1)$$, No memory variable is needed, only registers.\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 [comparison with C](#comparison-with-c). If you want to test this code you can [run locally](#run-locally).\n\n```c [C (inline asm)]\nbool isBalanced(char* num) {\n\tbool ret;\n\t__asm__(\n".intel_syntax noprefix\\n"\n"\t## dl: will be the digit as character\\n"\n"\t## ax: the sum of digits\\n"\n"\t## rdi: pointer to current digit\\n"\n"\txor\tdx, dx\\n"\n"\txor\trax, rax\\n"\n"loop:\\n"\n"\t## get the current digit as character in dl\\n"\n"\tmov\tdl, BYTE PTR [rdi]\\n"\n"\t\\n"\n"\t## end loop if character is null\\n"\n"\ttest\tdl, dl\\n"\n"\tje\tendloop\\n"\n"\\n"\n"\t## get the number rather than character\\n"\n"\tsub\tdl, \'0\'\\n"\n"\t\\n"\n"\t## check if even or odd\\n"\n"\ttest\tdil, 1\\n"\n"\tjne\todd\\n"\n"\t\\n"\n"\t## add character to ax\\n"\n"\tadd\tax, dx\\n"\n"\tjmp\tupdate\\n"\n"odd:\\n"\n"\t## substract character from ax\\n"\n"\tsub\tax, dx\\n"\n"\\n"\n"update:\\n"\n"\tinc\trdi\\n"\n"\tjmp\tloop\\n"\n"endloop:\\n"\n"\t## logical not of ax\\n"\n"\ttest\tax, ax\\n"\n"\tsetz\tal\\n"\n"\tjmp\tepilog\\n"\n"epilog:\\n"\n".att_syntax\\n"\n\t\t: "=a"(ret)\n\t);\n\treturn ret;\n}\n```\n```assembly [ASM (with comments)]\n    .intel_syntax noprefix\n    .globl  isBalanced\nisBalanced:\n\t## dl: will be the digit as character\n\t## ax: the sum of digits\n\t## rdi: pointer to current digit\n\txor\tdx, dx\n\txor\trax, rax\nloop:\n\t## get the current digit as character in dl\n\tmov\tdl, BYTE PTR [rdi]\n\t\n\t## end loop if character is null\n\ttest\tdl, dl\n\tje\tendloop\n\n\t## get the number rather than character\n\tsub\tdl, \'0\'\n\t\n\t## check if even or odd\n\ttest\tdil, 1\n\tjne\todd\n\t\n\t## add character to ax\n\tadd\tax, dx\n\tjmp\tupdate\nodd:\n\t## substract character from ax\n\tsub\tax, dx\n\nupdate:\n\tinc\trdi\n\tjmp\tloop\nendloop:\n\t## logical not of ax\n\ttest\tax, ax\n\tsetz\tal\n\tjmp\tepilog\nepilog:\n\tret\n```\n```assembly [ASM (without comments)]\n    .intel_syntax noprefix\n    .globl  isBalanced\nisBalanced:\n\n\n\n\txor\tdx, dx\n\txor\trax, rax\nloop:\n\n\tmov\tdl, BYTE PTR [rdi]\n\t\n\n\ttest\tdl, dl\n\tje\tendloop\n\n\n\tsub\tdl, \'0\'\n\t\n\n\ttest\tdil, 1\n\tjne\todd\n\t\n\n\tadd\tax, dx\n\tjmp\tupdate\nodd:\n\n\tsub\tax, dx\n\nupdate:\n\tinc\trdi\n\tjmp\tloop\nendloop:\n\n\ttest\tax, ax\n\tsetz\tal\n\tjmp\tepilog\nepilog:\n\tret\n```\n```assembly [ASM (without comments)]\n    .intel_syntax noprefix\n    .globl  isBalanced\nisBalanced:\n\txor\tdx, dx\n\txor\trax, rax\nloop:\n\tmov\tdl, BYTE PTR [rdi]\n\ttest\tdl, dl\n\tje\tendloop\n\tsub\tdl, \'0\'\n\ttest\tdil, 1\n\tjne\todd\n\tadd\tax, dx\n\tjmp\tupdate\nodd:\n\tsub\tax, dx\nupdate:\n\tinc\trdi\n\tjmp\tloop\nendloop:\n\ttest\tax, ax\n\tsetz\tal\n\tjmp\tepilog\nepilog:\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` and remove stack protector for comparison. \n\n```bash\n$ gcc -O2 -fno-stack-protector -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 these techniques in order to get optimized code.\n\n- Use `restrict`s, `const`s.\n- Type castings to smaller types.\n- Use do-while instead of while or for.\n\nMoreover, after the generated assembly code, I have also included my solution using assembly without comments for comparison.\n\n```C [-C code]\n#include <stdbool.h>\n\nbool isBalanced(char* num) {\n\tshort sum = 0;\n\twhile (*num) {\n\t\tif ((long) num % 2 == 0) {\n\t\t\tsum += *num - \'0\';\n\t\t} else {\n\t\t\tsum -= *num - \'0\';\n\t\t}\n\t\tnum++;\n\t}\n\t\n\treturn !sum;\n}\n```\n```assembly [-gcc -O0]\n\t.intel_syntax noprefix\n\t.globl\tisBalanced\nisBalanced:\n\tpush\trbp\n\tmov\trbp, rsp\n\tmov\tQWORD PTR -24[rbp], rdi\n\tmov\tWORD PTR -2[rbp], 0\n\tjmp\t.L2\n.L5:\n\tmov\trax, QWORD PTR -24[rbp]\n\tand\teax, 1\n\ttest\trax, rax\n\tjne\t.L3\n\tmov\trax, QWORD PTR -24[rbp]\n\tmovzx\teax, BYTE PTR [rax]\n\tmovsx\tdx, al\n\tmovzx\teax, WORD PTR -2[rbp]\n\tadd\teax, edx\n\tsub\teax, 48\n\tmov\tWORD PTR -2[rbp], ax\n\tjmp\t.L4\n.L3:\n\tmovzx\tedx, WORD PTR -2[rbp]\n\tmov\trax, QWORD PTR -24[rbp]\n\tmovzx\teax, BYTE PTR [rax]\n\tmovsx\tcx, al\n\tmov\teax, edx\n\tsub\teax, ecx\n\tadd\teax, 48\n\tmov\tWORD PTR -2[rbp], ax\n.L4:\n\tadd\tQWORD PTR -24[rbp], 1\n.L2:\n\tmov\trax, QWORD PTR -24[rbp]\n\tmovzx\teax, BYTE PTR [rax]\n\ttest\tal, al\n\tjne\t.L5\n\tcmp\tWORD PTR -2[rbp], 0\n\tsete\tal\n\tpop\trbp\n\tret\n```\n```assembly [-gcc -O1]\n\t.intel_syntax noprefix\n\t.globl\tisBalanced\nisBalanced:\n\tmovzx\teax, BYTE PTR [rdi]\n\ttest\tal, al\n\tje\t.L6\n\tmov\tedx, 0\n\tjmp\t.L5\n.L3:\n\tadd\tedx, 48\n\tcbw\n\tsub\tedx, eax\n.L4:\n\tadd\trdi, 1\n\tmovzx\teax, BYTE PTR [rdi]\n\ttest\tal, al\n\tje\t.L2\n.L5:\n\ttest\tdil, 1\n\tjne\t.L3\n\tcbw\n\tlea\tedx, -48[rdx+rax]\n\tjmp\t.L4\n.L6:\n\tmov\tedx, 0\n.L2:\n\ttest\tdx, dx\n\tsete\tal\n\tret\n```\n```assembly [-gcc -O2]\n\t.intel_syntax noprefix\n\t.globl\tisBalanced\nisBalanced:\n\tmovsx\tax, BYTE PTR [rdi]\n\ttest\tal, al\n\tje\t.L6\n\txor\tecx, ecx\n.L5:\n\tlea\tedx, -48[rcx+rax]\n\ttest\tdil, 1\n\tje\t.L4\n\tlea\tedx, 48[rcx]\n\tsub\tedx, eax\n.L4:\n\tmovsx\tax, BYTE PTR 1[rdi]\n\tadd\trdi, 1\n\tmov\tecx, edx\n\ttest\tal, al\n\tjne\t.L5\n\ttest\tdx, dx\n\tsete\tal\n\tret\n.L6:\n\tmov\teax, 1\n\tret\n```\n```assembly [-gcc -Os]\n\t.intel_syntax noprefix\n\t.globl\tisBalanced\nisBalanced:\n\txor\teax, eax\n.L2:\n\tmovsx\tdx, BYTE PTR [rdi]\n\ttest\tdl, dl\n\tje\t.L7\n\ttest\tedi, 1\n\tjne\t.L3\n\tlea\teax, -48[rax+rdx]\n\tjmp\t.L4\n.L3:\n\tadd\teax, 48\n\tsub\teax, edx\n.L4:\n\tinc\trdi\n\tjmp\t.L2\n.L7:\n\ttest\tax, ax\n\tsete\tal\n\tret\n```\n```assembly [-gcc -Oz]\n\t.intel_syntax noprefix\n\t.globl\tisBalanced\nisBalanced:\n\txor\teax, eax\n.L2:\n\tmovsx\tdx, BYTE PTR [rdi]\n\ttest\tdl, dl\n\tje\t.L7\n\ttest\tedi, 1\n\tjne\t.L3\n\tlea\teax, -48[rax+rdx]\n\tjmp\t.L4\n.L3:\n\tadd\teax, 48\n\tsub\teax, edx\n.L4:\n\tinc\trdi\n\tjmp\t.L2\n.L7:\n\ttest\tax, ax\n\tsete\tal\n\tret\n```\n```assembly [-my ASM]\n    .intel_syntax noprefix\n    .globl  isBalanced\nisBalanced:\n\txor\tdx, dx\n\txor\trax, rax\nloop:\n\tmov\tdl, BYTE PTR [rdi]\n\ttest\tdl, dl\n\tje\tendloop\n\tsub\tdl, \'0\'\n\ttest\tdil, 1\n\tjne\todd\n\tadd\tax, dx\n\tjmp\tupdate\nodd:\n\tsub\tax, dx\nupdate:\n\tinc\trdi\n\tjmp\tloop\nendloop:\n\ttest\tax, ax\n\tsetz\tal\n\tjmp\tepilog\nepilog:\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\nbool isBalanced(char* num);\n\nint main(int argc, const char *argv[]) {\n    // Use isBalanced 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']