OSSP 的 uuid 函式庫內有精簡的 md5/sha1 hash 實作

手邊 C++ 專案需要實現 SHA1 hash 的功能, 原本想到的是透過 OpenSSL / Botan 這類的現有函式庫來達到, 但轉念想想沒道理為了加扇窗就把整棟大樓的材料都堆進來. 就一直在網上尋找精簡的 md5/sha1 hash 實現. 不知道是鬼打牆還是怎地一直沒找到. 而事情就這麼巧, 接著在找 uuid 開源替代方案時找到 OSSP 的 uuid 專案, 裡面竟然帶有一套不依賴任何第三方函式庫的 md5/sha1 實現. 整個專案還是用 MIT 授權, 真是踏破鐵鞋無覓處...

有個小問題是 uuid 目前的 build process 不支援 Windows 平台 (以 OSSP 的宗旨來看也很合理) , 它是基於 autogen/configure 那一套 unix 標準程序的, 引用的 header 中也有包含 unistd.h 這類在 Windows 缺乏對應的文件. 不過評估了一下 porting 的功夫不會很大, 小改了一下目前在 MSVC 環境中已可建置它的 md5/sha1 hash 模組. 有時間會嘗試整個 porting. 想要導入 cmake 代替原有的 autogen, porting 完之後可以一次搞定 msvc, mingw, cygwin 三個環境.

Sourceforge: http://sourceforge.net/projects/osspuuidwin32/

跨網路資料交換

最近這一個月都在反覆實作與檢示 Client Server 之間的資料交換架構. 一般最直觀的資料交換, 就是任何一方發送資料時先經過制式的序列化 (serialization, 或稱 deflating, marshalling) 程序, 把運行時結構化的數據資料成員重新排列成平面且緊密的純二進位資料流 (binary data stream), 然後將資料流送出, 接收方再透過相對應的反序列化程序 (deserialization, 或稱 inflating, unmarshalling) 把收到的資料流重組回結構化的數據.

這樣直觀的流程套用在開發專案時會遇到一個問題: 每種需要進行資料交換的結構化數據類型都必需要撰寫其專有的序列化/反序列化程序. 這樣的需求在結構化數據類型會隨專案開發的進度而大量增加時就會變得很繁瑣. 為了解決這種窘境, 我們會希望在序列化時盡量讓輸出的資料流保有某種程度上的自述性. 也就是說不管面對何種類型的數據類型, 序列化/反序列化的做法都要能是同一套, 序列化時除了資料本身之外, 還夾帶了這些資料的型態, 彼此的結構關系這類資訊, 提供反序列化程序檢示, 賴以重組回結構化的數據. 舉一個極端的例子: 進行序列化時, 將結構數據輸出為用 JSON 或 YAML 這類資料描述語言的描述語句, 反序列化時解析這些語句重組回結構化數據. 通常這些描述語言都已有很好的各類程序語言函式庫, 可提供現成的輸出描述語句和解析語句的功能.

輸出具有自述性的資料流會有個不良影響是會導致資料流的膨脹. 原本只要夾帶資料本身, 現在要多附加資料型態和結構關係, 所以因資料膨脹導致交換效能降低是必然的結果. 那麼在效能跟繁瑣之間有沒有妥協方案呢? Google 提倡的 protobuf 就是一例. 它的運作原理是, 把資料型態和結構化關係這類額外的資訊另外寫成 .proto 的文件 (protobuf 本身的資料描述語法), 透過 protobuf 提供的編譯功能編譯這些 .proto 文件產生專有的序列化/反序列化模組, 程式運行時再透過這些模組對於該資料類型進行序列化工作. 輸出的二進位資料流的緊密度和效能就由 protobuf 來背書, 理論上會比自述性資料流來得好, 因為要傳輸的資料較密(量較少)且序列化過程中做的事較少.

目前已實現基於 JSON 自述的序列化程序, 正朝 protobuf 前進. 由於需要交換的結構化數據都是用 XML Schema 定義, 所以要做 protobuf 的實現必需先克服由 XML Schema 自動生成 .proto 文件的這一步.

