可變長碼解碼

條形碼讀碼器是一種利用光學原理獲得條形碼的映像、並將其轉化成數字電子信號的裝置。讀碼器要獲得條形碼的"相片"，必須要有光照明，多數為雷射。選擇雷射是因為它可以在很長的景深（即掃瞄器識讀條碼的距離）範圍內聚焦。

基本介紹

• 中文名：可變長碼解碼
• 外文名：Variable Length Decoding
• 檢測工具：Visual Leak Detector
• 條形碼：獲得條形碼的映像

可視雷射二極體VLD

條形碼讀碼器是一種利用光學原理獲得條形碼的映像、並將其轉化成數字電子信號的裝置。讀碼器要獲得條形碼的"相片"，必須要有光照明，多數為雷射。選擇雷射是因為它可以在很長的景深（即掃瞄器識讀條碼的距離）範圍內聚焦。　儘管CCD (英文全稱為"Charge CoupledDevice")讀碼器使用LED作為光源，但使用時必須使它緊貼條形碼或距離非常近，而雷射讀碼器則不同，因為它的景深有幾英寸長，所以不會對物體表面或條形碼造成刮擦或磨損。　此外，由於物體的防護材料（如玻璃）或物體本身的原因，讀碼器不可能接觸到條形碼時，長景深也會發揮優勢作用。　當讀碼器使用雷射時，通常會有一條雷射線掃描過條形碼。這就是條形碼掃瞄器得名的原因。用於條形碼掃瞄器的雷射類型有紅外雷射二極體、可視雷射二極體和氦氖雷射管。

由於多種原因，當前廣泛使用的是可視雷射二極體(英文簡稱"VLD""Visible Laser Diode")。雷射二極體的可靠性非常好，壽命要比氦氖雷射長几倍，而且工作電壓很低（通常只有2伏），沒有特殊供電要求。它們的封裝非常小而輕（如圖1所示），並且密封堅固。由於耗能非常小，它們可用在直接從計算機甚至電池取電的條形碼讀碼器中。　之所以選用可視雷射而不是紅外雷射，是因為IR類型的掃瞄器不能識讀列印在某些特殊材質上的條形碼。儘管條碼本身在人眼看來是暗條列印在淺色背景上，紅外雷射與可見光的被吸收程度是不同的。

紅外雷射沒有在條形碼掃瞄器中得到廣泛套用的另一個原因是：操作者在掃描時需要將可見的光線對準條碼。既然紅外光對於人眼是不可見的掃瞄器必須要有另外一個光源照亮條碼。　雷射二極體在構造上的另一個特徵是有一個光電感應監視器。除了晶片前端有雷射發射出來之外，後端也有一部分雷射發射出來。這部分光被位於雷射二極體內部的光電感應器所接收，由此產生的信號就可以在二極體密封體後方的一個管腳上得到。這個信號可以被VLD的驅動電路利用，以控制雷射能量的大小。　最後，可視雷射二極體的價格非常具有競爭力，僅是氦氖雷射管價格的幾分之一。因此套用在雷射條形碼掃瞄器中，VLD無疑是一種高效低價的解決方法。

可變長編碼

Variable Length Decoding 可變長解碼是VLC（variable-length coding）變長編碼的逆過程。

記憶體泄露檢測工具

VLD同樣是一款開源檢測記憶體泄露軟體的簡稱：Visual Leak Detector。

初識Visual Leak Detector

靈活自由是C/C++語言的一大特色，而這也為C/C++程式設計師出了一個難題。當程式越來越複雜時，記憶體的管理也會變得越加複雜，稍有不慎就會出現記憶體問題。記憶體泄漏是最常見的記憶體問題之一。記憶體泄漏如果不是很嚴重，在短時間內對程式不會有太大的影響，這也使得記憶體泄漏問題有很強的隱蔽性，不容易被發現。然而不管記憶體泄漏多么輕微，當程式長時間運行時，其破壞力是驚人的，從性能下降到記憶體耗盡，甚至會影響到其他程式的正常運行。另外記憶體問題的一個共同特點是，記憶體問題本身並不會有很明顯的現象，當有異常現象出現時已時過境遷，其現場已非出現問題時的現場了，這給調試記憶體問題帶來了很大的難度。

Visual Leak Detector是一款用於Visual C++的免費的記憶體泄露檢測工具。相比較其它的記憶體泄露檢測工具，它在檢測到記憶體泄漏的同時，還具有如下特點：

1、 可以得到記憶體泄漏點的調用堆疊，如果可以的話，還可以得到其所在檔案及行號；

2、 可以得到泄露記憶體的完整數據；

3、 可以設定記憶體泄露報告的級別；

