November 29, 2009

開課資訊:Unix 系統程式設計

本學期,應 [修平技術學院] 資訊網路技術系系主任高國峰博士的邀請,合開「Unix 系統程式設計」的課程,小弟負責除錯與程式開發技巧的部份,從十一月中旬到十二月中旬的每週一 (11/16, 11/23, 12/7, 12/14, 12/21) 10:00-14:00,為該系學生介紹 GNU/Linux 平台下,GNU toolchain 與 gdb 的操作,希望能貫徹 John Dewey (1938) 的「做中學」理論,落實於 Unix 系統程式設計。

John Dewey 注重「做中學」的教育方法,教育才要注重實際經驗,要從做中學習。而在 GNU/Linux 的環境,寫程式本身是相當幸運的事,只要能掌握方法,從系統開發工具到上層的軟體,都唾手可得,有了 apt-get / yum 後,就好像電腦裝了超級市場一般,隨時隨地都可取得這些豐富的資源。第一週上課前,在教室外觀察學生十分鐘,發現不少學生在「種田」、「開餐廳」(開心農場用語),於是乾脆把課程專題目標設定為「打造山寨開心農場」,具體的目標如下:
  • 從一個具體而微的 Embedded AJAX 系統出發,透過 gdb 去追蹤分析,進而作擴充
  • 掌握 UNIX 系統程式開發的技巧
  • 擴充給定簡單的系統,實做出部份「開心農場」的功能
當然,既然已聲明是「山寨」版本,自然功能有限,但重點是享受親手打造與掌握度,所以,我們會從 web server, CGI, AJAX (前端) 都自己慢慢刻,使用 C 語言及 HTML/JavaScript,以下是初期的系統運作畫面:

由上圖可見,我們將實做簡單的 web server + CGI,以 AJAX 作為立即資料的呈現,並且提供 login / logging 等功能。那,為什麼不選定 Perl, Python, Ruby, PHP 等成熟的開發環境,反而堅持「慣 C」來作這樣的功能呢?筆者的考量點有三個:
  • 使用 C 語言撰寫系統,較能掌握系統運行的狀況,而不會迷失在程式語言 / framework 的特性中
  • 可隨時用 gdb 追蹤與除錯整個系統 (web server + CGI)
  • 向學生證明,只要短短幾百行,還是能做出符合期望的系統出來 (Just Work)
坊間有頗多 Unix 系統程式設計的教材,往往都是 API 導向,就是詳盡的探討 system call 的使用,卻鮮少一個案例可貫通系統程式,而本系列的課程,希望作些改變。感謝系主任高國峰博士給筆者這個機會,未來幾周我們將會繼續進行。
由 jserv 發表於 01:10 AM | 迴響 (5)

November 28, 2009

演講:下一站,Android (漫談 Android 平台移植與調校)


應 [KatDC] 之邀,小弟將於 12 月 12 日 (週六),於 [KOS Forum] 分享一場技術演講,題目定為「下一站,Android」,漫談 Android 平台移植與調校。KOS 議程的時段是 13:00 - 16:40,聽眾設定為對開發 Android 以及使用者經驗設計有興趣之專業人士。

正如《下一站,幸福》的評論所說:「真正讓我們記憶深刻的,是那動人或辛酸的片段」,凡從事 Android 平台移植與調校的開發者,無一不在那些動人與辛酸的程式碼片段中,獲得難以磨滅的記憶,代價可不是幾個晚上拼命加班而已,往往是無數家庭的共通故事。本議程由 [0xlab] 的開發者分享 Android 平台移植調校的經驗,舉凡與傳統 GNU/Linux 的相容性、硬體圖形加速、系統效能評估,到功能層面的改進。預定提綱:
  • 「下一站」到底有多遠?
  • 特立獨行的 Android:相容性探討
  • 系統效能分析與評估
  • 硬體圖形加速
  • 功能層面的改進:以無線通訊為例
這裡不打算深入技術細節,但著重於邁向「下一站」該注重的議題,以及如何運有既有的技術水平,提昇 Android 平台的可用性與效能。期待各位先進的指教,謝謝!
由 jserv 發表於 02:05 PM | 迴響 (0)

November 13, 2009

親手打造 Dynamic Library Loader

