資料壓縮/可執行檔案壓縮

可執行軟體壓縮

在本章中，我們謹慎地區分三種軟體

• "資料壓縮軟體"，用於實現旨在壓縮和解壓縮各種型別檔案的演算法——這正是我們在前幾章中簡單稱為“軟體”的內容。
• "可執行檔案"——磁碟上的檔案，不僅僅是某種資料，供其他程式檢視或編輯，而是程式本身——文字編輯器、文字處理器、影像檢視器、音樂播放器、網路瀏覽器、編譯器、直譯器等。
• "原始碼"——磁碟上人類可讀的檔案，旨在饋送到編譯器（以生成可執行檔案）或饋送到直譯器。

可執行檔案在某些方面類似於英文文字——原始碼甚至更類似——因此，設計和旨在用於英文文字檔案的資料壓縮軟體通常可以很好地處理可執行檔案和原始碼。

但是，一些適用於可執行軟體壓縮的技術和概念在其他任何型別的檔案中都沒有意義，例如

• 自解壓可執行檔案，包括啟動時核心解壓縮
• 死程式碼消除和不可達程式碼消除（與有失真壓縮有一些類似之處）
• 重構冗餘程式碼，以及相反的過程：內聯（與字典壓縮有一些類似之處）
• 某些型別的程式碼大小縮減可能會在區域性使子程式（在隔離測量時）看起來執行速度變慢，但會提高系統的淨效能。特別是，迴圈展開、內聯、“完整跳轉表”與“稀疏測試”，以及靜態連結，都可能使子程式（在隔離測量時）看起來執行速度更快，但可能會增加指令快取未命中、TLB 快取未命中和虛擬記憶體分頁活動，從而降低整個系統的淨效能。
  • 過程抽象
  • 跨跳轉，也稱為尾部合併
• pcode 和執行緒程式碼
• 截至 1998 年，壓縮的抽象語法樹是已知最密集的可執行檔案格式，並且執行速度比位元組碼快。
• JavaScript 壓縮器（有時稱為“JavaScript 壓縮工具”）將 JavaScript 原始碼轉換為執行相同但更小的“壓縮”JavaScript 原始碼。CSS 壓縮器和 HTML 壓縮器的作用類似。
  • 簡單的壓縮器會刪除註釋和不必要的空格。
  • Closure Compiler 會進行更積極的死程式碼消除和單次使用函式內聯。
• 程式碼壓縮
• 執行時解壓縮
• 按需分頁，也稱為延遲載入，一種減少 RAM 使用量的方法
• 共享庫
• PIC 共享庫以及將 Linux 發行版壓縮到一張軟盤或單張軟盤 X 視窗系統瘦客戶端的其他技術。

• 寫時複製和其他減少 RAM 使用量的技術
• 各種減少磁碟儲存的技術，例如僅儲存原始碼（可能已壓縮）和一個即時記憶體編譯器，例如Wikipedia: Tiny C Compiler（或直譯器），而不是僅儲存本機可執行檔案或原始碼和可執行檔案。
• 選擇具有高程式碼密度的機器語言或高階語言
• 各種“最佳化空間”的方法（包括“-Os”編譯器選項）
• 使用 newlib、uClibc 或 sglibc 而不是 glibc
• 用於降低功耗的程式碼壓縮

• 多級或多波解包：檔案以一個非常小的（機器語言）解壓縮器開始——但解壓縮器不會直接將檔案的其餘部分解壓縮為機器語言，而是將其解壓縮為一個大型、複雜的解壓縮器（或直譯器或 JIT 編譯器）（以機器語言表示）以及其他資料；然後大型解壓縮器（或直譯器或 JIT 編譯器）將檔案的其餘部分轉換為機器語言。

壓縮後編譯與編譯後壓縮

編譯的哪個階段可以獲得最佳壓縮效果

• • 壓縮最終的特定於機器的二進位制可執行程式碼？
  • 壓縮原始的與機器無關的文字原始碼？例如，JavaScript 壓縮器。
  • 壓縮一些部分編譯的與機器無關的中間程式碼？例如，“精簡二進位制檔案”或“JAR 格式”

一些非常初步的早期實驗得出了一個令人驚訝的結果，即壓縮的高階原始碼與壓縮的可執行機器程式碼大小大致相同，但壓縮部分編譯的中間表示會生成比兩者都大的檔案。

過濾

許多資料壓縮演算法在將其饋送到熵編碼器之前，會使用“過濾器”或“預處理”或“去相關”原始資料。影像和影片的過濾器通常具有幾何解釋。專門用於可執行軟體的過濾器包括

• "檢測“CALL”指令，將其運算元從相對定址轉換為絕對定址，從而對同一位置的呼叫導致重複的字串，壓縮器可以匹配這些字串，從而提高 80x86 二進位制程式碼的壓縮率。" (Wikipedia: LZX (演算法)#Microsoft Cabinet 檔案)
• 將分支重新編碼為 PC 相對形式

• 與其從零開始單獨解壓應用程式的最新版本，不如從應用程式的舊版本開始，並對其進行修補，直到它與新的最新版本完全相同。這使得更新檔案變得更小，因為它們只需要包含補丁——應用程式舊版本與最新版本之間的差異。這可以被視為一種非常特殊的資料差異化。
  • BSDiff 4 使用的字尾排序演算法構建了相對較短的補丁檔案
  • Colin Percival在他的博士論文中，開發了一種更加複雜的演算法，用於為可執行檔案構建較短的補丁檔案。
• “反彙編”程式碼，將所有絕對地址和偏移量轉換為符號；然後修補反彙編後的程式碼；然後“重新彙編”修補後的程式碼。這使得將應用程式舊版本轉換為新版本的壓縮更新檔案更小。

一些程式設計師認為，匆忙編寫的程式的大小至少是其“所需”大小的 10 倍。

一些程式設計師認為，64 行原始碼對於許多有用的工具來說已經足夠了。

STEPS 專案的目標是“將構建系統所需的程式碼量減少 100 倍、1000 倍、10000 倍甚至更多”。

壓縮的其他大多數應用——甚至這些可執行檔案壓縮技術中的大多數——旨在為人類使用者提供看起來相同的結果，同時改進大多數使用者不會注意到的“後端”內容。但是，其中一些程式壓縮理念（重構、共享庫、使用更高級別的語言、使用特定領域的語言等）減少了人類必須閱讀以理解程式的原始碼量，從而為某些人（程式設計師）帶來了截然不同的體驗。節省的時間可以帶來巨大的成本降低。 這種“壓縮”後的原始碼可以說比原始程式碼更好；與影像壓縮和其他壓縮最多隻能獲得與原始影像相同的結果，而且通常效果更差的領域形成對比。