如何查看編譯器預先定義的巨集 (Predefined Macro) 有哪些?

建立跨平台且能兼容各家編譯器的 C/C++ 軟體專案時會需要知道各家 Compiler 在不同平台上分別會設定哪些 Predefined Macro, 以便後續於程式碼中利用.

目前 GNU 和 LLVM-Clang 的 Compiler 不管是 Unix 上或是 Windows 上的 cygwin/mingw 環境中, 都可透過同樣的方式去取得 Predefined Macro 列表:

    <gcc|g++|clang> -dM -E -x <c|c++> <input file>    

例如:

    clang -dM -E -x c /dev/null    

    g++ -dM -E -x c++ /dev/null    

而微軟的 cl 所定義的巨集可以直接查看 msdn 文件.

備忘: Unicode, UTF-8, CESU-8

最近都在跟 Redis 打交道, 我們的專案內部的字串資料都是用 wchar_t 的型式來操作的, 沒想到一考慮到跨平台就要面臨 Windows 和 Unix 對於 wchar_t 長度各自表述的問題. 又為了省空間 (字串純英數的比例較大), 在從資料庫存取字串時, 都加上了 UTF-8 (正確來說, 是 CESU-8) 轉換. 費了很多意料之外的時間在處理這些相關問題. 簡單整理了幾點注意事項備忘:

