2011年12月22日 星期四

Lua for UEFI

利用點空閒時間將Lua移植到UEFI,作成一支Shell Application,直接執行不帶參數的話可以直接在銀幕上輸入Script,二次Enter後直接執行,執行結果立即顯示在畫面上。


按照慣例,當然要弄個Game來玩玩,所以再把Good裡的打磚塊範例拿來稍微改一下。

這下子,在UEFI下也能打磚塊了!

2011年12月13日 星期二

以yardparser實作算式計算機

這篇文章是算式計算機系列的完結篇。
  1. (E)BNF表示式
  2. 手工打造算式計算機
  3. 以lex/yacc實作算式計算機
  4. 以Boost.Spirit實作算式計算機

;

(下載範例)

yardparser在使用上雖然沒辨法像Boost Spirit 一樣那麼直覺便利,可以將EBNF 語法規則直接定義在程式裡建立解析器,但使用類似的手法一樣可以將EBNF語法規則轉換為程式定義,建立一個語法解析器。yardparser也沒辨法像Boos Spirit那樣,可以在執行時期(run-time)動態的改變或產生新的解析器。除了上述的不同處之外,最大的差異是 yardparser 的編譯時間非常短及以 yardparser建立的parser執行速度非常快,同時產生的目的碼大小(code size)也相對小很多。

Boost Spirit 因為大量使用了 C++ Template Meta-programming 的相關技術,很完美的將EBNF語法規則語句嵌入到C++程式碼內和我們所寫的程式碼結合在一起,相當直覺也相當神奇。只不過如果從得到的編譯時間和執行效率來看,只能說 Boost Spirit 為我們提供了相當出色的語法糖(syntactic sugar),對於大型複雜的語法來說反而較難以適用。而 yardparser 雖然在使用上不如Boost Spirit那樣直覺便利,但至少在編譯時間和執行效率是大大滿足我們日常工作的需求。

底下同樣以簡單範例開始,介紹yardparser的基本使用。

A B

上面是原EBNF表示式的寫法,用來表示一個序列,在 A之後會有個B。而使用yardparser 則寫成如下的形式。

struct AB : CharSeq<'A', 'B'>
{
};

CharSeq 是 yardparser裡面事先定義好的 一個struct,作用是對輸入來源串流讀入字元來進行匹配動作。

(AB)*

以上定義了零個以上個AB序列的EBNF表示式的寫法,底下一樣轉換成yardparser的寫法。

struct StarAB : Star<AB>
{
};

AB是上一個例子裡定義,用來匹配 AB序列的規則。而Star是yardparser事先定義的一個struct,把AB作為它的參數,就能夠用來匹配零個以上的AB序列。

(AB)+

類似Star的語法,Plus是匹配一個以上的規則。

struct PlusAB : Plus<AB>
{
};

以上的規則定義用來檢驗匹配至少有一個以上的AB序列。

(AB)?

加上問號(?)表示這條規則是可有可無的(optional),或者換句話說AB序列出現的次數可以是零次或一次。轉換成yardparser的語法,如下所示。

struct OptionalAB : Opt<AB>
{
};

內建parser

yardparser 也內建了許多有用的parser,這些parser 或規則都以C/C++的struct 型式定義,主要可分為二大類。一類是基本規則,如 CharSeq、Star、Plus 等。另一類是 parser 類,如Digit、AlphaNum、Word等。除此之外包含於yardparser的範例中也內建了完整的C語言語法可以直接拿來應用,如DecNumber、Tok、Literal等。

底下列出常用基本語法規則。

Seq匹配序列
CharSeq匹配字元序列
CharSet匹配其中一個字元
CharSetRange匹配字元範圍中的一個
Star零個以上匹配
Plus一個以上匹配
Opt零個或一個匹配
Notboolean not
Orboolean or
True_tboolean true
False_tboolean false

底下是一些簡單的範例。

abstruct AB : CharSeq<'a', 'b'> {};
abcstruct ABC : CharSeq<'a', 'b', 'c'> {};
abc*struct ABandCstar : Seq<AB, Star<Char<'c'> > > {};
abc+struct ABandCplus : Seq<AB, Plus<Char<'c'> > > {};
bcstruct BC : CharSeq<'b', 'c'> {};
a(bc)+struct AandBCplus : Seq<Char<'a'>, Plus<BC> > {};
[abc]struct AorBorC : CharSet<'a', 'b', 'c'> {};
[a-z]struct AtoZ : CharSetRange<'a', 'z'> {};

下面是定義在c_grammer內的常用parser。

WS空白字元
DecNumber實數
HexNumber以0x開頭定義的十六進制數字
CharTok匹配字元,以空白字元斷開
Literal字面常數,包含數字文字等

動作程式碼

yardparser加入動作程式碼的方式和Boost Spirit的方式並不相同。底下以一個簡單的例子作比較,分別使用Boost Spirit及yardparser實作如下所列的簡單規則。