這幾個月又繼續設計 / 實做新的 Kernel (與相關的系統程式),貫徹「每年練習寫一個作業系統」的小目標,其中對 dynamic linker 的支援,是重要的特徵,本文則探討如何在 GNU/Linux 實做出 Dynamic Linker / Dynamic Library Loader (即 ld.so 與 libdl.so) 的功能,並以 ELF 執行檔格式作為探討對象,如此的概念可應用於 RTOS 與廣泛的嵌入式系統。

許多程式設計師都知道 dynamic linker,也知曉像是 LD_PRELOAD 的機制,但鮮少人真正瞭解其背後的內部工作原理,因為難題不僅是 linker 與 loader 的行為,而是在執行時期 (Runtime),要有種機制得以確保 dynamic linked 的程序中的函式 / 符號位址,已正確地指向了動態函式庫 (以下簡稱 "DLL" 或 DSO [Dynamic Shared object,UNIX 術語],本文不特別強調其分野) 裡頭的對應位址,基於如此考量,系統至少該具備以下的特徵:
  • PIC (Position Independent Code) : 簡單來說,DLL/DSO 本質上要能夠被載入到記憶體的任何有效的位址,也就是字面上 "Position Independent" 的意涵。而早期 UNIX 的 a.out 執行檔格式其實不是不能作 dynamic linker/loader,是被約束於 Position Dependent,也就是一定要被載入到特定的記憶體位址,才能運作,很沒有彈性,USL (UNIX SYSTEM Laboratories) 後來發展的 ELF 格式 (Executable and Linking Format) 就破除如此的限制。編譯器支援 PIC 的特徵 (gcc 的編譯選項是 "-fpic" / "-fPIC" ),會使輸出的 object code 與記憶體位址無關,並減少對絕對位址的使用。
  • 在執行時期才去處理符號 (變數與函式等):透過 ELF 裡頭的 symtab (symbol table) 與 relocation 機制去達成,也就是說,載入 DLL 的那一刻,其實無法執行程式本體,需要在解析 symtab 與對所有的位址都 relocation 後,才會真正去執行,而配合前述的 PIC,可大幅降低執行時期的開銷。當然,沒有 PIC,還是能做出 DLL/DSO,不過 relocation 的開銷就會相當可觀。
  • GOT (Global Offset Table) 的引入:要達到可用的 PIC,需要一份全域的 GOT,讓編譯器輸出的機械碼中,保留一個暫存器 (register) 去參照 GOT 這個排列好指向 symbol 位址的表格,如此一來,DLL/DSO 載入後,只需要一次的 relocation 即可得到全域的位址 (以 UNIX Process 的觀點)
實際上 PIC 與 GOT 的搭配,還有一些學問要探討,不過本文的方向則在「親手打造」,暫且先行忽略。接下來的篇幅,將在 i386 (IA32) 的 GNU/Linux 平台上,實做出 libdl.so 的關鍵功能,不依賴原本的 ld.so,理論上應該能快速移植到非 GNU/Linux 的系統。就 API 的角度來說,我們要實做出以下函式:
  • dlopen()
  • dlsym()
  • dlclose()
驗證我們親手打造的 Dynamic Library Loader 的方式:
  • 透過 dlopen() 將一個 ELF object code 載入並映射到記憶體,注意:為了簡化設計的難度,我們的實做將忽略 PIC/GOT
  • 透過 dlsym() 將稍早載入的 object code 中提取特定 symbol 的進入點 (UNIX Process 的函式位址),當然,這是做了 relocation 之後的位址
  • 傳遞必要的參數給指向前述位址的 function pointer,嘗試去執行,驗證其功能是否符合預期
  • 將 symbol 進入點作記憶體 dump,觀察其機械碼的排列方式
  • 以 dlclose() 將必要的資源釋放
在筆者的實做,這個特製的 Dynamic Library Loader 稱為 "ndl",自然前述的三個重要函式就被命名為 ndlopen(), ndlsym(), ndlclose(),以利辨識。先來看看測試的程式 (test-ndl.c):
#include <stdio.h>
#include "ndl.h"

/* dump machine code of loaded DSO */
static void dump(char *p);

