数据压缩/可执行文件压缩

可执行软件压缩

在本章中，我们谨慎地区分三种软件

• "数据压缩软件"，用于实现旨在压缩和解压缩各种类型文件的算法——这正是我们在前几章中简单称为“软件”的内容。
• "可执行文件"——磁盘上的文件，不仅仅是某种数据，供其他程序查看或编辑，而是程序本身——文本编辑器、文字处理器、图像查看器、音乐播放器、网络浏览器、编译器、解释器等。
• "源代码"——磁盘上人类可读的文件，旨在馈送到编译器（以生成可执行文件）或馈送到解释器。

可执行文件在某些方面类似于英文文本——源代码甚至更类似——因此，设计和旨在用于英文文本文件的数据压缩软件通常可以很好地处理可执行文件和源代码。

但是，一些适用于可执行软件压缩的技术和概念在其他任何类型的文件中都没有意义，例如

• 自解压可执行文件，包括启动时内核解压缩
• 死代码消除和不可达代码消除（与有损压缩有一些类似之处）
• 重构冗余代码，以及相反的过程：内联（与字典压缩有一些类似之处）
• 某些类型的代码大小缩减可能会在局部使子程序（在隔离测量时）看起来运行速度变慢，但会提高系统的净性能。特别是，循环展开、内联、“完整跳转表”与“稀疏测试”，以及静态链接，都可能使子程序（在隔离测量时）看起来运行速度更快，但可能会增加指令缓存未命中、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 倍甚至更多”。

压缩的其他大多数应用——甚至这些可执行文件压缩技术中的大多数——旨在为人类用户提供看起来相同的结果，同时改进大多数用户不会注意到的“后端”内容。但是，其中一些程序压缩理念（重构、共享库、使用更高级别的语言、使用特定领域的语言等）减少了人类必须阅读以理解程序的源代码量，从而为某些人（程序员）带来了截然不同的体验。节省的时间可以带来巨大的成本降低。 这种“压缩”后的源代码可以说比原始代码更好；与图像压缩和其他压缩最多只能获得与原始图像相同的结果，而且通常效果更差的领域形成对比。