2013年3月17日 星期日

從動態二維陣列配置技巧領略 Windows 程式設計

由於 SL811 與 USB Protocol 相關資料還在整理中,這系列文章可能還不會馬上出爐,因此
先來看一看小主題,也就是標題所述帶領讀者寫一支簡單的動態二維陣列配置程式,可是
讀者可能會有疑問,這跟 Windows 程式設計有甚麼關係呢 ? 因為這支程式用純 Windows
API 撰寫,完全不使用 Microsoft Visual C++ Runtime Library DLL (後簡稱 MSVCRT DLL)
內的 malloc,也就是讀者將不只知道動態二維陣列配置的概念,還會了解如何呼叫視窗系統的 API 實現這種功能,這會建立讀者對於 "行程" 最基本的觀念。另外,會解說這個主題的次要原因是最近處理了一些巨大的二維資料陣列問題,問題根源在於繪圖視窗是執行階段才被動態建立,所以作為緩衝區之二維陣列不可能先行宣告,因此必須設計一組可以動態配置二維陣列的 C 介面用於根據繪圖視窗大小動態配置二維陣列,因此想說用這篇講述怎麼完全都用一維
角度模擬任意 N 維陣列的基本原理。

首先,讓我們看一看在 Windows 程式設計中最重要的基本觀念,就是每支程式其實都是一個
Process (行程),每一個 Process 內又有一堆 Thread (執行緒),Process 至少會有一個
Thread,因為 Thread 是作業系統最小的執行單元,如圖一所示 :

圖一 Process 概念圖

圖一是整個 Windows 程式設計最重要的記憶體配置基本觀念,這樣的觀念在其他 OS
中其實也是類似的組成,可以看到,原來一個 Process 下所有的 Thread 都會共用三塊
記憶體分別是 Global variables、Heap 與 環境字串,一個 Process 這三塊各只擁有一份
其中 Global variables (全域變數) 就是你在寫程式宣告為 static 或是 本來就放在全域的
變數,Heap (堆積) 也是記憶體的一種,也就是本篇會用到的記憶體區塊,我會示範直接用
Windows API 從這個區塊配置一些記憶體來用,會被稱為 Heap 是因為這塊記憶體的組成
其實是用 Page 拼堆起來,One Page 的大小通常在 32-bit OS 下是 4KB,實際大小可以透過
Windows API 取得。環境字串就是在執行檔後輸入的命令列參數,系統會放到環境字串專屬記憶體位址,可以用 GetEnvironmentStrings API 獲得輸入的命令列參數,然後得要自己
解析環境字串得到要用的輸入參數。另外一個重要的觀念就是 Thread Stack,區域變數的
本質就是存放在 Thread Stack,每一個 Thread 都擁有自己獨立的 Thread Stack。

讀者在學習 ANSI C 的時候都知道,Process 向 OS 要求配置記憶體可以用 malloc
今天的主題出現了,malloc 配置的記憶體其實就是 Heap,這裡就解釋了為何圖一的
觀念很重要,原來 Heap 也是共用的記憶體,跟全域變數很像,也可以在 Thread 之間
被共用,只是全域變數是在編譯時,編譯器將每個全域變數安排至特定記憶體位址,
而 Heap 由 Process 動態配置與使用,本篇文章就是要讓讀者了解到怎麼直接操作
Heap,因此不會用到 malloc,而是直接使用相關的 Heap API 配置 Heap 記憶體,這樣
做的好處是可以完全只用系統提供的 API 而沒有任何 MSVCRT 版本的問題,這樣程式
好移植高效率而且相容性極佳,完全繞過 MSVCRT DLL。

有了上面的介紹,接著來看看怎麼配置動態二維記憶體空間,這是一個數學問題,在
電腦內部其實記憶體就是線性排列,也就是說不管是幾維空間都可以映射至一維空間
這邊就不證明了,直接給出一般性結果 (以 C 語言索引從零算起為準) :