int main()
{
    void *handle;

    /* add */
    handle = ndlopen("add.o");
    int (*fp_add) (int, int) = ndlsym(handle, "add");

    printf("add (%p):\n", fp_add);
    dump((char*) fp_add);

    printf("[add] 1 + 1 = %d\n", fp_add(1, 1));
    ndlclose(handle);

    printf("\n");

    /* hello */
    handle = ndlopen("hello.o");
    void (*fp_hello) (char *) = ndlsym(handle, "hello");
    char *msg = ndlsym(handle, "dyn_str");

    printf("hello (%p):\n", fp_hello);
    dump((char *) fp_hello);

    fp_hello("Hello World");
    fp_hello(msg);
    ndlclose(handle);

    return 0;
}

static void dump(char *p)
{
    int c = 0;
    while (*p != (char) 0xc3) { /* 'c3' = asm("ret") */
        printf("%02x ", (*p++) & 0xff);
        if (++c % 16 == 0)
            printf("\n");
    }
    printf("c3\n");
}
上述程式包含兩輪的測試,一個是載入 'add.o',另一個是 'hello.o',前者是簡單的算術操作,而後者涉及函式呼叫。對應的 DLL/DSO 程式碼列表:
jserv@venux:/tmp/ndl$ cat add.c 
int add(int x, int y)
{
	return x + y;
}
jserv@venux:/tmp/ndl$ cat hello.c
#include <stdio.h>

char dyn_str[] = "__DSO__";

void hello(char *s)
{
	printf("[hello] %s\n", s);
}
以下是參考的編譯與執行輸出:
jserv@venux:/tmp/ndl$ make
gcc -c hello.c -Os -Wall -fomit-frame-pointer -I./external
gcc -c add.c -Os -Wall -fomit-frame-pointer -I./external
gcc -o test_ndl test_ndl.c ndl.c dummy.c \
		/usr/lib/libbfd.a /usr/lib/libiberty.a -static \
		-Os -Wall -fomit-frame-pointer -I./external -Wl,-O1
jserv@venux:/tmp/ndl$ ./test_ndl 
	:: handle = 0x8e026a8
add (0x8e02854):
8b 44 24 08 03 44 24 04 c3
[add] 1 + 1 = 2

	:: reloc_name = __printf_chk
	:: handle = 0x8e02770
hello (0x8e029bc):
83 ec 10 ff 74 24 14 68 dc 29 e0 08 6a 01 e8 51 
a1 2f ff 83 c4 1c c3
[hello] Hello World
[hello] __DSO__
那麼上述的實驗中,有哪些該注意的細節呢?在深入探討筆者提出的 ndl 前,可以留意到:
  • 首先,'test_ndl' 這個程式本身是 statically linked,連結到 libbfd 與 libiberty 這兩個專門處理 ELF 的函式庫 (在 Debian/Ubuntu 裡頭,由套件 binutils-dev 所提供),並無連結到 libdl,而是採用我們親手打造的函式
  • 一般 statically linked 的程式無法使用 dlopen(),但我們的程式沒有如此限制,仍可在動態時期載入 DSO 並處理 symbol 與 relocation
  • 迴避 PIC/GOT 的細節,編譯參數沒有 -fpic 或 -fPIC
  • 'add.o' 與 'hello.o' 的差別在於,'hello.c' 有呼叫到 printf() 的動作,這致使執行時期仍需要多作一個 relocation,此動作需要在實際呼叫被載入的 hello() 前準備好,否則無法運作
讓我們觀察看看 'add.o' 與 'hello.o' 在 ELF 檔案中的資訊,可透過 binutils 的 readelf 工具程式分析:
jserv@venux:/tmp/ndl$ readelf -r add.o

There are no relocations in this file.
jserv@venux:/tmp/ndl$ readelf -r hello.o

Relocation section '.rel.text' at offset 0x368 contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000008  00000501 R_386_32          00000000   .rodata.str1.1
0000000f  00000902 R_386_PC32        00000000   __printf_chk
由此可見,'hello.o' 所呼叫的 printf() 函式主體其實位於 statically-linked 的 'test-ndl' 執行檔中,而 printf() 的符號在編譯時期被替換為 '__printf_chk'。readelf 工具程式告訴我們,'hello.o' 在 Relocation section '.rel.text' 有兩個符號,對照於 'hello.c':
  • '.rodata.str1.1' 即 "[hello] %s\n" (傳遞給 printf() 的參數),型態為 R_386_32 (absolute 32-bit)
  • '__printf_chk' 即 printf(),其型態為 R_386_PC32 (PC relative 32 bit signed)
