# E07: bits
###### tags: `sysprog2018`

:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2018 年系統軟體課程](https://www.facebook.com/groups/system.software2018/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::

## 預期目標

* 深度學習 [CS:APP](https://hackmd.io/c/S1vGugaDQ) 第 2 章和對應的補充教材
* 跨越理論與實務的鴻溝

## 在 Ubuntu Linux x86 64-bit 安裝 32-bit 開發套件

$ sudo apt update
$ sudo apt install libc6-dev:i386 gcc:i386

## 詳細閱讀 CMU CS:APP Data Lab 要求

* [Data Lab: Manipulating Bits](http://csapp.cs.cmu.edu/3e/datalab.pdf)
- 忽略 `2 Logistics`, `datalab-handout.tar`, `dlc`, `driver.pl`, 和 `8 The "Beat the Prof" Contest` 相關內容
- 專注於修改 `bits.c` 即可
* 取得成功大學修改過的版本 [datalab](https://github.com/sysprog21/datalab)

    $ git clone https://github.com/sysprog21/datalab
    $ cd datalab
    $ make check

* 參考輸出: (一開始什麼事都沒做，當然零分)

    ERROR: Test twosComp2SignMag(-2147483647[0x80000001]) failed...
    ...Gives 42[0x2a]. Should be -1[0xffffffff]
    ERROR: Test upperBits(0[0x0]) failed...
    ...Gives 42[0x2a]. Should be 0[0x0]
    Total points: 0/228

## 作業要求

* 自 GitHub 上 fork [datalab](https://github.com/sysprog21/datalab)，依據 [Data Lab: Manipulating Bits](http://csapp.cs.cmu.edu/3e/datalab.pdf)，補完欠缺的程式碼，並且通過自動測試
* 確保儘可能少的指令，可用 `$ gcc -S bits.c` 輸出組合語言並觀察 `bits.s` 的程式碼裡頭的 x86 (IA32) 指令
* 避免用分支 (branch)，設計時間複雜度為 $O(1)$ 的實作
* 選出其中 7 個位元操作的函式，詳細解釋其原理，需要比照 [clz 應用](https://hackmd.io/s/Bk-uxCYxz) 和 [bit-reverse](https://hackmd.io/s/ByzoiggIb) 的分析方式，==舉出真實世界中的應用案例== (最好在 GitHub 找出程式碼)，解說應搭配有效的測試程式碼
* 探討讓 [datalab](https://github.com/sysprog21/datalab) 得以 64-bit friendly 的提案，並舉出實際程式碼修改

## 繳交方式

* 編輯 [Homework 5 作業區共筆](https://hackmd.io/s/S1CRTc8jX)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

## 截止日期

* Oct 31, 2018 (含) 之前進行，不該截止日前一天才動手
* 越早在 GitHub 上有動態、越早接受 code review，評分越高

## 參考資訊

* [深入理解計算機系統（CS:APP) - Data Lab 詳解](https://www.viseator.com/2017/06/18/CS_APP_DataLab/)
* [CSAPP：datalab](https://www.jianshu.com/p/caf552ea3322)