Jan 8, 2016 課程紀錄

[2015q3 Week #17] [編輯共筆內容]

解答同學的提問

source: Homework 6 / 基礎觀念學習

From Source to Binary

[ Page 16 ]

Intro of CS143 - Compiler

[ Page 27-31 ]

IR -> `Optimization` -> `code generator` -> Object code

(IR = immediate representation)

Optimization 主要工作

Code generation: 將 IR 轉換城 instruction

STM32 程式開發:以 GNU Toolchain 為例

From Source to Binary

[ Page 31 ]

下圖說明如果沒有 IR 這樣的中間表示法,每個前端 (source files; human readable programming language) 直接對應到後端 (machine code) 的話,有太多種組合,勢必會讓開發量爆增。但如果先讓前端輸出 IR,然後 IR 再接到後端,這樣整體的彈性就大多了

[ Page 69 ]

[ Page 73 ] 

Hello World!

Insecure coding in C/C++

[ Page 155 ]

[ Page 179 ]

[ Page 222 ]

ARMv7-A Architecture

[ Page 5 ]

應用案例: Android 4.0

=> https://www.duosecurity.com/blog/a-look-at-aslr-in-android-ice-cream-sandwich-4-0

ARM Cortex-M3 Introduction

為什麼 bit banding 有 atomic特性?

依據 The Definitive Guide to ARM® Cortex®-M3 and Cortex®-M4 Processors,Page 84:

Note that the Cortex-M3 uses the following terms for the bit-band memory addresses:

這樣的設計概念在 30 年前的 Intel 8051 就有,但作得更完整,要特別注意讀寫資料的一致性。在 Page 85 有兩張圖:

Figure 5.4 說明如果不用 bit-band,Read 和 Write 之間會有額外設定 bit 2 的操作,這可能會因為 interrupt handing 而導致資料的不一致。但右圖展示的 bit-band,確保了 write 本身可作到 atomic

一個發揮 ARM Cortex-M bit-band 機制的案例就是 F9 microkernel 的 bitmap 處理,透過 bit-band,可大幅簡化程式設計的難度,特別在 Test-n-Set 的操作上:

https://github.com/f9micro/f9-kernel/blob/master/include/lib/bitmap.h

From Source to Binary

[ Page 40 ]

Virtual Machine Constructions for Dummies

[ Page 14 ]

從 Revolution OS 看作業系統生態變化

Q: 自由軟體的商業行為有什麼樣的型式? 是指技術支援的服務嗎?

Q: 影片中提及「Cygnus 還開發了BFD 函式庫,並在許多接受 NDA (保密協議) 的狀況下,開發新型晶片的軟體開發移植工具,將 GNU 開發工具移植到許多硬體架構」 , 這邊的保密協議是指要對什麼東西保密,不是都要open source了?

Something Behind Hello World

[ Page 57 ]

投影片的指令:

其中 `-PIC` 在 Using GCC to create static and shared library .so 的 2.1 提到

「編譯時要加上 -fPIC 用來產生 position-independent code。也可以用 -fpic參數」

當我用 `-fpic` 編譯,如果不特別指定平台,系統會是針對當下的環境,還是 `-fpic` 本身有預設值?

對照看這份說明:

http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/

我們先準備 add.c 程式碼,內容如下:

先檢查輸出的 object file:

gcc -c add.c -o add-no-pic.o -shared -O1

gcc -c add.c -o add-pic.o -fPIC -shared -O1

diff -u add-no-pic.o add-pic.o

沒差異!

但變成 shared library 後呢?

ld -shared -o add-no-pic.so add-no-pic.o 

ld -pic -fPIC -shared -o add-pic.so add-pic.o 

ls -l *.so

內容不一樣!

分別反組譯:

[沒有 PIC]

[開啟 PIC]

乍看只有位址不同,但為何 add-pic.so 比 add-no-pic.so 還大呢?

因為程式太簡單,看不出來,但換成以下呢? (add.c)

重複上述動作,發現 `.o` 和 `.so` 都不一樣!

反組譯:

[沒有 PIC]

[開啟 PIC]

看出來了嗎?真正的差異反映於 function call 的行為

延伸閱讀: http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/

From Source to Binary

[ Page 5 ]

CS4414

什麼是作業系統

[ 時間軸 6:17 ]

From Source to Binary

=> 筆記和提問

計算機組織結構的筆記

From Source to Binary

[ Page 71 ]

From Source to Binary

[ Page 5 ]

這邊提到驗證執行檔後並載入動態函式庫,為何要有 C Runtime?

先想想以下程式的執行: (hello.c)

當你在 GNU/Linux 下編譯和執行後 (`gcc -o hello hello.c ; ./hello`),可用 `echo $?` 來取得程式返回值,也就是 `1`,可是這個返回值總有機制來處理吧?所以你需要一套小程式來作,這就是 C runtime (簡稱 crt)。此外,還有 `atexit` 一類的函式,也需要  C runtime 的介入才能實現。

Something Behind Hello World

對照閱讀《程式設計師的自我修養-連結、載入、程式庫

對於全域變數的測試程式碼:

面試題目分析

[ source

給定一個 singly-linked list 結構:

要求:初始化 10000 個 element,使其內含值為介於 1 到 10000 之間的亂數,彼此不重複

程式碼: EX1.c by 魏騰昱

(需要改進,請見 GitHub 的 code review)

執行結果(以1~100示意)

效能分析

   

分析 : 由於每次random都必須在從頭在跑一遍看是否重複,若重複的話就在重新random,那在list越長的情況下重複的機率就越大,就必須不斷的重新random,因此執行時間將會變得無法預期

       

分析 : card shuffle alogrithm複雜度為O(n*n) , 因此效率比方法一要好很多

延伸討論 by YouTube 工程師 YC

以下是一些延申問題的討論。額外說明:

 1. 除了linked list本身的佔用的空間外,若允許額外使用O(N)的空間,怎麼做較好呢?

可在O(N)內完成,典型的空間換時間。

 2.若允許額外使用O(log(N))的空間,怎麼做較好呢?(call stack的空間也算) 

先初始化linked list並填入1~N的整數。

再使用merge sort的變形,但不依靠比較大小,而以亂數決定順序。Pseudo Code連結

這個程式結構跟merge sort一模一樣,只是以機率取代比大小而已

worst case time complexity是O(N*log(N)),space complexity是O(log(N))用在call stack上。

機率部份的計算比較奇怪一些,這是為了讓N!種組合出現的機率都相同。

比方說left剩3個right剩2個時,應該要有60%的機率從left拿取元素。

 3.若僅能允許額外使用O(1)的空間,怎麼做較好呢?

我會使用方法二O(N^2)的方法。有任何其他想法嗎?

 4.共筆上的方法一雖然不如方法二,其平均時間複雜度是多少呢?

這個方法的worst case time complexity是沒有理論上限的

就算是完美的RNG,理論上還是有可能連續連續出現同一個數字幾百萬次。

但是average case time complexity呢?

假設使用的PRNG夠亂(當作RNG討論),如果需要的平均時間能用一個算式model

應該就可以分析其時間隨資料量的成長趨勢。

* 先討論一個簡單的機率問題

重複做一件成功機率為p的事(每次機率皆為p,每次為獨立事件),一成功就停手

「做幾次會成功」的期望值是多少呢?

有p的機率會一次成功

有1-p的機率會在第一次失敗,然後再需要E次嘗試才會成功

設此期望值為E,可列等式E = p + (1-p) * (1+E)

化簡後可得E = 1/p,次數的期望值為成功率的倒數

具體的例子:連續丟銅板丟到正面才停,需要的平均次數是2次。連續丟六面骰子丟到1才停,平均需要的次數是6次。

* 接下來,考慮取一個元素的cost:

分析已經取了x個元素,要取第x+1個元素的狀況

從1~N中任取一個元素,有x/N的機率會取到重複的元素

試問:「取第幾次元素會取到不重複元素」的期望值是多少呢?

以p = 1 - x/N代入前式,需嘗試的次數期望值為N / (N - x)

那麼,共要做多少次整數比較呢?顯然,若選到已重複的元素,需比較次數的期望值為x/2

兩式相乘為N * x / (N - x) / 2

* 最後,考慮取得所有元素的cost總和

累加選擇每個元素,所需的比較次數則為:

最後一個term其實是harmonic數列的前N項。以積分的面積思考,其值不會超過1+ln(N-1) (見下式,可參考此圖,但此圖是求下限,考量每個區塊的右邊界則可求上限)

故整體cost為O(N^2*log(N))。

Code Review

回顧個人簡歷

2015q3Homeowork10