而在 'add.o' 中,自然是沒有額外的 relocations 操作。倘若我們再比對 ndl 所載入的 'hello.o' 與 ELF 的 .text section,就可獲得驗證,使用 objdump 工具:
jserv@venux:/tmp/ndl$ objdump -xd hello.o 

hello.o:     file format elf32-i386
hello.o
architecture: i386, flags 0x00000011:
HAS_RELOC, HAS_SYMS
start address 0x00000000
...
Disassembly of section .text:

00000000 <hello>:
   0:	83 ec 10             	sub    $0x10,%esp
   3:	ff 74 24 14          	pushl  0x14(%esp)
   7:	68 00 00 00 00       	push   $0x0
			8: R_386_32	.rodata.str1.1
   c:	6a 01                	push   $0x1
   e:	e8 fc ff ff ff       	call   f <hello+0xf>
			f: R_386_PC32	__printf_chk
  13:	83 c4 1c             	add    $0x1c,%esp
  16:	c3                   	ret
對照於 test_ndl 的輸出:
hello (0x8e029bc):
83 ec 10 ff 74 24 14 68 dc 29 e0 08 6a 01 e8 51
a1 2f ff 83 c4 1c c3
就再清楚不過了,'hello' symbol 的反組譯自 '83' 'ec' 10' (sub $0x10,%esp) 開始到 c3 (ret) 為止,都被載入到記憶體,並做了必要的 relocation。以下是簡要探討 ndlopen(), ndlsym(), ndlclose() 的實做,詳情可參閱原始程式碼 [ndl.tar.bz2]。

在原始程式 ndl.c 中,我們引入 libelf 所提供的 bfd.h 檔頭 (BFD, the Binary File Descriptor library),並宣告兩個結構體,供後續使用:
typedef struct {
    const char *name;
    void *fp;
} ndl_sym_t;

typedef struct {
    htab_t syms;
    char *map;
    size_t length;
} ndl_t;
在 API 的實做則是:
void *ndlsym(void *h, const char *symbol)
{
    ndl_t *handle = (ndl_t *) h;
    ndl_sym_t **sym;
    void *addr;
    sym = (ndl_sym_t **) htab_find_slot(handle->syms, symbol, NO_INSERT);
    if (! sym)
        return NULL;
    addr = (*sym)->fp;
    mprotect((void *)((((int) addr + 4095) & ~4095) - 4096),
             4096, PROT_READ | PROT_WRITE | PROT_EXEC);
    return addr;
}