S = integer

底下是使用Boost Spirit的實作。

void get_int(int i)
{
}

rule<> S = int_p [&get_int];

可以看到以Boost Spirit實作的S解析器中,語法及動作程式碼的部份是各自獨立的。我們可以很容易的把動作程式碼([&get_int])的部份從語法S裡去掉,rule S仍然可以運作,因此在真正為語法加上動作程式碼之前就已經可以開始對語法測試,因此可以等到所有語法都完成實作後再回過頭來加入動作程式碼。

現在再來看看yardparser對S的實作。

struct Integer
{
};

struct Factor : Or<Integer, ...>
{
};

從上面的範例中可以看到,yardparser的動作程式碼定義形式和一般的語法定義形式是同樣的,也就是在yardparser中動作程式碼可以視為是一特殊的語法解析器,它並不是用作在語法的匹配上,而是用於執行對應於語法規則上的操作。以上所示範例是一個最簡單的情況,而實際上常見的情況是動作程式碼會和語法規則夾雜在一塊,這在最後實際實作算式計算機時即可見到,在這方面 yardparser 和Boost Spirit比較起來就沒那麼簡單直覺。

現在來看看yardparser的parser原型(prototype)。

struct parser
{
  template<typename ParserState_t>
  static bool Match(ParserState_t& p);
};

在yardparser裡面每一個parser都定義成一個struct,struct裡面定義一個回傳值型別是bool名稱叫作Match的static函數。這條Match函數就是yardparser的核心函數,用來作語法匹配,底下透過一個簡單的範例來看看它是如何使用。

struct Integer
{
    template<typename ParserState_T>
    static bool Match(ParserState_T& p)
    {
        const char* p0 = p.GetPos();
        if (c_grammer::DecNumber::Match(p))
        {
            string s(p0, p.GetPos());
            int n = atoi(s.c_str());
            return true;
        }
        return false;
    }
};

如上面的簡單範例,Integer 定義了 Match 方法,在 Match 方法中透過 yardparser 內建的c_grammer中的DecNumber解析器來匹配數字。如果DecNumber的Match方法回傳成功,則表示目前匹配的字串是一個數字。不像是Boost Spirit的動作程式碼那麼直接,每一個動作程式碼函數的參數本身就已是轉換好的資料,可以直接使用,yardparser的動作程式碼需要自行將這個數字由字串裡抽取出來,轉換成內部資料儲存。

使用yardparser實作算式計算機

如下所列 ,寫下算式計算機的EBNF表示式。

factor     := integer | '(' expression ')'
term       := factor (('*' factor) | ('/' factor))*
expression := term (('+' term) | ('-' term))*

首先將以上的EBNF表示式轉換為使用yardparser定義,不帶動作程式碼,如下。

struct Factor : Or<Integer, Seq<Char<'('>, Expression, Char<')'> > > {};
struct Term : Seq<Factor, Star<Or<Seq<Char<'*'>, Factor>, Seq<Char<'/'>, 

Factor> > > > {};
struct Expression : Seq<Factor, Star<Or<Seq<Char<'+'>, Term>, 
Seq<Char<'-'>, Term> > > > {};

轉換後的yardparser程式定義如果沒有問題的話,應該能夠順利通過編譯,而且已經可以實際用來解析算式語法,只不過還沒加上動作程式碼所以還不能有真正的作用。

以下開始加上動作程式碼。如同前面的範例,需要加上動作程式碼的地方有五處,其中一個是將數字取出,以及加減乘除四種運算。取出數字的動作程式碼在上一節中已列出,底下說明如何加入加減乘除運算的動作程式碼。如下所示定義為加上動作程式碼後的語法程式定義。

struct Factor : Or<Integer, Seq<Char<'('>, Expression, Char<')'> > > {};
struct Term : Seq<Factor, Star<Or<DoMul<Seq<Char<'*'>, Factor> >, 
DoDiv<Seq<Char<'/'>, Factor> > > > > {};
struct Expression : Seq<Term, Star<Or<DoAdd<Seq<Char<'+'>, Term> >, 
DoSub<Seq<Char<'-'>, Term> > > > > {};

以上四個動作程式碼:DoMul、DoDiv、DoAdd及DoSub 分別為四種運算的動作程式碼。可以很明顯的看出來,加上動作程式碼後,沒辨法像使用Boost Spirit一樣一眼就能夠分辨出那一部份是語法,那一部份是動作程式碼。

最後加上一個用來作運算的數字堆疊,再整合Integer及四則運算的動作程式碼,完成算式計算機實作,其它部份程式碼如下所示。

