50.under-the-hood/28.working_with_bits_struct_union.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "view-in-github",
    "colab_type": "text"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/kangwonlee/2018pycpp/blob/main/50.under-the-hood/28.working_with_bits_struct_union.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Revisiting `struct` and `union`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `struct` is a group of data.  An array is also a group of data.  Difference is, to access data in `struct`, we would use *field name*s; for arrays, indices.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Also, *field*s of struct may have different types; for arrays, all same types.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Fields of `unions` share the same memory.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `union`: Little endian vs Big endian\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Let's see how our computer stores a multi-byte integer.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Using `union` we can make a multi-byte integer and an array of characters share the memory.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%writefile little_or_big.cpp\n",
    "// The directive above would write following text into a file\n",
    "\n",
    "#include <cstdio>\n",
    "#include <cstdint>\n",
    "\n",
    "// i and c[4] would share the same memory\n",
    "union little_big_tag{\n",
    "    uint32_t i;\n",
    "    char c[4];\n",
    "};\n",
    "\n",
    "\n",
    "int32_t main(const int32_t argn, const char * argv[]){\n",
    "    \n",
    "    // an instance of the union\n",
    "    union little_big_tag s;\n",
    "\n",
    "    // See if both int and char[] member share the same memory\n",
    "    printf(\"&(s.i) = %08lx\\n\", (uint64_t) (&(s.i)));\n",
    "    printf(\"&(s.c) = %08lx\\n\", (uint64_t) (&(s.c)));\n",
    "    \n",
    "    printf(\n",
    "        \"They share the same memory if non-zero: %x\\n\", \n",
    "        (\n",
    "            (uint64_t) (&(s.i)) == (uint64_t) (&(s.c))\n",
    "        )\n",
    "    );\n",
    "\n",
    "    // assign an integer to the integer member of s\n",
    "    s.i = 0x01020304;\n",
    "    // reading the memory as one 32 bit integer\n",
    "    printf(\"s.i = %08x\\n\", s.i);\n",
    "    // as four 8 bit characters\n",
    "    printf(\"s.c = %02x %02x %02x %02x\\n\", s.c[0], s.c[1], s.c[2], s.c[3]);\n",
    "\n",
    "    // check address of each member of char[4]\n",
    "    // which part of integer is in which part of array?\n",
    "    int32_t i = 0;\n",
    "    for (i = 0; 4 > i; i++){\n",
    "        printf(\"&(s.c[%d]) = %08lx\\n\", i, (uint64_t) (&(s.c[i])));\n",
    "    }\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -Wall -g -std=c++14 little_or_big.cpp -o little_or_big -Wa,-adhln=little_or_big.s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!./little_or_big\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 16bit color using `struct` and `union`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* For each field of struct, we may specify its length in **bits**.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Followinging could be one example for the 16bit color information.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "``` C++\n",
    "#include <cstdint>\n",
    "\n",
    "// Josh Kunz, Bit-field Packing in GCC and Clang\n",
    "//     https://jkz.wtf/bit-field-packing-in-gcc-and-clang\n",
    "\n",
    "struct high_color_tag{\n",
    "    uint16_t red:5;\n",
    "    uint16_t green:6;\n",
    "    uint16_t blue:5;\n",
    "};\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We can see that the sum of bits is `5 + 6 + 5 = 16`; two bytes.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Following C++ code would show some examples.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%writefile bit_field_struct.cpp\n",
    "#include <bitset>\n",
    "#include <cstdint>\n",
    "#include <cstdlib>\n",
    "#include <iomanip>\n",
    "#include <iostream>\n",
    "\n",
    "// Josh Kunz, Bit-field Packing in GCC and Clang, \n",
    "//     https://jkz.wtf/bit-field-packing-in-gcc-and-clang\n",
    "\n",
    "// Bit field struct\n",
    "struct high_color_tag{\n",
    "    uint16_t red:5;\n",
    "    uint16_t green:6;\n",
    "    uint16_t blue:5;\n",
    "};\n",
    "\n",
    "// Let the struct share memory with an unsigned 16bit integer\n",
    "union high_color_union_tag{\n",
    "    struct high_color_tag rgb_struct;\n",
    "    uint16_t hex;\n",
    "};\n",
    "\n",
    "\n",
    "int32_t main(const int32_t argn, const char * argv[]){\n",
    "    // realize the union\n",
    "    union high_color_union_tag rgb_union;\n",
    "    // number of examples\n",
    "    const int32_t n = 10;\n",
    "\n",
    "    // variables for r g b colors and index\n",
    "    uint32_t r = 0, g = 0, b = 0, i = 0;\n",
    "    \n",
    "    // table header\n",
    "    std::cout << \"| `r` | `g` | `b` | `hex` |\" << '\\n';\n",
    "    std::cout << \"|:---:|:---:|:---:|:-----:|\" << '\\n';\n",
    "\n",
    "    // example loop\n",
    "    for(i = 0; n > i; ++i){\n",
    "        // generate color values\n",
    "        // 1 << 5 == ?\n",
    "        r = rand() % (1 << 5);\n",
    "        g = rand() % (1 << 6);\n",
    "        b = rand() % (1 << 5);\n",
    "\n",
    "        // set values to the struct fields\n",
    "        rgb_union.rgb_struct.red = r;\n",
    "        rgb_union.rgb_struct.green = g;\n",
    "        rgb_union.rgb_struct.blue = b;\n",
    "\n",
    "        // bit patterns of color values\n",
    "        // https://stackoverflow.com/questions/7349689\n",
    "        std::bitset<5> b_r(r);\n",
    "        std::bitset<6> b_g(g);\n",
    "        std::bitset<6> b_b(b);\n",
    "\n",
    "        // bit pattern of the 16bit integer\n",
    "        std::bitset<16> b_hex(rgb_union.hex);\n",
    "\n",
    "        // print this example as a row\n",
    "        std::cout << \"| \" << std::hex << std::setw(6) << b_r\n",
    "                    << \" | \" << std::setw(6) << b_g\n",
    "                    << \" | \" << std::setw(6) << b_b\n",
    "                    << \" | \" << std::setw(16) << b_hex\n",
    "                    << \" |\\n\";\n",
    "    }\n",
    "\n",
    "    // std::cout << \"sizeof(rgb_union.rgb_struct)\" << sizeof(rgb_union.rgb_struct) << '\\n';\n",
    "\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!g++ -Wall -g -std=c++14 bit_field_struct.cpp -o bit_field_struct -Wa,-adhln=bit_field_struct.s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%bash\n",
    "# The directive above would run following as bash commands\n",
    "\n",
    "# Detect OS type because OSX may need different options\n",
    "# https://stackoverflow.com/questions/3466166/how-to-check-if-running-in-cygwin-mac-or-linux/18790824\n",
    "\n",
    "# obtain system information\n",
    "unameOut=\"$(uname -s)\"\n",
    "\n",
    "# detect system type\n",
    "case \"${unameOut}\" in\n",
    "    Linux*)     machine=Linux;;\n",
    "    Darwin*)    machine=Mac;;\n",
    "    CYGWIN*)    machine=Cygwin;;\n",
    "    MINGW*)     machine=MinGw;;\n",
    "    *)          machine=\"UNKNOWN:${unameOut}\"\n",
    "esac\n",
    "\n",
    "if [ $machine == \"Linux\" ]; then\n",
    "    # build command for Linux\n",
    "    g++ -Wall -g bit_field_struct.cpp -o ./bit_field_struct -Wa,-adhln=bit_field_struct.s\n",
    "elif [ \"Mac\" == $machine ]; then\n",
    "    # build command for OSX\n",
    "    # https://stackoverflow.com/questions/10990018/\n",
    "    clang++ -S -mllvm --x86-asm-syntax=intel bit_field_struct.cpp\n",
    "    clang++ -Wall -g bit_field_struct.cpp -o bit_field_struct\n",
    "else\n",
    "    # Otherwise\n",
    "    g++ -Wall -g bit_field_struct.cpp -o ./bit_field_struct.s -S\n",
    "    g++ -Wall -g bit_field_struct.cpp -o ./bit_field_struct\n",
    "fi\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%bash --out rgb_16 --err error\n",
    "./bit_field_struct\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert ((\"error\" not in dir()) or (not error)), error\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import IPython.display as disp\n",
    "disp.display(disp.Markdown(rgb_16))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now let's take a look at some lines of the assembly code.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "  44:bit_field_struct.cpp ****\n",
    "  45:bit_field_struct.cpp ****   // set values to the struct fields\n",
    "  46:bit_field_struct.cpp ****   rgb_union.rgb_struct.red = r;\n",
    " 568                            .loc 6 46 0\n",
    " 569 00e4 8B45BC                movl    -68(%rbp), %eax\n",
    " 570 00e7 83E01F                andl    $31, %eax\n",
    " 571 00ea 83E01F                andl    $31, %eax\n",
    " 572 00ed 89C2                  movl    %eax, %edx\n",
    " 573 00ef 0FB645B2              movzbl  -78(%rbp), %eax\n",
    " 574 00f3 83E0E0                andl    $-32, %eax\n",
    " 575 00f6 09D0                  orl     %edx, %eax\n",
    " 576 00f8 8845B2                movb    %al, -78(%rbp)\n",
    "  47:bit_field_struct.cpp ****   rgb_union.rgb_struct.green = g;\n",
    " 577                            .loc 6 47 0\n",
    " 578 00fb 8B45C0                movl    -64(%rbp), %eax\n",
    " 579 00fe 83E03F                andl    $63, %eax\n",
    " 580 0101 0FB6C0                movzbl  %al, %eax\n",
    " 581 0104 83E03F                andl    $63, %eax\n",
    " 582 0107 C1E005                sall    $5, %eax\n",
    " 583 010a 89C2                  movl    %eax, %edx\n",
    " 584 010c 0FB745B2              movzwl  -78(%rbp), %eax\n",
    " 585 0110 66251FF8              andw    $-2017, %ax\n",
    " 586 0114 09D0                  orl     %edx, %eax\n",
    " 587 0116 668945B2              movw    %ax, -78(%rbp)\n",
    " 48:bit_field_struct.cpp ****    rgb_union.rgb_struct.blue = b;\n",
    " 588                            .loc 6 48 0\n",
    " 589 011a 8B45C4                movl    -60(%rbp), %eax\n",
    " 590 011d 83E01F                andl    $31, %eax\n",
    " 591 0120 8D14C500000000        leal    0(,%rax,8), %edx\n",
    " 592 0127 0FB645B3              movzbl  -77(%rbp), %eax\n",
    " 593 012b 83E007                andl    $7, %eax\n",
    " 594 012e 09D0                  orl     %edx, %eax\n",
    " 595 0130 8845B3                movb    %al, -77(%rbp) \n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Please compare with the previous example.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "  25:bitwise_16bit_color.cpp ****\n",
    "  26:bitwise_16bit_color.cpp **** // set red value from bit 0 ~ 4\n",
    "  27:bitwise_16bit_color.cpp ****         hex |= (r & 0x1F);\n",
    " 567                            .loc 6 27 0\n",
    " 568 00d6 8B45B8                movl    -72(%rbp), %eax\n",
    " 569 00d9 83E01F                andl    $31, %eax\n",
    " 570 00dc 0945C4                orl     %eax, -60(%rbp)\n",
    "  28:bitwise_16bit_color.cpp ****\n",
    "  29:bitwise_16bit_color.cpp **** // set green value from bit 5 ~ 10\n",
    "  30:bitwise_16bit_color.cpp ****         hex |= ((g & 0x3F) << 5);\n",
    " 571                            .loc 6 30 0\n",
    " 572 00df 8B45BC                movl    -68(%rbp), %eax\n",
    " 573 00e2 C1E005                sall    $5, %eax\n",
    " 574 00e5 25E00700              andl    $2016, %eax\n",
    " 574      00\n",
    " 575 00ea 0945C4                orl     %eax, -60(%rbp)\n",
    "  31:bitwise_16bit_color.cpp ****\n",
    "  32:bitwise_16bit_color.cpp **** // set blue value from bit 11 ~ 15\n",
    "  33:bitwise_16bit_color.cpp ****         hex |= ((b & 0x1F) << 11);\n",
    " 576                            .loc 6 33 0\n",
    " 577 00ed 8B45C0                movl    -64(%rbp), %eax\n",
    " 578 00f0 C1E00B                sall    $11, %eax\n",
    " 579 00f3 0FB7C0                movzwl  %ax, %eax\n",
    " 580 00f6 0945C4                orl     %eax, -60(%rbp)\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}