void ndlclose(void *h)
{
    ndl_t *handle = (ndl_t *) h;
    free(handle->map);
}
ndlsym() 與 ndlclose() 的實做就相當顯然了,只要 dlopen() 能將 ELF 必要的欄位與資訊填入前述的資料結構,那麼就是作必要的查表動作即可,需要留意的是 mprotect() 的呼叫,因為我們要將對照後的記憶體位址區段標示為「可讀、可寫、可執行」(x86 的特性)。dlopen() 的實做稍微複雜一點,不過重點是實做 load_relocs() 函式,其接受指向 ndl_t 結構的 handle,以及指向已開啟 ELF object code 的 bfd 結構的 abfd 兩個參數。程式碼列表如下:
static int load_relocs(ndl_t *handle, bfd *abfd)
{
    int size, i;
    asection *sect = bfd_get_section_by_name(abfd, ".text");
    arelent **loc;

    size = bfd_get_reloc_upper_bound(abfd, sect);
    if (size < 0) {
        bfd_perror("bfd_get_reloc_upper_bound");
        return 1;
    }

    loc = (arelent **) malloc(size);

    size = bfd_canonicalize_reloc(abfd, sect, loc, g_syms);
    if (size < 0) {
        bfd_perror("bfd_canonicalize_reloc");
        return 1;
    }

    for (i = 0; i < size; i++) {
        arelent* rel = loc[i];
        void **p = (void **) (handle->map + sect->filepos + rel->address);
        const char *name;
        if (!rel->sym_ptr_ptr || !*(rel->sym_ptr_ptr))
            continue;
        name = (*(rel->sym_ptr_ptr))->name;
        if (!name || !name[0])
            continue;

        /* section */
        if (name[0] == '.') {
            asection* s = bfd_get_section_by_name(abfd, name);
            *p = handle->map + (int)*p + s->filepos + rel->addend;
        }
        /* function */
        else {
            *p = lookup_func_table(name, p);
            printf("\t:: reloc_name = %s\n", name);
        }
    }
    free(loc);

    return 0;
}
回顧筆者提到 Relocation section '.rel.text' 有兩個符號:'.rodata.str1.1' 與 '__printf_chk',前者以 '.' (句點) 開頭者,為 section,否則為 function,再回顧 objdump 的輸出:
jserv@venux:/tmp/ndl$ objdump -xd hello.o
...
SYMBOL TABLE:
00000000 l    df *ABS*	00000000 hello.c
00000000 l    d  .text	00000000 .text
00000000 l    d  .data	00000000 .data
00000000 l    d  .bss	00000000 .bss
00000000 l    d  .rodata.str1.1	00000000 .rodata.str1.1
00000000 l    d  .note.GNU-stack	00000000 .note.GNU-stack
00000000 l    d  .comment	00000000 .comment
00000000 g     F .text	00000017 hello
00000000         *UND*	00000000 __printf_chk
00000000 g     O .data	00000008 dyn_str
...
而作為一個 dynamic library loader,ndl 的工作就是基於這兩項,做出正確的查詢動作,以 BFD 提供的函式,將正確的位址找出。有趣的是,既然 printf() 在編譯時期被轉換為 '__printf_chk' 這個 symbol,而 'hello.o' 本身卻只有 undefined symbol (即上列 objdump 輸出的 '*UND*'),其實做在哪呢?就在 test_ndl.c 中,在編譯為 statically-linked 程式時,gcc 默默的將一份 '__printf_chk' 實做碼 (來自 GNU glibc) 連結到 test_ndl 這個應用程式。我們的 load_relocs() 中,針對函式的查詢則用輕便的方式:窮舉法,以下是原始程式碼:
static inline void *lookup_func_table(const char *func_name, void **ptr)
{
    if (0 == strcmp(func_name, "printf"))
        *ptr = (void *)((unsigned int) &printf -
                        (unsigned int) ptr - 4);
    else if (0 == strcmp(func_name, "puts"))
        *ptr = (void *)((unsigned int) &puts -
                        (unsigned int) ptr - 4);
    else if (0 == strcmp(func_name, "__printf_chk"))
        *ptr = (void *)((unsigned int) &__printf_chk -
                        (unsigned int) ptr - 4);
    else {
        /* FIXME: handle uncaught function entries */
    }
    return *ptr;
}
當然,筆者這麼作,實在是相當偷懶,但對一個 self-contained 的環境來說,應已足夠,需要留意的是 frame pointer 的操作,所以適度要調整進入點的位置:"ptr - 4"。正如前述所及,完整的 dynamic linker/loader 需要考慮相當多細節,但本文用最簡便的方式,提供可行且易於分析的途徑,未來筆者會再探討涉及作業系統與函式庫的議題。
由 jserv 發表於 10:14 AM | 迴響 (1)

November 04, 2009

打造 Brainfuck 的 JIT compiler

Brainfuck 是種極為精簡的程式語言,由 Urban Müller 在 1993 年發展。Urban Müller 當初的目標為提出一種簡單的、可用最小的編譯器來實現、符合 Turing complete 的程式。最早在 Amiga 機器上撰寫的編譯器只有 240 bytes 的大小,而 Brian Raiter 在 1999 年甚至於 i386/Linux 機器上做出僅需 166 bytes 的 Brainfuck 編譯器,詳情可見 [bf.asm]。

既然 Brainfuck 是符合 Turing complete 的程式語言,理論上可進行任何運算動作,可查看 Wikipedia 的 [Brainfuck] 詞目理解其簡潔的語法與設計,本文不贅述。作為一個「知易行難」的程式語言,Brainfuck 僅有八個指令,其中兩個是 I/O 動作。作為 Turing machine 的實踐,Brainfuck 對記憶體單元作直接的存取,對應到 C 語言的概念來說,如果 char *p 指向記憶體區塊的話,Brainfuck 語言的八個指令可對照為以下: (Brainfuck vs. C)
Brainfuck C
> ++p;
< --p;
+ ++*p;
- --*p;
. putchar(*p);
, *p = getchar();
[ while (*p) {
] }
也就是說,下方的 Brainfuck 程式碼:
    +++++[-]
    