vector<int> stack;
template<class RuleT>
struct DoMul
{
    template<typename ParserState_T>
    static bool Match(ParserState_T& p)
    {
        if (RuleT::Match(p))
        {
            stack[stack.size() - 2] *= stack[stack.size() - 1];
            stack.pop_back();
            return true;
        }
        return false;
    }
};

template<class RuleT>
struct DoDiv
{
    template<typename ParserState_T>
    static bool Match(ParserState_T& p)
    {
        if (RuleT::Match(p))
        {
            stack[stack.size() - 2] /= stack[stack.size() - 1];
            stack.pop_back();
            return true;
        }
        return false;
    }
};

template<class RuleT>
struct DoAdd
{
    template<typename ParserState_T>
    static bool Match(ParserState_T& p)
    {
        if (RuleT::Match(p))
        {
            stack[stack.size() - 2] += stack[stack.size() - 1];
            stack.pop_back();
            return true;
        }
        return false;
    }
};

template<class RuleT>
struct DoSub
{
    template<typename ParserState_T>
    static bool Match(ParserState_T& p)
    {
        if (RuleT::Match(p))
        {
            stack[stack.size() - 2] -= stack[stack.size() - 1];
            stack.pop_back();
            return true;
        }
        return false;
    }
};

int main(void)
{
    std::string str;
    while (getline(cin, str))
    {
        if (str.empty() || str[0] == 'q' || str[0] == 'Q')
            break;
        SimpleTextParser parser(str.c_str(), str.c_str() + str.length());
        if (!parser.Parse<Seq<Expression, EndOfInput> >())
            break;
        cout << str << " = " << stack.back() << "\n";
        stack.clear();
    }
    return 0;
}

注意到上述的實作裡,將字元 parser Char 改為 CharTok,目的是允許在字元間可以插入額外空白,CharTok由c_grammer集合所提供。


(下載範例)

2011年12月5日 星期一

以ListView元件的VirtualMode實作TreeListView

(下載範例)

在.NET framework裡面的System.Windows.Forms元件家族中有一般常見的TreeView元件及ListView元件,但卻沒有結合這兩者的TreeListView元件或ListTreeView元件。網路上可以找到很不錯的資源,這裡另外介紹一個簡單的方式,可以透過現有的機制實作TreeListView特性。

在.NET裡的ListView元件有一個VirtualMode,它的功能是由user自行管理ListViewItem內容。當VirtualMode啟動時,ListView元件會透過RetrieveVirtualItem事件向user要指定序號的ListViewItem。透過這一層機制,就能向我們提供一個彈性,稍加應用就能用以製作TreeListView元件功能。

