# 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 開發套件 ```shell $ 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) ```shell $ 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)