假設有一個 三維陣列大小 M[A][B][C],並且存取陣列索引於 M[a][b][c]
則實際映射至一維空間索引則是 M[C*B*a+C*b+c],N 維可以類推。

有了上面一般性結論,我們來測試一個 二維陣列 就知道對不對了

假設有一個 C 語言二維陣列

A[2][3] =
{
        {0, 1, 2},
        {3, 4, 5}
};

A[1][2] 時內容為 5,一維索引就是 3*1 + 2 = 5 ;
A[1][1] 時內容為 4,一維索引就是 3*1 + 1 = 4 ;
A[1][0] 時內容為 3,一維索引就是 3*1 + 0 = 3 ;

根據這樣的結果,我們可以配置一個任意一維陣列,在設計一條巨集
模擬二維索引的存取動作 :

假如 一維陣列 P[ROWS * COLS],用巨集做二維陣列存取就是

#define RCMAPPING(P,COLS,R,C) (P)[(COLS)*(R)+(C)]

透過這樣的巨集存取 P 就等價於 P[R][C]。

剩下的問題就是,那怎麼用 Windows API 直接配置 Heap 記憶體,讀者應該要建立起操作 Windows 下所有物件,都要先取得該物件的 Handle,有這樣的觀念後在看圖一,既然要操作 Handle,顯然要先取得於目前 Process 空間下的 Heap Handle,所以先呼叫 GetProcessHeap API 取得目前 Process 空間的 hHeap,拿到了 hHeap,剩下的就是操作 HeapAlloc HeapFree,這個用法與 malloc 和 free 簡直一模一樣,但是第一個參數要填入取得的 hHeap,表示Process 要配置 Heap 記憶體,原來這些 Heap API 就是 malloc 與 free 的底層函式。

下面給出我寫好的原始程式碼

/*
=======================================================
Code Example: Simple Dynamic 2D Array
Author      : UBIWU
=======================================================
*/

/* Exclude rarely-used stuff from Windows headers */
#define WIN32_LEAN_AND_MEAN

/* Enable current Windows version visual styles */
#pragma comment(linker,"\"/manifestdependency:type='win32' \
name='Microsoft.Windows.Common-Controls' version='6.0.0.0' \
processorArchitecture='*' publicKeyToken='6595b64144ccf1df' language='*'\"")

#include <windows.h>  // Windows headers files
#include <windowsx.h> // Windows extension header files
#include <process.h>  // Need this for calling _beginthreadex
#include <commctrl.h> // Windows common control header files
#include <shlwapi.h>  // Shell lightweight utility functions
#include <tchar.h>    // Generic-Text Mappings

#pragma comment(lib, "user32.lib") // GetAsyncKeyState API in user32.lib

typedef float FP32;
typedef FP32* PFP32;

typedef struct tagDYN2DARRAY
{
    PFP32  pfp32Data;
    LONG   lTotalRows;
    LONG   lTotalCols;
}DYN2DARRAY,*PDYN2DARRAY;

#define RCMAPPING(P,COLS,R,C) (P)[(COLS)*(R)+(C)]

static TCHAR g_szBuf[256];

