一種基于樹狀結(jié)構(gòu)的新型解碼器

摘要：介紹了一種新型解碼器，能夠在數(shù)據(jù)包中解碼出期望KPI的值。在機站測試等過程中，需要查看一些KPI值，而所有KPI是服務(wù)器端以數(shù)據(jù)包的形式發(fā)送到客戶端的。解碼器首先把各個目標KPI按位與，得到總的目標值m，然后m與樹狀結(jié)構(gòu)中的非葉子結(jié)點以及葉子結(jié)點按位與，如果結(jié)果值不等于非葉子結(jié)點，則跳過其子結(jié)點，繼續(xù)和其兄弟結(jié)點按位與，直到找到期望KPI。這種方法不用解碼出數(shù)據(jù)包中的全部數(shù)據(jù)，即可得到期望的KPI值，簡便而又高效，大大提高了工作效率。
關(guān)鍵詞：解碼器；數(shù)據(jù)包；樹狀結(jié)構(gòu)；C++；JAVA

0 引言
計算機網(wǎng)絡(luò)數(shù)據(jù)通常是以數(shù)據(jù)包進行傳輸?shù)?，?shù)據(jù)包由報頭、負載、報尾等部分組成。在機站測試等過程中需要經(jīng)常得到大量KPI(Key parameterindicator)的值，而這些KPI是由服務(wù)器以數(shù)據(jù)包的形式發(fā)送到客戶端的，那么如何在以二進制表示的數(shù)據(jù)包里面快速而準確地得到期望的KPI的值呢?在此設(shè)計了一個高效而實用的解碼器，用以快速得到某一字段的KPI值。

1 解碼器簡介
解碼器源代碼是一些C++代碼，用來解碼出數(shù)據(jù)包對應(yīng)的KPI的值。在基站、網(wǎng)絡(luò)等測試過程中經(jīng)常需要統(tǒng)計各種KPI的值，而相關(guān)KPI的值有時多達幾十甚至幾百個，如果想要在這龐大的數(shù)據(jù)里面，快速有效地得到一個或者幾個KPI的值，普通的方法是把這段碼流進行解碼得到全部對應(yīng)的值之后再查找期望的值。這種方法不僅費時費力而且容易出錯，在此利用一種樹狀結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)設(shè)計出了解碼特定值的解碼器，用以獲取期望KPI的值。這種解碼器不僅能夠幫助工作人員快速得到期望的KPI值，而且減少出錯的幾率，提高了工作效率。
下面介紹一些名詞的含義，消息是指由基本數(shù)據(jù)類型表示各種KPI及其組成形式的集合。消息定義文件是指用來定義諸如XSD、C頭文件、文本文件等消息格式的文件格式。邏輯表是XML格式文件，用來定義一些無法用C頭文件描述的邏輯條件。XSD即XML Schema Deftnition，用以規(guī)范和驗證XML格式的文檔。
每條信息對應(yīng)一個解碼函數(shù)，用以解碼數(shù)據(jù)包里面對應(yīng)的二進制流數(shù)據(jù)，各種解碼函數(shù)構(gòu)成了解碼器。它不是解碼整條消息，而是有選擇地解碼部分比特流以得到期望的KPI的值，因此它是非常高效的。
端模式(Endian)是指在計算機體系結(jié)構(gòu)中存儲信息的不同順序，分為大端(Big-endian)和小端(Little-endian)。大端指數(shù)據(jù)的高位存儲在內(nèi)存的低地址中，而數(shù)據(jù)的低位存儲在內(nèi)存的高地址中，小端則相反。
由于需要解碼不同的消息，而不同的消息具有不同的格式，因此和消息對應(yīng)的解碼函數(shù)也是不同的，那么就需要根據(jù)不同的消息格式生成相應(yīng)的解碼函數(shù)。在此每條消息用相應(yīng)C頭文件表示，然后根據(jù)C頭文件配置對應(yīng)的邏輯表。以C頭文件和邏輯表作為輸入，編寫Java代碼利用Eclipse生成相應(yīng)的解碼函數(shù)(解碼器)。
軟件最終產(chǎn)品為解碼器，其為具有解碼功能的C++源代碼，能夠有選擇地解碼出想要查看的KPI的值。解碼器的輸入為配置參數(shù)、C頭文件、邏輯表。配置參數(shù)指出了消息的格式、C頭文件的路徑、邏輯表的路徑、生成的解碼器的輸出路徑以及是大端或小端解碼等。程序根據(jù)C頭文件所定義的消息生成XSD文件，其是與C頭文件中的結(jié)構(gòu)體一一對應(yīng)的，然后根據(jù)產(chǎn)生的XSD文件、邏輯表以及配置參數(shù)生成解碼器。其數(shù)據(jù)流程圖如圖1所示。