對應為 C 語言程式碼為:
     *p=+5;
     while(*p != 0){
          *p--;
     }
體解「知易行難」的 Brainfuck,最好還是多練習,可搭配 [Brainfuck JS (interpreter & debugger)] 這強大的互動環境。

撰寫 Branfuck 編譯器是相當容易的,比方說,如果我們將 C 語言當作是 Brainfuck 的組合語言碼輸出 (事實上 LLVM 也有 C backend),那麼這動作就如上述的對應表一般,可一對一轉換,只要用 sed 一類的工具即可達到,以下是一個簡單的實做: [bf2c.sed]
#! /bin/sed -f
s/[^][+<>.,-]//g
s/\([-+]\)/\1\1*p;/g
s/</p--;/g
s/>/p++;/g
s/\./putchar(*p);/g
s/,/*p=getchar();/g
s/\[/while (*p) {/g
s/\]/}/g
1s/^/#include <stdio.h>\
int main(void){char *p=calloc(1,10000);/
$s/$/}/
Wikipedia 上那個經典的 Brainfuck 版本的 Hello World 程式 (需要留意的是,在 Brainfuck 中,寫一個 UNIX "cat" 工具程式,遠比寫 Hello World 簡單):
    ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
    >++.>+.+++++++..+++.>++.<<+++++++++++++++.
    >.+++.------.--------.>+.>.
就得到以下的「編譯」結果:
    #include <stdio.h> int main(void){char *p=calloc(1,10000); ++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; while (*p) {p++;++*p;++*p;++*p;++*p;++*p;++*p;++*p; p++;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; p++;++*p;++*p;++*p;p++;++*p;p--;p--;p--;p--;--*p;} p++;++*p;++*p;putchar(*p);p++;++*p;putchar(*p);++*p; ++*p;++*p;++*p;++*p;++*p;++*p;putchar(*p);putchar(*p); ++*p;++*p;++*p;putchar(*p);p++;++*p;++*p;putchar(*p); p--;p--;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; ++*p;++*p;++*p;++*p;++*p;++*p;putchar(*p);p++;putchar(*p); ++*p;++*p;++*p;putchar(*p); --*p;--*p;--*p;--*p;--*p;--*p;putchar(*p); --*p;--*p;--*p;--*p;--*p;--*p;--*p;--*p;putchar(*p); p++;++*p;putchar(*p);p++;putchar(*p);}
當然,編譯器不是查表對照而已,還得涉及到 relocation 與 optimization 的議題,這些稍候筆者再來討論。稍早筆者介紹過 [AsmJit : C++ 封裝的 Just-In-Time Assembler] 後,大鳥就做了一個 [JustFuck, A x86 Just-In-Time Compiler for Brainfuck],透過執行時期的行為,一邊分析 Brainfuck 的八個指令,一邊動態產生對應的機械碼,這真是個很不錯的範例實做

除了 [AsmJit],使用 [Xbyak] (New BSD License) 也是相當好的選擇,可快速以此 x86 / x86_64 JIT assembler 實現 Brainfuck 語言的 Just-in-Time compiler。以下是一個具體的 Brainfuck JIT 實做,適用的平台是 x86/Linux: (完整的套件在 [bfjit-x86.tar.bz2])
#include "xbyak/xbyak.h"
#include <stdio.h>

#include <stdlib.h>
#include <stdint.h>
#include <stack>
#include <fstream>

class Brainfuck : public Xbyak::CodeGenerator {
private:
    enum Direction { B, F };
    const char *toStr(int labelNo, Direction dir) {
        static char num[64];
        snprintf(num, sizeof(num), "%c%d", dir == B ? 'B' : 'F', labelNo);
        return num;
    }

public:
    int getContinuousChar(std::istream& is, char c) {
        int count = 1;
        char p;
        while (is >> p) {
            if (p != c) break;
            count++;
        }
        is.unget();
        return count;
    }
    Brainfuck(std::istream& is) : CodeGenerator(50000) {
        using namespace Xbyak;
        const Reg32& pPutchar(esi);
        const Reg32& pGetchar(edi);
        const Reg32& stack(ebp);
        const Address cur = dword [stack];
        push(ebp); // stack
        push(esi);
        push(edi);
        const int _P = 4 * 3;
        mov(pPutchar, ptr[esp + _P + 4]); // putchar
        mov(pGetchar, ptr[esp + _P + 8]); // getchar
        mov(stack, ptr[esp + _P + 12]); // stack
        int labelNo = 0;
        std::stack<int> keepLabelNo;
        char c;
        while (is >> c) {
            switch (c) {
            case '+':
            case '-':
                {
                    int count = getContinuousChar(is, c);
                    if (count == 1) {
                        c == '+' ? inc(cur) : dec(cur);
                    } else {
                        add(cur, (c == '+' ? count : -count));
                    }
                }
                break;
            case '>':
            case '<':
                {
                    int count = getContinuousChar(is, c);
                    add(stack, 4 * (c == '>' ? count : -count));
                }
                break;
            case '.':
                push(cur);
                call(pPutchar);
                pop(eax);
                break;
            case ',':
                call(pGetchar);
                mov(cur, eax);
                break;
            case '[':
                L(toStr(labelNo, B));
                mov(eax, cur);
                test(eax, eax);
                jz(toStr(labelNo, F), T_NEAR);
                keepLabelNo.push(labelNo++);
                break;
            case ']':
                {
                    int no = keepLabelNo.top(); keepLabelNo.pop();
                    jmp(toStr(no, B));
                    L(toStr(no, F));
                }
                break;
            default:
                break;
            }
        }
        pop(edi);
        pop(esi);
        pop(ebp);
        ret();
    }
};

int main(int argc, char *argv[])
{
    if (argc == 1) {
        fprintf(stderr, "bf filename.bf [0|1]\n");
        return 1;
    }
    std::ifstream ifs(argv[1]);
    Brainfuck bf(ifs);
    static int stack[32768];
    ((void (*)(void*, void*, int *)) bf.getCode())(
               (void *) putchar, (void *) getchar, stack
    );
    return 0;
}
額外打上以下的 patch,可得知 JIT compiler 輸出的 x86 機械碼:
--- bfjit.cpp	2009-11-04 07:44:18.000000000 +0800
+++ bfjit-dump.cpp	2009-11-04 07:50:07.000000000 +0800
@@ -94,6 +94,31 @@ public:
     }
 };

+void dump(const uint8_t *code, size_t size)
+{
+    puts("#include <stdio.h>\n"
+            "static int stack[32768];\n"
+            "static const unsigned char code[] = {");
+    for (size_t i = 0; i < size; i++) {
+        printf("0x%02x,", code[i]); if ((i % 16) == 15) putchar('\n');
+    }
+    puts("\n};");
+#ifdef __linux__
+    puts("#include <unistd.h>");
+    puts("#include <sys/mman.h>");
+#endif
+    puts("main()\n{");
+#ifdef __linux__
+    puts("\tlong pageSize = sysconf(_SC_PAGESIZE) - 1;");
+    puts("\tmprotect((void*)code, (sizeof(code) + pageSize) & ~pageSize, PROT_READ | PROT_EXEC);");
+#endif
+    puts(
+            "\t((void (*)(void*, void*, int *))code)("
+            "\t\t(void*)putchar, (void*)getchar, stack);\n"
+            "}"
+        );
+}
+
 int main(int argc, char *argv[])
 {
     if (argc == 1) {
@@ -101,10 +126,16 @@ int main(int argc, char *argv[])
         return 1;
     }
     std::ifstream ifs(argv[1]);
+    int mode = argc == 3 ? atoi(argv[2]) : 0;
     Brainfuck bf(ifs);
-    static int stack[32768];
-    ((void (*)(void*, void*, int *)) bf.getCode())(
-               (void *) putchar, (void *) getchar, stack
-    );
+    if (mode == 0) {
+        static int stack[32768];
+        ((void (*)(void*, void*, int *)) bf.getCode())(
+                   (void *) putchar, (void *) getchar, stack
+        );
+    } else {
+        dump(bf.getCode(), bf.getSize());
+    }
     return 0;
 }
+
其實,Brainfuck 與其說是程式語言,不如說是一種硬體架構的實現 (Turing machine),知名的編譯器開發計畫 [LLVM] 也包含一個 Brainfuck 的範例,作為一個 front-end,掛入 LLVM IR (中間表示),進而與 LLVM 豐富的編譯器元件作整合。
由 jserv 發表於 09:30 AM | 迴響 (4)