int APIENTRY WinMain
(
 HINSTANCE hInstance,
 HINSTANCE hPrevInstance,
 LPTSTR    lpszCmdLine,
 int       nCmdShow
)
{
    DWORD  dwWritten;
    UINT   cxIdx,cyIdx;
    HANDLE hHeap,hStdout;
    UINT   nBufSize;
    DYN2DARRAY dyn2d;

    AllocConsole();
    hStdout = GetStdHandle(STD_OUTPUT_HANDLE);

    dyn2d.pfp32Data  = NULL;
    dyn2d.lTotalRows = 2;
    dyn2d.lTotalCols = 3;
    nBufSize = dyn2d.lTotalRows * dyn2d.lTotalCols;
    hHeap = GetProcessHeap();
    dyn2d.pfp32Data = (PFP32)HeapAlloc(hHeap, 0, sizeof(FP32)*nBufSize);

    dyn2d.pfp32Data[0] = 0;
    dyn2d.pfp32Data[1] = 1;
    dyn2d.pfp32Data[2] = 2;
    dyn2d.pfp32Data[3] = 3;
    dyn2d.pfp32Data[4] = 4;
    dyn2d.pfp32Data[5] = 5;

    for(cyIdx = 0; cyIdx < dyn2d.lTotalRows; ++cyIdx)
    {
        for(cxIdx = 0; cxIdx < dyn2d.lTotalCols; ++cxIdx)
        {
            FP32 f32Val = RCMAPPING(dyn2d.pfp32Data, dyn2d.lTotalCols, 
                                    cyIdx, cxIdx);
            _stprintf(g_szBuf, _T("R%ld,C%ld=%f\n"), cyIdx, cxIdx, f32Val);
            WriteConsole(hStdout, g_szBuf, _tcsclen(g_szBuf), &dwWritten, NULL);
        }
    }

    if(dyn2d.pfp32Data)
    {
        HeapFree(hHeap, 0, dyn2d.pfp32Data);
        dyn2d.pfp32Data = NULL;
        dyn2d.lTotalRows = 0;
        dyn2d.lTotalCols = 0;
    }

    _stprintf(g_szBuf, _T("Press ESC key to exit"));
    WriteConsole(hStdout, g_szBuf, _tcsclen(g_szBuf), &dwWritten, NULL);

key_loop:
    if(GetAsyncKeyState(VK_ESCAPE) & 0x8000)
        goto key_exit;
    else
        goto key_loop;

key_exit:
    return 0;
}


可以看到我直接用 WinMain 寫 Console 型式的程式,因此呼叫了 GetAsyncKeyState 來將程式卡住,直到按下 ESC 按鍵才會結束,另外也順便在把前面自創進入點一文中 使用的系統 Console API 分別是 AllocConsole GetStdHandle WriteConsole 直接將結果顯示於 配置的 Console 視窗,不依賴 printf,至此,我們已經完成了一個真正的視窗程式設計完全使用 Windows API 達成所要的任務,真正的視窗程式設計並非一定要有 GUI 畫面要使用訊息迴圈這些東西,而是您是否能夠只用 Windows API 達成所要的功能,本篇示範了另外一種完全以 Console 為主的 WinMain 程式,完全只使用 Windows API 進行 Heap 記憶體配置,也不需呼叫 MSVCRT 內的 malloc。

補充 : 原始碼內 include 的那些 Header file 其實是寫視窗程式很常用的標準項目,通常我不管有沒有用都把那些東西貼上去,我寫這支程式的時候也是從以前寫的程式貼過來這邊,寫視窗程式基本上這些 Header file 通通都放著,不管是否真的有用到 Header file 裡面的函式。

讀者也可以自己用上面的原始碼測試看看~~~

執行結果如下


我是在指令列下編譯的程式原始碼,指令如下

cl /O2 DynAlloc2DMem.c

當然也可以用 Visual Studio 開個專案貼上原始碼來編譯
因為進入點是 WinMain,專案類型記得要選 Win32 專案

所以說 有時候敲指令反而比 Visual Studio 開專案編譯來的簡單

最後用 Dependency Walker 檢查這支程式與 DLL 的相依性


可以看到這支程式確實沒有用到 MSVCRT DLL 只使用了系統標準的 DLL,
也就是說,這支程式假如移到 Win7 32-bit 上仍然可以執行,因為是動態連結,
同樣的 API 所呼叫的版本自動就變成 Win7 系統上面的版本了。
視窗系統有三根重要核心支柱,分別是 KERNEL32.DLL USER32.DLL GDI32.DLL
一般來說,寫程式呼叫的程式庫越少越好,尤其是 DLL,但是所需的工程時間就會變長,
因為所有的功能得自己實現,好處就是整個程式軟體層少,速度快,但是有些功能
很複雜在加上可能沒有相關的背景,例如你的程式要解 MP3 要自己來恐怕就很困難了,
這時候就得要呼叫一些 Thirty Party 程式庫來解決問題。

