1、應(yīng)用場景

對于高精度采樣結(jié)果，其數(shù)值最大可能需要3字節(jié)，最少1字節(jié)，采用標(biāo)準(zhǔn)C的基礎(chǔ)數(shù)據(jù)類型，U16太小無法滿足需求，U32則浪費(fèi)內(nèi)存。當(dāng)樣本量很大時，其占用的空間問題便突顯出來。能否采用變長數(shù)據(jù)類型存儲呢?對小數(shù)據(jù)采用U8，大數(shù)據(jù)采用U32，隨著數(shù)值大小動態(tài)分配存儲空間，就是本文的討論的重點(diǎn)。

2、數(shù)據(jù)去冗余

U32的空間其數(shù)值范圍最大接近2^32，該值非常大，實際數(shù)值范圍遠(yuǎn)小于它，高位必然為0。例如U32表示1使用0x00000001，前面位都是0，其表達(dá)的數(shù)值和U8的0x01是一樣的，前面重復(fù)的一串0屬于冗余數(shù)據(jù)區(qū)，是可以剔除的。

假設(shè)5個數(shù)據(jù)D0..4，原本每個數(shù)據(jù)固定為U32類型，將其高位冗余0去掉，再拼接到U8的一維數(shù)組，則占用的空間和大大縮小。思路的核心是把 U32 或者U64 數(shù)組裁剪后拼接成U8 數(shù)組，同時確保使用時可

根據(jù)U8 數(shù)組中存儲的信息將對應(yīng)的數(shù)值還原。

假設(shè)有0x00000001、0x00000101、0x00000001三個數(shù)據(jù)，其有效部分是0x01、0x0101、0x01，如果直接拼接在一起，則沒法區(qū)分0x01010101的含義。因此數(shù)據(jù)在去掉高位0之后，還需進(jìn)行編碼標(biāo)記，便于后續(xù)解析還原。

3、數(shù)據(jù)編碼

數(shù)據(jù)編碼的主要作用是標(biāo)記當(dāng)前數(shù)據(jù)占用多少連續(xù)字節(jié)，有兩種方案：

1、固定位來定義字節(jié)長度(2位可以表示4字節(jié))

一字節(jié)：00******

二字節(jié)：01******，00******

三字節(jié)：10******，01******，00******

四字節(jié)：11******，10******，01******，00******

五字節(jié)：使用2位不支持

每個字節(jié)的最高2位表示屬于原始數(shù)據(jù)的第幾個(從0開始)，前面舉例的3個字節(jié)可以表示為：

0x01 編碼后二進(jìn)制為 00-000001，最高2位為0，表示當(dāng)前是編碼后的數(shù)據(jù)的最后一個字節(jié);

0x0101 編碼后二進(jìn)制為 01-000001--00-000001 解析時取每個字節(jié)的2位判斷，若為00則表示一個編碼數(shù)值結(jié)束。

因為前面2位固定用于標(biāo)記字節(jié)數(shù)，每個字節(jié)實際可用范圍只有6位，如果原數(shù)據(jù)位1000 0001，則最高兩位的10需要再占用一個字節(jié)表示，最終編碼為 01-000010--00-000001。

這種編碼方式，所有字節(jié)有效位是固定的，編解碼實現(xiàn)容易。缺點(diǎn)是4字節(jié)只有24位有效數(shù)據(jù)，假如原數(shù)據(jù)最大到25位，則每個字節(jié)分配3位來表示，不過這種大數(shù)據(jù)一般嵌入式很少使用。

2、字節(jié)最高位表示還有剩余數(shù)據(jù)，借鑒UTF8的編碼方式

一字節(jié)：0*******

兩字節(jié)：110*****，10******

三字節(jié)：1110****，10******，10******

四字節(jié)：11110***，10******，10******，10******

五字節(jié)：111110**，10******，10******，10******，10******

六字節(jié)：1111110*，10******，10******，10******，10******，10******

七字節(jié)：不支持

這種編碼方式，最高字節(jié)的有效位是變化的，其它字節(jié)有效位是6位。

兩種編碼方式的選取，主要是依據(jù)原始數(shù)據(jù)分布概率，如果原數(shù)據(jù)范圍在24位內(nèi)，則前面固定位的方式占優(yōu)，超過32位內(nèi)則動態(tài)的合適，如果數(shù)據(jù)范圍在16位內(nèi)則沒必要如此折騰。

關(guān)于源碼或者更多交流，請關(guān)注微信公眾號 嵌入式系統(tǒng)。

4、數(shù)據(jù)訪問

原數(shù)據(jù)每個值占用固定字節(jié)長度，可以方便的使用數(shù)組下標(biāo)遍歷，即地址偏移為(單個數(shù)字占用的字節(jié)數(shù))*(第幾個)，編碼為變長數(shù)據(jù)后，要想取到某個原數(shù)據(jù)編碼后的值，如果從數(shù)組頭開始遍歷效率是相當(dāng)?shù)偷?，有沒有更好的辦法呢?

將前面一維數(shù)組轉(zhuǎn)為二維數(shù)組，每行數(shù)組按前面的編碼實現(xiàn)，數(shù)據(jù)中預(yù)留4個字節(jié)，每行占滿時尾部標(biāo)記當(dāng)前行結(jié)束累計包括多少個原始數(shù)據(jù)，下個編碼值則存入下一行，依次類推。

圖片如上圖，二維數(shù)組的一行就退化為一維數(shù)組，每行在固定位置標(biāo)記存儲的數(shù)量。如果需要查找C10，先按標(biāo)記數(shù)目的字節(jié)地址遍歷，則可以找到第2行(從0開始)為13，表示需要查找的數(shù)據(jù)在本行，只需要遍歷該行，從C9開始往后查詢。

5、總結(jié)

選擇合適的數(shù)據(jù)類型的減小存儲空間，對大范圍的數(shù)據(jù)使用變長的類型拼接存儲，犧牲了部分時間，但節(jié)約了ram或flash空間，對資源緊缺的嵌入式設(shè)備具有一定的價值。

本文轉(zhuǎn)載自微信公眾號「嵌入式系統(tǒng)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系嵌入式系統(tǒng)公眾號。