June 30, 2008
追憶似水年華
-
眾鳥高飛盡，孤雲獨去閑
相看兩不厭，只有敬亭山
因為我們兩個小鬼都在六月份出生 (11 日與 30 日)，所以雙親乾脆就買一份蛋糕，同時為我們慶生，照片是在苗栗老家的客廳中，兄妹滿心期待地望著生日蛋糕，妹妹當時 3 歲，如紅色蠟燭所示，而右邊的蠟燭是青的，表示我的年紀滿 3 + 1 歲，這大概是少數我們充滿歡笑的合影。妹妹的乳名叫做「小美」，在客家話裡頭很常見，不過，也可說是七次登臨敬亭山、留下了人山兩不厭的太白式浪漫的展現，她的成長歷程一度是很順利，也聰明討人歡喜，有大量的創作與活動，但這十幾年來，過得很痛苦，自限於象牙塔中，有如中世紀的武士，獨自對抗著難為我們所察的敵人，而身心俱疲。
在年幼時，受到過度保護、與外界隔絕的我，幾乎不知什麼是朋友，與同學的關係僅限於課堂，而妹妹則是唯一的玩伴，只要鑰匙兒童一回家，兄妹倆立刻拉下鐵門簾，要不看電視、玩積木、談天、下棋，就是各自讀書，偶爾，我們一同打水仗、打電腦、拼圖、繪畫等等，那些是兒時美好的記憶，我們很少吵架，感情也很好。過去，妹妹在許多層面的表現一直大幅超越我，諸如功課、繪畫、鋼琴、身高、人緣，而處於身旁的我，就好像是個弟弟。後來發生了許多轉折，在我離鄉背井到台中唸書時發生的連鎖效應，總之，一切變調了，我幾乎無法與人談論妹妹所發生的事情，以及我們家庭的處理態度。
山脈對地球來說，只是短暫的穩定，是沈積與地質運動的產物，對生命短暫如飛絮的我們來說，就跟其他自然景物一般，無所謂雋永與否。但，若見到我們無法接受、或不喜愛的景物，可能牽引而生煩躁的心情，若所見者在我們的主觀感受，覺得它是美好的，生命本身即可能被牽引而進入美好的狀態。詩仙看山就是這樣的心境，產生了心理的變化，並緩緩帶領生命進入另一種難以言喻的變化。換句話說，人心好似一面鏡，當用平淡祥和的心態，去觀察周圍的人或事物時，周圍的人或事物也會用相同的眼光來看待自身。對我來說，看著過去的敬婷，就像詩仙見敬亭山，一幕幕鮮明的意象，仍映入心智想像中，只是逐漸遠去，我們一同生活的美好體驗，及於生活中的每一分、每一秒。
「生日快樂，小美」這句話，我一直不知道該如何再開口，只希望現在有機會能聽進去。眾鳥高飛，孤雲獨去，誰與誰能夠，不離不棄？
June 28, 2008
用 Makefile 實現 quick sort
在大學課程中，quick sort 大概是用來闡述遞迴概念的最佳範例，因為既簡潔又實用。多數的程式語言也可採用此概念，甚至連 GNU make 裡頭 function call 也能遞迴，所以，何不試著實做 quick sort 呢？以下是 proof-of-concept 的試作品：TRUE = 11111 gt = $(shell if [ $1 -gt $2 ] ; then echo $(TRUE); fi) lt = $(shell if [ $1 -lt $2 ] ; then echo $(TRUE); fi) le = $(shell if [ $1 -le $2 ] ; then echo $(TRUE); fi) qsort = \ $(if $(call le,$(words $1),1),$1, \ $(call qsort, \ $(foreach i,$1, \ $(if $(call gt,$(firstword $1),$i), $i,))) \ $(firstword $1) \ $(call qsort, \ $(foreach i,$1, \ $(if $(call lt,$(firstword $1),$i), $i,)))) data = $(shell od -vAn -N10 -w1 -tu1 < /dev/urandom) all: @echo $(call qsort, $(data))$(data) 給定自十個隨機亂數，取於 /dev/urandom，原理是讀入二進位的亂數資料後，透過 od 指令將每一個 byte 轉換成一個無符號整數。當然重點是 "qsort"，我們可看到 Makefile 中的宣告與實做中，遞迴地呼叫自身，也就是 $(call qsort, ...) 的動作，將 "divine and conquer" 的想法予以實現：先分成左右兩半，再來排序。 取得預先準備的 [Makefile.qsort]，執行的情況類似以下輸出：
$ make -f Makefile.qsort 2 20 29 58 88 165 172 230 242 246既然輸入資料取於亂數，所以只要看到遞增數列即可。
June 27, 2008
教育訓練：Gtk+ 程式設計初體驗
過去很榮幸得以在不同的場合，與朋友分享過一些電腦技術主題的演講，下個月則嘗試時間較長的教育訓練，但仍維持免費的分享形式。主題是「Gtk+ 程式設計初體驗」，由 [酷學園] 張羅議程的進行，詳細資訊可參考 [公告]，以下摘錄部份內容：
- 簡介
-
學習 GUI 程式設計，一開始從 "Hello World" 等級程式出發都沒問題，但頗為枯燥，「做中學」的模式較易讓人產生自信。本議程以專案目標導向的形式，探討 [Gtk+] 與相關技術，如：
- 用 Gtk+ 搭配 GStreamer，打造簡易的 media player
- 以 Gtk+ 的延伸 widget set，打造個 text editor
- 透過 Gtk+/WebKit，打造可嵌入到 Gtk+ 應用程式的 Web Browser
- 時間：2008 年 7 月 26 日 (星期六) 10:00 - 17:00
- 時間規劃： 總共 6 小時 (Part I: 10-12, Part II: 13-17)
- 地點：國立臺灣大學進修推廣部-304教室 :: 台北市羅斯福路四段107號 (位於羅斯福路上靠近基隆路口)
- 費用： 0 -
- 地理位置/交通路線: http://training.dpd.ntu.edu.tw/NTU/Portal/ntumap.htm
- 活動報名網址：http://registrano.com/events/sataipei200807
- 注意事項：
- 本議題提供錄影
- 報名時請務必填寫正確 E-Mail，主辦單位會在講者完成課程所需要的程式碼 +摘要電子檔後，將資料寄送給報名者
- 物件導向的思維與實做
- 視窗系統中的事件與其對應的操作處理
- 圖形元件的設計概念與組合、互動形式
- MVC (Model-View-Control) 設計模式的引入
June 25, 2008
探訪 stack frame：談不定數量參數
前文 [以 C 語言實做 Functional Language 的 Currying] 已探討在 IA32 stack 的操作，讓 Currying 的行為得以在此基礎，予以實現，而我們還可看另一種應用：C 語言的不定數量參數，也就是 stdarg.h 裡規範的行為。當我們使用 printf() 函式搭配強大的資料格式化處理 (printf 本身就是個小型的 interpreter) 時，不免會其運作行為感到好奇，以下是 GNU/Linux 上 /usr/include/stdio.h 的 prototype：(取自 glibc)__BEGIN_NAMESPACE_STD ... /* Write formatted output to stdout. This function is a possible cancellation point and therefore not marked with __THROW. */ extern int printf (__const char *__restrict __format, ...);注意到函式參數列裡頭的 "..."，語法上表示不定個數的參數輸入，在實做面則不離 stack 的行為，筆者以一個簡單的小程式，說明其運作原理： (multiply.c)
#include <stdio.h> #include <stdlib.h> static int multiply() { int *bp; int result = 1; /* Start stack traverse */ #if defined(__i386) __asm__( "movl %%ebp, %0" : "=g"(bp)); #elif defined(__x86_64__) __asm__( "movq %%rbp, %0" : "=g"(bp)); #else /* * Caution: this would fail if it points to the end of the saved * registers instead of the start. (gcc bug in 4.1 branch) */ bp = (void **) __builtin_frame_address(0); #endif bp += 2; while (abs(*bp) < 0x1000000) { result *= *bp++; } return result; } int main() { printf("1! = %7d\n", multiply(1)); printf("2! = %7d\n", multiply(1,2)); printf("3! = %7d\n", multiply(1,2,3)); printf("4! = %7d\n", multiply(1,2,3,4)); printf("5! = %7d\n", multiply(1,2,3,4,5)); printf("6! = %7d\n", multiply(1,2,3,4,5,6)); printf("7! = %7d\n", multiply(1,2,3,4,5,6,7)); printf("8! = %7d\n", multiply(1,2,3,4,5,6,7,8)); printf("9! = %7d\n", multiply(1,2,3,4,5,6,7,8,9)); return 0; }先看看 main() 裡頭的函式呼叫方式，數學的 1!, 2!, 3!, .., 9! (階層運算) 定義就是 1, 1*2, 1*2*3, ..., 1*2*3*...*8*9, 這裡用 multiply() 函式實現，又，筆者在前文已大致提及 C 語言的 function call 與 IA32 stack 的執行時期行為對應：%ebp 指向 frame pointer 頂端，function 本體必須在 prologue 處理好 caller/callee 的 frame pointer，而參數的傳遞也是這時該考量的。所以，若我們可取得 stack 中 frame pointer 的內含值，往後推算，不就可取得參數內容嗎？進而，我們可拿這些資料作自行規範的舉動，比方說本範例的乘法運算。
取得 %ebp 的方式可透過 inline assembly，如程式碼列表中 x86 與 x86_64 的動作，或者考慮到不同平台，可援引 GCC 的 GNU Extension : __builtin_frame_address，以下是文件的描述：
-
void *__builtin_frame_address (int level);
This function is similar to __builtin_return_address, but it returns the address of the function frame rather than the return address of the function. Calling __builtin_frame_address with a value of 0 yields the frame address of the current function, a value of 1 yields the frame address of the caller of the current function, and so forth.
The frame is the area on the stack which holds local variables and saved registers. The frame address is normally the address of the first word pushed on to the stack by the function. However, the exact definition depends upon the processor and the calling convention. On the Motorola 68000, if the function has a frame, then __builtin_frame_address will return the value of the frame pointer register a6 if level is 0.
stack frame 就是保存變數與暫存器的區域，通常是此函式被推入 (push) 到 stack 中頂端的位址，不過，確切的行為需要視硬體處理器 (如 x86 vs. RISC) 與呼叫方式 (如 ARM 的 OABI vs. EABI) 而定，不過我們這裡只想取得傳遞給 multiply() 的參數序列，就先不思考這麼多。需要留意的是，在 GNU gcc 4.1 branch 中，__builtin_frame_address(0) 的回傳值「有時」會是錯誤的，所以筆者先使用 inline assembly 處理。筆者先進行位移的動作，以自 %ebp 後方取得參數列表，在不參照參數個數的情況下，筆者用投機的途徑來判斷，因為代入者都是小整數序列，基本上只要確定是否落在合理範圍即可。以下是編譯執行的輸出：
$ gcc -xc multiply.c -O0 && ./a.out 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880由可見依序將 multiply() 後方傳遞的參數取出，將其累乘得階層運算值。注意，我們必須將 gcc optimization 關掉，以避免 gcc 將參數捨棄的狀況，另外，也不能傳遞 gcc 編譯的參數 "-fomit-frame-pointer"，這會導致 %ebp 取得與前述方式不一致而無法正確執行的問題。
另外，在 NetBSD/PowerPC 上， stdarg.h 其實就是使用 __builtin_frame_address 來實做對不定個數參數的處理，參見 /usr/src/sys/arch/powerpc/include/stdarg.h 的相關宣告如下：
#define va_start(ap, last) \ (__builtin_next_arg(last), \ (ap).__stack = __va_stack_args, \ (ap).__base = __va_reg_args, \ (ap).__gpr = __va_first_gpr, \ (ap).__fpr = __va_first_fpr) #define __va_first_gpr (__builtin_args_info(0)) #define __va_first_fpr (__builtin_args_info(1) - 32 - 1) #define __va_stack_args \ ((char *)__builtin_saveregs() + \ (__va_first_gpr >= 8 ? __va_first_gpr - 8 : 0) * sizeof(int)) #define __va_reg_args \ ((char *)__builtin_frame_address(0) + __builtin_args_info(4))不過，NetBSD 與 GNU/Linux 對 gcc 處理的更迭，現已用不同的方式封裝，但原理還是一致的。
June 21, 2008
操作 X 的 Cut and Paste Buffer
在 X Window System 要處理 X client 之間的資料分享，因為設計本質上與傳統 GUI 有極大差異，所以，不可等閒視之，也就是說，在 Win32 下很普通的 Clipboard 處理，搬到 X 下，其實得考慮相當多。Win32 Clipboard 無法「直接」對應到 X Clipboard，我們必須分很多層級去思考，一般的 X client 中，以滑鼠(mouse) / 指標(pointer) 作區域的文字 / 物件選擇動作，在真正貼上或複製到標的視窗前，其實涉及到跨越實體環境的資料分享 (考慮到 X Protocol 分散式處理本質) 的議題，所以，光是如何保存這些中間資訊，就是很大的學問。簡單的文字，可透過名為 X cut buffer 的空間，暫時保存 X cut-paste 過程的內容，但這僅是最基本的操作，一般設計較為複雜的 X Toolkit 如 Gtk+ 或 Qt，其實都援引不同的機制，不過，這不妨礙我們對系統的理解。作為最基本的資料分享機制，X cut and paste buffer 僅是很單純的存取緩衝區的資料，我們可這樣實做簡單的寫入操作，程式如下： (xcutbuf-set.c)
#define _GNU_SOURCE #include <X11/Xlib.h> #include <X11/Xatom.h> #include <stdio.h> #include <string.h> #define BUF_LENGTH 8080 int main(int argc, char* argv[]) { char buf[BUF_LENGTH]; Display *disp = XOpenDisplay(0); fgets(buf, BUF_LENGTH, stdin); XStoreBytes(disp, buf, strnlen(buf, BUF_LENGTH)); while (XGetSelectionOwner(disp, XA_PRIMARY) != None) { XSetSelectionOwner(disp, XA_PRIMARY, None, CurrentTime); } return 0; }這裡用到 XStoreBytes(3) 來對緩衝區作寫入動作，編譯並執行如下：
$ gcc -o xcutbuf-set xcutbuf-set.c -lX11 $ echo -n "Let's Do It" | ./xcutbuf-set自標準輸入取得資料後，就透過 XStoreBytes(3) 寫入 x cut buffer，需要留意的是，我們必須透過 XSetSelectionOwner(3) 來讓現在的 window selection (X 術語，表示指定的「選擇」動作，像是 cut-n-paste 的動作) 生效。在 rxvt 或 rxvt-unicode 下，我們可按下 "Shift" + "Insert" 按鍵組合，會自 X cut buffer 取出已寫入的資料，也就是剛剛那字串："Let's Do It"。透過函式呼叫，可取出裡頭的字串，程式碼如下： (xcutbuf-get.c)
#include <X11/Xlib.h> #include <stdio.h> int main(int argc, char* argv[]) { int count; Display *disp = XOpenDisplay(0); printf("==> %s\n", XFetchBytes(disp, &count)); return 0; }編譯並執行：
$ gcc -o xcutbuf-get xcutbuf-get.c -lX11 $ ./xcutbuf-get ==> Let's Do It以上，咱們邁出認識 X client 間資料交換最簡單的機制：X cut buffer 的操作，未來將會探討 X clipboard 運作的機制。
June 20, 2008
開機見 Hello World
幾周前，c9s 寫了篇文章 [如何在 Linux 下使用 GNU AS 撰寫組合語言(1)]，找筆者協助檢閱，簡單扼要地提及 ELF 執行檔主體、GNU Assembler 語法，最後以 80486 以後 (含) 引入的 cpuid 指令作範例，是不錯的入門文章。閱讀時，也想到之前提過 [電子書《使用開源軟件-自己動手寫操作系統》免費下載]，這份來自對岸高手 [solrex] 的電子書籍，於是，筆者也提供一個具體而微的組合語言範例，使其置入 floppy / hard-disk 的 boot sector 中，能如同 boot loader 一般，當系統啟動時，就被載入執行。當然，這裡還是用筆者最愛的 "Hello World" 程式，用組合語言來實現如下：
.text .globl start .code16 start: movb $0xE, %ah # write character in text mode for int 10h movb $'H', %al # write 'H', 'e', 'l', 'l', 'o' int $0x10 movb $'e', %al int $0x10 movb $'l', %al int $0x10 ... 省略 ... ret # Fill NOP instruction (opcde = 0x90) till base offset 0x1FE. .org 0x1FE, 0x90 # This indicates boot disk boot_flag: .word 0xAA55在 x86 開機的情境中，x86 CPU 會先執行位址 0xFFFF0 的程式，這就是 BIOS ROM 的進入點，一旦完畢後 (事實上，本世紀的 x86 BIOS 已複雜到難以用一句話描述行為，包含 Windows 95 與 GNU/Linux 等完整的作業系統，都可燒入至 BIOS ROM 之中，藉此提供快速啟動作業系統的某些服務之用)，執行權會試著交棒給 boot loader 或作業系統。BIOS 的設計會依設定的順序，查驗各別開機磁碟裝置 (如 floppy, hard disk, CD-ROM 等等) 的起始單元，並載入其內容的 512 bytes 至記憶體位址 0x0000:7c00，從而跳躍到該位址並執行，也就將控制權從 BIOS ROM 移轉到 boot loader 或作業系統主體，詳情可參閱 [X86 開機流程小記] 與 [Linux/x86 開機流程：自 MBR 到 init]。
就 hard-disk 來說，其起始單元特稱 MBR (Master Boot Record)，表示物理表示的 cylinder 0, head 0, sector 1，而 BIOS 的設計對於此空間的內容，需額外檢查最後兩 bytes 是否為 0x55 與 0xAA，才可判定有效，進而執行上述開機動作，否則繼續搜尋下個裝置。這段期間，x86 CPU 處於 16 bit Real mode，所以筆者提供的組合語言程式宣告了 ".code16"，告知 GNU Assembler 組譯出 16 bit 的機械碼，而上述的程式碼列表中，最後一行正是 0xAA55 (litten endian)。至於中間的程式碼，就不是特別重要，只是在呼叫 BIOS 中斷 int 10h 前，設定了 %ah 的值為 0xE，表示在文字模式下寫入字元，"Hello World!" 即是在此處理。中間的部份，補了 NOP 指令，以便讓末端的 0x55 與 0xAA 字元得以填入 BIOS 讀出的 512 bytes 尾端。
咱們看如何編譯這個小程式，並給定其正確的參數，先補個 Makefile 如下：
AS = as
LD = ld
OBJCOPY = objcopy
.S.o:
$(AS) -a $< -o $*.o > $*.map
all: disk.img
disk.img: boot.out
$(OBJCOPY) -O binary -j .text $< $@
boot.out: boot.o
${LD} -r -Ttext 0x7c00 -e _start -s -o boot.out boot.o
clean:
rm -f disk.img boot.out boot.o boot.map
編譯過程如下：$ make clean all rm -f desk.img boot.out boot.o boot.map as -a boot.S -o boot.o > boot.map ld -r -Ttext 0x7c00 -e _start -s -o boot.out boot.o objcopy -O binary -j .text boot.out disk.img注意到剛剛提及，BIOS 在控制權移轉時，會「載入各別開機磁碟裝置起始內容的 512 bytes 至記憶體位址 0x0000:7c00」，所以，在 GNU linker (ld) 的選項中，筆者特別讓組合語言的進入點 _start 對齊 .text 區域，也就是位址 0x7c00。最後，呼叫 objcopy 轉換目標程式碼為二進位格式，填入 boot sector 可接受的格式，這時可透過 qemu 來模擬開機的過程：
$ qemu -hda disk.img其模擬的畫面大致如下：
可見到系統畫面停留在我們給定的 "Hello World" 文字輸出。另外，在建構的過程中，筆者要求 GNU Assembler 也輸出 boot.map，也就是 "GAS LISTING"，其第一頁的最後幾行如下：
25 0026 B06C movb $'l', %al 26 0028 CD10 int $0x10 27 002a B064 movb $'d', %al 28 002c CD10 int $0x10 29 002e C3 ret 30 31 # Fill NOP instruction (opcde = 0x90) till base offset 0x1FE. 32 002f 90909090 .org 0x1FE, 0x90 32 90909090 32 90909090 32 90909090 32 90909090 33 34 # This indicates boot disk 35 01fe 55AA boot_flag: .word 0xAA55由上述表示可見，十六進位的 1FE + 2 bytes (作為識別用的 0x55 與 0xAA)，就等於十進位的 512 bytes，透過假指令，中間填補的 NOP 指令。
於是，這個「開機見 Hello World」的組合語言 boot sector 程式就完成了，包含 boot.S 與 Makefile 可自 [hello-boot.tar.bz2] 取得。
June 19, 2008
窺探 .bss section
幾年前只是對系統設計感到困惑，沒想到「分析 GCC 對 Hello World 的重重布幕」一類的舉動，竟成為激勵自我成長的目標，實在始料未及。拜 C 語言這種「披著高階語言羊皮的低階語言之狼」所賜，我們可透過稍早 blog [自我印列 ELF 簽名] 所提及的途徑，探索記憶體位址背後的意義。同樣地，我們也可從實驗觀察 GNU/Linux 中 ELF (executable and linkable format) 格式執行檔裡頭 .bss section 的呈現，關於這部份的背景知識，可參閱 Jollen 整理的 [.bss section：C 語言所種下的因] 與 [BSS Section 觀念教學] 等文章，本文則針對「窺探」的手法作補充。「窺探」ELF 執行檔有許多途徑，我們當然可用 binutils 裡面的 readelf / objdump 工具，但這裡我們直接用程式自我列印，筆者給定的程式如下：
#include <stdio.h> extern int __bss_start, _end; int a, b, c, d; /* un-initialized */ int main() { int *ptr; a = 1, b = 2, c = 3, d = 4; for (ptr = &__bss_start; ptr != &_end; ptr++) { printf("%d\n", *ptr); } return 0; }為行文便利，此小程式命名為 [bss.c]，咱們就先試著執行看看。在筆者的電腦安裝有 gcc 3.4 與 4.3 兩個版本，先用 gcc-3.4 看看：
$ gcc-3.4 -xc bss.c && ./a.out 0 4 1 2 3由上可見，C 語言程式碼中的 int a, b, c, d 在宣告的時候，並未給定數值，也就是「未作初始化」，這樣的變數在 ELF 的角度來看，就存放於 .bss section，而在 main() 中，這四個變數都在執行時期 (runtime) 被給定數值，上述的程式透過迴圈，將給定的 1, 2, 3, 4 等值都印列出來 (儘管順序不是預期的遞增排列，不過本文不會深入分析)，這是怎麼做到的呢？關鍵之處就在於一開始宣告的這行：
extern int __bss_start, _end;注意到此行前方的 "extern" 關鍵字，在 GNU Toolchain 會對名稱為 "__bss_start" 與 "_end" 的符號作特別處理，在預設的 linker script 中，會給定輸出 ELF 執行檔的 .bss section 的資訊，重點是，經過這樣的操作後，"__bss_start" 與 "_end" 只是 label 而非真正的變數，所以，並不佔用真正的記憶體空間。在 C 語言中，我們可取得其位址作指標的尋訪過程，以逐一得知 .bss section 各元素的內容值，這下似乎明暸了，但回顧剛剛的執行輸出，我們不免對其中的 "0" 感到困惑，是啊，這值到底從哪邊來？
在找尋答案之前，筆者改用 gcc-4.3 來作測試，其執行輸出如下：
$ gcc-4.3 -xc bss.c && ./a.out 0 0 4 1 2 3感覺起來就更離奇了，「又」多了一個 "0" 的輸出？！看來是 GNU Toolchain 對 ELF 執行檔額外施加了「魔法」，看來得搬出其他工具來分析。先觀察 objdump 對 .bss section 的分析：
$ gcc-3.4 -xc bss.c && objdump --section=.bss -x a.out ... SYMBOL TABLE: 08049598 l d .bss 00000000 .bss 08049598 l O .bss 00000001 completed.1 0804959c g O .bss 00000004 d 080495a0 g O .bss 00000004 a 080495a4 g O .bss 00000004 b 080495a8 g O .bss 00000004 c可以發現，事實上程式碼的 &__bss_start 勢必指向 ELF 執行檔透過 Program Loader 映射到記憶體中的 BSS 區域，而我們在程式中尋訪 .bss section 中的元素，大抵就是依照上面的 SYMBOL TABLE 的排列方式，而之前那個印列出的 "0" 數值，就是 "completed.1" 這個符號的內含值。同理，我們觀察透過 gcc-4.3 編譯時的分析結果：
$ gcc-4.3 -xc bss.c && objdump --section=.bss -x a.out ... SYMBOL TABLE: 0804a014 l d .bss 00000000 .bss 0804a014 l O .bss 00000001 completed.6625 0804a018 l O .bss 00000004 dtor_idx.6627 0804a01c g O .bss 00000004 d 0804a020 g O .bss 00000004 a 0804a024 g O .bss 00000004 b 0804a028 g O .bss 00000004 c在這份輸出中，我們看到形似剛剛 "completed.1" 的 "completed.6625" 符號，也多了名稱為 "dtor_idx.6627" 的符號。為了揭開謎團的真相，筆者又用 gcc-4.1 與 gcc-4.2 作實驗，這兩者得到與 gcc-3.4 編譯時相仿的輸出，但 "completed." 符號後方的數值名稱是不一樣的，由此可歸納，gcc-4.3 引入了一些我們未察覺的修改，而在 gcc-3.4 到 gcc-4.2 之間的 GNU Toolchain 所編譯的 ELF 執行檔，其 .bss section 也隱含我們不甚明暸的細節。
未完，待續
以 C 語言實做 Functional Language 的 Currying
在電腦科學的領域，Functional Language 的 Currying (也譯作「Curry 化」) 的正規定義為：(出自 [Wikipeida])-
「把接受多個參數的函數變換成接受一個單一參數(最初函數的第一個參數)的函數，並且返回接受餘下的參數而且返回結果的新函數的技術。
在 functional programming 中，絕大部分都在操作函數，也就是「操作函數的函數」或是「產生函數的函數」一類的行為，而 Currying function 則在當其參數不足時，先行合成另一個函數去處理其他參數，直到參數量足夠時，再行計算結果。舉例來說：
-
let f x y = x - y
-
let f' = f 3
[函數定義] f x y = x - y f(x, y) = x - y [函數定義] f' = f 3 f'(x) = 3 - x f'(2) 的返回值 = f(3, 2)看似平凡不過的推導，但在電腦科學的意義卻是非凡，因為這讓簡化的理論模型，如只接受單一參數的 lambda 得以處理多個參數的函數，當談及 Y Combinator 或者隱喻的遞迴操作，皆從此出發，進而開始璀璨的新頁，不過本文無意深入探索 Functional language，先行省略。
關鍵思維就是，上一個 Functor 處理參數的結果產生了下一個 Functor，下一個 Functor 繼續處理下一個參數，產生下一個 Functor，如此推廣下去。我們可進一步思考，Currying 的動作基本上就是讓一個函數得以 partially applied (術語為 partial application)，藉由新合成的函數作為回傳值，事實上，在 C++ STL (Standard Template Library) 與 C++ library [Loki] 中，即大量導入此思維，而在 Functional language 如 Lisp，給定的函數後可有一串參數，如 x, y, z, ...，我們可先行 partially apply 任意數量 (1 到 N 個) 的參數，獲得預期的功能，將功能本身予以抽象化處理。這樣的思維對真實環境下，應用程式的處理有什麼助益呢？舉例來說，檔案系統的操作，可能會有以下的行為：
- 計算所有檔案長度的總和
- 尋找目錄下最大或最小的檔案
- 尋找重複內容的檔案
def walk_dir(path_str, fun) path = Pathname.new(path_str) path.children.each do |entry| if entry.directory? fun = walk_dir(entry, fun) elsif entry.file? fun = fun.call(entry) end end return fun end如此一來，可封裝目錄操作，並一致化的處理，所以，若要實做取得目錄下所有檔案的空間，可這麼寫：
def cur_sum(sum) return lambda {|file| (file==nil) ? sum : cur_sum(sum + file.size)} end稍後再傳遞給尋訪的處理，如下：
puts walk_dir(ARGV[0], cur_sum(0)).call(nil)
同理，我們也可透過相近的手法，處理其他目錄層次的操作。不僅目錄尋訪可採用 Currying function 手法，對於資料庫也可，比方說知名的 Java ORM (Object-relational mapping) framework -- [hibernate] 裡頭的 Criteria Queries 就能應用 Currying 的形式如下：
SessionFactory.newSession(..).
newQuery(…).
setParameter(…).
setParameter(…)
即具有 Curry, Factory Chain 的形式特性。C++ 語言層面並未有 functional programming 的成份，但可透過模擬的方式處理，前述的 C++ STL 與 Loki 就是箇中經典範例，為此，台灣知名的技術作家 [jjhou] 曾多次撰文著述探討極其複雜的實作，集結於「泛型程式設計與 STL」主題，不過本文採用另一種輕巧的方式，並採用簡潔的 C 語言來實做。筆者模仿的對象是 Common Lisp 的語法，可參考其 cookbook 的 [Functions] 一節，筆者期望透過 C 語言模擬的 Currying 可如下操作：
typedef int (*intf)(); static int add(int x, int y) { return (x + y); } static int sub(int x, int y) { return (x - y); } int main() { intf ret; ret = curry(add, 1); printf("* (funcall (curry #'+ 1) 1)\n" "%d\n", (*ret)(1)); ret = curry(sub, 2); printf("* (funcall (curry #'- 2) 3)\n" "%d\n", (*ret)(3)); return 0; }筆者定義 intf 這個描述整數型態的 function pointer (容筆者囉唆一下，這當然是指 C 語言的語意)，在 main() 中建立一個實體 ret，並試著賦予以下操作：
ret = curry(add, 1);
printf("* (funcall (curry #'+ 1) 1)\n"
"%d\n", (*ret)(1));
這形式就符合前述「上一個 Functor 處理參數的結果產生了下一個 Functor，下一個 Functor 繼續處理下一個參數，產生下一個 Functor」，而且 curry() 的回傳值就是一個新的 function pointer，用以模擬「函數」的動作。那我們該如何實做這樣將 functional programming 與 C 語言橋接的 curry() function 呢？筆者的作法如下：
static char code[18] = { 0x55, /* push %ebp */ 0x89, 0xe5, /* mov %esp, %ebp */ 0xff, 0x75, 0x08, /* pushl 0x8(%ebp) */ 0x6a, 0, /* push $0x0 */ 0xe8, 0, 0, 0, 0, /* call <code+13> */ 0x83, 0xc4, 0x08, /* add $0x8, %esp */ 0xc9, /* leave */ 0xc3 /* ret */ }; int (*curry(intf Func, int arg))() { *(char*)(code + 7) = (char) arg; *(int*)(code + 9) = (int) Func - ((int) code + 9 + 4); return ((intf) code); }顯然，這段程式碼僅能在 IA32 上執行，不過要移植到其他平台，應該是相對單純的動作 (RISC 架構的話，stack 處理可簡化)。我們要掌握 Currying function 的形式與語意，所以筆者先建立一段 shellcode 範本，也就是 char code[]，將 Currying 的函數參數在 curry() function 中預先植入，並將函式本身的進入點也寫入 caller。不過，真正的技巧在於 IA32 stack 的處理，兩年前筆者在 [深入淺出 Hello World] Part II 的演講中已有提及，這裡再作簡要複習。
如上圖，IA32 的 stack 是段連續的記憶體空間的陣列表示，透過 stack 可用以支援 C 語言型態的程序呼叫，而所謂的 C 語言 function call，在 IA32 上，就是透過 %ebp 與 %esp 這兩個暫存器的操作來實現，示意圖如下：
當有新的項目堆入 (push) 到 IA32 stack 時，%esp 暫存器的內含值將會遞減，並將新項目寫入於 stack 的頂端；反之，當 pop 操作時，%esp 暫存器的內含值會遞增，並屏除頂端的項目。在 IA32 的規範，%ebp 為 frame / base pointer，%esp 為 stack pointer，通用暫存器 %eax 則用以表示 function 的回傳值，詳細的運作模式，可參閱 [x86 Assembly Guide]。
在筆者的 shellcode 範本：
static char code[18] = { 0x55, /* push %ebp */ 0x89, 0xe5, /* mov %esp, %ebp */ ... 0xc9, /* leave */ 0xc3 /* ret */ };省略的部份是 Currying function 的 function body 呼叫動作，而前半段稱為 prologue，後半段則是 epilogue。將 C 語言的程序呼叫對應到 IA32 stack 時，prologue 顧名思義，就是「序幕」的意思，即程序 / function 的開頭，有兩個動作需優先於其他動作前完成：
- 保存 caller (呼叫者 function) 的 frame pointer，存放到 IA32 stack，其組合語言就是 "push %ebp"
- 將目前的 stack pointer 設定為 callee (被呼叫的 function) 的 frame pointer，對應的組合語言就是 "movl %esp, %ebp"
- 將目前的 frame pointer (也就是 callee 的) 設定為 caller 的 stack pointer，對應的組合語言是 "movl %ebp, %esp"
- 自之前存放於 IA32 stack 的值取出，回復 caller 的 stack frame，對應的組合語言是 "popl %ebp"，不過，在 80286 以後 (含)，這兩個指令可被單一指令取代："leave"
- 當準備妥當後，"ret" 指令就可被執行，以返回 caller。注意，當 "leave" 指令被執行後，stack pointer 會指向 caller function 中透過 "call" 指令所推入 IA32 stack 的返回位址，因此，"ret" 指令實際上是自 IA32 stack 作 pop 出返回位址並跳躍到該位址執行，也就是 "pop eip" 的動作。
$ gcc -xc curry.c && ./a.out * (funcall (curry #'+ 1) 1) 2 * (funcall (curry #'- 2) 3) -1當然，這只是一個出發點，實務上可推廣到目錄檔案操作一類的應用。