4、 它是一個已經打包的lib，使用時無須編譯它的原始碼。而對於使用者自己的代碼，也只需要做很小的改動；

5、 他的原始碼使用GNU許可發布，並有詳盡的文檔及注釋。對於想深入了解堆記憶體管理的讀者，是一個不錯的選擇。

可見，從使用角度來講，Visual Leak Detector簡單易用，對於使用者自己的代碼，唯一的修改是#include Visual Leak Detector的頭檔案後正常運行自己的程式，就可以發現記憶體問題。從研究的角度來講，如果深入Visual Leak Detector原始碼，可以學習到堆記憶體分配與釋放的原理、記憶體泄漏檢測的原理及記憶體操作的常用技巧等。

本文首先將介紹Visual Leak Detector的使用方法與步驟，然後再和讀者一起初步的研究Visual Leak Detector的原始碼，去了解Visual Leak Detector的工作原理。

使用Visual Leak Detector(1.0)

下面讓我們來介紹如何使用這個小巧的工具。

首先從網站上下載zip包，解壓之後得到vld.h, vldapi.h, vld.lib, vldmt.lib, vldmtdll.lib,dbghelp.dll等檔案。將.h檔案拷貝到Visual C++的默認include目錄下，將.lib檔案拷貝到Visual C++的默認lib目錄下，便安裝完成了。因為版本問題，如果使用windows 2000或者以前的版本，需要將dbghelp.dll拷貝到你的程式的運行目錄下，或其他可以引用到的目錄。

接下來需要將其加入到自己的代碼中。方法很簡單，只要在包含入口函式的.cpp檔案中包含vld.h就可以。如果這個cpp檔案包含了stdafx.h，則將包含vld.h的語句放在stdafx.h的包含語句之後，否則放在最前面。如下是一個示例程式：

#include

void main()

{

…

}

接下來讓我們來演示如何使用Visual Leak Detector檢測記憶體泄漏。下面是一個簡單的程式，用new分配了一個int大小的堆記憶體，並沒有釋放。其申請的記憶體地址用printf輸出到螢幕上。

#include

#include

#include

void f()

{

int *p = new int(0x12345678);

printf("p=%08x, ", p);

}

int main()

{

f();

return 0;

}

編譯運行後，在標準輸出視窗得到：

p=003a89c0

在Visual C++的Output視窗得到：

WARNING: Visual Leak Detector detected memory leaks!

---------- Block 57 at 0x003A89C0: 4 bytes ---------- --57號塊0x003A89C0地址泄漏了4個位元組

Call Stack: --下面是調用棧，第一個為棧頂，依次入棧。

d:\test\testvldconsole\testvldconsole\main.cpp (7): f --表示在main.cpp第7行的f()函式

d:\test\testvldconsole\testvldconsole\main.cpp (14): main –雙擊以引導至對應代碼處

f:\rtm\vctools\crt_bld\self_x86\crt\src\crtexe.c (586): __tmainCRTStartup

f:\rtm\vctools\crt_bld\self_x86\crt\src\crtexe.c (403): mainCRTStartup

0x7C816D4F (File and line number not available): RegisterWaitForInputIdle

Data: --這是泄漏記憶體的內容，0x12345678

78 56 34 12 xV4..... ........

Visual Leak Detector detected 1 memory leak.

第二行表示57號塊有4位元組的記憶體泄漏，地址為0x003A89C0，根據程式控制台的輸出，可以知道，該地址為指針p。程式的第7行，f()函數裡，在該地址處分配了4位元組的堆記憶體空間，並賦值為0x12345678，這樣在報告中，我們看到了這4位元組同樣的內容。

可以看出，對於每一個記憶體泄漏，這個報告列出了它的泄漏點、長度、分配該記憶體時的調用堆疊、和泄露記憶體的內容（分別以16進制和文本格式列出）。雙擊該堆疊報告的某一行，會自動在代碼編輯器中跳到其所指檔案的對應行。這些信息對於我們查找記憶體泄露將有很大的幫助。

這是一個很方便易用的工具，安裝後每次使用時，僅僅需要將它頭檔案包含進來重新build就可以。而且，該工具僅在build Debug版的時候會連線到你的程式中，如果build Release版，該工具不會對你的程式產生任何性能等方面影響。所以盡可以將其頭檔案一直包含在你的原始碼中。

Visual Leak Detector工作原理

下面讓我們來看一下該工具的工作原理。