在這篇讀者可以認識到

1. 怎麼直接使用 Heap API 配置記憶體 粗淺的了解 C 程式庫內 malloc 原始的面貌。

2. 直接使用 AllocConsole GetStdHandle WriteConsole 與 _stprintf 實現類似
    printf 的功能。
3. 了解第二點後就直接用視窗程式進入點 WinMain 寫出類似 Console 專案的程式。

4. 用這個架構好的程式框架寫一支簡單的 動態二維陣列配置程式。
 -----------------------------------------------------------------------------------------------------------------
後記補充 : 讀者雖然看到在程式上極度簡化到只使用了 USER32 KERNEL32
事實上有兩個部分還是用到了 MSVCRT,主要是進入點的呼叫程式與使用
_stprintf ,這與 VC 連結器預設會自動取用 靜態版本 MSVCRT 有關,這兩部分是
非常原始的環境,牽涉到進入 WinMain 前的啟動預備環境實現格式化字串常式
實現這兩部份的工程非常複雜大約會有兩千行左右的程式碼,在這篇短短的小文中,
我們不應該去實現這些低階環境也沒那個時間,靜態版本的好處就是把用到的部分
直接將機械碼嵌入執行檔內,這樣就變成執行檔的一部份,因為 CRT 內的所有函式
最終要與系統互動的某些功能其底層就是呼叫 Kernel32.dll 裡面的函式了
所以我指的是在進入 WinMain 後也就是 User 寫程式的地方,盡可能使用 Windows API
來撰寫程式,一來可以培養更深的功底,二來可以加深對作業系統固有程式庫有更深的認識。
進入 WinMain 前的啟動預備環境位於 MSVCRT 內的函式 _tmainCRTStartup,讀者寫程式
不管事 main 還是 WinMain 事實上就是被它呼叫,它非常重要,因為它在呼叫 main 或
WinMain 前會進行一系列 Heap 的初始化動作,沒有經過這些動作,你就不能在
WinMain 程式開頭處只簡單的直接用 GetProcessHeap 取得 hHeap,那就得要呼叫
更低階的 HeapCreate 從頭製造 Heap 記憶體,這可就累了。總之,假如讀者還是想了解
CRT 程式庫裡面是怎麼實現這些功能,那只有閱讀程式碼了,給出主要幾個關鍵的原始檔

crt0.c         _tmainCRTStartup 所在之處
heapinit.c  _tmainCRTStartup 呼叫初始化 Heap 的函式被實作在這個檔案
output.c    實現格式化字串主要函式,例如 printf.c 最後也會呼叫這個模組裡面的函式

以上三個檔案就是 MSVCRT 中最重要的原始檔,基本上研究 CRT 程式庫原始碼並不是一件
簡單的任務,裡面牽涉到許多作業系統運作的原理,很大一部分圍繞在記憶體管理,主要
是檔案名稱開頭為 heap 相關的 C 檔案,另外一個巨大的輔助程式庫就是字串操作,當然還
有非常多其他零零散散的輔助函式,MSVCRT 會變的目前這麼複雜也不是一天造成,是跟
隨 Visual Studio 逐漸改版過好幾年進化而來,我自己的經驗是要直接念微軟的 MSVCRT 
原始碼增強編程功力最好從 VC6 的版本開始讀,假如你直接切入 VS2008 以上的 MSVCRT
原始碼,恩,大概只會霧裡看花,毫無收穫。

再次感謝學弟提供這個撰文評台 ...

因為排版問題,程式碼上色的部分改用 Online syntax highlighter like TextMate






Style 採用 Dawn

沒有留言:

張貼留言