2 編碼方法
每條消息都可由相應(yīng)的結(jié)構(gòu)體表示，這些結(jié)構(gòu)體位于C頭文件中，可以寫成樹狀結(jié)構(gòu)的形式。假設(shè)某條消息如圖2所示，由以下結(jié)構(gòu)體表示：其中A p、B p和C p處于同一層，root為根結(jié)構(gòu)體，包含了A p、B p和C p結(jié)構(gòu)體。基本數(shù)據(jù)類型包括整形、字符型、位域等，為葉子結(jié)點，非基本類型數(shù)據(jù)包括結(jié)構(gòu)體數(shù)組、聯(lián)合等，為非葉子結(jié)點。在此，這條消息可由樹狀結(jié)構(gòu)來表示，如圖3所示，root根結(jié)點表示為0000 0000，A結(jié)點表示為0000 0001，a1表示為0001 0001；B結(jié)點表示為0000 0010，b1表示為0001 0010，b2表示為0010 0010；C[0]表示為00000 100，c1表示為0001 0100，c2表示為0010 0100，c3表示為0100 0100；C表示為0000 1000，c4表示為0001 1000，c5表示為0010 1000，c6表示為01001000?？梢妑oot、A、B、C[0]、C[1]為非葉子結(jié)點，是非基本數(shù)據(jù)類型，其余是葉子結(jié)點，是基本數(shù)據(jù)類型。我們稱root為A、B、C[0]和C[1]的父結(jié)點，A是a1的父結(jié)點，B是b1和b2的父結(jié)點，以此類推。注意到，每個父結(jié)點和其子結(jié)點位與()的結(jié)果值都為父結(jié)點，例如：root(0000 0000)A(0000 0001)=root(0000 0000)，A(0000 0001)a1(0001 0001)=A(0000 0001)，B(0000 0010)b2(0010 0010)=B(00 00 0010)。由此，若要取KPI b2和c4的值，那么傳入的目標值為m=b2 |(位或)c4=0011 1010，讓目標值依次與某結(jié)點位與(＆)，如果結(jié)果值等于某結(jié)點，那么說明某結(jié)點的子結(jié)點包含或者是目標值，例如m(0011 1010)＆B(0000 0010)=B(0000 0010)，又已知B是非葉子結(jié)點，故B的子結(jié)點中必定包含目標結(jié)點，然后m依次與b1和b2按位與，mb1 b1，又知b1是葉子結(jié)點，故b1不是要解的目標值，則跳過b1，繼續(xù)解b1的兄弟b2，顯然，mb2=b2，又知b2是葉子結(jié)點，故b2是要解的目標值，以此可得到c4也為目標值。又mA A，又知A是非葉子結(jié)點，故可把A結(jié)點以下的子結(jié)點跳過不解，以此類推，C[1]及其子結(jié)點也可以跳過不解，那么這就大大提高了解碼的效率。

有時候存儲信息不需要一個完整的字節(jié)，只需要占一個或幾個二進制位，這種存儲信息的方式稱為位域。當消息里面包含位域的時候，由于不同的機器可能是大端或者小端。那么就需要定義是按照大端解碼還是按照小端解碼。

3 模塊設(shè)計
系統(tǒng)分為初始化、XSD轉(zhuǎn)換、XSD解析、XSD訪問等四個模塊。
初始化模塊主要進行參數(shù)配置，然后開始運行Eclipse生成解碼器。需要配置的參數(shù)有：消息名稱、C頭文件路徑、邏輯表路徑、解碼器輸出路徑、端類型等。
XSD轉(zhuǎn)換模塊主要進行C頭文件定義的結(jié)構(gòu)體的解析，并生成XSD文件。
XSD解析模塊將XSD文件解析成XSD素對象。這里采用DOM方式進行解析XSD文件，DOM(文檔對象模型)定義了層次化模型來表示XSD文檔，對應(yīng)XSD中的每一個元素定義一個相應(yīng)的類與其一一映射。解析時讀入整個XSD文件，然后在內(nèi)存構(gòu)建一個樹狀結(jié)構(gòu)，每遇到一個元素就實例化一個元素對象。XSD元素對象分為根元素、結(jié)構(gòu)體元素和葉子元素。根元素為整個XSD文件，如圖3中的root，結(jié)構(gòu)體元素為XSD文件的非葉子結(jié)點，如圖3中的A、C[0]等，葉子元素為XSD文件的葉子結(jié)點，其存儲了具體的KPI的值，如圖3中的a1等。
XSD訪問模塊的功能是在XSD對象中查詢邏輯表中的數(shù)據(jù)，并生成解碼器。
邏輯表主要是用來表示在C頭文件中不能表示的邏輯情況，在此有三類常見的邏輯。通常在一個union里面有多個元素，在解碼原始數(shù)據(jù)流時要選擇正確的元素，那么，就必須有一個指引元素，其指明了哪一個元素是被選擇的。如果這個指引元素是在union外，那么就稱其為key out union，相反則稱其為key in union。如果我們要解碼的KPI是一個變長數(shù)組，那么顯然在C頭文件中是沒有辦法描述的，在此我們定義一個變量專門用來定義變長數(shù)組的長度，稱其為variable length array。在某種條件下在數(shù)據(jù)流中有的數(shù)據(jù)是沒有意義的，那么就需要我們定義一個變量來決定其是否有意義，我們稱這樣的變量為optional。

4 結(jié)束語
針對數(shù)據(jù)包中的大量數(shù)據(jù)，解碼器利用樹狀結(jié)構(gòu)的編碼規(guī)則可以快速找到期望的KPI的值，這種對信息提取的高效性，可以大大提高工作效率，增加效益。此解碼器不僅可以單獨用來對數(shù)據(jù)包里面的數(shù)據(jù)進行提取，也可以和其它軟件一起構(gòu)成一個小型測試系統(tǒng)等。