在這之前，我們先來看一下Visual C++內置的記憶體泄漏檢測工具是如何工作的。Visual C++內置的工具CRT Debug Heap工作原來很簡單。在使用Debug版的malloc分配記憶體時，malloc會在記憶體塊的頭中記錄分配該記憶體的檔案名稱及行號。當程式退出時CRT會在main()函式返回之後做一些清理工作，這個時候來檢查調試堆記憶體，如果仍然有記憶體沒有被釋放，則一定是存在記憶體泄漏。從這些沒有被釋放的記憶體塊的頭中，就可以獲得檔案名稱及行號。

這種靜態的方法可以檢測出記憶體泄漏及其泄漏點的檔案名稱和行號，但是並不知道泄漏究竟是如何發生的，並不知道該記憶體分配語句是如何被執行到的。要想了解這些，就必須要對程式的記憶體分配過程進行動態跟蹤。Visual Leak Detector就是這樣做的。它在每次記憶體分配時將其上下文記錄下來，當程式退出時，對於檢測到的記憶體泄漏，查找其記錄下來的上下文信息，並將其轉換成報告輸出。

初始化

Visual Leak Detector要記錄每一次的記憶體分配，而它是如何監視記憶體分配的呢？Windows提供了分配鉤子(allocation hooks)來監視調試堆記憶體的分配。它是一個用戶定義的回調函式，在每次從調試堆分配記憶體之前被調用。在初始化時，Visual Leak Detector使用_CrtSetAllocHook註冊這個鉤子函式，這樣就可以監視從此之後所有的堆記憶體分配了。

如何保證在Visual Leak Detector初始化之前沒有堆記憶體分配呢？全局變數是在程式啟動時就初始化的，如果將Visual Leak Detector作為一個全局變數，就可以隨程式一起啟動。但是C/C++並沒有約定全局變數之間的初始化順序，如果其它全局變數的構造函式中有堆記憶體分配，則可能無法檢測到。Visual Leak Detector使用了C/C++提供的#pragma init_seg來在某種程度上減少其它全局變數在其之前初始化的機率。根據#pragma init_seg的定義，全局變數的初始化分三個階段：首先是compiler段，一般c語言的運行時庫在這個時候初始化；然後是lib段，一般用於第三方的類庫的初始化等；最後是user段，大部分的初始化都在這個階段進行。Visual Leak Detector將其初始化設定在compiler段，從而使得它在絕大多數全局變數和幾乎所有的用戶定義的全局變數之前初始化。

記錄記憶體分配

一個分配鉤子函式需要具有如下的形式：

int YourAllocHook( int allocType, void *userData, size_t size, int blockType, long requestNumber, const unsigned char *filename, int lineNumber);

就像前面說的，它在Visual Leak Detector初始化時被註冊，每次從調試堆分配記憶體之前被調用。這個函式需要處理的事情是記錄下此時的調用堆疊和此次堆記憶體分配的唯一標識——requestNumber。

得到當前的堆疊的二進制表示並不是一件很複雜的事情，但是因為不同體系結構、不同編譯器、不同的函式調用約定所產生的堆疊內容略有不同，要解釋堆疊並得到整個函式調用過程略顯複雜。不過windows提供一個StackWalk64函式，可以獲得堆疊的內容。StackWalk64的聲明如下：

BOOL StackWalk64( DWORD MachineType, HANDLE hProcess, HANDLE hThread, LPSTACKFRAME64 StackFrame, PVOID ContextRecord, PREAD_PROCESS_MEMORY_ROUTINE64 ReadMemoryRoutine, PFUNCTION_TABLE_ACCESS_ROUTINE64 FunctionTableAccessRoutine, PGET_MODULE_BASE_ROUTINE64 GetModuleBaseRoutine, PTRANSLATE_ADDRESS_ROUTINE64 TranslateAddress);STACKFRAME64結構表示了堆疊中的一個frame。給出初始的STACKFRAME64，反覆調用該函式，便可以得到記憶體分配點的調用堆疊了。

// Walk the stack.

while (count < _VLD_maxtraceframes) {

count++;

if (!pStackWalk64(architecture, m_process, m_thread, &frame, &context,

NULL, pSymFunctionTableAccess64, pSymGetModuleBase64, NULL)) {

// Couldn&apos;t trace back through any more frames.

break;

}

if (frame.AddrFrame.Offset == 0) {

// End of stack.

break;

}

// Push this frame&apos;s program counter onto the provided CallStack.

callstack->push_back((DWORD_PTR)frame.AddrPC.Offset);

}

那么，如何得到初始的STACKFRAME64結構呢？在STACKFRAME64結構中，其他的信息都比較容易獲得，而當前的程式計數器(EIP)在x86體系結構中無法通過軟體的方法直接讀取。Visual Leak Detector使用了一種方法來獲得當前的程式計數器。首先，它調用一個函式，則這個函式的返回地址就是當前的程式計數器，而函式的返回地址可以很容易的從堆疊中拿到。下面是Visual Leak Detector獲得當前程式計數器的程式：

