這則《假太陽》我是還在學時閱讀，那時啃完後覺得滿震撼的。故事是說人類最熟悉的天體，每天抬頭就可以看到的太陽，竟然是假的！原本真的那個太陽供應的能源只夠地球演化出猿猴，現在這個「假」太陽是被「人」調包過的！
這則《假太陽》故事有點宗教味道，但又不脫（倪匡筆下）科幻橋段，初次閱讀的應該不少人會跟我一樣，整個腦袋瓜轟轟的吧 XD
在 GodspeedLee 的分享下得知《時間迴旋》一書也有假太陽的設定。趁年假，花了一天的時間，順手把《時間迴旋》啃完了。
就科幻的部分，《時間迴旋》描寫更細膩，它除了會說明太陽跟地球的演化史外，也針對太陽被替換的方式，提出一系列合理的影響。例如說，夜空沒了星斗，月亮也不見了，甚至極光也消失了。這些是很好的科幻素材，依附在上面的人事物也由此帶出。
不過也因為內容描述太過詳盡，加上敘事方式不是很連貫，所以我是覺得有點囉唆。不符合我啃書喜歡挑重點的習慣 :p
Labels: book
開發 Embedded Systems 常常會碰到 f/w 要用到圖、字型、甚至音樂等 resource 的情況。實務上一種處理方式是將這些 resource 轉換後串成一個大的 C array 。然後再用 resource ID 去讀取它們。一些書上稱這種轉換的工具叫 Resource Maker 。不過我不會採取這種作法，雖然還是透過 resource ID 讀取，但不把 resource 轉成 C array ，而是直接轉成 binary 格式，要用時才去 storage 裡 load 進來，因為這樣比較節省記憶體空間。
多年前我就用 Python 寫了類似的工具，那時我把這支程式稱作 weave 。後來慢慢精練，演變成今天要介紹的 ResourceLink 。
同樣地，這裡我主要也是著重在 ResourceLink 裡用到的領域專用語言，來看看我怎麼描述這些 resource files ，以下是個 res.lst 的例子：
:0x00 # start offset (default is 0x00)
:kind=A # kind A for the enumeration
bat.png # file size: 2877 bytes
:kind=B # kind B for the enumeration
:4096 # offset to address: 4096
broom.png # file size: 3083 bytes
candle.png # file size: 2771 bytes
把這個 res.lst ，餵給 ResourceLink 後，可以產生 ResID.h, ResMap.i, 跟 res.bin 。
res.bin 就是這些 resource 檔案（三張圖檔）連結成的單一檔案。
ResID.h 為每一個 resource 都指定一個 enumerator ID：
// Generated by the Resource Link v1.14
// !author: Jiang Yu-Kuan
// !trail: reslnk.py id -oResID.h res.lst
#ifndef _RES_ID_H
#define _RES_ID_H
/** IDs of Resources */
typedef enum {
RES_A_BEGIN,
RES_PNG_bat = RES_A_BEGIN,
RES_A_END,
RES_B_BEGIN = RES_A_END,
RES_PNG_broom = RES_B_BEGIN,
RES_PNG_candle,
RES_B_END,
RES_End = RES_B_END,
RES_Total = RES_End
} ResID;
#endif // _RES_ID_H
ResMap.i 是用來描述每個資源檔的偏移植跟大小的：
// Generated by the Resource Link v1.14
// !author: Jiang Yu-Kuan
// !trail: reslnk.py map -dres -oResMap.i -a4 res.lst
// offset, size (in bytes)
{ 0, 2877}, // RES_PNG_bat (bat.png)
{ 4096, 3083}, // RES_PNG_broom (broom.png)
{ 7180, 2771}, // RES_PNG_candle (candle.png)
開發 Embedded Systems 相關應用時，常得處理多國語言。而系統資源受限的的場合，就算掛了 OS，往往也沒內建多國語言。這時候只能捲起袖子自己處理了。自幹的過程，很直覺地，多數人都會想到要有個類似右圖這樣的 Excel 字典檔當作翻譯表。
有了翻譯表後，我們還要有個字庫（font）。為了存取字庫裡的字，我們要先決定字序（character order）。有了字序後，我們就能根據字序，把翻譯表裡面的多國語言訊息，一一轉換成字序的串列（a sequence of character orders）。要秀某個訊息時，就根據這個字序列，回過頭把字庫裡的字形（glyph）抽取出來顯示。
如果要通吃幾乎各國的語言，一個奢侈的做法是直接用 Unicode 當字序，建立完整的字庫。不過這不適合用在資源受限的場合。
多年前，我遇到決定字序的問題時，想了一種簡單又好用的表示法。以 ASCII code 有對應字形的部分為例子，可以利用這個表示法描述如下：
# Printable characters of ASCII code
:0x20
!"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~
因為英文太常用了，所以 32 到 127 這段通常會保留給 ASCII code 用。其他國家的語言，我們可以只列出有用到的，以節省字庫佔的儲存空間，以下是實際的例子：
# A sample character list file
:0x20
!"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~
:0xA0
áíñóúąćęśП
РУЭабвдежз
ийклмнопрс
туфщыьэюя中
件像册删单图子定客影
文时显检此电相示置菜
言设访语间除验간겠국
까뉴니메문미방범삭설
스습시앨어언영을이인
일자전정제지틸파표하
한화확？
有了翻譯表（dic.xls）跟字序表（char.lst）後，就可以利用 LangConvert 產生下述的幾個 C 原始程式：
接下來還缺個從字序表轉出字形（glyph）的工具，這個大家可以自己練習看看。我這裡著重在介紹領域專用語言來表達字序表。
LangConvert 還有個新增的 command 可以透過 Google Translate 來對空的字典檔實施自動翻譯，有興趣的可以直接執行 demo_trans.bat 觀察看看。它會吃進還沒翻譯好的 dic_empty.xls ，然後吐出翻譯好的 dic_trans.xls 。
記得小學製作海報時，會用剪貼的方式分工，快速拼湊出一張教室海報。時代進步了，現在大家都用電腦，我好幾次觀察到現在美術人員幫忙設計 UI 時，也常常會先把整體畫出來，然後再一塊塊的剪下來。這些剪下來的圖，還有個貼切的稱呼，叫「切圖」
# source picture
#---------------
ipod-touch-5th-black.png
# x, y, w, h, target picture
#------------------------------------
117, 139, 62, 62, ico_FaceTime.png
190, 139, 62, 62, ico_Calendar.png
263, 139, 62, 62, ico_Photos.png
336, 139, 62, 62, ico_Camera.png
117, 223, 62, 62, ico_Weather.png
190, 223, 62, 62, ico_Clock.png
263, 223, 62, 62, ico_Maps.png
336, 223, 62, 62, ico_Videos.png
前陣子我把 AWK 撿回來練習，順便研究一下 Windows 下怎麼跑 GAWK 跟 AWKA 之類的工具。這期間，我想了幾個簡單的題目來練習。其中有個我稱作 EnumLookup 的工具，一些慣 C 的人應該會用到，所以在這裡做個分享。
顧名思義，這個工具的目的是針對 enum ，它可以在多個 C enumerations 上查詢 enumerator 或它們對應的值。這裡是安裝跟執行說明文件，大家可以根據上面的指引，直接下載內含執行檔的下載包來試用。
這個工具有個搭配的 enum.bat ，執行後可以雙向查詢：可反覆敲進數字來查對應的名字（enumerator），或者敲入名字（enumerator）來查對應的索引數字。
需要注意的是，這個工具沒有真的去實作完整的 C enum parser ，只是認「通常」情況下的 enum 特徵。下面這種寫成一行的寫法，無法正確執行：
typedef enum {SPRING, SUMMER, AUTUMN, WINTER} Season;因為這工具不認得寫成一行的寫法，只認得下面這種，比較正規的，分行寫法：
typedef enum {
SEASON_BEGIN,
SPRING = SEASON_BEGIN,
SUMMER,
AUTUMN,
WINTER,
SEASON_END,
SEASON_TOTALS = SEASON_END // the total number of seasons
} Season;
接連多日的年假已接近尾聲，吃吃喝喝之餘，很自然地就想到一個跟吃喝有關的練習。雖然年假前在公司搞的相框產品確實用到各式 UI 選單（menu），但我在這裡要聊的是名副其實的菜單（menu）。
為了製作精美的菜單，我用 Google 搜來幾張食物的圖片準備用作底圖，除了一張用作食物主選單底圖外，其餘三張分別用作飲料類、水果類和蔬菜類等用途。
考慮到要製作的菜單不只一張，且每張菜單的內容會一直修改，所以我不打算用繪圖軟體繪製菜單，這個重任當然要照慣例，委託給爬說語。要執行這支程式，必須先以 YAML 語法，利用文字編輯器寫下菜單的內容及呈現方式，存成 menu.yaml 。程式執行時會自動讀進這個描述檔，然後描繪出期望的菜單來。例如說，有張菜單長成這樣：
這是一張飲料類的菜單，它有 Coffee, Juice, Soda Water, Tea 等選項，要產生這張菜單， menu.yaml 這個純文字檔就要列出飲料類菜單的內容：
title: '== Drink =='
items:
- Coffee
- Juice
- Soda Water
- Tea
除了填寫菜單的內容外，還要填寫菜單的呈現方式：
style: # Style of title, items, focused items
font: [cour.ttf, 24]
title: {color: clYellow}
items: {color: clWhite}
當然不能忘記告知從 Google 那搜來的底圖：
basemap:
dim: [320, 240] # dimensions of width and height
color: clWhite
image: drink.jpg
type: image # {color, image}
完整描述請參閱 menu.yaml 。程式請參閱 MenuShow.py。
到電子商場逛一圈就會發現一堆產品都有 NAND flash 的身影（例如大拇哥，記憶卡，MP3 player，數位相框，甚至 PC 等）。前陣子和 simayi 閒聊時，他就提到：既然大家都愛用 NAND flash ，要是有人為它搞個 IP 或函式庫之類的，勢必可大幅節省開發時間。
相信處理過 NAND flash 的 firmware 人員，在啃讀 datasheet 的過程，難免得謹慎地交叉比對，好好推敲那也佔了不少篇幅的時序圖，以免自己還是不夠小心，誤解文意……
不知道大家看了那一疊 waveform 後，有什麼感想？我的看法是，那疊圖雖補足了許多重要細節，卻沒能好好強調重點，抽象度不夠。這根本是在折磨 firmware 人員，使我們構思演算法時綁手綁腳。
因此，在 K 完文件後，我為這疊 command waveforms 作的第一件事就是－－提昇抽象度，強調重點，用 Computer Science 學生都看得懂的語言重新詮釋過：
基本的正規表示法就捕捉到 NAND flash commands 的內涵，充分表現出蘊藏其中的模式 :)
適當的表示法可以流暢表達所思所想，幫助我們釐清思緒、避免錯誤；好的表示法更可以提供新的洞見，讓我們解決乍看之下非常困難的問題，甚至進一步導致新的發現。
將來要實現自動化，或 Workflow 軟體時，正規、簡明的表示法更是一個必要的基礎設施。
後記：就 NAND flash 而言，僅僅是 command 的正規化還不夠方便；為 NAND flash 設計演算法時，最好再架上另層一抽象，以幫助思考。
撬開一張 SD 卡，裡面最顯眼的，當然就是那大大一顆的 NAND flash ，我們餵給 SD 卡的資料都儲存在裡面；在 NAND flash 旁邊，還可看到一顆小一號的，那就是 controller IC ， 要確保資料的儲存是安全可靠的，有九成的責任都要算在 controller 身上。
在硬體介面方面， NAND Flash 雖有 bus 結構，卻沒去區分 address bus 及 data bus 。在 NAND Flash 上進行任何操作（如 read, write, erase 等），都要透過 command ，且無論 address, data, 或 command，都以同一組 I/O bus 傳輸。
此外， NAND flash 在資料 program 或保存過程，還會隨機出錯，所以廠商才會建議搭配 ECC (Error Correcting Coding) ，以資料冗餘來偵測及更正這種隨機的錯誤。
就算不考慮上述這些， NAND flash 還是非常難纏，對 firmware 人員來說更是如此：它無法像 RAM 或 ROM 那樣，隨插隨用；也不像 serial NOR flash 那樣，照著 spec. 下下 command 就能了事。我就以 Samsung K9F1G08U0B 這顆 NAND flash 為例，摘要如下：
相較於其他 floating gate 製品，NAND Flash 最讓人詬病的是壞塊（bad blocks），不但一出廠就允許壞塊存在，在保固的使用壽命內好塊還會陸續變成壞塊，更慘的是壞塊的發生還是隨機的。也因如此， NAND flash 的 firmware 或專用的檔案系統都得好好管理壞塊（Bad Block Management），讓用戶察覺不到壞塊存在。
再者，同樣是 floating gate 組出來的， NAND Flash 當然也有明顯的寫入次數限制，再加上它常用於頻繁、不均勻的寫入場合，所以要有一個叫作 wear leveling 的抽象層，讓針對單一邏輯位址的多次寫入，分散到不同的實體位址，以避免太快壽終。
浮動閘（floating gate）一詞會讓我銘記於心，是因為閱讀了《矽眼》，該書提到以浮動閘紀錄類神經元突觸加權值，這是「類比」儲存的一個應用。
然而，對多數內嵌系統設計人員來說，浮動閘是用在「數位」儲存的，諸如 EPROM, EEPROM, NOR flash, NAND flash 等。
無論是 EPROM, EEPROM 或 NOR flash ，早先都是設計來在上面直接跑程式的（不用 copy 到 RAM 上跑，術語叫做 execute in place, XIP），所以有獨立的 data bus 及 address bus 。
為了省空間，後來很多 MCU 都把 EPROM, EEPROM 或 NOR flash 包進同一棵 chip 了，這造成外部的 EEPROM 或 Flash 開始走 serial 路線。 serial EEPROM 或 serial Flash 對外的 pin 腳雖然大幅精簡了，卻失去了 XIP 的特性，因此主要被拿來儲存程式之外的東西。
由於 EEPROM 是 byte-wise writable 的，用起來超方便，所以資料量不大時我們都會用它。例如一些儀表類的內嵌系統，諸如血壓計之類的，其內部的關鍵零件是感測器，這些感測器的元件特性會隨溫度等外在因素漂移，所以需要在事後作校正，這些校正用的參數就很適合用 serial EEPROM 儲存。
有時候我們要存的不僅僅是簡短的幾筆，而是長時間累積下來的一大串 log 。例如未來的病患可能會長時間配戴血壓計血糖計之類的，隨時紀錄血壓血糖變化，然後隔固定時間，自動將這些資料傳到醫院的監控中心。這種場合因為要存的資料量較大，也許該考慮採用 serial Flash 。
操作 serial (NOR) Flash 跟操作 serial EEPROM 類似，都有 OP-Code Phase, Address Phase, Data Phase 等三個階段。偏偏 (NOR) flash 只能 block-wise writable ，這意味著就算只想改變一個 block 的某幾個 bytes 的內容，還是得先把整個 block 的值都讀出來，在 RAM 中修改後，再寫回去。
這幾年正火熱的 NAND Flash 一開始就是設計來替代硬碟這類大容量的儲存媒體。它雖價廉、肚大，卻是個極不穩定的傢伙，不但允許出廠就有壞塊（bad block），使用過程壞塊還會隨機增加，更扯的是廠商還信誓旦旦說這是良品，要大家看著辦。良品都這副德行了，真不敢想像一些 down grade 的會長成什麼樣子 :p
文末，再附上簡短的比較：
……秒針急急忙忙的去撥動每一根短棒，使它們產生意義。然後分針慢吞吞的做同樣的事，使那些短棒產生另一種意義。三種針的位置和關係不斷變更，在錶面上切割出許多角來，夾住那不可捉摸的時間。……（摘自作文七巧：P86）
算一算日子，在現任公司混吃也有九個月了。很幸運的，一進來就參與一顆 ASIC 的開發，從一開始的寫 tools 測試 FPGA 功能，後來的寫 f/w 測試 ASIC ，到最後的參與產品開發。照規劃，一開始只打算拿來秀秀圖，偶爾也秀秀時間日期。後來為了把這顆小 MCU 的能耐完全壓榨出來，前些日子我還幫它加了類比鐘（Analog Clock）。自此，相框就不再僅僅只是相框了：
想起專科的畢業專題，我實作過一組函式庫，用來執行 3D 投影及相關的座標轉換。一晃眼已經十多年了，最近為了完成的這個類比鐘，竟然連描點畫線的程式都得自己手寫……
這也沒辦法，先前那支專題程式是在 16 bit 的 286 CPU 上跑的，硬體上有浮點運算器可用，軟體方面也有 DOS 版的 Borland C++ 提供的 BGI 繪圖函式庫。而這次的類比鐘卻要運作於 8 bit 的 8051 MCU。
首先，我寫了常用於光柵繪圖的點（pixel）運算及畫線程式。既然可以描繪出線段了，接著就一段一段的，拿來描出時鐘刻度及各式指針：
由於底層光柵繪圖的座標系統（直角座標）實在不適合拿來描繪鐘面及指針，所以我只好祭出極座標。
雖然極座標到直角座標的轉換式是長成這樣的：
x = x0 + r⋅cos(θ) y = y0 + r⋅sin(θ)
我實際採用的轉換式子卻是：
x = x0 + r⋅sin(minute) y = y0 - r⋅cos(minute)
這是因為
值得一提的是，整個換算過程只用到整數運算，因為我不但採用了定點數運算技巧，還以爬說語產生了正弦、餘弦表格：
>>> from numpy import *
>>> scale = 127
>>> array([round(x) for x in scale*sin(arange(0, 2*pi, 2*pi/60))], dtype=int)
array([ 0, 13, 26, 39, 52, 63, 75, 85, 94, 103, 110,
116, 121, 124, 126, 127, 126, 124, 121, 116, 110, 103,
94, 85, 75, 64, 52, 39, 26, 13, 0, -13, -26,
-39, -52, -63, -75, -85, -94, -103, -110, -116, -121, -124,
-126, -127, -126, -124, -121, -116, -110, -103, -94, -85, -75,
-64, -52, -39, -26, -13])
>>> array([round(x) for x in scale*cos(arange(0, 2*pi, 2*pi/60))], dtype=int)
array([ 127, 126, 124, 121, 116, 110, 103, 94, 85, 75, 64,
52, 39, 26, 13, 0, -13, -26, -39, -52, -63, -75,
-85, -94, -103, -110, -116, -121, -124, -126, -127, -126, -124,
-121, -116, -110, -103, -94, -85, -75, -64, -52, -39, -26,
-13, 0, 13, 26, 39, 52, 63, 75, 85, 94, 103,
110, 116, 121, 124, 126])
定點數運算常用於 embedded systems 中，因為大部分低階的 MCU （例如： 8051, PIC, AVR 等）開發環境雖提供浮點運算，卻是軟體模擬的，除了慢，還明顯佔用原本就少得可憐的記憶體空間。 C/C++ 語言雖無定點數運算專用語法，程式員卻可通過手動調整，有效以整數運算完成相同效果。
定點數運作的原理，簡言之，就是將原來的實數（real number）或者小數（decimal），改寫成分數（fraction）：如果 x 是個含小數的實數，我們可以找來兩個整數（p, q），將它們相除，來近似原來的 x （p/q ~= x）。
實務上人們可能還會要求上述的 q 要是 2 的冪次，因為電腦處理的都是 0, 1 的二進位運算， q 表示成 2 的冪次可以達到較高的精度；另一個原因我想是許多 f/w 程式員都患了 shift 偏執症 :p
有個友人前陣子寫了江湖一點訣，還在 CSZone 引發一陣討論，有人提到說他用工程計算機把十進位數轉成二進位就搞定了，何苦寫程式來 try 出 p, q 。
最近興起，也想把數字轉成二進位以找出 p, q 時，發現手邊沒有合用的計算機，不爽之餘，再次以爬說語搞定這件事：
"""
File: fract.py
Converts a decimal into an equivalent fraction.
"""
__author__ = "Jiang Yu-Kuan, yukuan.jiang(at)gmail.com"
__date__ = "2008/05/17"
__revision__ = "1.2"
def fract(x, bits=8, deduced=False):
"""Find p, q such that p/q ~= x and p, q < 2**bits
"""
p, q = x, 1
while p < 2**bits:
if deduced:
print "%f = %d/%d" % (round(p)/float(q), round(p), q)
p *= 2
q *= 2
return int(p/2+0.5), q/2
if __name__ == "__main__":
p, q = fract(3.1415926535, deduced=True)
print "p=%d, q=%d" % (p, q)
用例：
J:\trial\python>python -i fract.py 3.000000 = 6/2 3.250000 = 13/4 3.125000 = 25/8 3.125000 = 50/16 3.156250 = 101/32 3.140625 = 201/64 p=201, q=64 >>> from math import e, pi >>> e 2.7182818284590451 >>> fract(e) (174, 64) >>> 174/64. 2.71875 >>> pi 3.1415926535897931 >>> fract(pi) (201, 64) >>> 201/64. 3.140625 >>>
在軟體開發過程，我們很可能得寫大量的程式碼來完成一些繁瑣、平凡的工作，避開這個窠臼的辦法就是「自動化」。誠如 Kernighan 和 Pike 在 The Practice of Programming 一書所闡述的，優秀的軟體設計運用幾個基本原則：簡單（simplicity）、清晰（clarity）、一般性（generality）、自動化（automation）。
舉個例子， IC designers 常會跟 f/w 人員一起關起門來，私下協調出各種用途的 registers （memory mapped I/O），這些開放給 f/w 人員使用的 register 介面，會有一份以 Verilog 形式存在，另一份則以 C code 的形式存在，在 IC 開發過程，這些 registers 會經歷多次的變更（例如改名字、改位址、添加 registers、刪減 registers 等）。可以想見，要手動讓這些 registers 在 Verilog 及 C 間維持一致，是件繁瑣、容易出錯的事。
電腦在處理這類格式轉換工作時，得有個 parser 來剖析源文件；偏偏要建構 parser 也有好些瑣碎的東西必須處理。幸好 Compiler 是門發展已久的學問，有許多 parser generators 可以讓這些繁瑣的建構過程自動化。
早期的 parser generators （例如： Yacc ）幾乎都是 LR 系列的，一個主要的原因是，教科書告訴我們 LL parser 是不切實際的，只有 LR parsers 才能有高效的表現；另一個理由是， LR parsers 想要手寫，大概也很難 :)
好玩的是後來出現了幾個廣為流行的 parser generators （例如： JavaCC, ANTLR, Boost.Spirit），都走 LL 風。這勾起我的好奇心，細查下才發現 LL 風的 parser generators 在 90 年代有了新的技術突破，我該 update 一下之前教科書塞進我腦袋的資訊了 =.="
如果大家也想複習一下學校教的 Compiler 技術，可以不用翻箱子找課本了，因為維基百科對這方面的資料，紀錄還滿完整的。文末附上我為相關條目所作的分類，相信可以為大家省卻一些時間。
先前曾經探討，像我們這種靠寫程式混吃的，最好備有兩把刷子，當發現其中一把刷子無法刷掉問題時，趕緊換上另一把刷刷看。通常一次只要用上一把，就可以把問題刷掉，偏偏有些問題比較棘手，要同時用上兩把刷子，左右開弓，才刷得乾淨！
這些要左右開弓的問題中，有個最典型的例子，那就是實作一個程式語言的編譯器（Compiler），它運作時恰好要經歷「分析」及「合成」兩個階段，這實在太妙了，所以我將它整理整理，簡述如下：
這些年下來，我反覆觀察到一個現象：程式員各有一套慣用的方法來克服自己遭遇到的問題，這些解題習慣可區分成兩種，工程師多只專精其一，只有少數能任意在兩者間自在地切換。
在很多情況下，無論程式員採用哪種作法，都可輕易把問題解掉；但是另有一些問題，卻不是這樣隨性而為就解得掉的－－這就值得我們好好玩味了……
以 1..n 的正整數相加這個例子來說，我知道程式員應該利用現成的副程式，以爬說語來寫，應該要長成這樣：
n = 100 y = sum(range(1, n+1))
假裝我們沒有現成的，像 sum 這樣的副程式可用。那麼，一種可能的寫法如下：
y = 0
for i in range(1, n+1):
y += i
這是標準的合成（Synthesis）法。以這個例子來說，如果不考慮時間複雜度要 O(n) ，這個方法其實沒什麼不好，畢竟它非常直覺，寫起來也很簡單。
大部分資訊背景的，甚至其他工程背景的，都傾向以這種「合成」的策略來克服問題。
由於這是個已經爛掉的例子，我們當然知道有個時間複雜度只要 O(1) 的作法：
y = (1+n)*n/2
這是典型的以分析（Analysis）手段來解題的例子。通常數學或物理等理科背景的人，比較慣用這種「分析」的手段來解決問題。
大部分的工程問題都牽連太廣、太複雜了，很難找到分析解；所以工程師們很習慣採用 trial and error 的合成策略，只求找到一個可行的作法。
這種「先兜出一個作法，看著它如何失敗，然後再兜另一個作法試試，不行的話再兜另一個……」的合成策略，陪伴我們度過無數個夜晚，也解決了不少問題，但如果每次「歪打」都沒有任何「正著」甚至「歪著」的跡象，這種策略就完全失靈了。
在合成策略無效或顯得白費功夫時，也許可以學著適應理科背景的慣用手法：「靜心分析問題，用數學精確地描繪出問題，建立模型，擴充內容，增大視界」，據此提供新的想法和嘗試的途徑。
Labels: concept, programming, Python
來這混吃也七個月有餘了，初到公司時正逢新 IC 開發，我受命寫了工具程式以驗證功能，完成了 Boot Loader 以執行外部程式，也開發了應用產品的 firmware 以提供下游客戶 total solution ～～
接單量產、功能穩定後，準備接手的同事人竟然在新竹－－先前架的 code server 一直都只在台北這邊的內網使用，安全無虞，現在既然要跨到外網了，當然得提防封包被監聽……
原先架設的版本控制系統 SVN 及搭配的問題追蹤系統 Trac ，兩者都是透過 HTTP 協定和用戶端連線，現在為了隱密地傳輸資料，最直接的方案就是改走 HTTPS （HTTP over SSL）協定。
要讓我們的網頁伺服器 Apache 支援 HTTPS ，最省事的作法就是安裝 Apache 時就採用整合了 SSL 的安裝包。很不巧的是我之前用的安裝包是 no_ssl 的版本，所以得重新安裝 Apache 。另一方面，這一段日子以來， 無論 Apache 或 SVN 等，都陸續推出了新版，索性就把它們都再安裝一次（記得要先 uninstall 喔），相關步驟整理如下：
Labels: programming, SCM
按鍵是很普遍的人機介面，也常用於內嵌系統（Embedded Systems）。既然大家那麼愛用按鍵，很自然地， Embedded Systems 軔體開發人員就常常得處理按鍵的偵測、編碼等議題。此外，為了按鍵操作流暢，我們還必須為按鍵設計適當的指法（fingering）及明確、統一的功能定義（function definition）。
不久前筆者設計了一款相框產品，它雖然只有三個按鍵，但除了要能執行基本操作，如上一張、下一張、設定自動換張的間隔時間等；也要能夠流暢地切換功能，如手動換張、自動換張、顯示日期時鐘、功能設定等；此外，最好還能透過這些操作，讓使用者充分感受到它優越的秀圖速度。
老實說，把這些操作通通塞進三個按鍵內並不是多困難的事，比較需要我們傷腦筋的是怎麼讓使用者覺得操作是簡單流暢、符合預期的。
這裡不是要跟你扯怎麼設計美美的畫面，雖然美美的畫面很重要，但畫面設計還是交給專業的美術人員，我們只要想辦法讓「程式的行為與使用者的期望完全一致」就好了。
為了達成這個目標，我在上面規劃了單擊、長壓、自動重複、組合鍵等操作指法（fingering）：
在決定了這些指法及其使用場合後，緊接著是要定義各個按鍵在不同指法及情境下所對應的功能（function definition），一個可能的定義如下：
最後，關於按鍵的處理，我之前還整理了一篇 Keypad Algorithm 大家可以順便去逛逛 :)
為甚麼好的設計會來自於差的設計呢？ Scott 在 Why Good Design Comes from Bad Design 提到攻讀 CMU Computer Science 博士時選了門介面設計課，第一堂課上他發現一位年輕人素描著隨身聽的各種變異版本，而且圖紙上已經堆積了三、四十種不同考量的版本了。 Scott 於是湊過去問這個小伙子「幹嘛費勁畫那麼多草稿？」，小伙子發楞了好一會才笑著回說：
I don't know what a good idea looks like until I've seen the bad ones.經過時日洗煉， Scott 後來也體會到當初認為多餘的作法，其背後的精神，他提到：
Each new idea I sketched out was more informed than the last. Each bad idea illustrated some important aspect of the problem that I hadn't thought about before. Out of every five or six ideas, I'd have one or two that might be feasible.
I learned the right way to present ideas–you have to show the other candidates in order to help support the good ones.
When the design student showed me his sketches, he was showing me that he was a designer. All creative, talented people recognize the value of process, and have no concerns about revealing to others that it takes many bad ideas to obtain good ones.這讓我想到 C++ 的老爸 Bjarne Stroustrup 也曾經提到：
At the start of an ambitious development project, we do not know the best way to structure the system. Often, we don't even know precisely what the system should do because particulars will become clear only through the effort of building, testing, and using the system. How - short of building the complete system - do we get the information necessary to understand what design decisions are significant and to estimate their ramifications?這段 William 翻譯如下：
-- ref. The C++ Programmming Language, p710
偉大的軟體開發專案開始之初，我們並不知道什麼才是最好的系統組織方式，甚至連應該做出什麼樣的系統都不知道；因為唯有透過打造、測試、使用系統的過程，一切才會明朗。如果尚未打造系統，該如何才能獲得必備資訊以事先瞭解有哪些重要的設計決定？至此，應該不難體會：無論是要創造一個好的設計或成就一項偉大的專案，非常重要的就是要畫出許多「草稿」、進行多項測試及「實驗」。
-- ref. 中譯本, p930
Labels: concept, design, programming
上週一（9/10）公司要我把 Subversion 環境架起來。除了很高興公司也打算採行版本控制環境來幫助程式開發外，我還打算一併把 Issue Tracking 系統掛上去。
說起 Issue Tracking System，要跟 Subversion 搭配良好，且一樣是 freeware 的，當然非 Trac 莫屬。細查之下，乖乖， Trac 竟然要裝那麼多相關套件，且各個套件還要挑正確版本，才可運作良好。
為了避免大家（或將來的自己）白走冤枉路，這裡把要安裝的東西及安裝步驟條列於後：
反正就把下列連結清單中的檔案都抓下來，待會再一口氣安裝。
上面安裝順序只要 Apache2 先於 Subversion 即可，因為 Subversion 安裝程式會認得執行中的 Apache2 ，並自動完成一些設定，讓人省很多功夫。
如果只是個人使用，且不打算搭配 Trac ，那裝 TortoiseSVN 即可，而 Apache2 只有下列情形下才需要安裝：
easy_install -Z http://subversion.tigris.org/downloads/1.4.5-win32/apache-2.0/svn-python-1.4.5.win32-py2.4.exe
easy_install -f http://clearsilver.net/downloads clearsilver==0.9.14
easy_install pysqlite
以上只要 Python24 先安裝即可。
cd Python24\Scripts
ren trac-admin trac-admin.py
ren tracd tracd.py
easy_install http://svn.edgewall.com/repos/trac/sandbox/webadmin/
easy_install http://trac-hacks.swapoff.org/svn/accountmanagerplugin/0.10
easy_install D:\Python24\lib\site-packages\tracaccountmanager-0.1.3dev_r2548-py2.4.egg
easy_install http://trac-hacks.org/svn/iniadminplugin/0.10
WebAdmin, AcdountManager, iniAdmin 這三個 Trac plugins ，可以讓我們直接在 Browser 上操作 Trac 設定，減少於命令列下指令的必要，強烈建議安裝。
如果還有其他需求的，可以到 Trac Hacks 看看有沒有人提供現成的。
此外，有 Trac 中文化需求的，可以到下列網站上逛逛：
首先要先以文字編輯器開啟 Apache2\conf\httpd.conf ，然後搜尋到
#LoadModule dav_module modules/mod_dav.so
將上面的註解 ( # 字號) 去除（如果依照上述的步驟安裝，註解應該被安裝程式拿掉了）。
然後在整個 LoadModule 區段的下方加入以下設定：
# For Subversion
LoadModule dav_svn_module modules/mod_dav_svn.so
LoadModule authz_svn_module modules/mod_authz_svn.so
# For Trac
LoadModule python_module modules/mod_python.so
這樣 Apache 重新啟動時，就會載入 DAV, SVN 和 Python 等模組。
Labels: programming, SCM
前些日子把讀過的機器人書整理上來後，網友 HuaHua 留言推薦了《機器人：由機器邁向超越人類心智之路》。後來我特地跑一趟政大書城，翻閱後才想起幾個月前也在這翻過。如今再次翻閱，還是沒抱回去好好端詳，最大原因是此書主要內容，我在其他諸如書、網路、或論文等，幾乎都涉獵過。
昨天到國家圖書館，無意間發現該書竟躺在那，頻頻向我招手……嗯，這次當然不能再錯過 ^__^
與其說這是本講機器（人）的書，不如說它是探討人造智能（AI）或電腦及機器智慧（Machine Intelligence）發展潛能的書。
這本書最合我胃口的是第二章〈小心！前有機器車〉，探討作者對機器自走車的實務經驗。裡面提到作者 Hans Moravec 在 Mobile Robot Laboratory 接受 Denning Mobile Robotics 委託，研究如何以二十四個聲納組成的障礙偵測裝置，量測、取得的距離資料，完成自主機器車導航的任務。
聲納是藉由發射一束以三十度角展開的超音波反射回來的聲波來推測距離的，其得到的距離很精確，回音由哪反射回來卻是未知的（因為有三十度的範圍）。所以採用追蹤影像突出特徵的作法無法適用。
作者和學生 Alberto Elfes 合作設計了個新方法解決這個問題。該方法不嘗試找出物體的位置，改而累積計算每個位置所擁有的物性（objectness）：
其具體的作法如下：
對自主移動機器人有興趣的，想知道機器人如何知道自己身在何方（Localization），如何藉由路徑規劃（Planning），由某個地方到達目的地（Navigation），強烈建議好好翻翻我之前在 Robot Book 閱讀清單也推薦過的 Introduction to Autonomous Mobile Robots 一書。
第三章 Power and Presence 主要探討計算能力與機器心智間的關係。曾經關注過電腦發展的人，對這章的推論應該不會太過驚訝：作者一開始先提提怎麼樣能力（如運算速度及記憶容量等）的電腦能達成怎麼樣的任務，然後粗估了人腦運算速度及記憶容量，既然電腦運算能力每年都要倍增，所以估出 2020 年時，個人電腦的能耐會達到人腦級。無論對這議題感到興趣或心存懷疑的，都非常建議也翻翻《心靈機器時代》，當中提到的時間與渾沌的定律（The Law of Time and Chaos），很值得一讀。
作者還在這章提到一個非常有意思的主題－－電腦史上不同時間點 PC 的記憶容量（megabytes）與運算速度（MIPS）相除，會粗略維持一個常數，約 1 秒鐘（大概等於電腦將整塊記憶體掃一次需要耗費的時間），原因是電腦跟外界溝通的主要對象是人類，所以要受人類的速度感所束縛，原文對這部份描述得很生動：
The megabyte/MIPS ratio seems to hold for nervous systems too! The contingency is the other way around: computers are configured to interact at human time scales, and robots interacting with humans seem also to be best at that ratio.
On the other hand, faster machines, for instance audio and video processors and controllers of high-performance aircraft, have many MIPS for each megabyte.
Very slow machines, for instance time-lapse security cameras and automatic data libraries, store many megabytes for each of their MIPS.
Flying insects seem to be a few times faster than humans, so may have more MIPS than megabytes.
As in animals, cells in plants signal one other electrochemically and enzymatically. Some plant cells seem specialized for communication, though apparently not as extremely as animal neurons. One day we may find that plants remember much, but process it slowly.
電腦是 Universal Turing Machine, UTM 的一個良好近似，和 UTM 對應的是 Universal Robots, UR 。不同的是 UTM 專職在虛擬的數位空間發揮運算能力， UR 則落實到現實世界裡的感官及行動上。
萬用機器人是第四章的主題，看看作者對這個議題的看法還滿有趣的。而第四章之後的章節雖很讓人眼界大開，但扯得有點遠了，現在還是將它當作科幻小說的情節，看看就好 :p
也許拜大廠效應（例如 Google、微軟及鴻海等相繼投入）所賜，也或者只因為熱門 Robot 商品接續問市所致，總覺得這陣子 Robot 愛好者有增多的趨勢。
碰巧這陣子我也 K 了好些 Robot 相關的書，內容包括理論及實作，涵蓋了電子、電機、機械、機構等，趁空檔把這些書整理整理，上來和大家分享 ^__^
要買 Robot 書，原文部份，天瓏那有專櫃，大家可以去翻閱翻閱；此外，若水堂那有許多相關簡中書，許多甚至是日文或英文書的中譯本，強烈建議去那瞧瞧，絕對不會讓您失望的。
以下就把我認為值得一讀的幾本列出來供大家參考：
更詳細的購買資訊，可以參考我利用 Google Docs and Spreadsheets 所作的整理。
