（二） 固定位長(cháng)算法（Fixed Bit Length Packing）
這種算法是把文本用需要的最少的位來(lái)進(jìn)行壓縮編碼。
比如八個(gè)十六進(jìn)制數：1，2，3，4，5，6，7，8。轉換為二進(jìn)制為：00000001，00000010，00000011，00000100，00000101，00000110，00000111，00001000。每個(gè)數只用到了低4位，而高4位沒(méi)有用到（全為0），因此對低4位進(jìn)行壓縮編碼后得到：0001，0010，0011，0100，0101，0110，0111，1000。然后補充為字節得到：00010010，00110100，01010110，01111000。所以原來(lái)的八個(gè)十六進(jìn)制數縮短了一半，得到4個(gè)十六進(jìn)制數：12，34，56，78。
這也是比較常見(jiàn)的壓縮算法之一。
（三） RLE算法
這種壓縮編碼是一種變長(cháng)的編碼，RLE根據文本不同的具體情況會(huì )有不同的壓縮編碼變體與之相適應，以產(chǎn)生更大的壓縮比率。
變體1：重復次數+字符
文本字符串：A A A B B B C C C C D D D D，編碼后得到：3 A 3 B 4 C 4 D。
變體2：特殊字符+重復次數+字符
文本字符串：A A A A A B C C C C B C C C，編碼后得到：B B 5 A B B 4 C B B 3 C。編碼串的最開(kāi)始說(shuō)明特殊字符B，以后B后面跟著(zhù)的數字就表示出重復的次數。
變體3：把文本每個(gè)字節分組成塊，每個(gè)字符最多重復 127 次。每個(gè)塊以一個(gè)特殊字節開(kāi)頭。那個(gè)特殊字節的第 7 位如果被置位，那么剩下的7位數值就是后面的字符的重復次數。如果第 7 位沒(méi)有被置位，那么剩下 7 位就是后面沒(méi)有被壓縮的字符的數量。例如：文本字符串：A A A A A B C D E F F F。編碼后得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）
以上3種不RLE變體是最常用的幾種，其他還有很多很多變體算法，這些算法在Winzip Winrar這些軟件中也是經(jīng)常用到的。
（四） LZ77算法
LZ77算法是由 Lempel-Ziv 在1977發(fā)明的，也是GBA內置的壓縮算法。LZ77算法有許多派生算法(這里面包括 LZSS算法)。它們的算法原理上基本都相同，無(wú)論是哪種派生算法，LZ77算法總會(huì )包含一個(gè)動(dòng)態(tài)窗口（Sliding Window）和一個(gè)預讀緩沖器（Read Ahead Buffer）。動(dòng)態(tài)窗口是個(gè)歷史緩沖器，它被用來(lái)存放輸入流的前n個(gè)字節的有關(guān)信息。一個(gè)動(dòng)態(tài)窗口的數據范圍可以從 0K 到 64K，而LZSS算法使用了一個(gè)4K的動(dòng)態(tài)窗口。預讀緩沖器是與動(dòng)態(tài)窗口相對應的，它被用來(lái)存放輸入流的前n個(gè)字節，預讀緩沖器的大小通常在0 – 258 之間。這個(gè)算法就是基于這些建立的。用下n個(gè)字節填充預讀緩存器（這里的n是預讀緩存器的大?。?。在動(dòng)態(tài)窗口中尋找與預讀緩沖器中的最匹配的數據，如果匹配的數據長(cháng)度大于最小匹配長(cháng)度 （通常取決于編碼器，以及動(dòng)態(tài)窗口的大小，比如一個(gè)4K的動(dòng)態(tài)窗口，它的最小匹配長(cháng)度就是2），那么就輸出一對〈長(cháng)度（length），距離（distance）〉數組。長(cháng)度(length)是匹配的數據長(cháng)度，而距離(distance)說(shuō)明了在輸入流中向后多少字節這個(gè)匹配數據可以被找到。
例如：（假設一個(gè) 10個(gè)字節的動(dòng)態(tài)窗口, 以及一個(gè)5個(gè)字節的預讀緩沖器）
文本：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動(dòng)態(tài)窗口 預讀緩存器
動(dòng)態(tài)窗口中包含10個(gè)A ，這就是最后讀取的10個(gè)字節。預讀緩沖器包含了 B A B A A。編碼的第一步就是尋找動(dòng)態(tài)窗口與預讀緩存器相似長(cháng)度大于2的字節部分。在動(dòng)態(tài)窗口中找不到B A B A A，所以B就被按照字面輸出。然后動(dòng)態(tài)窗口滑過(guò)1個(gè)字節，現在暫時(shí)輸出了一個(gè)B。
第二步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動(dòng)態(tài)窗口 預讀緩存器
現在預讀緩沖器包含A B A A A，然后再和動(dòng)態(tài)窗口進(jìn)行比較。這時(shí)，在動(dòng)態(tài)窗口找到了相似長(cháng)度為2的A B，因此一對〈長(cháng)度, 距離〉就被輸出了。長(cháng)度(length)是2 并且向后距離也是2，所以輸出為<2,2>，然后動(dòng)態(tài)窗口滑過(guò)2個(gè)字節?，F在已經(jīng)輸出了B <2,2>。
第三步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動(dòng)態(tài)窗口 預讀緩存器
繼續上面的方法得到輸出結果<5,8>?，F在已經(jīng)輸出了B <2,2> <5,8>。
最終的編碼結果是：A A A A A A A A A A A B <2,2> <5,8>。
但數組是無(wú)法直接用二進(jìn)制來(lái)表示的，LZ77會(huì )把編碼每八個(gè)數分成一組，每組前用一個(gè)前綴標示來(lái)說(shuō)明這八個(gè)數的屬性。比如數據流：A B A C A C B A C A按照LZ77的算法編碼為：A B A C<2,2> <4,5>，剛好八個(gè)數。按照LZ77的規則，用“0”表示原文輸出，“1”表示數組輸出。所以這段編碼就表示為：00001111B（等于0FH），因此得到完整的壓縮編碼表示：F A B A C 2 2 4 5。雖然表面上只縮短了1個(gè)字節的空間，但當數據流很長(cháng)的時(shí)候就會(huì )突出它的優(yōu)勢，這種算法在zip格式中是經(jīng)常用到。
除此之外還有很多壓縮算法，像霍夫曼編碼（Huffman Encoding）等等。這些編碼也是非常的著(zhù)名而且壓縮效率極高，不過(guò)這些編碼的算法相對比較繁瑣，規則也很復雜，由于篇幅就不逐一介紹了。如果大家對這方面感興趣可以到網(wǎng)站相關(guān)網(wǎng)站查詢(xún)資料。
小結：這一節介紹的幾種算法在GBA上是比較容易遇到的典型算法，但絕不是說(shuō)只有這幾種，還是有很多時(shí)候都得自己ASM跟蹤進(jìn)行分析，這里介紹給大家希望能拓展大家的思維，方便進(jìn)行程序分析，對于一切的問(wèn)題ASM才是萬(wàn)能的。
聯(lián)系客服