#if defined(_M_IX86) || defined(_M_X64)

#pragma auto_inline(off)

DWORD_PTR VisualLeakDetector::getprogramcounterx86x64 ()

{

DWORD_PTR programcounter;

__asm mov AXREG, [BPREG + SIZEOFPTR] // Get the return address out of the current stack frame

__asm mov [programcounter], AXREG // Put the return address into the variable we&apos;ll return

return programcounter;

}

#pragma auto_inline(on)

#endif // defined(_M_IX86) || defined(_M_X64)

得到了調用堆疊，自然要記錄下來。Visual Leak Detector使用一個類似map的數據結構來記錄該信息。這樣可以方便的從requestNumber查找到其調用堆疊。分配鉤子函式的allocType參數表示此次堆記憶體分配的類型，包括_HOOK_ALLOC, _HOOK_REALLOC, 和 _HOOK_FREE，下面代碼是Visual Leak Detector對各種情況的處理。

switch (type) {

case _HOOK_ALLOC:

visualleakdetector.hookmalloc(request);

break;

case _HOOK_FREE:

visualleakdetector.hookfree(pdata);

break;

case _HOOK_REALLOC:

visualleakdetector.hookrealloc(pdata, request);

break;

default:

visualleakdetector.report("WARNING: Visual Leak Detector: in allochook(): Unhandled allocation type (%d).\n", type);

break;

}

這裡，hookmalloc()函式得到當前堆疊，並將當前堆疊與requestNumber加入到類似map的數據結構中。hookfree()函式從類似map的數據結構中刪除該信息。hookrealloc()函式依次調用了hookfree()和hookmalloc()。

檢測記憶體泄露

前面提到了Visual C++內置的記憶體泄漏檢測工具的工作原理。與該原理相同，因為全局變數以構造的相反順序析構，在Visual Leak Detector析構時，幾乎所有的其他變數都已經析構，此時如果仍然有未釋放之堆記憶體，則必為記憶體泄漏。

分配的堆記憶體是通過一個鍊表來組織的，檢查記憶體泄漏則是檢查此鍊表。但是windows沒有提供方法來訪問這個鍊表。Visual Leak Detector使用了一個小技巧來得到它。首先在堆上申請一塊臨時記憶體，則該記憶體的地址可以轉換成指向一個_CrtMemBlockHeader結構，在此結構中就可以獲得這個鍊表。代碼如下：

char *pheap = new char;

_CrtMemBlockHeader *pheader = pHdr(pheap)->pBlockHeaderNext;

delete pheap;

其中pheader則為鍊表首指針。

報告生成

前面講了Visual Leak Detector如何檢測、記錄記憶體泄漏及其其調用堆疊。但是如果要這個信息對程式設計師有用的話，必須轉換成可讀的形式。Visual Leak Detector使用SymGetLineFromAddr64()及SymFromAddr()生成可讀的報告。

// Iterate through each frame in the call stack.

for (frame = 0; frame callstack->size(); frame++) {

// Try to get the source file and line number associated with

// this program counter address.

if (pSymGetLineFromAddr64(m_process,

(*callstack)[frame], &displacement, &sourceinfo)) {

...

}

// Try to get the name of the function containing this program

// counter address.

if (pSymFromAddr(m_process, (*callstack)[frame],

&displacement64, pfunctioninfo)) {

functionname = pfunctioninfo->Name;

}

else {

functionname = "(Function name unavailable)";

}

...

}

概括講來，Visual Leak Detector的工作分為3步，首先在初始化註冊一個鉤子函式；然後在記憶體分配時該鉤子函式被調用以記錄下當時的現場；最後檢查堆記憶體分配鍊表以確定是否存在記憶體泄漏並將泄漏記憶體的現場轉換成可讀的形式輸出。有興趣的讀者可以閱讀Visual Leak Detector的原始碼。

總結

在使用上，Visual Leak Detector簡單方便，結果報告一目了然。在原理上，Visual Leak Detector針對記憶體泄漏問題的特點，可謂對症下藥——記憶體泄漏不是不容易發現嗎？那就每次記憶體分配是都給記錄下來，程式退出時算總賬；記憶體泄漏現象出現時不是已時過境遷，並非當時泄漏點的現場了嗎？那就把現場也記錄下來，清清楚楚的告訴使用者那塊泄漏的記憶體就是在如何一個調用過程中泄漏掉的。

Visual Leak Detector是一個簡單易用記憶體泄漏檢測工具。現在最新的版本是1.9a，採用了新的檢測機制，並在功能上有了很多改進。讀者不妨體驗一下。