下面這個範例(C#),使用ListView元件的VirtualMode,模倣VisualStudio在debug時的LocalVariable視窗,如面圖所示。


首先建立內部資料結構,TreeListItem。
class TreeListItem
{
  public int Level = 0;
  public string Name;
  public string Value;
  public string Type;
  public List Child = new List();
  public bool Expand = false;
  public TreeListItem AddChild(string n, string v, string t)
  {
    TreeListItem c = new TreeListItem();
    c.Name = n;
    c.Value = v;
    c.Type = t;
    c.Level = this.Level + 1;

    Child.Add(c);

    return c;
  }
}
Level是用來表示階層,Child串列儲存下一個階層的子項目,而Expand則用來表示在Tree中這個項目是打開或關閉的將態。AddChild用來幫助加入一個子項目。

每當ListView元件內容變更時,我們需要手動去改變VirtualListSize的值,這時ListView元件就會透過RetrieveVirtualItem事件,向我們獲得每一個項目的內容。

在設定VirtualListSize的值之前,我們另外需要一個串列,用來存放每一個展開的可見的項目,這是為了方便同時也簡單實作。這個串列的內容,是根據已建立好的樹狀的項目資料,以遞迴方式展開取得。
TreeListItem Root = new TreeListItem();
Root是一個虛擬的項目,用來存放全部的資料內容。在範例程式開始時,會ctor裡事先建立完成。
  TreeListItem cThis = Root.AddChild("this", "{TreeListView.Form1, Text: }", "TreeListView.Form1");
  TreeListItem cRoot = cThis.AddChild("Root", "{TreeListView.Form1.TreeListItem}", "TreeListView.Form1.TreeListItem");
  TreeListItem cChild = cRoot.AddChild("Child", "Count = 0", "System.Collections.Generic.List");
  cChild.AddChild("Row View", "", "");
  cRoot.AddChild("Expand", "false", "bool");
  cRoot.AddChild("Level", "0", "int");
  cRoot.AddChild("Name", "null", "string");
  cRoot.AddChild("Value", "null", "string");
以上會建立如下結構的資料。
this
  Root
    Child
      Root View
    Expand
    Level
    Name
    Value
下面的程式碼定義BuildVirtualItems,根據目前的Expand狀態以遞迴方式重建VirtualItems串列,然後重設ListView元件的VirtualListSize值。
List VirtualItems = new List();

void BuildVirtualItems()
{
  VirtualItems.Clear();

  BuildVirtualItems(Root.Child);

  listView1.VirtualListSize = VirtualItems.Count;
}

void BuildVirtualItems(List Items)
{
  for (int i = 0; i < Items.Count; i++)
  {
    VirtualItems.Add(Items[i]);

    if (Items[i].Expand)
      BuildVirtualItems(Items[i].Child);
  }
}
當ListView元件的VirtualListSize的值被改變後,ListView元件會以RetrieveVirtualItem事件去取得新的項目內容。在RetrieveVirtualItem裡只需簡單的以事件參數傳遞進來的項目索引值到VirtualItems串列裡去抓出項目資料,以這筆資料新建一個ListViewItem物件回傳即可。
private void listView1_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
{
  TreeListItem c = VirtualItems[e.ItemIndex];

  string Name = "";

  for (int i = 0; i < c.Level; i++)
    Name += "  ";

  if (0 < c.Child.Count)
  {
    if (c.Expand)
      Name += "- ";
    else
      Name += "+ ";
  }
  else
    Name += "  ";

  Name += c.Name;

  ListViewItem Item = new ListViewItem(Name);
  Item.SubItems.Add(c.Value);
  Item.SubItems.Add(c.Type);

  e.Item = Item;
}
這裡面用文字的+及-模擬樹狀結構的展開及關閉狀態鈕。 最後再加上一個處理滑鼠事件,處理DoubleClick用來展開或關閉項目。記得將ListView元件的FullRowSelect屬性設為true,這樣才不用只點擊第一個欄位才有作用。
private void listView1_MouseDoubleClick(object sender, MouseEventArgs e)
{
  ListViewItem lvi = listView1.GetItemAt(e.X, e.Y);
  if (null == lvi)
    return;

  TreeListItem c = VirtualItems[lvi.Index];
  if (0 == c.Child.Count)
    return;

  c.Expand = !c.Expand;

  BuildVirtualItems();
}
因為+/-鈕是用文字模擬出來的,如果要在畫面上顯示更精確的狀態,則只需要自行實作DrawItem及DrawSubItem即可。

(下載範例)

2011年11月4日 星期五

How to debugger? (1)

許多人都說:不懂debugger的人,不會寫程式。身為一個會寫程式的程序員,我也是十分同意這句話的。想當初我也是渾渾噩噩的寫了一陣子程式之後,才知道什麼是debugger,之後果然就好像打通任督二脈一樣,突飛猛進。所以說,要會寫程式,一定要會debugger。礙於有許多新手程序員還是不懂什麼叫作debugger,所以就寫了這篇文,對debugger作一個基本的介紹,希望能對大家有所幫忙,可以像我一樣勇猛精進。

首先,由寫一個小小的測試程式開始,慢慢的再進入主題。

#include <iostream>
using namespace std;

int mul2(int a)
{
  return 3 * a;
}

int main(void)
{
  if (20 == mul2(10))
    cout << "debugger讚!\n";
  else
    cout << "奇怪ㄋㄟ\n";

  return 0;
}
下面是程式執行的結果。


真是奇怪ㄋㄟ,應該是要顯示"debugger讚!"才對吧!?這個時候只好來debugger一下下了,看看問題出在那裡。

第一招,小紅點

下小紅點,也就是所謂的下斷點,也有人說中斷,或說breakpoint。在程式裡面放個小紅點,當程式跑到有小紅點的地方的時候就會停下來,這時候我們就抓到機會,可以去檢查看看各個可疑的地方,也可以偷偷竄改一些資料,無所不用其極的就是要把程式裡面的虫抓出來搞定它。

下小紅點的方法有很多種,這裡我可以告訴你四種方法。

  1. __debugbreak();
  2. __asm int 3
  3. __asm _emit 0xCC

以上的方法都是手動在程式裡面放入小紅點,也就是在程式裡面塞進一個0xCC。那到底0xCC是什麼東西。去查一下x86指令集,原來0xCC就是int3。你又要問:什麼是int3?答案是:int3是個中斷,由x86硬體支援,軟體觸發。

當CPU執行指令的時候,如果執行到的指令是0xCC,也就是int3的時候,它會發出一個中斷,也就是interrupt。中斷發生的時候,CPU會暫時停止目前手上的工作,然後跳到事先準備好的中斷處理常式去執行,就跟執行副程式沒什麼二樣。發生int3中斷時,就執行int3handler副程式,發生int21時,就執行int21handler副程式。這些中斷副程式,大多是由BIOS或作業系統提供,要不然就是應用程式提供。像這裡的int3副程式就是由debugger提供,專門用來處理debugger相關程序。

如果你的程式是由一個debugger啟動的,那麼debugger會在你的程式開始執行之前,就已經事先安裝好debugger專用的int3副程式,這樣一來當CPU執行到int3的時候才能作適當的處理。另一方面,如果你的程式不是透過debugger啟動的,也就是說在你的程式啟動前,並沒有什麼人安裝了一個int3副程式,那麼當你的程式一執行到一個0xCC指令時,它就會當場當給你看。

講到這裡再補充一下,當你在debugger你的程式的時候,假如你的程式是除錯版,那你一定會發現到那些未被初始化的變數內容都會是一堆0xCC。當時你一定會對這些變數的內容為什麼都是0xCC感到奇怪,現在學到了debugger第一招之後,終於了解到了這些0xCC可不是隨隨便便放進去的,它們是有特殊用意的。

;

不過正常的情況下,我們都不必自己在程式裡面塞個0xCC。而是在debugger IDE裡面透過F9等方法,在執行裡放小紅點。這時候你會覺得奇怪,在開始debugger前我們的程式都已經編譯完成了,那麼用F9放小紅點的時候,這個0xCC是放到那裡去了?是插入放小紅點的位置呢?還是取代原來那個位置的指令,把它給蓋過去了?答案是後者。當然,debugger也不能那麼霸道。在它放入0xCC之前,會先把原來位置的指令儲存起來,以備在適當的時機再復原回來。

各位,現在重點來了。當CPU執行到一個0xCC指令時,會幹什麼事呢?

當CPU執行到一個0xCC指令時,會觸發一個int3中斷,這時CPU停下手邊工作,跳到int3副程式執行,而這個int3副程式是由debugger提供。所以說,剛剛的問題應該換成:當CPU執行到一個0xCC指令時,debugger會幹什麼事呢?

  1. 首先,debugger會把目前CPU所有的狀態儲存下來。這樣子,當我們對debugger說繼續跑的時候,debugger才能把原來的狀態復原,讓原來的工作能無接縫的繼續進行下去。
  2. 如果現在執行到的這個0xCC指令是我們自己插入到程式裡面去的,那麼debugger就不需要作什麼特別的處理。
  3. 如果這個0xCC指令是因為我們在debugger IDE裡透過像是按了F9等方式放進去的話,因為這個動作會取代原來的指令,所以現在要作的事情就是要把原來的指令還原,再執行原來的指令,這樣整個程式的狀態才會正確。執行動作如下:
    • 將原來的指令寫回原來的位置。
    • 將CPU的狀態設定成單步執行,來執行原來的指令。CPU裡面有一個程式指位器,因為剛剛已經執行了0xCC,而本來應該是要執行原本的指令,所以在把原來指令還原後,還要再把程式指位器退回一步,這樣下次執行時才會執行到原來的指令。當CPU是單步狀態時,每執行一個指令就會觸發一次中斷,而像執行到0xCC時每次才會觸發一次int3中斷。而單步時觸發的中斷是int1,這是硬體中斷。
    • 當執行完原來的指令後,再取消CPU單步模式。控制權又回到了debugger。
  4. 現在控制權在debugger手上,它會一直等待我們的命令,這時候我們就可以為所欲為,觀察變數內容,偷改記憶體內容等等,或再叫debugger繼續跑。
  5. 跳出繼續執行程式前,debugger會先把所有在一開始記錄下來的狀態復原,然後再繼續執行原來的程式。對原來的程式而言,它完全不知道被人動過什麼手腳。

一開始的時候講到有四種方法可以放小紅點,那麼第四種方法呢?

上面講的三種方法是軟體中斷,剩下最後一個方法講的是硬體的中斷。有一組暫存器,透過設定你想要CPU停在那裡它就停在那裡。這是專門給debugger使用的,一般在程式裡頭不會去使用。使用硬體小紅點和軟體小紅點的差別是,用硬體小紅點不用像軟體小紅點那麼麻煩,需要在停下來時,再把原來的指令還原再執行然後再有的沒有的,再加上其它有的沒有的特殊技能。所以對於debugger內部來說,都會優先使用硬體小紅點,只不過硬體小紅點數量有限,當硬體小紅點用完了的時候,就要配合軟體小紅點。

對了,忘了說當硬體小紅點觸發時,和CPU單步執行時一樣會發生一個int1中斷,所以也一樣會跳到int1副程式去執行。

;

現在將游標移動到第11行或if (20 == mul2(10))那一行,然後按下F9放一個小紅點。


接著按下F5開始debugger。你會看到執行到第11行的時候,程式就停下來了,在停下來的那行會有一個箭頭。


現在你知道,按了F9下小紅點,然後再按了F5開始debugger,然後程式在你放的小紅點停下來,這之間發生了什麼事情了。

接下來,第二招要上場了。

2011年9月2日 星期五

不能Google9999999..99999999999999999999999

試著在Google裡搜尋9999999..99999999999999999999999,你會發現Google也有不能Google的東西。

2011年8月3日 星期三

充分發揮多核威力的排序法 sleep sort

程式(sleepsort.bash):

while [ -n "$1" ]
do
  (sleep "$1"; echo "$1") &
  shift
done
wait


執行例:

user@your-c24a217e1d ~
$ bash sleepsort.bash 4 1 3
1
3
4

user@your-c24a217e1d ~
$ bash sleepsort.bash 4 2 5 1 3
1
2
3
4
5

2011年7月28日 星期四

mutable關鍵字的用法

mutable關鍵字總是會和const關鍵字扯上關係,所以要使用mutable關鍵字前,你先要知道const關鍵字的用法。const關鍵字的使用方法這裡就不提了,這是閱讀本文的基礎知識。

關鍵字const的用途很廣,這裡我們只需專注在和mutable有關係的部份即可,那就是const member function。

; 範例1
class Sprite
{
public:
...
int getWidth() const;
int getHeight() const;
...
};

如範例所示,Sprite的getWidth和getHeight函式都是const,表示說呼叫到這二個函式的時候不會變動到任何這個Sprite物件內的資料。這是一般的情況。可是有時候我們所設計的介面,雖然在語意上它是const,但在實作上我們又不得不去變動到物件內部的某些資料。

; 範例2
class ResourceManager
{
public:
...
bool loadResource(string const& resName, ResourceItemHandle& item) const;
...
};

在範例中ResourceManager提供的loadResource函式,依照原始的設計,這個函式它會載入指定名稱的ResourceItem,而這個動作不會對ResourceManager內部產生任何變更。可是為了增加效率,我們在實作時在ResourceManager內部作了一個Cache的動作,把載入的ResourceItem快取起來,這樣下次再載入時就可以直接用比較快的速度完成載作動作。

這個時候就會產生如上所提到的和const衝突的情形,所以我們就只好把const修飾拿掉。拿掉const修飾字是一種解決的方法,但長遠來看這實在不是個好主意。解決的辨法是使用mutable關鍵字。

; 範例3
class ResourceManager
{
public:
...
bool loadResource(string const& resName, ResourceItemHandle& item) const;
...
private:
mutable ResourceItemCache cache ;
};

在範例3裡面,我們加了一個用來對ResourceItem作快取的member。loadResource函式被呼叫時會先在這裡面搜尋是否同一個resource已被載入過,如果是就不再作真正的載入動作直接拿cache內的資料來使用。要不然就執行真正的載入動作,載入成功後再把載入的ResourceItem存到cache內以備下次快速載入用。

在宣告cache時,我們對cache這個member加了mutable修飾字。這樣一來,loadResource就可以成功的通過編譯,即使它加了const修飾字。

這樣子你的程式就可以更有魯棒性了。

2011年5月11日 星期三

任務檢測器

翻到一個古董,再把資料檔案翻出來,還可以執行!這是第一份工作時製作的小工具之一,功能是用來檢視及測試編輯好的任務。設計的這個Script實際上就好像是在寫組合語言一樣,只不過到後來企劃也訓練的會寫組合語言了...

(單步/執行結果)

(玩家屬性)

(任務原始碼)

(字串表)

2011年4月20日 星期三

地圖編輯器(Map Editor)橡皮擦工具允許改變大小

根據偶然經過的旅人的建議,將地圖編輯器(Map Editor)裡的橡皮擦改成也能夠自訂大小,這樣一來在作清除時可以自行決定方便使用的大小,改變大小的方法和在作畫時以滑鼠右鍵作區塊選取的操作相同。

2011年3月9日 星期三

不可思議: for (i = 0; i < 10; i++) 停不下來 !?

其實這是一個真實事件...

某一天上班時,我從一早就三不五時的聽到坐在我背後的同事低聲的哇哇叫。幾次下來,我也忍不住好奇的湊過去看看到底是怎麼一回事。結果他Demo了這麼一個不可思議的for迴圈給我看,難怪他一整個早上都在哇哇叫。這位同事因為整個陷入在這個不可思議的for迴圈裡而跳不出來,找不到問題的所在。但當局者迷,我當下眉頭一皺發覺事情並不單純,問題肯定不是出在這個for迴圈上面,再怎麼去看也是白癈力氣。這種奇奇怪怪的問題,很有可能是和記憶體的使用有關係,這個不可思議的for迴圈只不過是因為其它地方的Bug,所產生的現象。我把我的想法告訴了我這位同事後,過了不了多久,果然在其它地方找到了真正的問題所在,的確是因為記憶體的使用不當造成的現象。

;

底下在VC2003寫支小程式,立刻就能摸擬出這樣的現象。

int main()
{
int i, a[1];
for (i = 0; i < 10; i++) {
a[i] = 0;
}
}


如上所示,我宣告了一個只有一個元素的陣列a,然後用一個for迴圈去填a的內容。這裡所要示範的一個概念是:會產生這樣的問題,是因為i的值被其它人動到了。而在這個簡單的例子,就是利用這個概念,想辨法讓在填a的內容時,因為填寫錯誤(超出範圍),而去覆寫了i的值,而造成for迴圈停不下來的奇妙現象。



如圖在除錯模式中,在Watch裡加上檢視i和陣列a的位址和內容,然後一步步執行看看。可以發現i的位址和a[3]重疊了,但問題是a只宣告了一個元素,而這個迴圈卻打算存取10個元素。在這樣的情況下,i的值果然被覆寫了,所以這個for迴圈就這樣成為無窮迴圈而永遠跳不出來。

;

PS: 這個實驗是在VC2003和2005上作的,在其它Compiler也許會有不一樣的結果。

2011年3月4日 星期五

關於最佳化

  • 過早作最佳化是萬惡的根源 (Premature optimization is the root of all evil.)
  • 最佳化守則
    1. 別作! (Don't do it!)
    2. 高手專用:先別作! (For experts only: Don't do it yet!)

2011年2月21日 星期一

char *(*(**foo[][8])())[] ???

對於底下的宣告,我們很容易就能夠辨認。

int i;

一個int變數i。

char *p;

一個指向char的變數p,也就是一個char指標。

那麼,底下這個宣告呢?

double **d[8];

比較難點了,不過要辨識還不致於太困難。這是一個有8個元素的double的指標的指標的陣列(開始...了)。

那麼,底下這個呢?

char *(*(**foo[][8])())[];

絶大部份的人看到這樣子的宣告,肯定會嚇一大跳,心裡面想說:靠,這是什麼鬼東西!

;

要理解這樣的宣告,可以遵循底下的三條規則:
  1. 從變數的名稱開始看。
  2. 到變數的類型作結束(如上的int,char)。
  3. 先盡量往右看,直到有需要時再往左看(如遇到括號)。
如下所示是分解動作。

ExpressionMeaning
char *(*(**foo [][8])())[]
char *(*(**foo [][8])())[]foo is … char
char *(*(**foo [][8])())[]foo is an array of … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to pointer to … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to pointer to function returning … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to pointer to function returning pointer to … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to pointer to function returning pointer to array of … char
char *(*(**foo [][8])())[]foo is an array of an array of 8 pointer to pointer to function returning pointer to array of pointer to char

;

參考 : http://www.unixwiz.net/techtips/reading-cdecl.html

不過話說回來,我自己是不可能會在程式裡面用上這種自己都搞不大清楚的東西。

2011年1月31日 星期一

用Java寫一個簡單的Web Server

Java的生產力很高,拿它來寫個簡單的Web Server只需要不到200行的程式碼,底下就用Java一步一步實作一個簡單的HTTP網頁伺服器。

;

在開始前,需要對HTTP協定有一個基本的認識,在我們這個例子裡面,只需要知道GET請求(Request)即可。

當我們在瀏覽器的網址列輸入一個位址時,瀏覽器會送出一個GET請求到位址欄裡指定的網頁伺服器,去跟這個網頁伺服器取得網頁或檔案的內容。

例如,我們在網址列輸入 http://www.google.com.tw/,就是向www.google.com.tw這台伺服器要求一個檔案,而要求的檔案就是首頁(/)。

這個動作,瀏覽器會送出如下的HTTP請求命令到伺服器去 (以Chrome為例):

GET / HTTP/1.1
Host: www.google.com.tw
Connection: keep-alive
Cache-Control: max-age=0
Accept: application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,i
mage/png,*/*;q=0.5
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US) AppleWebKit/534.10 (
KHTML, like Gecko) Chrome/8.0.552.237 Safari/534.10
Accept-Encoding: gzip,deflate,sdch
Accept-Language: zh-TW,zh;q=0.8,en-US;q=0.6,en;q=0.4
Accept-Charset: Big5,utf-8;q=0.7,*;q=0.3
<注意,這裡還有一個空行,表示結束>

這裡的重點是第一行和最後一行。

由第一行,伺服器可以知道Client作的是那一種類的請求,這裡可以明顯的看到Client(Chrome)作了一個GET請求。同時,在第一行裡面也可以知道Client請求的是什麼。在此例中,可以看到Client請求的是/這個檔案。在第一行最後的部份,則是註明HTTP協定的版本號。

而最後一行,是一個空行,表示請求包的結束。伺服器在收到一個請求時,從第一行的請求命令開始,一直讀取到一個空行為止,為一個完整的封包。除了第一行和最後一行,對我們的簡單伺服器來說,中間的部份可以全都忽略不看。

伺服器收這個GET請求後,假如可以找到到指定的檔案,接下來就會把Client請求的檔案內容回傳,使用的格式如下:

HTTP/1.0 200 OK
Content-Type: text/html
Content-Length:
<注意,這裡還有一個空行,表示結束>
<接下來,這裡開始都是檔案資料內容,總長度為Content-Length所指定的數字>

否則回傳我們常見的404 Not Found錯誤,如下:

HTTP/1.0 404 File Not Found
<注意,這裡還有一個空行,表示結束>

有了以上這些知識後,就足夠我們寫個簡單的網頁伺服器。

;

考慮到因為每一個Client的請求,都是在發出時才和伺服器建立連線,完成後就立即切斷連線。所以在設計上,我們可以用多緒(multi-thread)的方法,每一個請求都用一個獨立的執行緒來處理,處理完成後切斷連線,同時也結束這個執行緒。

根據這個想法,很直接的就可以寫出如下的基本框架來:

public class SimpleWebServer implements Runnable {

 ServerSocket server = null ;

 public static void main(String args[]) throws Exception {
  new SimpleWebServer(80);
 }

 public SimpleWebServer(int port) throws Exception {
  server = new ServerSocket(port) ;
  run();
 }

 public void run() {

  try {

   //
   // 1, 等待一個新的連接請求(Request).
   //

   Socket s = server.accept();

   //
   // 2, 開新Thread處理新連接請求.
   //

   Thread task = new Thread(this);
   task.start();

   //
   // 3, 處理請求內容.
   //
   
   handleRequest(...);
  }
}
如上,在進入點main我們開了一個SimpleWebServer,給它一個80的port number(80是HTTP的port number)。SimpleWebServer的Constructor會建立一個ServerSocket的實體,然後啟動主執行緒。執行緒的主體非常簡單,它只作三件事情。
  1. 等待一個新的請求連線進來。
  2. 開啟一個新的執行緒繼續等待下一個新的連線請求進來。
  3. 處理這個請求。
完成這三件事情後,這條連線被關閉,執行緒結束。

以上的部份,已經是一個可以執行的最簡易版伺服器,差別只在於它完全不處理作任事。接下來,我們再把最後處理請求的部份完成。

;

void handleRequest(Socket s, BufferedReader reader, DataOutputStream os) throws Exception {

 try {

  //
  // 1, 讀取HTTP Header字串.
  //

  //
  // 2, 解出請求的資源路徑.
  //

  //
  // 3, 處理請求的資源.
  // (測試: 只處理Homepage的請求)
  //

  if ("/".equals(path) || "index.html".equals(path)) {
   String homepage = "Hello Simple Web Server";
   os.writeBytes(
     "HTTP/1.0 200 OK\r\nContent-Type: text/html\r\nContent-Length: " +
     homepage.length() +
     "\r\n\r\n" +
     homepage);

   return;
  }

  os.writeBytes("HTTP/1.0 404 File Not Found\r\n\r\n");
 } catch (Exception e) {
  os.writeBytes("HTTP/1.0 500 Internal Server Error\r\n\r\n");
 }
}
處理請求的部份也是分為三個步驟:
  1. 讀出HTTP請求內容。
  2. 從讀出的HTTP請求裡,取出請求的檔案名稱路徑。
  3. 傳送請求的檔案內容。
因為我們只實作一個最簡單的網頁伺服器,所以只處埋Homepage的請求。如果Client要求的是首頁,就回傳首頁的內容,這邊只回傳一個簡單的字串"Hello Simple Web Server"表示首頁。否則回傳找不到檔案的錯誤404 Not Found。其它狀況,則回傳伺服器錯誤500的錯誤碼。(更多的錯誤碼可以在這裡找到。)


完整的原始程式碼,在這裡下載。

2011年1月4日 星期二

COUNT (1)('2')(1.2F)("3") 巨集展開

最近在研究些C語言的前置處理器的一些有趣的特殊用法。

;

const int COUNT1 = 1;
const int COUNT2 = 2;
const int COUNT3 = 3;
const int COUNT4 = 4;

#define COUNT1(a) COUNT2
#define COUNT2(a) COUNT3
#define COUNT3(a) COUNT4

#define COUNT(arg) COUNT1

int main()
{
    printf("arg count = %d\n", COUNT (1)('2')(1.2F)("3"));
}

輸出結果:

arg count = 4

很神奇!

;

COUNT這個巨集是如何展開的呢?底下來看一下分解動作。


COUNT (1)('2')(1.2F)("3")
-> COUNT1('2')(1.2F)("3")
-> COUNT2(1.2F)("3")
-> COUNT3("3")
-> COUNT4

在前面的COUNT1~COUNT3因為在名稱右側都有個括號,所以會作為巨集展開,直到解到最後一個COUNT4,右側已經沒有了括號了,所以直接以上面的int直取代,也就是4。

;

PS: 在Boost裡面有個Preprocessor模組可以看到更多Preprocessor Metaprogramming的應用。
Related Posts Plugin for WordPress, Blogger...