• Unicode 定義中, 一個字碼單位稱為一個 code point. 每 65,535 個 code points 組成一個 plane. 而目前總共定義有 17 個 planes. 最常用的字碼都集中在第一個 plane 中 (plane #0), 該 plane 又稱為 BMP (Basic Multilingual Plane).
• Windows 中的 wchar_t 長度是 16 bits, 使用 UTF-16 編碼. 16 bits 只有辦法涵蓋一個 plane 的字碼量, 因此正常來說就是映射到 BMP 的字碼. 罕見情況下需要使用其它 plane 中的字碼時, 就用連續的兩個 wchar_t 來表示一個 Unicode code point (稱為 Surrogate Pair, 代理對). 所以不要認為 Windows 系統上所有的 wchar_t 字串  raw bytes 長度除以 2 就是字串長. 有機會陰溝裡翻船.
• Unix 中的 wchar_t 長度是 32 bits, 使用 UTF-32 編碼. 因為 32 bits 已經可以涵蓋所有 planes 所有 code points. 所以 Unix 上一個 wchar_t 一定就對應到一個 Unicode code point.
• UTF-8 轉換理論上要能函蓋所有 code points, 但實際上大多數的 UTF-8 轉換實作都只針對 BMP 中的 code points. 意即每次讀入一個 UTF-16 2bytes 轉換為 UTF-8 1~3bytes, 且不考慮 Surrogate Pair, 因此 Surrogate Pair 的兩個 wchar_t 會被錯誤地當成兩個獨立的 UTF-16 字碼進行轉換. 現今漸漸改用 CESU-8 這個詞來稱呼這種較簡略且非正規的轉換法. CESU 為 Compatibility Encoding Scheme for UTF-16 的縮寫.
• Modified UTF-8 原理其實跟 CESU-8 是幾乎相同的 (所以正確來說, 應該叫 Modified CESU-8), 只差在 UTF-16 中的 NULL (即 0x0000) 並不轉換為 (0x00), 而是 (0xC080) 的雙字節, 以避免該 (0x00) 被當成字串結尾.
• 包含 Orcale, Java, Dalvik, Tcl, 等等重量級的軟體專案, 其中號稱的 UTF-8 轉換, 其實都只有達到 CESU-8 或 Modified UTF-8 的程度.

References:

1. http://en.wikipedia.org/wiki/Unicode
2. http://en.wikipedia.org/wiki/UTF-8
3. http://en.wikipedia.org/wiki/CESU-8

C++11 導入的新觀念 extern template

雖然說是 C++11 的新觀念, 但早在 C++0x 時代 (C++11 還沒正式確定前的草案) 各家 Compiler 就已經在追 spec 了. 所以目前 Visual C++ 2008/2010 以及 GNU G++ 4.3 版以後都已經有支援 extern template.

提到 extern template 之前, 先複習一下 Template: C++ 的 Template 是一種樣版的觀念, 定義 Template 時通常會定義一些尚未確定的變數型態. 所以當編譯器處理到 Template 定義時, 它並不能直接生成執行碼, 而是要等到有人使用這個 Template, 決定了那些未定型態的變數真正的型態之後 (instantiate, 或稱實例化) , 才能生成執行碼. 這也是為何有些高度使用 Template 的 C++ 的函式庫能夠號稱以 "header only" 的型式散佈 (Ex: Boost C++ Library).

不過這樣作法會導致一個問題, 若有一個 Template (Ex: std::vector<T>), 在很多不同的檔案中都被使用到了, 而且以相同的對象實例化 (Ex: 皆為std::vector<int>), 那麼編譯器依序編譯這些檔案時, 每份 obj 文件中都會有一份該 Template 針對該型態實例化後的代碼 (*1). 這樣不但費時而且多餘. extern template 所要解決的就是這個問題, 它可以用來向編譯器宣告: 某個 Template 的特定對象實例化代碼, 可以在別處找到, 請不要再翻一次. 最後在連結階段再去尋找它的實例化代碼並且連結起來, 以達到加速編譯的目的 (最終程式大小也會變小).

為了驗證這個觀念, 做了一個小實驗. 有一個 Template class 名為 MyClass<T>, 定義在 MyClass.h:

#pragma once
#include <stdio.h>

template<typename T>
class MyClass
{
public:
    void print(T data) { printf(SALT ": data %d\n", data); }
};

假設某個函式庫使用到了這個 MyClass<T>:

#define SALT "lib"
#include "MyClass.h"

// libfunc() is not used in main program.
// It is here just to make sure compiler 
// instantiate the MyClass<int>
extern "C" void libfunc(int data) {
    MyClass<int> b;
    b.print(data);
}

// Compile this library by:
// g++ -o libtest.so thisfile.cpp -fpic -shared

另外使用這個函式庫的主程式也引用了 MyClass.h:

#define SALT "main"
#include "MyClass.h"

extern template class MyClass<int>;

int main(int argc, char *argv[]) {
    MyClass<int> b;
    b.print(50);
    return 0;
}

// Compile this by:
// g++ -o test thisfile.cpp -L. -ltest
// Run by:
// env LD_LIBRARY_PATH=. ./test

因為兩份文件定義了不同的 SALT, 我們可以用此鑑別最終呼叫的究竟是哪一方的 MyClass 實例化代碼.

若沒有 extern template class MyClass<int>; 這一行, 編譯器會幫主程式也產生一份 MyClass<int> 的實例化代碼, 輸出會是:

main: data 50

反之若有 extern template class 那一行, 編譯器就不會再實例化 MyClass<int>, 最後連結時發現函式庫中已有所需的代碼, 就會直接使用, 因此輸出會是:

lib: data 50

這樣的作法還提供了跨函式庫傳遞樣版物件時一個很好的解套方式, 回憶跨函式庫進行記憶體配置與釋放需考慮 Runtime 連結方式, 連結靜態 Runtime 時, 因為分立的 Heap 導致不能相互釋放對方配置的記憶體區塊, 使得樣版設計時要考慮更多, 綁手綁腳. 現在使用方只要確定有宣告 extern template, 確定使用函式庫內的樣版實例化代碼就可以保證連結到同樣的 Runtime 使用同樣的 Heap. 避掉這個棘手的情況.

*1: http://en.wikipedia.org/wiki/C%2B%2B0x#Extern_template

跨函式庫進行記憶體配置與釋放需考慮 Runtime 連結方式

最近發現在 Windows 中跨函式庫進行專案開發時, 只要是在函式庫中配置出 (new, alloc) 的記憶體, 不能在其它地方釋放 (delete, free). 不然馬上會有作業系統發出的例外通知. 特別的是這種情況只會發生在與 CRT 靜態連結的時候 (/MTd or /MT), 反之若是動態連結 CRT (/MDd or /MD) 就不會有這個問題.

網路上找了一些資訊, 以這幾篇提到的最為相關:

• http://stackoverflow.com/questions/443147/c-mix-new-delete-between-libs
• http://stackoverflow.com/questions/2266218/memory-heap-management-across-dlls

具體來說, 記憶體的配置與釋放是依賴 Runtime 在其所屬的 Heap 中進行操作的. 當主程式與函式庫分別都與 Runtime 做靜態連結時, Heap 會是各自擁有, 因此有某一方在其 Heap 中配置了記憶體區塊, 一定也只能在其中釋放, 另一方的 Heap 是全然無記錄的.

解決方法在上述的討論中已提到了很多, 就不再提及. 不過討論中有個點我蠻在意, 有位老兄提到這是共通的平台問題, 其它作業系統也會發生的. 由於我之前大都在 Linux 環境中工作, 但一直沒注意到這問題, 實在好奇就自己在 Linux 下做了一些實驗.

首先寫了一個簡單的函式庫, 它只有一個函數, 配置一塊記憶體空間後返回其指針.

#include <stdlib.h>

char* func() {
    return (char*)malloc(100);
}

編譯時分別編出與 Runtime (libc) 動態與靜態連結的版本:

gcc -o libtestlib.so -fpic -shared testlib.c          // 動態
gcc -o libtestlibs.so -fpic -shared -static testlib.c  // 靜態

接著是調用該函式庫的主程式, 這裡用的是顯式連結(Explicit Linking)而非隱式(Implicit Linking), 原因後述.

#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>

int main(int argc, char *argv[]) {
    int* (*func_ptr)();
    if (argc <= 1) return 0;

    // Load library specified as argv[1]
    void* handle = dlopen(argv[1], RTLD_NOW); 
    if (!handle) { 
        printf("failed to load library.\n"); 
        return 0;
    }

    // Get function ptr
    func_ptr = dlsym(handle, "func"); 
    if (!func_ptr) { 
        printf("null func_ptr!\n"); 
        dlclose(handle); 
        return 0;
    }

    // Invoke
    int* a = func_ptr(); 
    // Try to free the memory block alloced in library.
    free(a); 

    return 0;
}

編譯時一樣分別編出與 libc 動態與靜態連結的版本:

gcc -o test -ldl test.c           // 動態
gcc -o tests -ldl -static test.c  // 靜態

執行後會發現, 與 Runtime 靜態連結的版本 (tests) 在試圖釋放指針時, 會產生 double free 的例外. 但動態連結的版本 (test) 可以正常執行完畢. 發現這問題的確是平台共通的問題.

為何不用隱式連結? 我發現原因跟我之前為何從未注意到這問題有關係. Linux 下的 GCC toolchain 在進行編譯連結時, 對於函式庫的動態與靜態連結, 只會給你兩個大方向: 要嘛就全靜態, 要嘛就全動態, 關鍵看你有沒有指定 -static 這個參數. 而在 Windows 上遇到的這個問題, 是函式庫本身與 Runtime 靜態連結, 但函式庫和主程式之間卻是動態連結. 我在 Linux 上重現這樣的連結方式, 發現一定要先單獨將函式庫編好, 然後主程式中用顯示連結的方式來呼叫才有辦法做到. 若是直接指定 -static, 那麼連結器就會直接找函式庫的 .a 檔而非 .so 檔了. 可以說某種程度上, GCC toolchain 的參數設定方式簡化了連結方式的可能性, 這大概能解釋為何我 (也或許大部分先接觸 Unix 的人) 不曾在 Linux 上注意過此類問題吧.

Redis 導入筆記

Karl Seguin 有在網路上發表了一本免費的電子書: The Little Redis Book, 包含了 Redis 簡介與基礎知識. 一共短短 28 頁, 幾個小時就能獲得相當充足的入門資訊.

目前 Redis 官方尚不支援 Windows 的平台, 但是 Dušan Majkić (dmajkic) 這位老兄有公佈他非官方的 Win32/64 native port. 也有預先編好的執行檔可供下載. 下載完解開, 執行裡面的 redis-server.exe 啟動 server, redis-cli 則是純文字的 client. 可配合入門書邊看邊做些練習. 自己的 Windows C/C++ 程式中若要導入 Redis, 需要的 Redis C binding library - hiredis 也已經被 dmajkic porting 好, 在他的 source tarball 中可以找到.

實際上在 Windows 專案中要導入 Redis 時還會遇到一個問題是 dmajkic 提供的 porting 是基於 MinGW 的編譯環境, 若要在 Visual C++ 的專案中導入 hiredis 會缺少檔頭和 lib 檔這些東西. 不過還好可以在 MinGW 的環境中透過一些方式來補齊. 以下簡列步驟:

1. 安裝 MinGW 和 Visual Studio
2. 將 dmajkic 的 source tarball 解開在 msys 的家目錄中 (假設解在 D:\MinGW\msys\1.0\home\zevoid\dmajkic-redis)
3. 修改 hiredis 的 Makefile 使其可產生 exp 文件, 該文件後續可用來生成 lib 文件. 具體作法為編輯 Makefile, 尋找 MINGW32_NT, 將其後的 DYLIB_MAKE_CMD 內容最後面加上 -Wl,--output-def,hiredis.def
4. 執行 MinGW 的 Shell, 到 D:\MinGW\msys\1.0\home\zevoid\dmajkic-redis 底下進行 make; 接著切換目錄到 deps/hiredis 中進行 make dynamic, 確認有無 hiredis.dll 和 hiredis.exp 文件產生.
5. 開啟一個 Visual Studio 的命令列提示, 切換目錄到 D:\MinGW\msys\1.0\home\zevoid\dmajkic-redis\deps\hiredis 底下, 進行 lib /def:hiredis.exp, 確認 hiredis.lib 文件產生
6. 修改一下 hiredis.h, 移除裡面對於 sys/time.h 的引用 (VC 中沒這檔頭)
7. 將 dll, lib 和改好的檔頭 .h 這三個文件供 VC 專案使用. 注意 porting 過的 hiredis 需要依賴 Winsock 函式庫, 故專案需要加上對於 ws2_32.lib 的依賴

* 需注意 Winsock 函式庫在使用前需要呼叫 WSAStartup(), 這一點 dmajkic 的 hiredis porting 沒有幫忙做, 使用前要自行動手呼叫.

另外在使用 hiredis 時要注意的一點, 由於 hiredis 的 redisCommand() 函數都是接受 ANSI C 字串, 而大部分的 Visual C/C++ 程式都已改用 wide char (wchar_t) 這類的 UTF-16 字串編碼. 若在這樣的前提之下, 想要透過 hiredis 的 binding 良好地跟 Redis server 做互動, 必需要避免意外的 null terminated 問題. 一個方法是都先把字串都轉成 UTF-8 再丟給 hiredis, 取回時一樣要逆轉. 另一個方法是直接將 UTF-16 字串以 binary 形式存到 Redis 中, 如此在呼叫 hiredis 的 redisCommand() 等等函數時, 在 printf 形式的 format 字串中要使用 %b 這個關鍵字來指定即將要傳入的是 binary, 不應理會 bytes stream 中的 null byte. Ex:

wchar_t *b = L"hahaha abcd";

redisCommand(ctx, "set myrawbytes %b", (unsigned char*)b, wcslen(b)*sizeof(wchar_t));

注意指定 %b 之後, 後面會預期接收 raw byte 指標和一個 byte count.